GSoC Threads: Chandon's Results

The pencil's down date for the 2010 GSoC program has come and gone, and now we're starting the process of sorting through the rubble and seeing what all got accomplished this summer. I have been purposefully trying not to provide too many of my own status updates for Chandon's project this summer, instead wanting him to post his own updates as he went without me getting in the way. It's his project after all, and I wanted him to get all the credit for all the good work he was doing.

The project is now over, and he's posted a nice final review of what he managed to accomplish this summer. While it isn't everything that he mentioned in his proposal, it still is quite a nice step in the right direction and a lot of the necessary framework is now available to bring threading to Parrot in a real and usable way.

So what did he manage to do? In his branch there is now a more-or-less working implementation of green threads, which means Parrot is getting onto the same level of capability as modern Python or Ruby implementations. You can schedule multiple independent tasks to run and, while they cannot run truly in parallel on separate OS threads or even on multiple processor cores, you can get the illusion of concurrency. It also gives you the ability to run multiple tasks together without having to explicitly schedule them one after the other, or having to manually switch back and forth between them. In a later post I may go into some detail about how this all works, and how it can be used by programs.

This is a pretty significant step forward, and once a few of the final nits get worked out I think we will be able to merge this into Parrot trunk and start making use of the new functionality immediately. However, green threads is only one half of the promised "hybrid threads" that Chandon's proposal hoped to achieve. The other half is the ability to run Parrot code in true parallel on separate OS threads. This was the larger part of the project and definitely the more difficult piece. Today I would like to talk a little bit about why it didn't get done, and maybe motivate some people to look into help completing the work as we move forward.


Let's take a look at a small snippet of normal object-oriented code:

foo.bar();
foo.bar();

Extremely simple, we have an object "foo" and we are calling the "bar" method on it. In a very naive staticly-typed language this would be a simple operation. The compiler would determine the type of foo, calculate the location of the bar routine in memory and would simply call that address twice. This would be extremely fast to execute too, which everybody likes. This would basically be converted to this low-level pseudo-code:

call bar(foo)
call bar(foo)

Now let's move up to a slightly more complicated example: a statically-typed language which allows subclassing and method overriding. Now, the compiler doesn't necessarily know which function in memory corresponds to "foo.bar()", since foo could be of type Foo, or of type FooSubclass, or even FooSubSubclass, and the location of the appropriate bar function would change with each different type. However, for each type, the value of bar does not change. It can be overridden by subclasses, but it cannot be changed for the class itself. Now, the compiler needs to ask foo to get the appropriate method first:

method _bar = get_method(typeof(foo), "bar")
call _bar(foo)
call _bar(foo)

Assuming foo does not change type inside the call to _bar, this code works just fine. Next let's look at a more complicated example still, the case of a dynamic language like Perl or Python. In these languages the class MyFooClass is an object of type Class, and foo is an object of type MyFooClass. Also bar is not a compiled-in constant property of the Class, but is instead a mutable property of it. Inside the call to bar, maybe we change the definition of bar itself inside the class object. Likewise, the definition of routines like "find_method" inside Class can change. Accounting for all this dynamicism,  our code changes to look like this:

class fooclass = find_class(foo)
method _get_method = find_method(fooclass, "bar")
call _bar(foo)
class fooclass = find_class(foo)
method _get_method = find_method(fooclass, "bar")


call _bar(foo)

Keep in mind that everything can change inside each call to bar. We can:

• Modify the inheritance hierachy of MyFooClass to add or remove parent classes
• Add or remove methods in MyFooClass, and any item in it's inheritance hierarchy
• Add or remove methods on the object foo itself (like in javascript where foo.bar = function() {...})
• Change the class of foo

Let's bring this back to the idea of threading before I go too far off topic. Every time we call a method, or attempt to access a field on an object, we need to look those up in the associated Class object first. Those Class objects need to be global, because all code on all threads need to be able to lookup methods on any object, because we can pass objects between threads and we need to be able to work with them.

If classes are global, and need to be accessible from multiple threads, we inevitably run into the idea of contention: If one thread is changing the definition of foo.bar() at the same time that another thread is attempting to look it up, the thread doing the reading may end up with incomplete, corrupted, or incorrect information.

Global data is the enemy of good multithreading. Global data is a necessity for highly dynamic object systems like those supported by Parrot. Ergo, multithreading on Parrot is hard.


Look at all the global data in Parrot: there's the interpreter object itself, the packfiles, the list of Classes (and the methods/properties that they contain), the list of Namespaces (and the global values they contain), the context graph (and the contents of all registers in those contexts), the opcode table and the MMD signature cache. This is a hell of a lot of globally-available data, and we're going to need to find a sane way to limit corruptive concurrent access to these things. Not only that, but if we have to lock every single access to a global value, which means we need to obtain a lock every time we want to do a method call, our performance is going to be terrible.

