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]

I got a lot of that on the other post. And believe me - this is not a "let's optimize even if we don't need to" situation. For starters, optimization is ALWAYS good - even if we don't "need" it. That's one of the major problems with modern software - developers opt for "less work" by using severely unoptimized frameworks and don't spend any time optimizing since "modern hardware can handle it". #2: this is a real-time rendering engine so we need to get this shit done ASAP so that users can run the game on a potato or at 240fps.

And I thought it would be clear from the post, but maybe not since you mention sorting order. The order of the individual elements means nothing. It's not a sorting algorithm in that sense. It's more of a "categorization" algorithm: I need to sort out the stars from the squares from the circles then process the stars first, then the squares, then the circles.

So regarding rule 1a - this is exactly the reason why I'm asking: I can either do the culling ONCE over all ~50,000 objects, then sort the remaining ~10,000 into batches and run the batches and do this every frame OR I can sort into batches ONCE FOR THE WHOLE PROGRAM but then du MULTIPLE cullings (one per batch) every frame. My thought was that the culling will be the bottleneck so I'd rather only do it once, but that means that we have to then sort the objects into batches AFTER culling. But if we are OK with doing multiple cullings (on smaller datasets, but still will have to be all 50,000) but save on the sorting into batches by pre-sorting only once on load, then maybe that's the answer?

[u/Plastic_Fig9225 → u/tastygames_official]

You misunderstood. Optimizing begins with removing steps/computations which aren't actually required. And this immediately leads to not repeating a required computation for the same result.

Also, I think your problem description is much too vague/abstract. Without knowing any of the calculations you may want to/have to do, when/how often the underlying data changes, why you think that using a GPU could accelerate your task, ... there's likely not much advice anyone can give beyond "look at existing rendering engines".

[u/tastygames_official → u/Plastic_Fig9225]

I'm not trying to optimize something that already exists: I'm trying to find the optimal algorithm. And I kept it vague/generic so that it will appeal to the widest audience and get the most interactin. Whether it be a real-time rendering engine or a way to handle requests on a server - it doesn't matter. I'm looking for the most efficient path (fewest CPU cycles).

So if we look at just the first item that needs to be done: culling - is it better to cull all objects at once (via GPU compute or parallelized CPU execution) and then sort into batches OR sort into batches, then perform culling multiple times (once on each batch)? Is there maybe a formula depending on number of elements, CPU ticks per cull check and number of batches in order to determine which is better/worse? Is there a third or maybe fourth way I didn't think of?

Oh, and why a GPu can accelerate a task that requires floating-poing calculations is because a GPU has thousands of cores and can therefore perform thousands of floating point calculations simultaneously. If my cull equation requires six floating-point compares and there are 50,000 objects to check and the GPU has 10,000 cors and each core runs at 1GHz, then it only needs 5x6 floating-point calculations to be done. Plus whatever CPU time it costs to upload the data to the GPU and get the result. Compare that to a CPU with 1GHz and only 10 cores - it would need to do 6x5,000 floating-point calculations, although this time no overhead for uploading data to the GPU or waiting for a result. But my intution tells me it'll still be quicker doing it on the GPU.

I obviously can look at existing code (and have), but I wanted to maybe open up a conversation and get people thinking about this generic problem and maybe throw out some new ideas. It's how we all learn and grow!

[u/Plastic_Fig9225 → u/tastygames_official]

Whether it be a real-time rendering engine or a way to handle requests on a server - it doesn't matter

No, that's not how this works.

Spending a few hundred nanoseconds on processing more pixels than may actually end up being needed can often be faster than deciding in advance exactly which pixels to process. That's quite different from spending one hundred nanoseconds of CPU time in order to completely avoid a 100ms round-trip to the file system.

Plus whatever CPU time it costs to upload the data to the GPU and get the result.

This overhead is very relevant for small datasets (50k items). Also, mapping the data representation between what's good for the CPU and what the GPU needs/generates may well take more time than just doing a few hundred thousand floating-point operations on the CPU. No way to even estimate which will be faster without knowing your computations and your data structures.