From f1e1cc4695b34b292454e903adbf09e66cf2e9d5 Mon Sep 17 00:00:00 2001 From: Joshua Haberman Date: Thu, 17 Feb 2011 19:14:53 -0800 Subject: Split inttable into a hash part and an array part. upb_inttable() now supports a "compact" operation that will decide on an array size and put all entries with small enough keys into the array part for faster lookup. Also exposed the upb_itof_ent structure and put a few useful values there, so they are one fewer pointer chase away. --- src/upb_table.c | 360 +++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 253 insertions(+), 107 deletions(-) (limited to 'src/upb_table.c') diff --git a/src/upb_table.c b/src/upb_table.c index 720cc62..9a6cf7a 100644 --- a/src/upb_table.c +++ b/src/upb_table.c @@ -1,6 +1,8 @@ /* * upb - a minimalist implementation of protocol buffers. * + * There are a few printf's strewn throughout this file, uncommenting them + * can be useful for debugging. * Copyright (c) 2009 Joshua Haberman. See LICENSE for details. */ @@ -13,140 +15,294 @@ static const double MAX_LOAD = 0.85; +// The minimum percentage of an array part that we will allow. This is a +// speed/memory-usage tradeoff (though it's not straightforward because of +// cache effects). The lower this is, the more memory we'll use. +static const double MIN_DENSITY = 0.1; + static uint32_t MurmurHash2(const void *key, size_t len, uint32_t seed); -/* We use 1-based indexes into the table so that 0 can be "NULL". */ -static upb_inttable_entry *intent(upb_inttable *t, int32_t i) { - return UPB_INDEX(t->t.entries, i-1, t->t.entry_size); -} -static upb_strtable_entry *strent(upb_strtable *t, int32_t i) { - return UPB_INDEX(t->t.entries, i-1, t->t.entry_size); -} +/* Base table (shared code) ***************************************************/ -void upb_table_init(upb_table *t, uint32_t size, uint16_t entry_size) -{ +static uint32_t upb_table_size(upb_table *t) { return 1 << t->size_lg2; } +static size_t upb_table_entrysize(upb_table *t) { return t->entry_size; } +static size_t upb_table_valuesize(upb_table *t) { return t->value_size; } + +void upb_table_init(upb_table *t, uint32_t size, uint16_t entry_size) { t->count = 0; t->entry_size = entry_size; - t->size_lg2 = 0; - while(size >>= 1) t->size_lg2++; + t->size_lg2 = 1; + while(upb_table_size(t) < size) t->size_lg2++; size_t bytes = upb_table_size(t) * t->entry_size; t->mask = upb_table_size(t) - 1; t->entries = malloc(bytes); - memset(t->entries, 0, bytes); /* Both tables consider 0's an empty entry. */ } -void upb_inttable_init(upb_inttable *t, uint32_t size, uint16_t entsize) -{ - upb_table_init(&t->t, size, entsize); +void upb_table_free(upb_table *t) { free(t->entries); } + +/* upb_inttable ***************************************************************/ + +static upb_inttable_entry *intent(upb_inttable *t, int32_t i) { + //printf("looking up int entry %d, size of entry: %d\n", i, t->t.entry_size); + return UPB_INDEX(t->t.entries, i, t->t.entry_size); } -void upb_strtable_init(upb_strtable *t, uint32_t size, uint16_t entsize) -{ - upb_table_init(&t->t, size, entsize); +static uint32_t upb_inttable_hashtablesize(upb_inttable *t) { + return upb_table_size(&t->t); } -void upb_table_free(upb_table *t) { free(t->entries); } -void upb_inttable_free(upb_inttable *t) { upb_table_free(&t->t); } -void upb_strtable_free(upb_strtable *t) { - // Free refs from the strtable. - upb_strtable_entry *e = upb_strtable_begin(t); - for(; e; e = upb_strtable_next(t, e)) { - upb_string_unref(e->key); +void upb_inttable_sizedinit(upb_inttable *t, uint32_t arrsize, uint32_t hashsize, + uint16_t value_size) { + size_t entsize = _upb_inttable_entrysize(value_size); + upb_table_init(&t->t, hashsize, entsize); + for (uint32_t i = 0; i < upb_table_size(&t->t); i++) { + upb_inttable_entry *e = intent(t, i); + e->hdr.key = 0; + e->hdr.next = UPB_END_OF_CHAIN; + e->val.has_entry = 0; + } + t->t.value_size = value_size; + // Always make the array part at least 1 long, so that we know key 0 + // won't be in the hash part (which lets us speed up that code path). + t->array_size = UPB_MAX(1, arrsize); + t->array = malloc(upb_table_valuesize(&t->t) * t->array_size); + t->array_count = 0; + for (uint32_t i = 0; i < t->array_size; i++) { + upb_inttable_value *val = UPB_INDEX(t->array, i, upb_table_valuesize(&t->t)); + val->has_entry = false; } - upb_table_free(&t->t); } -static uint32_t strtable_bucket(upb_strtable *t, upb_string *key) -{ - uint32_t hash = MurmurHash2(upb_string_getrobuf(key), upb_string_len(key), 0); - return (hash & (upb_strtable_size(t)-1)) + 1; +void upb_inttable_init(upb_inttable *t, uint32_t hashsize, uint16_t value_size) { + upb_inttable_sizedinit(t, 0, hashsize, value_size); } -void *upb_strtable_lookup(upb_strtable *t, upb_string *key) -{ - uint32_t bucket = strtable_bucket(t, key); - upb_strtable_entry *e; - do { - e = strent(t, bucket); - if(e->key && upb_streql(e->key, key)) return e; - } while((bucket = e->next) != UPB_END_OF_CHAIN); - return NULL; +void upb_inttable_free(upb_inttable *t) { + upb_table_free(&t->t); + free(t->array); } static uint32_t empty_intbucket(upb_inttable *table) { - /* TODO: does it matter that this is biased towards the front of the table? */ - for(uint32_t i = 1; i <= upb_inttable_size(table); i++) { + // TODO: does it matter that this is biased towards the front of the table? + for(uint32_t i = 0; i < upb_inttable_hashtablesize(table); i++) { upb_inttable_entry *e = intent(table, i); - if(!e->has_entry) return i; + if(!e->val.has_entry) return i; } assert(false); return 0; } -/* The insert routines have a lot more code duplication between int/string - * variants than I would like, but there's just a bit too much that varies to - * parameterize them. */ -static void intinsert(upb_inttable *t, upb_inttable_entry *e) -{ - assert(upb_inttable_lookup(t, e->key) == NULL); - t->t.count++; - uint32_t bucket = upb_inttable_bucket(t, e->key); - upb_inttable_entry *table_e = intent(t, bucket); - if(table_e->has_entry) { /* Collision. */ - if(bucket == upb_inttable_bucket(t, table_e->key)) { - /* Existing element is in its main posisiton. Find an empty slot to - * place our new element and append it to this key's chain. */ - uint32_t empty_bucket = empty_intbucket(t); - while (table_e->next != UPB_END_OF_CHAIN) - table_e = intent(t, table_e->next); - table_e->next = empty_bucket; - table_e = intent(t, empty_bucket); - } else { - /* Existing element is not in its main position. Move it to an empty - * slot and put our element in its main position. */ - uint32_t empty_bucket = empty_intbucket(t); - uint32_t evictee_bucket = upb_inttable_bucket(t, table_e->key); - memcpy(intent(t, empty_bucket), table_e, t->t.entry_size); /* copies next */ - upb_inttable_entry *evictee_e = intent(t, evictee_bucket); - while(1) { - assert(evictee_e->has_entry); - assert(evictee_e->next != UPB_END_OF_CHAIN); - if(evictee_e->next == bucket) { - evictee_e->next = empty_bucket; - break; +// The insert routines have a lot more code duplication between int/string +// variants than I would like, but there's just a bit too much that varies to +// parameterize them. +static void intinsert(upb_inttable *t, upb_inttable_key_t key, void *val) { + assert(upb_inttable_lookup(t, key) == NULL); + upb_inttable_value *table_val; + if (_upb_inttable_isarrkey(t, key)) { + table_val = UPB_INDEX(t->array, key, upb_table_valuesize(&t->t)); + //printf("Inserting key %d to Array part! %p\n", key, table_val); + } else { + t->t.count++; + uint32_t bucket = _upb_inttable_bucket(t, key); + upb_inttable_entry *table_e = intent(t, bucket); + //printf("Hash part! Inserting into bucket %d?\n", bucket); + if(table_e->val.has_entry) { /* Collision. */ + //printf("Collision!\n"); + if(bucket == _upb_inttable_bucket(t, table_e->hdr.key)) { + /* Existing element is in its main posisiton. Find an empty slot to + * place our new element and append it to this key's chain. */ + uint32_t empty_bucket = empty_intbucket(t); + while (table_e->hdr.next != UPB_END_OF_CHAIN) + table_e = intent(t, table_e->hdr.next); + table_e->hdr.next = empty_bucket; + table_e = intent(t, empty_bucket); + } else { + /* Existing element is not in its main position. Move it to an empty + * slot and put our element in its main position. */ + uint32_t empty_bucket = empty_intbucket(t); + uint32_t evictee_bucket = _upb_inttable_bucket(t, table_e->hdr.key); + memcpy(intent(t, empty_bucket), table_e, t->t.entry_size); /* copies next */ + upb_inttable_entry *evictee_e = intent(t, evictee_bucket); + while(1) { + assert(evictee_e->val.has_entry); + assert(evictee_e->hdr.next != UPB_END_OF_CHAIN); + if(evictee_e->hdr.next == bucket) { + evictee_e->hdr.next = empty_bucket; + break; + } + evictee_e = intent(t, evictee_e->hdr.next); } - evictee_e = intent(t, evictee_e->next); + /* table_e remains set to our mainpos. */ } - /* table_e remains set to our mainpos. */ } + //printf("Inserting! to:%p, copying to: %p\n", table_e, &table_e->val); + table_val = &table_e->val; + table_e->hdr.key = key; + table_e->hdr.next = UPB_END_OF_CHAIN; } - memcpy(table_e, e, t->t.entry_size); - table_e->next = UPB_END_OF_CHAIN; - table_e->has_entry = true; - assert(upb_inttable_lookup(t, e->key) == table_e); + memcpy(table_val, val, upb_table_valuesize(&t->t)); + table_val->has_entry = true; + assert(upb_inttable_lookup(t, key) == table_val); } -void upb_inttable_insert(upb_inttable *t, upb_inttable_entry *e) -{ - if((double)(t->t.count + 1) / upb_inttable_size(t) > MAX_LOAD) { - /* Need to resize. New table of double the size, add old elements to it. */ +// Insert all elements from src into dest. Caller ensures that a resize will +// not be necessary. +static void upb_inttable_insertall(upb_inttable *dst, upb_inttable *src) { + for(upb_inttable_iter i = upb_inttable_begin(src); !upb_inttable_done(i); + i = upb_inttable_next(src, i)) { + //printf("load check: %d %d\n", upb_inttable_count(dst), upb_inttable_hashtablesize(dst)); + assert((double)(upb_inttable_count(dst)) / + upb_inttable_hashtablesize(dst) <= MAX_LOAD); + intinsert(dst, upb_inttable_iter_key(i), upb_inttable_iter_value(i)); + } +} + +void upb_inttable_insert(upb_inttable *t, upb_inttable_key_t key, void *val) { + if((double)(t->t.count + 1) / upb_inttable_hashtablesize(t) > MAX_LOAD) { + //printf("RESIZE!\n"); + // Need to resize. Allocate new table with double the size of however many + // elements we have now, add old elements to it. We create the new hash + // table without an array part, even if the old table had an array part. + // If/when the user calls upb_inttable_compact() again, we'll create an + // array part then. upb_inttable new_table; - upb_inttable_init(&new_table, upb_inttable_size(t)*2, t->t.entry_size); - new_table.t.count = t->t.count; - upb_inttable_entry *old_e; - for(old_e = upb_inttable_begin(t); old_e; old_e = upb_inttable_next(t, old_e)) - intinsert(&new_table, old_e); + //printf("Old table count=%d, size=%d\n", upb_inttable_count(t), upb_inttable_hashtablesize(t)); + upb_inttable_init(&new_table, upb_inttable_count(t)*2, upb_table_valuesize(&t->t)); + upb_inttable_insertall(&new_table, t); upb_inttable_free(t); *t = new_table; } - intinsert(t, e); + intinsert(t, key, val); +} + +void upb_inttable_compact(upb_inttable *t) { + // Find the largest array part we can that satisfies the MIN_DENSITY + // definition. For now we just count down powers of two. + upb_inttable_key_t largest_key = 0; + for(upb_inttable_iter i = upb_inttable_begin(t); !upb_inttable_done(i); + i = upb_inttable_next(t, i)) { + largest_key = UPB_MAX(largest_key, upb_inttable_iter_key(i)); + } + int lg2_array = 0; + while ((1UL << lg2_array) < largest_key) ++lg2_array; + ++lg2_array; // Undo the first iteration. + size_t array_size; + int array_count; + while (lg2_array > 0) { + array_size = (1 << --lg2_array); + //printf("Considering size %d (btw, our table has %d things total)\n", array_size, upb_inttable_count(t)); + if ((double)upb_inttable_count(t) / array_size < MIN_DENSITY) { + // Even if 100% of the keys were in the array pary, an array of this + // size would not be dense enough. + continue; + } + array_count = 0; + for(upb_inttable_iter i = upb_inttable_begin(t); !upb_inttable_done(i); + i = upb_inttable_next(t, i)) { + if (upb_inttable_iter_key(i) < array_size) + array_count++; + } + //printf("There would be %d things in that array\n", array_count); + if ((double)array_count / array_size >= MIN_DENSITY) break; + } + upb_inttable new_table; + int hash_size = (upb_inttable_count(t) - array_count + 1) / MAX_LOAD; + upb_inttable_sizedinit(&new_table, array_size, hash_size, + upb_table_valuesize(&t->t)); + //printf("For %d things, using array size=%d, hash_size = %d\n", upb_inttable_count(t), array_size, hash_size); + upb_inttable_insertall(&new_table, t); + upb_inttable_free(t); + *t = new_table; +} + +upb_inttable_iter upb_inttable_begin(upb_inttable *t) { + upb_inttable_iter iter = {-1, NULL, true}; // -1 will overflow to 0 on the first iteration. + return upb_inttable_next(t, iter); +} + +upb_inttable_iter upb_inttable_next(upb_inttable *t, upb_inttable_iter iter) { + const size_t hdrsize = sizeof(upb_inttable_header); + const size_t entsize = upb_table_entrysize(&t->t); + if (iter.array_part) { + while (++iter.key < t->array_size) { + //printf("considering value %d\n", iter.key); + iter.value = UPB_INDEX(t->array, iter.key, t->t.value_size); + if (iter.value->has_entry) return iter; + } + //printf("Done with array part!\n"); + iter.array_part = false; + // Point to the value of the table[-1] entry. + iter.value = UPB_INDEX(intent(t, -1), 1, hdrsize); + } + void *end = intent(t, upb_inttable_hashtablesize(t)); + // Point to the entry for the value that was previously in iter. + upb_inttable_entry *e = UPB_INDEX(iter.value, -1, hdrsize); + do { + e = UPB_INDEX(e, 1, entsize); + //printf("considering value %p (val: %p)\n", e, &e->val); + if(e == end) { + //printf("No values.\n"); + iter.value = NULL; + return iter; + } + } while(!e->val.has_entry); + //printf("USING VALUE! %p\n", e); + iter.key = e->hdr.key; + iter.value = &e->val; + return iter; +} + + +/* upb_strtable ***************************************************************/ + +static upb_strtable_entry *strent(upb_strtable *t, int32_t i) { + return UPB_INDEX(t->t.entries, i, t->t.entry_size); +} + +static uint32_t upb_strtable_size(upb_strtable *t) { + return upb_table_size(&t->t); +} + +void upb_strtable_init(upb_strtable *t, uint32_t size, uint16_t entsize) { + upb_table_init(&t->t, size, entsize); + for (uint32_t i = 0; i < upb_table_size(&t->t); i++) { + upb_strtable_entry *e = strent(t, i); + e->key = NULL; + e->next = UPB_END_OF_CHAIN; + } +} + +void upb_strtable_free(upb_strtable *t) { + // Free refs from the strtable. + upb_strtable_entry *e = upb_strtable_begin(t); + for(; e; e = upb_strtable_next(t, e)) { + upb_string_unref(e->key); + } + upb_table_free(&t->t); +} + +static uint32_t strtable_bucket(upb_strtable *t, upb_string *key) +{ + uint32_t hash = MurmurHash2(upb_string_getrobuf(key), upb_string_len(key), 0); + return (hash & t->t.mask); +} + +void *upb_strtable_lookup(upb_strtable *t, upb_string *key) +{ + uint32_t bucket = strtable_bucket(t, key); + upb_strtable_entry *e; + do { + e = strent(t, bucket); + if(e->key && upb_streql(e->key, key)) return e; + } while((bucket = e->next) != UPB_END_OF_CHAIN); + return NULL; } static uint32_t empty_strbucket(upb_strtable *table) { - /* TODO: does it matter that this is biased towards the front of the table? */ - for(uint32_t i = 1; i <= upb_strtable_size(table); i++) { + // TODO: does it matter that this is biased towards the front of the table? + for(uint32_t i = 0; i < upb_strtable_size(table); i++) { upb_strtable_entry *e = strent(table, i); if(!e->key) return i; } @@ -191,13 +347,16 @@ static void strinsert(upb_strtable *t, upb_strtable_entry *e) } memcpy(table_e, e, t->t.entry_size); table_e->next = UPB_END_OF_CHAIN; + //printf("Looking up, string=" UPB_STRFMT "...\n", UPB_STRARG(e->key)); assert(upb_strtable_lookup(t, e->key) == table_e); + //printf("Yay!\n"); } void upb_strtable_insert(upb_strtable *t, upb_strtable_entry *e) { if((double)(t->t.count + 1) / upb_strtable_size(t) > MAX_LOAD) { - /* Need to resize. New table of double the size, add old elements to it. */ + // Need to resize. New table of double the size, add old elements to it. + //printf("RESIZE!!\n"); upb_strtable new_table; upb_strtable_init(&new_table, upb_strtable_size(t)*2, t->t.entry_size); upb_strtable_entry *old_e; @@ -209,25 +368,12 @@ void upb_strtable_insert(upb_strtable *t, upb_strtable_entry *e) strinsert(t, e); } -void *upb_inttable_begin(upb_inttable *t) { - return upb_inttable_next(t, intent(t, 0)); -} - -void *upb_inttable_next(upb_inttable *t, upb_inttable_entry *cur) { - upb_inttable_entry *end = intent(t, upb_inttable_size(t)+1); - do { - cur = (void*)((char*)cur + t->t.entry_size); - if(cur == end) return NULL; - } while(!cur->has_entry); - return cur; -} - void *upb_strtable_begin(upb_strtable *t) { - return upb_strtable_next(t, strent(t, 0)); + return upb_strtable_next(t, strent(t, -1)); } void *upb_strtable_next(upb_strtable *t, upb_strtable_entry *cur) { - upb_strtable_entry *end = strent(t, upb_strtable_size(t)+1); + upb_strtable_entry *end = strent(t, upb_strtable_size(t)); do { cur = (void*)((char*)cur + t->t.entry_size); if(cur == end) return NULL; -- cgit v1.2.3