High Performance Multithreaded Code

Current CPUs have several cores per CPU. If a program wants to speed up with new hardware, the program has to exploit those extra cores. Using multiple threads is, therefore, becoming extremely popular.

Of course, people who talk a lot about multithreaded programming don't ever mention that most programs don't need to be any faster. While I feel obligated to point that out, this article is written for people who do want their applications to run faster.

In fact, I'm going to go even farther than that. This is for people who want to squeeze every last bit of performance out of their multithreaded code. This isn't for everyone.

Since I don't have a lot of experience with this, I'm going to talk about two books that I've read. They both talk about specific topics that are, I suspect, absolutely essential to some extremely high performance multithreaded code.

Interestingly, neither book talks about what I'm talking about directly. The books have absolutely no overlap, either. They both talk about different ends of the same problem without looking at the whole problem.

I enjoyed both of them.

The first, The Art of Multiprocessor Programming, was written by a couple of academics. It's a highly theoretical look at lock free and wait free data structures. It never talks about real hardware. It's also fascinating.

The second, Code Optimization: Effective Memory Usage, is an extremely practical guide to how modern hardware deals with a critical resource, memory. It talks in detail about what the hardware is doing. It doesn't touch algorithms that avoid the many problems that it talks about. It's a bit out of date as well, but it's still worth spending time with.

The Art of Multiprocessor Programming

You wouldn't be able to tell from the cover or the publisher's description of it, but this book is about lock free and wait free algorithms.

A component is lock free when many threads can access the routines and at least one thread will always make progress. If a thread holds a mutex, this is not possible. The thread with the mutex could page fault and be forced to wait. During that wait, no thread will make progress.

Wait free is an even stronger constraint. A routine is wait free if it will complete in a finite number of steps. That is, all threads will simultaneously make progress.

It's possible for a data structure to have some routines that are wait free and others that are merely lock free. The authors frequently try to make the most critical routines wait free and the less important ones lock free.

Lock free programming is a topic that's always fascinated me. It seems incredibly difficult. Researchers like the authors must agree, because there aren't that many lock free algorithms in the literature, yet. There are a few data structures out there, and a lot of work has been done on critical algorithms like heap management routines. There isn't much else, though.

The book, however, walks you through the techniques that are needed to build these algorithms. They describe and analyze the algorithms in ways that I don't normally bother with. Mathematical proofs appear to be critical to their process. Don't worry too much, though. None of the proofs outlined in the book were difficult to follow. Without the proofs, I would have had a difficult time understanding what they were doing, too.

Here's an example of an interesting theorem in the book. Modern processors have a variety of atomic instructions that are designed to help avoid locks. These instructions are critical to lock free programming. Examples include atomic increment and compare and swap.

Lock free algorithms replace locking a mutex with a number of these atomic instructions. Someone created a theorem that essentially states that most of these instructions are pathetic. (I'm only paraphrasing slightly.) Compare and swap is proven to be useful, however.

Lock free articles talk a lot about compare and swap. It's nice to understand why!

Incidentally, despite the title of my post, lock free algorithms are not necessarily faster than a conventional algorithm wrapped in a lock.

The Art of Multiprocessor Programming doesn't talk about it, but these atomic operations are expensive. They require a memory barrier. This requires communication with all of the other cores in the computer, and it's slow.

Arch, an Intel developer, puts it nicely here:

My opinion is that non-blocking algorithms are important in situations where lock preemption (arising from oversubscription) is an issue. But when oversubscription is not an issue, classic locked algorithms, combined with designing to avoid lock contention, will generally out perform non-blocking algorithms on current Intel hardware. I don't know about other hardware, but observe that:

1. Non-blocking algorithms generally use more atomic operations than it takes to acquire a lock.
2. Atomic operations in non-blocking algorithms generally need a memory fence.
3. Memory fences incur an inherent penalty on out-of-order processors or processors with caches.

Do keep that in mind when you read the book! If your algorithm uses too many of these atomic operations, there's no point in doing it. Locking a mutex doesn't require many of these operations.

The authors act like typical academics and ignore this problem completely. :)

Code Optimization: Effective Memory Usage

