[gclist] Re: gclist-digest V1 #70

[Giuliano Carlini]

Marc,

You wrote: 
>I reiterate my comment that you might as well go forward because it is less
>costly.

Why is it cheaper to go forward? The local IRG is computed during the local GC 
very cheaply. And if you go forward you need to handle this case:
           root-------------------\
                                   \
           A -------> B ------> C--->D
           ^                    |       
           |                    |
           ----------------------
That is, both a persistent root, and C point to D. If you start anywhere on the 
cycle ABC and go forward, you will encounter D which is live. You will either 
need to retain ABC which is inferior to going backwards, or you will need some 
kind of complex analysis which is more expensive than going backwards.


>More importantly, I think this algorithm is incorrect.  The mutator can be
>concurrently affecting the graph in a way that tricks this algorithm.

As you noted later, this is easily handled with a write barier.

Arturo claims to handle this without a write barrier, but I'm very suspicious of 
that claim. I'll need to look at his algorithm more closely. Even if it satisfies 
my meager intellect, I'd still be a bit suspicious until a proof were 
constructed. While academics sometimes neglect practical hands on testing of 
their constructs, we industrial types have a habit of neglecting formal analysis.

>Uugh!  On principle I am opposed to such claims of intellectual property on
>any algorithm.

I lean in this direction. At the very least, obtaining a patent should require 
much more inventive work than demonstrated here. As Arturo admits, using an IRG 
was pioneered by others. And once you have the IRG, tracing it is should not be 
considered so inventive as to deserve a patent. I mean, how hard is the thought 
process: "Hmmm. Tracing forward is hard. But, there is an IRG. AHA! Let's trace 
it."

But this is out of our hands. Lawyers have far more clout than we do. They've 
hoodwinked the politicians into believing that progress in CS will be impeded 
without patent protection. Despite 30 to 40 years of evidence to the contrary.

>In this particular case, you have no basis, because the
> algorithm has been published by others before.

I guess this depends on whether the patent was filed before the dates of 
publication. Arturo: when was the application filed? Marc: what are the 
publication dates you are aware of.

g