Use 1 byte hint for ar_table [Feature #15602]

On ar_table, Do not keep a full-length hash value (FLHV, 8 bytes)
but keep a 1 byte hint from a FLHV (lowest byte of FLHV).
An ar_table only contains at least 8 entries, so hints consumes
8 bytes at most. We can store hints in RHash::ar_hint.

On 32bit CPU, we use 4 entries ar_table.

The advantages:
* We don't need to keep FLHV so ar_table only consumes
  16 bytes (VALUEs of key and value) * 8 entries = 128 bytes.
* We don't need to scan ar_table, but only need to check hints
  in many cases. Especially we don't need to access ar_table
  if there is no match entries (in many cases).
  It will increase memory cache locality.

The disadvantages:
* This technique can increase `#eql?` time because hints can
  conflicts (in theory, it conflicts once in 256 times).
  It can introduce incompatibility if there is a object x where
  x.eql? returns true even if hash values are different.
  I believe we don't need to care such irregular case.
* We need to re-calculate FLHV if we need to switch from ar_table
  to st_table (e.g. exceeds 8 entries).
  It also can introduce incompatibility, on mutating key objects.
  I believe we don't need to care such irregular case too.

Add new debug counters to measure the performance:
* artable_hint_hit - hint is matched and eql?#=>true
* artable_hint_miss - hint is not matched but eql?#=>false
* artable_hint_notfound - lookup counts

1 files changed, 191 insertions, 146 deletions

diff --git a/hash.c b/hash.c
index fc65e4cc7d..d0386d4fb0 100644
--- a/hash.c
+++ b/hash.c
@@ -37,11 +37,11 @@
 
 #define HAS_EXTRA_STATES(hash, klass) ( \
     ((klass = has_extra_methods(rb_obj_class(hash))) != 0) || \
-    FL_TEST((hash), FL_EXIVAR|FL_TAINT|HASH_PROC_DEFAULT) || \
+    FL_TEST((hash), FL_EXIVAR|FL_TAINT|RHASH_PROC_DEFAULT) || \
     !NIL_P(RHASH_IFNONE(hash)))
 
 #define SET_DEFAULT(hash, ifnone) ( \
-    FL_UNSET_RAW(hash, HASH_PROC_DEFAULT), \
+    FL_UNSET_RAW(hash, RHASH_PROC_DEFAULT), \
     RHASH_SET_IFNONE(hash, ifnone))
 
 #define SET_PROC_DEFAULT(hash, proc) set_proc_default(hash, proc)
@@ -51,8 +51,8 @@
 static inline void
 copy_default(struct RHash *hash, const struct RHash *hash2)
 {
-    hash->basic.flags &= ~HASH_PROC_DEFAULT;
-    hash->basic.flags |= hash2->basic.flags & HASH_PROC_DEFAULT;
+    hash->basic.flags &= ~RHASH_PROC_DEFAULT;
+    hash->basic.flags |= hash2->basic.flags & RHASH_PROC_DEFAULT;
     RHASH_SET_IFNONE(hash, RHASH_IFNONE(hash2));
 }
 