By convention I think we can all agree that things like the opcode table should really not be modified when we have multiple threads running. But it's harder to make such a convention that class/method definitions should be treated as constant when multiple threads are running.

What we can do to alleviate some of the performance problems is to create short-term caches for things like Classes and Methods in local threads, with the understanding that without explicit synchronization, the exact ordering of read/write operations between threads cannot be guaranteed and can be scheduled for maximum benefit. If the relative execution times of two operations on separate threads cannot be guaranteed, then it makes no difference to functionality for the user whether those operations happen at random times with respect to each other and whether Parrot manually orders them to improve caching.

Think about it this way: We have two threads, one is writing a global value and one is reading it. These threads are operating in true parallel on two separate processor cores. If we run this program a million times, sometimes the read will randomly occur before the write, sometimes the write will occur before the read, and sometimes they will happen at the exact same moment and cause corruption. Depending on a simple matter of random timing, we could get three very different results from our program. Now, if Parrot implements a heuristic that if a write and a read happen within a very short period of time, Parrot will manually order them so that the read occurs before the write. And, if the read always happens before the write, maybe we don't read at all, but instead use a cached version. Then, only when the write has complete, we update the cache.

Another thing to think about is that we could disallow direct lookups of data in global variables, and give each thread a local copy of global values. Considering the principal I mentioned above, we can be a little bit liberal with the way we handle writes and reads. If a thread modifies its copy of a Class, those changes could be propagated to a global reference copy at a convenient time, and then propagated down to the local copies later, only when it's convenient to do so. Remember, if things are happening at random times compared to each other, it makes no substantive difference to the thread whether it's copy of a global variable is exactly up-to-date or whether it's a little bit lagged behind. That is, the reading thread doesn't know whether the writing thread had a legitimate delay before writing, or whether Parrot manually scheduled the write at a different time.

To get a complete Hybrid Threads implementation in Parrot like what Chandon was envisioning, we are going to have a few steps to take:

1. We have to break the Interpreter structure up into two parts: One which is truly global and contains data which all threads need, and one which is local for each thread and contains data that the thread needs. The local interpreter may contain a cache or a mirror of data in the global interpreter.
2. We need to come up with a good sane scheme (which will likely consist of both technical solutions and programmer conventions) to manage access to global values
3. We need to come up with a good sane scheme for sharing values between threads.Creating a local variable and passing a reference to it to another thread essentially turns it into a global variable and opens up problems with contention. We need a good way to manage this without slowing everything down.

All of these problems are solvable, and if we put forward a concerted effort we could have a decent hybrid threading system in Parrot within the next few months. We almost have a complete working Green Threads system ready to merge now, and hopefully that will be enough for our users while we get the rest of the details of the hybrid system worked out and implemented.

ParrotTheory: Locks and Synchonization

I've talked a good amount in the past and recently about threading, so today I'm going to talk about some of the small bits that make threading and concurrency work. I'm thinking that we're also going to need to implement some of these primitives in Parrot eventually, so consider this blog post an extremely verbose way of planning for that.

Let's start the discussion by looking at two small code snippets; a structure definition and a routine that uses that structure:

typedef struct _array {
  int length;
  int *values;
} array;

void push( array *ary, int x) { 
  array->length++; 
  realloc(array->values, newlen * sizeof(int));
  array->values[array->length - 1] = x;
}

This isn't nearly as contrived an example as it may seem initially, though I purposefully made the code a little bit naive. It's worth noting here that the idea of a structure which contains both an array and the integer length of that array is very common. It's how Parrot implements it's STRING type and several of its array PMC types as well. In fact, the push_int VTABLE method for the ResizableIntegerArray PMC probably looks extremely similar to this example code.

Astute observers, and veterans of threading trench warfare will see a problem with this code: There are no locks and no concurrency safeguards, so this code isn't thread safe. Let's take a short walkthrough of this code where we have a preemptive thread switch in the middle to another thread also attempting to access this same method on the same object:

