From 26bf2adaceb18877d836174226d2bfdc3f1fc512 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Tue, 6 Nov 2001 19:41:53 -0200 Subject: optimizations for space in LClosures and time cleanning weak tables --- lfunc.c | 22 +++++++------- lgc.c | 100 ++++++++++++++++++++++++++++++++------------------------------ lobject.h | 38 +++++++++++++----------- lvm.c | 13 ++++---- 4 files changed, 88 insertions(+), 85 deletions(-) diff --git a/lfunc.c b/lfunc.c index bed67101..1e903a5b 100644 --- a/lfunc.c +++ b/lfunc.c @@ -1,5 +1,5 @@ /* -** $Id: lfunc.c,v 1.47 2001/09/07 17:39:10 roberto Exp $ +** $Id: lfunc.c,v 1.48 2001/10/02 16:45:03 roberto Exp $ ** Auxiliary functions to manipulate prototypes and closures ** See Copyright Notice in lua.h */ @@ -20,7 +20,7 @@ cast(int, sizeof(TObject)*((n)-1))) #define sizeLclosure(n) (cast(int, sizeof(LClosure)) + \ - cast(int, sizeof(LClosureEntry)*((n)-1))) + cast(int, sizeof(TObject *)*((n)-1))) Closure *luaF_newCclosure (lua_State *L, int nelems) { @@ -50,8 +50,8 @@ static StkId uppoint (LClosure *cl) { StkId lp = NULL; int i; for (i=0; inupvalues; i++) { - if (cl->upvals[i].heap == NULL && (lp == NULL || cl->upvals[i].val > lp)) - lp = cl->upvals[i].val; + if (!isclosed(cl->upvals[i]) && (lp == NULL || cl->upvals[i] > lp)) + lp = cl->upvals[i]; } return lp; } @@ -77,17 +77,15 @@ static int closeCl (lua_State *L, LClosure *cl, StkId level) { int i; for (i=0; inupvalues; i++) { StkId var; - if (cl->upvals[i].heap == NULL && (var=cl->upvals[i].val) >= level) { + if (!isclosed(cl->upvals[i]) && (var=cl->upvals[i]) >= level) { if (ttype(var) != LUA_TUPVAL) { - UpVal *v = luaM_new(L, UpVal); - v->val = *var; - v->marked = 0; - v->next = G(L)->rootupval; + TObject *v = luaM_newvector(L, 2, TObject); + v[1] = *var; + setupvalue(v, G(L)->rootupval, LUA_HEAPUPVAL); G(L)->rootupval = v; - setupvalue(var, v); + setupvalue(var, &v[1], LUA_TUPVAL); } - cl->upvals[i].heap = vvalue(var); - cl->upvals[i].val = &vvalue(var)->val; + cl->upvals[i] = vvalue(var); got = 1; } } diff --git a/lgc.c b/lgc.c index abace987..d41b6d51 100644 --- a/lgc.c +++ b/lgc.c @@ -1,5 +1,5 @@ /* -** $Id: lgc.c,v 1.114 2001/10/25 19:14:14 roberto Exp roberto $ +** $Id: lgc.c,v 1.115 2001/10/31 19:58:11 roberto Exp $ ** Garbage Collector ** See Copyright Notice in lua.h */ @@ -22,6 +22,7 @@ typedef struct GCState { Table *tmark; /* list of marked tables to be visited */ + Table *toclear; /* list of visited weak tables (to be cleared after GC) */ } GCState; @@ -65,10 +66,10 @@ static void markclosure (GCState *st, Closure *cl) { lua_assert(cl->l.nupvalues == cl->l.p->nupvalues); protomark(cl->l.p); for (i=0; il.nupvalues; i++) { /* mark its upvalues */ - UpVal *u = cl->l.upvals[i].heap; - if (u && !u->marked) { - u->marked = 1; - markobject(st, &u->val); + TObject *u = cl->l.upvals[i]; + if (isclosed(u)) { + ttype(u-1) = LUA_TNIL; /* temporary value (to mark as visited) */ + markobject(st, u); } } } @@ -148,6 +149,10 @@ static void removekey (Node *n) { static void traversetable (GCState *st, Table *h) { int i; int mode = h->weakmode; + if (mode) { /* weak table? must be cleared after GC... */ + h->mark = st->toclear; /* put in the appropriate list */ + st->toclear = h; + } if (!(mode & LUA_WEAK_VALUE)) { i = sizearray(h); while (i--) @@ -167,17 +172,15 @@ static void traversetable (GCState *st, Table *h) { } -static void markall (lua_State *L) { - GCState st; - st.tmark = NULL; - marktagmethods(G(L), &st); /* mark tag methods */ - markstacks(L, &st); /* mark all stacks */ - marktable(&st, G(L)->type2tag); - markobject(&st, &G(L)->registry); - while (st.tmark) { /* mark tables */ - Table *h = st.tmark; /* get first table from list */ - st.tmark = h->mark; /* remove it from list */ - traversetable(&st, h); +static void markall (lua_State *L, GCState *st) { + marktagmethods(G(L), st); /* mark tag methods */ + markstacks(L, st); /* mark all stacks */ + marktable(st, G(L)->type2tag); + markobject(st, &G(L)->registry); + while (st->tmark) { /* mark tables */ + Table *h = st->tmark; /* get first table from list */ + st->tmark = h->mark; /* remove it from list */ + traversetable(st, h); } } @@ -198,30 +201,27 @@ static int hasmark (const TObject *o) { } -static void cleardeadnodes (Table *h) { - int i; - i = sizearray(h); - while (i--) { - TObject *o = &h->array[i]; - if (!hasmark(o)) - setnilvalue(o); /* remove value */ - } - i = sizenode(h); - while (i--) { - Node *n = node(h, i); - if (!hasmark(val(n)) || !hasmark(key(n))) { - setnilvalue(val(n)); /* remove value ... */ - removekey(n); /* ... and key */ +/* +** clear (set to nil) keys and values from weaktables that were collected +*/ +static void cleartables (Table *h) { + for (; h; h = h->mark) { + int i; + lua_assert(h->weakmode); + i = sizearray(h); + while (i--) { + TObject *o = &h->array[i]; + if (!hasmark(o)) + setnilvalue(o); /* remove value */ + } + i = sizenode(h); + while (i--) { + Node *n = node(h, i); + if (!hasmark(val(n)) || !hasmark(key(n))) { + setnilvalue(val(n)); /* remove value ... */ + removekey(n); /* ... and key */ + } } - } -} - - -static void cleartables (global_State *G) { - Table *h; - for (h = G->roottable; h; h = h->next) { - if (h->weakmode && ismarked(h)) - cleardeadnodes(h); } } @@ -284,16 +284,17 @@ static void collecttable (lua_State *L) { static void collectupval (lua_State *L) { - UpVal **v = &G(L)->rootupval; - UpVal *curr; + TObject **v = &G(L)->rootupval; + TObject *curr; while ((curr = *v) != NULL) { - if (curr->marked) { - curr->marked = 0; - v = &curr->next; + if (ttype(curr) == LUA_TNIL) { /* was marked? */ + ttype(curr) = LUA_HEAPUPVAL; /* unmark */ + v = &vvalue(curr); /* next */ } else { - *v = curr->next; - luaM_freelem(L, curr); + lua_assert(ttype(curr) == LUA_HEAPUPVAL); + *v = vvalue(curr); /* next */ + luaM_freearray(L, curr, 2, TObject); } } } @@ -411,8 +412,11 @@ void luaC_collect (lua_State *L, int all) { void luaC_collectgarbage (lua_State *L) { - markall(L); - cleartables(G(L)); + GCState st; + st.tmark = NULL; + st.toclear = NULL; + markall(L, &st); + cleartables(st.toclear); luaC_collect(L, 0); checkMbuffer(L); G(L)->GCthreshold = 2*G(L)->nblocks; /* new threshold */ diff --git a/lobject.h b/lobject.h index dbabc638..d8e6057f 100644 --- a/lobject.h +++ b/lobject.h @@ -1,5 +1,5 @@ /* -** $Id: lobject.h,v 1.114 2001/10/02 16:45:03 roberto Exp $ +** $Id: lobject.h,v 1.115 2001/10/25 19:14:14 roberto Exp $ ** Type definitions for Lua objects ** See Copyright Notice in lua.h */ @@ -31,8 +31,13 @@ #define NUM_TAGS 6 -/* extra tag: used locally when moving an upvalue from the stack to the heap */ +/* +** extra tags: +** first is used locally when moving an upvalue from the stack to the heap; +** second prefixes upvalues in the heap +*/ #define LUA_TUPVAL 6 +#define LUA_HEAPUPVAL 7 typedef union { @@ -40,7 +45,7 @@ typedef union { union Udata *u; union Closure *cl; struct Table *h; - struct UpVal *v; + struct lua_TObject *v; lua_Number n; /* LUA_TNUMBER */ } Value; @@ -81,8 +86,8 @@ typedef struct lua_TObject { #define setnilvalue(obj) ((obj)->tt=LUA_TNIL) -#define setupvalue(obj,x) \ - { TObject *_o=(obj); _o->tt=LUA_TUPVAL; _o->value.v=(x); } +#define setupvalue(obj,x,t) \ + { TObject *_o=(obj); _o->tt=(t); _o->value.v=(x); } #define setobj(obj1,obj2) \ { TObject *o1=(obj1); const TObject *o2=(obj2); \ @@ -165,13 +170,15 @@ typedef struct LocVar { /* -** Upvalues in the heap +** Upvalues in the heap. There is a small trick here: to allow a closure to +** diferentiate between upvalues in the heap and in the stack, upvalues in +** the heap always have another TObject before them (like those in the stack), +** but those `prefix' objects have a tag that cannot happen in the stack. +** Moreover, we use these extra `prexif' object to store GC-related +** information. */ -typedef struct UpVal { - TObject val; - struct UpVal *next; - int marked; -} UpVal; + +#define isclosed(u) (ttype((u)-1) == LUA_HEAPUPVAL) /* @@ -188,20 +195,16 @@ typedef struct CClosure { } CClosure; -typedef struct LClosureEntry { - TObject *val; - UpVal *heap; /* NULL when upvalue is still in the stack */ -} LClosureEntry; - typedef struct LClosure { lu_byte isC; lu_byte nupvalues; lu_byte marked; union Closure *next; /* first four fields must be equal to CClosure!! */ struct Proto *p; - LClosureEntry upvals[1]; + TObject *upvals[1]; } LClosure; + typedef union Closure { CClosure c; LClosure l; @@ -212,7 +215,6 @@ typedef union Closure { - /* ** Tables */ diff --git a/lvm.c b/lvm.c index 6f0d9ab7..cc94b836 100644 --- a/lvm.c +++ b/lvm.c @@ -1,5 +1,5 @@ /* -** $Id: lvm.c,v 1.196 2001/10/25 19:14:14 roberto Exp roberto $ +** $Id: lvm.c,v 1.197 2001/10/31 19:58:11 roberto Exp $ ** Lua virtual machine ** See Copyright Notice in lua.h */ @@ -391,8 +391,8 @@ StkId luaV_execute (lua_State *L, const LClosure *cl, StkId base) { } case OP_GETUPVAL: { int b = GETARG_B(i); - lua_assert(cl->upvals[b].heap || cl->upvals[b].val < base); - setobj(ra, cl->upvals[b].val); + lua_assert(isclosed(cl->upvals[b]) || cl->upvals[b] < base); + setobj(ra, cl->upvals[b]); break; } case OP_GETGLOBAL: { @@ -411,8 +411,8 @@ StkId luaV_execute (lua_State *L, const LClosure *cl, StkId base) { } case OP_SETUPVAL: { int b = GETARG_B(i); - lua_assert(cl->upvals[b].heap || cl->upvals[b].val < base); - setobj(cl->upvals[b].val, ra); + lua_assert(isclosed(cl->upvals[b]) || cl->upvals[b] < base); + setobj(cl->upvals[b], ra); break; } case OP_SETTABLE: { @@ -649,8 +649,7 @@ StkId luaV_execute (lua_State *L, const LClosure *cl, StkId base) { ncl->l.upvals[j] = cl->upvals[GETARG_B(*pc)]; else { lua_assert(GET_OPCODE(*pc) == OP_MOVE); - ncl->l.upvals[j].heap = NULL; - ncl->l.upvals[j].val = base + GETARG_B(*pc); + ncl->l.upvals[j] = base + GETARG_B(*pc); } } luaF_LConlist(L, ncl); -- cgit v1.2.3-55-g6feb