Paul Rubin wrote: > robert <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
