aboutsummaryrefslogtreecommitdiff
path: root/gdb/bcache.c
diff options
context:
space:
mode:
authorAndrew Cagney <cagney@redhat.com>2003-11-07 22:04:39 +0000
committerAndrew Cagney <cagney@redhat.com>2003-11-07 22:04:39 +0000
commit49df298f1fa4f80404f5dc1b496335abb924953e (patch)
tree08b6940f502cdc0c61237f4c88baf4cda971903e /gdb/bcache.c
parentf168dd8007e67f2572a89da61a25066944a0a3db (diff)
downloadgdb-49df298f1fa4f80404f5dc1b496335abb924953e.zip
gdb-49df298f1fa4f80404f5dc1b496335abb924953e.tar.gz
gdb-49df298f1fa4f80404f5dc1b496335abb924953e.tar.bz2
2003-11-07 Andrew Cagney <cagney@redhat.com>
* bcache.h: Update copyright. Add comments on bcache VS hashtab. * bcache.c (struct bstring): Make "length" an unsigned short, add "half_hash". (struct bcache): Add "half_hash_error_count". (bcache): Compute and save the "half_hash". Compare the "half_hash" before comparing the length. Update half_hash_error_count.
Diffstat (limited to 'gdb/bcache.c')
-rw-r--r--gdb/bcache.c39
1 files changed, 33 insertions, 6 deletions
diff --git a/gdb/bcache.c b/gdb/bcache.c
index 32454ce..ec8b777 100644
--- a/gdb/bcache.c
+++ b/gdb/bcache.c
@@ -38,8 +38,15 @@
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
{
@@ -79,6 +86,10 @@ struct bcache
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,
@@ -187,6 +198,8 @@ expand_hash_table (struct bcache *bcache)
void *
bcache (const void *addr, int length, struct bcache *bcache)
{
+ unsigned long full_hash;
+ unsigned short half_hash;
int hash_index;
struct bstring *s;
@@ -197,13 +210,24 @@ bcache (const void *addr, int length, struct bcache *bcache)
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. */
{
@@ -212,6 +236,7 @@ bcache (const void *addr, int length, struct bcache *bcache)
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++;
@@ -378,6 +403,8 @@ print_bcache_statistics (struct bcache *c, char *type)
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",