1. We have an array object with length 5 and items {1, 2, 3, 4, 5}
2. Thread A attempts to push the number 6 to the array, Thread B attempts to push the number 7.
3. Thread A enters the function. We set length to 6 and realloc to gain a sixth slot. The array now contains values {1, 2, 3, 4, 5, ?}, because the last value isn't initialized by realloc.
4. At this point, there is a preemptive thread switch and Thread B takes over control.
5. Thread B enters the function and sets length to 7 and reallocs again. The array now contains values {1, 2, 3, 4, 5, ?, ?}.
6. Thread B sets the sixth element to 7. The array is now {1, 2, 3, 4, 5, ?, 7}
7. Thread B gets preempted, Thread A takes over.
8. In thread A, the value of length is still 7, so [ary->length - 1] is still 6. When we add x to the array, we now have {1, 2, 3, 4, 5, ?, 6}

 There are some things we could try here, such as saving the values we need from the structure to local variables, so that even if we preempt in the middle of the functions the length field will be an accurate index. Or, we can try to rearrange the order of operations so some errors appear less frequently or less obviously.  The real problem here is that we have three operations that need to stay coupled: Increasing the known length of the array, reallocating array storage, and assigning an item to that storage. Any break between a set of coupled operations causes a problem. We call these areas of code where operations are sensitive to cross-thread interference critical sections.

As another example of a very small critical section, consider this one line of code:

foo = i++;

This seems pretty simple, but in fact it is not. This line of code requires several assembly language instructions, especially when we are talking about a non-optimized build:

1. Fetch the value of i from memory into a processor register
2. Copy the value of i to the variable foo
3. Increment the register containing the value for i
4. Copy the value of the register back to memory where i is located.

A preemptive thread switch can happen in between any of these steps. Consider the case where we break between steps 2 and 3 to another thread performing the same operation: If i is 5, Thread 1 foo is 5, Thread 2 Foo is 5, and at the end of the code snippet i is 7! If this code snippet is, for instance, in an SQL database generating unique integer keys for rows in a particular table, we've just generated non-unique keys and created a world of hurt for ourselves.

To get around these kinds of problems, one solution is to use a synchronization primitive. A synchronization primitive is any of a class of algorithms and objects that are designed to synchronize and limit access to shared resources. In this sense, a resource is anything that multiple threads might want to access: An IO stream, a global variable, a shared pointer, even a sensitive sequence of instructions,  etc. Any time we have a critical section of code that is sensitive to sharing we want to find a way to limit access to a finite number of simultaneous threads (usually one). There are several ways to do this.

A mutex, short for "mutual exclusion", object is a type of lock that helps to prevent access to a critical section. To pick a pertinent example, think of a mutex like a basketball. Only the one person in the game with the basketball can do things: shoot, pass and dribble. Other players on the team can do other stuff like running, covering, or posting, but they cannot do ball stuff without the ball. You cannot shoot the ball if you do not have the ball, you cannot pass the ball if you do not have the ball. This is a convention of the sport. If we were playing Calvinball instead, maybe we could do these things without looking preposterous. By convention also, if we as programmers declare that a certain shared resource can only be accessed by a thread (player) with the mutex (ball), the those are the rules for our system (game) and things can move along smoothly. Here's an example of that convention in action:

Mutex *m;
AQUIRE_MUTEX(m);
// critical section code
RELEASE_MUTEX(m);

The power in this code is that the AQUIRE_MUTEX() function will attempt to gain ownership of the mutex, and will wait indefinitely for the mutex to become available if some other thread already owns it. ACQUIRE_MUTEX is like waving your arms in the air, shouting "I'm open" until the current ball carrier passes the ball to you. Until you get the ball, you just have to stand with your arms in the air until you get it. Because of that behavior, no two threads can enter the same critical section, assuming of course that the programmer (you) has properly protected that critical section with the mutex. Keep in mind that there is no intrinsic property of the critical section itself that prevents multiple threads from running it simultaneously and corrupting data. The exclusion comes from the proper and pervasive use of locks like our mutex to keep the critical section safe. Here's another example:

Mutex m;

int pop(array* a) {
  ACQUIRE_MUTEX(m);
  int item = a->values[a->length - 1];
  a->length--;
  RELEASE_MUTEX(m);
  return item;
}

void push(array* a, int item) {
  a->values[a-length] = item; 
  a->length++;
}

In this example we can see that we aren't properly using the mutex everywhere, so we can't guarantee that we won't get corrupt data. Multiple threads could just as easily enter the push function simultaneously as could attempt to enter the pop function. If you don't use mutexes everywhere, it's almost as good as not using them anywhere. This is a convention that the coder must decide upon beforehand and follow diligently.


There are multiple ways to implement locks and mutexes. One idea is a spinlock, which attempts to access a flag and enters an endless while-loop until it can. An empty while-loop can be very inefficient on a processor, but if we call a sleep command inside the loop to allow other threads to run while we wait it isn't such a big problem. Spinlocks implemented by the OS inside the kernel event loop can be very efficient indeed. In fact, as a general rule, if the OS implements locking primitives they tend to be much better to use than anything you can write in userspace.