@@ -102,9 +102,6 @@ static int
 rb_any_cmp(VALUE a, VALUE b)
 {
     if (a == b) return 0;
-    if (FIXNUM_P(a) && FIXNUM_P(b)) {
-	return a != b;
-    }
     if (RB_TYPE_P(a, T_STRING) && RBASIC(a)->klass == rb_cString &&
 	RB_TYPE_P(b, T_STRING) && RBASIC(b)->klass == rb_cString) {
 	return rb_str_hash_cmp(a, b);
@@ -175,10 +172,10 @@ any_hash(VALUE a, st_index_t (*other_func)(VALUE))
 
     if (SPECIAL_CONST_P(a)) {
 	if (STATIC_SYM_P(a)) {
-	    hnum = a >> (RUBY_SPECIAL_SHIFT + ID_SCOPE_SHIFT);
-	    hnum = rb_hash_start(hnum);
-	    goto out;
-	}
+            hnum = a >> (RUBY_SPECIAL_SHIFT + ID_SCOPE_SHIFT);
+            hnum = rb_hash_start(hnum);
+            goto out;
+        }
 	else if (FLONUM_P(a)) {
 	    /* prevent pathological behavior: [Bug #10761] */
 	    goto flt;
@@ -315,12 +312,7 @@ static const struct st_hash_type identhash = {
     rb_ident_hash,
 };
 
-#define RESERVED_HASH_VAL (~(st_hash_t) 0)
-#define RESERVED_HASH_SUBSTITUTION_VAL ((st_hash_t) 0)
-
 typedef st_index_t st_hash_t;
-extern const st_hash_t st_reserved_hash_val;
-extern const st_hash_t st_reserved_hash_substitution_val;
 
 /*
  * RHASH_AR_TABLE_P(h):
@@ -332,17 +324,20 @@ extern const st_hash_t st_reserved_hash_substitution_val;
  * * as.st points st_table.
  */
 
-#define RHASH_AR_TABLE_MAX_SIZE      8
+#define RHASH_AR_TABLE_MAX_SIZE      sizeof(VALUE)
 #define RHASH_AR_TABLE_MAX_BOUND     RHASH_AR_TABLE_MAX_SIZE
 
-typedef struct ar_table_entry {
-    st_hash_t hash;
+#define RHASH_AR_TABLE_REF(hash, n) (&RHASH_AR_TABLE(hash)->pairs[n])
+#define RHASH_AR_CLEARED_HINT 0xff
+
+typedef struct ar_table_pair_struct {
     VALUE key;
-    VALUE record;
-} ar_table_entry;
+    VALUE val;
+} ar_table_pair;
 
 typedef struct ar_table_struct {
-    ar_table_entry entries[RHASH_AR_TABLE_MAX_SIZE];
+    /* 64bit CPU: 8B * 2 * 8 = 128B */
+    ar_table_pair pairs[RHASH_AR_TABLE_MAX_SIZE];
 } ar_table;
 
 size_t
@@ -354,30 +349,63 @@ rb_hash_ar_table_size(void)
 static inline st_hash_t
 ar_do_hash(st_data_t key)
 {
-    st_hash_t hash = (st_hash_t)rb_any_hash(key);
-    return (RESERVED_HASH_VAL == hash) ? RESERVED_HASH_SUBSTITUTION_VAL : hash;
+    return (st_hash_t)rb_any_hash(key);
+}
+
+static inline unsigned char
+ar_do_hash_hint(st_hash_t hash_value)
+{
+    return (unsigned char)hash_value;
+}
+
+static inline unsigned char
+ar_hint(VALUE hash, unsigned int index)
+{
+    return RHASH(hash)->ar_hint.ary[index];
 }
 
 static inline void
-ar_set_entry(ar_table_entry *entry, st_data_t key, st_data_t val, st_hash_t hash)
+ar_hint_set_hint(VALUE hash, unsigned int index, unsigned char hint)
 {
-    entry->hash = hash;
-    entry->key = key;
-    entry->record = val;
+    RHASH(hash)->ar_hint.ary[index] = hint;
 }
 
 static inline void
-ar_clear_entry(ar_table_entry* entry)
+ar_hint_set(VALUE hash, unsigned int index, st_hash_t hash_value)
 {
-    entry->key = Qundef;
-    entry->record = Qundef;
-    entry->hash = RESERVED_HASH_VAL;
+    ar_hint_set_hint(hash, index, ar_do_hash_hint(hash_value));
+}
+
+static inline void
+ar_clear_entry(VALUE hash, unsigned int index)
+{
+    ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, index);
+    pair->key = Qundef;
+    ar_hint_set_hint(hash, index, RHASH_AR_CLEARED_HINT);
 }
 
 static inline int
-ar_empty_entry(ar_table_entry *entry)
+ar_cleared_entry(VALUE hash, unsigned int index)
 {
-    return entry->hash == RESERVED_HASH_VAL;
+    if (ar_hint(hash, index) == RHASH_AR_CLEARED_HINT) {
+        /* RHASH_AR_CLEARED_HINT is only a hint, not mean cleared entry,
+         * so you need to check key == Qundef
+         */
+        ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, index);
+        return pair->key == Qundef;
+    }
+    else {
+        return FALSE;
+    }
+}
+
+static inline void
+ar_set_entry(VALUE hash, unsigned int index, st_data_t key, st_data_t val, st_hash_t hash_value)
+{
+    ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, index);
+    pair->key = key;
+    pair->val = val;
+    ar_hint_set(hash, index, hash_value);
 }
 
 #define RHASH_AR_TABLE_SIZE(h) (HASH_ASSERT(RHASH_AR_TABLE_P(h)), \
