Monday, 21 December 2009

Developer Journal 0 - Smart Pointer, Spatial, and Drawing Bottlenecks

I've been working on improving the performance of my simulator. I started by profiling my code with gprof and found that the bottlenecks were caused by using smart pointers, communication code and drawing.

The Smart Pointer Bottleneck

The smart pointer bottleneck was easy to fix. The bottleneck was due to creating a new smart pointer for each loop. The solution was to access my agent object directly. Although this was an easy fix, the hard part was learning to profile code to figure out the bottleneck location. The old code was:

for( int i = 0; i <> myAgent;
agent = myVector[ i ];

The improved code was:

shared_ptr<> myAgent;
for( int i = 0; i < myagent =" myVector[">DoSomething();

Another improvement was:

for( int i = 0; i <>DoSomething();

The Spatial Bottleneck

The second bottleneck is a harder problem. When an agent sends a signal, agents need to check whether there are other agents within range to receive the signal. If you have 100 agents, then the number of checks increase quickly. I suspect that I'll need some kind of spatial data structure to solve this problem. Unfortunately, most spatial data structures are for things that don't move such as floors and walls.

For now I am putting off solving this problem but I am thinking of using a simple 3d grid structure approach after I've taken care of the drawing bottleneck.

The Drawing Bottleneck

The drawing bottleneck has a two causes. The simulator draws things in an inefficient way and draws things that don't need to be drawn.

Each time the simulator draws a scene it sends a bunch of information to the video card. For example, each agent has a different model, so when the simulator draws 100 agents, it has to send 100 different models to the video card about 30 times a second.

The thing is, agents all use the same model with different sizes.

The new code sends the model to the video card once. Then, each time the simulator draws a scene, it sends size information to the video card and then uses the model that is already in the video card. This way, there is a lot less information that needs to be sent from the simulator to the video card.

Display Lists

Since I am using OpenGL, the first thing I'm using is display lists. I've read in Astle & Hawkins (2004) that display lists may increase performance only on some video cards. However, they seem easy to use and by changing my code to use them, I'll be setting up the code to later use vertex buffers.

There are a few ways to use display lists which I'll be trying out. I don't know if there is a big enough difference between each of the ways. When you're using display lists, you can call one list at a time or a group of lists in one call.

In my code, each list is a polygon. You can get each list to include more than one polygon at a time.

Combining each of those options creates 4 options.

Vertex Buffers

I think that when I test out using vertex buffers, I'll have a similar number of options to try.

Viewing Frustums

So that wraps up drawing things inefficiently. Now, onto drawing things needlessly. At the moment my code does not use a viewing frustum to reduce the amount of drawing. I know that this is a basic step but it was not something I needed until now. Luckily, there has already been some code written for using frustums so I only need to activate it.

Scene Graphs

The next thing to try would be scene graphs. Scene graphs allow you to filter out things you don't need to draw by looking at the larger group that things belong to. For example, if there are two houses and you're only looking at one. You don't need to draw the other house and all the things in it.

However, scene graphs seem to be more for things that don't move much. In my simulation, the bottleneck is from drawing agents and my agents move a lot. This is similar to the problem of figuring out a spatial data structure for communication.

Once I've tried out the simpler changes for increasing drawing efficiency I'll do some reading about scene graphs. There are a few graphic programming books that seem to discuss this well but I feel that possible answers are more likely in game physics programming books. This is because scene graphs in physics simulations must deal with lots of moving things.

No comments:

Post a Comment