4 ms·
Is there a way to make these data structures hardware friendly? So that SIMD instructions can be used, memory is traversed continuously, without multiple pointe
by fluffy87 6y ago
Is there a way to make these data structures hardware friendly? So that SIMD instructions can be used, memory is traversed continuously, without multiple pointer indirections, etc?
Are there any blogposts about this?
- T0pH4t 6y agoYou can do this at the hashtable level when comparing keys. I think TBB does it. https://software.intel.com/en-us/node/506171 https://software.intel.com/en-us/node/506171
- jasonwatkinspdx 6y agoFor chaining hash tables like this you can use a linked list of buckets where each bucket allows multiple entries, and entries can be scanned with SIMD operations. The downside is it considerably complicates the insertion/update logic, so depending on the workload it may be a net performance loss. If the hash table is designed for concurrency the extra complexity can very likely lead to tricky to understand bugs or performance cliffs.
- jleahy 6y agoThere are many ways, and they look nothing like this of course. For a hint, have a look at how a CPU implements the LRU cache (eg. L1, L2). It’s not rocket science.