4 ms·

This was a great talk, and was presented to a packed house (see below). If you don't want to watch the whole video, the issue really boils down to this: 1) Lot

This was a great talk, and was presented to a packed house (see below). If you don't want to watch the whole video, the issue really boils down to this: 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 :/

chrisseaton 10y ago
I wonder if you could completely elide the CAS needed by userspace locks (the bit which thrashes the cache I presume) while there is only one thread running. Then when a new thread is created for the first time (if it ever is), pause the program and promote and acquire all the locks. Like how the JVM assumes classes are final and removes virtual calls until it first sees a subclass.
- fatbird 10y ago
  Late in the talk he discusses strategies to avoid thrashing that amount to making locks as local as possible, ideally such that they behave the same way they would in the current unsynchronized environment. The big problem is that all the locks are global, so a change to a lock triggers a gigantic cascade of cache invalidation (and voided branch prediction, etc). 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.
  - chrisseaton 10y ago
    Right, but I'm suggesting why bother using atomic operations and cache invalidation if there is known to be just one thread? Which is the case we want the lowest overhead on. Why not only start doing that stuff when the second thread is started.
    - fatbird 10y ago
      Ok, I think I see the point you're making, but what I took from Hastings talk is that devolving locking to as local a scope as possible is doing just that: wherever possible, locking in an analytically single threaded context which is trivial and basically cost-free. 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.
      - chrisseaton 10y ago
        The complexity requirement is the tricky one then, yes. I think I'd disagree with Guido there - a little complexity in the VM managed by a few experts is probably a good cost to accept for millions of users.
        sametmax 10y ago
        It's not Guido's point. He means that CPython, being the reference implementation, must remain easy to understand.
    - fatbird 10y ago
- fatbird 10y ago
  Sorry if I keep responding, but there's a lot of interesting points in your question. > 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.
  - chrisseaton 10y ago
    Well the user space locks he discusses already read a variable and branch between uncontended and contended cases. Specialising speculatively for single threaded would just be a third cannot-be-contended case. But yes it'd work better with a JIT - yet another reason to write one.
  - dbcurtis 10y ago
    There is a version of Python that JITs -- I forget it's name at the moment, though.
    - anateus 10y ago
      PyPy
    - smortaz 10y ago
      there are several. we (microsoft) are also trying to get an api into cpython so that anyone can use to build JITs for python. our sample implementation is at: https://github.com/Microsoft/Pyjion https://github.com/Microsoft/Pyjion pycon 2016 talk: https://www.youtube.com/watch?v=1DAIzO3QXcA https://www.youtube.com/watch?v=1DAIzO3QXcA
  - ori_b 10y ago
    Sort of. if (threads) lock(...); should still be pretty quite a bit faster than fine grained locks everywhere, since your atomics aren't broadcasting and shooting down cache lines everywhere.
- gpderetta 10y ago
  Some JVM do exactly that. The optimisation is called biased locking and would likely work in python as well.
- geofft 10y ago
  I think that was one of the suggestions from the after-talk conversation. The trouble is that you have to do it on thread creation, which is sort of a cheesy way to ensure single-threaded performance doesn't go down: it still leaves multi-threaded applications performing worse than under the GIL, which isn't super helpful. Ideally you'd do it on the first access to the object by a second thread, but there's no particular interface that makes it clear that's what's happening: the second thread just knows about the object somehow, and reads it at some point. And there are enough global variables in Python (e.g., every module) that simply promoting it when it's visible to multiple threads is too aggressive.
- ori_b 10y ago
  There's a lot you can do. There's not much you can do in cpython as it currently stands without breaking a lot of code, especially when it comes to extensions.
  - chrisseaton 10y ago
    I work on a new Ruby interpreter, and our solution to this problem has been to interpret the C code of extensions. That way we can give it one API, but really implement another.
Animats 10y ago
Nothing is truly thread-local in Python. You can muck with anything from another thread, finding it with "dir" and altering it with "setattr" if necessary. This implies worst-case locking. 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.
mtanski 10y ago
> 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. 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.
- sametmax 10y ago
  Multi-interpretter is another possibility that is currently explorer. Still need to load 1 interpretter by core, but no more serialization to share objects.
  - loqi 10y ago
    How so? Sharing arbitrary objects via memory requires some form of coordinated memory management. So you still need a process-wide GC, meaning you're probably stuck with that 30% hit from thread-safe refcounting. 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.
    - sametmax 10y ago
      Right now multi-processing use a very expensive serialization to send to one worker to another. Shared memory is much cheaper. 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.

