Re: markbits out of cells. 1st attempt.

[Han-Wen Nienhuys <hanwen at cs dot uu dot nl>]

Hi jim,

>> markbits_p = address ^ (1 <<x - 1)
>Do you really mean exclusive-or (^) here?

No, no no, this was after a long day of work.  I think I meant

    markbits_p = address & ~(1 << x - 1)

>> * x has to be so large enough, such that most pages don't contain
>>   markbits.
>
>You're reading the data structure to do the traversal, so those are
>pages you'll need in memory anyway.  Why not locate the mark bits on
>the same page as their data?  Is the fact that the mark bits will be
>written, while most of the data is unchanging, part of the
>consideration?

I wasn't thinking of CPU cache behavior.  The problem I want to solve
is GUILE gc in combination with paging (Read: formatting large scores
in LilyPond).  The current marking scheme has two major disadvantages:

1. mark bits are written all over the heap (in a disorganized
pattern), causing many pages to written during the mark phase.

2. to check a mark bit, the part of the heap containing the cell has
to be in core, causing many pages to be read (in a disorganized
pattern.) - note: you don't need to know the contents of a cell if it
is already marked.

If most of heap pages do not contain mark bits, both 1. and 2. should
not be a problem.

> If you just store a pointer in the heap segment, you incur an extra
> memory reference to discover whether a cell is marked or not.

Thinking this over once again I think I like separating memory
references from the heap, because it makes the entire heap read only,
and it is simpler to manage. Maybe it would even be possible to use
the alignment slack to store the marks.

-- 

Han-Wen Nienhuys, hanwen@cs.uu.nl ** GNU LilyPond - The Music Typesetter 
      http://www.cs.uu.nl/people/hanwen/lilypond/index.html