Another type of lock primitive is a semaphore, though it is subtly different. A semaphore allows a finite number of threads to access a finite number of shared resources at a time. Where a normal mutex, like a spinlock, allows only one thread to enter at a time the semaphore may allow one or more. Consider a case where we have five worker threads in a web server, and 100 incoming connections. A semaphore uses a first-come-first-served method to assign incoming connections to available threads. Each incoming connection attempts to access the semaphore. As requests are completed, threads signal their availability and the semaphore assigns the next connection in the list to that thread. A semaphore with only one shared object acts like a normal mutex or spinlock.

The overhead of a lock is the amount of effort it takes to acquire and manage the lock. In a uniprocessor system the lock may be very simple to obtain: First disable interrupts so we cannot be preempted by another thread, check the status of the lock, obtain the lock if it's available, and re-enable interrupts. In a multiprocessor system, especially one with shared memory, the overhead and error-checking involved can be much higher. In these systems the performance gain from using threads can be much higher too, so it's a trade-off.

Granularity is the amount of stuff in your critical section protected by a lock. Course Granularity means that we have lots of code inside our critical section. This is good because we need fewer locks and therefore experience lower overhead. Plus, it's easier as a programmer to make sure we acquire fewer locks over large swaths of our program. The downside is that the larger our protected critical section is, the more likely other threads are going to be blocked waiting to enter it. This, in turn, can create problems like high latency. Fine Granularity is the opposite, where we lock as little code as possible. The upside is that we don't have to worry about multiple threads blocking for long on small bits of code. The downside is that acquiring more locks means more lock overhead, and more programmer effort to implement all the locks consistently and safely. Fine granularity can also lead to deadlock, where multiple threads are stuck waiting for locks that other threads own.

The Python interpreter, as an example, implements a single Global Interpreter Lock, which is a lock to govern the entire Python interpreter. Only one operating system thread can be running the interpreter at once, to prevent corruption of global data. I think new versions of Ruby do this too.

There are other methods of synchronizing access to shared resources. One method is to make all data immutable; If you can't modify data, you can't corrupt it. Since Parrot's strings are immutable, you shouldn't ever need a lock when working with them. You may still need to worry about playing with a mutable container PMC which holds strings, or the mutable registers which point to strings, however.

Parrot is definitely going to want to make use of OS-supplied locks in some fashion. Maybe we want to make a PMC wrapper around system lock primitives, or we want to create some kind of lock manager that uses a single system mutex to distribute a series of immutable tokens to worker threads. The exact details of locking are certainly up for debate, but the fact that we don't want to brew our own should be obvious.

Since locks need to be used consistently for them to be of use at all strongly hints at the fact that Parrot should probably do the locking internally. We probably don't want to apply locks to every single operation, since the common case programs are single-threaded applications and we don't want to apply the performance penalty of lock overhead to programs which don't need it. If Parrot can identify only those PMCs which are shared, it can apply locks selectively to those PMCs only, limiting overhead to only the places where it is necessary. For instance, if we add a synchronize op:

$P0 = syncronize $P1

We can create some kind of wrapper PMC type whose vtables enter a lock, call the vtable of the synchronized PMC, and then release the lock. In this example, if everybody used $P0 when they wanted to modify $P1, all operations would be safe. The onus would be on the programmer to explicitly mark the PMC as synchronized, of course, and many programmers will probably forget to do that.

Maybe instead of passing PMC references between threads directly we create and pass clones and modify them separately on different threads. Then, when we want our changes from one thread appear in another thread, we would call some kind of propagate op:

propagate thread, obj

This would pause the specified thread, update the object contents, and then unpause the thread. This would be very similar to the message passing that languages like Erlang use (not exactly the same, because Erlang wouldn't pause the recipient for this, but you get the idea).

Maybe we have a system where we only share read-only copies. So thread A would own the PMC, but thread B could get a read-only copy of it. This would completely obviate the need to lock the PMC since only one thread could write to it, but then we need some kind of mechanism where thread B could make modifications back if necessary, or maybe B could gain the writable copy and make A's copy read-only. This system could get very complicated very quickly, however.

We could also avoid most locks if we used a transactional memory system to avoid memory corruption, but that could still add overhead to the single-threaded common case and then we would still want a system of locks for other operations that don't require locking a PMC.

These are only a handful of the many potential options that Parrot has ahead of it, and I can go into greater detail about any of them that people are interested in thinking about. I think Parrot is going to want at least some kind of locking mechanism, so we could start prototyping those things immediately if we wanted. How these mechanisms get implemented and applied within Parrot is obviously the bigger issue that we can ignore for now.