Tuesday, October 21, 2008

Parallel programming with pthreads

Today, we had a little conversation about pthreads programming in the office. Every now and then the topic of pthreads seems to come up. Surprisingly, I'm one of very few who actually has had some hands-on experience with it. I remember that learning pthreads was difficult because there were no easy tutorials around, and I didn't really know where to start. There is a certain learning curve to it, especially when you don't really know what your doing or what it is you'd want to be doing with this pthread library.

A thread is a "light-weight process", and that doesn't really explain what it is, especially when they say that the Linux kernel's threads are just as "fat" as the processes are.
You should consider a thread a single (serialized) flow of instructions that is executed by the CPU. A process is a logical context in the operating system that says what memory is allocated for a running program, what files are open, and what threads are running on behalf of this process. Now, not only can the operating system run multiple processes simultaneously (1), a single process can also be multi-threaded.

The cool thing about this multi-threadedness is that the threads within a process share the same memory, as the memory is allocated to the process that the threads belong to. Having shared memory between threads means that you can have a global variable and access and manipulate that variable from multiple threads simultaneously. Or, for example, you can allocate an array and have multiple threads operate on segments of the array.

Programming with pthreads can be hard. The pthread library is a fairly low-level library, and it usually requires some technical insight to be able to use it effectively. After having used pthreads for a while, you are likely to sense an urge to write wrapper-functions to make the API somewhat more high-level.
While there are some synchronization primitives like mutexes and condition variables available in the library, it is really up to the programmer to take proper advantage of these — as is often the case with powerful low-level APIs, the API itself doesn't do anything for you; it is you who has to make it all work.

Programming pthreads is often also hard for another reason; the library enables you to write programs that preempt themselves all the time, drawing you into a trap of writing operating system-like code. This kind of parallelism in code is incredibly hard to follow, and therefore also incredibly hard to debug and develop. The programmer, or developer, if you will, should definitely put some effort into making a decent design beforehand, preferably including a schematic of the communication flow that should occur between the threads. The easiest parallel programs do not communicate at all; they simply divide the data to be processed among the threads, and take off.
It should be clear that the pthread library is powerful, and that the code's complexity is really all the programmer's fault.

While the shared memory ability of pthreads is powerful, it does have the drawback that when the programmer cocks up and a single thread generates a dreadful SIGSEGV, the whole process bombs (2).
Also, as already described above, pthreads has the tendency of luring you into a trap of creating parallelism that is not based on communication, creating overly complex code flows.
The automatic shared memory has the drawback that you may not always want to share data among all threads, and that the code is not thread-safe unless you put mutex locks in crucial spots. It is entirely up to the programmer to correctly identify these spots and make sure that the routines are fully thread-safe.
It is for these reasons that communication libraries like MPI, PVM, and even fork()+socket based code are still immensely popular. The latest well-known example of a forking multi-threaded application is the Google Chrome browser, in which a forked-off "thread" may crash, but will not take the entire application down.

This blog entry has gotten too long to include some useful code examples. Therefore I will provide you with a useful link:

Skip right to the examples, unless of course you wish to learn some more on the theory of threads...  Note how this tutorial covers all you need to know, and cleverly stays away from the more advanced features of the pthread library, that you are not likely to need to know anyway.

If the C programming language is not your thing, try using the Python threading module. Although not truly concurrent threads, Python's threading threads appear very similar in use and behavior to pthreads.

Another interesting topic related to parallel programming is that of deadlock and starvation, and the "dining philosophers" problem. See this online computer science class material for more.

  1. Multiple processes or threads of execution can run concurrently on multi-processor or multi-core machines. On uniprocessor machines, they are scheduled one after another in a time-shared fashion.
  2. There are (or have been, in the past?) implementations of UNIX in which it's unclear what thread receives the UNIX signal. I believe Linux sends it to the main thread, ie. the first thread that was started when the process was created. For this reason, it's wise to keep the main thread around during the lifetime of the process.

Monday, October 13, 2008

Why C++ is not my favorite programming language

Eric S. Raymond, famous figure in the open source movement (1), wrote on his blog he was working on a paper with the colorful title "Why C++ Is Not Our Favorite Programming Language". The title alone struck a chord in me, having a general aversion of C++ for a long time now.

C++ is the object-oriented dialect of the C programming language, and was originally meant to be a "better C". C++ offers full "object-orientation", as it boasts classes, inheritance, templates, exceptions, operator overloading, references, constructors, destructors, accessors, virtual member functions, templates, and more. All of this is then mangled by the compiler and eventually a binary comes out, just like you would compile and link regular C codes.

I have personally written quite a lot of C++ code, but my latest C++ code dates back to the late 1990s. The reason: I was completely fed up with programming in C++ (and Java, that other object-oriented language), and switched back to plain C.

