* Fixups to the make man page

* Minor syntax cleanups in the manual
* In non-maintainer mode set NDEBUG to disable assert()
* Performance improvements in strcache:
    Build Info			1000	2000	4000
    3.82 -g			2.61s	8.85s	33.52s
    3.82 -O2			1.90s	7.62s	27.82s
    New -g (with asserts)	1.03s	2.31s	5.79s
    New -O2 (no asserts)	0.65s	1.50s	3.52s

1 files changed, 118 insertions, 73 deletions

diff --git a/strcache.c b/strcache.c
index 830ec7d..d256e83 100644
--- a/strcache.c
+++ b/strcache.c
@@ -16,29 +16,40 @@ this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 #include "make.h"
 
+#include <stddef.h>
 #include <assert.h>
 
 #include "hash.h"
 
-/* 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
    reference counting.  We just store the string, and then remember it in a
    hash so it can be looked up again. */
 
+typedef unsigned short int sc_buflen_t;
+
 struct strcache {
-  struct strcache *next;    /* The next block of strings.  */
-  char *end;                /* Pointer to the beginning of the free space.  */
-  int count;                /* # of strings in this buffer (for stats).  */
-  int bytesfree;            /* The amount of the buffer that is free.  */
+  struct strcache *next;    /* The next block of strings.  Must be first!  */
+  sc_buflen_t end;          /* Offset to the beginning of free space.  */
+  sc_buflen_t bytesfree;    /* Free space left in this buffer.  */
+  sc_buflen_t count;        /* # of strings in this buffer (for stats).  */
   char buffer[1];           /* The buffer comes after this.  */
 };
 
-static int bufsize = CACHE_BUFFER_SIZE;
+/* The size (in bytes) of each cache buffer.
+   Try to pick something that will map well into the heap.
+   This must be able to be represented by a short int (<=65535).  */
+#define CACHE_BUFFER_BASE       (8192)
+#define CACHE_BUFFER_ALLOC(_s)  ((_s) - (2 * sizeof (size_t)))
+#define CACHE_BUFFER_OFFSET     (offsetof (struct strcache, buffer))
+#define CACHE_BUFFER_SIZE(_s)   (CACHE_BUFFER_ALLOC(_s) - CACHE_BUFFER_OFFSET)
+
+static sc_buflen_t bufsize = CACHE_BUFFER_SIZE (CACHE_BUFFER_BASE);
 static struct strcache *strcache = NULL;
+static struct strcache *fullcache = NULL;
+
+static unsigned long total_buffers = 0;
+static unsigned long total_strings = 0;
+static unsigned long total_size = 0;
 
 /* 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
@@ -49,50 +60,65 @@ static struct strcache *
 new_cache()
 {
   struct strcache *new;
-  new = xmalloc (sizeof (*new) + bufsize);
-  new->end = new->buffer;
+  new = xmalloc (bufsize + CACHE_BUFFER_OFFSET);
+  new->end = 0;
   new->count = 0;
   new->bytesfree = bufsize;
 
   new->next = strcache;
   strcache = new;
 
+  ++total_buffers;
   return new;
 }
 
 static const char *
-add_string(const char *str, int len)
+add_string (const char *str, unsigned int len)
 {
-  struct strcache *best = NULL;
+  char *res;
   struct strcache *sp;
-  const char *res;
+  struct strcache **spp = &strcache;
+  /* We need space for the nul char.  */
+  unsigned int sz = len + 1;
 
   /* 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;
-
-  /* First, find a cache with enough free space.  We always look through all
-     the blocks and choose the one with the best fit (the one that leaves the
-     least amount of space free).  */
-  for (sp = strcache; sp != NULL; sp = sp->next)
-    if (sp->bytesfree > len && (!best || best->bytesfree > sp->bytesfree))
-      best = sp;
+     no existing cache is large enough.  Change the maximum size.  */
+  if (sz > bufsize)
+    bufsize = CACHE_BUFFER_SIZE ((((sz + 1) / CACHE_BUFFER_BASE) + 1)
+                                 * CACHE_BUFFER_BASE);
+  else
+    /* Find the first cache with enough free space.  */
+    for (; *spp != NULL; spp = &(*spp)->next)
+      if ((*spp)->bytesfree > sz)
+        break;
 
   /* If nothing is big enough, make a new cache.  */
-  if (!best)
-    best = new_cache();
+  sp = *spp;
+  if (sp == NULL)
+    {
+      sp = new_cache ();
+      spp = &sp;
+    }
+
+  /* Add the string to this cache.  */
+  res = &sp->buffer[sp->end];
+  memmove (res, str, len);
+  res[len] = '\0';
+  sp->end += sz;
+  sp->bytesfree -= sz;
+  ++sp->count;
 
-  assert (best->bytesfree > len);
+  /* If the amount free in this cache is less than the average string size,
+     consider it full and move it to the full list.  */
+  ++total_strings;
+  total_size += sz;
 
