JobSwarm : A microthreading framework with lockless FIFO

(I'm trying to use Google Code for the first time. You can try getting the code from there at this link. Please read the latest post about JobSwarm on this site.)

I used part of my Christmas break to implement a system that I have been wanting for a long time. I call it a 'JobSwarm'. What it is, is a micro-threading library that can handle tens of thousands of extremely tiny jobs with almost no overhead.

In the sample program provided I compute a fractal by decomposing it into 65,536 individual jobs, each one representing 64 pixels of a 2kx2k image.

The usage pattern for the JobSwarm is as follows.

First, you create a JobSwarmContext. This is a single instance of the JobSwarm system. When you create a JobSwarmContext you tell it how many physical threads you want to use. You can either create a single JobSwarmContext for your entire application, or you can create different ones in various subsystems.

When a JobSwarmContext is released any currently executing jobs will have to be completed before the method can return.

To use the JobSwarm you simply inherit the pure-virtual interface 'JobSwarmInterface' and implement three methods.

They are:

job_process
job_onFinish
job_onCancel

You find this interface in the header file 'JobSwarm.h' and enclosed in the namespace 'JOB_SWARM'.

A simple example of how to use this is in 'fractal.cpp' and in the class 'FractalJob'.

The three methods are implemented as follows:

job_process : This is the actual 'work' this job is supposed to do. This code will operate in a seperate thread and, therefore, must be entirely thread safe.

job_onFinish : This is a method which is called when your job has completed. This method is invoked in the main thread (the thread which owns the JobSwarmContext). This allows you to do anything with results you may have computed during the 'job_process' call.

job_onCancel : This is a methd which is called when your job was cancelled. This method is called from the main thread.

To manage the job swarm you use the following methods on the JobSwarmContext.

createSwarmJob : This creates a single job to be processed.

cancel : This cancels a previously posted job. It is very important to note that this only marks the job to be cancelled! You cannot destruct the job until you recieve the 'job_onCancel' callback.

processSwarmJobs : This is a 'pump' loop method which is called from the main thread. This call allows completed and/or cancelled jobs to be despooled. This is a very lightweight call but if you forget to invoke it none of your job completion events will ever occur.

setUseThreads : By default the job swarm system runs using hardware threads. However, for debugging and/or performance comparison tests, it can be toggled on and off on the fly. Setting 'useThreads' to false does not close out the hardware threads themselves, it simply moves the 'work' of the individual jobs into the main thread when you call the 'processSwarmJobs' pump method.

I am releasing this JobSwarm code for a reason. First, I hope other people might adopt it and improve the code and I would, thereby, benefit from it. I was also frustrated in my efforts to find a very tiny and simple micro-threading solution by searching on the net.

This system could use some improvements. For example, in addition to needing a true lock-free FIFO, it also might be nice if it supported job priorities.

It also might be interesting to support inter-job communication, if that sort of thing made sense and/or was useful.

I am making this code available in two forms.

First, as a small console application with just a tiny amount of source code.

You can download it from JobSwarm.zip

The source included with 'JobSwarm.zip' is as follows:

fractal.cpp and fractal.h : A very simple fractal routine which can solve the fractal in a linear fashion or by breaking it up into 65,536 distinct 'jobs'.

JobSwarm.cpp and JobSwarm.h : The main JobSwarm system. Has no OS dependent code in it.

LockFreeQ.cpp and LockFreeQ.h : Provides a lock-free circular queue for a single provider / single consumer system. Also provides an API for a lock free FIFO, however the implementation currently does use locks.

main.cpp : The console demo/test app.

pool.h : A double linked list template class used by the JobSwarm to manage jobs. Minimizes memory allocations.

sgif.cpp and sgif.h : A snippet of code to save a block of memory as a GIF image.

ThreadConfig.cpp and ThreadConfig.h : A wrapper layer to hide OS dependencies for threading related calls. Intended to be multi-platform but the current implementation is only for Windows.

The second application is a larger framework called 'ThreadFrac', which provides an interactive graphics application which allows you to visually see the performance differences when toggling the job swarm on and off on multi-core machines.

You can download and install it from ThreadFrac.exe

I look forward to bug-fixes, improvements, and feedback from the development community.

Thanks,

John

--------------------- Revision update January 3, 2009 --------------

I made the following important revisions to the JobSwarm.zip download.

• I removed the source files 'fractal.cpp' and 'fractal.h'
• I revised the 'main.cpp' to act as a much simpler example program on how to use the JobSwarm system. Simply look through and/or step through the code that is there.
• I created two separate examples of how to use the JobSwarm system.
• First : One class with a callback interface is created for each separate job. This may be the most common use case but requires more setup and memory allocation in some use cases.
• Second: A single class receives callbacks for all of the 'jobs' and it uses the user data and user id field to figure out just what needs to be calculated in that context.
• I added support for a userData and userId field for jobs. This extra meta data is available as an optional additional information to pass into the job service callbacks.
• I fixed a crash bug that would happen occasionally when trying to deconstruct the JobSwarmContext
• This version was built with VC2008. If you have an earlier version of VC you won't be able to load the solution and project files. Simply create a new console app and add the source files, that is all you need to build the example program.
• 
  

Thanks to everyone who previously downloaded the sample and gave me feedback. It was all very useful.