From 1454a04f81708850353dbdc0807a099c5aaab55b Mon Sep 17 00:00:00 2001 From: Paul Smith Date: Mon, 21 Feb 2011 07:30:11 +0000 Subject: * 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 --- strcache.c | 191 ++++++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 118 insertions(+), 73 deletions(-) (limited to 'strcache.c') 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 . */ #include "make.h" +#include #include #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); } -- cgit v1.2.3