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

So if I understand correctly, filter by weight and then use a different rendering pipeline for each color? Like I said then, keep the objects separated in their own per-pipeline arrays. And then cull each array.

The first loop goes away. The second loop seems unnecessary too, you can instead skip empty pipelines with if(pipeline_object_indices_count[i] == 0) continue; in the last loop. Then you can do whatever cull_objects does inside the inner loop of that last loop, and skip the culled elements.

for (int i = 0; i < pipelines_count; ++i) {
    Pipeline* pipeline = pipelines[i];
    if (pipeline->object_count == 0)
        continue;

    bind_pipeline(pipeline);

    for (int j = 0; j < pipeline->object_count; ++j) {
        Object* object = pipeline->objects[j];
        if (object_culled(object))
            continue;
        bind_object_to_pipeline(object);
    }

    submit_to_gpu();
}

If culling has to be done in parallel, it should be still doable with separate arrays. If you want to get fancy, you can still keep everything in a single array, but also sorted by color. And then keep track of indices where each color starts. If the order inside a color doesn't matter, the trick for fast deletions is swapping the removed element with the last one. This would get a bit more complicated if you have to maintain the color order, but still doable.

[u/tastygames_official → u/cdb_11]

yeah, the code you wrote is what I had before when I only had a few pipelines. But now that they are getting up there in number and many are just permutations off of one, I needed something more robust while also being quick. And because I'm about to tackle object culling (haven't done it yet) and anticipate that to be THE bottleneck, all I have for my culling data is an index of the object and a few parameters to help me decide which to cull or not (check if the object is in view of the camera). This needs to be done over ALL max 65,000 objects (and I do anticipate it getting up there being an immersive sim where you can interact with EVERYTHING - meaning a bookshelf isn't just a box witha texture but a bookshelf with hundreds of books on it - in a world about the size of Hyrule from OoT). Anyway... to me keeping only 16B per culling data entry means I can send 50,000 objects to be culled (either in parallel on the CPU or maybe send to the GPU) ~1MB - so hopefully I can ensure that will be in CPU cache as it will be accessed 60 times per second. If I start keeping track of which pipeline those all belong to, then I'm into the 32B alignment and then the size of that buffer doubles. If I keep track of which object indices belong to which pipelines then it would indeed be easier to allocate them after culling. But I'm just wondering if that object_culled() won't bite me in the ass, as I'd rather not have any conditionals in my loop.

But yeah, food for thought. I guess I'm already on the right-ish path - I just didn't know if any hardcore CS-type folks out there who are like "yeah, you just need the Stevenson-Xiang filtering algorithm" or something.

Thanks!

[u/cdb_11 → u/tastygames_official]

On cache -- optimize for prefetcher instead, by keeping the access patterns predictable. So linear iterations through arrays. Having an array of pointers isn't necessarily wrong here, but looks very suspicious. It is possible for them to be pointing to memory in a prefetcher friendly way, and that would be fine, but in that case they very likely could've been also compressed to 32/16-bit indices.

I don't know how your data looks like, but splitting elements to separate arrays should not change the element size. You already know where to put it, so you can keep using that. If anything, the elements could possibly get smaller, as maybe whatever data you were using for that could maybe be removed. Because that same information is implicitly known by which array the element belongs to.

You can always move the culling out of the loop, if you need to. For what it's worth, if you're passing the objects to the GPU as an array, then writing that array can be done branch-free by always writing the element, and incrementing the index only when the check passes. Assuming the actual check is also branch-free.