-  /* Add the string to the best cache.  */
-  res = best->end;
-  memcpy (best->end, str, len);
-  best->end += len;
-  *(best->end++) = '\0';
-  best->bytesfree -= len + 1;
-  ++best->count;
+  if (sp->bytesfree < (total_size / total_strings) + 1)
+    {
+      *spp = (*spp)->next;
+      sp->next = fullcache;
+      fullcache = sp;
+    }
 
   return res;
 }
@@ -128,7 +154,7 @@ 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.  */
+  /* Count the total number of add operations we performed.  */
   ++total_adds;
 
   if (!HASH_VACANT (key))
@@ -147,7 +173,10 @@ strcache_iscached (const char *str)
   struct strcache *sp;
 
   for (sp = strcache; sp != 0; sp = sp->next)
-    if (str >= sp->buffer && str < sp->end)
+    if (str >= sp->buffer && str < sp->buffer + sp->end)
+      return 1;
+  for (sp = fullcache; sp != 0; sp = sp->next)
+    if (str >= sp->buffer && str < sp->buffer + sp->end)
       return 1;
 
   return 0;
@@ -163,7 +192,7 @@ strcache_add (const char *str)
 }
 
 const char *
-strcache_add_len (const char *str, int len)
+strcache_add_len (const char *str, unsigned int len)
 {
   /* If we're not given a nul-terminated string we have to create one, because
      the hashing functions expect it.  */
@@ -179,7 +208,7 @@ strcache_add_len (const char *str, int len)
 }
 
 int
-strcache_setbufsize(int size)
+strcache_setbufsize(unsigned int size)
 {
   if (size > bufsize)
     bufsize = size;
@@ -198,49 +227,65 @@ strcache_init (void)
 void
 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;
-  int lastused = 0, lastfree = 0;
+  const struct strcache *sp;
+  unsigned long numbuffs = 0, fullbuffs = 0;
+  unsigned long totfree = 0, maxfree = 0, minfree = bufsize;
 
-  if (strcache)
+  if (! strcache)
     {
-      const struct strcache *sp;
+      printf(_("\n%s No strcache buffers\n"), prefix);
+      return;
+    }
 
-      /* Count the first buffer separately since it's not full.  */
-      lastused = strcache->end - strcache->buffer;
-      lastfree = strcache->bytesfree;
+  /* Count the first buffer separately since it's not full.  */
+  for (sp = strcache->next; sp != NULL; sp = sp->next)
+    {
+      sc_buflen_t bf = sp->bytesfree;
 
-      for (sp = strcache->next; sp != NULL; sp = sp->next)
-        {
-          int bf = sp->bytesfree;
-          int sz = sp->end - sp->buffer;
+      totfree += bf;
+      maxfree = (bf > maxfree ? bf : maxfree);
+      minfree = (bf < minfree ? bf : minfree);
 
-          ++numbuffs;
-          numstrs += sp->count;
+      ++numbuffs;
+    }
+  for (sp = fullcache; sp != NULL; sp = sp->next)
+    {
+      sc_buflen_t bf = sp->bytesfree;
 
-          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);
-        }
+      ++numbuffs;
+      ++fullbuffs;
     }
 
-  avgsize = numbuffs ? (int)(totsize / numbuffs) : 0;
-  avgfree = numbuffs ? (int)(totfree / numbuffs) : 0;
+  /* Make sure we didn't lose any buffers.  */
+  assert (total_buffers == numbuffs + 1);
+
+  printf (_("\n%s strcache buffers: %lu (%lu) / strings = %lu / storage = %lu B / avg = %lu B\n"),
+          prefix, numbuffs + 1, fullbuffs, total_strings, total_size,
+          (total_size / total_strings));
 
-  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);
+  printf (_("%s current buf: size = %hu B / used = %hu B / count = %hu / avg = %hu B\n"),
+          prefix, bufsize, strcache->end, strcache->count,
+          (strcache->end / strcache->count));
+
+  if (numbuffs)
+    {
+      unsigned long sz = total_size - bufsize;
+      unsigned long cnt = total_strings - strcache->count;
+      sc_buflen_t avgfree = totfree / numbuffs;
+
+      printf (_("%s other used: total = %lu B / count = %lu / avg = %lu B\n"),
+              prefix, sz, cnt, sz / cnt);
+
+      printf (_("%s other free: total = %lu B / max = %lu B / min = %lu B / avg = %hu B\n"),
+              prefix, totfree, maxfree, minfree, avgfree);
+    }
 
-  fputs (_("\n# strcache hash-table stats:\n# "), stdout);
+  printf (_("\n%s strcache performance: lookups = %lu / hit rate = %lu%%\n"),
+          prefix, total_adds, (long unsigned)(100.0 * (total_adds - total_strings) / total_adds));
+  fputs (_("# hash-table stats:\n# "), stdout);
   hash_print_stats (&strings, stdout);
 }