Category Archives: Programming

Programming topics. Threads, graphics, realtime, whatever.

Small revisit of C++ message passing (in a threaded program)

The post C/C++ Message Passing from June ’08 is one or the more popular ones, if Google Analytics is to be believed. Not only that, but every one who arrived there by Google search was looking for C++, not C.

Upon re-reading it, it occurs to me that it would be a good candidate for being a lock free structure.  With C++0x, this should be pretty simple to do, using the new atomic template.  For straight C though, I would have to use compiler specific extensions (or inline assembly), so there may be little reason not to make a C++ specific version of the code that is lock free.

I’ve also thought of trying to use C++0x to construct a purely functional data structure library.  In that case, C++0x would be chosen because of the new shared_ptr addition.  I might have to have a post soon exploring that idea a bit further.

So far, I’ve converted this to be a C++ class and to use templates instead of void*s. Otherwise, it still behaves the same and still uses pthread locking directly. Additional versions will be forthcoming. Here is the recent work.

Hopefully it will be of use to some of the searchers. Keep an eye out for future revisions.

Circular buffers as C Macros

I was recently reviewing some FIFO based serial TX/RX circular buffer code that I thought was buggy in the FIFO part.  Since the FIFO was entwined with the ISRs, it was hard to test in isolation.  I looked around at some other FIFO implementations for PIC and AVR, and all of them did the same thing, including duplicated all of the FIFO code for every serial port implemented.   It seemed to me that it would be better to have the two activities separated to provide better re-usability and test-ability.

Back when I was working on PCI audio drivers, I thought the same thing.  Everyone wrote their sample FIFOs directly into the ISR functions in the driver.  Back then, I seperated my FIFO out into a separate reusable module that could be tested thoroughly from user land.  I grabbed that to use on my current project, but it depended on malloc and free, something notably missing on a lot of 8 bit micro controllers.  Also, it would result in extra function call overhead, which is not good in ISRs on PICs (very limited hardware call stack).

Anyway, after debugging the FIFO in my ISRs, I decided to extract it all out into a file of just that code. Then I transformed those functions into macros to do away with the function call overhead.

Here is draft 1, if it is of any use to anyone, and even if it isn’t I certainly wouldn’t mind review/commentary.

I could wrap the globals into a struct, but then I still would need a
custom struct for each instance to change the size of the array at run
time, unless I required a global struct, and MAKE_FIFO inserted a
pointer to a global array…

I’m not sure, which might be better.

Also, if you were to need 32bit elements instead of 8 bit elements, just change the type in MAKE_FIFO.

/**
* @file
* @author Joshua Boyd
* @version 1.0
*
* @description DESCRIPTION
*
* Macros for statically allocated, circular buffer, character FIFOs.
*
* NOTE: change the types in MAKE_FIFO to support types other than
* chars. Should just work for any primitive type, and only
* a little more work for structs.
*
* The basic usage is to MAKE_FIFO your fifo, giving it a name and size
* then GET, PUT, etc, the fifo of that name.
*
*/

/**
* Make a new FIFO.
*
* @param prefix - the name of the fifo, eg. 485_tx, or 232_rx.
* @param size - number of elements in the fifo.
*/
#define MAKE_FIFO(prefix, size) \
char prefix ##_buffer[size];\
long prefix ##_next_in = 0;\
long prefix ##_next_out = 0;\
long prefix ##_ovfl=0;

/**
* Get and remove an element from the FIFO.
*
* Value here works a little like a reference in C++.
*
* @param name of the fifo
* @param Location for the returned element.
*/
#define GET(prefix, value) { \
value=prefix ##_buffer[prefix ##_next_out]; \
prefix ##_next_out = (prefix ##_next_out+1) % sizeof(prefix ##_buffer);}

/**
* Get an element from the FIFO without removing it.
*
* Value here works a little like a reference in C++.
*
* @param name of the fifo
* @param Location for the returned element.
*/
#define PEEK(prefix, value) { \
value=prefix ##_buffer[prefix ##_next_out];}

/**
* Remove an element from the FIFO without getting it.
*
* @param name of the fifo
*/
#define REMOVE(prefix) { \
prefix ##_next_out = (prefix ##_next_out+1) % sizeof(prefix ##_buffer);}

/**
* Return the index of the next input location.
*
* NOTICE: This is the only macro meant for internal use, and not the
* application programmer.
*/
#define NEXT_IN(prefix) ((prefix ##_next_in + 1) % sizeof( prefix ##_buffer ))

