Hmmm... I argue that the hash is nearly free actually.
An unordered_map traversal is probably DDR4 latency bound. That's ~50-nanoseconds (200 clock ticks) per access. What's the CPU going to do in that time?
Well, spending 10 to 20 clock ticks on a typical hash algorithm is fine. Then it will wait the other 180 clock ticks for RAM. If you got hyperthreading, maybe the CPU will go to another thread and do meaningful work while waiting for RAM... but... I think you get the gist.
Even IF the hash were free, the CPU is waiting for RAM anyway. So you got plenty of time to make that hash worthwhile. Even an integer division/modulo operator (worst case ~80 clock ticks) can fit in there while waiting for RAM, with plenty of room to spare.
I guess if everything was in L1 cache, the story is a bit different. A lot of "depends", depends on the data, the access frequency, etc. etc.
Hmmm... I argue that the hash is nearly free actually.
An unordered_map traversal is probably DDR4 latency bound. That's ~50-nanoseconds (200 clock ticks) per access. What's the CPU going to do in that time?
Well, spending 10 to 20 clock ticks on a typical hash algorithm is fine. Then it will wait the other 180 clock ticks for RAM. If you got hyperthreading, maybe the CPU will go to another thread and do meaningful work while waiting for RAM... but... I think you get the gist.
Even IF the hash were free, the CPU is waiting for RAM anyway. So you got plenty of time to make that hash worthwhile. Even an integer division/modulo operator (worst case ~80 clock ticks) can fit in there while waiting for RAM, with plenty of room to spare.
I guess if everything was in L1 cache, the story is a bit different. A lot of "depends", depends on the data, the access frequency, etc. etc.