I''ve heard that large look up tables can cause cache problems on new computers. What''s happening? What are the problems and why do they occur? Digital Radiation

Modern processors are very, very, fast. Memory is slow. Loading a value from memory into a register takes forever (relative to the processor). To help this you have a cache of fast memory. When the processor wants to read some memory it checks the cache first and if it''s there it can read it a lot faster.

Data caches only work if you have "data locality" - i.e. most of the time you''re reading/writing stuff near what you''ve been reading/writing in the past. If you''ve got a huge lookup table that you''re accessing randomly you could destroy your locality and performance will suffer. Your program will still work correctly though. Occasionally it''s better to compute a value rather than looking it up because of all this.

Whether or not any of this effects you depends entirely on your particular situation - how much cache you''ve got, the data access paterns in your app, what processor you''re using, etc, etc. Gross generalities like "large lookup tables are always bad" don''t mean anything. You need to profile to see if it''s actually effecting you or not.

-Mike

Still there''s a problem if you only profile on one computer (or a bunch of similar (with similar chipsets)), since the size of cache (as mentioned) differ between different chipsets, but also other things like the number of addresses that can collide before one is thrown out of the cache differ (cache associativity), will make your code run much slower on some systems if optimized to specific for one (or a few) system(s). Thus generalities like "large lookup tables are always bad" actually do mean something, but how large and how they are accessed are the important things.

/Andreas

I can attest to this. I am using 16 bit color in my game, and I''m alpha blending shadows of the characters flying over the land. As it stands, I am calculating a blend 50% black with the pixel over which the shadow will show, and a while ago I decided to try a lookup table in hopes that it would speed it up a lot. So I made a huge lookup table (65536 entries) with one entry for each color blended 50% with black.

On one system, the speed stayed the same, but on another, the framerate went down 15-20 fps!

So anyway, I went back to calculating on the fly

As long as you can keep tables small enough the speed difference might be worth it, but anything really huge is probably better off being done when it''s needed.