3 ms·

>I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overu

>I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common. To give some context, iterating over an array of three small items takes worst case roughly 100ns(cache miss), best case 1ns(l1 cache hit). Most common hashmap implementations (like std::unordered_map) dynamically allocate items so they're stored randomly in memory, giving roughly 300ns worst case(3 cache misses), 3ns best case(3 l1 cache hits) for iterating over them. So using a hash map is going to be 3x slower without even accounting for the time spent hashing, and 3x more likely to hit the worse case due to requiring three cachelines still in the l1 cache for best performance as opposed to just one. If regularly adding/deleting items, using a std::unordered_map would literally be orders of magnitude slower due to using malloc/free for each item added/removed.

Bancakes 5y ago
How did you get exactly a 3x slowdown? I thought unordered_map is a vector of vectors aka separate chaining?
- MauranKilom 5y ago
  No. unordered_map buckets are linked lists of nodes (key + value pairs). So you have one indexing into the bucket array to retrieve the list pointer, and then you may or may not have to chase an arbitrarily long linked list. But the nodes are necessarily allocated separately, so (assuming the bucket array is in cache [previous post should say 4 cachelines, not 3] and you don't have to chase beyond the first list element) you still have that indirection somewhere into memory. This all comes from the specification requiring even load factors arbitrarily close to 1 and to still have amortized constant time insertion, lookup and deletion.
  - Bancakes 5y ago
    That's horrid. I have some old code where adjacency matrices are unordered maps of unordered maps. Yikes.
eru 5y ago
Yes. Pointer chasing datastructures really want to live in a language that has a compacting and relocating garbage collector. If all your objects are doomed to die where there were born, you better put them in the right place. (So an array is good for C-like languages.)
- tankenmate 5y ago
  Or even better yet, use a language with a sensible SSA implementation that can identify local only variables and allocate them on the stack (like golang).
  - eru 5y ago
    That technique is useful _and_ independent of what I suggested. Ie you can do it whether you have garbage collection or not. Though it's less important on languages with compacting garbage collectors, because there allocation can be just a pointer bump, which is pretty similar to what you do for stack allocation. See also this Scheme implementation which allocates everything on the C stack: > Previous Schemes for implementing full tail-recursion when compiling into C have required some form of "trampoline" to pop the stack. We propose solving the tail-recursion problem in the same manner as Standard ML of New Jersey, by allocating all frames in the (garbage-collected) heap. The Scheme program is translated into continuation-passing style, so the target C functions never return. The C stack pointer then becomes the allocation pointer for a Cheney-style copying garbage collection scheme. Our Scheme can use C function calls, C arguments, C variable-arity functions, and separate compilation without requiring complex block-compilation of entire programs. Introduction IEEE Scheme [IEEE90] requires that all functions be properly tail-recursive, in order that tail-recursive programs not require an unbounded amount of stack space. Several Scheme compilers have targeted the C language [Bartlett89], because C is an efficient systems programming language which is available on nearly ev... http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7143 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7... Do keep in mind that some languages like Scheme (because of call/cc) and Haskell (because of laziness) in general don't have a single stack. See eg https://en.wikipedia.org/wiki/Parent_pointer_tree https://en.wikipedia.org/wiki/Parent_pointer_tree for what Scheme needs to do. Of course, allocation of variables with hierarchically nested lifetimes (ie stack allocation) is still an important and common special case that your compiler/interpreter should probably recognize and handle well. Escape analysis is a well studied field after all. https://en.wikipedia.org/wiki/Escape_analysis https://en.wikipedia.org/wiki/Escape_analysis

Bancakes 5y ago

How did you get exactly a 3x slowdown? I thought unordered_map is a vector of vectors aka separate chaining?

MauranKilom 5y ago
No. unordered_map buckets are linked lists of nodes (key + value pairs). So you have one indexing into the bucket array to retrieve the list pointer, and then you may or may not have to chase an arbitrarily long linked list. But the nodes are necessarily allocated separately, so (assuming the bucket array is in cache [previous post should say 4 cachelines, not 3] and you don't have to chase beyond the first list element) you still have that indirection somewhere into memory. This all comes from the specification requiring even load factors arbitrarily close to 1 and to still have amortized constant time insertion, lookup and deletion.
- Bancakes 5y ago
  That's horrid. I have some old code where adjacency matrices are unordered maps of unordered maps. Yikes.

eru 5y ago

Yes. Pointer chasing datastructures really want to live in a language that has a compacting and relocating garbage collector. If all your objects are doomed to die where there were born, you better put them in the right place. (So an array is good for C-like languages.)

tankenmate 5y ago
Or even better yet, use a language with a sensible SSA implementation that can identify local only variables and allocate them on the stack (like golang).
- eru 5y ago
  That technique is useful _and_ independent of what I suggested. Ie you can do it whether you have garbage collection or not. Though it's less important on languages with compacting garbage collectors, because there allocation can be just a pointer bump, which is pretty similar to what you do for stack allocation. See also this Scheme implementation which allocates everything on the C stack: > Previous Schemes for implementing full tail-recursion when compiling into C have required some form of "trampoline" to pop the stack. We propose solving the tail-recursion problem in the same manner as Standard ML of New Jersey, by allocating all frames in the (garbage-collected) heap. The Scheme program is translated into continuation-passing style, so the target C functions never return. The C stack pointer then becomes the allocation pointer for a Cheney-style copying garbage collection scheme. Our Scheme can use C function calls, C arguments, C variable-arity functions, and separate compilation without requiring complex block-compilation of entire programs. Introduction IEEE Scheme [IEEE90] requires that all functions be properly tail-recursive, in order that tail-recursive programs not require an unbounded amount of stack space. Several Scheme compilers have targeted the C language [Bartlett89], because C is an efficient systems programming language which is available on nearly ev... http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7143 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7... Do keep in mind that some languages like Scheme (because of call/cc) and Haskell (because of laziness) in general don't have a single stack. See eg https://en.wikipedia.org/wiki/Parent_pointer_tree https://en.wikipedia.org/wiki/Parent_pointer_tree for what Scheme needs to do. Of course, allocation of variables with hierarchically nested lifetimes (ie stack allocation) is still an important and common special case that your compiler/interpreter should probably recognize and handle well. Escape analysis is a well studied field after all. https://en.wikipedia.org/wiki/Escape_analysis https://en.wikipedia.org/wiki/Escape_analysis