Exploiting Dual Core's with Py_NewInterpreter's separated GIL ?

[Joe Seigh]

Paul Rubin wrote:
> robert <no-spam at no-spam-no-spam.invalid> writes:
> 
>>>I don't want to discourage you but what about reference
>>>counting/memory
>>>management for shared objects? Doesn't seem fun for me.
>>
>>in combination with some simple locking (anyway necessary) I don't
>>see a problem in ref-counting.
>>If at least any interpreter branch has a pointer to the (root)
>>object in question the ref-count is >0. ----
>>Question Besides: do concurrent INC/DEC machine OP-commands execute
>>atomically on Multi-Cores as they do in Single-Core threads?
> 
> 
> Generally speaking, no, the inc/dec instructions are not atomic.  You
> can do an atomic increment on the x86 using LOCK XCHG (or maybe LOCK
> INC is possible).  The thing is that the locking protocol that
> guarantees atomicity is very expensive, like 100x as expensive as an
> unlocked instruction on a big multiprocessor.  So yes, of course you
> could accomplish reference counting through locks around the ref
> counts, but performance suffers terribly.  The solution is to get rid
> of the ref counts and manage the entire heap using garbage collection.

Atomic increment and decrement instructions are not by themselves
sufficient to make reference counting safe.  It's what Boost::shared_ptr
uses to make itself internally thread-safe but it's not safe to copy
a shared_ptr without "owning" it. Not like Java where you can safely
copy a reference (Java pointer) no matter what.

Basically there's a race condition where an object containing the
refcount can be deleted between the time you load a pointer to
the object and the time you increment what used to be a refcount
and is possibly something else but definitely undefined.

I have an experimental refcounting implementation at
http://atomic-ptr-plus.sourceforge.net/


> 
> For stuff like dictionary access, there are protocols (again based on
> LOCK XCHG) that don't require locking for lookups.  Only updates
> require locking.  Simon Peyton-Jones has a good paper about how it's
> done in Concurrent Haskell:
> 
>   http://research.microsoft.com/~simonpj/papers/stm/stm.pdf
> 
> This is really cool stuff and has found its way into Perl 6.  I'd like
> to see Python get something like it.

That seems to be about STM (Software Transactional Memory).  What you're
describing seems to be read lock-free using what I call PDR
(PCOW (Partial Copy On Write) Deferred Reclaimation).  Examples of PDR
are RCU (used in Linux kernel),  Maged Michael's SMR hazard pointers,
and thread-safe GC (used in Java's concurrent collections java.util.concurrent).

You can also use PDR to manage safe refcounting ,e.g. RCU based refcounting, rcuref,
in the Linux kernel.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.