[H-GEN] Which is better?

[Russell Stuart]

On Tue, 2004-04-27 at 18:05, Andrae Muys wrote:
> Uniprocessor Garbage Collection Techniques
> http://citeseer.ist.psu.edu/wilson92uniprocessor.html
>     - A much longer paper, but can be read by section.  Covers a number 
> of different algorithms; including incremental, and conservative (ie. 
> works with C/C++) collectors.  Also includes discussions on locality, 
> and implementation issues.  Estimates the cpu-cost of GC to be ~10% and 
> the memory-cost a factor of 2.

A handy reference to have - I have read the paper before, and can never
remember where I saw it.

To put it in more precise terms - the paper estimates the cpu-cost of GC
to be 10% over manual memory allocation, and factor or 2 over manual
memory allocation.  By manual memory allocation they mean malloc and
friends.  10% sounds low - but they are trading memory use for CPU
cycles.  Fair enough.  Java's foot print is about 3 times - so it
probably pushes the 10% closer to, if not below, 0.

But, you can't compare it with stack based allocation and static
memory.  I can't help but think the authors of your first paper live in
some sort of parallel universe.  For example, this statement:
  "Thus, allocating a cell from the heap is identical in cost to 
  pushing a cell onto the stack."
By "pushing a cell onto the stack", I presume he means executing
the machines push instruction.  Actually it is a parallel universe -
its for a machine that effectively has an infinite amount of memory.
Honest to god - this is pushing the limits even for GC advocates.

You also say the paper "concept that Heap Allocation need not be
substantially more expensive than Stack Allocation".  It doesn't.  It
attempts to show that, on real machines (I presume you don't call
something with more memory than will ever be needed real), the free
operation for GC is faster than a stack based free.  I can't really
comment on their GC analysis.  But for stack based analysis it is based
on the assumption that a stack based "free" costs one instruction.  It
usually doesn't because there are usually several objects in the stack
frame.  That is assuming that freeing up a stack allocation costs any
additional instructions over freeing up the stack frame - which again
usually isn't the case.  In fact in the real world stack based
allocation usually has a 0 cost over and above setting up the stack
frame.  As you can probably guess, I think the paper is a waste of bits,
possibly worse if people go looking to it for advice.

Actually you don't need deep analysis to show that stack based is
cheap.  If you take a relatively modem language like C#, which I think
we can safely assume has had the best brains money can buy working on
its design, it not only continues with Java's atomic values like int's,
longs and so on - it expands on them by introducing struct's.  This is
because, and their designers said so quite explicitly - they are
faster.  If they weren't they would dynamically allocate everything.

Re: "This is flat out wrong; and a good example of the sort of dodgy 
practices associated with premature optimisation."  Well, as I hope I
have shown, its not flat out wrong.  In fact its merely repeating the
advice given by Java's designers.  For example, they say instead of
writing:

  String timeFormat(DateTime t) {
    SimpleDateFormat myDateformat = new SimpleDateFormat("...");
    return myDateformat.format(t);
  }

write:

  static SimpleDateFormat myDateformat = new SimpleDateFormat("...");
  String timeFormat(DateTime t) {
    return myDateformat.format(t);
  }

You see lots of "howto" examples like this.  In Java, not writing your
code like this could almost be considered a bug.  Its not like it is
harder to read.

Onto more philosophical arguments, I took Harry's original question as a
beginners search for general patterns in writing code.  I don't mean
design pattern - I mean some much more low level - like what is the best
way to write a "for (;;)" statement.  The answer Harry got back was that
in modern languages on modern machines writing:
  for (int i = 0; i < array.length; i += 1)
as opposed to:
  int l = array.length;
  for (int i = 0; i < l; i += 1)
will make stuff all difference.  You are better off going for the
clearer version.  This advice is spot on, of course.

To put it another way, if someone is going to optimise your program,
they are unlikely to every change the first version into the second -
ever.   Since the second version is harder to read don't do it.  But, if
they see the SimpleDateFormat example I gave earlier in a slow running
program, they will probably curse him.  They will wonder where else he
has done something like this.  Its something every good Java programmer
keeps in the back of his mind - is this memory allocation necessary? 
Can I move it outside of the loop?  Outside of the function?  Outside of
the class?  If it doesn't seriously hurt the code readability then the
answer is almost always yes - he should.  Like any rule it can be
overdone, but applying it well will generally save time.

So, since Harry was seemed to be looking for advice on low level
patterns - I offered this one up.  And I stand by it.