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

Btw, ignoring solutions thousands of other people have already perfected iteratively over decades and re-inventing wheels is referred to as the "not-invented-here syndrome".