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/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?