4 ms·

While not entirely true... One counter-example I can think of is that of Judy trees - http://judy.sourceforge.net/ http://judy.sourceforge.net/ which uses more

While not entirely true... One counter-example I can think of is that of Judy trees - http://judy.sourceforge.net/ http://judy.sourceforge.net/ which uses more instructions to try to keep the data in cache for as long as possible. A (CPU) cache-line fill is additional time required to do a read reference from RAM when a word is not found in cache. In today's computers the time for a cache-line fill is in the range of 50..2000 machine instructions. Therefore a cache-line fill should be avoided when fewer than 50 instructions can do the same job. More info at http://judy.sourceforge.net/doc/10minutes.htm http://judy.sourceforge.net/doc/10minutes.htm

anamax 16y ago
> One counter-example I can think of is that of Judy trees - http://judy.sourceforge.net/ http://judy.sourceforge.net/ which uses more instructions to try to keep the data in cache for as long as possible. It's not a counter-example. The cost of running a program includes the cost to access memory as well as the cost of executing instructions. It also includes the cost to access disk/flash.
kragen 16y ago
BTW, the HAT-trie is supposedly a speed improvement over Judy and all other known data structures for that problem. I don't yet understand it well enough to evaluate that claim.