Written by Fred Fish <fnf@cygnus.com>
Rewritten by Jim Blandy <jimb@cygnus.com>
- Copyright 1999, 2000, 2002 Free Software Foundation, Inc.
+ Copyright 1999, 2000, 2002, 2003 Free Software Foundation, Inc.
This file is part of GDB.
#include "gdb_obstack.h"
#include "bcache.h"
#include "gdb_string.h" /* For memcpy declaration */
+#include "gdb_assert.h"
#include <stddef.h>
#include <stdlib.h>
struct bstring
{
+ /* Hash chain. */
struct bstring *next;
- size_t length;
+ /* Assume the data length is no more than 64k. */
+ unsigned short length;
+ /* The half hash hack. This contains the upper 16 bits of the hash
+ value and is used as a pre-check when comparing two strings and
+ avoids the need to do length or memcmp calls. It proves to be
+ roughly 100% effective. */
+ unsigned short half_hash;
union
{
long unique_size; /* size of unique strings, in bytes */
long total_size; /* total number of bytes cached, including dups */
long structure_size; /* total size of bcache, including infrastructure */
+ /* Number of times that the hash table is expanded and hence
+ re-built, and the corresponding number of times that a string is
+ [re]hashed as part of entering it into the expanded table. The
+ total number of hashes can be computed by adding TOTAL_COUNT to
+ expand_hash_count. */
+ unsigned long expand_count;
+ unsigned long expand_hash_count;
+ /* Number of times that the half-hash compare hit (compare the upper
+ 16 bits of hash values) hit, but the corresponding combined
+ length/data compare missed. */
+ unsigned long half_hash_miss_count;
};
/* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
struct bstring **new_buckets;
unsigned int i;
+ /* Count the stats. Every unique item needs to be re-hashed and
+ re-entered. */
+ bcache->expand_count++;
+ bcache->expand_hash_count += bcache->unique_count;
+
/* Find the next size. */
new_num_buckets = bcache->num_buckets * 2;
for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
/* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
never seen those bytes before, add a copy of them to BCACHE. In
either case, return a pointer to BCACHE's copy of that string. */
-void *
-bcache (const void *addr, int length, struct bcache *bcache)
+static void *
+bcache_data (const void *addr, int length, struct bcache *bcache)
{
+ unsigned long full_hash;
+ unsigned short half_hash;
int hash_index;
struct bstring *s;
bcache->total_count++;
bcache->total_size += length;
- hash_index = hash (addr, length) % bcache->num_buckets;
+ full_hash = hash (addr, length);
+ half_hash = (full_hash >> 16);
+ hash_index = full_hash % bcache->num_buckets;
- /* Search the hash bucket for a string identical to the caller's. */
+ /* Search the hash bucket for a string identical to the caller's.
+ As a short-circuit first compare the upper part of each hash
+ values. */
for (s = bcache->bucket[hash_index]; s; s = s->next)
- if (s->length == length
- && ! memcmp (&s->d.data, addr, length))
- return &s->d.data;
+ {
+ if (s->half_hash == half_hash)
+ {
+ if (s->length == length
+ && ! memcmp (&s->d.data, addr, length))
+ return &s->d.data;
+ else
+ bcache->half_hash_miss_count++;
+ }
+ }
/* The user's string isn't in the list. Insert it after *ps. */
{
memcpy (&new->d.data, addr, length);
new->length = length;
new->next = bcache->bucket[hash_index];
+ new->half_hash = half_hash;
bcache->bucket[hash_index] = new;
bcache->unique_count++;
}
}
+void *
+deprecated_bcache (const void *addr, int length, struct bcache *bcache)
+{
+ return bcache_data (addr, length, bcache);
+}
+
+const void *
+bcache (const void *addr, int length, struct bcache *bcache)
+{
+ return bcache_data (addr, length, bcache);
+}
\f
/* Allocating and freeing bcaches. */
{
/* Allocate the bcache pre-zeroed. */
struct bcache *b = XCALLOC (1, struct bcache);
- obstack_specify_allocation (&b->cache, 0, 0, xmalloc, xfree);
+ /* We could use obstack_specify_allocation here instead, but
+ gdb_obstack.h specifies the allocation/deallocation
+ functions. */
+ obstack_init (&b->cache);
return b;
}
print_percentage (int portion, int total)
{
if (total == 0)
- printf_filtered ("(not applicable)\n");
+ /* i18n: Like "Percentage of duplicates, by count: (not applicable)" */
+ printf_filtered (_("(not applicable)\n"));
else
- printf_filtered ("%3d%%\n", portion * 100 / total);
+ printf_filtered ("%3d%%\n", (int) (portion * 100.0 / total));
}
int occupied_buckets;
int max_chain_length;
int median_chain_length;
+ int max_entry_size;
+ int median_entry_size;
- /* Count the number of occupied buckets, and measure chain lengths. */
+ /* Count the number of occupied buckets, tally the various string
+ lengths, and measure chain lengths. */
{
unsigned int b;
- int *chain_length
- = (int *) alloca (c->num_buckets * sizeof (*chain_length));
+ int *chain_length = XCALLOC (c->num_buckets + 1, int);
+ int *entry_size = XCALLOC (c->unique_count + 1, int);
+ int stringi = 0;
occupied_buckets = 0;
while (s)
{
+ gdb_assert (b < c->num_buckets);
chain_length[b]++;
+ gdb_assert (stringi < c->unique_count);
+ entry_size[stringi++] = s->length;
s = s->next;
}
}
/* To compute the median, we need the set of chain lengths sorted. */
qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
compare_ints);
+ qsort (entry_size, c->unique_count, sizeof (entry_size[0]),
+ compare_ints);
if (c->num_buckets > 0)
{
max_chain_length = 0;
median_chain_length = 0;
}
+ if (c->unique_count > 0)
+ {
+ max_entry_size = entry_size[c->unique_count - 1];
+ median_entry_size = entry_size[c->unique_count / 2];
+ }
+ else
+ {
+ max_entry_size = 0;
+ median_entry_size = 0;
+ }
+
+ xfree (chain_length);
+ xfree (entry_size);
}
- printf_filtered (" Cached '%s' statistics:\n", type);
- printf_filtered (" Total object count: %ld\n", c->total_count);
- printf_filtered (" Unique object count: %lu\n", c->unique_count);
- printf_filtered (" Percentage of duplicates, by count: ");
+ printf_filtered (_(" Cached '%s' statistics:\n"), type);
+ printf_filtered (_(" Total object count: %ld\n"), c->total_count);
+ printf_filtered (_(" Unique object count: %lu\n"), c->unique_count);
+ printf_filtered (_(" Percentage of duplicates, by count: "));
print_percentage (c->total_count - c->unique_count, c->total_count);
printf_filtered ("\n");
- printf_filtered (" Total object size: %ld\n", c->total_size);
- printf_filtered (" Unique object size: %ld\n", c->unique_size);
- printf_filtered (" Percentage of duplicates, by size: ");
+ printf_filtered (_(" Total object size: %ld\n"), c->total_size);
+ printf_filtered (_(" Unique object size: %ld\n"), c->unique_size);
+ printf_filtered (_(" Percentage of duplicates, by size: "));
print_percentage (c->total_size - c->unique_size, c->total_size);
printf_filtered ("\n");
- printf_filtered (" Total memory used by bcache, including overhead: %ld\n",
+ printf_filtered (_(" Max entry size: %d\n"), max_entry_size);
+ printf_filtered (_(" Average entry size: "));
+ if (c->unique_count > 0)
+ printf_filtered ("%ld\n", c->unique_size / c->unique_count);
+ else
+ /* i18n: "Average entry size: (not applicable)" */
+ printf_filtered (_("(not applicable)\n"));
+ printf_filtered (_(" Median entry size: %d\n"), median_entry_size);
+ printf_filtered ("\n");
+
+ printf_filtered (_(" Total memory used by bcache, including overhead: %ld\n"),
c->structure_size);
- printf_filtered (" Percentage memory overhead: ");
+ printf_filtered (_(" Percentage memory overhead: "));
print_percentage (c->structure_size - c->unique_size, c->unique_size);
- printf_filtered (" Net memory savings: ");
+ printf_filtered (_(" Net memory savings: "));
print_percentage (c->total_size - c->structure_size, c->total_size);
printf_filtered ("\n");
- printf_filtered (" Hash table size: %3d\n", c->num_buckets);
- printf_filtered (" Hash table population: ");
+ printf_filtered (_(" Hash table size: %3d\n"), c->num_buckets);
+ printf_filtered (_(" Hash table expands: %lu\n"),
+ c->expand_count);
+ printf_filtered (_(" Hash table hashes: %lu\n"),
+ c->total_count + c->expand_hash_count);
+ printf_filtered (_(" Half hash misses: %lu\n"),
+ c->half_hash_miss_count);
+ printf_filtered (_(" Hash table population: "));
print_percentage (occupied_buckets, c->num_buckets);
- printf_filtered (" Median hash chain length: %3d\n",
+ printf_filtered (_(" Median hash chain length: %3d\n"),
median_chain_length);
- printf_filtered (" Average hash chain length: ");
+ printf_filtered (_(" Average hash chain length: "));
if (c->num_buckets > 0)
printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
else
- printf_filtered ("(not applicable)\n");
- printf_filtered (" Maximum hash chain length: %3d\n", max_chain_length);
+ /* i18n: "Average hash chain length: (not applicable)" */
+ printf_filtered (_("(not applicable)\n"));
+ printf_filtered (_(" Maximum hash chain length: %3d\n"), max_chain_length);
printf_filtered ("\n");
}