# How to use caching to increase render performance?

First of all I am going to cover the basic design of my 2d tile-based engine written with SDL in C++, then I will point out what I am up to and where I need some hints.

# Concept of my engine

My engine uses the concept of GameScreens which are stored on a stack in the main game class. The main methods of a screen are usually LoadContent, Render, Update and InitMultithreading. (I use the last one because I am using v8 as a JavaScript bridge to the engine.

The main game loop then renders the top screen on the stack (if there is one; otherwise, it exits the game) - actually it calls the render methods, but stores all items to be rendered in a list. After gathering all this information the methods like SDL_BlitSurface are called by my GameUIRenderer which draws the enqueued content and then draws some overlay. The code looks like this:

while(Game is running) {
Handle input
if(Screens on stack == 0) exit

Update timer etc.
Clear the screen

Peek the screen on the stack and collect information on what to render

Actually render the enqueue screen stuff and some overlay etc.

Flip the screen
}


The GameUIRenderer uses as hinted a std::vector<std::shared_ptr<ImageToRender>> to hold all necessary information described by this class:

class ImageToRender {
private:
SDL_Surface* image;
int x, y, w, h, xOffset, yOffset;
};


This bunch of attributes is usually needed if I have a texture atlas with all tiles in one SDL_Surface and then the engine should crop one specific area and draw this to the screen.

The GameUIRenderer::Render() method then just iterates over all elements and renders them something like this:

std::for_each(
this->m_vImageVector.begin(),
this->m_vImageVector.end(),
[this](std::shared_ptr<ImageToRender> pCurrentImage) {
SDL_Rect rc = { pCurrentImage->x, pCurrentImage->y, 0, 0 };
// For the sake of simplicity ignore offsets...
SDL_Rect srcRect = { 0, 0, pCurrentImage->w, pCurrentImage->h };
SDL_BlitSurface(pCurrentImage->pImage, &srcRect, g_pFramework->GetScreen(), &rc);
}
);
this->m_vImageVector.clear();


# Current ideas which need to be reviewed

The specified approach works really good and IMHO it is really has a good structure, however the performance could be definitely increased. I would like to know what do you suggest, how to implement efficient caching of surfaces etc so that there is no need to redraw the same scene over and over again?

The map itself would be almost static, only when the player moves, we would need to move the map. Furthermore animated entities would either require updates of the whole map or updates of only the specific areas the entities are currently moving in. My first approaches were to include a flag IsTainted which should be used by the GameUIRenderer to decide whether to redraw everything or use cached version (or to not render anything so that we do not have to Clear the screen and let the last frame persist). However this seems to be quite messy if I have to manually handle in my Render method of the screen class if something has changed or not.

### Edit: Possible optimizations I was reminded of

I have been rendering every frame all tiles of the map one by one which became... yeah quite some heavy work to do for both CPU and GPU. Currently I am working on drawing all layers into one surface for each layer which holds all static tiles. In my current test it is much easier to draw n surfaces (where n is the number of layers) rather than about n*3600 small 16x16 tiles.

Though I am not thinking right now of culling this could be worth some thoughts. However I have to find out how to efficiently render entities, like items to interact with (signs, doors, ...) and NPCs which actually can walk on their own - but that is another problem and not really linked to this one.

• First and inevitable step in order to increase performance is measuring. Profile the application to see where the real bottlenecks are. Don't make any assumptions, like better caching can actually solve any bottlenecks in your code, before even knowing where the bottlenecks are! Come back with solid numbers and we can analyze possible optimization strategies. – Maik Semder Sep 9 '12 at 11:15
• @MaikSemder: I thought this should be obvious enough that the CPU is constantly at 13% usage (inspected just by watching the task manager for a first impression) when (in my current test) redrawing every few msecs about 80 tiles (combined with the repetetive creation and deletion of my ImageToRender objects) in comparison to drawing it once and then idling while there are neither animations nor movement or any input. Why should I waste resources this obviously when it can be handled much better? Furthermore drawing nothing to the screen actually results in CPU usage of < 1%. – Christian Ivicevic Sep 9 '12 at 11:51

Profile, profile, profile. Use AMD CodeAnalyst to inspect CPU bottlenecks and gDEBugger to inspect GPU bottlenecks.

However, there are some general tips I can give you.

• Don't loop over iterators.

Instead, opt for direct access. Here's how I would rewrite your code:

for (size_t i = 0; i < this->m_vImageVector.size(); i++)
{
std::shared_ptr<ImageToRender> pCurrentImage = this->m_vImageVector[i];

SDL_Rect rc = { pCurrentImage->x, pCurrentImage->y, 0, 0 };
// For the sake of simplicity ignore offsets...
SDL_Rect srcRect = { 0, 0, pCurrentImage->w, pCurrentImage->h };
SDL_BlitSurface(pCurrentImage->pImage, &srcRect, g_pFramework->GetScreen(), &rc);
}
this->m_vImageVector.clear();


This has to with Microsoft's silly implementation of iterator dereferencing. Every time you dereference an iterator, a check is made to see if it's still in bounds.

• Dive into the source for SDL_BlitSurface.

Check what it's actually doing. Is it copying while constantly checking the boundaries of both the source and destination rectangle? Try implementing an "unsafe" version which doesn't have such checks.

• Group by type

Instead of having an unordered list of images to render, order the list by image id. This way, you can render multiple sprites at once. Let's say you want three instances of a Tree sprite. Instead of rendering the whole image, we render it per pixel. In code:

// let's assume we can read and write directly to and from a pixel surface
unsigned int* dst_pixels = g_pFramework->GetScreen()->pixels;
unsigned int* src_pixels = pCurrentImage->pImage->pixels;

// pitch is the amount of bytes to skip to go to the next line
// if the width is 640 and the image is 4 bytes per pixel, then the pitch is 2560
unsigned int dst_pitch = g_pFramework->GetScreenWidth();
unsigned int src_pitch = pCurrentImage->w;

std::vector<SDL_Rect> src_rect;

// this offset is a pointer directly to the pixel we want to start drawing at
std::vector<unsigned int*> src_rect_offset;
for (size_t i = 0; i < src_rect.size(); i++)
{
src_rect_offset.push_back(dst_pixels + (src_rect.y * dst_pitch) + src_rect.x);
}

// write multiple images at once
for (unsigned int y = 0; y < pCurrentImage->h; y++)
{
for (size_t i = 0; i < src_rect.size(); i++)
{
unsigned int* dst_pixels_write = src_rect_offset[i];

for (unsigned int x = 0; x < pCurrentImage->w; x++)
{
dst_pixels_write[x] = src_pixels[x];
}

src_rect_offset[i] += dst_pitch;
}

src_pixels += src_pitch;
}


However, great care must be taken that you don't write outside of your screen! For example, if a sprite is clamped by the bottom border, this algorithm will write outside the destination surface's memory and cause a heap corruption.

• I really appreciate your efforts! Concerning for_each vs. generic for loop I haven't been able to notice differences in performance right now with small test maps, though I will stick to your suggestion! A custom SDL_BlitSurface method is quite... difficult for now but I will keep that in mind. And last but not least the direct rendering: I don't know why I haven't rendered all static tiles layer by layer to one big cached surface for each layer so that I do not need to iterate over EVERY tile over and over again. Dynamic entities will need this though it is just small share :D – Christian Ivicevic Sep 10 '12 at 15:53