In this post I share a few hints about QSemaphore, the C++ extern Keyword, and creating circular buffers for 2 threads in the producer/consumer model.
The Overall Project
So the overall project I’m working on is to create a coin flipping simulation to see how many flips it would take to reach n consecutive results of the same coin face. The math is a bit beyond me in terms of prediction, so I’m focusing on the simulation aspect.
One of the tricks of this process is in C++, creating a random number is a bit of a hack. The good news is with the forthcoming Intel Ive Bridge processors we’ll get the RdRAND instruction for generating truly random numbers.
For now though we’re stuck with seeding rand() with srand() via a time() call, something along the lines of:
#include
time_t seconds;
time(&seconds);
srand((unsigned int) seconds);
This works but again, it’s not truly random in the purest sense of the word.
No matter, to create my simulation I wrote a simple program that spawns a few threads and iterates over a large number of ‘flips’ to see how long a streak we can create. For the curious, over 1 billion flips we usually average about 22 consecutive heads or tails.
The program spawns ‘self contained’ threads in that the result of each flip stores its result in that threads buffer. Thus, with 4 threads we get 4 sets of 1 billion flips, not 4 billion consecutive flips. I thus set out to create a producer/consumer application using semaphores for using more than one core where are larger number of consecutive flips could be simulated. To be clear this is for educational purposes — being a web guy means you usually don’t get to create such logic, and so even though we could just let the existing program run for longer, it’s not so much about actual implementation but education.
The C++ extern keyword
One of the first issues encountered was how do we create a global variable my producer and consumer thread classes can both talk to?
In other words, because we’re using a shared data structures two separate classes need to communicate with (the semaphores and buffer), it makes sense to make them global. The alternative is to create a slightly more complex class structure but I’m not interested in doing so.
With that being the case the trick with this, as I found out, is that unlike using a single file say, main.cpp, and just declaring the globals at the top of the file, when using multiple class files the compiler quickly becomes confused regarding where and when variables are declared and used.
To see the basic problem consider the basic project layout:
As this is a Qt application main.cpp is only used for setting up the UI, and can be ignored. mainwindow.cpp however, is where we react to a button press that starts our two threads:
This calls a slot in mainwindow.cpp as follows:
void MainWindow::slot_startThreads()
{
Producer *producer = new Producer;
Consumer *consumer = new Consumer;
producer->start();
consumer->start();
producer->wait();
consumer->wait();
}
Thus, we create instances of producer and consumer, these two classes inherit QThread. Both classes need access to a char buffer called buffer, which means we somehow need to make this buffer visible to both classes.
At first it would appear that we simply define buffer above main.cpp’s main() function. No go. Doing so makes buffer available to any function within main.cpp, but not any other file.
Next I tried to define buffer in mainwindow.cpp and mainwindow.h — again, no go.
To be honest I was somewhat baffled by this. If it works in a single file instance why not multiple? Well that’s when I learned about extern.
So lets say in different, brand new project we have mainwindow.cpp with the following code:
#include "mainwindow.h"
#include "ui_mainwindow.h"
#include "test.h"
int age = 1;
MainWindow::MainWindow(QWidget *parent) :
QMainWindow(parent),
ui(new Ui::MainWindow)
{
ui->setupUi(this);
test *t = new test;
}
MainWindow::~MainWindow()
{
delete ui;
}
In a class called test we have a call to qDebug() << age:
#include "test.h"
test::test()
{
qDebug() << age;
}
When we compile this code as is we get an error:
C:\QtSDK\Projects\extern\test.cpp:5: error: 'age' was not declared in this scope
But if we make one simple change in test.cpp by declaring age to be extern:
#include "test.h"
test::test()
{
extern int age;
qDebug() << age;
}
Everything works, and in the running program we spit out 1 to the console.
I needn’t go too deep into this here, for that we have this great link, but the main take-away is extern tells the compiler this value is defined elsewhere, and so long as it is, no problem.
One final point though: in our coin flipping simulation we have a few globals, and as you may have noticed from the project files screen shot, we have global.h and global.cpp.
See, in larger projects we don’t want to sprinkle too many externs around because as some will attest, globals are in fact a bad thing. I’m not quite sold on that concept (that globals are bad if used wisely), but I will say that if we need globals we should at least keep then unified in one location. Thus, in my code we have global.h and global.cpp:
#ifndef GLOBALS_H
#define GLOBALS_H
#include <QSemaphore>
// consts don't need labels in the compiler
const int DataSize = 10;
const int BufferSize = 4;
// but variables do, which means they must be extern and defined in cpp file(s)
extern char buffer[BufferSize];
extern int consecutive; // used in the full flipper application
extern QSemaphore freeSpace;
extern QSemaphore usedSpace;
#endif // GLOBALS_H
1
1
#include "global.h"
char buffer[BufferSize];
QSemaphore freeSpace(BufferSize);
QSemaphore usedSpace(0);
However, as soon as we go the global.h include file route a series of potential pitfall awaits us.
As you may notice by the comments, some variables we declare will be const, and these guys are handled differently than non-const vars with respect to global use and the extern keyword.
Also, in my code I need to include the global.h file in several places, but this means we’re now susceptible to multiple inclusion issues. Of course a decent IDE will add the boilerplate:
#ifndef GLOBALS_H
#define GLOBALS_H
[...]
#endif // GLOBALS_H
…but this won’t prevent a subtle compiler error from rearing its ugly head.
Basically, if we have a const variable we do not need the extern keyword so long as any instance of a global variable is preceded by including our global.h file. However, any non-const variable must be declared extern, and then assigned a value in a cpp file, as we’ve done above.
If we don’t do this all sorts of strange compiler errors will be generated, most having to do with the variable being declared multiple times.
A great place to learn more is this link.
QSemaphore
Moving along then, at this point I have my global data structures for storing my coin flip data. Now we need to implement the QSemaphore logic for our circular buffer.
The basic idea of a semaphore is to make a shared data item have parts that can be operated on by two or more different threads via locking. A great example of this is a circular buffer.
We start the buffer out by having a producer thread write data to it. The semaphore then marks, at a specific point, that some data has been processed, at which point a consumer thread reads and processes that data.
My thought process for this project is that the producer thread will flip the coin (generate a random number), the consumer will compare that flip to the previous and if the same, store it in a buffer which resets a consecutive flip count if a non-consecutive flip occurs.
This is by no means supposed to be the proper way to do this in terms of speed or efficiency, I just figure it’s a good way to learn about QSemaphors.
The Implementation
My application uses a single widget with a start button that when clicked, calls the slot_startThreads method defined as follows:
void MainWindow::slot_startThreads()
{
this->ui->pushButton_startThreads->setText("Working...");
this->ui->pushButton_startThreads->setDisabled(true);
QDateTime start, end;
start = start.currentDateTime();
Producer *producer = new Producer;
Consumer *consumer = new Consumer;
producer->start();
consumer->start();
producer->wait();
consumer->wait();
// output total
qDebug() << "Consecutive: " << consecutive + 1;
// reset consecutive
consecutive = 1;
// benchmark
end = end.currentDateTime();
int elapsed = end.toMSecsSinceEpoch() - start.toMSecsSinceEpoch();
qDebug() << "Elapsed time: " << elapsed << " (seconds)";
this->ui->pushButton_startThreads->setDisabled(false);
this->ui->pushButton_startThreads->setText("Start Threads");
}
I’ve included benchmark code to compare this method against a non-buffered version, please see below for results on that bit.
The producer and consumer classes are defined as follows:
#ifndef CONSUMER_H
#define CONSUMER_H
#include <QThread>
#include <QSemaphore>
#include <QDebug>
#include "global.h"
class Consumer : public QThread
{
public:
Consumer(); // for producer the only thing that changes is the constructor name
void run(); // both classes simply implement run()
};
#endif // CONSUMER_H
And implemented as follows:
#include "producer.h"
Producer::Producer() {}
void Producer::run()
{
int first_die, streak, max_streak;
streak = 0; max_streak = 0;
time_t seconds;
time(&seconds);
srand((unsigned int) seconds);
// flip logic
const int LOW = 1;
const int HIGH = 10;
for(int i = 0; i < DataSize / BufferSize; i++){
freeSpace.acquire(BufferSize);
for(int j = 0; j < BufferSize; j++){
first_die = rand() % (HIGH - LOW + 1) + LOW;
if(first_die > 5){
buffer[j] = 'T';
} else {
buffer[j] = 'H';
}
}
usedSpace.release(BufferSize);
}
}
#include "consumer.h"
Consumer::Consumer() {}
void Consumer::run()
{
char last = 'A';
int streak = 0;
for(int i = 0; i < DataSize / BufferSize; i++){
usedSpace.acquire(BufferSize);
for(int j = 0; j < BufferSize; j++){
if(last == buffer[j]){
streak++;
} else {
streak = 0;
}
if(streak > consecutive){
consecutive++;
}
last = buffer[j];
}
freeSpace.release(BufferSize);
}
}
The key drivers are the global.h and global.cpp files, defined as shown above — this is where we define the number of flips and the buffer size.
The end result of this code is 1,000,000 flips is achieved in an average of 43 milliseconds. Also of interest is in our global.h file we can define the size of the buffer used by the semaphore (aka the resource size). Smaller values like 512 for one million flips returns the same average performance as 1 megabyte. However, when we up the flips to one-hundred million a buffer size of 512 bytes averages around 4 seconds, a two-megabyte buffer in 3.5. Going to a four megabyte buffer further reduces this to 3.1 milliseconds, at which point going higher has a negligible effect on performance.
The key here is the buffer size has a direct impact on the number of context switches our threads perform, which in other words means the larger of a resource the semaphore controls the less overhead we have.
For example, a 128 byte buffer increases our benchmark time to 7 seconds simply because of the number of times we need to switch threads.
Of course it also must be said that our code is unbalanced in that the consumer thread must wait for the longer random number generation operations of the producer thread. If we spent more time on this we would make an effort to make sure our producer and consumer operate at a matching frequency.
Finally, I would point out that a single threaded version of the same flipping logic is almost twice as fast. This should not be that much of a surprise, in that the type of processing we’re trying to achieve here is largely dependent on the overhead assumed with using a generalized semaphore.
Files Used For This Project
producer-consumer
