[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: PATCH: fixes bug with calling garbage collector from custom lua_Alloc
- From: "Robert G. Jakabosky" <bobby@...>
- Date: Thu, 15 May 2008 03:33:55 -0700
Updated patch attached 'emergency_gc-5.1.3.patch'. Includes two memory
optimizations, no new bugfixes in this release.
The two memory optimizations are broken into two patches that can be used
without the emergency gc patch. The emergency gc patch includes them. These
two optimizations help to decrease the peak memory usages of scripts that use
tables or work with a lot of unique strings. The most benefit will be to
scripts that need to run with a limited amount of memory.
Patch: 'stringtable_resize-5.1.3.patch'
The Lua core has a global hashtable for internalized strings. As new strings
are created that hashtable needs to grow and when strings are freed by the
garbage collector that hashtable needs to be shrunk. The current resize
method allocates a new hashtable and moves all the strings from the old
hashtable to the new one, before it frees the old hashtable. This patch will
do the resize without having to have two hashtables allocated at the same
time by doing an in-place resize. This patch is simple compared to the next
patch and it shouldn't increase cpu usage.
Patch: 'hashpart_resize-5.1.3.patch'
This patch makes a similar change to the way Lua tables are resized, but
required a lot more work.
Other attachments:
stringtable_resize.lua - script used to test new resize method of internal
string table.
stringtable_resize.log - output of script for both old & new resize method. A
debug message was added to the resize methods during the two runs. The peak
memory usage for this script was about 4k lower for the new method.
wordfreq.lua - script used for testing table resizing. A text file of the
book "War and Peace" was used as input.
wordfreq_peakmem_old_resize.log - output from wordfreq.lua using old resize
method.
wordfreq_peakmem_new_resize.log - output from wordfreq.lua using new resize
method. Peak memory usage is about 400K lower then the old resize method.
On Wednesday 14, Bogdan Marinescu wrote:
> By the way, shouldn't your patch be published to
> http://lua-users.org/wiki/LuaPowerPatches? I don't tknow if there are
> any special requirements for a patch to be published on that page, but
> I think this would make it more visible to the Lua community.
I was going to add it to that page then I decided to wait until it was more
stable(no outstanding bugs are features). I will add it after getting some
feedback on the new changes.
> On Tue, May 13, 2008 at 10:07 AM, Bogdan Marinescu
>
> <bogdan.marinescu@gmail.com> wrote:
> > Once again, excellent work. I can't wait to test this on an embedded
> > platform, but right now my ARM board is dead for some reason. I'll try
> > with another board though.
Thanks and let me know how it goes with running it on an embedded platform.
--
Robert G. Jakabosky
diff --git a/src/lapi.c b/src/lapi.c
index 5fde5eb..e5d9a84 100644
--- a/src/lapi.c
+++ b/src/lapi.c
@@ -656,14 +656,14 @@ LUA_API void lua_settable (lua_State *L, int idx) {
LUA_API void lua_setfield (lua_State *L, int idx, const char *k) {
StkId t;
- TValue key;
lua_lock(L);
api_checknelems(L, 1);
t = index2adr(L, idx);
api_checkvalidindex(L, t);
- setsvalue(L, &key, luaS_new(L, k));
- luaV_settable(L, t, &key, L->top - 1);
- L->top--; /* pop value */
+ setsvalue2s(L, L->top, luaS_new(L, k));
+ api_incr_top(L);
+ luaV_settable(L, t, L->top - 1, L->top - 2);
+ L->top -= 2; /* pop key and value */
lua_unlock(L);
}
@@ -903,11 +903,11 @@ LUA_API int lua_gc (lua_State *L, int what, int data) {
g = G(L);
switch (what) {
case LUA_GCSTOP: {
- g->GCthreshold = MAX_LUMEM;
+ set_block_gc(L);
break;
}
case LUA_GCRESTART: {
- g->GCthreshold = g->totalbytes;
+ unset_block_gc(L);
break;
}
case LUA_GCCOLLECT: {
@@ -924,6 +924,10 @@ LUA_API int lua_gc (lua_State *L, int what, int data) {
break;
}
case LUA_GCSTEP: {
+ if(is_block_gc(L)) {
+ res = 1; /* gc is block so we need to pretend that the collection cycle finished. */
+ break;
+ }
lu_mem a = (cast(lu_mem, data) << 10);
if (a <= g->totalbytes)
g->GCthreshold = g->totalbytes - a;
@@ -945,6 +949,24 @@ LUA_API int lua_gc (lua_State *L, int what, int data) {
g->gcstepmul = data;
break;
}
+ case LUA_GCSETMEMLIMIT: {
+ /* GC values are expressed in Kbytes: #bytes/2^10 */
+ lu_mem new_memlimit = (cast(lu_mem, data) << 10);
+ if(new_memlimit > 0 && new_memlimit < g->totalbytes) {
+ /* run a full GC to make totalbytes < the new limit. */
+ luaC_fullgc(L);
+ if(new_memlimit < g->totalbytes)
+ new_memlimit = (g->totalbytes + 1024) & ~(1024-1); /* round up to next multiple of 1024 */
+ }
+ g->memlimit = new_memlimit;
+ /* new memlimit might be > then requested memlimit. */
+ res = cast_int(new_memlimit >> 10);
+ break;
+ }
+ case LUA_GCGETMEMLIMIT: {
+ res = cast_int(g->memlimit >> 10);
+ break;
+ }
default: res = -1; /* invalid option */
}
lua_unlock(L);
diff --git a/src/lauxlib.c b/src/lauxlib.c
index 10f14e2..e48cba6 100644
--- a/src/lauxlib.c
+++ b/src/lauxlib.c
@@ -23,6 +23,10 @@
#include "lua.h"
#include "lauxlib.h"
+#include "lgc.h"
+#include "ldo.h"
+#include "lobject.h"
+#include "lstate.h"
#define FREELIST_REF 0 /* free list of references */
@@ -624,15 +628,39 @@ LUALIB_API int (luaL_loadstring) (lua_State *L, const char *s) {
/* }====================================================== */
+static int l_check_memlimit(lua_State *L, size_t needbytes) {
+ global_State *g = G(L);
+ int cycle_count = 0;
+ lu_mem limit = g->memlimit - needbytes;
+ /* make sure the GC is not disabled. */
+ if (!is_block_gc(L)) {
+ while (g->totalbytes >= limit) {
+ /* only allow the GC to finished atleast 1 full cycle. */
+ if (g->gcstate == GCSpause && ++cycle_count > 1) break;
+ luaC_step(L);
+ }
+ }
+ return (g->totalbytes >= limit) ? 1 : 0;
+}
+
+
static void *l_alloc (void *ud, void *ptr, size_t osize, size_t nsize) {
- (void)ud;
- (void)osize;
+ lua_State *L = (lua_State *)ud;
+ void *nptr;
if (nsize == 0) {
free(ptr);
return NULL;
}
- else
- return realloc(ptr, nsize);
+ if(nsize > osize && L != NULL) {
+ if(G(L)->memlimit > 0 && l_check_memlimit(L, nsize - osize))
+ return NULL;
+ }
+ nptr = realloc(ptr, nsize);
+ if (nptr == NULL && L != NULL) {
+ luaC_fullgc(L); /* emergency full collection. */
+ nptr = realloc(ptr, nsize); /* try allocation again */
+ }
+ return nptr;
}
@@ -646,6 +674,7 @@ static int panic (lua_State *L) {
LUALIB_API lua_State *luaL_newstate (void) {
lua_State *L = lua_newstate(l_alloc, NULL);
+ lua_setallocf(L, l_alloc, L); /* allocator need lua_State. */
if (L) lua_atpanic(L, &panic);
return L;
}
diff --git a/src/lbaselib.c b/src/lbaselib.c
index 2a4c079..7a82778 100644
--- a/src/lbaselib.c
+++ b/src/lbaselib.c
@@ -192,9 +192,10 @@ static int luaB_gcinfo (lua_State *L) {
static int luaB_collectgarbage (lua_State *L) {
static const char *const opts[] = {"stop", "restart", "collect",
- "count", "step", "setpause", "setstepmul", NULL};
+ "count", "step", "setpause", "setstepmul","setmemlimit","getmemlimit", NULL};
static const int optsnum[] = {LUA_GCSTOP, LUA_GCRESTART, LUA_GCCOLLECT,
- LUA_GCCOUNT, LUA_GCSTEP, LUA_GCSETPAUSE, LUA_GCSETSTEPMUL};
+ LUA_GCCOUNT, LUA_GCSTEP, LUA_GCSETPAUSE, LUA_GCSETSTEPMUL,
+ LUA_GCSETMEMLIMIT,LUA_GCGETMEMLIMIT};
int o = luaL_checkoption(L, 1, "collect", opts);
int ex = luaL_optint(L, 2, 0);
int res = lua_gc(L, optsnum[o], ex);
diff --git a/src/ldo.c b/src/ldo.c
index 8de05f7..2e9c86d 100644
--- a/src/ldo.c
+++ b/src/ldo.c
@@ -208,7 +208,9 @@ void luaD_callhook (lua_State *L, int event, int line) {
static StkId adjust_varargs (lua_State *L, Proto *p, int actual) {
int i;
int nfixargs = p->numparams;
+#if defined(LUA_COMPAT_VARARG)
Table *htab = NULL;
+#endif
StkId base, fixed;
for (; actual < nfixargs; ++actual)
setnilvalue(L->top++);
@@ -218,10 +220,13 @@ static StkId adjust_varargs (lua_State *L, Proto *p, int actual) {
lua_assert(p->is_vararg & VARARG_HASARG);
luaC_checkGC(L);
htab = luaH_new(L, nvar, 1); /* create `arg' table */
+ sethvalue2s(L, L->top, htab); /* put table on stack */
+ incr_top(L);
for (i=0; i<nvar; i++) /* put extra arguments into `arg' table */
- setobj2n(L, luaH_setnum(L, htab, i+1), L->top - nvar + i);
+ setobj2n(L, luaH_setnum(L, htab, i+1), L->top - 1 - nvar + i);
/* store counter in field `n' */
setnvalue(luaH_setstr(L, htab, luaS_newliteral(L, "n")), cast_num(nvar));
+ L->top--; /* remove table from stack */
}
#endif
/* move fixed parameters to final position */
@@ -231,11 +236,13 @@ static StkId adjust_varargs (lua_State *L, Proto *p, int actual) {
setobjs2s(L, L->top++, fixed+i);
setnilvalue(fixed+i);
}
+#if defined(LUA_COMPAT_VARARG)
/* add `arg' parameter */
if (htab) {
sethvalue(L, L->top++, htab);
lua_assert(iswhite(obj2gco(htab)));
}
+#endif
return base;
}
@@ -494,6 +501,7 @@ static void f_parser (lua_State *L, void *ud) {
struct SParser *p = cast(struct SParser *, ud);
int c = luaZ_lookahead(p->z);
luaC_checkGC(L);
+ set_block_gc(L); /* stop collector during parsing */
tf = ((c == LUA_SIGNATURE[0]) ? luaU_undump : luaY_parser)(L, p->z,
&p->buff, p->name);
cl = luaF_newLclosure(L, tf->nups, hvalue(gt(L)));
@@ -502,6 +510,7 @@ static void f_parser (lua_State *L, void *ud) {
cl->l.upvals[i] = luaF_newupval(L);
setclvalue(L, L->top, cl);
incr_top(L);
+ unset_block_gc(L);
}
diff --git a/src/lfunc.c b/src/lfunc.c
index 813e88f..d2ce63d 100644
--- a/src/lfunc.c
+++ b/src/lfunc.c
@@ -66,7 +66,6 @@ UpVal *luaF_findupval (lua_State *L, StkId level) {
}
uv = luaM_new(L, UpVal); /* not found: create a new one */
uv->tt = LUA_TUPVAL;
- uv->marked = luaC_white(g);
uv->v = level; /* current value lives in the stack */
uv->next = *pp; /* chain it in the proper position */
*pp = obj2gco(uv);
@@ -74,6 +73,7 @@ UpVal *luaF_findupval (lua_State *L, StkId level) {
uv->u.l.next = g->uvhead.u.l.next;
uv->u.l.next->u.l.prev = uv;
g->uvhead.u.l.next = uv;
+ luaC_marknew(L, obj2gco(uv));
lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
return uv;
}
diff --git a/src/lgc.c b/src/lgc.c
index d9e0b78..5ffc51b 100644
--- a/src/lgc.c
+++ b/src/lgc.c
@@ -232,8 +232,10 @@ static void traverseclosure (global_State *g, Closure *cl) {
int i;
lua_assert(cl->l.nupvalues == cl->l.p->nups);
markobject(g, cl->l.p);
- for (i=0; i<cl->l.nupvalues; i++) /* mark its upvalues */
- markobject(g, cl->l.upvals[i]);
+ for (i=0; i<cl->l.nupvalues; i++) { /* mark its upvalues */
+ if(cl->l.upvals[i])
+ markobject(g, cl->l.upvals[i]);
+ }
}
}
@@ -258,6 +260,7 @@ static void traversestack (global_State *g, lua_State *l) {
CallInfo *ci;
markvalue(g, gt(l));
lim = l->top;
+ if(l->stack == NULL) return; /* no stack to traverse */
for (ci = l->base_ci; ci <= l->ci; ci++) {
lua_assert(ci->top <= l->stack_last);
if (lim < ci->top) lim = ci->top;
@@ -419,8 +422,6 @@ static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
else { /* must erase `curr' */
lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
*p = curr->gch.next;
- if (curr == g->rootgc) /* is the first element of the list? */
- g->rootgc = curr->gch.next; /* adjust first */
freeobj(L, curr);
}
}
@@ -437,7 +438,10 @@ static void checkSizes (lua_State *L) {
/* check size of buffer */
if (luaZ_sizebuffer(&g->buff) > LUA_MINBUFFER*2) { /* buffer too big? */
size_t newsize = luaZ_sizebuffer(&g->buff) / 2;
- luaZ_resizebuffer(L, &g->buff, newsize);
+ /* make sure newsize is larger then the buffer's in use size. */
+ newsize = (luaZ_bufflen(&g->buff) > newsize) ? luaZ_bufflen(&g->buff) : newsize;
+ if(newsize < luaZ_sizebuffer(&g->buff))
+ luaZ_resizebuffer(L, &g->buff, newsize);
}
}
@@ -609,10 +613,14 @@ static l_mem singlestep (lua_State *L) {
void luaC_step (lua_State *L) {
global_State *g = G(L);
+ if(is_block_gc(L)) return;
+ set_block_gc(L);
l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
if (lim == 0)
lim = (MAX_LUMEM-1)/2; /* no limit */
g->gcdept += g->totalbytes - g->GCthreshold;
+ if (g->estimate > g->totalbytes)
+ g->estimate = g->totalbytes;
do {
lim -= singlestep(L);
if (g->gcstate == GCSpause)
@@ -630,11 +638,14 @@ void luaC_step (lua_State *L) {
lua_assert(g->totalbytes >= g->estimate);
setthreshold(g);
}
+ unset_block_gc(L);
}
void luaC_fullgc (lua_State *L) {
global_State *g = G(L);
+ if(is_block_gc(L)) return;
+ set_block_gc(L);
if (g->gcstate <= GCSpropagate) {
/* reset sweep marks to sweep all elements (returning them to white) */
g->sweepstrgc = 0;
@@ -656,6 +667,7 @@ void luaC_fullgc (lua_State *L) {
singlestep(L);
}
setthreshold(g);
+ unset_block_gc(L);
}
@@ -683,6 +695,14 @@ void luaC_barrierback (lua_State *L, Table *t) {
}
+void luaC_marknew (lua_State *L, GCObject *o) {
+ global_State *g = G(L);
+ o->gch.marked = luaC_white(g);
+ if (g->gcstate == GCSpropagate)
+ reallymarkobject(g, o); /* mark new objects as gray during propagate state. */
+}
+
+
void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
global_State *g = G(L);
o->gch.next = g->rootgc;
diff --git a/src/lgc.h b/src/lgc.h
index 5a8dc60..a623703 100644
--- a/src/lgc.h
+++ b/src/lgc.h
@@ -37,6 +37,18 @@
#define test2bits(x,b1,b2) testbits(x, (bit2mask(b1, b2)))
+/*
+** Possible Garbage Collector flags.
+** Layout for bit use in 'gsflags' field in global_State structure.
+** bit 0 - Protect GC from recursive calls.
+*/
+#define GCFlagsNone 0
+#define GCBlockGCBit 0
+
+
+#define is_block_gc(L) testbit(G(L)->gcflags, GCBlockGCBit)
+#define set_block_gc(L) l_setbit(G(L)->gcflags, GCBlockGCBit)
+#define unset_block_gc(L) resetbit(G(L)->gcflags, GCBlockGCBit)
/*
** Layout for bit use in `marked' field:
@@ -101,6 +113,7 @@ LUAI_FUNC void luaC_callGCTM (lua_State *L);
LUAI_FUNC void luaC_freeall (lua_State *L);
LUAI_FUNC void luaC_step (lua_State *L);
LUAI_FUNC void luaC_fullgc (lua_State *L);
+LUAI_FUNC void luaC_marknew (lua_State *L, GCObject *o);
LUAI_FUNC void luaC_link (lua_State *L, GCObject *o, lu_byte tt);
LUAI_FUNC void luaC_linkupval (lua_State *L, UpVal *uv);
LUAI_FUNC void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v);
diff --git a/src/lstate.c b/src/lstate.c
index 4313b83..64dd71f 100644
--- a/src/lstate.c
+++ b/src/lstate.c
@@ -119,6 +119,8 @@ static void close_state (lua_State *L) {
lua_State *luaE_newthread (lua_State *L) {
lua_State *L1 = tostate(luaM_malloc(L, state_size(lua_State)));
luaC_link(L, obj2gco(L1), LUA_TTHREAD);
+ setthvalue(L, L->top, L1); /* put thread on stack */
+ incr_top(L);
preinit_state(L1, G(L));
stack_init(L1, L); /* init stack */
setobj2n(L, gt(L1), gt(L)); /* share table of globals */
@@ -126,7 +128,8 @@ lua_State *luaE_newthread (lua_State *L) {
L1->basehookcount = L->basehookcount;
L1->hook = L->hook;
resethookcount(L1);
- lua_assert(iswhite(obj2gco(L1)));
+ lua_assert(!isdead(G(L), obj2gco(L1)));
+ L->top--; /* remove thread from stack */
return L1;
}
@@ -160,6 +163,7 @@ LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
g->uvhead.u.l.prev = &g->uvhead;
g->uvhead.u.l.next = &g->uvhead;
g->GCthreshold = 0; /* mark it as unfinished state */
+ g->estimate = 0;
g->strt.size = 0;
g->strt.nuse = 0;
g->strt.hash = NULL;
@@ -167,6 +171,7 @@ LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
luaZ_initbuffer(L, &g->buff);
g->panic = NULL;
g->gcstate = GCSpause;
+ g->gcflags = GCFlagsNone;
g->rootgc = obj2gco(L);
g->sweepstrgc = 0;
g->sweepgc = &g->rootgc;
@@ -175,6 +180,7 @@ LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
g->weak = NULL;
g->tmudata = NULL;
g->totalbytes = sizeof(LG);
+ g->memlimit = 0;
g->gcpause = LUAI_GCPAUSE;
g->gcstepmul = LUAI_GCMUL;
g->gcdept = 0;
diff --git a/src/lstate.h b/src/lstate.h
index 3bc575b..93fc594 100644
--- a/src/lstate.h
+++ b/src/lstate.h
@@ -71,6 +71,7 @@ typedef struct global_State {
void *ud; /* auxiliary data to `frealloc' */
lu_byte currentwhite;
lu_byte gcstate; /* state of garbage collector */
+ lu_byte gcflags; /* flags for the garbage collector */
int sweepstrgc; /* position of sweep in `strt' */
GCObject *rootgc; /* list of all collectable objects */
GCObject **sweepgc; /* position of sweep in `rootgc' */
@@ -81,6 +82,7 @@ typedef struct global_State {
Mbuffer buff; /* temporary buffer for string concatentation */
lu_mem GCthreshold;
lu_mem totalbytes; /* number of bytes currently allocated */
+ lu_mem memlimit; /* maximum number of bytes that can be allocated, 0 = no limit. */
lu_mem estimate; /* an estimate of number of bytes actually in use */
lu_mem gcdept; /* how much GC is `behind schedule' */
int gcpause; /* size of pause between successive GCs */
diff --git a/src/lstring.c b/src/lstring.c
index 4911315..601974b 100644
--- a/src/lstring.c
+++ b/src/lstring.c
@@ -20,30 +20,32 @@
void luaS_resize (lua_State *L, int newsize) {
- GCObject **newhash;
stringtable *tb;
int i;
- if (G(L)->gcstate == GCSsweepstring)
- return; /* cannot resize during GC traverse */
- newhash = luaM_newvector(L, newsize, GCObject *);
tb = &G(L)->strt;
- for (i=0; i<newsize; i++) newhash[i] = NULL;
+ if (G(L)->gcstate == GCSsweepstring || newsize == tb->size)
+ return; /* cannot resize during GC traverse or doesn't need to be resized */
+ if (newsize > tb->size) {
+ luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *);
+ for (i=tb->size; i<newsize; i++) tb->hash[i] = NULL;
+ }
/* rehash */
for (i=0; i<tb->size; i++) {
GCObject *p = tb->hash[i];
+ tb->hash[i] = NULL;
while (p) { /* for each node in the list */
GCObject *next = p->gch.next; /* save next */
unsigned int h = gco2ts(p)->hash;
int h1 = lmod(h, newsize); /* new position */
lua_assert(cast_int(h%newsize) == lmod(h, newsize));
- p->gch.next = newhash[h1]; /* chain it */
- newhash[h1] = p;
+ p->gch.next = tb->hash[h1]; /* chain it */
+ tb->hash[h1] = p;
p = next;
}
}
- luaM_freearray(L, tb->hash, tb->size, TString *);
+ if (newsize < tb->size)
+ luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *);
tb->size = newsize;
- tb->hash = newhash;
}
@@ -53,6 +55,9 @@ static TString *newlstr (lua_State *L, const char *str, size_t l,
stringtable *tb;
if (l+1 > (MAX_SIZET - sizeof(TString))/sizeof(char))
luaM_toobig(L);
+ tb = &G(L)->strt;
+ if ((tb->nuse + 1) > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
+ luaS_resize(L, tb->size*2); /* too crowded */
ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString)));
ts->tsv.len = l;
ts->tsv.hash = h;
@@ -61,13 +66,10 @@ static TString *newlstr (lua_State *L, const char *str, size_t l,
ts->tsv.reserved = 0;
memcpy(ts+1, str, l*sizeof(char));
((char *)(ts+1))[l] = '\0'; /* ending 0 */
- tb = &G(L)->strt;
h = lmod(h, tb->size);
ts->tsv.next = tb->hash[h]; /* chain new entry */
tb->hash[h] = obj2gco(ts);
tb->nuse++;
- if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
- luaS_resize(L, tb->size*2); /* too crowded */
return ts;
}
diff --git a/src/ltable.c b/src/ltable.c
index ec84f4f..92eac99 100644
--- a/src/ltable.c
+++ b/src/ltable.c
@@ -269,20 +269,35 @@ static void setarrayvector (lua_State *L, Table *t, int size) {
}
-static void setnodevector (lua_State *L, Table *t, int size) {
+static Node *getfreepos (Table *t) {
+ while (t->lastfree-- > t->node) {
+ if (ttisnil(gkey(t->lastfree)))
+ return t->lastfree;
+ }
+ return NULL; /* could not find a free place */
+}
+
+
+static void resizenodevector (lua_State *L, Table *t, int oldsize, int newsize) {
int lsize;
- if (size == 0) { /* no elements to hash part? */
+ if (newsize == 0) { /* no elements to hash part? */
t->node = cast(Node *, dummynode); /* use common `dummynode' */
lsize = 0;
}
else {
+ Node *node = t->node;
int i;
- lsize = ceillog2(size);
+ lsize = ceillog2(newsize);
if (lsize > MAXBITS)
luaG_runerror(L, "table overflow");
- size = twoto(lsize);
- t->node = luaM_newvector(L, size, Node);
- for (i=0; i<size; i++) {
+ newsize = twoto(lsize);
+ if (node == dummynode) {
+ oldsize = 0;
+ node = NULL; /* don't try to realloc `dummynode' pointer. */
+ }
+ luaM_reallocvector(L, node, oldsize, newsize, Node);
+ t->node = node;
+ for (i=oldsize; i<newsize; i++) {
Node *n = gnode(t, i);
gnext(n) = NULL;
setnilvalue(gkey(n));
@@ -290,19 +305,138 @@ static void setnodevector (lua_State *L, Table *t, int size) {
}
}
t->lsizenode = cast_byte(lsize);
- t->lastfree = gnode(t, size); /* all positions are free */
+ t->lastfree = gnode(t, newsize); /* reset lastfree to end of table. */
+}
+
+
+static Node *find_prev_node(Node *mp, Node *next) {
+ Node *prev = mp;
+ while (prev != NULL && gnext(prev) != next) prev = gnext(prev);
+ return prev;
+}
+
+
+/*
+** move a node from it's old position to it's new position during a rehash;
+** first, check whether the moving node's main position is free. If not, check whether
+** colliding node is in its main position or not: if it is not, move colliding
+** node to an empty place and put moving node in its main position; otherwise
+** (colliding node is in its main position), moving node goes to an empty position.
+*/
+static int move_node (lua_State *L, Table *t, Node *node) {
+ Node *mp = mainposition(t, key2tval(node));
+ /* if node is in it's main position, don't need to move node. */
+ if (mp == node) return 1;
+ /* if node is in it's main position's chain, don't need to move node. */
+ if (find_prev_node(mp, node) != NULL) return 1;
+ /* is main position is free? */
+ if (!ttisnil(gval(mp)) || mp == dummynode) {
+ /* no; move main position node if it is out of its main position */
+ Node *othermp;
+ othermp = mainposition(t, key2tval(mp));
+ if (othermp != mp) { /* is colliding node out of its main position? */
+ /* yes; swap colliding node with the node that is being moved. */
+ Node *prev;
+ Node tmp;
+ tmp = *node;
+ prev = find_prev_node(othermp, mp); /* find previous */
+ if (prev != NULL) gnext(prev) = node; /* redo the chain with `n' in place of `mp' */
+ *node = *mp; /* copy colliding node into free pos. (mp->next also goes) */
+ *mp = tmp;
+ return (prev != NULL) ? 1 : 0; /* is colliding node part of its main position chain? */
+ }
+ else { /* colliding node is in its own main position */
+ /* add node to main position's chain. */
+ gnext(node) = gnext(mp); /* chain new position */
+ gnext(mp) = node;
+ }
+ }
+ else { /* main position is free, move node */
+ *mp = *node;
+ gnext(node) = NULL;
+ setnilvalue(gkey(node));
+ setnilvalue(gval(node));
+ }
+ return 1;
+}
+
+
+static int move_number (lua_State *L, Table *t, Node *node) {
+ int key;
+ lua_Number n = nvalue(key2tval(node));
+ lua_number2int(key, n);
+ if (luai_numeq(cast_num(key), nvalue(key2tval(node)))) {/* index is int? */
+ /* (1 <= key && key <= t->sizearray) */
+ if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) {
+ setobjt2t(L, &t->array[key-1], gval(node));
+ setnilvalue(gkey(node));
+ setnilvalue(gval(node));
+ return 1;
+ }
+ }
+ return 0;
+}
+
+
+static void resize_hashpart (lua_State *L, Table *t, int nhsize) {
+ int i;
+ int lsize=0;
+ int oldhsize = (t->node != dummynode) ? twoto(t->lsizenode) : 0;
+ if (nhsize > 0) { /* round new hashpart size up to next power of two. */
+ lsize=ceillog2(nhsize);
+ if (lsize > MAXBITS)
+ luaG_runerror(L, "table overflow");
+ }
+ nhsize = twoto(lsize);
+ /* grow hash part to new size. */
+ if (oldhsize < nhsize)
+ resizenodevector(L, t, oldhsize, nhsize);
+ else { /* hash part might be shrinking */
+ if (nhsize > 0) {
+ t->lsizenode = cast_byte(lsize);
+ t->lastfree = gnode(t, nhsize); /* reset lastfree back to end of table. */
+ }
+ else { /* new hashpart size is zero. */
+ resizenodevector(L, t, oldhsize, nhsize);
+ return;
+ }
+ }
+ /* break old chains, try moving int keys to array part and compact keys into new hashpart */
+ for (i = 0; i < oldhsize; i++) {
+ Node *old = gnode(t, i);
+ gnext(old) = NULL;
+ if (ttisnil(gval(old))) { /* clear nodes with nil values. */
+ setnilvalue(gkey(old));
+ continue;
+ }
+ if (ttisnumber(key2tval(old))) { /* try moving the int keys into array part. */
+ if(move_number(L, t, old))
+ continue;
+ }
+ if (i >= nhsize) { /* move all valid keys to indices < nhsize. */
+ Node *n = getfreepos(t); /* get a free place */
+ lua_assert(n != dummynode && n != NULL);
+ *n = *old;
+ }
+ }
+ /* shrink hash part */
+ if (oldhsize > nhsize)
+ resizenodevector(L, t, oldhsize, nhsize);
+ /* move nodes to their new mainposition and re-create node chains */
+ for (i = 0; i < nhsize; i++) {
+ Node *curr = gnode(t, i);
+ if (!ttisnil(gval(curr)))
+ while (move_node(L, t, curr) == 0);
+ }
}
static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
int i;
int oldasize = t->sizearray;
- int oldhsize = t->lsizenode;
- Node *nold = t->node; /* save old hash ... */
if (nasize > oldasize) /* array part must grow? */
setarrayvector(L, t, nasize);
- /* create new hash part with appropriate size */
- setnodevector(L, t, nhsize);
+ resize_hashpart(L, t, nhsize);
if (nasize < oldasize) { /* array part must shrink? */
t->sizearray = nasize;
/* re-insert elements from vanishing slice */
@@ -313,14 +447,6 @@ static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
/* shrink array */
luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
}
- /* re-insert elements from hash part */
- for (i = twoto(oldhsize) - 1; i >= 0; i--) {
- Node *old = nold+i;
- if (!ttisnil(gval(old)))
- setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old));
- }
- if (nold != dummynode)
- luaM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */
}
@@ -358,6 +484,8 @@ static void rehash (lua_State *L, Table *t, const TValue *ek) {
Table *luaH_new (lua_State *L, int narray, int nhash) {
Table *t = luaM_new(L, Table);
luaC_link(L, obj2gco(t), LUA_TTABLE);
+ sethvalue2s(L, L->top, t); /* put table on stack */
+ incr_top(L);
t->metatable = NULL;
t->flags = cast_byte(~0);
/* temporary values (kept only if some malloc fails) */
@@ -366,7 +494,8 @@ Table *luaH_new (lua_State *L, int narray, int nhash) {
t->lsizenode = 0;
t->node = cast(Node *, dummynode);
setarrayvector(L, t, narray);
- setnodevector(L, t, nhash);
+ resizenodevector(L, t, 0, nhash);
+ L->top--; /* remove table from stack */
return t;
}
@@ -379,15 +508,6 @@ void luaH_free (lua_State *L, Table *t) {
}
-static Node *getfreepos (Table *t) {
- while (t->lastfree-- > t->node) {
- if (ttisnil(gkey(t->lastfree)))
- return t->lastfree;
- }
- return NULL; /* could not find a free place */
-}
-
-
/*
** inserts a new key into a hash table; first, check whether key's main
diff --git a/src/lua.c b/src/lua.c
index 3a46609..670b1de 100644
--- a/src/lua.c
+++ b/src/lua.c
@@ -45,6 +45,7 @@ static void print_usage (void) {
"Available options are:\n"
" -e stat execute string " LUA_QL("stat") "\n"
" -l name require library " LUA_QL("name") "\n"
+ " -m limit set memory limit. (units are in Kbytes)\n"
" -i enter interactive mode after executing " LUA_QL("script") "\n"
" -v show version information\n"
" -- stop handling options\n"
@@ -278,6 +279,7 @@ static int collectargs (char **argv, int *pi, int *pv, int *pe) {
break;
case 'e':
*pe = 1; /* go through */
+ case 'm': /* go through */
case 'l':
if (argv[i][2] == '\0') {
i++;
@@ -305,6 +307,15 @@ static int runargs (lua_State *L, char **argv, int n) {
return 1;
break;
}
+ case 'm': {
+ const char *limit = argv[i] + 2;
+ int memlimit=0;
+ if (*limit == '\0') limit = argv[++i];
+ lua_assert(limit != NULL);
+ memlimit = atoi(limit);
+ lua_gc(L, LUA_GCSETMEMLIMIT, memlimit);
+ break;
+ }
case 'l': {
const char *filename = argv[i] + 2;
if (*filename == '\0') filename = argv[++i];
diff --git a/src/lua.h b/src/lua.h
index 5bc97b7..a21f56f 100644
--- a/src/lua.h
+++ b/src/lua.h
@@ -226,6 +226,8 @@ LUA_API int (lua_status) (lua_State *L);
#define LUA_GCSTEP 5
#define LUA_GCSETPAUSE 6
#define LUA_GCSETSTEPMUL 7
+#define LUA_GCSETMEMLIMIT 8
+#define LUA_GCGETMEMLIMIT 9
LUA_API int (lua_gc) (lua_State *L, int what, int data);
diff --git a/src/lvm.c b/src/lvm.c
index ee3256a..8b5085b 100644
--- a/src/lvm.c
+++ b/src/lvm.c
@@ -295,6 +295,7 @@ void luaV_concat (lua_State *L, int total, int last) {
if (l >= MAX_SIZET - tl) luaG_runerror(L, "string length overflow");
tl += l;
}
+ G(L)->buff.n = tl;
buffer = luaZ_openspace(L, &G(L)->buff, tl);
tl = 0;
for (i=n; i>0; i--) { /* concat all strings */
@@ -303,6 +304,7 @@ void luaV_concat (lua_State *L, int total, int last) {
tl += l;
}
setsvalue2s(L, top-n, luaS_newlstr(L, buffer, tl));
+ luaZ_resetbuffer(&G(L)->buff);
}
total -= n-1; /* got `n' strings to create 1 new */
last -= n-1;
@@ -723,6 +725,7 @@ void luaV_execute (lua_State *L, int nexeccalls) {
p = cl->p->p[GETARG_Bx(i)];
nup = p->nups;
ncl = luaF_newLclosure(L, nup, cl->env);
+ setclvalue(L, ra, ncl);
ncl->l.p = p;
for (j=0; j<nup; j++, pc++) {
if (GET_OPCODE(*pc) == OP_GETUPVAL)
@@ -732,7 +735,6 @@ void luaV_execute (lua_State *L, int nexeccalls) {
ncl->l.upvals[j] = luaF_findupval(L, base + GETARG_B(*pc));
}
}
- setclvalue(L, ra, ncl);
Protect(luaC_checkGC(L));
continue;
}
--- lua-5.1.3.orig/src/ltable.c 2007-12-28 07:32:23.000000000 -0800
+++ lua-5.1.3.resize/src/ltable.c 2008-05-15 01:41:42.000000000 -0700
@@ -269,20 +269,35 @@
}
-static void setnodevector (lua_State *L, Table *t, int size) {
+static Node *getfreepos (Table *t) {
+ while (t->lastfree-- > t->node) {
+ if (ttisnil(gkey(t->lastfree)))
+ return t->lastfree;
+ }
+ return NULL; /* could not find a free place */
+}
+
+
+static void resizenodevector (lua_State *L, Table *t, int oldsize, int newsize) {
int lsize;
- if (size == 0) { /* no elements to hash part? */
+ if (newsize == 0) { /* no elements to hash part? */
t->node = cast(Node *, dummynode); /* use common `dummynode' */
lsize = 0;
}
else {
+ Node *node = t->node;
int i;
- lsize = ceillog2(size);
+ lsize = ceillog2(newsize);
if (lsize > MAXBITS)
luaG_runerror(L, "table overflow");
- size = twoto(lsize);
- t->node = luaM_newvector(L, size, Node);
- for (i=0; i<size; i++) {
+ newsize = twoto(lsize);
+ if (node == dummynode) {
+ oldsize = 0;
+ node = NULL; /* don't try to realloc `dummynode' pointer. */
+ }
+ luaM_reallocvector(L, node, oldsize, newsize, Node);
+ t->node = node;
+ for (i=oldsize; i<newsize; i++) {
Node *n = gnode(t, i);
gnext(n) = NULL;
setnilvalue(gkey(n));
@@ -290,19 +305,138 @@
}
}
t->lsizenode = cast_byte(lsize);
- t->lastfree = gnode(t, size); /* all positions are free */
+ t->lastfree = gnode(t, newsize); /* reset lastfree to end of table. */
+}
+
+
+static Node *find_prev_node(Node *mp, Node *next) {
+ Node *prev = mp;
+ while (prev != NULL && gnext(prev) != next) prev = gnext(prev);
+ return prev;
+}
+
+
+/*
+** move a node from it's old position to it's new position during a rehash;
+** first, check whether the moving node's main position is free. If not, check whether
+** colliding node is in its main position or not: if it is not, move colliding
+** node to an empty place and put moving node in its main position; otherwise
+** (colliding node is in its main position), moving node goes to an empty position.
+*/
+static int move_node (lua_State *L, Table *t, Node *node) {
+ Node *mp = mainposition(t, key2tval(node));
+ /* if node is in it's main position, don't need to move node. */
+ if (mp == node) return 1;
+ /* if node is in it's main position's chain, don't need to move node. */
+ if (find_prev_node(mp, node) != NULL) return 1;
+ /* is main position is free? */
+ if (!ttisnil(gval(mp)) || mp == dummynode) {
+ /* no; move main position node if it is out of its main position */
+ Node *othermp;
+ othermp = mainposition(t, key2tval(mp));
+ if (othermp != mp) { /* is colliding node out of its main position? */
+ /* yes; swap colliding node with the node that is being moved. */
+ Node *prev;
+ Node tmp;
+ tmp = *node;
+ prev = find_prev_node(othermp, mp); /* find previous */
+ if (prev != NULL) gnext(prev) = node; /* redo the chain with `n' in place of `mp' */
+ *node = *mp; /* copy colliding node into free pos. (mp->next also goes) */
+ *mp = tmp;
+ return (prev != NULL) ? 1 : 0; /* is colliding node part of its main position chain? */
+ }
+ else { /* colliding node is in its own main position */
+ /* add node to main position's chain. */
+ gnext(node) = gnext(mp); /* chain new position */
+ gnext(mp) = node;
+ }
+ }
+ else { /* main position is free, move node */
+ *mp = *node;
+ gnext(node) = NULL;
+ setnilvalue(gkey(node));
+ setnilvalue(gval(node));
+ }
+ return 1;
+}
+
+
+static int move_number (lua_State *L, Table *t, Node *node) {
+ int key;
+ lua_Number n = nvalue(key2tval(node));
+ lua_number2int(key, n);
+ if (luai_numeq(cast_num(key), nvalue(key2tval(node)))) {/* index is int? */
+ /* (1 <= key && key <= t->sizearray) */
+ if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) {
+ setobjt2t(L, &t->array[key-1], gval(node));
+ setnilvalue(gkey(node));
+ setnilvalue(gval(node));
+ return 1;
+ }
+ }
+ return 0;
+}
+
+
+static void resize_hashpart (lua_State *L, Table *t, int nhsize) {
+ int i;
+ int lsize=0;
+ int oldhsize = (t->node != dummynode) ? twoto(t->lsizenode) : 0;
+ if (nhsize > 0) { /* round new hashpart size up to next power of two. */
+ lsize=ceillog2(nhsize);
+ if (lsize > MAXBITS)
+ luaG_runerror(L, "table overflow");
+ }
+ nhsize = twoto(lsize);
+ /* grow hash part to new size. */
+ if (oldhsize < nhsize)
+ resizenodevector(L, t, oldhsize, nhsize);
+ else { /* hash part might be shrinking */
+ if (nhsize > 0) {
+ t->lsizenode = cast_byte(lsize);
+ t->lastfree = gnode(t, nhsize); /* reset lastfree back to end of table. */
+ }
+ else { /* new hashpart size is zero. */
+ resizenodevector(L, t, oldhsize, nhsize);
+ return;
+ }
+ }
+ /* break old chains, try moving int keys to array part and compact keys into new hashpart */
+ for (i = 0; i < oldhsize; i++) {
+ Node *old = gnode(t, i);
+ gnext(old) = NULL;
+ if (ttisnil(gval(old))) { /* clear nodes with nil values. */
+ setnilvalue(gkey(old));
+ continue;
+ }
+ if (ttisnumber(key2tval(old))) { /* try moving the int keys into array part. */
+ if(move_number(L, t, old))
+ continue;
+ }
+ if (i >= nhsize) { /* move all valid keys to indices < nhsize. */
+ Node *n = getfreepos(t); /* get a free place */
+ lua_assert(n != dummynode && n != NULL);
+ *n = *old;
+ }
+ }
+ /* shrink hash part */
+ if (oldhsize > nhsize)
+ resizenodevector(L, t, oldhsize, nhsize);
+ /* move nodes to their new mainposition and re-create node chains */
+ for (i = 0; i < nhsize; i++) {
+ Node *curr = gnode(t, i);
+ if (!ttisnil(gval(curr)))
+ while (move_node(L, t, curr) == 0);
+ }
}
static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
int i;
int oldasize = t->sizearray;
- int oldhsize = t->lsizenode;
- Node *nold = t->node; /* save old hash ... */
if (nasize > oldasize) /* array part must grow? */
setarrayvector(L, t, nasize);
- /* create new hash part with appropriate size */
- setnodevector(L, t, nhsize);
+ resize_hashpart(L, t, nhsize);
if (nasize < oldasize) { /* array part must shrink? */
t->sizearray = nasize;
/* re-insert elements from vanishing slice */
@@ -313,14 +447,6 @@
/* shrink array */
luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
}
- /* re-insert elements from hash part */
- for (i = twoto(oldhsize) - 1; i >= 0; i--) {
- Node *old = nold+i;
- if (!ttisnil(gval(old)))
- setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old));
- }
- if (nold != dummynode)
- luaM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */
}
@@ -366,7 +492,7 @@
t->lsizenode = 0;
t->node = cast(Node *, dummynode);
setarrayvector(L, t, narray);
- setnodevector(L, t, nhash);
+ resizenodevector(L, t, 0, nhash);
return t;
}
@@ -379,15 +505,6 @@
}
-static Node *getfreepos (Table *t) {
- while (t->lastfree-- > t->node) {
- if (ttisnil(gkey(t->lastfree)))
- return t->lastfree;
- }
- return NULL; /* could not find a free place */
-}
-
-
/*
** inserts a new key into a hash table; first, check whether key's main
diff --git a/src/lstring.c b/src/lstring.c
index a84cfab..601974b 100644
--- a/src/lstring.c
+++ b/src/lstring.c
@@ -20,30 +20,32 @@
void luaS_resize (lua_State *L, int newsize) {
- GCObject **newhash;
stringtable *tb;
int i;
- if (G(L)->gcstate == GCSsweepstring)
- return; /* cannot resize during GC traverse */
- newhash = luaM_newvector(L, newsize, GCObject *);
tb = &G(L)->strt;
- for (i=0; i<newsize; i++) newhash[i] = NULL;
+ if (G(L)->gcstate == GCSsweepstring || newsize == tb->size)
+ return; /* cannot resize during GC traverse or doesn't need to be resized */
+ if (newsize > tb->size) {
+ luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *);
+ for (i=tb->size; i<newsize; i++) tb->hash[i] = NULL;
+ }
/* rehash */
for (i=0; i<tb->size; i++) {
GCObject *p = tb->hash[i];
+ tb->hash[i] = NULL;
while (p) { /* for each node in the list */
GCObject *next = p->gch.next; /* save next */
unsigned int h = gco2ts(p)->hash;
int h1 = lmod(h, newsize); /* new position */
lua_assert(cast_int(h%newsize) == lmod(h, newsize));
- p->gch.next = newhash[h1]; /* chain it */
- newhash[h1] = p;
+ p->gch.next = tb->hash[h1]; /* chain it */
+ tb->hash[h1] = p;
p = next;
}
}
- luaM_freearray(L, tb->hash, tb->size, TString *);
+ if (newsize < tb->size)
+ luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *);
tb->size = newsize;
- tb->hash = newhash;
}
mem_limit = 90000
luaS_resize_old: old=0, newsize=32, nuse=0, moved=0
luaS_resize_old: old=32, newsize=64, nuse=32, moved=32
luaS_resize_old: old=64, newsize=128, nuse=64, moved=64
luaS_resize_old: old=128, newsize=256, nuse=128, moved=128
luaS_resize_old: old=256, newsize=512, nuse=256, moved=256
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_old: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_old: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_old: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_old: old=1024, newsize=2048, nuse=1023, moved=1023
tests/stringtable_resize.lua: memused=54218, peak_memused=58757
totalbytes=54218, memlimit=0
luaS_resize_old: old=2048, newsize=1024, nuse=194, moved=194
tests/stringtable_resize.lua: memused=0, peak_memused=58757
mem_limit = 90000
luaS_resize_new: old=0, newsize=32, nuse=0, moved=0
luaS_resize_new: old=32, newsize=64, nuse=32, moved=32
luaS_resize_new: old=64, newsize=128, nuse=64, moved=64
luaS_resize_new: old=128, newsize=256, nuse=128, moved=128
luaS_resize_new: old=256, newsize=512, nuse=256, moved=256
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
luaS_resize_new: old=2048, newsize=1024, nuse=207, moved=207
luaS_resize_new: old=1024, newsize=512, nuse=207, moved=207
luaS_resize_new: old=512, newsize=1024, nuse=512, moved=512
luaS_resize_new: old=1024, newsize=2048, nuse=1023, moved=1023
tests/stringtable_resize.lua: memused=54218, peak_memused=54722
totalbytes=54218, memlimit=0
luaS_resize_new: old=2048, newsize=1024, nuse=194, moved=194
tests/stringtable_resize.lua: memused=0, peak_memused=54722
local size = 818
local arr
local debug = false
for x=0,10 do
arr = {}
for i=0,size do
val = tostring(i)
arr[i] = val
if debug then print(i, " = ", arr[i]) end
end
for i=0,size do
val = tostring(i)
local val2 = arr[i]
assert(val2 == val,string.format("expected '%s' at idx %d, instead got '%s'",val,i,val2))
if debug then print(i, " = ", arr[i]) end
end
end
new mem_limit = 9000000
34481 the
22221 and
16633 to
14849 of
10516 a
9989 he
8966 in
8166 that
7980 his
7354 was
5658 with
5587 it
5364 had
4724 her
4668 not
4630 him
4525 at
4505 i
4395 s
4045 but
4020 as
3998 on
3770 you
3505 for
3486 she
3295 is
2842 said
2788 all
2691 from
2436 by
2428 be
2425 were
2394 what
2254 they
2157 who
2130 one
2070 this
2056 which
1971 have
1962 pierre
1927 prince
1900 so
1625 an
1577 up
1556 there
1529 them
1524 or
1495 when
1480 did
1475 been
1439 their
1396 no
1368 would
1332 now
1297 only
1292 if
1267 are
1266 me
1237 out
1212 natasha
1210 my
1185 man
1150 t
1143 andrew
1116 could
1066 will
1065 we
1055 more
1036 do
1018 himself
1010 about
1005 how
1001 into
940 then
924 time
914 princess
891 face
879 french
862 went
845 some
844 know
841 after
831 before
830 old
827 eyes
805 your
799 very
791 men
776 rostov
769 room
767 thought
755 go
750 like
745 well
726 see
726 count
718 moscow
718 began
710 again
701 has
699 down
tests/wordfreq.lua: memused=1887420, peak_memused=2325795
totalbytes=1887420, memlimit=0
tests/wordfreq.lua: memused=0, peak_memused=2325795
new mem_limit = 9000000
34481 the
22221 and
16633 to
14849 of
10516 a
9989 he
8966 in
8166 that
7980 his
7354 was
5658 with
5587 it
5364 had
4724 her
4668 not
4630 him
4525 at
4505 i
4395 s
4045 but
4020 as
3998 on
3770 you
3505 for
3486 she
3295 is
2842 said
2788 all
2691 from
2436 by
2428 be
2425 were
2394 what
2254 they
2157 who
2130 one
2070 this
2056 which
1971 have
1962 pierre
1927 prince
1900 so
1625 an
1577 up
1556 there
1529 them
1524 or
1495 when
1480 did
1475 been
1439 their
1396 no
1368 would
1332 now
1297 only
1292 if
1267 are
1266 me
1237 out
1212 natasha
1210 my
1185 man
1150 t
1143 andrew
1116 could
1066 will
1065 we
1055 more
1036 do
1018 himself
1010 about
1005 how
1001 into
940 then
924 time
914 princess
891 face
879 french
862 went
845 some
844 know
841 after
831 before
830 old
827 eyes
805 your
799 very
791 men
776 rostov
769 room
767 thought
755 go
750 like
745 well
726 see
726 count
718 moscow
718 began
710 again
701 has
699 down
tests/wordfreq.lua: memused=1887420, peak_memused=1898260
totalbytes=1887420, memlimit=0
tests/wordfreq.lua: memused=0, peak_memused=1898260
-- $Id: wordfreq.lua,v 1.3 2004-07-03 05:36:11 bfulgham Exp $
-- http://shootout.alioth.debian.org
-- contributed by Roberto Ierusalimschy
-- this version reads 4K chunks of input at a time
local words = {} -- list of all words (for sorting)
local count = {} -- count occurrences of each word
local BUFSIZE = 2^12
while true do
local lines, rest = io.read(BUFSIZE, "*l")
if lines == nil then break end
lines = lines..(rest or '') -- ensures whole lines
for w in string.gmatch(string.lower(lines), "(%l+)") do
local cw = count[w]
if not cw then -- first occurrence?
cw = 0
table.insert(words, w)
end
count[w] = cw + 1
end
end
table.sort(words, function (a,b)
return count[a] > count[b] or (count[a] == count[b] and a > b)
end)
for i=1,table.getn(words) do
local w = words[i]
io.write(string.format("%7d %s\n", count[w], w))
if i > 100 then break end
end
