4 ms·
Those arrays usually contain pointers to other data structures, allocated on the heap in different places, which often results in a cache miss / cpu stall. It's
by collinvandyck76 3y ago
Those arrays usually contain pointers to other data structures, allocated on the heap in different places, which often results in a cache miss / cpu stall. It's still a constant time lookup, but for small values of N, avoiding the cache misses is often faster, even with an O(N) algorithm.
- arp242 3y agoAlso you do need to calculate that hash key, which isn't free either. I generally found that lookups in lists are faster than hashmaps for sizes smaller than about 10 or so, but details may vary on the exact implementation etc.
- seanhunter 3y agoThis is the origin of the famous quote from Rob Pike which goes something like "Simple data structures are better when n is small and n is almost always small". It hasn't aged as well as he might have liked, given that sometimes n gets really really big now, but the point still holds- in lots of common use cases simple algorithms with low constant factors dominate fancy algorithms with theoretically better O() up to a certain threshold data scale. In this case it would presumably be up to a certain number of routes and/or ip addresses.