Python multiprocessing: I did it my way

Python has a wonderful multiprocessing module for parallel execution. It's well known that Python's threading module does not do real multithreading due to the Global Interpreter Lock (GIL). Hence multiprocessing, which forks a pool of workers so you can efficiently run tasks in parallel.

In principle:

    p = multiprocessing.Process(target=func)
    p.start()
    p.join()

In practice, I have had weird issues with multiprocessing. Two notable issues:

• program does not start any processes at all, and just exits
• program raises an exception in QueueFeederThread at exit

Apparently the multiprocessing module has its problems, and although there are fixes in the most recent versions, I can't rely on that when the users of my program are running on operating systems that don't always include the latest greatest Python.

So, a decision had to be made. I ditched the multiprocessing module and replaced it with my own, that calls os.fork(). The resulting code is much easier to handle than with  multiprocessing, too.

Note that os.fork() does not port to Microsoft Windows. My target platform is UNIX anyway.

Pseudo-code:

    parallel(func, work_array):
        for i < numproc:
            fork()
            if child:
                work_items = part_of(work_array)
                for item in work_items:
                    func(item)

                # child exits
                exit(0)

        wait_for_child_procs()

So, a pool of numproc workers is spawned. Each of the child processes do their part of the work given in work_array. No communication is needed here because fork() causes the child to be a copy of the parent process, and thus getting a copy of work_array.

This is the simplest kind of parallel programming in UNIX. Surprisingly, this bit of code works better for me than the multiprocessing module — which supposedly does the same thing, under the hood.

Having decent language support for parallel programming is of utmost importance in today's world, where having a quadcore CPU is no exception; practically all modern computers are multi-core machines. A modern programming language should offer some easy mechanisms to empower the programmer, enabling you to take advantage of the hardware at hand.

Proper multithreading is exceptionally hard (if not impossible) to do for interpreted languages. This is a fact of life. Using a forking model, you can still get good parallellism.

MD5 and libs and licenses

I keep running into code that looks like this:

#define S21 5
#define S22 9
#define S23 14
#define S24 20
    GG ( a, b, c, d, in[ 1], S21, UL(4129170786)); /* 17 */
    GG ( d, a, b, c, in[ 6], S22, UL(3225465664)); /* 18 */
    GG ( c, d, a, b, in[11], S23, UL( 643717713)); /* 19 */
    GG ( b, c, d, a, in[ 0], S24, UL(3921069994)); /* 20 */
    GG ( a, b, c, d, in[ 5], S21, UL(3593408605)); /* 21 */
    GG ( d, a, b, c, in[10], S22, UL(  38016083)); /* 22 */
    GG ( c, d, a, b, in[15], S23, UL(3634488961)); /* 23 */
    /* ... etcetera ... */
    HH ( ... )
    II ( ... )

This is an excerpt of C code for the MD5 algorithm as implemented by Ron Rivest, published in RFC-1321 in 1992. What's wrong with this picture? Well, not so much, except that there is this nice OpenSSL library that is present practically everywhere. The OpenSSL library provides this functionality and the code has been reviewed by dozens of people and is being used by millions.

Using libssl for MD5 digests is easy:

#include <openssl/md5.h>

    unsigned char digest[16];
    MD5_CTX ctx;

    MD5_Init(&ctx);
    MD5_Update(&ctx, buf, buf_len);
/* multiple calls to MD5_Update() may be made */
    MD5_Final(digest, &ctx);

Link with -lssl and you're done.

On OSX, something is up. OSX no longer ships OpenSSL. Instead, Apple now provides their “CommonCrypto API”, which is, ironically, not so common. An ugly trick to get OpenSSL MD5 code to work with CommonCrypto:

#include <CommonCrypto/CommonDigest.h>

#define MD5_CTX      CC_MD5_CTX
#define MD5_Init     CC_MD5_Init
#define MD5_Update   CC_MD5_Update
#define MD5_Final    CC_MD5_Final

#ifdef MD5_DIGEST_LENGTH
#undef MD5_DIGEST_LENGTH
#define MD5_DIGEST_LENGTH    CC_MD5_DIGEST_LENGTH
#endif

Why did Apple do this, you may ask. The reason is probably software licensing; OpenSSL's dualistic license is problematic in particular for apps on iOS devices. Apple could probably have kept OpenSSL on the Mac, but they didn't.

