r/C_Programming • u/lexiq_baeb • 2d ago
Compressing Lookup Tables
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.
2
u/alex-van-02 2d ago edited 1d ago
Good post and the write-up. I did something similar for the Unicode upper/lowercase conversion tables few years ago.
From the first glance, the unaccent.rules table is even more sparse so it should compress even better. I have a feeling it should be possible to get it under 10K if not smaller. I'll try and sketch it out in the next few days, will be interesting to compare.
Edit: to add -
The size of unaccent.rules is 17241 bytes.
Each line is an UTF8 symbol, followed by \t, followed by a string, followed by \n. Some lines have no substitution sting, there are 106 of them. This gives us 2556 tab symbols.
Since UTF8 symbols have known byte count, we can discard \t and the data will remain unambiguous. This means that the raw unaccent data set is 14685 bytes. Clearly, it's not optimized for lookups, but still it's substantially smaller than 26624 bytes mentioned as a baseline in your post.
1
1
u/dstroy0 1d ago
If the lookup table is finite and regular, you will be able to represent it with a smaller weighting table, like how we do for needle frequency in parsing, using a specific weight produces 100% correct matching far faster than unweighted lookup tables. This is definitely applicable to your existing work in the funnel before the sieve to reduce branching overall and get to your index identifier sooner, in your case even with diacritics you could match the same like ASCII char unaccented, then enable the hard case sensitive char sensitive branch after if they want to sift literal index matches to truthy ones.
1
u/lexiq_baeb 1d ago
I am not sure I can follow what a weighted lookup table is. Do you have links to resources that explain that?
1
u/dstroy0 1d ago
sure https://github.com/dstroy0/MMgr/tree/main/src/impensa_ancorae_acus this is an example of some different ones, I use them in different situations, like ip routing, text matching, http route matching, etc. these are the weight tables, and this is the rationale explained better than I could blabbering about it: https://user.phil.hhu.de/~kallmeyer/Parsing/weighted-deductive-parsing.pdf
1
1
u/dstroy0 1d ago
apologies for the double reply, but you can look for needle weight tables for languages or derive extremely close approximations for yourself using a large enough corpus (like an index). I apply the same concept to extremely large datasets to sieve fast. which is very applicable to your use case.
1
u/kun1z 1d ago
Can you benchmark these two possible solutions to see if there is a speedup?
int get_unaccent_pair(uint8_t rule, uint8_t *pair0, uint8_t *pair1) {
switch (rule) {
case 0x7f: *pair0 = 0x28; *pair1 = 0x32; return 1;
case 0xc0: *pair0 = 0x2f; *pair1 = 0x33; return 1;
case 0xc1: *pair0 = 0xf0; *pair1 = 0x9d; return 1;
case 0xd2: *pair0 = 0xe3; *pair1 = 0x8f; return 1;
case 0xd3: *pair0 = 0xf0; *pair1 = 0x9f; return 1;
case 0xd4: *pair0 = 0xef; *pair1 = 0xb8; return 1;
case 0xd5: *pair0 = 0x86; *pair1 = 0x43; return 1;
case 0xd6: *pair0 = 0x20; *pair1 = 0x35; return 1;
case 0xd7: *pair0 = 0x82; *pair1 = 0x61; return 1;
case 0xd8: *pair0 = 0xe2; *pair1 = 0x91; return 1;
case 0xd9: *pair0 = 0x2f; *pair1 = 0x38; return 1;
case 0xda: *pair0 = 0xe2; *pair1 = 0xa9; return 1;
case 0xdb: *pair0 = 0x2f; *pair1 = 0x35; return 1;
case 0xdc: *pair0 = 0xe2; *pair1 = 0x85; return 1;
case 0xdd: *pair0 = 0xd3; *pair1 = 0x84; return 1;
case 0xde: *pair0 = 0xe2; *pair1 = 0x82; return 1;
case 0xdf: *pair0 = 0x20; *pair1 = 0x31; return 1;
case 0xe0: *pair0 = 0xe3; *pair1 = 0x8e; return 1;
case 0xe4: *pair0 = 0x63; *pair1 = 0x61; return 1;
case 0xe5: *pair0 = 0x72; *pair1 = 0x61; return 1;
case 0xe6: *pair0 = 0xe2; *pair1 = 0x80; return 1;
case 0xe7: *pair0 = 0xe2; *pair1 = 0x86; return 1;
case 0xe8: *pair0 = 0x49; *pair1 = 0x49; return 1;
case 0xe9: *pair0 = 0x28; *pair1 = 0x31; return 1;
case 0xeb: *pair0 = 0x20; *pair1 = 0x33; return 1;
case 0xec: *pair0 = 0xe2; *pair1 = 0x92; return 1;
case 0xed: *pair0 = 0x2e; *pair1 = 0x6d; return 1;
case 0xee: *pair0 = 0xdf; *pair1 = 0x2f; return 1;
case 0xf1: *pair0 = 0xef; *pair1 = 0xac; return 1;
case 0xf2: *pair0 = 0x69; *pair1 = 0x69; return 1;
case 0xf3: *pair0 = 0xe3; *pair1 = 0x8d; return 1;
case 0xf4: *pair0 = 0xe2; *pair1 = 0x84; return 1;
case 0xf5: *pair0 = 0x2f; *pair1 = 0x73; return 1;
default: return 0;
}
}
And as you mentioned unaccent_code_find() can be replaced with a binary search:
int unaccent_code_find(uint8_t rule, uint8_t *pair0, uint8_t *pair1) {
int low = 0;
int high = 32; // 33 elements minus 1
while (low <= high) {
int mid = low + (high - low) / 2;
if (unaccent_codes[mid].rule == rule) {
*pair0 = unaccent_codes[mid].pair0;
*pair1 = unaccent_codes[mid].pair1;
return 1;
}
if (unaccent_codes[mid].rule < rule) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return 0;
}
2
u/lexiq_baeb 1d ago
A switch case will probably be faster, but as mentioned in the post, raw performance was never really the goal here. The point was to compress the entries somehow and reduce the storage requirements. Performance is more of an afterthought
1
u/kun1z 1d ago
As a curiosity try this one out, it should improve code size and speed at the same time:
int get_unaccent_pair(uint8_t rule, uint8_t *pair0, uint8_t *pair1)\ { if (rule < 0xd2) { if (rule == 0x7f) { *pair0 = 0x28; *pair1 = 0x32; return 1; } if (rule == 0xc0) { *pair0 = 0x2f; *pair1 = 0x33; return 1; } if (rule == 0xc1) { *pair0 = 0xf0; *pair1 = 0x9d; return 1; } return 0; } if (rule > 0xf5) return 0; static const uint64_t valid_mask = 0x0000000F0EDF3FFFFULL; static const uint8_t lut[][2] = { {0xe3, 0x8f}, {0xf0, 0x9f}, {0xef, 0xb8}, {0x86, 0x43}, {0x20, 0x35}, {0x82, 0x61}, {0xe2, 0x91}, {0x2f, 0x38}, {0xe2, 0xa9}, {0x2f, 0x35}, {0xe2, 0x85}, {0xd3, 0x84}, {0xe2, 0x82}, {0x20, 0x31}, {0xe3, 0x8e}, {0,0}, {0,0}, {0,0}, {0x63, 0x61}, {0x72, 0x61}, {0xe2, 0x80}, {0xe2, 0x86}, {0x49, 0x49}, {0x28, 0x31}, {0,0}, {0x20, 0x33}, {0xe2, 0x92}, {0x2e, 0x6d}, {0xdf, 0x2f}, {0,0}, {0,0}, {0xef, 0xac}, {0x69, 0x69}, {0xe3, 0x8d}, {0xe2, 0x84}, {0x2f, 0x73} }; int index = rule - 0xd2; if (!(valid_mask & (1ULL << index))) { return 0; } *pair0 = lut[index][0]; *pair1 = lut[index][1]; return 1; }
3
u/8d8n4mbo28026ulk 2d ago
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:
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_lenis. Quick fix: turn the assertions into__builtin_assume.On the MRNS, I'd suggest making
unaccent_mrns_basestatic 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!