Lock-free, multi-threaded Mandelbrot

(yeah, the title is stupid)

After I got a little bored with memory experiment I moved on to something more interesting - lock free containers and multi-threaded tasks/jobs. This is all rather new to me, so it seemed like an interesting stuff. What we have here is simple system for distributing independent tasks on multiple threads. Basic system was inspired by Industrial Light&Magic’s code from OpenEXR. Main difference is that attached snippet is basically lock-free (it only locks when initializing threads at the very beginning). Queue is basically an implementation of Fober’s/Orlarey’s/Letz’ paper: “Optimized Lock-Free FIFO Queue continued” (to be tested: whether the optimization mentioned in this paper really helps in the situation of values so cheap to copy, it may not, but feels more consistent).

Now, as usual – it’s just an experiment. To be honest I’m not sure if I’d want to use it in production code. In real life tasks are usually rather expensive anyway, so the cost of locks is amortized. What’s more important - debugging lock-free code is a nightmare, in most cases all you can do is try to analyze it and shoot in the dark. One tip I can give you in case of containers - write basic version of algorithm first, without caring about threads at all. When it works – modify. Divide problem into sub-problems. At first, I thought - “bah, queue, that’s easy, let’s go”. 15 minutes later, I quietly coded single-threaded version and went from there. Another problem is that it’s not enough to have lockless container, there are other issues to take care about. Take waiting for all the tasks to finish for example. With locks, we can just lock on number of tasks and use “inverted semaphore” to signalize that group is empty. Without, we can create one semaphore per task and wait for all of them, but I dont like this solution too much. Attached code uses simple way: atomic counters.

Anyway, test application plots Mandelbrot fractal in 512x512 resolution (and saves as TGA file). For comparison, there’s a single-threaded version and one with 4 threads, each running multiple tasks. Each task plots a horizontal slice of image (number of lines per task depends on number of tasks, it can be specified from commandline. For example: threadtest.exe 64 -> run with 64 tasks). It’s a very simple example, because tasks are totally independent and operate on separated pieces of data, so it’s a perfect situation. As expected, on my dual core laptop I’m getting nearly 2x speedup (it may be a little less, because I’m running some dummy tasks as well, just to stress the system). World’s fastest Mandelbrot wasnt really a point here, BTW, this should be done other way anyhow, for good example see Crystal Dream 2 (and that’s 486, my friends).

Source code and executable can be downloaded here. (I’ll gladly accept bug reports, as I said - it’s a learning experiment).

PS. And now for something completely different - make sure to visit Gamasutra and read Timeshift postmortem, game with probably the most extraordinary development cycle ever.

[Edit] Source code re-uploaded.

Old comments

ed 2008-04-10 22:39:21

As for Crystal Dream mandelbrot, I believe it was only zoomer with precalculated images (zoom 8 frames, next image, zoom 8 frames, next image etc). We did this the same in our demo on Atari XL/XE :) http://youtube.com/watch?v=zZDwRAnVmPc (wait to 7:20). Although in our version with lower resolution you can actually see zooming artefacts.

admin 2008-04-12 10:43:16

Yeah, it was obviously impossible to have true zoomer at that time. Still, it’s the result that matters and it looked (still does) pretty impressive. Havent seen that demo of yours before, BTW, pretty nice as well, spent some hours yesterday watching some totally oldschool Atari/C=64 stuff :)

j0rn 2008-05-22 06:56:46

Hey dudes, take a look back to CD2, it was not precalculated, the coder just specifies in it, in credits/faq at the end of the demo, I remember that ;)

John W. Ratcliff 2009-01-05 20:21:11

Weird, I was working on the same exact project but had never found your version before.
The link to download the project appears to be dead. Do you have a version I can look at?
You can check out my version on my coding site, it is called ThreadFrac
John

admin 2009-01-06 08:49:55

Doh, you’re right, project vanished from the server in mysterious circumstances. I’ll re-upload it later today.
I already have your version, I’ve your Code Suppository in RSS reader. Haven’t had a time to examine it in detail yet, though.

Tristan Matthews 2011-08-02 03:55:37

Thank! Your code saved me some time, I ported a slightly simpler version to GCC if you’re interested.