/**
* Put an element into the FIFO.
*
* @param name of the fifo
* @param Value of the new element.
*/
#define PUT(prefix, value) { int8 t; \
prefix ##_buffer[ prefix ##_next_in ] = value; \
t = prefix ##_next_in; \
prefix ##_next_in = ( prefix ##_next_in + 1) % sizeof( prefix ##_buffer ); \
if(prefix ##_next_in == prefix ##_next_out) { \
prefix ##_next_in = t; \
prefix ##_ovfl = 1; }}

/**
*
* Set the points back to as if it were empty.
* Doesn't erase the data, but only a GET or PEEK will
* return garbage after this has been called.
*
* @param Name of the FIFO
*/
#define FLUSH(prefix) prefix ##_next_in = prefix ##_next_out = 0

/**
* Is the FIFO empty? True/False
*
* @param FIFO name
* @return T/F
*/
#define IS_EMPTY(prefix) (prefix ##_next_in == prefix ##_next_out)

/**
* Is there any data? True/False.
* Basically the opposite of IS_EMPTY
*
* @param Name of the FIFO
* @return TRUE/FALSE
*/
#define IS_NOT_EMPTY(prefix) (prefix ##_next_in != prefix ##_next_out)

/**
* Is there any data? True/False.
* Basically the opposite of IS_EMPTY
* The same as IS_NOT_EMPTY
*
* @param Name of the FIFO
* @return TRUE/FALSE
*/
#define KBHIT IS_NOT_EMPTY

/**
*
* Is the FIFO full? True/False
*
* @param FIFO name
* @return TRUE/FALSE
*/
#define IS_FULL(prefix) (NEXT_IN(prefix) == prefix ##_next_out)

/**
* Is there free space?
* This is basically the opposite of IS_FULL
*
* @param FIFO name
* @return TRUE/FALSE
*/
#define IS_NOT_FULL(prefix) (prefix ##_next_in>prefix ##_next_out?prefix ##_next_in-prefix ##_next_out:(prefix ##_next_in+sizeof(prefix ##_buffer) - prefix ##_next_out))

/**
* Is there free space?
* THis is the same as IS_NOT_FULL.
* This is basically the opposite of IS_FULL
*
* @param FIFO name
* @return TRUE/FALSE
*/
#define AVAIL IS_NOT_FULL

toStr revisited

After my initial toStr C++ exploration, I recent found myself reading about Boost’s lexical_cast, which is does something similar, albeit more general and with more verbosity. lexical_cast will not only convert nearly anything to a string, it will also do its best to convert anything to anything, via a string in the middle.

Upon finding that, I was considering rewriting toStr to use lexical_cast (the only reason to hang onto toStr at all would have been for brevity in my code), but then I somehow stumbled upon Herb Sutter’s article The String Formatters of Manor Farm, which talks about the performance of various int to string methods. As it is, int to string is what I use my toStr function for most of the time (followed by doubles probably), so this is the performance I’m most interested in.

From Herb’s article, I learned that lexical_cast was extremely slow. stringstream, which is what the current implementation of toStr uses, is also extremely slow (but not as bad as lexical_cast). On the other hand, snprintf is very fast. I verified this with some of my own tests on Solaris/SunStudio and Linux/GCC. Rather then write up my own performance tests, allow me to refer you to this write up, as well as back to Herb Sutter’s article that I reference above.

snprintf requires explicit formatting strings, but this isn’t an issue because I can specialize the template for certain types, like ints. And, if I know the type, then I also know the maximum length string that can be generated. For instance, a 32 bit int, is 12 digits (The ‘-‘ if negative, 10 digits for the main number, and one digit for the trailing \0), while a 64 bit int is 22 digits. I could also figure out the maximum size for floats and doubles, but I haven’t yet done so.

So I will now modify toStr to include the existing version while specializing to be about 17 times faster for ints.


template
static inline std::string toStr(T v)
{
std::stringstream s;
s << v; return s.str(); } template <>
inline std::string toStr(int v)
{
//max 64 value: 18446744073709551615
char tmp[22]; //derived from the max 64bit value + 1 for '-' and 1 for \0
snprintf(tmp, 22, "%i", v);
return std::string(tmp);
}

PostgreSQL connection pooling for mod_php

In a quest for better performance with postgres, I’ve been looking for connection pooling tools. There are a few quirks that I tend to require be met. First, it must run on Solaris. This isn’t so much a quirk, since the server runs Solaris and is SPARC hardware, and I’m not going to install a second server in colo just to accomodate software that doesn’t work on Solaris/SPARC. Additionally, I refuse to install GCC, so it must build with Sun Studio, which is much more GCC compatible that it used to be, but still isn’t GCC. Also, I want it to be reasonably simple to install and setup. I am willing to consider prebuilt packages from sunfreeware. If I get desperate enough, maybe even blastwave. Unfortunately, none of the top choices appear to be on sunfreeware.

The top choices appear to be:

  • pgpool
  • This is the classic choice, building and install is easy, but setup is very arcane.

  • pgbouncer
  • This looks like it should be simple to install and setup, but the configure script refuses to find my libevent install.

  • SQLRelay
  • Works for many databases, unlike the others, including sqlite. However, it requires the rudiments library from the same author, and this library won’t build because the autoconf stuff doesn’t understand anything but GCC.

So, I haven’t broken down to checking out blastwave yet, but so far none of the normal choices are working out for PostgreSQL connection pooling.

Then, I made a small breakthrough when I found that PHP has pg_pconnect. pg_pconnect does some background bookeeping to keep connections open after you call pg_close, and return the same connection if the arguments are the same. Practically, this means that if you use a PHP system that keeps persistant php interpreters (say, mod_php in Apache, which is what I use for PHP), then you have effectively gotten connection pooling for PHP only.

This is a big help already, but I still need a solution that helps out with python.

Yes, I am working on a little web development on vacation.

Databases for simple web development

I have log been a fan of PostgreSQL over MySQL, believe that PostgreSQL is more feature complete and generally as fast or faster, with obvious caveats about being used appropriately, of course, and not to mention no real comparative testing. Every body gets to have an untested opinion, right?

I did end up doing some performance testing though. What I learned is that both are reasonable fast at simple queries. Great. However opening a new connection to MySQL is much faster than opening a new connection to PostgreSQL. Once the connection is open, but seem equally fast for very simple tests.

Why this matters though is that simple web development in many languages with the most common tools don’t do connection pooling. If you want to just whip up an example PHP program using mod_php, then every page load will result in a new connection. The same goes for mod_python or mod_wsgi (as well as frameworks sitting on top of those plugins). Using each of these common tools with PostgreSQL results in a slow web site. This was driven home when I upgraded from a single 550mhz UltraSPARC II to a dual 1.1Ghz UltraSPARC3 III, and still certain web apps I’ve been tinkering with writing using PostgreSQL for the database are slow.

Certainly there are ways around this. Using a database connection pooling tool for starters, would certainly cure the problem. Also, choosing something that keeps your script running (or a least your database connections open) would also help. Or even writing your application as stand alone program that keeps the database connections open and talks to the web server via JSON-RPC or XML-RPC. But, to quickly whip something out MySQL may be simpler.

Of course, for some applications Sqlite could be a contender. Certainly it is very fast, and very simple to use. For a scalable web site though, it is probably out of the question. There is a reason that Django defaults to using Sqlite first though. And there are also, those less traditional database servers like CouchDB or memcachedb which seem to generally have very fast connection times.

This is a bit disappointing though. AOLServer used to offer connection pooling built into the web server. Of course, I certainly don’t want to use TCL as my development language, but still that would be nice to have.

Meanwhile, can anyone suggest a good Solaris and PostgreSQL connection pooling library?

toStr – A small C++ utility function.

This can be used as string(“bob”) + toStr(5) without declaring the type, presuming that the type can correctly be inferred by the compiler. Obviously, T must support operator<<.

template <class T>
static inline std::string toStr(T v)
{
  std::stringstream s;
  s << v;
  return s.str();
}

RESTful message queuing in Python

Alright.  Pass 1 is done.  Here is a link to it.  The server is in Python.  Clients in PHP and Python are provided.  It follows this design document.  On a quad Opteron, it gets about 600 short messages a second.  It isn’t threaded.  Next step on this project is to redo this in Erlang.  And then maybe C++ for the heck of it.

This uses WSGI, specifically the wsgi reference server, so in theory it shouldn’t be hard to adopt to other wsgi servers, like mod_wsgi.  However, beware of problems of thread safety.  Also beware that wsgi servers that use multiple processes will require some sort of external data store instead of process local memory.

(edit: Download link was moved to github, design doc link was also changed)

A new message queuing system

First, why a new one?  Because I haven’t found any that do what I need and look simple and well supported.  Besides, it seems like a reasonable learning experience.

The initial summary of what I need is a light weight method for PHP (in the form of scripts running in mod_php) to send messages to a back end program written in Python. However, in the future other languages may be used, so general cross language compatibility is important. That means either bindings exist for every conceivable language, or bindings are trivial to write.  Also, the solution must run on Solaris.

Comparison:

At work I use Apache QPID, which is an AMQP implementation. I can’t find any PHP client for AMQP though. I was able to find discussion that suggested that the AMQP protocol is too heavyweight for PHP being run in mod_php.

Looking at other solutions, I don’t want to run anything that requires Java for the server. That rules out Apache ActiveMQ and other JMS systems. I also believe that XMPP is too heavy weight to parse.  I also found some systems written in Perl, Ruby, and PHP, but they looked rather slap dash, and I don’t particularly want to use those languages.  The initial requirement for supporting PHP is only because I’m working on a PHP web app that I forked.  I do not want to add any new PHP code bases that I need to maintain.  Besides, once I start looking at fringe choices, it gets to be a lot easier to justify writing my own, particularly if I am going to use it as a learning project to get more familiar with, say, Erlang.

Summary:

It is to be a RESTful design.  I will be using JSON for the payloads, but I haven’t decided yet if it makes sense to force this, or if it makes sense to allow all ascii data.  Queues will be single read, meaning that if multiple end points need to get the same message, then there will need to be a separate queue for each end point.  Initially there will be no security model or persistence.  Commands will be standard HTTP verbs.  If possible I will try to make response codes valid HTTP response codes.

Goals:

Run on Solaris

Support Python, PHP, and Javascript as clients.

Limitations:

Initially this will not support persistence.

Also, this will not support any security.

Commands:

PUT queueName

Create a new queue. What the responses will be still need to be decided.

Responses:

201 created, entity required, probably just a confirmation message

409 already existed.

POST queueName

The body of the post will be the contents of the message.

403 queueName wasn’t found.

201 created, and perhaps the entity will be an id for the message.

GET

Gets that do not match the following patterns will be answered with a 404.

GET msg/queueName

Get the next message from the queue queueName.  Here I need some way to to return a message ID in addition to the message body.  It may make sense for the response to be JSON: {‘id’: integer, ‘content’: <valid JSON here>}

If the response is as proposed, the the contents of the POST must be valid JSON as well.

403 queueName wasn’t found.

200, the message

GET queues

Get a list of the created queues.

200

DELETE queueName/integer

Delete a message identified with integer from queue queueName.

204 deleted, no entity required

403, queuename or integer not found.

DELETE queueName

Delete a queue and all the messages in it.

204 Deleted, no entity in response

403 queueName wasn’t found

Thread Worker Pooling in Python

The worker pool pattern is a fairly common tool for writing multi-threaded programs.  You divide your work up into chunks of some size and you submit the to a work queue.  Then there is a pool of threads that watch that queue for tasks to execute, and when complete, they add the jobs into the finished queue.

Here is the file.

Thanks to Global Interpreter Lock, threads are of somewhat limited usefulness in Python.  I foresee myself mostly using this for network limited tasks, like downloaded a large quantity of RSS feeds.  My idea is that tasks put into the system shouldn’t modify global state, so if I actually needed this for computational tasks, it may be feasible to build it on forks instead, or perhaps the 2.6 multiprocessing system.  However, I still use a lot of systems with only python 2.3 installed, so I’m not likely to want to write 2.6 specific code anytime soon.

Many of the thread pool systems I seem have you specify a single function for the pool, then you just enqueue the inputs.  Mine is different in that each item in the queue can be a different function.  I haven’t actually used it this way though, so it is possible that the extra flexibility is generally wasted.

Python’s lambda seem rather limited.  It is limited to a single expression.  I suppose that this is what Lisp and Scheme do as well, but their expressions offer things like progn.  My first idea is that the task to execute would be a function with no arguments.  I was picturing using a lambda to wrap up whatever I wanted to do.

Now, I still offer that via addTask and assume it internally, but I also offer addTaskArgs, and it takes a function reference, and either an argument list (as a list) or a named argument list (as a dict) and wraps it in a lambda to enqueue.

I now find that my knowledge about how to unit test threaded code is rather limited, and the included unit tests are extremely thin.

Seeking

I am now looking for a new job and am no longer with Sigma Electronics.

My first preference would be a position writing software for post production or visual effects at either a software company or a post production or visual effects company.

Other than that, I am also interested in positions or contract work developing embedded systems, graphics applications, or web applications.

I just thought I would throw this out in case anyone can point me towards any leads.

Thank you.