[gclist] write barrier via VM traps

[Eliot Moss]

Ok, since I was a co-author on the paper being discussed, I'll wade in on
this.

o The primary cost was indeed that of taking the trap and having it reflected
  to a user-mode signal handler in Unix. If, once a page is dirty, one removes
  the protection so that later writes do not cause a trap, then the frequency
  of traps drops off, which, curiously, makes the individual traps cost more
  (presumably because less of the kernel code and data structures are in cache
  or TLB). One thing that we showed was that cost "in real life" of each trap
  was 10 times higher than cost measured in a tight loop. Rather than being
  sub-millisecond (on a 10 to 20 MHz processor), it became more like 5 ms. I
  agree that this is _mostly_ an OS problem, not fundamentally a hardware
  problem.

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.

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.

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.

o Our paper was done in the context of a Smalltalk system. Smalltalk is much
  more dynamic, in several ways, than Java, and it is easier to "bury"
  overheads, even in a "high performance" Smalltalk system than it will be in
  a high performance (native code) Java system. We have a Java VM under
  construction in which we can examine some of these questions.

o My personal view is that sub-page protection bits are probably a good idea,
  for supporting noting of changes for garbage collectors as well as
  persistent programming. They might also make certain kinds of debugger and
  profiling features cheaper. And they need not introduce that much hardware
  cost. But without paper studies to prove their value, I don't see a trend
  towards supplying them.

PS -- Sorry to be short on citations; I felt it best to start to respond now
rather than to wait to get all the details together :-).

-- Eliot

J. Eliot B. Moss, Associate Professor
Computer Science Department, LGRC          (413) 545-4206
University of Massachusetts                (413) 545-1249 (fax)
Box 34610                                  moss@cs.umass.edu (email)
Amherst MA 01003-4610