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 ([EMAIL PROTECTED])
http://www.compton.nu/
Index: rxstacks.c
===================================================================
RCS file: /cvs/public/parrot/rxstacks.c,v
retrieving revision 1.5
diff -u -r1.5 rxstacks.c
--- rxstacks.c 17 May 2002 21:38:20 -0000 1.5
+++ rxstacks.c 30 Jun 2002 17:42:02 -0000
@@ -46,13 +46,20 @@
/* Register the new entry */
if (++chunk->used == STACK_CHUNK_DEPTH) {
- /* Need to add a new chunk */
- IntStack_Chunk new_chunk = mem_allocate_aligned(sizeof(*new_chunk));
- new_chunk->used = 0;
- new_chunk->next = stack;
- new_chunk->prev = chunk;
- chunk->next = new_chunk;
- stack->prev = new_chunk;
+ if (chunk->next == stack) {
+ /* Need to add a new chunk */
+ IntStack_Chunk new_chunk = mem_allocate_aligned(sizeof(*new_chunk));
+ new_chunk->used = 0;
+ new_chunk->next = stack;
+ new_chunk->prev = chunk;
+ chunk->next = new_chunk;
+ stack->prev = new_chunk;
+ }
+ else {
+ /* Reuse the spare chunk we kept */
+ chunk = chunk->next;
+ stack->prev = chunk;
+ }
}
}
@@ -67,11 +74,17 @@
/* That chunk != stack check is just to allow the empty stack case
* to fall through to the following exception throwing code. */
- /* Need to pop off the last entry */
- stack->prev = chunk->prev;
- stack->prev->next = stack;
- /* Relying on GC feels dirty... */
- chunk = stack->prev;
+ /* If the chunk that has just become empty is not the last chunk
+ * on the stack then we make it the last chunk - the GC will clean
+ * up any chunks that are discarded by this operation. */
+ if (chunk->next != stack) {
+ chunk->next = stack;
+ }
+
+ /* Now back to the previous chunk - we'll keep the one we have
+ * just emptied around for now in case we need it again. */
+ chunk = chunk->prev;
+ stack->prev = chunk;
}
/* Quick sanity check */
Index: stacks.c
===================================================================
RCS file: /cvs/public/parrot/stacks.c,v
retrieving revision 1.34
diff -u -r1.34 stacks.c
--- stacks.c 25 Jun 2002 23:50:51 -0000 1.34
+++ stacks.c 30 Jun 2002 17:42:02 -0000
@@ -208,22 +208,29 @@
/* Do we need a new chunk? */
if (chunk->used == STACK_CHUNK_DEPTH) {
- /* Need to add a new chunk */
- Stack_Chunk_t *new_chunk = mem_allocate_aligned(sizeof(Stack_Chunk_t));
-
- new_chunk->used = 0;
- new_chunk->next = stack_base;
- new_chunk->prev = chunk;
- chunk->next = new_chunk;
- stack_base->prev = new_chunk;
- chunk = new_chunk;
-
- /* Need to initialize this pointer before the collector sees it */
- chunk->buffer = NULL;
- chunk->buffer = new_buffer_header(interpreter);
-
- Parrot_allocate(interpreter, chunk->buffer,
- sizeof(Stack_Entry_t) * STACK_CHUNK_DEPTH);
+ if (chunk->next == stack_base) {
+ /* Need to add a new chunk */
+ Stack_Chunk_t *new_chunk = mem_allocate_aligned(sizeof(Stack_Chunk_t));
+
+ new_chunk->used = 0;
+ new_chunk->next = stack_base;
+ new_chunk->prev = chunk;
+ chunk->next = new_chunk;
+ stack_base->prev = new_chunk;
+ chunk = new_chunk;
+
+ /* Need to initialize this pointer before the collector sees it */
+ chunk->buffer = NULL;
+ chunk->buffer = new_buffer_header(interpreter);
+
+ Parrot_allocate(interpreter, chunk->buffer,
+ sizeof(Stack_Entry_t) * STACK_CHUNK_DEPTH);
+ }
+ else {
+ /* Reuse the spare chunk we kept */
+ chunk = chunk->next;
+ stack_base->prev = chunk;
+ }
}
entry = (Stack_Entry_t *)(chunk->buffer->bufstart) + chunk->used;
@@ -286,11 +293,17 @@
/* That chunk != stack check is just to allow the empty stack case
* to fall through to the following exception throwing code. */
- /* Need to pop off the last entry */
- stack_base->prev = chunk->prev;
- stack_base->prev->next = stack_base;
- /* Relying on GC feels dirty... */
- chunk = stack_base->prev;
+ /* If the chunk that has just become empty is not the last chunk
+ * on the stack then we make it the last chunk - the GC will clean
+ * up any chunks that are discarded by this operation. */
+ if (chunk->next != stack_base) {
+ chunk->next = stack_base;
+ }
+
+ /* Now back to the previous chunk - we'll keep the one we have
+ * just emptied around for now in case we need it again. */
+ chunk = chunk->prev;
+ stack_base->prev = chunk;
}
/* Quick sanity check */