chrisseaton 10y ago

I wonder if you could completely elide the CAS needed by userspace locks (the bit which thrashes the cache I presume) while there is only one thread running. Then when a new thread is created for the first time (if it ever is), pause the program and promote and acquire all the locks. Like how the JVM assumes classes are final and removes virtual calls until it first sees a subclass.

fatbird 10y ago
Late in the talk he discusses strategies to avoid thrashing that amount to making locks as local as possible, ideally such that they behave the same way they would in the current unsynchronized environment. The big problem is that all the locks are global, so a change to a lock triggers a gigantic cascade of cache invalidation (and voided branch prediction, etc). 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.
- chrisseaton 10y ago
  Right, but I'm suggesting why bother using atomic operations and cache invalidation if there is known to be just one thread? Which is the case we want the lowest overhead on. Why not only start doing that stuff when the second thread is started.
  - fatbird 10y ago
    Ok, I think I see the point you're making, but what I took from Hastings talk is that devolving locking to as local a scope as possible is doing just that: wherever possible, locking in an analytically single threaded context which is trivial and basically cost-free. 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.
    - chrisseaton 10y ago
      The complexity requirement is the tricky one then, yes. I think I'd disagree with Guido there - a little complexity in the VM managed by a few experts is probably a good cost to accept for millions of users.
      - sametmax 10y ago
        It's not Guido's point. He means that CPython, being the reference implementation, must remain easy to understand.
  - fatbird 10y ago
fatbird 10y ago
Sorry if I keep responding, but there's a lot of interesting points in your question. > 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.
- chrisseaton 10y ago
  Well the user space locks he discusses already read a variable and branch between uncontended and contended cases. Specialising speculatively for single threaded would just be a third cannot-be-contended case. But yes it'd work better with a JIT - yet another reason to write one.
- dbcurtis 10y ago
  There is a version of Python that JITs -- I forget it's name at the moment, though.
  - anateus 10y ago
    PyPy
  - smortaz 10y ago
    there are several. we (microsoft) are also trying to get an api into cpython so that anyone can use to build JITs for python. our sample implementation is at: https://github.com/Microsoft/Pyjion https://github.com/Microsoft/Pyjion pycon 2016 talk: https://www.youtube.com/watch?v=1DAIzO3QXcA https://www.youtube.com/watch?v=1DAIzO3QXcA
- ori_b 10y ago
  Sort of. if (threads) lock(...); should still be pretty quite a bit faster than fine grained locks everywhere, since your atomics aren't broadcasting and shooting down cache lines everywhere.
gpderetta 10y ago
Some JVM do exactly that. The optimisation is called biased locking and would likely work in python as well.
geofft 10y ago
I think that was one of the suggestions from the after-talk conversation. The trouble is that you have to do it on thread creation, which is sort of a cheesy way to ensure single-threaded performance doesn't go down: it still leaves multi-threaded applications performing worse than under the GIL, which isn't super helpful. Ideally you'd do it on the first access to the object by a second thread, but there's no particular interface that makes it clear that's what's happening: the second thread just knows about the object somehow, and reads it at some point. And there are enough global variables in Python (e.g., every module) that simply promoting it when it's visible to multiple threads is too aggressive.
ori_b 10y ago
There's a lot you can do. There's not much you can do in cpython as it currently stands without breaking a lot of code, especially when it comes to extensions.
- chrisseaton 10y ago
  I work on a new Ruby interpreter, and our solution to this problem has been to interpret the C code of extensions. That way we can give it one API, but really implement another.

Animats 10y ago

Nothing is truly thread-local in Python. You can muck with anything from another thread, finding it with "dir" and altering it with "setattr" if necessary. This implies worst-case locking. 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.

mtanski 10y ago

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

sametmax 10y ago
Multi-interpretter is another possibility that is currently explorer. Still need to load 1 interpretter by core, but no more serialization to share objects.
- loqi 10y ago
  How so? Sharing arbitrary objects via memory requires some form of coordinated memory management. So you still need a process-wide GC, meaning you're probably stuck with that 30% hit from thread-safe refcounting. 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.
  - sametmax 10y ago
    Right now multi-processing use a very expensive serialization to send to one worker to another. Shared memory is much cheaper. 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.