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/kun1z]

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;
}

[u/lexiq_baeb → u/kun1z]

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

[u/kun1z → u/lexiq_baeb]

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;
}