<br><br><div><span class="gmail_quote">On 4/15/07, <b class="gmail_sendername">Talin</b> <<a href="mailto:talin@acm.org">talin@acm.org</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

Greg Ewing wrote:<br>> 2) Objects owned by a thread<br>><br>> Python code creates and destroys temporary objects<br>> at a high rate -- stack frames, argument tuples,<br>> intermediate results, etc. If the code is executed

> by a thread, those objects are rarely if ever seen > outside of that thread. It would be beneficial if > refcount operations on such objects could be carried > out by the thread that created them without locking.

<br><br>While we are on the topic of reference counting, I'd like to direct your<br>attention to Recycler, an IBM research project:<br><br>"The Recycler is a concurrent multiprocessor garbage collector with<br>extremely low pause times (maximum of 6 milliseconds over eight

<br>benchmarks) while remaining competitive with the best throughput-<br>oriented collectors in end-to-end execution times. This paper describes<br>the overall architecture of the Recycler, including its use of reference<br>

counting and concurrent cycle collection, and presents extensive<br>measurements of the system comparing it to a parallel, stop-the-world<br>mark-and-sweep collector."<br><br>There are a bunch of research papers describing Recycler which can be

<br>found at the following link:<br><br><a href="http://www.research.ibm.com/people/d/dfb/publications.html">http://www.research.ibm.com/people/d/dfb/publications.html</a><br><br>I'd start with the papers entitled "Java without the Coffee Breaks: A

Non-intrusive Multiprocessor Garbage Collector" and "Concurrent Cycle Collection in Reference Counted Systems". Let me describe a bit about how the Recycler works and how it relates to what you've proposed.

<br><br>The basic idea is that for each thread, there is a set of thread local<br>data (TLD) that contains a pair of "refcount buffers", one buffer for<br>increfs and one buffer for decrefs. Each refcount buffer is a flat array

<br>of pointers which starts empty and gradually fills up.<br><br>The "incref" operation does not actually touch the reference count field<br>of the object. Instead, an "incref" appends a pointer to the object to

the end of the incref buffer for that thread. Similarly, a decref operation appends a pointer to the object to the decref buffer. Since the refcount buffers are thread-local, there is no need for locking or synchronization.

<br><br>When one of the buffers gets full, both buffers are swapped out for new<br>ones, and the old buffers are placed on a queue which is processed by<br>the collector thread. The collector thread is the only thread which is

<br>allowed to actually touch the reference counts of the individual<br>objects, and its the only thread which is allowed to delete objects.<br><br>Processing the buffers is relatively simple: First, the incref buffer is<br>

processed. The collector thread scans through each pointer in the<br>buffer, and increments the refcount of each object. Then the decref<br>buffer is processed in a similar way, decrementing the refcount.<br><br>However, it also needs to process the buffers for the other threads

<br>before the memory can be reclaimed. Recycler defines a series of<br>"epochs" (i.e. intervals between collections). Within a refcount buffer,<br>each epoch is represented as a contiguous range of values within the

array -- all of the increfs and decrefs which occurred during that epoch. An auxiliary array records the high water mark for each epoch.</blockquote><div> Huh, interesting idea.  I downloaded the papers and plan to give them a read.  The one isssue I can see with this is that because of these epochs and using a buffer instead of actually manipulating the refcount means a delay.  And I know some people love the (mostly) instantaneous garbage collection when the refcount should be at 0.

<br><br>Anyway, I will give the paper a read before I make any more ignorant statements about the design.  =)<br><br>-Brett<br></div></div>