One counter-example I can think of is that of Judy trees - 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.
> One counter-example I can think of is that of Judy trees - 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.
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.
Comments
While not entirely true...
One counter-example I can think of is that of Judy trees - 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
> One counter-example I can think of is that of Judy trees - 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.
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.