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:

ptheads programming tutorial

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.
   

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++

or

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.
   

Fullscreen GL ...

Programming games is fun. Games typically run in fullscreen mode, so in today's world, it's important to have a portable way of setting a full screen mode. It looks like this is more of a hassle than you'd think it is.

I'm fond of SDL because it's quite a powerful library. There is a SDL_WM_ToggleFullScreen function that lets you switch between full screen and windowed mode. I noticed however, that on the Mac, the full screen mode of SDL would actually resize the application window to maximum size rather than take up the whole screen. The problem is that the Apple menu bar remains visible on the top of the screen, and also the dock would still pop up when you move the mouse to the bottom of the screen.
In Windows, I found that it helps to resize the window to the maximum resolution before trying to toggle to full screen.
The man page of SDL_WM_ToggleFullscreen does say that toggling to full screen is not supported on all platforms.
To my astonishment, there is a rather simple fix for this, but first I'd like to tell you about the little adventure I had with GLUT.

Because of the full screen problem I had with SDL, I decided to switch to GLUT and try that out. GLUT is real easy to use, because it feels much more high-level than SDL and you quickly get results with little effort. GLUT features a so called 'GameMode' in which it switches to a full screen mode. While this seems to work across platforms, I'm having an incredibly pesky issue in that the screen is no longer being updated — all animations and movement appear frozen although the display function is being called. It's like glutSwapBuffers is not swapping buffers anymore or so?
Switch back to windowed mode, and everything works perfectly again. It's not the obvious beginners mistake of not re-initializing GL ... I don't know what it is, and I spent way too much time on trying to get this to work. Searching the web also doesn't turn up much information, other than people saying that GLUT is bugged and you should use SDL.
What's also really odd, is that GLUT allowed me to set a 10000x3000 video mode on my 1440x900 monitor. SDL doesn't let you do weird things like that.

Exit GLUT, it's nice for trying out a quick scene, but for anything larger, I'm through with it.
Getting back to SDL, it turns out to be amazingly simple to enter full screen mode. Forget about SDL_WM_ToggleFullScreen, as it's useless. Use SetVideoMode instead:

SetVideoMode(max_xres, max_yres, bpp, SDL_OPENGL | SDL_FULLSCREEN);

The maximum resolution can be obtained by using SDL_ListModes. You should always use this, as a good program knows what video modes are supported and what modes are not.
You can switch back to windowed mode by omitting the SDL_FULLSCREEN flag, and mind to set the window size back to it's original size.
The beauty of all of this is that it appears to be portable, too. As to why anyone ever thought up a broken SDL_WM_ToggleFullScreen function, we'll probably never know.

Doomed to code

I read an interesting interview with John Carmack, lead programmer at id Software, famous (1) for creating the game DOOM. In the interview, he talked a little about his game engines with the cool sounding code names "Tech 4", "Tech 5", "Tech 6", etc. To my surprise, there were some very negative comments to this article, people complaining that Carmack is not doing anything innovative at all, as he is recreating the same old game over and again. He is obsessed with his engine and not creating fun games any more.

This made me realize that Carmack is, above all, a programmer, and he is making his code evolve. This is what technical programmers do and what they live for.
In the early 1990s he had a lot of success with his DOOM project, and all he wants is to impress people with a better, faster, cleaner, leaner, more technologically advanced version. Likewise, in the early 1990s, I had a lot of success (although never as much :-) by doing a lot of programming on a BBS (2) and I developed several iterations of this BBS. You wouldn't believe the amount of time spent thinking up new ways of doing the internals and tinkering with the code.
Not only is programming addictive, so is having success. Trying to recreate that past success can be a great driving force. Deep inside of me there may always be the wish to create a new implementation of the BBS. John Carmack has this dream too, and he's earning a living with it.

To my surprise, Carmack is not merely striving for visual perfection. He has recognized that today's popular gaming console (read: the XBox 360) contains 2 year old hardware and therefore needs simpler graphics (like, for instance, tricked shadows rather than compute intensive real shadowing effects) to get more performance.
Kiddies that are complaining that Carmack is only talking about performance, simply don't get it. The performance of the rendering engine is a very important aspect of a game.
The "60 Hz versus 30 Hz" debate is hyped, but not entirely unimportant; having a 60 Hz engine sounds more technologically advanced, however, it sounds to me that a 30 Hz engine would have tons more time per cycle left for doing other things, like AI. Good AI is what makes games fun to play.

One last thing he mentioned that raised my interest was what Carmack said about mega-textures, a technique developed by him that makes it possible to define the world in one giant unique texture, rather than to build the world from repeating textures.
The interesting thing is that he said "it is only two pages of code"; he is now talking casually about what was presented a year ago as his big new thing. Now that he's been working with it for many months, it's not that special to him any more. This behavior is typical for programmers (I do it all the time).
Funnily enough, a lot of cool code snippets are only one or two pages.
It is also a jab at other game developers; the mega-texture technique is apparently not that hard to implement and other knuckleheads should have been able to find out how by now, too.

John Carmack is still a hero in my book, even if id Software's games are not as shockingly groundbreaking as the original DOOM. It's not like the guy gathered fame for no reason at all, (Paris Hilton comes to mind ...) and as long as he keeps revealing technical details about the inner workings of his engines, he's got my attention.

As for the complaining kids out there ... it's just like what I always told the users of the BBS: anyone who dares complain should go and write their own. And one day, I even followed my own advice.

---

1. Carmack is like a celebrity, lately doing more interviews than a movie star, and spending more time writing keynote presentations than writing code.
2. BBS: Some kind of (now ancient) online service featuring a message board with forums, and interactive chat.