# Sprite batching seems slow

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:

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.

• oi46.tinypic.com/23hau5v.jpg oi45.tinypic.com/25s3lt1.jpg Images for the issue explained at the bottom. – Dekowta Sep 20 '12 at 20:33
• Have you tried profiling your code to see where it is actually taking up the time? If not, check this out: stackoverflow.com/questions/67554/… – Cypher Sep 21 '12 at 0:02
• Can you add the important parts of your code the to question? Pastebin only lasts so long, then this question isn't very good. Though, maybe it should be closed as too localized... – MichaelHouse Sep 21 '12 at 16:27
• I have tried profiling and although it can help a lot if you don't exactly what you are looking for its kind of useless. also the pastebin will last for as long as there is pastebin as its on my account and set to last forever. – Dekowta Sep 21 '12 at 19:06
• You may want to take a look at directxtk.codeplex.com. One of the guys from the XNA team (Shawn Hargreaves) is working on this now and it looks pretty good, it may give you some help with your SpriteBatch. – Jonathan Connell Oct 16 '12 at 6:39

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.

• I had the unordered_map before but I found it to actually be slower than using a map. I think the unordered_map would only benefit it I was starting to use a lot of different textures. – Dekowta Sep 20 '12 at 21:54
• std::map does not iterate its members when you look up items! – mikijov Oct 16 '12 at 4:22

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.
• ok that seems to make a lot of sense. What you suggested though slightly breaks the implementation I had in mind as I was planning of building an editor from the code so that could load textures in at any time and start rendering them. Ideally I would love to have a system similar to xna's sprite batch. But I will take what you said into consideration and try and reduce the overhead of memory allocation and deallocation as well as improving my use of stl classes. – Dekowta Sep 21 '12 at 18:32
• You could just create the batch when you load a texture in. Or preallocate empty batches which you can assign to specific textures later. Just don't perform lots of memory allocation during the actual rendering process and you'll do a lot better. – Kylotan Sep 21 '12 at 19:11

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.