/* Constant string caching for GNU Make.
-Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
+Copyright (C) 2006-2013 Free Software Foundation, Inc.
This file is part of GNU Make.
GNU Make is free software; you can redistribute it and/or modify it under the
You should have received a copy of the GNU General Public License along with
this program. If not, see <http://www.gnu.org/licenses/>. */
-#include "make.h"
+#include "makeint.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
that this doesn't seem to be much of an issue in practice.
*/
static struct strcache *
-new_cache()
+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;
}
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))
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;
}
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. */
}
int
-strcache_setbufsize(int size)
+strcache_setbufsize (unsigned int size)
{
if (size > bufsize)
bufsize = size;
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);
}
projects / platform / upstream / make.git / blobdiff