[pypy-dev] pypy-stm and lock-free data structures

[Armin Rigo]

Hi Andrew,

On Thu, Oct 24, 2013 at 8:27 PM, Andrew Francis <andrewfr_ice at yahoo.com> wrote:
> A bit more context - I have looked at the C code for the Go channel
> implementation and said "wow, there is a lot of locking there"! I also have
> been following conversations concerning race conditions and the race
> detector (based on thread sanitizer) and asking myself: pypy-stm could do
> this.

Precisely my point.  You're coming with paper X describing Y and
thinking "pypy-stm could do this", whereas I don't see any obvious
connection between the two.  To repeat myself, pypy-stm has no GIL
internally, but exposes to the user semantics that are the same as a
GIL Python.

To be on the clear side, you could use CPython and write C, with
GIL-releasing code around the complicated lock-free algorithm; but the
point of the lock-free algorithm is to be very fast, negating the
advantage of releasing the GIL in the first place.  Is that correct?

Then if you want to integrate it inside pypy-stm instead, it's more
complicated than that: we don't want an algorithm (say a simple
lock-free queue) without some behavior that is tailored to the stm
world.  For example, if you implement only a queue, then: - pops will
appear out of order if they are done in some order but the
transactions commit in a different orders; - pops will be lost if they
are done by a transaction that aborts; - pushes must be at least
delayed until the transaction commits, otherwise we see bogus data
from other threads.

So you need to think about it more deeply than just "pypy-stm is cool,
let's use it for X".  You can't just think about pypy-stm as a
lock-free Python, because that's only half the truth.  PyPy-stm is all
about a special use of lock-free algorithms in order to give the user
the illusion of the GIL.  I would say that it's not really the correct
ground to experiment with lock-free structures in general --- it's a
place where we can experiment with custom adaptations of some
lock-free structures, done towards a specific goal that makes sense
for the user of pypy-stm.


A bientôt,

Armin.