This book is dated 2003. It's several processor generations out of date. Don't panic, though. It turns out that a lot of what Kris Kaspersky says has been true for far longer than that.

There's a good chance that some of his discussion of ways to exploit specific CPU generations isn't useful anymore. However, interleaving memory bank access, N-way associative cache behavior, and many other interesting properties of memory are unlikely to change immediately.

You'd think that memory technology would change enough that the same quirky code optimizations wouldn't work for a whole decade. Apparently, you'd be wrong.

This is, as you might imagine, the exact opposite of the previous book. This is about how the memory systems in a (somewhat) modern PC work. This is about the details of machine architecture and how to use those details to speed up your code.

In fact, translating the information in this book to highly parallel computing will require some thought. It was written without much thought to the behavior of multicore processors.

That's not the point, though. Multithreaded programming is all about memory access. If you poke the memory in the wrong order, your program will slow way, way down. Compilers are not yet smart enough to do all the work for you.

It's worth talking a bit about how important memory access is. Here's a slide shamelessly stolen from Robert Harkness at the San Diego Supercomputer Center:



Performance in on a log scale. Memory bandwidth has a dramatically lower slope than CPU speed.

You could say that, eventually, performance will be entirely dominated by the usage of memory. However, we're almost there already. High performance data-parallel programming requires the knowledge in this book.

I do wish he'd write a second edition, though. Some of the chip-specific discussions are interesting, but they aren't necessarily relevant anymore.

Lower Performance Multithreaded Code

I should emphasize that most of the stuff in both of these books is useful for pushing performance a bit faster than you'd thought possible.

If you haven't already gotten to the point where you think your code can't be sped up, then you're likely to have more serious problems that will erase the improvements available from these books.

Actually, there's one significant exception to that. If you're using a low associativity cache poorly, then you could get almost no cache utilization. In some cases, you can make minor changes to your memory usage and go from no cache utilization to good cache utilization. That's probably a more important change than using a good algorithm.

Generally, however, these books are not what you need to make your web page load faster. None of the code that I've written in the last few years needs this. I'll keep looking for applications, though, because optimizing performance in exotic ways is a fun!

I enjoyed both books a lot even though they didn't seem directly applicable. I hope you will, too.

Futexes are Fun

Futexes are a synchronization primitive that is new to the 2.6 Linux kernel. If you're like me and had never heard of them before a few days ago, then I recommend reading Ulrich Drepper's article, Futexes are Tricky. To a Windows programmer like myself, futexes are a wonderful idea that would be lots of fun to play with. Essentially, they're the antithesis of Window's synchronization model.

Hmmm. I guess I'm showing how much I dislike Window's synchronization model...

Let's start there. In Windows, if you want to use a synchronization object, you go to the Micrsoft-approved zoo of Win32/.NET synchronization objects, and you find one that's close to what you need. You then modify your problem to fit this synchronization object.

Okay, the zoo of synchronization objects that Microsoft gives you isn't bad. There are some extremely useful ones in there. If you're using .NET, you even get to use a monitor, which was missing from Win32.

In fact, if you're doing relatively normal programming in Windows, you'll never even realize that you're missing futexes. However, if you're trying to build an application that has to have optimal performance, then you may want something unusual.

You may want to do a WaitForMultipleObjects on 65 mutexes. You may want to optimize a mutex implementation as much as possible, and you're willing to give up features like re-entrance. There are a lot of things you might need, and Microsoft deliberately doesn't give you all of them. Thomas Becker has tried to implement something that's not in Microsoft's zoo, and the difficulties that he ran into are instructive.

POSIX doesn't have a universal solution, either. However, it does have a monitor, and, assuming performance isn't an issue, you can solve any problem using this.

Futexes are all that and more. They let a programmer write their own synchronization object in user mode. They do this by avoiding doing anything that's unnecessary. A futex lets you have a thread join a wait list and sleep until it is woken. The user mode code decides when a thread will enter the wait list, and when threads in the wait list will get woken up. They're still a bit new, and they don't let you control which thread gets woken up with much precision. Even if it's missing some features, however, it's still an exciting idea. It allows user mode libraries almost complete control over the performance and features of a synchronization object.

