48 ms·

Maps can be ordered though. In Python they are, and keyword arguments in Python are implemented as these ordered maps (dicts), and they disallow duplicate keys.

by boxed 3y ago

Maps can be ordered though. In Python they are, and keyword arguments in Python are implemented as these ordered maps (dicts), and they disallow duplicate keys. So I do understand how it can be confusing coming from another language for example.

sph 3y ago
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. The former requires taking 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 pointer equality comparison (due to keywords being interned strings). 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.
- boxed 3y ago
  > 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.
- hinkley 3y ago
  Ordered maps are usually a hybrid linked list. When iterating you can traverse the linked list data, rather than the buckets.

by boxed 3y ago

sph 3y ago

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. The former requires taking 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 pointer equality comparison (due to keywords being interned strings). 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.

boxed 3y ago
> 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.
hinkley 3y ago
Ordered maps are usually a hybrid linked list. When iterating you can traverse the linked list data, rather than the buckets.