@@ -392,7 +420,6 @@ ar_empty_entry(ar_table_entry *entry)
 
 #define RHASH_ST_TABLE_SET(h, s)  rb_hash_st_table_set(h, s)
 #define RHASH_TYPE(hash) (RHASH_AR_TABLE_P(hash) ? &objhash : RHASH_ST_TABLE(hash)->type)
-#define RHASH_AR_TABLE_REF(hash, n) (&RHASH_AR_TABLE(hash)->entries[n])
 
 #define HASH_ASSERT(expr) RUBY_ASSERT_MESG_WHEN(1, expr, #expr)
 
@@ -411,17 +438,17 @@ rb_hash_dump(VALUE hash)
                 RHASH_AR_TABLE_SIZE(hash), RHASH_AR_TABLE_BOUND(hash));
 
         for (i=0; i<bound; i++) {
-            ar_table_entry *cur_entry = RHASH_AR_TABLE_REF(hash, i);
             st_data_t k, v;
 
-            if (!ar_empty_entry(cur_entry)) {
+            if (!ar_cleared_entry(hash, i)) {
                 char b1[0x100], b2[0x100];
-                /* h = cur_entry->hash; */
-                k = cur_entry->key;
-                v = cur_entry->record;
-                fprintf(stderr, "  %d key:%s val:%s\n", i,
+                ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
+                k = pair->key;
+                v = pair->val;
+                fprintf(stderr, "  %d key:%s val:%s hint:%02x\n", i,
                         rb_raw_obj_info(b1, 0x100, k),
-                        rb_raw_obj_info(b2, 0x100, v));
+                        rb_raw_obj_info(b2, 0x100, v),
+                        ar_hint(hash, i));
                 n++;
             }
             else {
@@ -440,13 +467,11 @@ hash_verify_(VALUE hash, const char *file, int line)
         unsigned i, n = 0, bound = RHASH_AR_TABLE_BOUND(hash);
 
         for (i=0; i<bound; i++) {
-            ar_table_entry *cur_entry = RHASH_AR_TABLE_REF(hash, i);
-            st_data_t h, k, v;
-            if (!ar_empty_entry(cur_entry)) {
-                h = cur_entry->hash;
-                k = cur_entry->key;
-                v = cur_entry->record;
-                HASH_ASSERT(h != RESERVED_HASH_VAL);
+            st_data_t k, v;
+            if (!ar_cleared_entry(hash, i)) {
+                ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
+                k = pair->key;
+                v = pair->val;
                 HASH_ASSERT(k != Qundef);
                 HASH_ASSERT(v != Qundef);
                 n++;
@@ -606,33 +631,64 @@ ar_alloc_table(VALUE hash)
     return tab;
 }
 
-static inline int
-ar_equal(VALUE x, VALUE y)
-{
-    return x == y || rb_any_cmp(x, y) == 0;
-}
+NOINLINE(static int ar_equal(VALUE x, VALUE y));
 
-static inline int
-ar_ptr_equal(ar_table_entry *entry, st_hash_t hash_val, VALUE key)
+static int
+ar_equal(VALUE x, VALUE y)
 {
-    return entry->hash == hash_val && ar_equal(key, entry->key);
+    return rb_any_cmp(x, y) == 0;
 }
 
 static unsigned
-ar_find_entry(VALUE hash, st_hash_t hash_value, st_data_t key)
+ar_find_entry_hint(VALUE hash, unsigned char hint, st_data_t key)
 {
     unsigned i, bound = RHASH_AR_TABLE_BOUND(hash);
+    const unsigned char *hints = RHASH(hash)->ar_hint.ary;
 
     /* if table is NULL, then bound also should be 0 */
 
     for (i = 0; i < bound; i++) {
-        if (ar_ptr_equal(RHASH_AR_TABLE_REF(hash, i), hash_value, key)) {
-            return i;
+        if (hints[i] == hint) {
+            ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
+            if (ar_equal(key, pair->key)) {
+                RB_DEBUG_COUNTER_INC(artable_hint_hit);
+                return i;
+            }
+            else {
+#if 0
+                static int pid;
+                static char fname[256];
+                static FILE *fp;
+
+                if (pid != getpid()) {
+                    snprintf(fname, sizeof(fname), "/tmp/ruby-armiss.%d", pid = getpid());
+                    if ((fp = fopen(fname, "w")) == NULL) rb_bug("fopen");
+                }
+
+                st_hash_t h1 = ar_do_hash(key);
+                st_hash_t h2 = ar_do_hash(pair->key);
+
+                fprintf(fp, "miss: hash_eq:%d hints[%d]:%02x hint:%02x\n"
+                            "      key      :%016lx %s\n"
+                            "      pair->key:%016lx %s\n",
+                        h1 == h2, i, hints[i], hint,
+                        h1, rb_obj_info(key), h2, rb_obj_info(pair->key));
+#endif
+                RB_DEBUG_COUNTER_INC(artable_hint_miss);
+            }
         }
     }
+    RB_DEBUG_COUNTER_INC(artable_hint_notfound);
     return RHASH_AR_TABLE_MAX_BOUND;
 }
 
+static unsigned
+ar_find_entry(VALUE hash, st_hash_t hash_value, st_data_t key)
+{
+    unsigned char hint = ar_do_hash_hint(hash_value);
+    return ar_find_entry_hint(hash, hint, key);
+}
+
 static inline void
 ar_free_and_clear_table(VALUE hash)
 {
@@ -652,13 +708,10 @@ ar_free_and_clear_table(VALUE hash)
     HASH_ASSERT(RHASH_TRANSIENT_P(hash) == 0);
 }
 
-void st_add_direct_with_hash(st_table *tab, st_data_t key, st_data_t value, st_hash_t hash); /* st.c */
-
 static void
 ar_try_convert_table(VALUE hash)
 {
     st_table *new_tab;
-    ar_table_entry *entry;
     const unsigned size = RHASH_AR_TABLE_SIZE(hash);
     st_index_t i;
 
@@ -669,10 +722,8 @@ ar_try_convert_table(VALUE hash)
     new_tab = st_init_table_with_size(&objhash, size * 2);
 
     for (i = 0; i < RHASH_AR_TABLE_MAX_BOUND; i++) {
-        entry = RHASH_AR_TABLE_REF(hash, i);
-        HASH_ASSERT(entry->hash != RESERVED_HASH_VAL);
-
-        st_add_direct_with_hash(new_tab, entry->key, entry->record, entry->hash);
+        ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
+        st_add_direct(new_tab, pair->key, pair->val);
     }
     ar_free_and_clear_table(hash);
     RHASH_ST_TABLE_SET(hash, new_tab);
@@ -689,7 +740,6 @@ ar_force_convert_table(VALUE hash, const char *file, int line)
     }
 
     if (RHASH_AR_TABLE(hash)) {
-        ar_table_entry *entry;
         unsigned i, bound = RHASH_AR_TABLE_BOUND(hash);
 
 #if RHASH_CONVERT_TABLE_DEBUG
@@ -701,10 +751,10 @@ ar_force_convert_table(VALUE hash, const char *file, int line)
         new_tab = st_init_table_with_size(&objhash, RHASH_AR_TABLE_SIZE(hash));
 
         for (i = 0; i < bound; i++) {
-            entry = RHASH_AR_TABLE_REF(hash, i);
-            if (ar_empty_entry(entry)) continue;
+            if (ar_cleared_entry(hash, i)) continue;
 
-            st_add_direct_with_hash(new_tab, entry->key, entry->record, entry->hash);
+            ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
+            st_add_direct(new_tab, pair->key, pair->val);
         }
         ar_free_and_clear_table(hash);
     }
@@ -736,15 +786,16 @@ ar_compact_table(VALUE hash)
     }
     else {
         unsigned i, j=0;
-        ar_table_entry *entries = RHASH_AR_TABLE_REF(hash, 0);
+        ar_table_pair *pairs = RHASH_AR_TABLE(hash)->pairs;
 
         for (i=0; i<bound; i++) {
-            if (ar_empty_entry(&entries[i])) {
+            if (ar_cleared_entry(hash, i)) {
                 if (j <= i) j = i+1;
                 for (; j<bound; j++) {
-                    if (!ar_empty_entry(&entries[j])) {
-                        entries[i] = entries[j];
-                        ar_clear_entry(&entries[j]);
+                    if (!ar_cleared_entry(hash, j)) {
+                        pairs[i] = pairs[j];
+                        ar_hint_set_hint(hash, i, (st_hash_t)ar_hint(hash, j));
+                        ar_clear_entry(hash, j);
                         j++;
                         goto found;
                     }
@@ -778,7 +829,7 @@ ar_add_direct_with_hash(VALUE hash, st_data_t key, st_data_t val, st_hash_t hash
         }
         HASH_ASSERT(bin < RHASH_AR_TABLE_MAX_BOUND);
 
-        ar_set_entry(RHASH_AR_TABLE_REF(hash, bin), key, val, hash_value);
+        ar_set_entry(hash, bin, key, val, hash_value);
         RHASH_AR_TABLE_BOUND_SET(hash, bin+1);
         RHASH_AR_TABLE_SIZE_INC(hash);
         return 0;
@@ -792,11 +843,11 @@ ar_general_foreach(VALUE hash, int (*func)(ANYARGS), st_update_callback_func *re
         unsigned i, bound = RHASH_AR_TABLE_BOUND(hash);
 
         for (i = 0; i < bound; i++) {
-            enum st_retval retval;
-            ar_table_entry *cur_entry = RHASH_AR_TABLE_REF(hash, i);
-            if (ar_empty_entry(cur_entry)) continue;
-            retval = (*func)(cur_entry->key, cur_entry->record, arg, 0);
-            /* cur_entry is not valid after that */
+            if (ar_cleared_entry(hash, i)) continue;
+
+            ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
+            enum st_retval retval = (*func)(pair->key, pair->val, arg, 0);
+            /* pair may be not valid here because of theap */
 
             switch (retval) {
               case ST_CONTINUE:
@@ -806,20 +857,18 @@ ar_general_foreach(VALUE hash, int (*func)(ANYARGS), st_update_callback_func *re
                 return 0;
               case ST_REPLACE:
                 if (replace) {
-                    VALUE key;
-                    VALUE value;
-
-                    key = cur_entry->key;
-                    value = cur_entry->record;
-                    retval = (*replace)(&key, &value, arg, TRUE);
-
-                    ar_table_entry *entry = RHASH_AR_TABLE_REF(hash, i);
-                    entry->key = key;
-                    entry->record = value;
+                    VALUE key = pair->key;
+                    VALUE val = pair->val;
+                    retval = (*replace)(&key, &val, arg, TRUE);
+
+                    // TODO: pair should be same as pair before.
+                    ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
+                    pair->key = key;
+                    pair->val = val;
                 }
                 break;
               case ST_DELETE:
-                ar_clear_entry(RHASH_AR_TABLE_REF(hash, i));
+                ar_clear_entry(hash, i);
                 RHASH_AR_TABLE_SIZE_DEC(hash);
                 break;
             }
@@ -847,27 +896,24 @@ ar_foreach_check(VALUE hash, int (*func)(ANYARGS), st_data_t arg,
     if (RHASH_AR_TABLE_SIZE(hash) > 0) {
         unsigned i, ret = 0, bound = RHASH_AR_TABLE_BOUND(hash);
         enum st_retval retval;
-        ar_table_entry *cur_entry;
         st_data_t key;
-        st_hash_t hash_value;
+        ar_table_pair *pair;
+        unsigned char hint;
 
         for (i = 0; i < bound; i++) {
-            cur_entry = RHASH_AR_TABLE_REF(hash, i);
-            if (ar_empty_entry(cur_entry))
-              continue;
-            key = cur_entry->key;
-            hash_value = cur_entry->hash;
+            if (ar_cleared_entry(hash, i)) continue;
 
-            retval = (*func)(key, cur_entry->record, arg, 0);
-            hash_verify(hash);
+            pair = RHASH_AR_TABLE_REF(hash, i);
+            key = pair->key;
+            hint = ar_hint(hash, i);
 
-            cur_entry = RHASH_AR_TABLE_REF(hash, i);
+            retval = (*func)(key, pair->val, arg, 0);
+            hash_verify(hash);
 
             switch (retval) {
               case ST_CHECK: {
-                  if (cur_entry->key == never && cur_entry->hash == RESERVED_HASH_VAL)
-                      break;
-                  ret = ar_find_entry(hash, hash_value, key);
+                  if (pair->key == never) break;
+                  ret = ar_find_entry_hint(hash, hint, key);
                   if (ret == RHASH_AR_TABLE_MAX_BOUND) {
                       retval = (*func)(0, 0, arg, 1);
                       return 2;
@@ -879,8 +925,8 @@ ar_foreach_check(VALUE hash, int (*func)(ANYARGS), st_data_t arg,
               case ST_REPLACE:
                 return 0;
               case ST_DELETE: {
-                  if (!ar_empty_entry(cur_entry)) {
-                      ar_clear_entry(cur_entry);
+                  if (!ar_cleared_entry(hash, i)) {
+                      ar_clear_entry(hash, i);
                       RHASH_AR_TABLE_SIZE_DEC(hash);
                   }
                   break;
@@ -910,12 +956,13 @@ ar_update(VALUE hash, st_data_t key,
     }
 
     if (existing) {
-        ar_table_entry *entry = RHASH_AR_TABLE_REF(hash, bin);
-        key = entry->key;
-        value = entry->record;
+        ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, bin);
+        key = pair->key;
+        value = pair->val;
     }
     old_key = key;
     retval = (*func)(&key, &value, arg, existing);
+    /* pair can be invalid here because of theap */
 
     switch (retval) {
       case ST_CONTINUE:
@@ -925,16 +972,16 @@ ar_update(VALUE hash, st_data_t key,
             }
         }
         else {
-            ar_table_entry *entry = RHASH_AR_TABLE_REF(hash, bin);
+            ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, bin);
             if (old_key != key) {
-                entry->key = key;
+                pair->key = key;
             }
-            entry->record = value;
+            pair->val = value;
         }
         break;
       case ST_DELETE:
         if (existing) {
-            ar_clear_entry(RHASH_AR_TABLE_REF(hash, bin));
+            ar_clear_entry(hash, bin);
             RHASH_AR_TABLE_SIZE_DEC(hash);
         }
         break;
@@ -961,13 +1008,13 @@ ar_insert(VALUE hash, st_data_t key, st_data_t value)
         }
         HASH_ASSERT(bin < RHASH_AR_TABLE_MAX_BOUND);
 
-        ar_set_entry(RHASH_AR_TABLE_REF(hash, bin), key, value, hash_value);
+        ar_set_entry(hash, bin, key, value, hash_value);
         RHASH_AR_TABLE_BOUND_SET(hash, bin+1);
         RHASH_AR_TABLE_SIZE_INC(hash);
         return 0;
     }
     else {
-        RHASH_AR_TABLE_REF(hash, bin)->record = value;
+        RHASH_AR_TABLE_REF(hash, bin)->val = value;
         return 1;
     }
 }
@@ -988,7 +1035,7 @@ ar_lookup(VALUE hash, st_data_t key, st_data_t *value)
         else {
             HASH_ASSERT(bin < RHASH_AR_TABLE_MAX_BOUND);
             if (value != NULL) {
-                *value = RHASH_AR_TABLE_REF(hash, bin)->record;
+                *value = RHASH_AR_TABLE_REF(hash, bin)->val;
             }
             return 1;
         }
@@ -1009,9 +1056,11 @@ ar_delete(VALUE hash, st_data_t *key, st_data_t *value)
         return 0;
     }
     else {
-        ar_table_entry *entry = RHASH_AR_TABLE_REF(hash, bin);
-        if (value != 0) *value = entry->record;
-        ar_clear_entry(entry);
+        if (value != 0) {
+            ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, bin);
+            *value = pair->val;
+        }
+        ar_clear_entry(hash, bin);
         RHASH_AR_TABLE_SIZE_DEC(hash);
         return 1;
     }
@@ -1022,20 +1071,19 @@ ar_shift(VALUE hash, st_data_t *key, st_data_t *value)
 {
     if (RHASH_AR_TABLE_SIZE(hash) > 0) {
         unsigned i, bound = RHASH_AR_TABLE_BOUND(hash);
-        ar_table_entry *entry, *entries = RHASH_AR_TABLE(hash)->entries;
 
         for (i = 0; i < bound; i++) {
-            entry = &entries[i];
-            if (!ar_empty_entry(entry)) {
-                if (value != 0) *value = entry->record;
-                *key = entry->key;
-                ar_clear_entry(entry);
+            if (!ar_cleared_entry(hash, i)) {
+                ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
+                if (value != 0) *value = pair->val;
+                *key = pair->key;
+                ar_clear_entry(hash, i);
                 RHASH_AR_TABLE_SIZE_DEC(hash);
                 return 1;
             }
         }
     }
-    if (value != 0) *value = 0;
+    if (value != NULL) *value = 0;
     return 0;
 }
 
@@ -1050,9 +1098,9 @@ ar_keys(VALUE hash, st_data_t *keys, st_index_t size)
           break;
         }
         else {
-            ar_table_entry *cur_entry = RHASH_AR_TABLE_REF(hash, i);
-            if (!ar_empty_entry(cur_entry))
-              *keys++ = cur_entry->key;
+            if (!ar_cleared_entry(hash, i)) {
+                *keys++ = RHASH_AR_TABLE_REF(hash, i)->key;
+            }
         }
     }
 
@@ -1070,9 +1118,9 @@ ar_values(VALUE hash, st_data_t *values, st_index_t size)
           break;
         }
         else {
-            ar_table_entry *cur_entry = RHASH_AR_TABLE_REF(hash, i);
-            if (!ar_empty_entry(cur_entry))
-              *values++ = cur_entry->record;
+            if (!ar_cleared_entry(hash, i)) {
+                *values++ = RHASH_AR_TABLE_REF(hash, i)->val;
+            }
         }
     }
 
@@ -1097,6 +1145,7 @@ ar_copy(VALUE hash1, VALUE hash2)
             }
         }
         *new_tab = *old_tab;
+        RHASH(hash1)->ar_hint.word = RHASH(hash2)->ar_hint.word;
         RHASH_AR_TABLE_BOUND_SET(hash1, RHASH_AR_TABLE_BOUND(hash2));
         RHASH_AR_TABLE_SIZE_SET(hash1, RHASH_AR_TABLE_SIZE(hash2));
         RHASH_AR_TABLE_SET(hash1, new_tab);
@@ -1456,7 +1505,7 @@ rb_hash_dup(VALUE hash)
 {
     const VALUE flags = RBASIC(hash)->flags;
     VALUE ret = hash_dup(hash, rb_obj_class(hash),
-			 flags & (FL_EXIVAR|FL_TAINT|HASH_PROC_DEFAULT));
+			 flags & (FL_EXIVAR|FL_TAINT|RHASH_PROC_DEFAULT));
     if (flags & FL_EXIVAR)
         rb_copy_generic_ivar(ret, hash);
     return ret;
@@ -1597,7 +1646,7 @@ set_proc_default(VALUE hash, VALUE proc)
 	}
     }
 
-    FL_SET_RAW(hash, HASH_PROC_DEFAULT);
+    FL_SET_RAW(hash, RHASH_PROC_DEFAULT);
     RHASH_SET_IFNONE(hash, proc);
 }
 
@@ -1836,7 +1885,7 @@ rb_hash_default_value(VALUE hash, VALUE key)
 {
     if (rb_method_basic_definition_p(CLASS_OF(hash), id_default)) {
 	VALUE ifnone = RHASH_IFNONE(hash);
-	if (!FL_TEST(hash, HASH_PROC_DEFAULT)) return ifnone;
+	if (!FL_TEST(hash, RHASH_PROC_DEFAULT)) return ifnone;
 	if (key == Qundef) return Qnil;
 	return rb_funcall(ifnone, id_yield, 2, hash, key);
     }
@@ -1896,7 +1945,7 @@ rb_hash_lookup2(VALUE hash, VALUE key, VALUE def)
 {
     st_data_t val;
 
-    if (rb_hash_stlike_lookup(hash, key, &val)) {
+    if (hash_stlike_lookup(hash, key, &val)) {
         return (VALUE)val;
     }
     else {
@@ -2009,7 +2058,7 @@ rb_hash_default(int argc, VALUE *argv, VALUE hash)
 
     rb_check_arity(argc, 0, 1);
     ifnone = RHASH_IFNONE(hash);
-    if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
+    if (FL_TEST(hash, RHASH_PROC_DEFAULT)) {
 	if (argc == 0) return Qnil;
 	args[0] = hash;
 	args[1] = argv[0];
@@ -2064,7 +2113,7 @@ rb_hash_set_default(VALUE hash, VALUE ifnone)
 static VALUE
 rb_hash_default_proc(VALUE hash)
 {
-    if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
+    if (FL_TEST(hash, RHASH_PROC_DEFAULT)) {
 	return RHASH_IFNONE(hash);
     }
     return Qnil;
@@ -3253,7 +3302,7 @@ rb_hash_to_h(VALUE hash)
     }
     if (rb_obj_class(hash) != rb_cHash) {
 	const VALUE flags = RBASIC(hash)->flags;
-	hash = hash_dup(hash, rb_cHash, flags & HASH_PROC_DEFAULT);
+	hash = hash_dup(hash, rb_cHash, flags & RHASH_PROC_DEFAULT);
     }
     return hash;
 }
@@ -3497,7 +3546,7 @@ hash_equal(VALUE hash1, VALUE hash2, int eql)
 
 #if 0
     if (!(rb_equal(RHASH_IFNONE(hash1), RHASH_IFNONE(hash2)) &&
-	  FL_TEST(hash1, HASH_PROC_DEFAULT) == FL_TEST(hash2, HASH_PROC_DEFAULT)))
+	  FL_TEST(hash1, RHASH_PROC_DEFAULT) == FL_TEST(hash2, RHASH_PROC_DEFAULT)))
 	return Qfalse;
 #endif
     return Qtrue;
@@ -5986,10 +6035,6 @@ Init_Hash(void)
 {
 #undef rb_intern
 #define rb_intern(str) rb_intern_const(str)
-
-    RUBY_ASSERT(RESERVED_HASH_VAL == st_reserved_hash_val);
-    RUBY_ASSERT(RESERVED_HASH_SUBSTITUTION_VAL == st_reserved_hash_substitution_val);
-
     id_hash = rb_intern("hash");
     id_yield = rb_intern("yield");
     id_default = rb_intern("default");