Four Functions and Enum Labelings

2016-12-26

This post shows four solutions to an instance of the function-directed enum labeling problem. Today I'll show the code, and tomorrow I'll explain how they were discovered.

It's important to understand that these four functions are not equivalent: each one requires a different enum labeling. But they have the same structure, which is what we care about.

For brevity, the first three are shown in Python without the enum labeling, which looks like a random assignment of integers. The last one is shown in C++ with the enum labeling and proof that it works.

Notes:

The integer labels should have no runtime cost: ony any CPU architecture, one byte will fit in the constant portion of an instruction. In other words, we're replacing a 221-byte lookup table with just a handful of instructions.
The initial idea and first 2 solutions are by Veedrac. I replicated his results, found the third solution, and then he found the fourth. As you'll see, they get shorter and simpler.

Solution 1

The idea here is that id & (-id - 23) is close to what we want, and then we fix it up with some ad hoc conditionals. The naive version would have around 21 tests; this has 6.

def LookupKind1(id):
  kind = id & (-id - 23)
  if kind:      return kind
  if id <= 1:   return 20
  if id <= 9:   return 44
  if id <= 40:  return 48
  if id <= 72:  return 50
  if id <= 105: return 4
  return 2

Solution 2

The expression (id & 230) & (id + 13) has 3 operations instead of 2, but it only requires one conditional fix.

def LookupKind2(id):
  return (id & 230) & (id + 13) if id else 32

Solution 3

I used Veedrac's method to find this solution with 5 instructions and no branches. In the last post I talked about branch misprediction a bit.

def LookupKind3(id):
  return (-id + 12) & (id ^ 6) & (id + 14)

Solution 4

This solution has only 4 instructions, and still no branches.

def LookupKind4(id):
  return 175 & id & ((id ^ 173) + 11)

Here it is in strongly-typed C++:

Kind LookupKind(Id id) {
  int i = static_cast<int>(id);
  int k = 175 & i & ((i ^ 173) + 11);
  return static_cast<Kind>(k);
}

The file ik7.cc has the full enum labeling and an exhaustive test of all 221 lookups. Run it like this:

$ ./run.sh ik7
+ mkdir -p _tmp
+ c++ -std=c++11 -O3 -o _tmp/ik7 ik7.cc
+ _tmp/ik7
PASSED  // This is printed after 221 tests pass

Tomorrow I'll explain how these solutions were discovered. You can also take a peek at the reddit thread, but I'll explain it a bit more concisely and present the "metaprogramming" code.