Re: circularity detection on 64bit platforms with bitmaps

[Vladimir T. <vtz...@gm...>]

Hi Don,
On Nov 6, 2008, at 9:26 PM, Don Cohen wrote:
> Sam Steingold writes:
>> Don Cohen wrote:
>>>
>>> - What does this have to do with multithreading?
>> bitmaps are used only with MT
> This is weird!
> I now see that single thread was using GC mark bits,
> and I can see that you can't share those bits in the case where
> you have to compute circularities in two threads at the same time.
> But what happens if you have to GC in one thread while doing the
> circularity check in another?  Then your bit maps no longer work.
> So, without reading the code further, it seems that you either have
> to delay GC (and all threads that want to do it, very likely all of
> them if you run out of space) until the check is done, or be prepared
> to abandon and restart the circularity check after the GC finishes.

The circularity check cannot be interrupted by GC - there are no so  
called "safe points" in it.
So if a GC is requested while circularity check is in progress - the  
GC will wait till circ check finishes in order to be able to suspend  
this thread.
(if we want -  "safe for GC" points may introduced in circularity  
detection of course - but currently there are none).

> If you're willing to lock out GC while you compute circularities,
> then it seems you should be willing to lock out other circularity
> checks, and so you can use the GC bits again.  But at this point
> I don't understand why you don't at least start with a hash table.
> When that gets too big it becomes more reasonable to lock out all
> other circularity checks and GCs.

We'll start - next week :) - just too busy these days.
I think we should not use any dynamic memory allocation.
Something like this:
http://article.gmane.org/gmane.lisp.clisp.devel/19419

> The file also says that this check is used in both print and read.
> I don't understand why it should be used by either.  In print, if
> *print-circle* is nil then you don't have to worry about circularities
> at all, and if it's t then I'd expect you to create a hash table of
> pointers as you print.

Yes - print is the "difficult" case.

> In read, it seems all you have to do is recognize the circularity
> markers as they arrive, store the new ones and look up the old ones.
> And all of this should have no impact on GC.
>

You are right here. This involves changes to the reader (which I have  
still not touched).

Vladimir