Home > Programming > Pre-calculated Look-up Tables

Pre-calculated Look-up Tables

October 19, 2009

For many years it’s been common knowledge that pre-computing values and storing them in a look-up table is often much more efficient. That may still be true on the resource constrained embedded side; however, on the desktop side this may not be the case due to the multi-level caching schemes used in CPU’s today.

I stumbled across the following quote in a un-related article:

“There seems to be a common fallacy among programmers that using memory is good: on current hardware it is often much faster to recompute values than to have to reference memory to get a precomputed value. A full cache miss can be hundreds of cycles, and hundreds of times the power consumption of an instruction that hits in the first level cache. Making things smaller almost always makes them faster (and lower power). Similarly, it can be much faster to redraw an area of the screen than to copy a saved image from RAM to a screen buffer. Many programmer’s presumptions are now completely incorrect and we need to reeducate ourselves.”

This particular quote jumped out at me because it goes opposite to what I have known for a long time. Goes to show that profiling is really the only way to really optimize a system.

The quote is part of a wide ranging unrelated interview with Jim Gettys talking about the “One Laptop Per Child” project. http://lwn.net/Articles/188060/

Categories: Programming
%d bloggers like this: