Table lookups are efficient

14 October 2024 · 4 min

When optimizing small functions, I often rely on a table lookup: I replace the actual computation with table of precomputed values. It is often surprisingly efficient.

Let us consider an example. Suppose that you are given an array of characters and you want to replace all instances of the character ‘\’ with the two-character string “\\”, all instances of the character ‘\n’ with the two-character string “\n”, and all instances of the character ‘\r’ with the two-character string “\r”. You might do it with a sequence of branches, like so:

int index = 0;
for (char c : original) {
  if (c == '\\') {
    newArray[index++] = '\\';
    newArray[index++] = '\\';
  } else if (c == '\n') {
    newArray[index++] = '\\';
    newArray[index++] = 'n';
  } else if (c == '\r') {
    newArray[index++] = '\\';
    newArray[index++] = 'r';
  } else {
    newArray[index++] = c;
  }
}

Instead, we could store the escape sequences in a table, and load it from the table. In Java, it might look as follows…

    private static final byte[] silly_table3;

    static {
        silly_table3 = new byte[256];
        silly_table3['\\'] = '\\';
        silly_table3['\n'] = 'n';
        silly_table3['\t'] = 't';
    }

//...

int index = 0;
for (char c : original) {
  byte b = silly_table3[c%256];
  if (c < 256 &&  b > 0) {
    newArray[index++] = '\\';
    newArray[index++] = (char)b;
  } else {
    newArray[index++] = c;
  }
}

My table is unnecessarily large: I leave it as an exercise to the reader to optimize the code so that a much smaller table could be used.

When processing inputs sequentially, we often have some data loading. In this case, we must load each character from the input array. The table lookups also require some load operations, but modern processors can typically execute two loads per cycle or more. Thus we are often not severely limited by the number of loads. The loads have some latency, but a table lookup in a hot function is often cached closed to the CPU. Thus we may have a relatively short latency (e.g., 5 cycles). If there is not too much dependency between how we process successive characters, this latency is not too harmful. On the plus side, table lookups reduce the number of instructions issued, and they often keep branch mispredictions to a minimum. Though processors become better at predicting branches, mispredicted branches remain quite expensive.

You might be concerned that tables can make your binary code larger. However, that may not be true. One of the most important optimization that compiler make is ‘inlining’. That is, your small functions are often replicated several times to avoid the overhead of a function call and to allow for more advanced optimizations. A hot function implemented with tables is made of few instructions. These instructions can be reproduced at little cost all over your code base. In contrast, an implementation made of many instructions can be costly to inline.

I wrote a little Java benchmark to test out the idea. I provide random ASCII inputs. In my tests, the table approach is over 20% faster.

The results will vary depending on your system and processor.

The table approach is not very sensitive to the complexity of the problem. In my case, I needed to replace 3 distinct characters. I could extend it to 5 distinct characters or more by updating the table. The conventional approach becomes increasingly more complex and expensive as I add characters. Thus the benefits of the table approach grow as the problem gets more complex. Conversely, there is a limit to the value of the table approach: it is inefficient to use a table when you need to identify just one character.

Optimizing compilers may turn your conventional code into a table lookup. For example, a switch-case is sometimes compiled to a small table. Further, what appears like a branch (if-else) might be compiled to conditional move instructions or even to a table. When in doubt, you should examine the assembly output. Unfortunately, Java makes it a bit difficult to do.

These speeds (1 GB/s) are not impressive. But Java makes it difficult to use more advanced low-level optimizations. Java Vector, when it becomes more mature, could help.

Credit: The blog post was motivated by an email by Lucas Sloan.