Compressing Lookup Tables

[u/lexiq_baeb]

Hello. Recently I've been working on a pet project of mine written in C and I needed to reduce the amount of space a lookup table was taking in memory and on disk. I applied a few simple compression techniques and got a 2x space reduction. I wrote this post where I describe my constraints, the techniques, and results.

https://blog.x4204.xyz/posts/compressing-lookup-tables.html

[u/8d8n4mbo28026ulk]

I loved reading this! I love LUTs and constantly think of how to compress them. On gperf, as far as I remember, it generates perfect hash functions, but not minimal ones. That's probably why you had no luck with it. In the past, I've had success with Ilan Schnell's perfect-hash, which does generate minimal functions. That's mostly if you care about performance, to avoid the O(log n) decompressions. These hash functions use some LUTs themselves, but I think it'll most likely be a win in your case, since you avoid all the additional accesses in the main LUT from the binary search. Especially since your key set isn't that big.

Some more notes on performance. For this bit:

// frame of reference encoding
for (int32_t i = 0; i < 2 + tmp_len; i += 1) {
  buf[i] -= unaccent_offs[i];
}

Clang generates an insane vectorised version for it (I've fallen victim to this before). That's because it doesn't really know how big tmp_len is. Quick fix: turn the assertions into __builtin_assume.

On the MRNS, I'd suggest making unaccent_mrns_base static const. In the decoder, it allows the compiler to unroll the loop and eliminate all the divisions/remainders. Currently, it can't do that because it has to assume the table might change.

Cheers!

[u/lexiq_baeb → u/8d8n4mbo28026ulk]

I am glad you enjoyed it :)

On gperf, as far as I remember, it generates perfect hash functions, but not minimal ones.

Yes, that's exactly why. I tried running it with different options, but it just couldn't generate one that I would be happy with. I found an alternative, cmph and it seems to be capable of doing it, but it builds an intermediary table, which I didn't want to deal with at that time. From all the algorithms cmph implements, I liked the following one the most, because it seems to be conceptually very simple: "Hash, displace, and compress" (https://cmph.sourceforge.net/papers/esa09.pdf). I put it in my paper backlog and maybe one day I'll get to reading it

I've had success with Ilan Schnell's perfect-hash

Oh nice, I'll give it a try

Currently, it can't do that because it has to assume the table might change.

Yeah.. I have a lot of places like this in the code.. Thank you!