You (Probably) Shouldn't use a Lookup Table

[irthomasthomas]

• You (Probably) Shouldn't use a Lookup Table

You (Probably) Shouldn't use a Lookup Table

DESCRIPTION: SPECULATIVE BRANCHES
THOUGHTS ON SOFTWARE, HARDWARE, PERFORMANCE, MATH, AND SIMILAR TOPICS
HOME
ABOUT ME
CATEGORIES
TAGS
CONSULTING

I have been working on another post recently, also related to division, but I wanted to address a comment I got from several people on the previous division article. This comment invariably follows a lot of articles on using math to do things with chars and shorts. It is: “why are you doing all of this when you can just use a lookup table?”

Even worse, a stubborn and clever commenter may show you a benchmark where your carefully-crafted algorithm performs worse than their hamfisted lookup table. Surely you have made a mistake and you should just use a lookup table. Just look at the benchmark!

When you have only 8 or 16 bits of arguments, it is tempting to precompute all of the answers and throw them in a lookup table. After all, a table of 256 8-bit numbers is only 256 bytes, and even 65536 16-bit numbers is well under a megabyte. Both are a rounding error compared to the memory and code footprints of software today. A lookup table is really easy to generate, and it’s just one memory access to find the answer, right?

The correct response to the lookup table question is the following: If you care about performance, you should almost never use a lookup table algorithm, despite what a microbenchmark might say.

URL: https://specbranch.com/posts/lookup-tables/

Suggested labels

{'label-name': 'performance', 'label-description': 'Analyzing software efficiency and speed considerations', 'confidence': 64.93}

[irthomasthomas]

Related content

#689 - Similarity score: 1.0

#655 - Similarity score: 0.83

#161 - Similarity score: 0.81

#654 - Similarity score: 0.81

#641 - Similarity score: 0.81

#639 - Similarity score: 0.8