[gclist] write barrier via VM traps

Hans Boehm boehm@hoh.mti.sgi.com
Tue, 27 May 1997 09:42:05 -0700


[ I also don't have access to the appropriate references at the moment.  So
this is again a quick reaction.  I think we're converging anyway.]

On May 27,  9:40am, Eliot Moss wrote:
> Subject: [gclist] write barrier via VM traps
> Ok, since I was a co-author on the paper being discussed, I'll wade in on
> this.
>
> o If you examine the paper, you'll see that Tony Hosking calculated
break-even
>   points, that is, the number of mutations at which it becomes cheaper to
take
>   one trap than to keep executing software write barrier code at each
>   mutation. In our particular system, it was hundreds to thousands of
>   mutations (this is from memory; I urge interested parties to look up the
>   paper). A software write barrier could be made even faster than ours by
>   keeping a pointer to the base of a card mark table in a register, which
>   would make the break-even point higher. The trade-off is undoubtedly a
>   gradual one.
Hundreds to thousands of mutations per page is not a huge number for some
applications.  Consider a program that sorts an array of a million C-like
strings.  On a 32 bit, 4K/page machine, this is likely to perform something on
the order of 10 million pointer assignments on 1000 pages without any
intervening allocation or collection.  This would put it way over the breakeven
point for VM-based dirty bits.

>
> o The scanning costs are still significant. Someone at Univ of Washington
>   considered the case of providing page dirty bits from the OS, thus removing
>   almost all of the trap overhead. As I recall, they found the cost to be
>   comparable to a software write barrier, but not necessarily a lot cheaper.
If someone with acces to a Sun machine wants to do experiments, my collector
can use either trap-maintained or kernel-maintained dirty bits under Solaris.

>
> o To my knowledge, no one has done a careful study of the value of sub-page
>   protection bits. It is a study I have wanted to do for some time, but it
has
>   been hard to get it high enough on the agenda to get it done, and when I
>   have proposed it to vendors supporting my work, it has also not been rated
>   as a high priority with them, even w.r.t. Java.
Note that at least early RS/6000 hardware had sub-page (32 byte?) protection
hardware, and probably even some OS support.  Real experiments shouldn't be
impossible.


On May 27,  9:40am, Charles Fiterman wrote:
> Subject: Re: [gclist] write barrier via VM traps
> I don't think much of these methods any more because we are
> getting such good results with pseudo incremental mode and
> footprint reduce.
>
I agree that "pseudo incremental mode" or abortable collections are cheaper
than real incremental collections.   And they're often perfectly sufficient.
 But they're not a complete replacement for a write-barrier.  The main problem
is that not all applications have idle time at predictable and sufficiently
short intervals, or at all.  This is particularly a problem with multi-threaded
applications that run a compute-bound thread in the background, while expecting
interactive performance from a "foreground" thread.

A less serious issue is that even if there is idle time, you may run into more
problems than necessary with programs that page, since the computation during
idle time will most likely replace the mutator's working set, causing it to run
more slowly when it resumes.

Hans


-- 
Hans-Juergen Boehm
boehm@mti.sgi.com