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.

6 files changed, 413 insertions, 194 deletions

diff --git a/src/upb.h b/src/upb.h
index 837fc52..c5b4310 100644
--- a/src/upb.h
+++ b/src/upb.h
@@ -29,6 +29,12 @@ extern "C" {
 #define UPB_MIN(x, y) ((x) < (y) ? (x) : (y))
 #define UPB_INDEX(base, i, m) (void*)((char*)(base) + ((i)*(m)))
 
+// Rounds val up to the next multiple of align.
+INLINE size_t upb_align_up(size_t val, size_t align) {
+  return val % align == 0 ? val : val + align - (val % align);
+}
+
+
 // The maximum that any submessages can be nested.  Matches proto2's limit.
 #define UPB_MAX_NESTING 64
 
diff --git a/src/upb_decoder.c b/src/upb_decoder.c
index 9c216d5..4467440 100644
--- a/src/upb_decoder.c
+++ b/src/upb_decoder.c
@@ -11,6 +11,12 @@
 #include <stdlib.h>
 #include "upb_def.h"
 
+// If the return value is other than UPB_CONTINUE, that is what the last
+// callback returned.
+extern upb_flow_t upb_fastdecode(const char **p, const char *end,
+                                 upb_value_handler_t *value_cb, void *closure,
+                                 void *table, int table_size);
+
 /* Pure Decoding **************************************************************/
 
 // The key fast-path varint-decoding routine.  Here we can assume we have at
@@ -329,6 +335,12 @@ void upb_decoder_run(upb_src *src, upb_status *status) {
       CHECK_FLOW(upb_pop(d));
     }
 
+    // Decodes as many fields as possible, updating d->ptr appropriately,
+    // before falling through to the slow(er) path.
+    //CHECK_FLOW(upb_fastdecode(&d->ptr, d->end,
+    //                          d->dispatcher->top->handlers.set->value,
+    //                          d->top->handlers.closure));
+
     // Parse/handle tag.
     upb_tag tag;
     if (!upb_decode_tag(d, &tag)) {
@@ -373,15 +385,19 @@ void upb_decoder_run(upb_src *src, upb_status *status) {
     }
 
     // Look up field by tag number.
-    upb_fielddef *f = upb_msgdef_itof(d->top->msgdef, tag.field_number);
+    upb_itof_ent *e = upb_msgdef_itofent(d->top->msgdef, tag.field_number);
 
-    if (!f) {
+    if (!e) {
       if (tag.wire_type == UPB_WIRE_TYPE_DELIMITED)
         CHECK(upb_decode_string(d, &val, &d->tmp));
       CHECK_FLOW(upb_dispatch_unknownval(&d->dispatcher, tag.field_number, val));
       continue;
-    } else if (!upb_check_type(tag.wire_type, f->type)) {
-      // TODO: put more details in this error msg.
+    }
+
+    upb_fielddef *f = e->f;
+
+    if (tag.wire_type != e->native_wire_type) {
+      // TODO: Support packed fields.
       upb_seterr(status, UPB_ERROR, "Field had incorrect type, name: " UPB_STRFMT
                  ", field type: %d, expected wire type %d, actual wire type: %d",
                  UPB_STRARG(f->name), f->type, upb_types[f->type].native_wire_type,
@@ -398,10 +414,10 @@ void upb_decoder_run(upb_src *src, upb_status *status) {
     // that the top 32 bits all match the highest bit of the low 32 bits.
     // If this is not true we are losing data.  But the main protobuf library
     // doesn't check this, and it would slow us down, so pass for now.
-    switch (f->type) {
+    switch (e->field_type) {
       case UPB_TYPE(MESSAGE):
       case UPB_TYPE(GROUP):
-        CHECK_FLOW(upb_push(d, f, val, f->type));
+        CHECK_FLOW(upb_push(d, f, val, e->field_type));
         continue;  // We have no value to dispatch.
       case UPB_TYPE(STRING):
       case UPB_TYPE(BYTES):
diff --git a/src/upb_def.c b/src/upb_def.c
index 7e962c8..01143da 100644
--- a/src/upb_def.c
+++ b/src/upb_def.c
@@ -12,11 +12,6 @@
 
 #define alignof(t) offsetof(struct { char c; t x; }, x)
 
-/* Rounds p up to the next multiple of t. */
-static size_t upb_align_up(size_t val, size_t align) {
-  return val % align == 0 ? val : val + align - (val % align);
-}
-
 static int upb_div_round_up(int numerator, int denominator) {
   /* cf. http://stackoverflow.com/questions/17944/how-to-round-up-the-result-of-integer-division */
   return numerator > 0 ? (numerator - 1) / denominator + 1 : 0;
@@ -491,10 +486,10 @@ static upb_flow_t upb_enumdef_EnumValueDescriptorProto_endmsg(void *_b) {
     return UPB_BREAK;
   }
   upb_ntoi_ent ntoi_ent = {{b->name, 0}, b->number};
-  upb_iton_ent iton_ent = {{b->number, 0}, b->name};
+  upb_iton_ent iton_ent = {0, b->name};
   upb_enumdef *e = upb_downcast_enumdef(upb_defbuilder_last(b));
   upb_strtable_insert(&e->ntoi, &ntoi_ent.e);
-  upb_inttable_insert(&e->iton, &iton_ent.e);
+  upb_inttable_insert(&e->iton, b->number, &iton_ent);
   // We don't unref "name" because we pass our ref to the iton entry of the
   // table.  strtables can ref their keys, but the inttable doesn't know that
   // the value is a string.
@@ -579,8 +574,7 @@ upb_enum_iter upb_enum_begin(upb_enumdef *e) {
 }
 
 upb_enum_iter upb_enum_next(upb_enumdef *e, upb_enum_iter iter) {
-  assert(iter);
-  return upb_inttable_next(&e->iton, &iter->e);
+  return upb_inttable_next(&e->iton, iter);
 }
 
 upb_string *upb_enumdef_iton(upb_enumdef *def, upb_enumval_t num) {
@@ -621,9 +615,9 @@ static upb_flow_t upb_fielddef_endmsg(void *_b) {
 
   // Field was successfully read, add it as a field of the msgdef.
   upb_msgdef *m = upb_defbuilder_top(b);
-  upb_itof_ent itof_ent = {{f->number, 0}, f};
+  upb_itof_ent itof_ent = {0, upb_types[f->type].native_wire_type, f->type, f};
   upb_ntof_ent ntof_ent = {{f->name, 0}, f};
-  upb_inttable_insert(&m->itof, &itof_ent.e);
+  upb_inttable_insert(&m->itof, f->number, &itof_ent);
   upb_strtable_insert(&m->ntof, &ntof_ent.e);
   return UPB_CONTINUE;
 }
@@ -702,6 +696,7 @@ static upb_flow_t upb_msgdef_endmsg(void *_b) {
     return UPB_BREAK;
   }
 
+  upb_inttable_compact(&m->itof);
   // Create an ordering over the fields.
   upb_field_count_t n = upb_msgdef_numfields(m);
   upb_fielddef **sorted_fields = malloc(sizeof(upb_fielddef*) * n);
@@ -830,7 +825,7 @@ upb_msg_iter upb_msg_begin(upb_msgdef *m) {
 }
 
 upb_msg_iter upb_msg_next(upb_msgdef *m, upb_msg_iter iter) {
-  return upb_inttable_next(&m->itof, &iter->e);
+  return upb_inttable_next(&m->itof, iter);
 }
 
 /* upb_symtab adding defs *****************************************************/
diff --git a/src/upb_def.h b/src/upb_def.h
index 6e4bc25..cca908b 100644
--- a/src/upb_def.h
+++ b/src/upb_def.h
@@ -162,7 +162,9 @@ typedef struct _upb_msgdef {
 
 // Hash table entries for looking up fields by name or number.
 typedef struct {
-  upb_inttable_entry e;
+  bool junk;
+  upb_wire_type_t native_wire_type;
+  upb_fieldtype_t field_type;
   upb_fielddef *f;
 } upb_itof_ent;
 typedef struct {
@@ -173,9 +175,13 @@ typedef struct {
 // Looks up a field by name or number.  While these are written to be as fast
 // as possible, it will still be faster to cache the results of this lookup if
 // possible.  These return NULL if no such field is found.
+INLINE upb_itof_ent *upb_msgdef_itofent(upb_msgdef *m, uint32_t num) {
+  return (upb_itof_ent*)upb_inttable_fastlookup(
+      &m->itof, num, sizeof(upb_itof_ent));
+}
+
 INLINE upb_fielddef *upb_msgdef_itof(upb_msgdef *m, uint32_t num) {
-  upb_itof_ent *e =
-      (upb_itof_ent*)upb_inttable_fastlookup(&m->itof, num, sizeof(*e));
+  upb_itof_ent *e = upb_msgdef_itofent(m, num);
   return e ? e->f : NULL;
 }
 
@@ -194,14 +200,15 @@ INLINE upb_field_count_t upb_msgdef_numfields(upb_msgdef *m) {
 //     upb_fielddef *f = upb_msg_iter_field(i);
 //     // ...
 //   }
-typedef upb_itof_ent *upb_msg_iter;
+typedef upb_inttable_iter upb_msg_iter;
 
 upb_msg_iter upb_msg_begin(upb_msgdef *m);
 upb_msg_iter upb_msg_next(upb_msgdef *m, upb_msg_iter iter);
-INLINE bool upb_msg_done(upb_msg_iter iter) { return iter == NULL; }
+INLINE bool upb_msg_done(upb_msg_iter iter) { return upb_inttable_done(iter); }
 
 INLINE upb_fielddef *upb_msg_iter_field(upb_msg_iter iter) {
-  return iter->f;
+  upb_itof_ent *ent = (upb_itof_ent*)upb_inttable_iter_value(iter);
+  return ent->f;
 }
 
 /* upb_enumdef ****************************************************************/
@@ -218,7 +225,7 @@ typedef struct {
 } upb_ntoi_ent;
 
 typedef struct {
-  upb_inttable_entry e;
+  bool junk;
   upb_string *string;
 } upb_iton_ent;
 
@@ -234,17 +241,18 @@ upb_string *upb_enumdef_iton(upb_enumdef *e, upb_enumval_t num);
 //   for(i = upb_enum_begin(e); !upb_enum_done(i); i = upb_enum_next(e, i)) {
 //     // ...
 //   }
-typedef upb_iton_ent *upb_enum_iter;
+typedef upb_inttable_iter upb_enum_iter;
 
 upb_enum_iter upb_enum_begin(upb_enumdef *e);
 upb_enum_iter upb_enum_next(upb_enumdef *e, upb_enum_iter iter);
-INLINE bool upb_enum_done(upb_enum_iter iter) { return iter == NULL; }
+INLINE bool upb_enum_done(upb_enum_iter iter) { return upb_inttable_done(iter); }
 
 INLINE upb_string *upb_enum_iter_name(upb_enum_iter iter) {
-  return iter->string;
+  upb_iton_ent *e = (upb_iton_ent*)upb_inttable_iter_value(iter);
+  return e->string;
 }
 INLINE int32_t upb_enum_iter_number(upb_enum_iter iter) {
-  return iter->e.key;
+  return upb_inttable_iter_key(iter);
 }
 
 
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;
diff --git a/src/upb_table.h b/src/upb_table.h
index b173101..3903c75 100644
--- a/src/upb_table.h
+++ b/src/upb_table.h
@@ -25,12 +25,21 @@ extern "C" {
 
 typedef uint32_t upb_inttable_key_t;
 
-#define UPB_END_OF_CHAIN (uint32_t)0
+#define UPB_END_OF_CHAIN (uint32_t)-1
 
 typedef struct {
-  upb_inttable_key_t key;
   bool has_entry:1;
-  uint32_t next:31;  // Internal chaining.
+  // The rest of the bits are the user's.
+} upb_inttable_value;
+
+typedef struct {
+  upb_inttable_key_t key;
+  uint32_t next;  // Internal chaining.
+} upb_inttable_header;
+
+typedef struct {
+  upb_inttable_header hdr;
+  upb_inttable_value val;
 } upb_inttable_entry;
 
 // TODO: consider storing the hash in the entry.  This would avoid the need to
@@ -43,11 +52,12 @@ typedef struct {
 } upb_strtable_entry;
 
 typedef struct {
-  void *entries;
-  uint32_t count;       /* How many elements are currently in the table? */
-  uint16_t entry_size;  /* How big is each entry? */
-  uint8_t size_lg2;     /* The table is 2^size_lg2 in size. */
-  uint32_t mask;
+  void *entries;        // Hash table.
+  uint32_t count;       // Number of entries in the hash part.
+  uint32_t mask;        // Mask to turn hash value -> bucket.
+  uint16_t entry_size;  // Size of each entry.
+  uint16_t value_size;  // Size of each value.
+  uint8_t size_lg2;     // Size of the hash table part is 2^size_lg2 entries.
 } upb_table;
 
 typedef struct {
@@ -56,83 +66,121 @@ typedef struct {
 
 typedef struct {
   upb_table t;
+  void *array;           // Array part of the table.
+  uint32_t array_size;   // Array part size.
+  uint32_t array_count;  // Array part number of elements.
 } upb_inttable;
 
-/* Initialize and free a table, respectively.  Specify the initial size
- * with 'size' (the size will be increased as necessary).  Entry size
- * specifies how many bytes each entry in the table is. */
-void upb_inttable_init(upb_inttable *table, uint32_t size, uint16_t entry_size);
+// Initialize and free a table, respectively.  Specify the initial size
+// with 'size' (the size will be increased as necessary).  Value size
+// specifies how many bytes each value in the table is.
+//
+// WARNING!  The lowest bit of every entry is reserved by the hash table.
+// It will always be overwritten when you insert, and must not be modified
+// when looked up!
+void upb_inttable_init(upb_inttable *table, uint32_t size, uint16_t value_size);
 void upb_inttable_free(upb_inttable *table);
-void upb_strtable_init(upb_strtable *table, uint32_t size, uint16_t entry_size);
+void upb_strtable_init(upb_strtable *table, uint32_t size, uint16_t entry_size);  // TODO: update
 void upb_strtable_free(upb_strtable *table);
 
-INLINE uint32_t upb_table_size(upb_table *t) { return 1 << t->size_lg2; }
-INLINE uint32_t upb_inttable_size(upb_inttable *t) {
-  return upb_table_size(&t->t);
-}
-INLINE uint32_t upb_strtable_size(upb_strtable *t) {
-  return upb_table_size(&t->t);
-}
-
+// Number of values in the hash table.
 INLINE uint32_t upb_table_count(upb_table *t) { return t->count; }
 INLINE uint32_t upb_inttable_count(upb_inttable *t) {
-  return upb_table_count(&t->t);
+  return t->array_count + upb_table_count(&t->t);
 }
 INLINE uint32_t upb_strtable_count(upb_strtable *t) {
   return upb_table_count(&t->t);
 }
 
-/* Inserts the given key into the hashtable with the given value.  The key must
- * not already exist in the hash table.  The data will be copied from e into
- * the hashtable (the amount of data copied comes from entry_size when the
- * table was constructed).  Therefore the data at val may be freed once the
- * call returns. */
-void upb_inttable_insert(upb_inttable *t, upb_inttable_entry *e);
-void upb_strtable_insert(upb_strtable *t, upb_strtable_entry *e);
+// Inserts the given key into the hashtable with the given value.  The key must
+// not already exist in the hash table.  The data will be copied from val into
+// the hashtable (the amount of data copied comes from value_size when the
+// table was constructed).  Therefore the data at val may be freed once the
+// call returns.  For string tables, the table takes a ref on str.
+//
+// WARNING: the lowest bit of val is reserved and will be overwritten!
+void upb_inttable_insert(upb_inttable *t, upb_inttable_key_t key, void *val);
+void upb_strtable_insert(upb_strtable *t, upb_strtable_entry *ent);  // TODO: update
+void upb_inttable_compact(upb_inttable *t);
+
+INLINE uint32_t _upb_inttable_bucket(upb_inttable *t, upb_inttable_key_t k) {
+  uint32_t bucket = k & t->t.mask;  // Identity hash for ints.
+  assert(bucket != UPB_END_OF_CHAIN);
+  return bucket;
+}
 
-INLINE uint32_t upb_inttable_bucket(upb_inttable *t, upb_inttable_key_t k) {
-  return (k & t->t.mask) + 1;  /* Identity hash for ints. */
+// Returns true if this key belongs in the array part of the table.
+INLINE bool _upb_inttable_isarrkey(upb_inttable *t, upb_inttable_key_t k) {
+  return (k < t->array_size);
 }
 
-/* Looks up key in this table.  Inlined because this is in the critical path of
- * decoding.  We have the caller specify the entry_size because fixing this as
- * a literal (instead of reading table->entry_size) gives the compiler more
- * ability to optimize. */
-INLINE void *upb_inttable_fastlookup(upb_inttable *t, uint32_t key,
-                                     uint32_t entry_size) {
-  uint32_t bucket = upb_inttable_bucket(t, key);
+// Looks up key in this table, returning a pointer to the user's inserted data.
+// We have the caller specify the entry_size because fixing this as a literal
+// (instead of reading table->entry_size) gives the compiler more ability to
+// optimize.
+INLINE void *_upb_inttable_fastlookup(upb_inttable *t, uint32_t key,
+                                      size_t entry_size, size_t value_size) {
+  upb_inttable_value *arrval =
+      (upb_inttable_value*)UPB_INDEX(t->array, key, value_size);
+  if (_upb_inttable_isarrkey(t, key)) {
+    //printf("array lookup for key %d, &val=%p, has_entry=%d\n", key, val, val->has_entry);
+    return (arrval->has_entry) ? arrval : NULL;
+  }
+  uint32_t bucket = _upb_inttable_bucket(t, key);
   upb_inttable_entry *e =
-      (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket-1, entry_size);
-  if (key == 0) {
-    while (1) {
-      if (e->key == 0 && e->has_entry) return e;
-      if ((bucket = e->next) == UPB_END_OF_CHAIN) return NULL;
-      e = (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket-1, entry_size);
-    }
-  } else {
-    while (1) {
-      if (e->key == key) return e;
-      if ((bucket = e->next) == UPB_END_OF_CHAIN) return NULL;
-      e = (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket-1, entry_size);
-    }
+      (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket, entry_size);
+  //printf("looking in first bucket %d, entry size=%zd, addr=%p\n", bucket, entry_size, e);
+  while (1) {
+    //printf("%d, %d, %d\n", e->val.has_entry, e->hdr.key, key);
+    if (e->hdr.key == key) return &e->val;
+    if ((bucket = e->hdr.next) == UPB_END_OF_CHAIN) return NULL;
+    //printf("looking in bucket %d\n", bucket);
+    e = (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket, entry_size);
   }
 }
 
+INLINE size_t _upb_inttable_entrysize(size_t value_size) {
+  return upb_align_up(sizeof(upb_inttable_header) + value_size, 8);
+}
+
+INLINE void *upb_inttable_fastlookup(upb_inttable *t, uint32_t key,
+                                      uint32_t value_size) {
+  return _upb_inttable_fastlookup(t, key, _upb_inttable_entrysize(value_size), value_size);
+}
+
 INLINE void *upb_inttable_lookup(upb_inttable *t, uint32_t key) {
-  return upb_inttable_fastlookup(t, key, t->t.entry_size);
+  return _upb_inttable_fastlookup(t, key, t->t.entry_size, t->t.value_size);
 }
 
 void *upb_strtable_lookup(upb_strtable *t, upb_string *key);
 
-/* Provides iteration over the table.  The order in which the entries are
- * returned is undefined.  Insertions invalidate iterators.  The _next
- * functions return NULL when the end has been reached. */
-void *upb_inttable_begin(upb_inttable *t);
-void *upb_inttable_next(upb_inttable *t, upb_inttable_entry *cur);
-
+// Provides iteration over the table.  The order in which the entries are
+// returned is undefined.  Insertions invalidate iterators.
 void *upb_strtable_begin(upb_strtable *t);
 void *upb_strtable_next(upb_strtable *t, upb_strtable_entry *cur);
 
+// Inttable iteration (should update strtable iteration to use this scheme too).
+// The order is undefined.
+//   for(upb_inttable_iter i = upb_inttable_begin(t); !upb_inttable_done(i);
+//       i = upb_inttable_next(t, i)) {
+//     // ...
+//   }
+typedef struct {
+  upb_inttable_key_t key;
+  upb_inttable_value *value;
+  bool array_part;
+} upb_inttable_iter;
+
+upb_inttable_iter upb_inttable_begin(upb_inttable *t);
+upb_inttable_iter upb_inttable_next(upb_inttable *t, upb_inttable_iter iter);
+INLINE bool upb_inttable_done(upb_inttable_iter iter) { return iter.value == NULL; }
+INLINE upb_inttable_key_t upb_inttable_iter_key(upb_inttable_iter iter) {
+  return iter.key;
+}
+INLINE void *upb_inttable_iter_value(upb_inttable_iter iter) {
+  return iter.value;
+}
+
 #ifdef __cplusplus
 }  /* extern "C" */
 #endif