[gclist] Sun bitmap marking patent

[Boehm, Hans]

Could anyone shed some light on Sun's bitmap-based marking patent?  Its
existence was pointed out to me by Anthony Green yesterday.

This is US patent number 5920876.  (You can get to it from
http://164.195.100.11/netahtml/srchnum.htm by pasting in the preceding
number, or you might try the URL:
http://164.195.100.11/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&
u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1='5920876'.WKU.&OS=PN/5920876&RS=PN/5
920876 )

As far as I can tell, it covers basically any garbage collection scheme that
identifies pointers via bitmaps associated with the object, and uses
portions of this bitmap to index into something like a branch table.  It
seems to me that the claimed invention is really the use of the branch table
(i.e. switch statement) instead of a branch on each bit, since bitmap-based
mark schemes were clearly prior art on April 23, 1997.  However the patent
seems to cover the 1-bit-at-a-time scheme if it uses an indirect branch to
test the bit.

As far as I can tell, it does not cover schemes in which the descriptor
associated with the object is either the address of a mark routine, or a
sequence such addresses, or a sequence of branch table indices, or anything
along these lines, so long as it does not specifically associate one bit
with each possible pointer location in the object.  Thus at least it seems
to be easy to come up with slightly more complex schemes that have
equivalent or better performance and do not infringe the patent.  (A
sequence of jump table indicees gives more flexibility, in that you do not
have to consider the same number of words each time through the loop.)

Questions:
Can someone from Sun, e.g. one of the inventors, shed more light on this?
Has anyone else looked at this patent more carefully?
Any informed opinions about whether this might be enforcable?
Is there any prior art that uses bitmaps in this context, and examines more
than one bit at a time?  (There is clearly prior art that examines one bit
at a time, and there are many other contexts in which the multiple bit at a
time optimization is used.  I don't know of any systems that combine the
two.  And it probably didn't help much to do so until very recently.)

Hans