TEC Techniques Technique
Precomputation and lookup tables
Also known as: lookup table · table in advance · space–time tradeoff · table-driven CRC · CRC-32
If a function with a small number of possible inputs is called millions of times, its answers can be computed in advance and taken from a table. This is how the CRC-32 checksum of every zip archive is computed: eight steps per byte become one, and War and Peace is checked ten times faster. The measurement shows something else too: a bigger table is not always faster.
Every file in a zip archive has a CRC-32 checksum recorded with it: the unpacker recomputes it and so learns that the file is not damaged. By definition CRC processes data bit by bit: eight steps of “shift and maybe subtract” for every byte. War and Peace (the Russian original) is five megabytes, forty million steps. But every eight steps depend on just one byte, and there are 256 different bytes. Compute all 256 answers in advance, and a byte is processed in one step. Type any text and walk through it byte by byte.
At each step the state and the byte give an index, a number from 0 to 255, and it picks one cell of the table. Switch on “show the eight bit steps”: the same eight shifts the table replaced, and their result matches the number in the cell. The table is a kilobyte of memory. On the site’s server the CRC-32 of the whole novel is computed in Go eleven times faster with the table than bit by bit.
The idea
If a function is called many times but has few different inputs, compute it for all inputs once and put the answers into an array. Every later call is one memory access. This trades memory for time: the table takes space, but the work turns into a read. It pays off when computing costs more than reading from memory and the table fits in cache.
It is a relative of memoization: there answers are stored as they are asked for, here all at once, before the first question. And a relative of prefix sums: there the answers to all the questions “the sum from the start to i” are computed in advance, and any segment is obtained by a subtraction.
Why the table gives the same result
CRC is the remainder of dividing the polynomial written by the bits of the data by a fixed polynomial P, and “subtract” here means XOR. By definition a byte is eight steps: if the lowest bit of the state is one, shift and XOR with P, otherwise just shift.
Let c be the 32-bit state, b a byte of data, and T[i] the result of eight steps started from the number i. Then eight steps started from c XOR b give (c >> 8) XOR T[(c XOR b) & 255].
One step is a shift right and maybe an XOR with P. Both the shift and the XOR with a constant commute with XOR: the shift of (x XOR y) is the XOR of the shifts. So eight steps on the number x = c XOR b are x shifted by 8, XOR some number Q, the sum of the copies of P that were subtracted. Which copies to subtract is decided only by the lowest bit at each step, and in the first eight steps it comes from the low byte of x: the XOR with P at step j also changes bits checked later, but only depending on the low bits already read. So Q depends only on x & 255. For the number i = x & 255 the same eight steps give i >> 8 XOR Q = 0 XOR Q, that is, T[i] = Q. It remains to note that x >> 8 = c >> 8: the byte b sits only in the low eight bits and leaves with the shift.
There is nothing specific to CRC here: precomputation works for any function to which only a few bits of input matter. The table of ones in a byte is built the same way (counting the ones in a 64-bit number then costs eight reads), and so is the sine table in old games: in the Doom source code of 1993 the sine is taken from the array finesine rather than computed.
Is a bigger table faster?
If an 8-bit table replaces eight steps with one, a 16-bit table of 65,536 entries should process two bytes per step and be twice as fast. The measurement: the CRC-32 of War and Peace bit by bit and with tables of 4, 8 and 16 bits, with the standard functions alongside.
From bits to a 4-bit table and on to 8 bits the time falls severalfold. But the 16-bit table is slower than the 8-bit one, in both Go and Python. The 8-bit table is a kilobyte; it lives in the first-level cache, and every access is almost free. The 16-bit table is 256 KB: it does not fit in the first-level cache, and an access to it costs several times more than the steps it saves. In Python the cost of the step itself adds to this: putting two bytes together into one number is a few extra interpreter operations. More about this wall in the article “Cache-friendly data”.
The standard functions are tens and hundreds of times faster than any of our tables. They use next-level tricks: several small tables at once, to process four or eight bytes per step, and, where the processor can compute CRC itself, its special instructions. The practical conclusion is simple: CRC, hashes and counting ones are taken from the standard library, and precomputation is written by hand for your own functions.
Code
CRC-32 bit by bit and with the table, a check against the standard function, and what CRC is computed for in the first place: it catches any single-bit error and any damage to a run of consecutive bits up to 32 long.
Both functions and the library one give the same result. The strings “War and Peace” and “War and peace” differ by one letter, and their sums by almost every digit. All 128 flipped bits and all 2720 damaged runs up to 32 bits long are detected. This is not luck but a property: a CRC with a polynomial of degree 32 is guaranteed to detect any damage to a run no longer than 32 bits. That is why it is used in networks and file systems, where errors most often come in bursts.
What it costs
Building the table is O(number of entries × cost of one computation), once. Each query is O(1), one memory read. Precomputation pays off when there are more queries than table entries and computing costs more than reading.
The extreme case is tables that take years to compute. In chess, for all positions with seven pieces on the board it has been computed whether the position is won and in how many moves: such endgame tables take tens of terabytes, and a program that reaches seven pieces no longer thinks but reads the answer. The opposite extreme is a table more expensive than the computation: if the answer takes a couple of cycles, an access to a table outside the cache only slows the program down, like the 16-bit table in the measurement.
Problems
The problem is to compute the CRC of every line of War and Peace for two different polynomials. Without a table the solution does not fit in the time limit.
CRC line by line