Work, stress, and management

Now that we have entered the multi-core age, we should all be writing multi-threaded code. Even though it's nothing new, I'd still like to devote a (another) blog post to it. I came up with an extremely generic model that applies in most cases. It is based on the producer-consumer model, but with a twist. The standard producer-consumer is often a bit too simplistic in practice.

The Worker

Suppose we have a main thread that has a bunch of work to do. The work must be a number of tasks that are all the same, like for instance scaling a number of images. It doesn't really matter what kind of work it is, as long as you have a number of units that must be processed.

A single work unit is abstracted into a work object. This single work object will be processed by a process function. The process will be executed by a worker thread, who handles the work units. The work will be given to the worker by the main thread; the main thread acts like a manager.

This is a standard producer-consumer paradigm where the producer injects work, while the consumer takes work.

The Stressful Worker

Now imagine that processing a work unit takes some time, and the main thread doesn't have much else to do. This will mean that the main thread will be quick to hand out more work, piling it up for the worker as it is processing each unit one by one. This is overburdening the worker.

A solution to this problem is to have the manager wait until the worker is finished. You can optimize this and hand out a number of work units to a worker before waiting until the workload drops below a certain threshold. Note that the workload is really the length of the work queue (in the case where all work units are alike).

Another solution is to have the manager co-operate and let him do some work himself. This changes the model (and the code!) a lot since in this case, it's better to have the worker take on work by itself rather than being a slave.

Another solution is to have the manager manage multiple worker threads, one for each available core in the system of course. Depending on the type of work, it may or may not be easily possible to make use of multiple threads.

Some pseudo-code

Here's some pseudo-code to illustrate what I've been talking about.

1. The naive implementation, which causes overburdening the worker:

# the manager (producer)

for work in pile_of_work {

worker.give_work(work)

}

worker.time_to_go_home = 1

# the worker (consumer)

forever {

work = get_work()

if not work {

if time_to_go_home {

exit

}

continue

}

process(work)

}

2. The stressful worker, with a kind manager:

# the manager (producer)

for work in pile_of_work {

while worker.workload >= max_load {

sleep a bit or do something else

}

worker.give_work(work)

}

worker.time_to_go_home = 1

# the worker (consumer)

forever {

work = get_work()

if not work {

if time_to_go_home {

exit

}

continue

}

workload += 1

process(work)

workload -= 1

}

Clever people will note that sleeping is ugly and the manager should block instead until it is notified by the worker that it is done doing its job. This is best implemented using condition variables:

# the manager (producer)

for work in pile_of_work {

worker.give_work(work)

manager_condition.wait()

}

worker.time_to_go_home = 1

# the worker (consumer)

forever {

work = get_work()

if not work {

if time_to_go_home {

exit

}

continue

}

workload += 1

process(work)

workload -= 1

if workload < maxload {

# signal I'm ready for more

manager_condition.signal()

}

}

In this last case, I let the worker decide if he's ready to take on more work.

Python programmers get away easy: there happens to be a standard Queue class that implements the above workqueue, complete with a maximum workload that blocks the producer when the worker is being overburdened.

tutorial: Key Value Coding done right

In MacOS X / Cocoa, there is this concept of "Key Value Coding". It allows you to loosely couple objects together in a flexible way. For example, this is used by NSCollectionView to glue the interface (the GUI) of the program to the actual code of the program.

Key Value Coding means that you can get the value of a property by its key (which is a string). Note that this is exactly what a NSDictionary does, so making your custom class work with KVC, is a lot like making it look like a NSDictionary.

If you are still confused about what KVC is and want to know more, you may read the excellent page on KVC at MacResearch.

Turning a class into a KVC class

To make a class KVC compliant, it has to respond to the -valueForKey: method. The quick and dirty way is to implement this by checking the string and returning nil if it's an unknown key. In many cases this will actually work. There are some little extras that you should know, though. They are best explained by example:

@interface Album : NSObject {

NSString *artist, *title;

}

@property (retain) NSString *artist, *title;

// in Album.m

@synthesize artist, title;

-(id)valueForKey:(NSString *)key {

if ([key isEqualToString:@"artist"]) {

if (artist == nil)

return [NSNull null];

return artist;

}

if ([key isEqualToString:@"title"]) {

if (title == nil)

return [NSNull null];

return title;

}
@throw [NSException exceptionWithName:NSUndefinedKeyException reason:[NSString stringWithFormat:@"key '%@' not found", key] userInfo:nil];
return nil;

}

-(NSArray *)allKeys {

return [NSArray arrayWithObjects:@"artist", @"title", nil];

}

-(NSArray *)allValues {

return [NSArray arrayWithObjects:artist, title, nil];

}

Concluding

When making your class KVC compliant, take care of the following:

• implement -valueForKey: and check the name of every property
• if the property is nil, return [NSNull null] to indicate that the value is nil
• throw an NSUndefinedKeyException if the key is not found
• implement -allKeys, returning an array containing all valid keys
• implement -allValues, returning an array containing all values

flocking boids

Hi ... I got a bit stuck with my 3D space game when trying to get real-time impostors right. Impostors are dynamic billboards for rendering hundreds of distant asteroids. After a three week holiday, it was hard getting back into the code, so I put it on hold for now. On the bright side, I started working on a new arcade game that is really 2D, but with a 3D twist. It is inspired by Geometry Wars / |g|ridwars, GridRunner, and another old Jeff Minter game that features four cannons along the screen edges.

An intern that I'm currently working with, pointed out flocking to me. The guy is studying game technolology — you can actually get a master's degree in game technology nowadays, how great is that?

