3 ms·
Especially when an ordered map is backed by a binary tree (TreeMap), which is the worst data structure. Btree ordered maps good, hash tables good (if point que
by loeg 7y ago
Especially when an ordered map is backed by a binary tree (TreeMap), which is the worst data structure. Btree ordered maps good, hash tables good (if point queries are sufficient); binary trees have terrible cache locality.
- kccqzy 7y agoCache locality issues can be fixed by using a good allocator (or a good compacting GC).
- AstralStorm 7y agoHow can an allocator optimize the layout of a dynamically sized structure that's being changed without compacting? Now, compacting is an O(n) memory move plus additional calculation to figure out optimal-ish layout. (Can be amortized, but it's same as amortizing hash table resizing. Optimal layout cannot be decided without profiling, and that's expensive.)