The attached patch adds a new stack type that only handles INTVALs. These are much more efficient than generic stacks--on Win32 they shave a few ten-thousandths of a second off each run of the rx_popindex op, and take a full hundredth of a second off the benchmark. It also shows performance improvements on BSD. They also take up less memory. All tests pass on both platforms; one warning is removed (as a side effect of the modified interface for regex stacks) and no new ones are introduced.
--Brent Dax [EMAIL PROTECTED] Parrot Configure pumpking and regex hacker <obra> mmmm. hawt sysadmin chx0rs <lathos> This is sad. I know of *a* hawt sysamin chx0r. <obra> I know more than a few. <lathos> obra: There are two? Are you sure it's not the same one?
diff -ruN -x CVS parrot-cvs/parrot/MANIFEST parrot/parrot/MANIFEST --- parrot-cvs/parrot/MANIFEST Wed Jan 16 01:14:26 2002 +++ parrot/parrot/MANIFEST Tue Jan 15 18:03:52 2002 @@ -114,6 +114,8 @@ include/parrot/resources.h include/parrot/runops_cores.h include/parrot/rx.h +include/parrot/rxstacks.h +include/parrot/runops_cores.h include/parrot/stacks.h include/parrot/string.h include/parrot/trace.h @@ -193,6 +195,7 @@ runops_cores.c rx.c rx.ops +rxstacks.c stacks.c string.c t/harness diff -ruN -x CVS parrot-cvs/parrot/Makefile.in parrot/parrot/Makefile.in --- parrot-cvs/parrot/Makefile.in Wed Jan 16 01:14:26 2002 +++ parrot/parrot/Makefile.in Tue Jan 15 18:02:56 2002 @@ -63,7 +63,7 @@ $(INC)/global_setup.h $(INC)/vtable.h $(INC)/oplib/core_ops.h $(INC)/oplib/core_ops_prederef.h \ $(INC)/runops_cores.h $(INC)/trace.h \ $(INC)/pmc.h $(INC)/key.h $(INC)/resources.h $(INC)/platform.h \ -$(INC)/interp_guts.h ${jit_h} ${jit_struct_h} $(INC)/rx.h +$(INC)/interp_guts.h ${jit_h} ${jit_struct_h} $(INC)/rx.h $(INC)/rxstacks.h CLASS_O_FILES = classes/default$(O) classes/perlint$(O) classes/perlstring$(O) \ classes/perlnum$(O) classes/perlarray$(O) classes/perlundef$(O) \ @@ -79,7 +79,7 @@ INTERP_O_FILES = exceptions$(O) global_setup$(O) interpreter$(O) parrot$(O) register$(O) \ core_ops$(O) core_ops_prederef$(O) memory$(O) packfile$(O) stacks$(O) \ string$(O) encoding$(O) chartype$(O) runops_cores$(O) trace$(O) pmc$(O) key$(O) \ -platform$(O) ${jit_o} resources$(O) rx$(O) +platform$(O) ${jit_o} resources$(O) rx$(O) rxstacks$(O) O_FILES = $(INTERP_O_FILES) $(IO_O_FILES) $(CLASS_O_FILES) $(ENCODING_O_FILES) $(CHARTYPE_O_FILES) @@ -303,6 +303,8 @@ register$(O): $(H_FILES) rx$(O): $(H_FILES) + +rxstacks$(O): $(H_FILES) stacks$(O): $(H_FILES) diff -ruN -x CVS parrot-cvs/parrot/include/parrot/rx.h parrot/parrot/include/parrot/rx.h --- parrot-cvs/parrot/include/parrot/rx.h Wed Jan 16 01:14:26 2002 +++ parrot/parrot/include/parrot/rx.h Tue Jan 15 14:26:50 2002 @@ -1,7 +1,7 @@ /* rx.h * Copyright: (When this is determined...it will go here) * CVS Info - * $Id: rx.h,v 1.8 2002/01/15 22:13:39 brentdax Exp $ + * $Id: rx.h,v 1.7 2002/01/15 16:54:35 brentdax Exp $ * Overview: * Supporting file for the regular expression engine * Data Structure and Algorithms: @@ -16,6 +16,7 @@ #define PARROT_RX_H_GUARD #include "parrot/parrot.h" +#include "parrot/rxstacks.h" typedef struct bitmap_t { char *bmp; @@ -57,7 +58,7 @@ opcode_t *substfunc; - struct Stack_chunk_t* stack; + rxStack stack; } rxinfo; #if __cplusplus diff -ruN -x CVS parrot-cvs/parrot/include/parrot/rxstacks.h parrot/parrot/include/parrot/rxstacks.h --- parrot-cvs/parrot/include/parrot/rxstacks.h Wed Dec 31 16:00:00 1969 +++ parrot/parrot/include/parrot/rxstacks.h Tue Jan 15 14:30:16 2002 @@ -0,0 +1,55 @@ +/* stacks.h + * Copyright: (When this is determined...it will go here) + * CVS Info + * $Id$ + * Overview: + * Regex stack handling routines for Parrot + * Data Structure and Algorithms: + * History: + * Notes: + * References: + */ + +#if !defined(PARROT_RXSTACKS_H_GUARD) +#define PARROT_RXSTACKS_H_GUARD + +#include "parrot/parrot.h" + +#define STACK_CHUNK_DEPTH 256 + +typedef struct rxStack_entry_t { + INTVAL value; +}* rxStack_Entry; + +typedef struct rxStack_chunk_t { + INTVAL used; + struct rxStack_chunk_t *next; + struct rxStack_chunk_t *prev; + struct rxStack_entry_t entry[STACK_CHUNK_DEPTH]; +}* rxStack_Chunk; + +typedef rxStack_Chunk rxStack; + +rxStack +rxstack_new(struct Parrot_Interp *); + +INTVAL +rxstack_depth(struct Parrot_Interp *, rxStack); + +void +rxstack_push(struct Parrot_Interp *, rxStack, INTVAL); + +INTVAL +rxstack_pop(struct Parrot_Interp *, rxStack); + +#endif + +/* + * Local variables: + * c-indentation-style: bsd + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + * + * vim: expandtab shiftwidth=4: +*/ diff -ruN -x CVS parrot-cvs/parrot/rx.c parrot/parrot/rx.c --- parrot-cvs/parrot/rx.c Wed Jan 16 01:14:26 2002 +++ parrot/parrot/rx.c Tue Jan 15 17:57:12 2002 @@ -37,7 +37,7 @@ rx->groupstart=pmc_new(interpreter, enum_class_PerlArray); rx->groupend=pmc_new(interpreter, enum_class_PerlArray); - rx->stack = new_stack(interpreter); + rx->stack = rxstack_new(interpreter); string_transcode(interpreter, rx->string, encoding_lookup("utf32"), rx->string->type, &rx->string); @@ -75,18 +75,6 @@ return bitmap_match(bmp, ch); } -STRING *rxP_get_substr(struct Parrot_Interp *interpreter, STRING * source, INTVAL startindex, INTVAL length) { - STRING *ret; - - /*printf("rxP_get_substr(%p, %p(%d), %d, %d)", interpreter, source, -1, startindex, length);*/ - - ret=string_make(interpreter, NULL, 0, NULL, 0, NULL); - - string_substr(interpreter, source, startindex, length, &ret); - - return ret; -} - Bitmap bitmap_make(struct Parrot_Interp *interpreter, STRING* str) { UINTVAL i, ch; Bitmap bmp=mem_sys_allocate(sizeof(struct bitmap_t)); @@ -98,7 +86,7 @@ } for(i=0; i < string_length(str); i++) { - ch=string_ord(str, i); + ch=string_ord(str, (INTVAL)i); if(ch > 255) { bmp->bigchars=string_concat(interpreter, bmp->bigchars, string_make(interpreter, (void*)&ch, 1, 0, 0, 0), 0); @@ -145,7 +133,7 @@ UINTVAL i; for(i=0; i < string_length(bmp->bigchars); i++) { - if(string_ord(bmp->bigchars, i) == ch) { + if(string_ord(bmp->bigchars, (INTVAL)i) == ch) { return 1; } } diff -ruN -x CVS parrot-cvs/parrot/rx.ops parrot/parrot/rx.ops --- parrot-cvs/parrot/rx.ops Wed Jan 16 01:14:26 2002 +++ parrot/parrot/rx.ops Tue Jan 15 14:23:56 2002 @@ -225,8 +225,8 @@ rx->minlength=0; rx->whichway=enum_rxdirection_forwards; - while(stack_depth(interpreter, rx->stack)) { - stack_pop(interpreter, rx->stack, NULL, STACK_ENTRY_INT); + while(rxstack_depth(interpreter, rx->stack)) { + rxstack_pop(interpreter, rx->stack); } rx->string=$2; @@ -271,10 +271,10 @@ rxinfo *rx2; RX_dUNPACK($1); - rx2=rx_allocate_info(interpreter, rx->string); + rx2=mem_sys_allocate(sizeof(rxinfo)); *rx2=*rx; - rx2->stack=new_stack(interpreter); + rx2->stack=rxstack_new(interpreter); $1=pmc_new(interpreter, enum_class_ParrotPointer); $1->data=rx2; @@ -401,7 +401,7 @@ op rx_pushindex(in pmc) { RX_dUNPACK($1); - stack_push(interpreter, rx->stack, &rx->index, STACK_ENTRY_INT, NULL); + rxstack_push(interpreter, rx->stack, rx->index); goto NEXT(); } @@ -418,7 +418,7 @@ op rx_pushmark(in pmc) { RX_dUNPACK($1); - stack_push(interpreter, rx->stack, (void *)&RX_MARK, STACK_ENTRY_INT, NULL); + rxstack_push(interpreter, rx->stack, RX_MARK); goto NEXT(); } @@ -436,7 +436,7 @@ RX_dUNPACK($1); INTVAL i; - stack_pop(interpreter, rx->stack, &i, STACK_ENTRY_INT); + i=rxstack_pop(interpreter, rx->stack); if(i==RX_MARK) { goto OFFSET($2); @@ -527,8 +527,8 @@ rx->index=rx->startindex; - while(stack_depth(interpreter, rx->stack)) { - stack_pop(interpreter, rx->stack, NULL, STACK_ENTRY_INT); + while(rxstack_depth(interpreter, rx->stack)) { + rxstack_pop(interpreter, rx->stack); } goto NEXT(); diff -ruN -x CVS parrot-cvs/parrot/rxstacks.c parrot/parrot/rxstacks.c --- parrot-cvs/parrot/rxstacks.c Wed Dec 31 16:00:00 1969 +++ parrot/parrot/rxstacks.c Tue Jan 15 14:31:20 2002 @@ -0,0 +1,102 @@ +/* rxstacks.c + * Copyright: (When this is determined...it will go here) + * CVS Info + * $Id$ + * Overview: + * Regex stack handling routines for Parrot + * Data Structure and Algorithms: + * Same as regular stacks, except they store only INTVALs and don't have + * cleanup routines. + * History: + * Notes: + * References: */ + +#include <assert.h> +#include "parrot/parrot.h" +#include "parrot/rxstacks.h" + +#define STACK_CHUNK_BASE(x) (void *)(MASK_STACK_CHUNK_LOW_BITS & (ptrcast_t)x) + +rxStack +rxstack_new(struct Parrot_Interp *interpreter) +{ + rxStack stack=mem_allocate_aligned(sizeof(struct rxStack_chunk_t)); + stack->used=0; + stack->next=stack; + stack->prev=stack; + return stack; +} + +INTVAL +rxstack_depth(struct Parrot_Interp *interpreter, rxStack stack) +{ + rxStack_Chunk chunk; + INTVAL depth = stack->used; + + for (chunk = stack->next; chunk != stack; chunk = chunk->next) + depth += chunk->used; + + return depth; +} + +void +rxstack_push(struct Parrot_Interp *interpreter, rxStack stack, INTVAL data) +{ + rxStack_Chunk chunk = stack->prev; + rxStack_Entry entry = &chunk->entry[chunk->used]; + + entry->value = data; + + /* Register the new entry */ + if (++chunk->used == STACK_CHUNK_DEPTH) { + /* Need to add a new chunk */ + rxStack_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; + } +} + +INTVAL +rxstack_pop(struct Parrot_Interp *interpreter, rxStack stack) +{ + rxStack_Chunk chunk = stack->prev; + rxStack_Entry entry; + + /* We may have an empty chunk at the end of the list */ + if (chunk->used == 0 && chunk != stack) { + /* 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; + } + + /* Quick sanity check */ + if (chunk->used == 0) { + INTERNAL_EXCEPTION(ERROR_STACK_EMPTY, "No entries on stack!\n"); + } + + entry = &chunk->entry[chunk->used - 1]; + + /* Now decrement the SP */ + chunk->used--; + + /* Snag the value */ + return entry->value; +} + +/* + * Local variables: + * c-indentation-style: bsd + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + * + * vim: expandtab shiftwidth=4: +*/