After a "bad collections", avoid switching back back to generational

After a major bad collection (one that collects too few objects),
next collection will be major again. In that case, avoid switching
back to generational mode (as it will have to switch again to
incremental to do next major collection).

1 files changed, 114 insertions, 44 deletions

diff --git a/lgc.c b/lgc.c
index 0c3386e7..bf0460d5 100644
--- a/lgc.c
+++ b/lgc.c
@@ -101,6 +101,7 @@
 
 static void reallymarkobject (global_State *g, GCObject *o);
 static lu_mem atomic (lua_State *L);
+static void entersweep (lua_State *L);
 
 
 /*
@@ -1162,15 +1163,7 @@ static void youngcollection (lua_State *L, global_State *g) {
 }
 
 
-/*
-** Enter generational mode. Must go until the end of an atomic cycle
-** to ensure that all threads are in the gray list. Then, turn all
-** objects into old and finishes the collection.
-*/
-static void entergen (lua_State *L, global_State *g) {
-  luaC_runtilstate(L, bitmask(GCSpause));  /* prepare to start a new cycle */
-  luaC_runtilstate(L, bitmask(GCSpropagate));  /* start new cycle */
-  atomic(L);
+static void atomic2gen (lua_State *L, global_State *g) {
   /* sweep all elements making them old */
   sweep2old(L, &g->allgc);
   /* everything alive now is old */
@@ -1183,15 +1176,31 @@ static void entergen (lua_State *L, global_State *g) {
   sweep2old(L, &g->tobefnz);
 
   g->gckind = KGC_GEN;
+  g->lastatomic = 0;
   g->GCestimate = gettotalbytes(g);  /* base for memory control */
   finishgencycle(L, g);
 }
 
 
 /*
+** Enter generational mode. Must go until the end of an atomic cycle
+** to ensure that all threads and weak tables are in the gray lists.
+** Then, turn all objects into old and finishes the collection.
+*/
+static lu_mem entergen (lua_State *L, global_State *g) {
+  lu_mem numobjs;
+  luaC_runtilstate(L, bitmask(GCSpause));  /* prepare to start a new cycle */
+  luaC_runtilstate(L, bitmask(GCSpropagate));  /* start new cycle */
+  numobjs = atomic(L);  /* propagates all and then do the atomic stuff */
+  atomic2gen(L, g);
+  return numobjs;
+}
+
+
+/*
 ** Enter incremental mode. Turn all objects white, make all
 ** intermediate lists point to NULL (to avoid invalid pointers),
-** and go to pause state.
+** and go to the pause state.
 */
 static void enterinc (global_State *g) {
   whitelist(g, g->allgc);
@@ -1201,6 +1210,7 @@ static void enterinc (global_State *g) {
   g->finobjrold = g->finobjold = g->finobjsur = NULL;
   g->gcstate = GCSpause;
   g->gckind = KGC_INC;
+  g->lastatomic = 0;
 }
 
 
@@ -1215,54 +1225,114 @@ void luaC_changemode (lua_State *L, int newmode) {
     else
       enterinc(g);  /* entering incremental mode */
   }
+  g->lastatomic = 0;
 }
 
 
 /*
 ** Does a full collection in generational mode.
 */
-static void fullgen (lua_State *L, global_State *g) {
+static lu_mem fullgen (lua_State *L, global_State *g) {
   enterinc(g);
-  entergen(L, g);
+  return entergen(L, g);
+}
+
+
+/*
+** Set debt for the next minor collection, which will happen when
+** memory grows 'genminormul'%.
+*/
+static void setminordebt (global_State *g) {
+  luaE_setdebt(g, -(cast(l_mem, (gettotalbytes(g) / 100)) * g->genminormul));
 }
 
 
 /*
-** Does a generational "step". If memory grows 'genmajormul'% larger
-** than last major collection (kept in 'g->GCestimate'), does a major
-** collection. Otherwise, does a minor collection and set debt to make
-** another collection when memory grows 'genminormul'% larger.
-** When it does a major collection, it then checks whether it could
-** reclaim at least ?? memory. If not, it sets a long pause for the
-** next collection. (Therefore, the next collection will be a major
-** one, too.)
+** Does a major collection after last collection was a "bad collection".
+**
+** When the program is building a big struture, it allocates lots of
+** memory but generates very little garbage. In those scenarios,
+** the generational mode just wastes time doing small collections, and
+** major collections are frequently what we call a "bad collection", a
+** collection that frees too few objects. To avoid the cost of switching
+** between generational mode and the incremental mode needed for full
+** (major) collections, the collector tries to stay in incremental mode
+** after a bad collection, and to switch back to generational mode only
+** after a "good" collection (one that traverses less than 9/8 objects
+** of the previous one).
+** The collector must choose whether to stay in incremental mode or to
+** switch back to generational mode before sweeping. At this point, it
+** does not know the real memory in use, so it cannot use memory to
+** decide whether to return to generational mode. Instead, it uses the
+** number of objects traversed (returned by 'atomic') as a proxy. The
+** field 'g->lastatomic' keeps this count from the last collection.
+** ('g->lastatomic != 0' also means that the last collection was bad.)
+*/
+static void stepgenfull (lua_State *L, global_State *g) {
+  lu_mem newatomic;  /* count of traversed objects */
+  lu_mem lastatomic = g->lastatomic;  /* count from last collection */
+  if (g->gckind == KGC_GEN)  /* still in generational mode? */
+    enterinc(g);  /* enter incremental mode */
+  luaC_runtilstate(L, bitmask(GCSpropagate));  /* start new cycle */
+  newatomic = atomic(L);  /* mark everybody */
+  if (newatomic < lastatomic + (lastatomic >> 3)) {  /* good collection? */
+    atomic2gen(L, g);  /* return to generational mode */
+    setminordebt(g);
+  }
+  else {  /* another bad collection; stay in incremental mode */
+    g->GCestimate = gettotalbytes(g);  /* first estimate */;
+    entersweep(L);
+    luaC_runtilstate(L, bitmask(GCSpause));  /* finish collection */
+    setpause(g);
+    g->lastatomic = newatomic;
+  }
+}
+
+
+/*
+** Does a generational "step".
+** Usually, this means doing a minor collection and setting the debt to
+** make another collection when memory grows 'genminormul'% larger.
+**
+** However, there are exceptions.  If memory grows 'genmajormul'%
+** larger than it was at the end of the last major collection (kept
+** in 'g->GCestimate'), the function does a major collection. At the
+** end, it checks whether the major collection was able to free a
+** decent amount of memory (at least half the growth in memory since
+** previous major collection). If so, the collector keeps its state,
+** and the next collection will probably be minor again. Otherwise,
+** we have what we call a "bad collection". In that case, set the field
+** 'g->lastatomic' to signal that fact, so that the next collection will
+** go to 'stepgenfull'.
+**
 ** 'GCdebt <= 0' means an explicit call to GC step with "size" zero;
-** in that case, always do a minor collection.
+** in that case, do a minor collection.
 */
 static void genstep (lua_State *L, global_State *g) {
-  lu_mem majorbase = g->GCestimate;  /* memory after last major collection */
-  lu_mem majorinc = (majorbase / 100) * getgcparam(g->genmajormul);
-  lu_mem memnew = gettotalbytes(g);
-  if (g->GCdebt > 0 && memnew > majorbase + majorinc) {
-    fullgen(L, g);
-    memnew = gettotalbytes(g);
-    if (memnew < majorbase + (majorinc / 2)) {
-      /* collected at least half of memory growth since last major
-         collection; go back to minor collections */
-      luaE_setdebt(g, -(cast(l_mem, (memnew / 100)) * g->genminormul));
+  if (g->lastatomic != 0)  /* last collection was a bad one? */
+    stepgenfull(L, g);  /* do a full step */
+  else {
+    lu_mem majorbase = g->GCestimate;  /* memory after last major collection */
+    lu_mem majorinc = (majorbase / 100) * getgcparam(g->genmajormul);
+    if (g->GCdebt > 0 && gettotalbytes(g) > majorbase + majorinc) {
+      lu_mem numobjs = fullgen(L, g);  /* do a major collection */
+      if (gettotalbytes(g) < majorbase + (majorinc / 2)) {
+        /* collected at least half of memory growth since last major
+           collection; keep doing minor collections */
+        setminordebt(g);
+      }
+      else {  /* bad collection */
+        g->lastatomic = numobjs;  /* signal that last collection was bad */
+        setpause(g);  /* do a long wait for next (major) collection */
+      }
     }
-    else {
-      /* memory seems to be growing; do a long wait for next (major)
-         collection */
-      setpause(g);
+    else {  /* regular case; do a minor collection */
+      youngcollection(L, g);
+      setminordebt(g);
+      g->GCestimate = majorbase;  /* preserve base value */
     }
   }
-  else {
-    youngcollection(L, g);
-    memnew = gettotalbytes(g);
-    luaE_setdebt(g, -(cast(l_mem, (memnew / 100)) * g->genminormul));
-    g->GCestimate = majorbase;  /* preserve base value */
-  }
+  lua_assert(isdecGCmodegen(g));
 }
 
 /* }====================================================== */
@@ -1493,10 +1563,10 @@ static void incstep (lua_State *L, global_State *g) {
 void luaC_step (lua_State *L) {
   global_State *g = G(L);
   if (g->gcrunning) {  /* running? */
-    if (g->gckind == KGC_INC)
-      incstep(L, g);
-    else
+    if(isdecGCmodegen(g))
       genstep(L, g);
+    else
+      incstep(L, g);
   }
 }