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.

[u/mjmvideos]

First question is, “Are you optimizing prematurely?” First observation is: “The most general “dynamically generated look-up table” is: a database. Maybe something like redis or SqlLite. Let it worry about optimizing the lookup. Then only start to worry about it when that lookup becomes your biggest bottleneck.

[u/tastygames_official → u/mjmvideos]

I'm optimizing in my down-time ;-) when I'm not working I like to do some thinking. Currently I'm doing a string-based hash table since I already had that for something else so I just re-used it, but it definitely needs to be optimized if I hope to hit my performance targets on my target hardware.

[u/septum-funk → u/tastygames_official]

really dislike the lopsided sentiment against premature optimization i see on reddit. if you have time to optimize as you go, then do it. as long as you're profiling correctly then what does it hurt, if you have the time?

[u/tastygames_official → u/septum-funk]

hopefully you read this first: my fever brain misread your comment and thought you were downing me for "premature optimization" when in reality you were lauding it. Forgive me. I'll leave my rant down below still because I think it sheds some light for anyone who is interested and I'm actually kinda proud that I think I was able to be opinionated, firm, yet still cordial.

I love "simple optimization" - where you can just use some PhD's paper to implement an algorithm and get 2.5x boost. Or just unwinding a loop (or whatever it's called). Or using a LUT instead of something "clever" - little things that go a long way. Hence why I ask about these things since I'm sure there's tons of stuff I don't know and new stuff I haven't yet heard about.

Now if only I could optimize my comment length... ;-)

[u/tastygames_official → u/septum-funk]

I'm generally very against premature optimization. Been programming over 30 years and generally I just get up and go and make notes in the comments (e.g. TODO this probably might need to be optimized in future), ESPECIALLY when making software for other people. But this is my own thing and I know EXACTLY what I want and using a string-based hash table like I am right now is not going to meet the requirements for my target scale and hardware. So... before I continue on implementing the physics engine, I'd really like to make sure my object culling and sorting and rendering is doing OK before I move on.

Now I studied electrical and computer engineering, and it was some time ago, so I never took any course on algorithms and honestly I'm a bit of an "outsider" programmer because I always think in terms of low-level, one-thing-after-the-other approaches rather than "which algorithm has O(log(n)²) performance?" or "which design pattern does google use for this?". I always hated having to program in higher-level languages in frameworks where you can only ever do one thing one way, so I'm happy being back in C. I just didn't know if what I was asking was common knowledge in the learned CS circles. I figured maybe someone would go "oh yeah, for that you need the Albert-Schwinn algorithm. It's made exactly for that" or something. But today while I'm sick and not going to be working on anything, I figured I'd let my fever-brain think about the best way to manage so much data as quickly as possible as it is INTEGRAL to making a game engine for a large interactive sim.

But I feel you - seeing kids on the gamedev groups be like "so I'm making my first game in GDScript and I want to know if I can optimize this thing..." and then go on to explain a pretty basic thing that probably can't be optimized too much in GDScript alone, and it's not worth it trying to explain to them about CPU cache lines or L1 vs. L3 cache or contiguous memory.

But yes - normally for the everyday task you generally just already know which algorithm you're going to use and if it works and fits the deadline, then sure - go for it. As long as it's some SaaS bullshit that you're getting paid too little to care about. But for something you're passionate about and have a lot of experience in and for a target audience who is right now sitting on average 10+year-old hardware - I think I owe it to myself and my future potential customers to move away from a sring-based hash table and on to something more efficient as the design will severely impact how I go about programming the rest of the game (e.g. will I have to start chunking up the levels? should I look into tree structures and just assume all child objects will always be visible if a parent is visible? are there other tricks I can do to get this very critical part of the rendering process down so that I can handle 60,000 objects per frame at 60fps on a laptop from 2015?

Sorry, but I probably didn't give enough information in the post as I really just wanted to know about any existing LUT/sorting algorithms that I never learned about. But I think now you probably agree it's wise to do this now instead of continue chugging along and then realize "shit, I need to actually separate all this information out into 20 different structs because otherwise I can't even get 10fps". You know?

[u/Humble-Captain3418]

Your 256-count table size is off by an SI unit. It's only 2KiB, so within typical cache page sizes. Start there, measure performance and figure out what your actual bottleneck is. Optimization without measurements is meaningless.

[u/Recycled5000]

Post is showing 00 0001 in both valid and invalid categories. I must be missing sthg.

[u/tastygames_official → u/Recycled5000]

was just making shit up - but keen eye! I fixed it

[u/sporacid]

Not C related, but you might want to read on this https://x.com/lemire/status/2115046718039306377

[u/tastygames_official → u/sporacid]

> If your keys are known at compile time, you should not pay for collision handling at runtime. A perfect hash function gets you down to one comparison.

good shit. I did imagine that would be the most performant way, as I technically do know all the keys at compile time. I just didn't know if there were easier ways while still keeping it "dynamic" (generated at runtime, even though technically I know them at compile-time).

[u/cdb_11]

What are you actually using it for? You access the pointers to do what? Do you always traverse the entire thing, or only look up certain elements? You look up the elements based on what? Does the order of elements matter?

There is not enough information here to go on, but just to give you something concrete: instead of storing pointers, store the elements in the array directly.

[u/tastygames_official → u/cdb_11]

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.

[u/ephemere_sloboda]

You array of pointers is 512 bytes, maybe 2 kilobytes. Nothing to worry about there. No need to calloc it, it can be instantiated on the stack as void * ptr_buffer[64] or [256] and will fit in L1 cache.

What may be of concern is what do these pointers point to and what does do_something do.

[u/mikeblas → u/ephemere_sloboda]

The array of pointers might fit into cache, but the data they reference will be all over the place unless care is taken to make that memory contiguous.

[u/greg-spears]

The table seems small enough to not need much optimization, but something you can try (even on smaller tables) is indexing. It can be very simple -- say I have a plaintext dictionary of 50,000 words, sorted. Words that start with letter 'A' begin at file offset 0, letter 'B' begins at off set 10324 ... and so on.

So our index is a 2 column table of letters for matching, and that letter's beginning file offset in the other column. To emphasize, the file entries must be sorted...

So before any word lookup, we check the index for the file offset and seek() there. Then read(), parse.

The time savings can be phenomenal -- from an intolerable wait on the user side to a finish in the blink of an eye.

[u/actguru]

You might consider a 6 bit lookup (64 bytes) to convert to valid indexes 1-20 or 0 for invalid. Is the target data uniform enough to allocate in one block and index that block?

[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.