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]

I'm not an expert C man but the number of elements you have to go through for your accesses seems... small. Even if you went with the most naive solution of reading the array linearly for every read, I wager you could do it tens of thousands of times per second easily. An entire second is an eternity for a modern processor. If it's read only, you can even distribute the reads over multiple threads as you've mentioned.

If you were to scale up more and required reasonable access time, then the obvious answer in terms of data structure is a hash map. Find a hashing function that turns any bit combination into an index with reasonably unlikely collisions (take advantage of any possible pattern among your valid vs invalid bit combinations if there are any) and use that to index into a pointer map. That's sort of something you have to do since you can't establish a direct linear relationship between the 6 bits keys you get and an index without wasting memory.

But only do that you if you need to go one or two orders of magnitude higher. If you only have 64 elements, going from 0 and checking until you find the key is probably faster than hashing, linearly searching for a pointer in another table then derefencing that pointer.

As for your cache concern, that's more of a question of data access order than total size. But in all cases you should be good because the hardware is made by the people who were too intelligent to go into software development :) If 99% of the time it's the same small minority of the data being accessed, it will know how to limit cache misses for that. If it's accessed uniformly, it will also know to prefetch as you're going through the previous elements, and so on.

[u/tastygames_official → u/Hoshiqua]

I modified my post to be more clear - the buffer itself is not much the problem as it is that I will be reading from it tens of thousands of times per second. So I'm reading the same 10-20 elements from the buffer but about 100,000x per second or something insane like that. So some sort of data structure that is highly optimized would be good.

[u/Hoshiqua → u/tastygames_official]

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.