Re: Exploiting Dual Core's with Py_NewInterpreter's separated GIL ?
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
Re: Exploiting Dual Core's with Py_NewInterpreter's separated GIL ?
Ross Ridge wrote: > Joe Seigh wrote: > >>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. > > > That doesn't really make sense. The object can't be deleted because > the thread should already have a reference (directly or indirectly) to > the object, otherwise any access to it can cause the race condition you > describe. > True but if the thread didn't already have a reference, how would you get that initial reference to a shared object without a lock? -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software. -- http://mail.python.org/mailman/listinfo/python-list
Re: Exploiting Dual Core's with Py_NewInterpreter's separated GIL ?
Martin v. Löwis wrote: > You still didn't say what you would suggest to make it thread-safe > again; most likely, you proposal would be to add locking. If I > understand Joe's approach correctly, he has a solution that does > not involve locking (although I don't understand how it works). > Sun had applied for a patent on it. You can go to the uspto search page here http://www.uspto.gov/patft/index.html and look for 20060218561 Code preparation technique employing lock-free pointer operations 20060037026 Lightweight reference counting using single-target synchronization Click on the images link on the patent application where the illustrations are which show the concepts probably better than the text. The first one above is actually a continuation patent on three different techniques. One using double wide compare and swap, one using ROP (Repeat Offender Problem), a form of PDR, and one using DCAS (compare and swap of two separate locations) which only exists on MC68020 and MC68030 processors. -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software. -- http://mail.python.org/mailman/listinfo/python-list
Re: Exploiting Dual Core's with Py_NewInterpreter's separated GIL ?
Ross Ridge wrote: > Ross Ridge schrieb: > >>So give an example where reference counting is unsafe. > > > Martin v. Löwis wrote: > >>Nobody claimed that, in that thread. Instead, the claim was >>"Atomic increment and decrement instructions are not by themselves >>sufficient to make reference counting safe." > > [...] > > The problem your describing isn't that reference counting hasn't been > made safe. What you and Joe seem to be trying to say is that atomic > increment and decrement instructions alone don't make accessing shared > structure members safe. How you increment and decrement a reference count is an implementation issue and whether it's correct or not depends on the semantics of the refcount based pointer. I.e. what kind of thread safety guarantees are we ascribing to pointer operations? Java reference (pointer) guarantees are not the same as C++ Boost shared_ptr guarantees. In Java simple pointer assignment, "a = b;" is always safe no matter what any other thread may be doing to a and/or b. With shared_ptr you have to have a priori knowlege that the refcount for b will never go to zero during the copy operation. Usually that implies ownership of b. To get a better feeling for the latter semantics you should take a look at C++ String implementations. A C++ String COW (copy on write) implementation using atomic inc/dec is as thread-safe as a non-COW String implementation because in both cases you have to own the strings you access. About the term "thread-safe". In Posix it's taken as meaning an operation on non-shared data isn't affected by other threads. So non-COW strings are thread-safe, and COW strings are thread-safe if their internal refcounting is synchronized properly. But note that in both cases, the implemention is transparent to the user. So as you say, a lot depends on how you access or want to access shared structure members, e.g. with or without locking. -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software. -- http://mail.python.org/mailman/listinfo/python-list
