From 8b17d6bd89cd79820c76bd88bc064e44fc03a1bd Mon Sep 17 00:00:00 2001 From: Guido van Rossum Date: Tue, 30 Mar 1993 13:18:41 +0000 Subject: Changes to speed up local variables enormously, by avoiding dictionary lookup (opcode.h, ceval.[ch], compile.c, frameobject.[ch], pythonrun.c, import.c). The .pyc MAGIC number is changed again. Added get_menu_text to flmodule. --- Include/ceval.h | 1 + Include/frameobject.h | 2 + Include/opcode.h | 14 +++--- Modules/flmodule.c | 9 ++++ Objects/frameobject.c | 6 +++ Python/ceval.c | 136 ++++++++++++++++++++++++++++++++++++++++++++++---- Python/compile.c | 135 +++++++++++++++++++++++++++++++------------------ Python/import.c | 2 +- Python/pythonrun.c | 11 +++- 9 files changed, 245 insertions(+), 71 deletions(-) diff --git a/Include/ceval.h b/Include/ceval.h index bec6681..a9f79b5 100644 --- a/Include/ceval.h +++ b/Include/ceval.h @@ -28,6 +28,7 @@ object *call_object PROTO((object *, object *)); object *getglobals PROTO((void)); object *getlocals PROTO((void)); +void mergelocals PROTO((void)); void printtraceback PROTO((object *)); void flushline PROTO((void)); diff --git a/Include/frameobject.h b/Include/frameobject.h index 4d17267..d46b454 100644 --- a/Include/frameobject.h +++ b/Include/frameobject.h @@ -36,6 +36,8 @@ typedef struct _frame { codeobject *f_code; /* code segment */ object *f_globals; /* global symbol table (dictobject) */ object *f_locals; /* local symbol table (dictobject) */ + object *f_fastlocals; /* fast local variables (listobject) */ + object *f_localmap; /* local variable names (dictobject) */ object **f_valuestack; /* malloc'ed array */ block *f_blockstack; /* malloc'ed array */ int f_nvalues; /* size of f_valuestack */ diff --git a/Include/opcode.h b/Include/opcode.h index 67c0b82..0f08760 100644 --- a/Include/opcode.h +++ b/Include/opcode.h @@ -72,10 +72,7 @@ OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. #define RAISE_EXCEPTION 81 #define LOAD_LOCALS 82 #define RETURN_VALUE 83 -/* -#define REQUIRE_ARGS 84 -#define REFUSE_ARGS 85 -*/ + #define BUILD_FUNCTION 86 #define POP_BLOCK 87 #define END_FINALLY 88 @@ -113,14 +110,15 @@ OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. #define LOAD_LOCAL 115 /* Index in name list */ #define LOAD_GLOBAL 116 /* Index in name list */ -#define LOAD_FAST 117 /* Local variable number */ -#define STORE_FAST 118 /* Local variable number */ -#define RESERVE_FAST 119 /* Number of local variables */ - #define SETUP_LOOP 120 /* Target address (absolute) */ #define SETUP_EXCEPT 121 /* "" */ #define SETUP_FINALLY 122 /* "" */ +#define RESERVE_FAST 123 /* Number of local variables */ +#define LOAD_FAST 124 /* Local variable number */ +#define STORE_FAST 125 /* Local variable number */ +#define DELETE_FAST 126 /* Local variable number */ + #define SET_LINENO 127 /* Current line number */ /* Comparison operator codes (argument to COMPARE_OP) */ diff --git a/Modules/flmodule.c b/Modules/flmodule.c index 00cf12c..3d424d1 100644 --- a/Modules/flmodule.c +++ b/Modules/flmodule.c @@ -1201,6 +1201,14 @@ get_menu (g, args) } static object * +get_menu_text (g, args) + genericobject *g; + object *args; +{ + return call_forms_Rstr (fl_get_menu_text, g-> ob_generic, args); +} + +static object * addto_menu (g, args) genericobject *g; object *args; @@ -1211,6 +1219,7 @@ addto_menu (g, args) static struct methodlist menu_methods[] = { {"set_menu", set_menu}, {"get_menu", get_menu}, + {"get_menu_text", get_menu_text}, {"addto_menu", addto_menu}, {NULL, NULL} /* sentinel */ }; diff --git a/Objects/frameobject.c b/Objects/frameobject.c index cec0502..85c89f6 100644 --- a/Objects/frameobject.c +++ b/Objects/frameobject.c @@ -38,6 +38,8 @@ static struct memberlist frame_memberlist[] = { {"f_code", T_OBJECT, OFF(f_code)}, {"f_globals", T_OBJECT, OFF(f_globals)}, {"f_locals", T_OBJECT, OFF(f_locals)}, + {"f_fastlocals",T_OBJECT, OFF(f_fastlocals)}, + {"f_localmap", T_OBJECT, OFF(f_localmap)}, {"f_lasti", T_INT, OFF(f_lasti)}, {"f_lineno", T_INT, OFF(f_lineno)}, {NULL} /* Sentinel */ @@ -82,6 +84,8 @@ frame_dealloc(f) XDECREF(f->f_code); XDECREF(f->f_globals); XDECREF(f->f_locals); + XDECREF(f->f_fastlocals); + XDECREF(f->f_localmap); f->f_back = free_list; free_list = f; } @@ -142,6 +146,8 @@ newframeobject(back, code, globals, locals, nvalues, nblocks) f->f_globals = globals; INCREF(locals); f->f_locals = locals; + f->f_fastlocals = NULL; + f->f_localmap = NULL; if (nvalues > f->f_nvalues || f->f_valuestack == NULL) { XDEL(f->f_valuestack); f->f_valuestack = NEW(object *, nvalues+1); diff --git a/Python/ceval.c b/Python/ceval.c index 64f2429..45d0a6a 100644 --- a/Python/ceval.c +++ b/Python/ceval.c @@ -81,6 +81,7 @@ static int cmp_member PROTO((object *, object *)); static object *cmp_outcome PROTO((int, object *, object *)); static int import_from PROTO((object *, object *, object *)); static object *build_class PROTO((object *, object *)); +static void locals_2_fast PROTO((frameobject *, int)); /* Pointer to current frame, used to link new frames to */ @@ -994,19 +995,51 @@ eval_code(co, globals, locals, arg) break; case RESERVE_FAST: - if (oparg > 0) { - XDECREF(fastlocals); - x = newlistobject(oparg); - fastlocals = (listobject *) x; + x = GETCONST(oparg); + if (x == None) + break; + if (x == NULL || !is_dictobject(x)) { + fatal("bad RESERVE_FAST"); + err_setstr(SystemError, "bad RESERVE_FAST"); + x = NULL; + break; } + XDECREF(f->f_fastlocals); + XDECREF(f->f_localmap); + INCREF(x); + f->f_localmap = x; + f->f_fastlocals = x = newlistobject( + x->ob_type->tp_as_mapping->mp_length(x)); + fastlocals = (listobject *) x; break; case LOAD_FAST: - /* NYI */ + x = GETLISTITEM(fastlocals, oparg); + if (x == NULL) { + err_setstr(NameError, + "undefined local variable"); + break; + } + INCREF(x); + PUSH(x); break; case STORE_FAST: - /* NYI */ + w = GETLISTITEM(fastlocals, oparg); + XDECREF(w); + w = POP(); + GETLISTITEM(fastlocals, oparg) = w; + break; + + case DELETE_FAST: + x = GETLISTITEM(fastlocals, oparg); + if (x == NULL) { + err_setstr(NameError, + "undefined local variable"); + break; + } + DECREF(x); + GETLISTITEM(fastlocals, oparg) = NULL; break; case BUILD_TUPLE: @@ -1068,6 +1101,7 @@ eval_code(co, globals, locals, arg) w = GETNAMEV(oparg); v = TOP(); err = import_from(f->f_locals, v, w); + locals_2_fast(f, 0); break; case JUMP_FORWARD: @@ -1299,8 +1333,6 @@ eval_code(co, globals, locals, arg) current_frame = f->f_back; DECREF(f); - - XDECREF(fastlocals); return retval; } @@ -1418,10 +1450,92 @@ call_trace(p_trace, p_newtrace, f, msg, arg) object * getlocals() { - if (current_frame == NULL) + /* Merge f->f_fastlocals into f->f_locals, then return the latter */ + frameobject *f; + object *locals, *fast, *map; + int i; + f = current_frame; + if (f == NULL) return NULL; - else - return current_frame->f_locals; + locals = f->f_locals; + fast = f->f_fastlocals; + map = f->f_localmap; + if (locals == NULL || fast == NULL || map == NULL) + return locals; + if (!is_dictobject(locals) || !is_listobject(fast) || + !is_dictobject(map)) + return locals; + i = getdictsize(map); + while (--i >= 0) { + object *key; + object *value; + int j; + key = getdict2key(map, i); + if (key == NULL) + continue; + value = dict2lookup(map, key); + if (value == NULL || !is_intobject(value)) + continue; + j = getintvalue(value); + value = getlistitem(fast, j); + if (value == NULL) { + err_clear(); + if (dict2remove(locals, key) != 0) + err_clear(); + } + else { + if (dict2insert(locals, key, value) != 0) + err_clear(); + } + } + return locals; +} + +static void +locals_2_fast(f, clear) + frameobject *f; + int clear; +{ + /* Merge f->f_locals into f->f_fastlocals */ + object *locals, *fast, *map; + int i; + if (f == NULL) + return; + locals = f->f_locals; + fast = f->f_fastlocals; + map = f->f_localmap; + if (locals == NULL || fast == NULL || map == NULL) + return; + if (!is_dictobject(locals) || !is_listobject(fast) || + !is_dictobject(map)) + return; + i = getdictsize(map); + while (--i >= 0) { + object *key; + object *value; + int j; + key = getdict2key(map, i); + if (key == NULL) + continue; + value = dict2lookup(map, key); + if (value == NULL || !is_intobject(value)) + continue; + j = getintvalue(value); + value = dict2lookup(locals, key); + if (value == NULL) + err_clear(); + else + INCREF(value); + if (value != NULL || clear) + if (setlistitem(fast, j, value) != 0) + err_clear(); + } +} + +void +mergelocals() +{ + locals_2_fast(current_frame, 1); } object * diff --git a/Python/compile.c b/Python/compile.c index 116b6bb..dd79937 100644 --- a/Python/compile.c +++ b/Python/compile.c @@ -27,7 +27,6 @@ OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. /* XXX TO DO: XXX Compute maximum needed stack sizes while compiling XXX Generate simple jump for break/return outside 'try...finally' - XXX Include function name in code (and module names?) */ #include "allobjects.h" @@ -2032,7 +2031,7 @@ compile_funcdef(c, n) node *ch; REQ(n, funcdef); /* funcdef: 'def' NAME parameters ':' suite */ c->c_name = STR(CHILD(n, 1)); - com_addoparg(c, RESERVE_FAST, 0); /* Patched up later */ + com_addoparg(c, RESERVE_FAST, com_addconst(c, None)); /* Patched! */ ch = CHILD(n, 2); /* parameters: '(' [varargslist] ')' */ ch = CHILD(ch, 1); /* ')' | varargslist */ if (TYPE(ch) == RPAR) @@ -2100,79 +2099,95 @@ compile_node(c, n) } } -/* Optimization for local and global variables. +/* Optimization for local variables in functions (and *only* functions). - XXX Need to update this text for LOAD_FAST stuff... - - Attempt to replace all LOAD_NAME instructions that refer to a local - variable with LOAD_LOCAL instructions, and all that refer to a global - variable with LOAD_GLOBAL instructions. + This replaces all LOAD_NAME, STORE_NAME and DELETE_NAME + instructions that refer to local variables with LOAD_FAST etc. + The latter instructions are much faster because they don't need to + look up the variable name in a dictionary. To find all local variables, we check all STORE_NAME and IMPORT_FROM instructions. This yields all local variables, including arguments, function definitions, class definitions and import statements. + (We don't check DELETE_NAME instructions, since if there's no + STORE_NAME the DELETE_NAME will surely fail.) - There is one leak: 'from foo import *' introduces local variables - that we can't know while compiling. If this is the case, LOAD_GLOBAL - instructions are not generated -- LOAD_NAME is left in place for - globals, since it first checks for globals (LOAD_LOCAL is still used - for recognized locals, since it doesn't hurt). - - This optimization means that using the same name as a global and - as a local variable within the same scope is now illegal, which - is a change to the language! Also using eval() to introduce new - local variables won't work. But both were bad practice at best. - - The optimization doesn't save much: basically, it saves one - unsuccessful dictionary lookup per global (or built-in) variable - reference. On the (slow!) Mac Plus, with 4 local variables, - this saving was measured to be about 0.18 ms. We might save more - by using a different data structure to hold local variables, like - an array indexed by variable number. + There is one problem: 'from foo import *' introduces local variables + that we can't know while compiling. If this is the case, wo don't + optimize at all (this rarely happens, since import is mostly used + at the module level). + + Note that, because of this optimization, code like the following + won't work: + eval('x = 1') + print x NB: this modifies the string object co->co_code! */ static void -optimizer(co) - codeobject *co; +optimize(c) + struct compiling *c; { unsigned char *next_instr, *cur_instr; object *locals; + int nlocals; int opcode; int oparg; object *name; - int star_used; - + int fast_reserved; + object *error_type, *error_value; + #define NEXTOP() (*next_instr++) #define NEXTARG() (next_instr += 2, (next_instr[-1]<<8) + next_instr[-2]) #define GETITEM(v, i) (getlistitem((v), (i))) -#define GETNAMEOBJ(i) (GETITEM(co->co_names, (i))) - +#define GETNAMEOBJ(i) (GETITEM(c->c_names, (i))) + locals = newdictobject(); if (locals == NULL) { - err_clear(); - return; /* For now, this is OK */ + c->c_errors++; + return; } + nlocals = 0; + + err_get(&error_type, &error_value); - next_instr = (unsigned char *) GETSTRINGVALUE(co->co_code); + next_instr = (unsigned char *) getstringvalue(c->c_code); for (;;) { opcode = NEXTOP(); if (opcode == STOP_CODE) break; if (HAS_ARG(opcode)) oparg = NEXTARG(); - if (opcode == STORE_NAME || opcode == IMPORT_FROM) { + if (opcode == STORE_NAME || opcode == DELETE_NAME || + opcode == IMPORT_FROM) { + object *v; name = GETNAMEOBJ(oparg); - if (dict2insert(locals, name, None) != 0) { - DECREF(locals); - return; /* Sorry */ + if (dict2lookup(locals, name) != NULL) + continue; + err_clear(); + v = newintobject(nlocals); + if (v == NULL) { + c->c_errors++; + goto err; } + nlocals++; + if (dict2insert(locals, name, v) != 0) { + DECREF(v); + c->c_errors++; + goto err; + } + DECREF(v); } } - star_used = (dictlookup(locals, "*") != NULL); - next_instr = (unsigned char *) GETSTRINGVALUE(co->co_code); + if (nlocals == 0 || dictlookup(locals, "*") != NULL) { + /* Don't optimize anything */ + goto end; + } + + next_instr = (unsigned char *) getstringvalue(c->c_code); + fast_reserved = 0; for (;;) { cur_instr = next_instr; opcode = NEXTOP(); @@ -2180,18 +2195,40 @@ optimizer(co) break; if (HAS_ARG(opcode)) oparg = NEXTARG(); - if (opcode == LOAD_NAME) { + if (opcode == RESERVE_FAST) { + int i = com_addconst(c, locals); + cur_instr[1] = i & 0xff; + cur_instr[2] = (i>>8) & 0xff; + fast_reserved = 1; + continue; + } + if (!fast_reserved) + continue; + if (opcode == LOAD_NAME || + opcode == STORE_NAME || + opcode == DELETE_NAME) { + object *v; + int i; name = GETNAMEOBJ(oparg); - if (dict2lookup(locals, name) != NULL) - *cur_instr = LOAD_LOCAL; - else { + v = dict2lookup(locals, name); + if (v == NULL) { err_clear(); - if (!star_used) - *cur_instr = LOAD_GLOBAL; + continue; } + i = getintvalue(v); + switch (opcode) { + case LOAD_NAME: cur_instr[0] = LOAD_FAST; break; + case STORE_NAME: cur_instr[0] = STORE_FAST; break; + case DELETE_NAME: cur_instr[0] = DELETE_FAST; break; + } + cur_instr[1] = i & 0xff; + cur_instr[2] = (i>>8) & 0xff; } } - + + end: + err_setval(error_type, error_value); + err: DECREF(locals); } @@ -2206,6 +2243,8 @@ compile(n, filename) return NULL; compile_node(&sc, n); com_done(&sc); + if (TYPE(n) == funcdef && sc.c_errors == 0) + optimize(&sc); co = NULL; if (sc.c_errors == 0) { object *v, *w; @@ -2218,7 +2257,5 @@ compile(n, filename) XDECREF(w); } com_free(&sc); - if (co != NULL && filename[0] != '<') - optimizer(co); return co; } diff --git a/Python/import.c b/Python/import.c index 4b7ee13..2171f4b 100644 --- a/Python/import.c +++ b/Python/import.c @@ -54,7 +54,7 @@ extern char *argv0; /* Magic word to reject pre-0.9.9 .pyc files */ -#define MAGIC 0x99BE2AL +#define MAGIC 0x99BE3AL static object *modules; diff --git a/Python/pythonrun.c b/Python/pythonrun.c index e59458e..c387c62 100644 --- a/Python/pythonrun.c +++ b/Python/pythonrun.c @@ -304,16 +304,23 @@ run_node(n, filename, globals, locals) char *filename; /*dict*/object *globals, *locals; { + object *res; + int needmerge = 0; if (globals == NULL) { globals = getglobals(); - if (locals == NULL) + if (locals == NULL) { locals = getlocals(); + needmerge = 1; + } } else { if (locals == NULL) locals = globals; } - return eval_node(n, filename, globals, locals); + res = eval_node(n, filename, globals, locals); + if (needmerge) + mergelocals(); + return res; } object * -- cgit v0.12