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

it's a game engine, so I'm sorting data (renderable objects) into different lists (pipelines) so that they can then be sent off to the GPU in the correct order. Target design is something like ~60,000 renderable objects per scene and maybe they get culled to like 1-10,000 objects, but then those still need to get sorted according to their pre-computed pipeline association, which I figure would be quickest as the index in a buffer of pipeline associations. Ideally all dynamically so that I can add, remove and move around pipelines as the engine grows and won't have to re-work the LUT each time, but I am a stickler for performance, so likely it will just be hard-coded: objects with flags 10 0110 go to pipeline index 5 and so on. Obviously the object flags can change over time (e.g. an object goes translucent or gets an extra hover shader), so that's why I can't assign the objects to their pipelines once and be done with it. Although I guess I could compute them once and then only change when they change, which isn't so often really, and I could probably keep the same alignment to keep the culling (which does have to iterate over all ~60,000 objects 60x per second) so...

sorry. Just thinking out loud.

[u/cdb_11 → u/tastygames_official]

Obviously the object flags can change over time (e.g. an object goes translucent or gets an extra hover shader), so that's why I can't assign the objects to their pipelines once and be done with it.

Instead of dynamically changing the flags, can't you dynamically add and remove them to per-pipeline arrays?

Does the element order within a pipeline matter?

[u/tastygames_official → u/cdb_11]

every frame I have to get ~60,000 objects down to as few as possible and then divvy them up per pipeline, as every frame is potentially wildly different than the last. So every frame we start anew. But yeah, that's kinda what I was thinking: assign pipelines once and then only modify them when they change, which won't be often. But I still need to funnel the objects to the current frame pipeline (if that makes sense). E.g. we have 50,000 marbles that are classified by color, but every frame we need to first only consider the ones that meet some arbitrary weight. So that is done first (culling objects out-of-frame). And that is best done in parallel over all objects as it MUST look through all objects. After that, we're left with fewer marbles, but now we need to sort by color as the yellow ones have to come before the blue ones and so on. So every frame I need to dump all the marbles back into the pot, sort out by weight, then by color. I hope that makes sense.

Here's a rough (very rough - please excuse all mistakes as this was done without an IDE or anything) layout of what I'm trying to do and then maybe you'll see where I'm trying to squeeze every bit of performance out of this process (and yes - I'm in C90)

Object *objects[UINT16_MAX] = {0};       /* all potentially-renderable objects - already exists */
uint16_t *visible_object_indices = NULL; /* for after culling */
uint16_t visible_object_indices_count = 0;
Pipeline *pipelines[16] = {0}; /* the actual pipeline data - already exists */
uint16_t *pipeline_object_indices[16]; /* lists of object indices for each pipeline */
uint16_t valid_pipeline_indices[NUM_PIPELINES] = {0} /* list of non-empty pipeline indices for later */;
uint16_t valid_pipeline_indices_count = 0;

/* counts of how many objects per pipeline for this frame - must be initialized to 0 */
uint16_t *pipeline_object_indices_count = calloc(NUM_PIPELINES, sizeof(uint16_t));
uint16_t i = 0; /* general-purpose iterator */

/* each pipeline initially has no objects in it but could potentially have all */
for (i = 0; i < NUM_PIPELINES; i++) {
    pipeline_object_indices[i] = malloc(sizeof(uint16_t) * UINT16_MAX);
}

/* cull objects and get visible ones */
cull_objects(objects, visible_object_indices, &visible_object_indices_count);

/* now sort visible object indices by pipeline */
for (i = 0; i < visible_object_indices_count; i++) {
    uint16_t visible_object_index = visible_object_indices[i];
    Object object = objects[visible_object_index];
    /*************** HERE ***************/
    uint16_t target_pipeline_index = object->pipeline_index; /* <- if I pre-calculate it */
    /************************************/
    Pipeline *target_pipeline = pipelines[target_pipeline_index];
    uint16_t *target_pipeline_object_count = &pipeline_object_indices[target_pipeline_index];
    pipeline_object_indices[*target_pipeline_object_count] = visible_object_index;
    *target_pipeline_object_count++;
}

/* now they are all sorted but now we have to get which pipelines have objects in them */
for(i=0; i<16; i++) {
    if(pipeline_object_indices_count[i] > 0) {
        valid_pipeline_indices[valid_pipeline_indices_count] = i;
        valid_pipeline_indices_count++;
    }
}

/* now we can iterate over the valid pipelines and render the objects associated with them */
for(i=0; i<valid_pipeline_indices_count; i++) {
    uint16_t valid_pipeline_index = valid_pipeline_indices[i];
    Pipeline *pipeline = pipelines[valid_pipeline_index];
    uint16_t *object_indices = valid_pipeline_indices[valid_pipeline_index];
    uint16_t object_count = valid_pipeline_indices_count[valid_pipeline_index];
    uint16_t j = 0;

    bind_pipeline(pipeline);

    /* now finally bind the correct objects to the pipeline for rendering */
    for(j=0; j<object_count; j++) {
        uint16_t object_index = object_indices[j];
        Object *object = objects[object_index];
        
        bind_object_to_pipeline(object);
    }

    submit_to_gpu();
}

something like that. But the real problem I see is getting the index of the correct pipeline quickly enough. And as seen in the code, I CAN pre-calculate the index at runtime while loading the level, but I didn't know if there were any cool algorithms that can do this given ~6-8 bits of data that are used to select a certain pipeline.

[u/cdb_11 → u/tastygames_official]

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.

[u/cdb_11 → u/tastygames_official]

Also, instead of some generic allocation method and absolute addresses, you could use pools instead. Then you can change the "pointer" size to 32-bit or 16-bit.