This is a major update, which switches virtually every allocated-but-not-freed

string into the strcache.  As a side-effect, many more structure members and
function arguments can/should be declared const.

As mentioned in the changelog, unfortunately measurement shows that this
change does not yet reduce memory.  The problem is with secondary expansion:
because of this we store all the prerequisites in the string cache twice.
First we store the prerequisite string after initial expansion but before
secondary expansion, then we store each individual file after secondary
expansion and expand_deps().  I plan to change expand_deps() to be callable
in either context (eval or snap_deps) then have non-second-expansion
targets call expand_deps() during eval, so that we only need to store that
dependency list once.

1 files changed, 48 insertions, 24 deletions

diff --git a/strcache.c b/strcache.c
index 5b72399..8065194 100644
--- a/strcache.c
+++ b/strcache.c
@@ -20,8 +20,9 @@ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.  */
 
 #include "hash.h"
 
-/* The size (in bytes) of each cache buffer.  */
-#define CACHE_BUFFER_SIZE   (4096)
+/* The size (in bytes) of each cache buffer.
+   Try to pick something that will map well into the heap.  */
+#define CACHE_BUFFER_SIZE   (8192 - 16)
 
 
 /* A string cached here will never be freed, so we don't need to worry about
@@ -39,6 +40,11 @@ struct strcache {
 static int bufsize = CACHE_BUFFER_SIZE;
 static struct strcache *strcache = NULL;
 
+/* Add a new buffer to the cache.  Add it at the front to reduce search time.
+   This can also increase the overhead, since it's less likely that older
+   buffers will be filled in.  However, GNU make has so many smaller strings
+   that this doesn't seem to be much of an issue in practice.
+ */
 static struct strcache *
 new_cache()
 {
@@ -61,9 +67,9 @@ add_string(const char *str, int len)
   struct strcache *sp;
   const char *res;
 
-  /* If the string we want is too large to fit into a single buffer, then we're
-     screwed; nothing will ever fit!  Change the maximum size of the cache to
-     be big enough.  */
+  /* If the string we want is too large to fit into a single buffer, then
+     we're screwed; nothing will ever fit!  Change the maximum size of the
+     cache to be big enough.  */
   if (len > bufsize)
     bufsize = len * 2;
 
@@ -113,6 +119,7 @@ str_hash_cmp (const void *x, const void *y)
 }
 
 static struct hash_table strings;
+static unsigned long total_adds = 0;
 
 static const char *
 add_hash (const char *str, int len)
@@ -121,6 +128,9 @@ add_hash (const char *str, int len)
   char *const *slot = (char *const *) hash_find_slot (&strings, str);
   const char *key = *slot;
 
+  /* Count the total number of adds we performed.  */
+  ++total_adds;
+
   if (!HASH_VACANT (key))
     return key;
 
@@ -179,7 +189,7 @@ strcache_setbufsize(int size)
 void
 strcache_init (void)
 {
-  hash_init (&strings, 1000, str_hash_1, str_hash_2, str_hash_cmp);
+  hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
 }
 
 
@@ -191,32 +201,46 @@ strcache_print_stats (const char *prefix)
   int numbuffs = 0, numstrs = 0;
   int totsize = 0, avgsize, maxsize = 0, minsize = bufsize;
   int totfree = 0, avgfree, maxfree = 0, minfree = bufsize;
-  const struct strcache *sp;
+  int lastused = 0, lastfree = 0;
 
-  for (sp = strcache; sp != NULL; sp = sp->next)
+  if (strcache)
     {
-      int bf = sp->bytesfree;
-      int sz = (sp->end - sp->buffer) + bf;
+      const struct strcache *sp;
+
+      /* Count the first buffer separately since it's not full.  */
+      lastused = strcache->end - strcache->buffer;
+      lastfree = strcache->bytesfree;
+
+      for (sp = strcache->next; sp != NULL; sp = sp->next)
+        {
+          int bf = sp->bytesfree;
+          int sz = sp->end - sp->buffer;
 
-      ++numbuffs;
-      numstrs += sp->count;
+          ++numbuffs;
+          numstrs += sp->count;
 
-      totsize += sz;
-      maxsize = (sz > maxsize ? sz : maxsize);
-      minsize = (sz < minsize ? sz : minsize);
+          totsize += sz;
+          maxsize = (sz > maxsize ? sz : maxsize);
+          minsize = (sz < minsize ? sz : minsize);
 
-      totfree += bf;
-      maxfree = (bf > maxfree ? bf : maxfree);
-      minfree = (bf < minfree ? bf : minfree);
+          totfree += bf;
+          maxfree = (bf > maxfree ? bf : maxfree);
+          minfree = (bf < minfree ? bf : minfree);
+        }
     }
 
   avgsize = numbuffs ? (int)(totsize / numbuffs) : 0;
   avgfree = numbuffs ? (int)(totfree / numbuffs) : 0;
 
-  printf (_("\n%s # of strings in strcache: %d\n"), prefix, numstrs);
-  printf (_("%s # of strcache buffers: %d\n"), prefix, numbuffs);
-  printf (_("%s strcache size: total = %d / max = %d / min = %d / avg = %d\n"),
-          prefix, totsize, maxsize, minsize, avgsize);
-  printf (_("%s strcache free: total = %d / max = %d / min = %d / avg = %d\n"),
-          prefix, totfree, maxfree, minfree, avgfree);
+  printf (_("\n%s # of strings in strcache: %d / lookups = %lu / hits = %lu\n"),
+          prefix, numstrs, total_adds, (total_adds - numstrs));
+  printf (_("%s # of strcache buffers: %d (* %d B/buffer = %d B)\n"),
+          prefix, (numbuffs + 1), bufsize, ((numbuffs + 1) * bufsize));
+  printf (_("%s strcache used: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
+          prefix, totsize, lastused, maxsize, minsize, avgsize);
+  printf (_("%s strcache free: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
+          prefix, totfree, lastfree, maxfree, minfree, avgfree);
+
+  fputs (_("\n# strcache hash-table stats:\n# "), stdout);
+  hash_print_stats (&strings, stdout);
 }