oo hardware

Andreas Raab andreas.raab at gmx.de
Tue Mar 25 00:56:06 UTC 2003


> > Well a write barrier just needs a write not a read modify 
> > write cycle so it should be better
> 
> But it has to monitor every write.

Yup, but this can be _really_ cheap. For example, we could (trivially)
implement a write barrier by using hardware memory protection. This costs
extra cycles if have a hit but is exactly ZERO cost for those 98% of writes
where it isn't triggered (I once measured the percentage of hits for Squeak
and it turned out to be in the 1-2% range for your average activities). I
had been talking to Dan about this - one of the things you could do when
using HW protection is (besides others) to keep track of the modified pages
and use those as "roots" instead of some explicit roots table - this would
have a number of advantages such as that a) you have an essentially
"infinite roots table" (as you could enumerate over all the pages of memory)
b) you would have the overhead only upon the first write to each page and c)
you would handle large objects much more efficiently than we do today (as
you would only trace the particular page of the object which gets modified).
All in all, if such a scheme is implemented correctly the cost of the write
barrier could be very close to zero.

> >  but that depends on the hardware write buffers working
> > well. I'm assuming a card marking write barrier. New space 
> > doesn't need any write barrier protection.
> 
> Sure, but I think it's really not a very clear-cut matter, with a lot 
> of dependencies on how the hardware works and how programs behave.

One thing to keep in mind here is that the tradeoff really is in the
combination of freeing AND allocating objects. A copying (compacting)
collector has some overhead when reclaiming objects - but it is incredibly
cheap in allocation. Any non-compacting memory manager has to spend much
more time figuring out a "reasonable place" where to put an object, manage
free-lists etc. etc. etc. This is essentially why copying collectors win so
big when it comes to lots of short-lived objects. They do little work on
compaction (assuming not many survivors) and essentially none on allocation.

> > The copy only happens when collecting so it only effects 
> > live objects and with a generational collector we are hoping
> > that most objects die young.
> 
> Sure, but you are copying the entire object from one place to 
> another, instead of modifying a single word. 
> Also, hope is just that:  hope.

Well, that's true and yet, I have in my entire use of Smalltalk (which is
10+ years) exactly once found this to be a real problem - which was solved
by reading up and experimenting a bit with a few GC parameters. About the
only place where I find the the incremental behavior cumbersome if when you
essentially deal with tons of "media data" - just bits (primitive numbers
and floats) which - if not represented as a homogenous type - tend to
explode in your face. But fortunately, Squeak has float arrays and vector
operations for many of those things ;)

> Not a guarantee. 

There's no guarantee for a non-copying memory manager either ;-) It's just a
question of the tradeoffs - in a compacting GC/allocator you reason that you
don't want to spend time on allocation/freeing individual objects which is
true for small, short-lived objects. In a non-compacting scheme you reason
that you don't want to spend time in copying objects and compacting memory;
which is true for large long-lived objects. In any case, if the basic
assumptions change you have a problem.

> If environmental parameters change (larger objects, 
> not so many dying quite so young) then it doesn't work out the same 
> way.  For (one) example, Objective-C objects tend to be 
> larger and also tend to stick around longer.
> 
> So I think the matter is not quite so cut and dry.

Well, actually it is. It's quite simple: If you have many small, short-lived
objects then a compacting GC/allocator is the way to go. If you have few,
large, long-lived objects (let's call them data structures ;) then it
clearly isn't. And vice versa: If you have a compacting allocator make sure
your app doesn't use huge data structures. If you don't, make sure it does.

Cheers,
  - Andreas



More information about the Squeak-dev mailing list