The C programming language is simple, and therefore very straightforward. C translates back to assembly language and machine code relatively easily, and because of this, if you know how a computer works, you will know how to write in C.
This is entirely not the case with object-oriented languages — object-oriented languages are on a higher level of abstraction and take the low-levelness away from the programmer. While this seems nice when you are working on a high level of abstraction, it makes things annoyingly difficult for the programmer who likes/wants/needs to understand what is really going on at a lower level.
Technically, this is a non-issue because in C++ the developer decides what objects look like, and when there is a need to do so, you can take a debugger and trace into those classes to see what is going on. In reality, C++ is making things harder rather than simplifying them.

Back in the day, C++ code always produced a binary that performed less well than a compiled and linked plain C code. The reason? The C++ program is calling constructor and destructor functions all the time, often consuming cpu for no real reason. Moreover, C++ has runtime type-checking that costs performance.
After more than a decade, compilers have advanced, and there are always codes for which the degraded performance is not important. Being also an assembly programmer (speed freak!), it annoyed the hell out of me to actually feel the C++ apps being sluggish on my old 80486 cpu.

For certain codes, like games, graphical user interfaces, or 3D modelers, it appears to be a good idea to use an object-oriented language, because you are already thinking in objects. Now replace that last word "objects" with "structures", and you've already taken the first step to implementing the same thing in plain, good old C.
While classes appear as useful "structures-on-steriods" (ie. regular C structs with member functions), their C counterparts (ie. structs with functions that operate on the structs) are easier to comprehend only because of the use of pointers. While pointers are usually hard to comprehend by a novice, they are a must-have for the experienced programmer.
While C++ does not hide pointers, the preferred way handling objects is by reference. A reference is like a hidden pointer that only confuses the journeyman programmer. In machine language, there is no such thing as a reference, there are only pointers.
I can already hear the crowd say the old saying "pointers are the root of all evil", but in reality, "bugs are the root of all evil". The pointer is a very powerful asset than can prevent unnecessary copying of data.

As a master in C, I've actually managed to write object-oriented-like codes in plain C. This is not surprising, because C allows you to create anything you like, even weird programs like compilers and operating system kernels. In fact, the first C++ compilers spit out mangled C code rather than object code.

They say C++ is good for teaching object-oriented programming. This was only true until Java arrived. I have experience with Java, and it's awful, but I guess it can be used to teach object-oriented programming.
What strikes me as odd, is that C++ was not ready at the time when I learned it. I actually have C++ code that does not compile today without making some necessary changes, while it was all correct when I wrote it. This actually also holds true for very old C codes (2), but I've never encountered this kind of issue for my own C codes. (Anyway, C does evolve because there is also C99 and the like. However, C99 is fully backwards compatible with older Cs).
Later, templates were added and while this black magic was presented as the Next Big Thing, it never did anything useful for me. Templates are best used for implementing lists and stacks into classes, although it appears better to me to have a list of structs with pointers point to the object data (3).

Implementing good C++ classes is hard because they are supposed to be generic, abstract implementations. Often, there comes a time when the class will turn against you and needs redesigning — leading to a major overhaul of the complete code. Proper design should prevent this, but in practice, implementating code is different from designing code and there will be frequent times when you curse at C++ for putting this on your head.

Even if a clever C++ supporter manages to undermine every statement I have made against C++ in this blog entry, I will still have the final word: I just don't like the C++ syntax.
Honestly, tell me which code fragment looks nicer:
std::cout << "Hello, world!\n"; // in C++
printf("Hello, world!\n"); /* in C */
In the C++ code fragment above, intuition would tell you that the direction brackets point in the wrong direction (!) Also, no one seems to know how to pronounce "cout" (4).
The "cout" function is actually being called without having instantiated an object of the "std" class, making this a very questionable example of "object-oriented" programming.
In fact, "cout" is not a function; it is more like the "stdout" global variable in standard C. The output is being produced via an overloaded operator function, for the shift-left operator. Funky? Yes. Fancy? Yes. But as to why a shift-left operator would have to print text, totally eludes me. The fact that printf() is a library function that, in the end, enters the write() system call, that I can understand.

My favorite object-oriented language is Python. But then again, I don't use its object-oriented capabilities much. The best things about python are its comprehensive syntax, and its brilliant memory management (to the developer, there appears to be none because all objects are reference counted and garbage collected). This costs performance, so for the more cpu-intensive stuff, I use C.
Either way, I prefer a procedural language over a weird, code obfuscating, mind bending object-bloated language that attempts to mask the natural program flow, any time.

  1. Eric S. Raymond is the author of various well-known open source programs, and he is the author of the essay The Cathedral and the Bazaar.
  2. The Lion's Book lists an ancient UNIX kernel source code that contains old C statements that are no longer valid today.
  3. Actually, my old, now famous, bbs100 code uses a dirty (but clever and efficient) typecast trick to turn structs into linkable or stackable items.
  4. No one seems to know how to pronounce "Stroustrup", either.