From 29341bbc6ca4be934e01b591b98bc01f0a93f57b Mon Sep 17 00:00:00 2001 From: andreas_kupries Date: Tue, 22 Jul 2008 21:41:10 +0000 Subject: * generic/tclBasic.c: Reworked the handling of bytecode literals * generic/tclCompile.c: for #280 to fix the abysmal performance * generic/tclCompile.h: for deep recursion, replaced the linear * generic/tclExecute.c: search through the whole stack with * generic/tclInt.h: another hashtable and simplified the data structure used by the compiler (array instead of hashtable). Incidentially this also fixes the memory leak reported via [Bug 2024937]. --- ChangeLog | 11 +++++ generic/tclBasic.c | 136 ++++++++++++++++++++++++++++++++++++++------------- generic/tclCompile.c | 43 ++++++++++------ generic/tclCompile.h | 11 ++--- generic/tclExecute.c | 6 ++- generic/tclInt.h | 20 +++++++- 6 files changed, 167 insertions(+), 60 deletions(-) diff --git a/ChangeLog b/ChangeLog index aeb8c8a..7b8e05b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,14 @@ +2008-07-22 Andreas Kupries + + * generic/tclBasic.c: Reworked the handling of bytecode literals + * generic/tclCompile.c: for #280 to fix the abysmal performance + * generic/tclCompile.h: for deep recursion, replaced the linear + * generic/tclExecute.c: search through the whole stack with + * generic/tclInt.h: another hashtable and simplified the data + structure used by the compiler (array instead of hashtable). + Incidentially this also fixes the memory leak reported via [Bug + 2024937]. + 2008-07-21 Don Porter * tests/encoding.test: Make failing tests pass again. [Bug 1972867] diff --git a/generic/tclBasic.c b/generic/tclBasic.c index 8c1fe40..f2e4fc6 100644 --- a/generic/tclBasic.c +++ b/generic/tclBasic.c @@ -14,7 +14,7 @@ * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. * - * RCS: @(#) $Id: tclBasic.c,v 1.295.2.1 2008/07/21 19:38:13 andreas_kupries Exp $ + * RCS: @(#) $Id: tclBasic.c,v 1.295.2.2 2008/07/22 21:41:11 andreas_kupries Exp $ */ #include "tclInt.h" @@ -445,9 +445,11 @@ Tcl_CreateInterp(void) iPtr->linePBodyPtr = (Tcl_HashTable *) ckalloc(sizeof(Tcl_HashTable)); iPtr->lineBCPtr = (Tcl_HashTable *) ckalloc(sizeof(Tcl_HashTable)); iPtr->lineLAPtr = (Tcl_HashTable*) ckalloc (sizeof (Tcl_HashTable)); + iPtr->lineLABCPtr = (Tcl_HashTable*) ckalloc (sizeof (Tcl_HashTable)); Tcl_InitHashTable(iPtr->linePBodyPtr, TCL_ONE_WORD_KEYS); Tcl_InitHashTable(iPtr->lineBCPtr, TCL_ONE_WORD_KEYS); Tcl_InitHashTable(iPtr->lineLAPtr, TCL_ONE_WORD_KEYS); + Tcl_InitHashTable(iPtr->lineLABCPtr, TCL_ONE_WORD_KEYS); iPtr->activeVarTracePtr = NULL; @@ -1433,6 +1435,19 @@ DeleteInterpProc( Tcl_DeleteHashTable (iPtr->lineLAPtr); ckfree((char*) iPtr->lineLAPtr); iPtr->lineLAPtr = NULL; + + if (iPtr->lineLABCPtr->numEntries) { + /* + * When the interp goes away we have nothing on the stack, so + * there are no arguments, so this table has to be empty. + */ + + Tcl_Panic ("Argument location tracking table not empty"); + } + + Tcl_DeleteHashTable (iPtr->lineLABCPtr); + ckfree((char*) iPtr->lineLABCPtr); + iPtr->lineLABCPtr = NULL; } Tcl_DeleteHashTable(&iPtr->varTraces); @@ -4586,6 +4601,80 @@ TclArgumentRelease(interp,objv,objc) } } +void +TclArgumentBCEnter(interp,codePtr,cfPtr) + Tcl_Interp* interp; + void* codePtr; + CmdFrame* cfPtr; +{ + Interp* iPtr = (Interp*) interp; + Tcl_HashEntry* hePtr = Tcl_FindHashEntry (iPtr->lineBCPtr, (char *) codePtr); + + if (hePtr) { + ExtCmdLoc* eclPtr = (ExtCmdLoc*) Tcl_GetHashValue (hePtr); + int i; + + for (i=0; i < eclPtr->nueiloc; i++) { + + ExtIndex* eiPtr = &eclPtr->eiloc[i]; + Tcl_Obj* obj = eiPtr->obj; + int new; + Tcl_HashEntry* hPtr; + CFWordBC* cfwPtr; + + hPtr = Tcl_CreateHashEntry (iPtr->lineLABCPtr, (char*) obj, &new); + if (new) { + /* + * The word is not on the stack yet, remember the current location + * and initialize references. + */ + cfwPtr = (CFWordBC*) ckalloc (sizeof (CFWordBC)); + cfwPtr->framePtr = cfPtr; + cfwPtr->eiPtr = eiPtr; + cfwPtr->refCount = 1; + Tcl_SetHashValue (hPtr, cfwPtr); + } else { + /* + * The word is already on the stack, its current location is not + * relevant. Just remember the reference to prevent early removal. + */ + cfwPtr = (CFWordBC*) Tcl_GetHashValue (hPtr); + cfwPtr->refCount ++; + } + } /* for */ + } /* if */ +} + +void +TclArgumentBCRelease(interp,codePtr) + Tcl_Interp* interp; + void* codePtr; +{ + Interp* iPtr = (Interp*) interp; + Tcl_HashEntry* hePtr = Tcl_FindHashEntry (iPtr->lineBCPtr, (char *) codePtr); + + if (hePtr) { + ExtCmdLoc* eclPtr = (ExtCmdLoc*) Tcl_GetHashValue (hePtr); + int i; + + for (i=0; i < eclPtr->nueiloc; i++) { + Tcl_Obj* obj = eclPtr->eiloc[i].obj; + Tcl_HashEntry* hPtr = Tcl_FindHashEntry (iPtr->lineLABCPtr, (char *) obj); + CFWordBC* cfwPtr; + + if (!hPtr) { continue; } + + cfwPtr = (CFWordBC*) Tcl_GetHashValue (hPtr); + + cfwPtr->refCount --; + if (cfwPtr->refCount > 0) { continue; } + + ckfree ((char*) cfwPtr); + Tcl_DeleteHashEntry (hPtr); + } /* for */ + } /* if */ +} + /* *---------------------------------------------------------------------- * @@ -4629,43 +4718,20 @@ TclArgumentGet(interp,obj,cfPtrPtr,wordPtr) } /* - * Check if the Tcl_Obj has location information as a bytecode literal. We - * have to scan the stack up and check all bytecode frames for a possible - * definition. + * Check if the Tcl_Obj has location information as a bytecode literal, in + * that stack. */ - for (framePtr = iPtr->cmdFramePtr; - framePtr; - framePtr = framePtr->nextPtr) { - const ByteCode* codePtr; - Tcl_HashEntry* hePtr; - - if (framePtr->type != TCL_LOCATION_BC) continue; - - codePtr = framePtr->data.tebc.codePtr; - hePtr = Tcl_FindHashEntry (iPtr->lineBCPtr, (char *) codePtr); - - if (hePtr) { - ExtCmdLoc* eclPtr = (ExtCmdLoc*) Tcl_GetHashValue (hePtr); - Tcl_HashEntry *hlPtr = Tcl_FindHashEntry (&eclPtr->litIndex, (char *) obj); - - if (hlPtr) { - /* - * Convert from the current invoker CmdFrame to a CmdFrame - * refering to the actual word location. We are directly - * manipulating the relevant command frame in the frame stack. - * That is no problem because TEBC is already setting the pc - * for each invokation, so moving it somewhere will not affect - * the following commands. - */ - - ExtIndex* eiPtr = (ExtIndex*) Tcl_GetHashValue (hlPtr); + hPtr = Tcl_FindHashEntry (iPtr->lineLABCPtr, (char *) obj); + if (hPtr) { + CFWordBC* cfwPtr = (CFWordBC*) Tcl_GetHashValue (hPtr); + ExtIndex* eiPtr = cfwPtr->eiPtr; - framePtr->data.tebc.pc = codePtr->codeStart + eiPtr->pc; - *cfPtrPtr = framePtr; - *wordPtr = eiPtr->word; - } - } + framePtr = cfwPtr->framePtr; + framePtr->data.tebc.pc = ((ByteCode*) framePtr->data.tebc.codePtr)->codeStart + eiPtr->pc; + *cfPtrPtr = cfwPtr->framePtr; + *wordPtr = eiPtr->word; + return; } } diff --git a/generic/tclCompile.c b/generic/tclCompile.c index 145a7b9..19011d9 100644 --- a/generic/tclCompile.c +++ b/generic/tclCompile.c @@ -11,7 +11,7 @@ * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. * - * RCS: @(#) $Id: tclCompile.c,v 1.146.2.2 2008/07/21 19:38:17 andreas_kupries Exp $ + * RCS: @(#) $Id: tclCompile.c,v 1.146.2.3 2008/07/22 21:41:12 andreas_kupries Exp $ */ #include "tclInt.h" @@ -802,8 +802,6 @@ TclCleanupByteCode( if (hePtr) { ExtCmdLoc *eclPtr = Tcl_GetHashValue(hePtr); int i; - Tcl_HashSearch hSearch; - Tcl_HashEntry *hlPtr; if (eclPtr->type == TCL_LOCATION_SOURCE) { Tcl_DecrRefCount(eclPtr->path); @@ -817,14 +815,10 @@ TclCleanupByteCode( } /* Release index of literals as well. */ - for (hlPtr = Tcl_FirstHashEntry(&eclPtr->litIndex, &hSearch); - hlPtr != NULL; - hlPtr = Tcl_NextHashEntry(&hSearch)) { - ExtIndex* eiPtr = (ExtIndex*) Tcl_GetHashValue (hlPtr); - ckfree((char*) eiPtr); - Tcl_DeleteHashEntry (hlPtr); + if (eclPtr->eiloc != NULL) { + ckfree((char *) eclPtr->eiloc); } - Tcl_DeleteHashTable (&eclPtr->litIndex); + ckfree((char *) eclPtr); Tcl_DeleteHashEntry(hePtr); } @@ -914,7 +908,9 @@ TclInitCompileEnv( envPtr->extCmdMapPtr->nloc = 0; envPtr->extCmdMapPtr->nuloc = 0; envPtr->extCmdMapPtr->path = NULL; - Tcl_InitHashTable(&envPtr->extCmdMapPtr->litIndex, TCL_ONE_WORD_KEYS); + envPtr->extCmdMapPtr->eiloc = NULL; + envPtr->extCmdMapPtr->neiloc = 0; + envPtr->extCmdMapPtr->nueiloc = 0; if (invoker == NULL) { /* @@ -2446,15 +2442,30 @@ TclEnterCmdWordIndex (eclPtr, obj, pc, word) int pc; int word; { - int new; - ExtIndex* eiPtr = (ExtIndex*) ckalloc (sizeof (ExtIndex)); + ExtIndex* eiPtr; + + if (eclPtr->nueiloc >= eclPtr->neiloc) { + /* + * Expand the ExtIndex array by allocating more storage from the heap. The + * currently allocated ECL entries are stored from eclPtr->loc[0] up + * to eclPtr->loc[eclPtr->nuloc-1] (inclusive). + */ + + size_t currElems = eclPtr->neiloc; + size_t newElems = (currElems ? 2*currElems : 1); + size_t newBytes = newElems * sizeof(ExtIndex); + + eclPtr->eiloc = (ExtIndex *) ckrealloc((char *)(eclPtr->eiloc), newBytes); + eclPtr->neiloc = newElems; + } + + eiPtr = &eclPtr->eiloc[eclPtr->nueiloc]; + eiPtr->obj = obj; eiPtr->pc = pc; eiPtr->word = word; - Tcl_SetHashValue (Tcl_CreateHashEntry (&eclPtr->litIndex, - (char*) obj, &new), - eiPtr); + eclPtr->nueiloc ++; } /* diff --git a/generic/tclCompile.h b/generic/tclCompile.h index f1be02c..e5ef895 100644 --- a/generic/tclCompile.h +++ b/generic/tclCompile.h @@ -9,7 +9,7 @@ * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. * - * RCS: @(#) $Id: tclCompile.h,v 1.90.2.1 2008/07/21 19:38:18 andreas_kupries Exp $ + * RCS: @(#) $Id: tclCompile.h,v 1.90.2.2 2008/07/22 21:41:12 andreas_kupries Exp $ */ #ifndef _TCLCOMPILATION @@ -141,14 +141,11 @@ typedef struct ExtCmdLoc { ECL *loc; /* Command word locations (lines). */ int nloc; /* Number of allocated entries in 'loc'. */ int nuloc; /* Number of used entries in 'loc'. */ - Tcl_HashTable litIndex; /* HashValue is ExtIndex* */ + ExtIndex* eiloc; + int neiloc; + int nueiloc; } ExtCmdLoc; -typedef struct ExtIndex { - int pc; /* Instruction pointer of a command in ExtCmdLoc.loc[.] */ - int word; /* Index of word in ExtCmdLoc.loc[cmd]->line[.] */ -} ExtIndex; - EXTERN void TclEnterCmdWordIndex (ExtCmdLoc *eclPtr, Tcl_Obj* obj, int pc, int word); diff --git a/generic/tclExecute.c b/generic/tclExecute.c index 0003fb2..7866a7c 100644 --- a/generic/tclExecute.c +++ b/generic/tclExecute.c @@ -13,7 +13,7 @@ * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. * - * RCS: @(#) $Id: tclExecute.c,v 1.369.2.1 2008/04/08 16:12:02 dgp Exp $ + * RCS: @(#) $Id: tclExecute.c,v 1.369.2.2 2008/07/22 21:41:13 andreas_kupries Exp $ */ #include "tclInt.h" @@ -1753,6 +1753,8 @@ TclExecuteByteCode( bcFramePtr->cmd.str.cmd = NULL; bcFramePtr->cmd.str.len = 0; + TclArgumentBCEnter((Tcl_Interp*) iPtr,codePtr,bcFramePtr); + #ifdef TCL_COMPILE_DEBUG if (tclTraceExec >= 2) { PrintByteCodeInfo(codePtr); @@ -7389,6 +7391,8 @@ TclExecuteByteCode( } } + TclArgumentBCRelease((Tcl_Interp*) iPtr,codePtr); + /* * Restore the stack to the state it had previous to this bytecode. */ diff --git a/generic/tclInt.h b/generic/tclInt.h index e0e65e4..bbbdf2f 100644 --- a/generic/tclInt.h +++ b/generic/tclInt.h @@ -13,7 +13,7 @@ * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. * - * RCS: @(#) $Id: tclInt.h,v 1.362.2.2 2008/07/21 19:38:18 andreas_kupries Exp $ + * RCS: @(#) $Id: tclInt.h,v 1.362.2.3 2008/07/22 21:41:13 andreas_kupries Exp $ */ #ifndef _TCLINT @@ -1147,6 +1147,19 @@ typedef struct CFWord { int refCount; /* #times the word is on the stack */ } CFWord; +typedef struct ExtIndex { + Tcl_Obj* obj; /* Reference to the word */ + int pc; /* Instruction pointer of a command in ExtCmdLoc.loc[.] */ + int word; /* Index of word in ExtCmdLoc.loc[cmd]->line[.] */ +} ExtIndex; + + +typedef struct CFWordBC { + CmdFrame* framePtr; /* CmdFrame to acess */ + ExtIndex* eiPtr; /* Word info: PC and index */ + int refCount; /* #times the word is on the stack */ +} CFWordBC; + /* * The following macros define the allowed values for the type field of the * CmdFrame structure above. Some of the values occur only in the extended @@ -1845,6 +1858,7 @@ typedef struct Interp { * body. It is keyed by the address of the * Proc structure for a procedure. The values * are "struct ExtCmdLoc*" (See tclCompile.h) */ + Tcl_HashTable* lineLABCPtr; Tcl_HashTable* lineLAPtr; /* This table remembers for each argument of a * command on the execution stack the index of * the argument in the command, and the @@ -2457,6 +2471,10 @@ MODULE_SCOPE void TclArgumentRelease(Tcl_Interp* interp, Tcl_Obj* objv[], int objc); MODULE_SCOPE void TclArgumentGet(Tcl_Interp* interp, Tcl_Obj* obj, CmdFrame** cfPtrPtr, int* wordPtr); +MODULE_SCOPE void TclArgumentBCEnter(Tcl_Interp* interp, + void* codePtr, CmdFrame* cfPtr); +MODULE_SCOPE void TclArgumentBCRelease(Tcl_Interp* interp, + void* codePtr); MODULE_SCOPE int TclArraySet(Tcl_Interp *interp, Tcl_Obj *arrayNameObj, Tcl_Obj *arrayElemObj); MODULE_SCOPE double TclBignumToDouble(mp_int *bignum); -- cgit v0.12