That's pretty darn clever. My next goal is to find an application at PC-Doctor that needs a futex. It sounds like a lot of fun, but it won't work on Windows.

This originally appeared on PC-Doctor's blog.

Fairness in Win32 Lock Objects

Windows Vista has given up fairness in their synchronization objects. In fact, Windows XP isn't guaranteed to be fair, but Vista goes quite a bit further.

The issue and the solution is explained pretty well by Joe Duffy over here. At first glance, it looks as though this could cause some really bad thread starvation in some circumstances.

The change to unfair locks clearly has the risk of leading to starvation. But, statistically speaking, timing in concurrent systems tends to be so volatile that each thread will eventually get its turn to run, probabilistically speaking. Many more programs would suffer from the convoy problems resulting from fair locks than would notice starvation happening in production systems as a result of unfair locks.

The problem they're trying to solve and the problem that I'm worried about are pretty similar, so it's worth explaining it carefully. If you have a mutex that protects a small chunk of code, and you have a large number of threads trying to get that mutex, then you have the potential to have a lock convoy. You can get this easily if you wake up a large number of threads with the same priority and have them all immediately try to get another lock.

Here's what happens. A bunch of threads are waiting for a mutex. A thread releases the mutex. Under Windows XP, the next thread in line to get the mutex now owns the mutex and gets a temporary priority boost. Windows does a context switch to the new thread, and it performs a short operation and releases the mutex. (Note that this will also boost the priority of the next thread in line, but that thread will have the same priority, so no context switch is performed.)

These context switches are expensive. Joe Duffy claims that it's about 1000 cycles. Avoiding these switches would be a good thing, so Vista changes the way mutexes work. When a thread releases a mutex under Vista, the mutex does not become owned by the next thread in the queue. Instead, it becomes unowned. This allows a third thread that's already in the running state to grab the mutex and keep going without any context switches at all. That's much cheaper, much less fair, and has the potential to starve the waiting threads.

One problem with this is that you're giving priority to running threads over waiting threads. As the number of cores in your CPU goes up, then the number of running threads gets higher. Eventually, isn't there going to be some starvation of the waiting threads?

I tried for a while to construct an artificial scenario where a thread could be starved for a long period of time. I've got to admit that I couldn't do it. The reason is that there is always some randomness in the scheduling. In order to make it so that there is a problem, I had to increase the fraction of time that a thread holds the synchronization object. Once you do that, you're going to limit the number of threads that can run without having to run into problems with a lack of fairness. It feels as though that might be true of all problems where this change becomes bad, but I couldn't prove it.

In short, Vista gives up the pretense of fairness in synchronization objects, and it does so without guaranteeing that it doesn't starve a thread. However, it looks to me as though thread starvation will never be a huge issue.

This originally appeared on PC-Doctor's blog.

Multithreaded Programming for the Masses

Writing software on multicore CPUs is a hard problem. The chip designers have told us that they're not going to do all the work for us programmers anymore. Now we have to do something. (Here's a good description of the problem from Herb Sutter.) Writing multithreaded apps is not easy. I've done a lot of it in C++, and the tools, the libraries, and the design patterns just don't make it trivial. I don't mean to say that it's impossible, however. It's certainly possible if you're careful, you plan for it from the beginning, and you know what you're doing. The real problem is that 99% of programmers aren't all that good. A defect in multithreaded code can be really hard to track down, so it's expensive if you get it wrong. A lot of companies and research groups have been spending a lot of time trying to figure out how to make it easier. I haven't been doing any research on the topic, but, like a good blogger, I'm going to comment on it anyway.

First of all, do we have to speed up all applications by the number of cores in your CPU? Your typical Visual Basic programmer isn't any good at threading, but do they have to be? They can create dialog boxes and display data and let you edit that data. Do they have to know anything about threads for this?

Probably not.

It's still possible to speed up that dialog box, too. If there's some text entered by the user, the grammar/spelling checker might be running on a different core from the UI widget. This wasn't done by the Visual Basic programmer. The dialog might have been drawn using a graphics engine that used threads or even offloaded some computations to the video card. Again, this wasn't done by the programmer who's never worried about threads.

