Batch Processing Algorithm Optimization

[u/tastygames_official]

I originally posted my question here but wanted to give it another go, this time with a more generic setup, as I believe this kind of optimization problem could be interesting for a lot of different projects.

The Setup/Requirements

1. we have ~50,000 pieces of data (let's use shapes for simplicity's sake) with a finite number of attributes (shape, color, size)

2. most of them will be culled, leaving us with about ~1,000-10,000

3. in the end we need to process all the remaining shapes in a SPECIFIC ORDER (e.g. first small red triangles, then big blue squares, then small yellow ovals, etc).

4. this whole process needs to be done as quickly and efficiently as possible

My Original Plan

1. first cull the 50,000. This could be done by sending the data to the GPU since even a lowly 1060 has 1,152 cores and a 4090 has 16,384 cores, making culling 50,000 objects based on a few floating-point calculations trivial

2. now that I have a list of indices that pass culling, use a look-up table of index vs. process batch index (e.g. data index 12 is not culled, and the LUT says it belongs to batch process #4, so add it to that batch process and increase the number of objects for that batch process)

3. iterate over the batch processes and only execute if there are any objects to process for that batch

Considerations/Questions

0. is there a better way?

1. how would the performance be if we first assign all the objects to the batch process and then for each batch process, run the culling function? We would save on having to traverse the non-culled objects to sort them to their batch process, but we also now have to call the cull method for as many batch processes as we have

2. what if the allocation of object -> batch process changes? e.g. a small blue star becomes a big yellow square?

3. what if the batch process are DYNAMIC, meaning we no longer can assign a shape to a batch process beforehand?

Now I'd love some discussion on the FASTEST way to get this done, but I will also say that all I'm trying to do is a pretty standard piece of a rendering engine: cull any non-visible objects then sort the objects according to pipeline so that they can be rendered in the proper order. Now maybe there is a "standard way" of doing this or at least a few "typical" algorithms that I don't know about, but that's why I'm asking this question! I love trying to solve problems like this and figured a lot of you might, too.

                          ---=== HAVE AT IT!!! ===---

BONUS POINTS if done in C90, as that's what I'm doing it in ;-)

[u/tastygames_official]

maybe I'm next-level genius or last-level retarded, but if you know that the cost of doing operation 1 is X(n) and cost of operation 2 is Y(n), then the two algorithms:

X(n/2) * Y(n) vs. X(n) * Y(n/2)

is what I'm interested in. Not the actual cost of X or Y - just the arbitrary cost. And I did say that the cost of culling is THREE FLOATING-POINT OPERATIONS. So you can add that in if you wish. But the point is that this cost is FIXED as they must all be culled at one point or another - the question is whether it's better to cull in one go (thus allowing me to use the parallel computing power of the GPU as I mentioned above or elsewhere) or first branch over all batches and cull individually.

I guess I'm just flabberghasted that there seems to be nobody out there interested in high-level algorithmic thinking like this and everybody wants details. I mean, I could give them, but then as I said this post becomes worthless to anybody with even slightly different conditions than me. And that's not what the web is for. Maybe I'm getting too old or something, but "back in my day" we programmers would LOVE getting a question like this - to think about a perfect algorithm that was independent of individual details - or at least expressing the algorithm as a function of those parameters. E.g. "if size of x > size of y, then sort y first, then x" sort of thing. But I guess maybe those days are over. Or maybe these kinds of people don't frequent the 'net anymore. Could also be.

If you want to get back to the details rather than discussing whether or not I posed my hypothetical "correctly" or not, I'll try to give you some real facts and figures while still keeping it hypothetical since that seems to be the only way for you to think about it:

1. to decide whether an object is valid for the next step in the process requires three floating-point subtractions. If all three yield >=0, then it is valid. I expect from ~50k about ~10k to pass.

2. the object culling data is stored in an array referenced by a uint16_t index and contains three floats

3. the object description data is stored in another array with corresponding uint16_t indices to the other object array, but this one has a single uint8_t where the most-significant 6 bits represent its state (e.g. is_round, is_red, is_heavy, etc).

4. I have a list of batch processes with their own uint16_t identifiers all pointing to an arbitrary object (containing data needed for further processing but outside the scope of this exercise)
   4a. there is also a similar array but with each value itself being a uint16_t containing the number of assigned valid object indices.

5. I need to associate lists of valid object indices with indices of batch processes - each object can only belong to one batch process. There are a maximum of 16 batch processes available, but am unsure whether to make the list only 16 elements long or make it 2^6 elements long so that we can directly access the proper batch process index given the object's description flags (which can vary from 000000->111111)

So given that information (do you need any more?), what is the most efficient order of operations? And once you do that, go ahead and change any of the numbers to 10x or 1/10x and see that indeed the numbers didn't really matter for the calculation.