Anyway, flocking, also known as swarming, is a technique reminiscent of particle systems. While particle systems simulate physics models like fireworks, smoke, or fountains (water drops), flocking is an AI system that is great for simulating groups of animals. An impressive YouTube video shows such a simulation of a flock of birds that is under attack by two birds of prey.

On first thought, you might think that group behaviour is programmatically implemented by controlling the group as a whole. This is not true. Every bird (or boid, as the bots are called) in the flock is an autonomous entity sporting its own artificial intelligence.

How is this implemented? Each boid has an area of sight. If it sees it is going to collide with another boid (or object), it will adjust its heading to avoid collision.

At the same time, the boid wants to stay with the group. It does this by adjusting its heading, to get close to others, while trying to match the heading of a boid that is near. As a consequence, the boid will follow others.

Coming from an age when computers were slow, I first thought that this would be too slow to do in real-time. As it turns out, a modern cpu has no problems whatsoever with the little bit of math required for directing each boid. A pitfall is to have a boid influence another, and recursing because this action influences another, and ... You should not try to solve a mathematical puzzle here. Instead, focus on only one boid at a time and have it make the decision of how to adjust its heading. Do this for every boid, every discrete time step.

I implemented the AI rules in 2D in a game, and while the result is not as impressive as the flock of birds video, it is kind of cool. I started out by making sure that the monsters (or boids) would no longer pass through each other. This is done with a simple circle collision test. When a monster collides, it chooses another direction to move in. Once this was working, changing the code to get flocking behaviour was rather easy: increase the collision radius (area of sight) and adjust the direction only slightly rather than choosing an entirely different direction.

One problem I ran into was that the play area in this game is small and I don't want monsters to fly off the screen. So, the monster had to turn at the edges. Again, increase the area of sight, and have it adjust the direction.

In the game, the gliders (paper airplane models) flock together, while the magenta thargoids are going around like bumper cars, and are disturbing the gliders. The yellow cubes are stationary obstacles in the arena.

Note that it is possible to extend the AI with more rules, but flocking is a technique that already yields quite amazing results with just a few simple rules.

Vertex Buffer Objects - what you can and can not do with them

In 3D games, models consisting of thousands of vertices and polygons, are rendered to screen at least at 30 frames per second. For every frame, these vertices are transmitted from the memory to the GPU over the bus. For static models, this is a huge waste of time and bus bandwidth, because the vertices are the same for every frame. Why not cache the data in graphics memory and tell the GPU to get it there? This is what vertex buffer objects (VBOs) are all about.

In my 3D space game, I added the 3D model of an asteroid. The model has ~2700 vertices, which is not much at all (by modern standards), but I decided it should be a VBO and enable the code for even higher detailed models.

Never having used VBOs before, I took the safe route and implemented the asteroid first without any VBO code, and rewrote it later to use a VBO. This was a lot of extra work, but there were some lessons learned.

I found the following:

• use GL_TRIANGLE_STRIP for the most efficient way of rendering shapes. However, for most meshes from 3D modelers you would use GL_TRIANGLES. For the asteroid, I use GL_TRIANGLE_STRIP.
• Use glDrawElements() rather than glDrawArrays(). Making an extra array with indices seems more work but is very worthwhile the extra effort.
• I had to include degenerate triangles to stitch multiple triangle strips together. Degenerate triangles are 'fake' triangles that refer to the first vertex in the next triangle strip. (Consider triangle ABC, and degenerate triangle DEE to refer to EFG).
• ARB extensions for VBOs are old-fashioned by now. VBOs have been included in OpenGL for a long time and you can use the functions without the need for meddling with ARB extensions.
• Allocating a new VBO for every type of coordinate is wasteful. Instead, allocate a single VBO to store vertices, texture coordinates, normals, colors, etc. and use glBufferSubData() to place the data into the vertex buffer object.
• If you use glDrawElements(), you must buffer the indices using a separate VBO. The reason for this is that the indices have target GL_ELEMENT_ARRAY_BUFFER. I tried mixing indices into subbuffers (GL_ARRAY_BUFFERs) and it did not work for me.
• If you do not have an array at hand, but generate coordinates on the fly, use glMapBuffer() to get a pointer to memory. Mind that you are not directly writing into graphics memory; the buffer will be copied to graphics memory by glUnmapBuffer().

So, are VBOs the golden egg? Well, no. They are a great way of speeding up the rendering of high poly-count meshes. There are things that VBOs are simply not suited for. This has to do with both the limitations of OpenGL and what it is that you're trying to achieve. For example, I tried loading the stars into a VBO. This turned out not to work very well, because in my code, stars are point sprites, and each star has a specific point size. Since you can not set the point size in a vertex array, it also makes no sense to use a VBO. I sorted the stars by size to draw them as a vertex array nevertheless, but this resulted in a low vertex count per call so it still makes no sense to use a VBO here.

I also noticed that 1D textures do not work in vertex arrays. Maybe I'm using them for the wrong purpose (texturing GL_LINEs) but considering that glBegin/glEnd is practically deprecated there may be a problem here.

Another problem I had was with face culling. This is not the VBOs fault, but I suspect that when you drape a triangle strip into a convex shape, it may show artifacts. Enabling depth testing did not help me here, but disabling face culling did.

Although VBOs are an add-on to vertex arrays, it seems like OpenGL always requires you to turn your code inside out when you want to change something. I stuck to static meshes for now and decided to abstract a VBO class from it, which wasn't exactly easy either. Anyway, here is a link to a site that I used to implement VBOs:

• http://www.ozone3d.net/tutorials/opengl_vbo_p2.php