So, we don't always have to know about threads. Some substantial fraction of the programmers in the world don't have to speed up their code using multiple cores. That's good news. We really need to admit that not all programmers need to make their programs faster. The libraries they use can be made faster without compromising the reliability of the program itself.

That's not the whole story, though. Let's look at the other end of the spectrum. How about a video game?

Graphical processing is astonishingly easy to parallelize. GPUs will continue to get faster over time because of this. A lot of calculations can be done on individual pixels. It's relatively rare that two pixels that are far apart will affect each other substantially. (There are some techniques that defy this statement, but a lot of them rely heavily on expensive matrix calculations which may be parallelizable. I know nothing about these techniques, but I'm going to guess that they're easy to parallelize, too.)

If video cards are going to continue to get faster, then the CPU had better keep up. The CPU is going to have to generate enough data to avoid starving the GPU. As the GPU gets infinitely fast compared to a single core of the CPU, this will require multiple cores.

Uh, oh. Does this mean that all game designers will need to use multiple threads?

I'm sure that it doesn't. Couldn't the game engine programmers do all of the hard work and let the average game programmer use a safe API that avoids threads? Certainly a level designer who's scripting an in-game event in Lua would not be forced to worry about threads!

What about an AI programmer? I don't know enough about game engine design to say for sure, but I'd be willing to bet that a cleverly designed game engine could avoid exposing a lot of the multithreaded mess to many programmers, but at some point AI programmers will have to do things on multiple cores at the same time.

While the AI programmer might be fairly smart, and they might be trained in multithreaded programming techniques, that does not mean that it's a good idea to subject him or her to mutexes, condition variables, thread creation, deadlock avoidance, etc. That's not a good use of a programmer's time.

What can be done to help a programmer who really does have to run code on multiple cores?

Functional programming languages are a potential solution. The creators of languages like ML, Haskell, and Erlang realized that your compiler can do a lot of fancy things if the programmer isn't ever allowed to modify a value. If things can't be modified, then they can be easily parallelized. Once you create an object, as many cores as you want can read it without even bothering to lock it. Of course, this will frustrate a Visual Basic programmer who is used to changing a variable as the object that the variable represents changes. It requires some significantly different programming techniques.

Once again, this is not for everyone.

Futures are a pretty slick way to abstract away threads and some locks. It doesn't eliminate the headaches of multithreaded programming, but it has the potential to make things simpler.

A future is a chunk of code that a programmer wants to execute. Instead of calling the function that contains the code and waiting for the return value immediately afterwards, the programmer separates the calling and the waiting. First you tell your library that you want your future to run. The library can do whatever it wants at this point. It could execute it immediately. It could put it in a queue to be run by a thread pool. It could ignore it completely. The program can then do whatever it wants. At some point, it may want the result of the future. Then the program will ask the library for the result of the future. The library may have to wait for the result to be ready, but eventually the result will be returned.

The great part about futures is that threads don't have to be created. If you can divide your program's logic into N bits, you can let your library and compiler figure out how to use that to speed up the program using multiple cores.

Unfortunately, futures don't eliminate the need to worry about locks. Since that's probably a more difficult problem than thread management, futures are not a panacea.

There are some other ways to easily parallelize your code. SQL statements are a great example. Databases are really good at optimizing SQL for this sort of thing.

Intel has a strong interest in making it easier for programmers to use their new chips. Their Thread Building Blocks library uses STL-style algorithms and protected iterator ranges to express parallelism. It also has a "task scheduler" that behaves at least a bit more like a futures library. This seems like a really great idea. An STL-style algorithm that describes the parallelism to the library is not always sufficiently flexible to describe a problem. However, if it is sufficient, it's extremely easy to use. The task scheduler is more conventional and would probably be much nicer with a good lambda library.

OpenMP is another library designed to abstract away many of the details of parallizing code. It's not strictly a library, however. It requires some compiler support as well. The programmer uses a function that behaves much like a Unix fork() command. OpenMP then manages several threads to handle the different branches of the fork. While I'm certainly not an expert, this doesn't seem like either a clean solution or a sufficiently flexible solution.

I'm sure there are other research projects out there. If you know of any interesting ones, please post a comment about it below.

This originally appeared on PC-Doctor's blog.