From 5ec762a6006959a9ef37b4e7855702d621481b2f Mon Sep 17 00:00:00 2001 From: Joshua Haberman Date: Mon, 15 Jun 2009 09:07:12 -0700 Subject: Added TODO about experimenting with Cuckoo Hashing. --- upb_table.h | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'upb_table.h') diff --git a/upb_table.h b/upb_table.h index 41cc2f7..5a23ae5 100644 --- a/upb_table.h +++ b/upb_table.h @@ -64,6 +64,11 @@ inline struct upb_inttable_entry *upb_inttable_mainpos( inline void *upb_inttable_lookup(struct upb_inttable *table, int32_t key, int32_t entry_size) { + /* TODO: experiment with Cuckoo Hashing, which can perform lookups without + * any branches, cf: + * http://www.cs.cmu.edu/~damon2006/pdf/zukowski06archconscioushashing.pdf. + * The tradeoff is having to calculate a second hash for every lookup, which + * will hurt the simple array case. */ struct upb_inttable_entry *e = upb_inttable_mainpos2(table, key, entry_size); do { if (key == e->key) return e; -- cgit v1.2.3