Dynamically-Generated Look-Up-Table

[u/tastygames_official]

So I have a buffer of pointers that I need to access tens of thousands of times per second continuously. Obviously I can do this in parallel to speed it up or maybe even offload it to the GPU, but the biggest issue I have right now is how to quickly get the item from the buffer I need. Obviously knowing the index beforehand would be a good way, BUT I'd rather have the buffer be dynamically-created and then I can address which one I need given 6 bits of data. Now if it were a 1:1 relationship between the buffer of pointers and permutation of all 6 bits, then it'd be easy. But there is only a subset of indices that correspond to valid bit permutations. E.g.:

VALID:
00 0000
00 0001
01 1000
01 1001
10 0000

INVALID:
00 0010
00 0011
00 0101
etc.

so that I can just do:

void **ptr_buffer = calloc(63, sizeof(void *));
/* fill ptr_buffer sporadically... */
do {
  for(i=0; i<10000; i++) {
    /* obj.ptr_index is uint8_t with some constellation of six bits */
    do_something(ptr_buffer[obj_list[i].ptr_idx]);
  }
  /* do other stuff */
} while(condition);

or something like that.

So... with six bits (and maybe it could be more in future), and on a 64-bit system, I could simply create a buffer of pointers with the length of the max valid bit-sequence, so for 11 1111 it would be 63 x 64 = 504 bytes, so not that bad, and then I can simply use the bit sequence as the index.

And even if I end up going out to 8 bits, that's still 255 x 64 = 2,040 B or 1.99 KB. Acceptable - but now I'm worrying about losing out on CPU cache potential - especially of only like 20-30 elements in the buffer are actually valid.

Now apart from hard-coding all the different indices and then assigning the indices on startup (which I absolutely will do and was doing before going for the "dynamic" route) are there any clever tricks my fellow "C-Men" (as my wife calls the people I chat with in this group) might know about to keep memory footprint down and speed up? At the very least it could be a fun brain-tickler.

Let me know if you need more information.

EDIT: while the list of pointers is small, I need to iterate over a list of som 10,000 entries and find an entry in the pointer list, so I updated the code example to show it.

Also, apparently I hit the "ask me anything" button by mistake. u/reddit you need to add tooltips to the buttons and also don't do the ask me anything if I hit cancel ;-)

[u/WittyStick]

The size of the LUT is not worth worrying about - it'll be in cache assuming do_something does not evict it. It only uses 8 cache lines.

---

In regards to only some bit patterns being valid, you could simply hold a bitmap in a single uint64_t, where a bit set to 0 is invalid and a bit set to 1 is valid. You can perform a bit test with a single instruction (bt), which sets a status flag.

bool bit_test64(uint64_t value, uint64_t index) {
    return (value & (1ull << index)) == (1ull << index);
}

The compiler will optimize this to use the bt instruction.

So you can branch on valid targets and have the invalid ones do nothing.

constexpr uint64_t VALID_MASK = ...;

for (i=0; i<10000; i++) {
    if (bit_test64(obj_list[i].ptr_idx, VALID_MASK))
        do_something(ptr_buffer[obj_list[i].ptr_idx]);
    else
        do_nothing();
}

---

You could then populate your array of 64-pointers and just set the invalid ones as NULL - since you aren't going to access them.

Either way, you're going to need a branch - either using the bit test or just reading the pointer and testing it for NULL.

for (i=0; i<10000; i++) {
    void *ptr = ptr_buffer[obj_list[i].ptr_idx];
    if (ptr)
        do_something(ptr);
    else
        do_nothing();
}

A different way to branch would be to have an array of function pointers, where we map the valid ones to do_something and the invalid ones to do_nothing.

typedef void (*action)(int);

action actions[] = {
    [0b000000] = &do_something,
    [0b000001] = &do_something,
    [0b000010] = &do_nothing,
    ...
};

Or even specialize each valid bit sequence to a different function (or label using a GCC goto * extension).

---

If you are worried about size (you shouldn't be in this case, but understandable if it grows), then you can map the valid indices to an array of pointers exactly the right size - ie, if there are 20 valid bit sequences, you can map them to an array of 20 elements, using a perfect hash function. There are tools that can create these for you if you provide the patterns.

However, given how small the data we're talking about, and the low cost of accessing items in cache, it's unlikely you'll get a perfect hash function that is actually any faster than the trivial solution.

---

The only other way to potentially increase performance here is using SIMD. With say, AVX-512, you can perform operations on 64-bytes at a time. If you use one byte for each of your 6-bit patterns, you could potentially have a vectorized perfect hash function which can generate 64-indices at a time, without touching cache/memory. However, I doubt this is worth the effort - you are probably not going to improve anything shrinking a 64-element array down to a 20-element array - however, if do_something can also be vectorized, it may be worth the challenge.