Experimental PATCH to improve thread performance

The attached patch against Ruby 1.8.6-p110 improves the performance of
multi-threaded applications, especially those that create helper threads
when the parent thread is deeply nested in its call stack.

Totally Bogus Benchmark script #1:
----------------------------

$depth = 0

def outer name
  if ($depth+=1) < 2000
    outer name
  else
    250.times {
      Thread.new do
        inner :inner, name, Thread.current
      end.join
    }
  end
end

def inner innerName, outerName, parent
  Thread.new do
    parent.join
    k = Proc.new {|n0, n1| q = n0.to_s << n1.to_s }
    k[innerName, outerName]
  end
end
   
outer :outer

---------------------

Equally Bogus Benchmark Script #2:
----------------------------

$depth = 0

def outer name
  ball = Thread.current
  inner = Thread.new Thread.current do | outer |
    loop {
      Thread.stop until (Thread.critical=true; ball == inner)
      (ball=outer).run
    }
  end
  2000.times {|i|  
    Thread.stop until (Thread.critical=true; ball == Thread.current)
    (ball=inner).run
  }
end

def recurse someArg
  if ($depth+=1) < 2000
    recurse 3.14159
  else
    outer :outer
  end
end

recurse "top"
-------------------------------

On my 1.5 Ghz Centrino laptop, benchmark #1 executes about twice as fast
after the attached patch is applied.  Benchmark #2 shows a 30% improvement.

Admittedly these benchmarks were contrived, as all benchmarks are,
to demonstrate situations where this patch would yield the greatest
performance
improvement.  However, I don't believe there is any Ruby script that will
execute measurably slower or take more memory after this patch is applied.
(Yes, I'm challenging someone to prove me wrong there :-)

Unpatched, 'C' Ruby allows each thread's backtrace to chain up into the
frames of its parent, frozen at the time the child was first created.
This means that context switches require copying not only the active
thread's
frames, but all of the parent's as well.  Further, creating new Proc
object's
in the child thread requires that "framedup()" copy the parent's frames as
well as the child's.  Moreover, the frozen parent's stack keeps the garbage
collector from releasing objects referenced there, even after those
references are no longer present in the active parent thread as it
continues to execute (or dies).

This patch works by isolating each thread's stack from that of its parent.
There is still just one stack, but when a new thread is created, its current
"ruby_frame" is linked directly back to Ruby's "top_frame".  Thus, each
thread
behaves as through it was started with its own empty stack.  When a context
switch is performed, only the slice of the stack that is accessible by
the active
thread need by copied from the heap.  Whenever it is necessary
to duplicate the active thread's frames, only those are copied, not the
parent's
as well.  This saves both time and space.  The only "cost" is an additional
pointer in the (already large) "struct thread"

If all this seems a bit too good to be true, it just might be.
I've tested the patch against our multi-threaded "killer" app that
managed to crash all unpatched versions of Ruby 1.6.8, 1.8.x, 1.9 and JRuby.
If you've got a multi-threaded test or application, I invite you to
try it against this patch.  Feedback would be very much appreciated.

Yes, there are a couple side effects:

1)  ruby backtraces from child threads will now end at the thread's
creation.
     Frames from other thread's will no longer be included in any backtrace.
     I strongly suspect that Ruby 1.9, JRuby and other "native threaded"
     Ruby implementations will behave this way as well.
     (Can anyone confirm this?)

2)  The 'C'-level stack will become corrupt as slices of it get copied
     into and out of the heap.  If you are using a 'C'-level debugger, its
     backtrace command will get confused after it ascends the stack
     into frames above those of the current Ruby thread.

Background:
I noticed this monolithic stack copying behavior while debugging a
couple segfault causing bugs I'd found in ruby 1.8.6 and 1.6.8.
These resulted in some instances when a child thread
outlived its parents.  (See my recent post:  Continuations on dead
threads ...)

In 1.6.8, the situation is worse.  Without the appropriate version of
this patch,
the "newest" 1.6.8 snapshot will very occasionally crash running these
benchmarks.
The good news is that benchmark #1 runs 5 times faster after 1.6.8 is
patched :-)
Benchmark #2 runs  twice as fast.  If anyone, aside from me, is still
interested
in Ruby v1.6.8, just let me know.  I'll be happy to post a patch for it.

- brent