Changeset 903 in kBuild for trunk/src/gmakenew/strcache.c

Timestamp:

May 23, 2007 5:31:19 AM (18 years ago)

Author:

bird

Message:

Merged with the 2007-05-23 CVS. Added rsort and fixed a couple of windows build issues.

File:

• trunk/src/gmakenew/strcache.c (modified) (9 diffs)

trunk/src/gmakenew/strcache.c

@@ -21 +21 @@
 #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)
 
 
@@ -40 +41 @@
 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()
 {
   struct strcache *new;
-  new = (struct strcache *) xmalloc (sizeof (*new) + bufsize);
+  new = xmalloc (sizeof (*new) + bufsize);
   new->end = new->buffer;
   new->count = 0;
@@ -62 +68 @@
   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;
@@ -114 +120 @@
 
 static struct hash_table strings;
+static unsigned long total_adds = 0;
 
 static const char *
@@ -119 +126 @@
 {
   /* Look up the string in the hash.  If it's there, return it.  */
-  char **slot = (char **) hash_find_slot (&strings, str);
+  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))
@@ -156 +166 @@
 strcache_add_len (const char *str, int len)
 {
-  char *key = alloca (len + 1);
-  memcpy (key, str, len);
-  key[len] = '\0';
-
-  return add_hash (key, len);
+  /* If we're not given a nul-terminated string we have to create one, because
+     the hashing functions expect it.  */
+  if (str[len] != '\0')
+    {
+      char *key = alloca (len + 1);
+      memcpy (key, str, len);
+      key[len] = '\0';
+      str = key;
+    }
+
+  return add_hash (str, len);
 }
 
@@ -174 +190 @@
 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);
 }
 
@@ -186 +202 @@
   int totsize = 0, avgsize, maxsize = 0, minsize = bufsize;
   int totfree = 0, avgfree, maxfree = 0, minfree = bufsize;
-  const struct strcache *sp;
-
-  for (sp = strcache; sp != NULL; sp = sp->next)
+  int lastused = 0, lastfree = 0;
+
+  if (strcache)
     {
-      int bf = sp->bytesfree;
-      int sz = (sp->end - sp->buffer) + bf;
-
-      ++numbuffs;
-      numstrs += sp->count;
-
-      totsize += sz;
-      maxsize = (sz > maxsize ? sz : maxsize);
-      minsize = (sz < minsize ? sz : minsize);
-
-      totfree += bf;
-      maxfree = (bf > maxfree ? bf : maxfree);
-      minfree = (bf < minfree ? bf : minfree);
+      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;
+
+          totsize += sz;
+          maxsize = (sz > maxsize ? sz : maxsize);
+          minsize = (sz < minsize ? sz : minsize);
+
+          totfree += bf;
+          maxfree = (bf > maxfree ? bf : maxfree);
+          minfree = (bf < minfree ? bf : minfree);
+        }
     }
 
@@ -208 +233 @@
   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);
+}