A lookup table in Wikipedia’s words:

In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation.

It used to be used extensively when cpu were short of power, but it’s still useful nowadays to squeeze performance for heavily used pieces of code.

The usual structure behind lookup tables is a tightly packed array, which is not necessarily a very haskelly structure.

Another thing you’re looking for with lookup table is, a limited values that the indexes can take. Either through the type directly (for example Word8) or through a fast mathematic operations (for example mod). You can’t resonably create lookup tables over a Word32 type for example.

First we need something that we want to convert to lookup table. So as an example, i’ll take the simple function that converts an hexadecimal Character to an Int.

The following piece of code represent this convertion, expressed naively:

1
2
3
4
5
6

    module N (hex) where
    hex c
            | c >= '0' && c <= '9' = fromEnum c - fromEnum '0'
            | c >= 'A' && c <= 'F' = fromEnum c - fromEnum 'A'
            | c >= 'a' && c <= 'f' = fromEnum c - fromEnum 'a'
            | otherwise            = 0xff

Benchmarks

Secondly let’s put in place some benchmarks using Criterion. The naive piece of code is going to be the reference implementation, and the benchmarks are going to be executed with differents levels of optimisations (no, O, and O2)

The Benchmark itself is using Char for conveniency, where it should use Word8 to be accurate and safe. Some of the code below would be unsafe to run if run with the Char type and not having any validation function in front, or a casting to a Word8.

This is the benchmark:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import Criterion.Main
import qualified N -- naive computing

import Data.List (foldl')

-- simple benchmark function
dataList = take 100000 $ cycle ['\x1'..'\xf0']
process hexF = foldl' (\acc c -> acc + hexF c) 0
    
main = defaultMain [
        bgroup "lookup"
                [ bench "naive" $ whnf (process N.hex) dataList
                ]
        ]

It yields the following result for the naive implemetation:

Vector

Ok, now let’s try improving this number. First we’re going to try to mimics more low level language by using an array through the Vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

module V (hex) where
import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed ((!))

hex c = vtable ! (fromEnum c)
vtable = V.fromList table

\_\_ = 0xff
table :: [Int]
table = [
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
         0, 1, 2, 3, 4, 5, 6, 7,  8, 9,__,__,__,__,__,__,
        10,11,12,13,14,15,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,10,11,12,13,14,15,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,

        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,
        __,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__ ]

It gives:

This is a bit disappointing, you would expect slighly better performance here, but since we know we are doing safe indexing we can replace the indexing operator (!) by the unsafeIndex operation. doing so lead to:

We’re back in business, but one thing that you could notice while looking at core (or the assembly), is that the list is stored as a list, and thus the vector is created at runtime. I’m not sure if there’s any way to do better through the vector interface to create more efficently the table.

Matching

Instead of taking a lowlevel approch, maybe a high level approch will do better. Pattern matching is one of the very nice feature of advanced languages like OCaml and Haskell, and it usually have good performance result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

module M (hex) where

hex :: Char -> Int
hex '\x30' = 0
hex '\x31' = 1
hex '\x32' = 2
hex '\x33' = 3
hex '\x34' = 4
hex '\x35' = 5
hex '\x36' = 6
hex '\x37' = 7
hex '\x38' = 8
hex '\x39' = 9
hex '\x40' = 10
hex '\x41' = 11
hex '\x42' = 12
hex '\x43' = 13
hex '\x44' = 14
hex '\x45' = 15
hex '\x61' = 10
hex '\x62' = 11
hex '\x63' = 12
hex '\x64' = 13
hex '\x65' = 14
hex '\x66' = 15
hex _      = 255

This is really simple and give really good result. This is somewhat surprising and also show the amount of optimisation GHC is putting in the pattern match.

with no, and default O optimisation, it beats the vector-unsafe interface.

As a note of warning: the pattern matching approch works very well when the number of case stays low, however when there’s too many cases, the compilation slow down massively and the runtime slow down too.

ByteString

The high level approch works quite well, however it really feel that something more could be done:

• Pattern matches performance degenerates if the number of cases increases.
• Vectors are not generated at compile time.

We can try to leverage the OverloadedStrings extension, to create an array of bytes through the ByteString interface.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

{-# LANGUAGE OverloadedStrings #-}
module B (hex) where

import Data.ByteString (ByteString, index)
import Data.ByteString.Char8 ()
import Data.ByteString.Unsafe (unsafeIndex)

hex :: Char -> Int
hex c = fromIntegral (table `index` fromEnum c)

table :: ByteString
table =
	"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\xff\xff\xff\xff\xff\xff\
	\\x0a\x0b\x0c\x0d\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\x0a\x0b\x0c\x0d\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"

It yields:

The test is also repeated replacing the index by an unsafeIndex:

While the vector and bytestring should in theory yield the same performance since they’re both arrays, the bytestring get a slight boost for O and O2. This might be due only to the overloadedStrings extension which allow compilation times representation of the packed array.

Magic Hash

MagicHash is the name of the GHC extension to be able to use GHC primitives directly. The primitive approch, is building on top of the bytestring approch. The only major difference is the usage of a raw Addr#, which represent an address in memory (just like a void * in C), instead of the more classical ByteString.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

{-# LANGUAGE MagicHash, BangPatterns #-}
module F (hex) where

import Data.List
import GHC.Prim
import GHC.Word
import GHC.Types

data Table = Table !Addr#

hex :: Char -> Int
hex (C# i) = I# (word2Int# $ indexWord8OffAddr# addr (ord# i))
	where !(Table addr) = table

table = Table
	"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\xff\xff\xff\xff\xff\xff\
	\\x0a\x0b\x0c\x0d\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\x0a\x0b\x0c\x0d\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\
	\\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"#

It yields the most impressive performance so far:

While it doesn’t beat the pattern matching without optimisation (which is odd), it’s consistantly the fastest for O (default optimisation level with cabal) and O2.

All levels

O and O2 levels

Wrapping up

The lookup table are at the time of writing far best represented through the primitives, but unfortunately it does comes at the expense of portability to different haskell compiler, and also doesn’t necessarily feels like very nice haskell code.

As such it should probably be reserved to cases where you really need to squeeze the last drop of performance and where the lookup is key to differenciate between a slow and fast piece of code.

As relatively close 2nd, the bytestring and vector interface are both good candidates as long as the unsafeIndex function is used. unsafe indexing is perfectly safe in static cases where you know what’s your input range.

Pattern matching is quite interesting, since it’s not really in the same category as the others, but yet manage to offer really good performance. With pattern matching you can also more easily covers a sparse range of input, which is harder and more time consuming to do with typical lookup tables.

In any case, the most important thing is: benchmarks ! Do not blindly optimise simple functions; the big performance picture is the most important place where you should start.

You can find some real world usage of primitive lookup tables:

• Cryptocipher’s AES
• base16-bytestring (and the pull request containing the performance improvement report)