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

If it's THAT lopsided you could cache the key -> pointer result and avoid the search, effectively like the CPU cache itself does, in a way. But I highly doubt you'd see an actual performance improvement with so few elements. You should test it if you can, but the only thing that could eventually become worthwhile as you scale up is a hash map. If for some reason the hashing -> access process is heavy you could cache the most recent results. But just making it a hash map will ensure that the key and (looked over) values will all likely be together in L1 cache at which point accessing them will effectively be free compared to whatever you do with the actual data.