(* It's either this or the NSA forced them into putting some weakened PRNGs into CommonCrypto).

Coming full circle, you would be justified not to use a common library in cases where you run into  issues with the software license. There are many free and open software licenses, and many of them have quirks. This is a major annoyance in software development, and something to consider when using libraries.

One and one are eleven

Oh C++, why art thou so hard? Thou giveth us nought but grievance and pain. Often I've cried out because C++ just wouldn't play nice. The language is too hard to learn, and it couldn't do anything you could do in plain C. But I've actually started to like C++. I have come to appreciate it a lot. I suppose it ages like fine wine. C++11 brings a lot of good to the table, well, as long as your compiler is up to par.

Rather than go over all the features of C++11 (there's enough of that on the web to go 'round), I want to show you a neat trick. Lo and behold.

template <typename... Tpack>
void go(Tpack&&... args) {
    std::function<void()> func = std::bind(std::forward<Tpack>(args)...);
    std::thread(trampoline, func);
}

This defines a go() function that allows you to fire up any function (with arguments!) as a thread. The thing with Tpack is a variadic template, which is a type-safe kind of varargs. The call to std::bind turns it into a std::function object, which is a kind of functor. std::thread creates a new thread and launches a trampoline function that will invoke the function functor for us. Okay, the actual implementation is a little different, I have simplified it here for the sake of example. For one thing, you should catch the std::system_error exception that is thrown in case the operating system fails to launch the thread.

So now we can easily run any function as a thread. Next, I wanted go() to accept my custom Functor class as well. Normally you would go about that doing that like so:

void go(const Functor&);
void go(Functor&);

Guess what, it didn't work! The result was a (not so) glorious Segmentation fault. Tracing it revealed that the compiler was favoring the go(Tpack&&...) variant over the specific Functor functions. But no worries, template specialization to the rescue:

// specialized templates for passing in a Functor
// const Functor& is only used for const functions or
// explicitly const Functors
// in most cases go(Functor&) is used
template <>
inline void go<const Functor&>(const Functor& f) {
    do_something_with(f);
}

template <>
inline void go<Functor&>(Functor& f) {
    do_something_with(f);
}

This weird looking stuff is C++ dark magick, written in the black of night by the light of a candle. If you look past all the confusing glyphs, it's simply telling the compiler to call the right function for what kind of argument we have.

All of this wasn't quite possible to this extent before C++11. Other than impressing your girlfriend with this trickery (not!), C++11 comes with a most important change: the move constructor. This is something you MUST learn. It's hard to believe, but before eleven it was not possible to simply return instances from a function, because the destructor would kick in — you would return a copy and the original object would be destroyed. C++11 fixes this long standing problem by handing you the opportunity to move the content of the original to the copy, allowing you to return objects, like in any sane programming language. Actually, the move constructor is much more important than showing off template and thread trickery, but Brian and me really wanted to bring you the go() function this time.

The Yearly Countdown

End of year, December 31st. Every year millions of families world-wide gather round the tv-set just before midnight to watch the clock tick tick tick away the final seconds of the year. The clock strikes twelve and we yell “Happy New Year!” while outside fireworks burst, lighting up the sky.

It's about time

For some years already I run a desktop widget that counts down the year. I made it with Dashcode when I was just messing around on a boring January day. After nearly a year, I found an interesting bug: it started counting up in the next year..! Just like a regular clock does.

Anyway, it's fun saying things like “99 days left!” out of the blue and see people reacting “what was that all about?”.

The year 2012 had a leap second so there was another bug: it was off by a second. This was totally unnecessary had I implemented it properly ... Just saying that dealing with time can be tricky.

Two minutes to midnight

Counting down the days until year+1 Jan 1 00:00:00 is fun and not hard to do. Be mindful though that the naive implementation of doing sleep(1) in a loop is plain wrong. You will find your family and friends yelling out Happy New Year a split second before the counter reaches zero. Why is that? The thing is, you forgot about milliseconds, microseconds, and nanoseconds. This is illustrated by the following timeline:

23:59:56.852 countdown program start
             sleep 1
23:59:57.852 sleep 1
23:59:58.852 sleep 1
23:59:59.852 sleep 1
00:00:00.000 Happy New Year! on tv
00:00:00.852 countdown program reacts too late

Here, the program starts at an offset of 852 milliseconds causing it to react too late; it practically misses the strike of midnight. 852 milliseconds feels like almost a full second, so the countdown program just isn't good enough.

A better way to do it is to use either usleep() or nanosleep() to sleep fractions of a second and round it off to an (near) exact tick of a second.

Sleep with one eye open

Although you can do nanosecond sleeps, the practical accuracy of your software clock is about 15 milliseconds. This is because of timeslicing in multitasking operating systems. Really? Well, yes and no. Modern computers have a High Precision Event Timer (HPET) that can be used to do more accurate timing of events. This is entirely meant for doing things like performance measurements and not so much for wallclock time keeping.

No time to waste

A countdown timer is pretty neat and not so hard to write. It gets more fun when you add a big LED display in OpenGL graphics. I suppose it's too late now to get it approved in the App store and get rich before 2014 starts, but we can always try again next year.

Best wishes! and if you want to read more about high precision timing, see this excellent blog post by another code monkey:

http://tdistler.com/2010/06/27/high-performance-timing-on-linux-windows