I've stripped down the whole stack code to use one item per chunk. It
passes all tests (3 disabled that push infintely and check for
CHECK_LIMIT and t/pmc/eval_6 which is borken).
This slows down register saving (and other stack operations)
considerably whithout any additional measures[1]:
$ perl tools/dev/parrotbench.pl -c=parrotbench.conf -b='^oof' -t
Numbers are cpu times in seconds. (lower is better)
p-j-Oc parr-j parr-C perl-th perl python ruby
oofib 4.150s 11.530s 12.450s 4.100s 3.540s 2.140s 2.170s
p-j-Oc = parrot -j -Oc where savetop is optimized to pushtopp
parr-j = parrot -j, all 4 registers are saved (both unoptimized build)
[1] The old stack code used a next pointer to prevent stack thrashing.
This is of not much use for single items (and probably doesn't work with
Continuations), so I'm thinking of dedicated free_lists (again!) that
hold popped of stack items of one buffer size kind. They'll be kept
alive by marking them during DOD. If we cannot do this, I see not much
chance to gain old subroutine call performance.
Here is the diffstat of the patch:
classes/closure.pmc | 3
classes/coroutine.pmc | 2
imcc/pcc.c | 8 +-
include/parrot/stacks.h | 13 ---
src/debug.c | 16 +---
src/register.c | 46 +++++-------
src/stack_common.c | 142 ++++----------------------------------
src/stacks.c | 57 ++++++---------
src/sub.c | 18 +---
t/op/stacks.t | 4 -
t/pmc/eval.t | 4 +
11 files changed, 86 insertions(+), 227 deletions(-)
TODOS: cleanup, POD, debug.c stack commands.
leo
[
stack-items.patch 19K ]
--- parrot/classes/closure.pmc Sun Feb 22 19:54:30 2004
+++ parrot-leo/classes/closure.pmc Tue Mar 23 10:21:04 2004
@@ -89,8 +89,7 @@
struct Parrot_Sub * sub;
PMC* ret = SUPER();
sub = PMC_sub(ret);
- sub->ctx.pad_stack = stack_copy(interpreter,
- PMC_sub(SELF)->ctx.pad_stack);
+ sub->ctx.pad_stack = PMC_sub(SELF)->ctx.pad_stack;
return ret;
}
--- parrot/classes/coroutine.pmc Sun Feb 22 19:54:30 2004
+++ parrot-leo/classes/coroutine.pmc Tue Mar 23 12:08:35 2004
@@ -73,7 +73,7 @@
void mark () {
struct Parrot_Coroutine *c = (struct Parrot_Coroutine *)PMC_sub(SELF);
mark_stack(INTERP, c->co_control_stack);
- mark_stack(INTERP, c->co_pad_stack);
+ /* mark_stack(INTERP, c->co_pad_stack); */
SUPER(); /* mark rest */
}
}
--- parrot/imcc/pcc.c Mon Mar 22 17:43:49 2004
+++ parrot-leo/imcc/pcc.c Tue Mar 23 12:01:06 2004
@@ -935,16 +935,16 @@
ins = set_I_const(interp, unit, ins, 4, 0);
#endif
/*
+ * emit a savetop for now
+ */
+ ins = insINS(interp, unit, ins, "savetop", regs, 0);
+ /*
* if we reuse the continuation, update it
*/
if (!sub->pcc_sub->nci)
if (!need_cc)
ins = insINS(interp, unit, ins, "updatecc", regs, 0);
- /*
- * emit a savetop for now
- */
/* restore self */
- ins = insINS(interp, unit, ins, "savetop", regs, 0);
if (meth_call) {
regs[0] = s0;
n = 0;
--- parrot/include/parrot/stacks.h Sat Feb 21 19:10:24 2004
+++ parrot-leo/include/parrot/stacks.h Tue Mar 23 10:22:28 2004
@@ -15,8 +15,7 @@
#include "parrot/parrot.h"
-#define STACK_CHUNK_DEPTH 256
-#define STACK_CHUNK_LIMIT 1000
+#define STACK_CHUNK_LIMIT 100000
typedef struct Stack_Entry {
UnionVal entry;
@@ -26,13 +25,7 @@
typedef struct Stack_Chunk {
pobj_t obj;
- size_t used;
- int n_chunks;
- int chunk_limit;
- size_t item_size;
- size_t items_per_chunk;
const char * name;
- struct Stack_Chunk *next;
struct Stack_Chunk *prev;
} Stack_Chunk_t;
@@ -47,9 +40,7 @@
/*
* stack_common functions
*/
-Stack_Chunk_t * cst_new_stack(Parrot_Interp, const char *name, size_t, size_t);
-Stack_Chunk_t * stack_copy(Parrot_Interp, Stack_Chunk_t *stack);
-void stack_unmake_COW(Parrot_Interp, Stack_Chunk_t *stack);
+Stack_Chunk_t * cst_new_stack(Parrot_Interp, const char *name, size_t);
void* stack_prepare_push(Parrot_Interp, Stack_Chunk_t **stack_p);
void* stack_prepare_pop(Parrot_Interp, Stack_Chunk_t **stack_p);
--- parrot/src/debug.c Sat Mar 13 09:44:44 2004
+++ parrot-leo/src/debug.c Tue Mar 23 10:12:40 2004
@@ -2147,9 +2147,7 @@
unsigned long depth = 0, i = 0;
Stack_Chunk_t *chunk = interpreter->ctx.int_reg_stack;
- valid_chunk(chunk, command, depth,
- FRAMES_PER_INT_REG_CHUNK, i);
-
+ internal_exception(1, "TODO");
if (!chunk) {
i = depth / FRAMES_PER_INT_REG_CHUNK;
PIO_eprintf(interpreter, "There are only %li frames\n",i);
@@ -2182,9 +2180,7 @@
unsigned long depth = 0, i = 0;
Stack_Chunk_t *chunk = interpreter->ctx.num_reg_stack;
- valid_chunk(chunk, command, depth,
- FRAMES_PER_NUM_REG_CHUNK, i);
-
+ internal_exception(1, "TODO");
if (!chunk) {
i = depth / FRAMES_PER_NUM_REG_CHUNK;
PIO_eprintf(interpreter, "There are only %li frames\n",i);
@@ -2216,9 +2212,7 @@
unsigned long depth = 0, i = 0;
Stack_Chunk_t *chunk = interpreter->ctx.string_reg_stack;
- valid_chunk(chunk, command, depth,
- FRAMES_PER_STR_REG_CHUNK, i);
-
+ internal_exception(1, "TODO");
if (!chunk) {
i = depth / FRAMES_PER_STR_REG_CHUNK;
PIO_eprintf(interpreter, "There are only %li frames\n",i);
@@ -2251,9 +2245,7 @@
unsigned long depth = 0, i = 0;
Stack_Chunk_t *chunk = interpreter->ctx.pmc_reg_stack;
- valid_chunk(chunk, command, depth,
- FRAMES_PER_PMC_REG_CHUNK, i);
-
+ internal_exception(1, "TODO");
if (!chunk) {
i = depth / FRAMES_PER_PMC_REG_CHUNK;
PIO_eprintf(interpreter, "There are only %li frames\n",i);
--- parrot/src/register.c Sat Feb 21 20:15:11 2004
+++ parrot-leo/src/register.c Tue Mar 23 11:41:20 2004
@@ -20,6 +20,8 @@
=head2 C Implementation
+TODO update pod
+
As the registers and register frame stacks for the various types share
essentially the same structure we'll take as our example the integer
registers and their register frame stack.
@@ -76,16 +78,16 @@
setup_register_stacks(Parrot_Interp interpreter, struct Parrot_Context *ctx)
{
ctx->int_reg_stack = cst_new_stack(interpreter,
- "IntReg_", sizeof(struct IRegFrame), FRAMES_PER_CHUNK);
+ "IntReg_", sizeof(struct IRegFrame));
ctx->string_reg_stack = cst_new_stack(interpreter,
- "StringReg_", sizeof(struct SRegFrame), FRAMES_PER_CHUNK);
+ "StringReg_", sizeof(struct SRegFrame));
ctx->num_reg_stack = cst_new_stack(interpreter,
- "NumReg_", sizeof(struct NRegFrame), FRAMES_PER_CHUNK);
+ "NumReg_", sizeof(struct NRegFrame));
ctx->pmc_reg_stack = cst_new_stack(interpreter,
- "PMCReg_", sizeof(struct PRegFrame), FRAMES_PER_CHUNK);
+ "PMCReg_", sizeof(struct PRegFrame));
}
/*
@@ -102,11 +104,10 @@
void
mark_register_stack(Parrot_Interp interpreter, Stack_Chunk_t* chunk)
{
- /* go up to top */
- for (; chunk && chunk->prev; chunk = chunk->prev)
- ;
- for (; chunk; chunk = chunk->next) {
+ for (; ; chunk = chunk->prev) {
pobject_lives(interpreter, (PObj*)chunk);
+ if (chunk == chunk->prev)
+ break;
}
}
@@ -124,21 +125,20 @@
void
mark_pmc_register_stack(Parrot_Interp interpreter, Stack_Chunk_t* chunk)
{
- UINTVAL i, j;
- for (; chunk && chunk->prev; chunk = chunk->prev)
- ;
- for ( ; chunk; chunk = chunk->next) {
- struct PRegChunkBuf* pc = chunk->bufstart;
+ UINTVAL j;
+ for ( ; ; chunk = chunk->prev) {
+ struct PRegFrame *pf = chunk->bufstart;
+
pobject_lives(interpreter, (PObj*)chunk);
- for (i = 0; i < chunk->used; i++) {
- struct PRegFrame *pf = &pc->PRegFrame[i];
+ if (chunk == chunk->prev)
+ break;
+ /* TODO for variable sized chunks use buflen */
for (j = 0; j < NUM_REGISTERS/2; j++) {
PObj* reg = (PObj*) pf->registers[j];
if (reg)
pobject_lives(interpreter, reg);
}
}
- }
}
/*
@@ -155,19 +155,17 @@
void
mark_string_register_stack(Parrot_Interp interpreter, Stack_Chunk_t* chunk)
{
- UINTVAL i, j;
- for (; chunk && chunk->prev; chunk = chunk->prev)
- ;
- for ( ; chunk; chunk = chunk->next) {
- struct SRegChunkBuf* sc = chunk->bufstart;
+ UINTVAL j;
+ for ( ; ; chunk = chunk->prev) {
+ struct SRegFrame *sf = chunk->bufstart;
+
pobject_lives(interpreter, (PObj*)chunk);
- for (i = 0; i < chunk->used; i++) {
- struct SRegFrame *sf = &sc->SRegFrame[i];
+ if (chunk == chunk->prev)
+ break;
for (j = 0; j < NUM_REGISTERS/2; j++) {
PObj* reg = (PObj*) sf->registers[j];
if (reg)
pobject_lives(interpreter, reg);
- }
}
}
}
--- parrot/src/stack_common.c Sun Mar 21 16:46:50 2004
+++ parrot-leo/src/stack_common.c Tue Mar 23 11:23:29 2004
@@ -18,8 +18,7 @@
=over 4
=item C<Stack_Chunk_t *
-cst_new_stack(Interp *interpreter, const char *name, size_t item_size,
- size_t items_per_chunk)>
+cst_new_stack(Interp *interpreter, const char *name, size_t item_size)>
Create a new stack and name it. C<< stack->name >> is used for
debugging/error reporting.
@@ -32,94 +31,29 @@
#include <assert.h>
Stack_Chunk_t *
-cst_new_stack(Interp *interpreter, const char *name, size_t item_size,
- size_t items_per_chunk)
+cst_new_stack(Interp *interpreter, const char *name, size_t item_size)
{
Stack_Chunk_t *chunk = new_bufferlike_header(interpreter,
sizeof(Stack_Chunk_t));
- SET_NULL(chunk->next);
- SET_NULL(chunk->prev);
- chunk->n_chunks = 1;
- chunk->chunk_limit = STACK_CHUNK_LIMIT;
+ chunk->prev = chunk;
chunk->name = name;
- chunk->item_size = item_size;
- chunk->items_per_chunk = items_per_chunk;
- chunk->used = 0;
/* Block DOD from murdering our newly allocated stack buffer. */
Parrot_block_DOD(interpreter);
- Parrot_allocate(interpreter, (Buffer *)chunk, item_size * items_per_chunk);
+ Parrot_allocate(interpreter, (Buffer *)chunk, item_size);
Parrot_unblock_DOD(interpreter);
return chunk;
}
-/*
-
-=item C<Stack_Chunk_t *
-stack_copy(Parrot_Interp interpreter, Stack_Chunk_t *stack)>
-
-COW copy a stack. This is done by allocating a new stack buffer header,
-that points to possibly common next chunks and to common buffer memory.
-
-=cut
-
-*/
-
-Stack_Chunk_t *
-stack_copy(Parrot_Interp interpreter, Stack_Chunk_t *stack)
-{
- Stack_Chunk_t *chunk = new_bufferlike_header(interpreter,
- sizeof(Stack_Chunk_t));
- /*
- * the private0_FLAG indiciates, that we might share the
- * next stack_chunk too
- */
- PObj_get_FLAGS((Buffer *) stack) |=
- (PObj_COW_FLAG | PObj_private0_FLAG);
- /* just copy the header, all pointers are shared now */
- mem_sys_memcopy(chunk, stack, sizeof(*stack));
- return chunk;
-}
-
-/*
-
-=item C<void
-stack_unmake_COW(Parrot_Interp interpreter, Stack_Chunk_t *stack)>
-
-Make a COWed stack_chunk non-COWed.
-
-=cut
-
-*/
-
-void
-stack_unmake_COW(Parrot_Interp interpreter, Stack_Chunk_t *stack)
-{
- Buffer for_alloc;
- /*
- * allocate a dummy stacks memory
- * also be sure not to allocate from the constant pool
- */
- PObj_flags_CLEARALL(&for_alloc);
- Parrot_allocate(interpreter, &for_alloc, stack->buflen);
- /*
- * copy over used items data
- */
- mem_sys_memcopy(for_alloc.bufstart, stack->bufstart,
- stack->item_size * stack->items_per_chunk);
- stack->bufstart = for_alloc.bufstart;
- PObj_COW_CLEAR((Buffer*)stack);
-}
-
/*
=item C<void*
stack_prepare_push(Parrot_Interp interpreter, Stack_Chunk_t **stack_p)>
-Return a pointer, where new entries go for push. UnCOW if necessary
+Return a pointer, where new entries go for push.
=cut
@@ -129,43 +63,13 @@
stack_prepare_push(Parrot_Interp interpreter, Stack_Chunk_t **stack_p)
{
Stack_Chunk_t *chunk = *stack_p, *new_chunk;
- /*
- * before any change unCOW if necessary
- */
- if (PObj_COW_TEST((Buffer*)chunk))
- stack_unmake_COW(interpreter, chunk);
- /*
- * if this chunk is full, allocate a new one
- */
- if (chunk->used == chunk->items_per_chunk) {
- if (chunk->next == NULL) {
- new_chunk = cst_new_stack(interpreter, chunk->name,
- chunk->item_size, chunk->items_per_chunk);
- new_chunk->prev = chunk;
- chunk->next = new_chunk;
- new_chunk->n_chunks = chunk->n_chunks + 1;
- if (new_chunk->n_chunks == new_chunk->chunk_limit)
- internal_exception(1, "Stack '%s' too deep\n",
- chunk->name);
- *stack_p = chunk = new_chunk;
- }
- else {
- /*
- * we have a next chunk: this is either a spare chunk
- * kept during stack_pop to avoid thrashing or
- * a common next stack_chunk
- */
- if (PObj_get_FLAGS((Buffer*)chunk->next) & PObj_private0_FLAG) {
+
+ /* TODO check free list */
new_chunk = cst_new_stack(interpreter, chunk->name,
- chunk->item_size, chunk->items_per_chunk);
+ chunk->buflen);
new_chunk->prev = chunk;
- chunk->next = new_chunk;
- }
- *stack_p = chunk = chunk->next;
- assert(!PObj_COW_TEST( (Buffer *) chunk));
- }
- }
- return (char*) chunk->bufstart + chunk->used++ * chunk->item_size;
+ *stack_p = new_chunk;
+ return new_chunk->bufstart;
}
/*
@@ -173,7 +77,7 @@
=item C<void*
stack_prepare_pop(Parrot_Interp interpreter, Stack_Chunk_t **stack_p)>
-Return a pointer, where new entries are poped off. UnCOW if necessary.
+Return a pointer, where new entries are poped off.
=cut
@@ -184,29 +88,15 @@
{
Stack_Chunk_t *chunk = *stack_p;
/*
- * before any change unCOW if necessary
- */
- if (PObj_COW_TEST((Buffer*)chunk))
- stack_unmake_COW(interpreter, chunk);
- /*
- * if this chunk is empty go to previous if any
+ * go to previous if any
*/
- if (chunk->used == 0 && chunk->prev) {
- if (chunk->next) {
- /* GC will collect it */
- chunk->next = NULL;
- }
-
- /* Now back to the previous chunk - we'll keep the one we have
- * just emptied around for now in case we need it again. */
- *stack_p = chunk = chunk->prev;
- assert(!PObj_COW_TEST( (Buffer *) chunk));
- }
- if (chunk->used == 0) {
+ if (chunk == chunk->prev) {
internal_exception(ERROR_STACK_EMPTY, "No entries on %sStack!",
chunk->name);
}
- return (char*) chunk->bufstart + --chunk->used * chunk->item_size;
+ /* TODO put chunk on a free list */
+ *stack_p = chunk->prev;
+ return chunk->bufstart;
}
/*
--- parrot/src/stacks.c Thu Mar 4 13:08:54 2004
+++ parrot-leo/src/stacks.c Tue Mar 23 11:40:44 2004
@@ -8,6 +8,8 @@
=head1 DESCRIPTION
+TODO update pod
+
The stack is stored as a doubly-linked list of chunks (C<Stack_Chunk>),
where each chunk has room for C<STACK_CHUNK_DEPTH> entries. The
invariant maintained is that there is always room for another entry; if
@@ -75,8 +77,7 @@
new_stack(Interp *interpreter, const char *name)
{
- return cst_new_stack(interpreter, name,
- sizeof(Stack_Entry_t), STACK_CHUNK_DEPTH);
+ return cst_new_stack(interpreter, name, sizeof(Stack_Entry_t));
}
@@ -99,31 +100,29 @@
Stack_Entry_t *entry;
size_t i;
- for (; chunk && chunk->prev; chunk = chunk->prev)
- ;
- for (; chunk; chunk = chunk->next) {
+ for (; ; chunk = chunk->prev) {
pobject_lives(interpreter, (PObj *)chunk);
+ if (chunk == chunk->prev)
+ break;
entry = (Stack_Entry_t *)(chunk->bufstart);
- for (i = 0; i < chunk->used; i++) {
- switch (entry[i].entry_type) {
+ switch (entry->entry_type) {
case STACK_ENTRY_PMC:
- if (entry[i].entry.pmc_val) {
+ if (entry->entry.pmc_val) {
pobject_lives(interpreter,
- (PObj *)entry[i].entry.pmc_val);
+ (PObj *)entry->entry.pmc_val);
}
break;
case STACK_ENTRY_STRING:
- if (entry[i].entry.string_val) {
+ if (entry->entry.string_val) {
pobject_lives(interpreter,
- (PObj *)entry[i].entry.string_val);
+ (PObj *)entry->entry.string_val);
}
break;
default:
break;
}
}
- }
}
/*
@@ -154,15 +153,15 @@
*/
size_t
-stack_height(Interp *interpreter, Stack_Chunk_t *top)
+stack_height(Interp *interpreter, Stack_Chunk_t *chunk)
{
- Stack_Chunk_t *chunk;
- size_t height = top->used;
+ size_t height = 0;
- for (chunk = top->prev; chunk; chunk = chunk->prev)
- height += chunk->used;
- assert(height == (top->n_chunks - 1) * STACK_CHUNK_DEPTH +
- top->used);
+ for (; ; chunk = chunk->prev) {
+ if (chunk == chunk->prev)
+ break;
+ ++height;
+ }
return height;
}
@@ -197,16 +196,15 @@
offset = (size_t)depth;
}
chunk = stack; /* Start at top */
- while (chunk != NULL && offset >= chunk->used) {
- offset -= chunk->used;
+ while ( offset) {
+ if (chunk == chunk->prev)
+ break;
+ --offset;
chunk = chunk->prev;
}
- if (chunk == NULL)
+ if (chunk == chunk->prev)
return NULL;
- if (offset < chunk->used) {
- entry = (Stack_Entry_t *)PObj_bufstart(chunk) +
- chunk->used - offset - 1;
- }
+ entry = (Stack_Entry_t *)PObj_bufstart(chunk);
return entry;
}
@@ -235,13 +233,6 @@
if (num_entries >= -1 && num_entries <= 1) {
return;
- }
-
- /* If stack is copy-on-write, copy it before we can execute on it */
- if (PObj_COW_TEST( (Buffer *) stack)) {
- stack_unmake_COW(interpreter, stack);
- if (depth >= STACK_CHUNK_DEPTH)
- internal_exception(1, "Unhandled deep rotate for COWed stack");
}
--- parrot/src/sub.c Mon Mar 22 13:38:12 2004
+++ parrot-leo/src/sub.c Tue Mar 23 10:20:07 2004
@@ -57,16 +57,8 @@
cow_copy_context(struct Parrot_Interp *interp,
struct Parrot_Context *dest, struct Parrot_Context *src)
{
- dest->int_reg_stack = stack_copy(interp, src->int_reg_stack);
- dest->num_reg_stack = stack_copy(interp, src->num_reg_stack);
- dest->string_reg_stack = stack_copy(interp, src->string_reg_stack);
- dest->pmc_reg_stack = stack_copy(interp, src->pmc_reg_stack);
- dest->pad_stack = stack_copy(interp, src->pad_stack);
- dest->user_stack = stack_copy(interp, src->user_stack);
- dest->control_stack = stack_copy(interp, src->control_stack);
- dest->warns = src->warns;
- dest->errors = src->errors;
- buffer_mark_COW(dest->warns);
+ memcpy(dest, src, sizeof(*src));
+ buffer_mark_COW(dest->warns); /* XXX */
buffer_mark_COW(dest->errors);
}
@@ -159,7 +151,7 @@
return;
}
/* save current interp stack */
- *ctx_stack = stack_copy(interp, *interp_stack);
+ *ctx_stack = *interp_stack;
/* we push a mark on that stack, so if the coroutine pops
* beyond its own stack into the interpeter stack
* we can catch this
@@ -452,13 +444,13 @@
save_context(interp, ctx);
setup_register_stacks(interp, &interp->ctx);
/* put in a COWed copy of the user stack */
- ctx->user_stack = stack_copy(interp, interp->ctx.user_stack);
+ ctx->user_stack = interp->ctx.user_stack;
/* create new pad and control stacks,
* when invoking the coroutine the real stacks are
* constructed in swap_context
* XXX decide what to do with pad
*/
- ctx->pad_stack = stack_copy(interp, interp->ctx.pad_stack);
+ ctx->pad_stack = interp->ctx.pad_stack;
co->co_control_stack = new_stack(interp, "Control");
--- parrot/t/op/stacks.t Mon Mar 8 10:28:56 2004
+++ parrot-leo/t/op/stacks.t Tue Mar 23 11:24:37 2004
@@ -1341,6 +1341,8 @@
ok 8
OUTPUT
+SKIP: {
+ skip("no stack limit currently", 3);
output_is(<<CODE, <<'OUTPUT', "check limit - User");
lp:
save I0
@@ -1366,7 +1368,7 @@
CODE
Stack 'Control' too deep
OUTPUT
-
+}
##############################
# set integer registers to some value given by $code...
--- parrot/t/pmc/eval.t Mon Mar 8 10:29:00 2004
+++ parrot-leo/t/pmc/eval.t Tue Mar 23 12:14:02 2004
@@ -97,6 +97,9 @@
fin
OUTPUT
+SKIP: {
+ skip("wrong stack handling", 1);
+
output_is(<<'CODE', <<'OUTPUT', "nano forth sub");
_main:
load_bytecode "examples/assembly/nanoforth2.pasm"
@@ -126,3 +129,4 @@
6
11
OUTPUT
+}
