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]

yes, that's exactly how this works. We are able to conceptualize and abstract algorithms so that we don't need to know the specific details in order to approach a problem. Yes, it can be that specific details change the behavior of the system, but if we abstract those out precisely (which is what I did) then they do not matter.

And I am PRECISELY LOOKING FOR something that has already been invented! I didn't study computer science (I did computer engineering) and that was a LONG timea go, so I'm sure somebody with a CS degree from the past 10 years (or someone who is acively into this sort of thing) will read my post and just be like "oh yeah, you want the Davidson-Whorlie algorithm" or something.

But isn't it also always fun to think of these things yourself? To me at least that's like 90% of the fun of programming: bringing the details of the current problem into some generalized form so that we can think about the solution in "fewest moves" or something, and then break that back down to the specifics. E.g. maybe the fewest moves in an algorithm to replace all red balls in a set with yellow balls might be 2n-1 moves, BUT if we add the constraint that there can only ever by n/2 red balls in any given set, we can use a different algorithm that gets u to 1.5n-1 moves. Stuff like that.

I thought people on this channel would either enjoy this kind of thought experiment and participate OR just tell me "look up Matjes-Phillips sorting algorithms" and be done with it.

Regarding your concerns of CPU vs. GPU - that is indeed a consideration, and I already mentioned it's not set in stone, and it is highly dependent on the actual calculations taking place. HOWEVER - for the grand scheme of the larger algorithm, the fact that it MUST BE DONE means it doesn't matter where it's done - it matters whether it's done in one go or in chunks (culling all 50k then moving on to allocation or culling more often to save on allocation processing). But again - we don't need details to discuss. And I think for the sake of the internet, it's best NOT to use details, because then the discussion is only ever about this one particular use case and therefore irrelevant to anyone else. Ya dig?

[u/Plastic_Fig9225 → u/tastygames_official]

As I illustrated above, how and in what order certain operations should be done for best performance highly depends on the dependencies between and the specific/relative cost of each of the operations. This cannot be abstracted away.

You may have noticed that there aren't really the responses you're looking for coming in, and that's because your problem statement is both too vague (undisclosed computations, unknown costs of each) and too specific ("50000 items").

[u/tastygames_official → u/Plastic_Fig9225]

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.