Re:Thoughts on Elixir, Phoenix and LiveView after 18 months ...
by boxed on Monday August 14, 2023 @07:56AM
(#37120005)
> It's just a matter of algorithmic complexity. A hashmap, ordered or not, is more complicated than a linked list, which is what Keywords are built upon.
You mean implementation complexity right? Anyway, I was talking about semantics, not performance or implementation.
> If you have less than 10 elements, a linked list will always be faster than any hashmap on modern CPUs.
Citation needed. That personally sounds totally bonkers to me. Faster HOW? If the pointers of each node in the linked list are far apart in memory the L1/L2 cache misses will absolutely destroy the performance.
I think you're talking from a ton of assumptions that you haven't stated. If the list is that short, why isn't it a contiguous array in memory? That's going to be way smaller and way way faster in every way.
The former requires turning an arbitrary piece of data, hashing it to an integer, and indexing a cell based off this value, dealing with potential collisions on the way. In C terms it's 50 lines long.
The latter is a simple iteration and string comparison. In C terms it's 5 lines long.
It is confusing if you've never programmed close to the metal and only know high level languages. Maps are good for data that you need to access in random order, linked lists/keyword lists for data that either you access in linear order, or it is so small the overhead of a map is too much.
If you have less than 10 elements, a linked list will always be faster than any hashmap on modern CPUs.