summaryrefslogtreecommitdiff
path: root/strcache.c
diff options
context:
space:
mode:
Diffstat (limited to 'strcache.c')
-rw-r--r--strcache.c191
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);
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-08 19:51:21 +0000