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:
+*/
