[gclist] A problem with the Baker treadmill.

[James McCartney]

At 1:49 PM -0600 1/13/97, Paul R. Wilson wrote:
>One thing I'm not clear on is the costs of synchronization operations
>on today's chips.  Last time I thought about this, I was worried
>that on some chips, synch operations were expensive (e.g., no atomic
>test-and-set).  (And I was under the impression that on some crummy
>OS's, the only portable synch operations were system calls.  This
>is less of an issue for you.)

You can get test_and_set, compare_and_swap, fetch_and_store, fetch_and_add,
etc. on the PowerPC pretty efficiently with the lwarx, stwcx instructions.
I think the Be does some evil things to make the 603 work as a
multiprocessor and I'm not sure if they break the reservation mechanism
above.

>BTW, some info on your system might be helpful.  Are you using Be
>threads, and are they switched unpredictably?  How fast are the
>synch instructions?  Do you have a separate GC thread, or do you
>fake it by doing some GC work by an out-of-line call every n bytes
>of allocation?

Well currently it is only single threaded and the multiprocessing
version is only on the drawing board. I envision multiple mutating
threads and a single collector. The Be's threads are all within
the same address space, can be unpredictably interrupted, can
be moved to a different processor between interrupts. Since two
threads may be scheduled on the same processor spin locks are out
because you could wind up spinning for your entire time quanta before
the thread that released the lock got scheduled.

The suggestion to log overwritten pointers is interesting because
a singly linked list can be pushed and popped without blocking using
compare_and_swap. Therefore you'd only need one list, not one per thread.
So only the collector thread would need to relink objects in the
treadmill and change their colors. If the color of an object is changed
at the end of the scan of it, then the object doesn't need to be
locked when being updated by the mutator. You may get an extra
pointer thrown onto the log list if the scanner scans a pointer, the write
barrier logs it and then the scanner changes the containing object's color.
Hmm would that lead to a non halting algorithm? Don't think so
because the scanner can check the color of the logged pointers
to see if they are already grey. Am I thinking straight?

(There is an interesting paper "Non-Blocking Garbage Collection
for Multiprocessors" by Herlihy and Moss, but it makes copies
of objects out the wazoo -- every time an object is updated.)


   --- james mccartney     james@clyde.as.utexas.edu   james@lcsaudio.com
If you have a PowerMac check out SuperCollider, a real time synth program:
ftp://mirror.apple.com//mirrors/Info-Mac.Archive/gst/snd/super-collider-demo.hqx