Stack performance issue

There is a performance issue in the stack code, which the attached
patch attempts to address.

The problem revolves around what happens when you are close to the
boundary between two chunks. When this happens you can find that you
are in a loop where something is pushed on the stack, causing a new
chunk to be allocated. That item is then popped causing the new chunk
to be discarded only for it to have to be allocated again on the next
iteration of the loop.

This is a well known problem with chunked stacks - it is certainly a
known issue on ARM based machines which use the chunked stack variant
of the ARM procedure call standard. The solution there is to always
keep one chunk in reserve - when you move back out of a chunk you don't
free it. Instead you wait until you move back another chunk and then
free the chunk after the one that has just emptied.

Even this can go wrong if your loop pushes more that one chunks worth
of data on the stack and then pops it again, but that is far rarer than
the general case of pushing one or two items which happens to take it
over a chunk boundary.

The attached patch implements this one behind logic, both for the
generic stack and the integer stack. If nobody has any objections
then I'll commit it tomorrow sometime.

Some figures from my test programs, running on a K6-200 linux box. The
test programs push and pop 65536 times with the first column being when
that loop doesn't cross a chunk boundary and the second being when it
does cross a chunk boundary:

                                  No overflow     Overflow
  Integer stack, before patch      0.065505s     16.589480s
  Integer stack, after patch       0.062732s      0.068460s
  Generic stack, before patch      0.161202s      5.475367s
  Generic stack, after patch       0.166938s      0.168390s

Tom

-- 
Tom Hughes (tom@compton.nu)
http://www.compton.nu/

• Stack performance issue by Tom Hughes
• Re: Stack performance issue by mrjoltcola
• Re: Stack performance issue by Melvin Smith
• Re: Stack performance issue by Tom Hughes
• Re: Stack performance issue by Dan Sugalski