Sprite batching seems slow

Question

I have implemented a sprite batching system in OpenGL which will batch sprites based on their texture. However, when I'm rendering ~5000 sprites all using the same texture I'm getting roughly 30fps.

The process is as followed

• Create sprite batch which also create a VBO with a set size and also creates the shaders as well

• Call begin and initialise the render mode (at the moment just setting alpha on)

• Call Draw with a sprite. This checks to see if the texture of the sprite has already been loaded and if so it just creates a pointer to the batch item and adds the new sprite coords. If not then it creates a new batch item and adds the sprite coords to that; it adds the batch item to the main batch. If the max sprite count is reached render will be called

• Call end which calls render to render the left over sprites in the batch, and also resets the buffer offset

• Render loops through each item in the batch and will bind the texture of the batch item, map the data to the buffer and then draw the array. The buffer will then be offset by the amount of sprites drawn.

I have a feeling that it could be the method I'm using to store the batched sprites or it could be something else that i'm missing but I still can work it out.

The class files are at these URLs:

• http://pastebin.com/iCB608tA (header)
• http://pastebin.com/ZAytErGB (class)

On top of this, I'm also getting a weird issue where two sprites are batched on after the other the second sprite will use the same coordinates as the last. But, the one that is drawn after it is fine. I can't seem to find what is causing this issue.

Answer 1

Searching through 5000 elements every time you add a element could already become a CPU bottleneck. You are dealing with real-time graphics here, so if it takes a few ms it's already too much. Iterating over 5000 elements is probably much less than a ms, but iterating 5000 times over up to 5000 elements quickly adds up. Say iterating over 5000 elements takes 0.02 ms, now you do that 5000 times that's already 100ms, 10 fps. For the iterating alone.

I would suggest you to do the sorting only once, e.g. shortly before you are drawing them.

Another option would be to just check the last or the last few sprites in the list, it's quite a simplification but still should be able to optimize most cases.

Edit: Oh just noticed that you are using a std::map as data structure. It iterates over it's elements to find stuff. std::unordered_map is a alternative which makes use of hashing and can access elements in constant time.

Answer 2

You have lots of inefficiencies in there. (When I say 'slow' below, I mean 'relatively slow'.)

• Iterating over a std::map is slow, because the data is sprinkled around memory and requires indirections. Ideally you would use a contiguous data structure like a std::vector if you need to iterate over it often.
• Lookups in a std::map (eg. m_BatchItems[Sprite->getTexture()]) are fairly slow.
• Allocating memory is slow. Ideally you wouldn't be calling new MLBatchItem::batchInfo in the middle of a draw operation. But if m_BatchItems was a vector instead, you could just push_back the new batchInfo and no extra memory would have to be allocated if the capacity was big enough.
• Deallocating memory is slow. You shouldn't call delete it->second in your rendering function. Again, if this data was stored in a vector or similar you can deallocate all of it instantly rather than bit by bit.

Ideally, what you would do might be more like this:

• preallocate your batches based on the textures your game uses. You probably know these at load time so you don't need to create them dynamically.
• fill the batches outside of the draw/render code by adding the information whenever a new sprite is added to the game, and removing it when the sprite is removed.
• each batch would contain a vector of BatchInfo, with capacity set fairly large to begin with to reduce memory allocations.
• at render time, for each batch, iterate over the vector of batchinfo objects.
• if you really need to limit batching to 1000 sprites, instead of using multiple batches, use 1 batch but render it 1000 items at a time.

Answer 3

I just want to add to the other good answers, that your graphics card fill rate could also be affecting this. What I mean is that if your sprites are large, drawing 5000 of them will fill the whole window several times (or they will fill the same area 5000 times). A graphics card can fill only so many pixels per second. As a quick test, reduce the size of each sprite (e.g. to 10x10), and see if your performance improves.

If this turns out to be the case, it means you will need some kind of culling mechanism so that as few covered (behind others) sprites are drawn.