Hi all!
This is an update about the Software Transactional Memory subproject of
PyPy. I have some good news of progress. Also,
Remi Meier will
likely help me this summer. He did various
investigations with PyPy-STM for his Master's Thesis and contributed back
a lot of ideas and some code. Welcome again Remi!
I am also sorry that it seems to advance so slowly. Beyond the usual
excuses --- I was busy with other things, e.g. releasing PyPy 2.0 --- I
would like to reassure people: I'm again working on it, and the financial
contributions are still there and reserved for STM (almost half the money is
left, a big thank you again if you contributed!).
The real reason for the apparent slowness, though, is that it is really
a research project. It's possible to either have hard deadlines, or to
follow various tracks and keep improving the basics, but not both at the
same time.
During the past month where I have worked again on STM, I worked still on
the second option; and I believe it was worth every second of it. Let me try
to convince you :-)
The main blocker was that the STM subsystem, written in C, and the
Garbage Collection (GC) subsystem, written in RPython, were getting
harder and harder to coordinate. So what I did instead is to give up
using RPython in favor of using only C for both. C is a good language
for some things, which includes low-level programming where we must take
care of delicate multithreading issues; RPython is not a good fit in
that case, and wasn't designed to be.
I started a fresh Mercurial repo
which is basically a stand-alone C library. This library (in heavy development
right now!) gives any C
program some functions to allocate and track GC-managed objects, and
gives an actual STM+GC combination on these objects. It's possible
(though rather verbose) to use it directly in C programs, like in a
small example interpreter. Of course the eventual purpose is to link it
with PyPy during translation to C, with all the verbose calls
automatically generated.
Since I started this, bringing the GC closer to the STM, I kept finding
new ways that the two might interact to improve the performance, maybe
radically. Here is a summary of the current ideas.
When we run
multiple threads, there are two common cases: one is to access (read and write)
objects that have only been seen by the current thread; the other is to read
objects seen by all threads, like in Python the modules/functions/classes,
but not to write to them. Of course, writing to the same object from
multiple threads occurs too, and it is handled correctly (that's the whole
point), but it is a relatively rare case.
So each object is classified as "public" or "protected" (or "private",
when they belong to the current transaction). Newly created objects, once
they are no longer private, remain protected until
they are read by a different thread. Now, the point is to use very
different mechanisms for public and for protected objects. Public
objects are visible by all threads, but read-only in memory; to change
them, a copy must be made, and the changes are written to the copy (the
"redolog" approach to STM). Protected objects, on the other hand, are
modified in-place, with (if necessary) a copy of them being made
for the sole purpose of a possible abort of the transaction (the "undolog"
approach).
This is combined with a generational GC similar to PyPy's --- but here,
each thread gets its own nursery and does its own "minor collections",
independently of the others.
So objects are by default protected; when another thread tries to follow a
pointer to them, then it is that other thread's job to carefully "steal"
the object and turn it public (possibly making a copy of it if needed,
e.g. if it was still a young object living in the original nursery).
The same object can exist temporarily in multiple versions: any number
of public copies; at most one active protected copy; and optionally one
private copy per thread (this is the copy as currently seen by the
transaction in progress on that thread). The GC cleans up the
unnecessary copies.
These ideas are variants and extensions of the same basic idea
of keeping multiple copies with revision numbers to track them.
Moreover, "read barriers" and "write barriers" are used by the C program
calling into this library in order to be sure that it is accessing the
right version of the object. In the currently investigated variant
I believe it should be possible to have rather cheap
read barriers, which would definitely be a major speed improvement over
the previous variants. Actually, as far as I know, it would be a major
improvement over most of the other existing STMs: in them, the typical read barrier
involves following chains of pointers, and checking some dictionary to see if this
thread has a modified local copy of the object. The difference with a
read barrier that can resolve most cases in a few CPU cycles should be
huge.
So, this is research :-) It is progressing, and at some point I'll be
satisfied with it and stop rewriting everything; and then the actual
integration into PyPy should be straightforward (there is already code
to detect where the read and write barriers need to be inserted, where
transactions can be split, etc.). Then there is support for the
JIT to be written, and so on. But more about it later.
The purpose of this post was to give you some glimpses into what I'm
working on right now. As usual, no plan for release yet. But you can
look forward to seeing the C library progress. I'll probably also start
soon some sample interpreter in C, to test the waters (likely a
revival of duhton).
If you know nothing about Python but all about the C-level
multithreading issues, now is a good time to get involved :-)
Thanks for reading!
Armin