Removing Python's GIL: The Gilectomy [video]
youtube.com
youtube.com
1) Lot's and lot's of fine grained locks. One on every collection. Oooof.
2) All that locking and unlocking absolutely thrashes the cache with Larry's current prototype implementation. I was surprised at how little time was spent doing the actual locking/unlocking itself. I was blown away by the performance impact of maintaining cache coherent locks (at least in Larry's current implementation). And for reference, I was a logic designer on mainframes in the 1980's where we paid attention to making locks perform well across independent caches, so I'm no newb around this issue, but it was still striking to me.
(packed house) Larry's joke at the beginning about "practicing for getting on your plane later tonight" is a reference to the packed seating. The Portland convention center staff were taking the Portland fire marshall's directives quite seriously. We spent several minutes making sure every seat was occupied, and then the staff evicted the standee's :/
Like how the JVM assumes classes are final and removes virtual calls until it first sees a subclass.
It's a great talk; the video is really worth watching. At the end, he says he welcomes anyone to join him in the sprints, but basically don't bother unless you really know cpython and multithreading programming because this is very advanced stuff.
The cache invalidation isn't done by cpython, it's done at the the chip level when global atomic incr and decr instructions are triggered. Hastings was pretty clear that the performance hit was very closely tied to the way that modern processors depend very heavily on caching, pipelining, branch prediction, etc.
I think that the kind of implementation you're suggesting, where the VM adopts a locking strategy based on whether or not it's actually multi-threaded, might be possible, but sounds like it conflicts with Guido's edict that no GIL-less solution will be accepted that overly complicates that cpython codebase.
I'm probably making a hash of the talk, but I saw it in person, and it was surprisingly clear to someone like me who isn't a serious C programmer, but remembers their class in operating systems and kernel design.
> Like how the JVM assumes classes are final and removes virtual calls until it first sees a subclass.
AFAIK, the python VM doesn't do any JITting at all. A runtime decision in the VM about handling locks is impossible at this point, I think.
https://github.com/Microsoft/Pyjion
pycon 2016 talk:
if (threads)
lock(...);
To get past all that locking, you need to be able to determine which objects are never visible to more than one thread. They don't need locks. PyPy might be able to do this; it does some global analysis.
Sadly I'm not optimistic about the approach. Fine grained locking most times has a cost people don't think about. Using reference counting converts every read into two writes (to update ref counts). Then we get into second order effects where unrelated data structures share a cache line with the lock & reference counts. You're just fighting the machine architecture.
Even with additional optimizations, I just can't getting acceptable results with the approach as taken. With the constraints put in place by Guido around GIL elimination it looks like python on multicore is going to be what we have today.
And all the other locking issues are still in play. How would you share a list with another interpreter such that they don't both have access to the same list items? Any solution that looks like a deep copy isn't going to be much better than just serializing across a process boundary.
Even if you didn't have the GIL, you would still need locks with threads to manipulate any mutable datastructure. The usual concurreny safety advice always apply.
- Doing better than atomic inc/dec for those reference counts is going to be hard. All of those techniques are still in an "unconfirmed myth" state AFAICT: someone published a paper but nobody has confirmed that the result holds on a broader set of machines, workloads, baselines, etc.
- Great call on userspace locking. Note that you can do this portably. You don't need special OS support. See https://webkit.org/blog/6161/locking-in-webkit/
- Seems like lots of the locking use cases can indeed be made lock-free if you are willing to roll up your sleeves and get dirty. That's what I would do.
- I still bet that the dominant cost is lock contention and he is not analyzing his data correctly. He appears to claim that it can't be locks because the total CPU time is greater than the total length of critical sections and that some analysis tools tell him that there is massive cache trashing. But that's exactly what happens if you contend on locks too often. Lock contention causes context switches and thread migrations. Both of those things require cache flushes. So the code that runs under contention will report massive cache thrashing because it will have a high probability of being on a cold cache. Programs indeed will run slower under contention than without it, and while his slow-down is extreme, I've seen worse and fixed it by removing some contention. He should find every contended lock and kill it with fire.
- The dip at 4 cores doesn't surprise me. Computers are strange and most "scalability" charts (X axis is CPUs, Y axis is some measure of perf) I've made had weirdly reproducible dips and jerks.
See closed github issues for gilectomy.
Exhibit #1: the lock to protect lazy initialization. That just needs a CAS on the slow path and a load-load fence on the fast path. Delete the object you created if you lose the race and try again.
Exhibit #2: you can probably do dirty things to make loading from dicts/lists not require locks even though storing to them does.
template<typename T, typename... Args>
void constructSingleton(Atomic<T*>& singletonRef, Args&&... args)
{
for (;;) {
T* oldValue = singletonRef.load();
if (oldValue)
return oldValue;
T* newValue = new T(std::forward<Args>(args)...);
if (singletonRef.compareExchangeWeak(nullptr, newValue))
return newValue;
delete newValue;
}
}
This is a python conference talking about a long-known perf issue and the guy just asked why not use another language. It's like going to WWDC and asking why everyone isn't using Android.
This was definitly not the intent of the troll, just a joke. But a badly executed one. It's like going to a political meeting, hearing somebody's plan to improve economy, and as a question asking him why not just change country. It makes little sense.
Plus, everybody should consider the resume of the guy, cause he is not just a newcomer trying to show off. He is a hell of a good dev.
The guy's competence isn't the issue. It's the requirements of what the fix can and cannot do.
_Everything_ is a mess due to the massive technical debt of never improving key parts of the runtime.
I mean what's the point of a runtime where adding threads makes things magnitudes slower than running in a single-thread?
"But that's just the state right now, they will fix this!"
No, they won't. Just as a perspective: People usually fight over a single percent of improvement or less when working on runtime concurrency. Nobody just goes in and fixes _magnitudes_ of performance issues without rethinking what has been done and picking a completely different approach. This is not about making things "faster". This is literally going from doing necessary work to discovering a way of not having to do the work at all anymore. That's just not going to happen. Neither locks nor reference counting have anywhere near this optimization potential given the current language semantics.
I think the whole (C)Python community missed the train more than a decade ago. Things that necessarily had to happen just didn't happen. Many communities and groups of developers "professionalize" over time. This doesn't seem to have happened in Python.
Just an example: C extensions. It has been clear for at least a decade that the existing C interface won't work for threading, "real" garbage collection, etc.
What would have been smart: Providing a better interface 10 years ago, effectively giving C ext devs 10 years of time to migrate their code. This way efforts to remove the GIL today would have to satisfy one fewer constraint that's currently crippling all of the efforts.
Same with a lot of other things ... getting rid of the GIL would have required changes to various parts of the stack over the years (GC, language -> Python 3?, APIs ...), turning the actual removal of the GIL just into a final act of a multi-step process.
What actually happened: Nothing. And now they just try to break the large lock into millions of smaller locks ... in 2016. WAT? This just tells me that key people in the Python community never really gave a damn about the issue and therefore this guy will waste his time.
I have never expected Python's demise, but it now seems that largely its culture and not its lacking technology brought it down for good. From my perspective, they should have never released Python 3 with a GIL. That's what broke Python's neck, finally.
Why not use another language? I think it's a perfectly valid question for that guy to ask.
My personal opinion on "Why not use another language" is a bit different though:
Adopting a different language might make sense – not necessarily for technical reasons but for cultural. The technical issues could have been addressed in time, and the language would be in a much better situation today.
The fact that the technical issues have not been addressed for such a long time shows a clear lack of leadership and focus. I think these cultural issues are a bigger problem than the technical issues. You can fix code, but you can't fix people.
* it prevents deadlocks
* it prevents livelocks
* it means you don't have to lock when you share across threads
and how it's not a big deal because
* you're IO-bound anyway
* you can easily write performance critical parts in C
* you can use multiple processes, in fact that's better design anyway
So I would have asked more critical questions. Feel free to call that trolling if you want.
For me Python is the ultimate glue code - it's the duck tape of my programming world. If I know multi-core performance is going to be an issue up front, I would pick another language.
No other language really does it right like Go - unifying event based and traditional multi-threading paradigms in a way that transparently utilizes all the cores on your system, while allowing you to write plain old iterative, blocking code.
Go may be less than ideal in many other regards (i.e. the rest of the language), but it gets this right.
Not trying to start a war but... Erlang, Haskell, F#, and a few others abstracted Evented IO and parallelism before Go even existed.
I would never consider Go mainstream myself though. Erlang is practically more mainstream.
Erlang is mainstream, but being functional probably not open to consideration for 99% of developers.
If so, I'll use it today!
So even though I work in a majority Go company, and I feel like Go is quite mainstream, I firmly believe that Rust is the future!
Btw, sorry if this Rust enthusiasm comes across as a bit over the top, I'm quite tired. I just really like it is all.
Rust definitely does things Go doesn't, but Go also offers things Rust doesn't: builtin concurrency and parallelism with goroutines and channels, garbage collection (which is useful when your app can tolerate its moderate overhead), very fast compilation, and great tooling.
Green Threads is one of the most important features in golang - to pretend that "Rust offers almost everything that Go does", but ignore the number 1 feature is dishonest.
It is cool you like Go, it is a nice language. But before you claim "it is the only language that does X", you should learn about other langues as well.
And I don't consider any functional language as a viable choice for the vast majority of mainstream users.
Dunno if that'll work in practice, but it seems like the best possible plan going forward to get the change without causing strife.
This is why I have shifted most of my code (I work in data warehousing) to Go. Python is handy for little scripts and data mining.
- We can view this work is as a revisiting of Greg Stein's GIL-removal attempt in Python 1.4:
http://dabeaz.blogspot.com/2011/08/inside-look-at-gil-remova...
It seems wholly reasonable to revisit the approach in light of how the language and ecosystem have changed since 1999.
There are demands made of CPython core developers to remove or address the problem of the GIL, and these efforts demonstrate how much work is necessary to do that successfully.
- Comparing single-threaded performance in a GIL implementation against single-threaded performance in a GIL-less implementation is considered an unfair comparison. A GIL-less will do extra book-keeping that will necessarily result in slower single-threaded performance.
Unless you can choose between having the GIL or not, I think it's perfectly reasonable to compare the performance. If you can choose, then I think it's still useful to know the kind of overhead you're adding.
If you create a new Python implementation from scratch it doesn't need to be there. It is not intrinsic to Python; it is intrinsic to the specific CPython implementation.
It is also, broadly speaking, easy to remove the GIL. However the bar the CPython developers have set is that they will not accept a GIL-removal patch that harms single-threaded performance. This is the bar that has proved difficult to hurdle.
It is also fair to point out that while it's a perennial topic in the Python community, it is not the only scripting language implementation with a GIL or moral equivalent in it.
[1]: For similar reasons, none of the core implementations of the 1990s-era dynamic scripting languages have a very good true multi-threading story. (Some of the alternates can do it, like Jython.) They don't all even have implementations, and last I knew, none of them have anything that you ought to use in production. I don't think this is a fundamental limitation of any of the languages in question, it's just that it's really hard to retrofit threading onto a non-threaded code base after ~ten very heavy years of development. There's a set of other things that are hard to retrofit in to an existing code base if they don't start there from day one, like "unit testability" or "proper string handling".
So the problem in Python will never be fixed in my opinion - the problem is Python and there's no saving it. Without breaking backwards compatibility it will always be better to use processes instead of threads and keep the GIL.
Personally my feeling is that if you care enough about performance to be threading in Python, you care enough about performance to not be using Python anyhow. It's a nice language, it's by far my favorite of the scripting languages of its family, but even with all the PyPy JIT and other magic tech words you can throw at it, it's still a slow language. When that doesn't matter, great; when it does, you eventually reach the point where you're stuck. (I've never been overwhelmed by the "implement it in C then" argument, for many reasons, and nowadays to an increasing degree if you're going to implement your "core" in another language for speed, there's a language you can choose that is both nice to use and already fast for your task, and that's only going to get more true as time goes on.)
But assuming threadsafe collections is still a problem - that will never match single-threaded GIL Python running in multiple processes unless some efficient way can be found to optimistically make the collections not threadsafe and only pay the synchronization costs when they're really shared between threads. I think that's a solvable problem, but not with the STM approach PyPy took. Still performance will likely lag the mutli-process solution which doesn't have that cost.
I would rather see a Python that introduces a way to allocate PyObjects in shared memory and with no thread safety. Since it's a new system, that can be done without breaking compatibility. Then sharing between processes could be as easy as sharing between threads and just as efficient. The GIL could stay in that case and the C API could be left unchanged.
Do IronPython and Jython, Python implementations which do not have a GIL, use fine-grained locking? How is multi-threaded performance on these implementations? Surely not as bad as this talk implies CPython with fine-grained locking would be?
It only took him about a week to remove the GIL (and the talk includes the steps); all this work is making a GIL-less python work as well as one with a GIL.
The backstory of Python's GIL is a tradeoff made nearly a quarter-century ago. Python came from the Unix world, where forking processes was the common way of having multiple lines of execution, but in the 90s threading was starting to take off as an alternative (insert standard anecdote about Java adopting threading since it had to run on set-top TV boxes that couldn't handle multi-process concurrency).
So Python needed to gain support for threading, but also needed to not horribly break a lot of existing code -- particularly extensions written in C -- and not destroy performance. Which was an issue since Python's memory management and garbage collection internals were not thread-safe, and it would've been both a major slowdown and a major breaking change to just say "all right, we'll do this in the theoretically best possible way".
The trade-off solution was to introduce this global lock which needed to be acquired and released. The side effects of the lock are twofold:
1. Only a single thread can be executing at a time within a given Python interpreter process, and
2. The bookkeeping around the lock introduces overhead. This overhead is negligible in some cases but ruinous in others.
The tradeoff seemed reasonable at the time, though. For one thing, hardware capable of exposing the single-thread limit as a relevant limit wasn't exactly common in 1992. For another, the overhead of the GIL mainly bites you in CPU-bound workloads, and at the time people wanted threading to write I/O-bound applications like networking daemons.
Here in 2016, of course, everybody has a multi-core computer in their pocket and we see plenty of CPU-bound workloads that we'd like to parallelize. Which is why people complain about the GIL. But now it's even more of a breaking change to try to remove it, and still has performance implications.
Both language and interpreter design. I was wanting to give a talk or at least write about some of the internals of the interpreter and language and how to do it better next time.
In case there is interest for this I might actually get around doing that for once.
(I have played around with a different from of GIL-less execution a few years back that was based on independent interpreters and message passing thread bound objects but I ran into so many issues with the interpreter :()
Yes, I'm very interested in your thoughts on this, particularly wrt interpreter design.
Do you think anyone will ever use the lessons learned about interpreters and write a "better next time" implementation of Python, or do you only see an improved runtime appearing alongside a significantly different language?
Consider this simple statement:
tmp = p.f; o.f = tmp;
In a garbage-collected language that supports concurrency and has no GIL, this is a wait-free operations with no locks. You load p.f. You store o.f. Maybe there is a GC barrier, but that fast-paths to a load-branch combo 99% of the time. It's all easy and fast.
In a reference-counted language that supports concurrency and has no GIL, you're in a world of hurt.
First you have to make sure that you atomically increment the reference count on 'tmp'. This is guaranteed to have to store to the memory that 'tmp' points to. Note that in the GC world, no such store happened. Already here you have a problem: you're storing to memory much more often. Stores are the things that parallel CPUs hate, because the hardware now has to do work to propagate the value you stored to the other CPUs.
But wait, there's more. You also have to atomically decrement the reference count of the object that 'o.f' used to point to. That's another store that will have to be propagated. Now your algorithm for "o.f = tmp" looks like this:
1. Atomically increment the reference count of 'tmp'.
2. Load the old value of o.f and atomically decrement the reference count. If it drops to zero, delete the object.
3. Store 'tmp' into 'o.f'.
But wait, you're not done yet. You also have to handle the dec race on 'o.f'. If two threads simultaneously store to 'o.f', in which case you now have a race in steps 2 and 3. You'd think that you can just use an atomic swap in (2), but then you'd be wrong: you don't want two threads to both load the same old object from (lets that one 'oldfart') and dec it. Here's an example:
Thread #1: o.f = tmp;
Thread #2: o.f = thingy;
If the interleaving is Thread #1 executes step (2) then Thread #2 executes step (2) then Thread #1 executes step (3) then Thread #2 executes step (3), then you will dec 'oldfart' twice, inc 'tmp' once, and inc 'thingy' once. This means that you've over-released 'oldfart' and over-retained 'tmp'. Bad news!
So, you have to put a lock around steps (2) and (3). Basically every field in memory has to have a lock around it. That sucks!
It's kind of funny to me that people who are stuck with reference counting say things like "yeah, garbage collection can be made to be as fast as reference counting". That makes me lol. Garbage collection is so much faster than reference counting, particularly in concurrency scenarios, because:
In a GC: "o.f = p.f" is a load and a store, with maybe an extra load-branch if you have a barrier. That's it. There's no locks! There's no atomics! Notably, the only thing being stored to is "o.f", just as the user intended.
In reference counting: "o.f = p.f" means atomic ops on 'tmp', a lock around "o.f", and atomic ops on 'oldfart'. The lock will require one or two atomic ops. There will be atomic stores to the cache line of "o.f", the cache line of "tmp", and the cache line of "oldfart". What a mess!
TL;DR. Garbage collection is a slam dunk of overwhelming awesomeness.
From what I know, most current managed languages are using GC, not reference counting, so perhaps it's an inherently better approach.
There is a version of PyPy without a GIL[2], but it runs much slower on ordinary code and is still under development. The developers are looking for financial support.[3] The approach is to identify large blocks of code as transactions, and run them in parallel. If they try to access the same data, one transaction fails and is backed out. It's like database rollback.
But you have to write your code like this:
from transaction import TransactionQueue
tr = TransactionQueue()
for key, value in bigdict.items():
tr.add(func, key, value)
tr.run()
Note that Python has support for shared memory:
https://docs.python.org/2/library/multiprocessing.html#shari...
In fact, `numpy` has its own mechanisms to support shared memory between processes:
https://bitbucket.org/cleemesser/numpy-sharedmem
Neither of these approaches seem to be used very commonly in practice.
Python itself has some "sub-interpreter" support. There was a long conversation about this last year:
https://mail.python.org/pipermail/python-ideas/2015-June/034...
Finally, I have a working approach using `dlmopen` to host multiple interpreters within the same process:
https://gist.github.com/dutc/eba9b2f7980f400f6287
- the approach is so bizarre, because it's a very naïve multiple-embedding. It was intended to prove that you could run a Python 2 and a Python 3 together in the same process as part of a dare. This was thought impossible, since there are symbols with non-unique names that the dynamic linker would be unable to distinguish (which lead me to the `RTLD_DEEPBIND` flag for `dlopen`,) and that there is global state in a Python interpreter that interacts in undesirable ways (which lead me to `dlmopen` and linker namespaces.)
- this approach is stronger than the traditional subinterpreter approach, since I can host multiple interpreters of distinct versions. i.e., I can host a Python 1.5 inside a Python 2.7 inside a Python 3.5.
- the approach is stronger in that I completely isolate C libraries. There's a good amount of functionality provided by C libraries that maintain global state. e.g., `locale.setlocale` is a wrapping of C stdlib locale and is globally scoped.
- this approach is weaker in that it requires a dynamic linker that supports linker namespaces, which effectively limits its use on Windows
- this approach is weaker in that it's not complete: there's insufficient interest in this approach for me to actually write the shims to allow communication between processes.
- this approach is weaker in that it has some weird restrictions such as being able to spawn only 15 sub-interpreters before running out of thread-local storage space
I suppose the premise is that the GIL-removal efforts involve pessimistic coördination. A sub-interpreter approach might have a lighter touch and allow the user to handle coördination between processes (perhaps even requiring/allowing them to handle locks themselves.)
Is it normally implemented along with buffered reference counting? It feels like those fit together very neatly, one thread managing the counts and receiving updates from the other threads, and each other thread tries to only send updates it needs to.
Is it simply a case of doing something basic a lot of times is faster than doing something smarter a few times because computers are just really fast at basic things? Or is there something more to this?
1. Same or better performance 2. No breaking existing extensions 3. Not overly-complicating the cpython implementation
These are tough requirements, but obviously sensible, and Hasting's discussion of trying to meet them is interesting.