> The key to making programs fast is
> to make them do practically nothing.
> ;-)
is a paraphrase of something I posted here a long time ago:
> You can't make programs run faster,
> you can only make them do less.
While not entirely true (and Ph.D. theses have been written about the corners where it's wrong) it's an excellent start when you have to make a program run faster.
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.
You can make them do less, but you can also make them spend less time doing nothing at all. Concurrency optimizations and prefetching fall into this category.
Comments
This:
is a paraphrase of something I posted here a long time ago: While not entirely true (and Ph.D. theses have been written about the corners where it's wrong) it's an excellent start when you have to make a program run faster.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.
I have your comment taped over my monitor :)
You can make them do less, but you can also make them spend less time doing nothing at all. Concurrency optimizations and prefetching fall into this category.