Timeline for How can I associate algorithm-specific data to the objects it works with, efficiently yet cleanly?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2021 at 20:11 | answer | added | radarbob | timeline score: 0 | |
| Jan 6, 2021 at 15:21 | answer | added | B. Ithica | timeline score: 1 | |
| Dec 18, 2020 at 6:43 | comment | added | rwong | The reason I focused on the key bit-width and hash function, is because I know that certain compilers (e.g. MSVC) uses a byte-oriented hash function FNV1a. When applied to 64-bit key types, the function executes its inner loop 8 times. When the hash table is used in certain types of algorithms (without further customizations or optimizations), the computation of hash function can show up prominently on CPU profiler results. Since a hash table must store the actual key in memory, a wide key type means it will consume more memory, which occupies space on the CPU cache. | |
| Dec 18, 2020 at 6:37 | history | reopened | Doc Brown design Users with the design badge or a synonym can single-handedly close design questions as duplicates and reopen them as needed. | ||
| Dec 18, 2020 at 6:35 | history | closed | Doc Brown design Users with the design badge or a synonym can single-handedly close design questions as duplicates and reopen them as needed. | Duplicate of Is micro-optimisation important when coding? | |
| Dec 18, 2020 at 6:34 | comment | added | Doc Brown | 2~5%, that's all? I am under the impression you are barking the wrong tree. Please have a look into Is micro-optimisation important when coding? | |
| Dec 18, 2020 at 5:07 | comment | added | rwong | A low-level CPU execution profiler (one that has low overhead and observes the "currently executing instruction address" on a periodic timer interrupt) can also help identify where the performance difference happens. | |
| Dec 18, 2020 at 4:44 | comment | added | 1201ProgramAlarm | Possibly create algorithm-specific classes, that store the data the algorithm requires and the pointer to the associated node. Going from the node back to the extra info can be done using an index added to the Node that identifies the extra data stored with it. | |
| Dec 18, 2020 at 3:39 | comment | added | rwong |
I would consider using a hash table as the cleanest approach with good performance. As an alternative, have you considered: (1) instead of using a 64-bit type (a pointer) as key, how about using a 32-bit type (if you can create a 32-bit unique identifier for each node) ? (2) have you considered providing your own key hash function for the key type? (3) have you investigated preallocation for your hash table? These three questions summarize my own experience in optimizing C++ unordered_map performance.
|
|
| Dec 18, 2020 at 3:04 | history | edited | Helloer | CC BY-SA 4.0 |
deleted 4 characters in body
|
| Dec 18, 2020 at 2:59 | history | asked | Helloer | CC BY-SA 4.0 |