S. Rao (sonny@burdell.org) on 10/23/06 wrote:
---------------------------
>Tzvetan Mikov (tzvetanmi@yahoo.com) on 10/22/06 wrote:
>---------------------------
>>S. Rao (sonny@burdell.org) on 10/21/06 wrote:
>>---------------------------
>>Again, I disagree. Object creation is supposed to be an extremely cheap operation,
>>ideally comparable in cost to literally pushing the object onto the stack. In a
>>single threaded environment with a compacting GC this is an attainable goal.
>
>I've never heard this before.. I've always thought
>object allocation was an expensive proposition, how
>could it possibly be as cheap as a simple stack allocation,
>and why would Java have primitive types if that were true
>(maybe a big can of worms here :-))?

In the old days of dynamic languages a type of GC called "baker two-space" or "copying GC" was used.

This method is very simple. Memory is divided into two equal halves. For a while all objects are allocated from the first half. Then when the first half is filled the garbage collector starts, it copies all reachable objects from the first half into the second half. At the same time it compacts them.

In such a system object allocation is very cheap. A pointer called the "fill-pointer" or "free-space-pointer" is simply advanced to create an object. So, say in lisp a cons-pair is two words long. The free-space-pointer is simply incremented by two, and it's old value is used as the location of the cons-pair. You have to check for overflow of the pointer. This is far less than what say "malloc" has to do, generally it must do a function call then look up things in tables before allocating any memory.

Elsethread I mention why although superficially attractive this scheme often doesn't work great in practice:
http://www.realworldtech.com/forums/index.cfm?action=detail&id=73806&threadid=73581&roomid=11