Subject: [PATCH 1/2] ihash: initial implementation

From: Eric Wong <[email-masked]>
Date: Sun, 9 Mar 2014 02:05:09 +0000

This hash implementation embeds the hash chaining pointer inside the
stored struct itself, avoiding a level of indirection and additional
malloc overhead for storing structs.

ihash is based on the ccan container_of macro using pointer
arithmetic to extract the location of the original struct based on
the hash node.  This is a common pattern for data structures in the
Linux and FreeBSD kernels.

ihash should be ideal for hash tables of internal data structures which
require separate allocations.  This includes frozen strings, method
entries, constants, and globals.  This should also be able to work well
with weakmap and the symbol table, since we can share the same allocated
struct common to two (or more) hash tables.

Before (unpacked entries):
  st_table -> st_table->bins -> st_table_entry -> value

Before (packed entries):
  st_table -> st_table->packed.entries -> value

After:
  rb_ihash_table -> value

Benefits:

+ Reduced memory usage from reduced malloc overhead and the removal
  order-preserving linked list pointers

+ Reduced indirection, this should help successful lookups and
  reduce cache misses.

+ Missed lookups keeps the cache warm for future lookups/inserts

Downsides:

- Cost of lookup misses may be higher compared to a packed st_table
  (but not an unpacked st_table)

- Does not preserve order of entries.  Ordering may be layered on
  on a case-by-case basis.

Other notes:

Not general purpose, so it must be customized on a case-by-case
basis.  We should use something else for simple ID->VALUE or
VALUE->VALUE mappings (iv_tbl, iv_index_tbl).  I will look into
funny-falcon's sparse array implementation for ivars.

Updates since initial versions:
* unlink -> detach, this is hopefully more descriptive
* RB_IHASH_MAX_DENSITY default lowered to 5 to match st
* RB_IHASH_MAX_DENSITY may be defined before including ihash.h
* use container_of from ccan rather than home-grown version
---
 common.mk |   3 +
 ihash.c   | 273 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ihash.h   | 115 ++++++++++++++++++++++++++
 3 files changed, 391 insertions(+)
 create mode 100644 ihash.c
 create mode 100644 ihash.h

diff --git a/common.mk b/common.mk
index 324487c..47f32f1 100644
--- a/common.mk
+++ b/common.mk
@@ -48,6 +48,7 @@ COMMONOBJS    = array.$(OBJEXT) \
 		enumerator.$(OBJEXT) \
 		error.$(OBJEXT) \
 		eval.$(OBJEXT) \
+		ihash.$(OBJEXT) \
 		load.$(OBJEXT) \
 		proc.$(OBJEXT) \
 		file.$(OBJEXT) \
@@ -615,6 +616,7 @@ PROBES_H_INCLUDES  = {$(VPATH)}probes.h
 VM_CORE_H_INCLUDES = {$(VPATH)}vm_core.h {$(VPATH)}thread_$(THREAD_MODEL).h \
 		     {$(VPATH)}node.h {$(VPATH)}method.h {$(VPATH)}ruby_atomic.h \
 	             {$(VPATH)}vm_debug.h {$(VPATH)}id.h {$(VPATH)}thread_native.h \
+	             {$(VPATH)}ihash.h \
 	             $(CCAN_LIST_INCLUDES)
 
 ###
@@ -677,6 +679,7 @@ eval.$(OBJEXT): {$(VPATH)}eval.c {$(VPATH)}eval_intern.h {$(VPATH)}vm.h \
   $(RUBY_H_INCLUDES) $(VM_CORE_H_INCLUDES) {$(VPATH)}eval_error.c \
   {$(VPATH)}eval_jump.c {$(VPATH)}gc.h {$(VPATH)}iseq.h \
   $(ENCODING_H_INCLUDES) {$(VPATH)}internal.h $(PROBES_H_INCLUDES) {$(VPATH)}vm_opts.h {$(VPATH)}probes_helper.h
+ihash.$(OBJEXT): {$(VPATH)}ihash.c $(RUBY_H_INCLUDES) {$(VPATH)}ihash.h
 load.$(OBJEXT): {$(VPATH)}load.c {$(VPATH)}eval_intern.h \
   {$(VPATH)}util.h $(RUBY_H_INCLUDES) $(VM_CORE_H_INCLUDES) \
   {$(VPATH)}dln.h {$(VPATH)}internal.h $(PROBES_H_INCLUDES) {$(VPATH)}vm_opts.h
diff --git a/ihash.c b/ihash.c
new file mode 100644
index 0000000..fded28c
--- /dev/null
+++ b/ihash.c
@@ -0,0 +1,273 @@
+#include "ihash.h"
+#include "internal.h"
+
+/* accounts for the compiler-agnostic flexible array byte */
+#define SIZEOF_IHASH_TBL (sizeof(struct rb_ihash_tbl) - 1)
+
+static inline size_t
+rb_ihash_nbins(const struct rb_ihash_tbl *tbl)
+{
+    return tbl->hash_mask + 1;
+}
+
+static inline size_t
+rb_ihash_binpos(const struct rb_ihash_tbl *tbl, st_index_t hash)
+{
+    return ((size_t)hash & (size_t)tbl->hash_mask);
+}
+
+static inline struct rb_ihash_node **
+rb_ihash_bins(const struct rb_ihash_tbl *tbl)
+{
+    return (struct rb_ihash_node **)tbl->flexible_array;
+}
+
+size_t
+rb_ihash_memsize(const struct rb_ihash_tbl *tbl)
+{
+    size_t nbins = rb_ihash_nbins(tbl);
+    size_t n = SIZEOF_IHASH_TBL + nbins * sizeof(struct rb_ihash_node *);
+
+    return n + sizeof(struct rb_ihash_node) * tbl->num_entries;
+}
+
+static struct rb_ihash_tbl *
+rb_ihash_alloc(const struct rb_ihash_type *type, size_t nbins)
+{
+    size_t nbytes = SIZEOF_IHASH_TBL + nbins * sizeof(struct rb_ihash_node *);
+    struct rb_ihash_tbl *tbl = xcalloc(1, nbytes);
+
+    tbl->type = type;
+    tbl->hash_mask = nbins - 1;
+
+    if ((size_t)tbl->hash_mask != (nbins - 1)) {
+	rb_bug("ihash table too big");
+    }
+
+    return tbl;
+}
+
+struct rb_ihash_tbl *
+rb_ihash_new(const struct rb_ihash_type *type, size_t power)
+{
+    return rb_ihash_alloc(type, 1 << power);
+}
+
+int
+rb_ihash_foreach(struct rb_ihash_tbl **tblp, rb_ihash_iterate fn, void *arg)
+{
+    struct rb_ihash_tbl *tbl = *tblp;
+    size_t nbins = rb_ihash_nbins(tbl);
+    struct rb_ihash_node **bins = rb_ihash_bins(tbl);
+    size_t i;
+
+    for (i = 0; i < nbins; i++) {
+	struct rb_ihash_node *cur = bins[i];
+	struct rb_ihash_node *last = 0;
+
+	while (cur) {
+	    struct rb_ihash_node *next = cur->ihash_next;
+	    struct rb_ihash_node *tmp;
+
+	    switch (fn(cur, arg)) {
+	      case RB_IHASH_DETACHED:
+		if (last) last->ihash_next = next;
+		else bins[i] = next;
+		cur = next;
+		tbl->num_entries--;
+		break;
+	      case RB_IHASH_CHECK:
+		/* check if hash is modified during iteration */
+		tmp = 0;
+		tbl = *tblp;
+		nbins = rb_ihash_nbins(tbl);
+		bins = rb_ihash_bins(tbl);
+
+		if (i < nbins) {
+		    for (tmp = bins[i]; tmp; tmp = tmp->ihash_next) {
+			if (tmp == cur) break;
+		    }
+		}
+		if (!tmp) return 1;
+		last = cur;
+		cur = cur->ihash_next;
+		break;
+	      case RB_IHASH_CONTINUE:
+		last = cur;
+		cur = next;
+		break;
+	      case RB_IHASH_STOP:
+		return 0;
+	    }
+	}
+    }
+    return 0;
+}
+
+struct rb_ihash_node *
+rb_ihash_lookup(const struct rb_ihash_tbl *tbl, const struct rb_ihash_node *key)
+{
+    st_index_t hval = tbl->type->hash(key);
+    struct rb_ihash_node **bins = rb_ihash_bins(tbl);
+    size_t pos = rb_ihash_binpos(tbl, hval);
+    struct rb_ihash_node *cur = bins[pos];
+
+    for (; cur; cur = cur->ihash_next) {
+	if (tbl->type->cmp(key, cur) == 0) {
+	    return cur;
+	}
+    }
+    return 0;
+}
+
+static inline void
+rb_ihash_add_pos(struct rb_ihash_tbl *tbl,
+		struct rb_ihash_node *ins, size_t pos)
+{
+    struct rb_ihash_node **bins = rb_ihash_bins(tbl);
+
+    ins->ihash_next = bins[pos];
+    bins[pos] = ins;
+}
+
+static enum rb_ihash_next
+relink_i(struct rb_ihash_node *node, void *ptr)
+{
+    struct rb_ihash_tbl *new_tbl = ptr;
+    st_index_t hval = new_tbl->type->hash(node);
+    size_t pos = rb_ihash_binpos(new_tbl, hval);
+
+    rb_ihash_add_pos(new_tbl, node, pos);
+
+    return RB_IHASH_DETACHED;
+}
+
+static void
+rb_ihash_grow(struct rb_ihash_tbl **oldp)
+{
+    /* start with 16 buckets if we need to become a real hash */
+    static const size_t isize = 1 << 4;
+    struct rb_ihash_tbl *old_tbl = *oldp;
+    size_t old_nbins = rb_ihash_nbins(old_tbl);
+    size_t nbins = (old_nbins == 1) ? isize : (old_nbins << 1);
+    struct rb_ihash_tbl *new_tbl = rb_ihash_alloc(old_tbl->type, nbins);
+
+    rb_ihash_foreach(oldp, relink_i, new_tbl);
+    *oldp = new_tbl;
+    rb_ihash_free(old_tbl);
+}
+
+static void
+rb_ihash_added(struct rb_ihash_tbl **tblp)
+{
+    struct rb_ihash_tbl *tbl = *tblp;
+    size_t nbins = rb_ihash_nbins(tbl);
+
+    tbl->num_entries++;
+    if (tbl->num_entries > (RB_IHASH_MAX_DENSITY * nbins)) {
+	rb_ihash_grow(tblp);
+    }
+}
+
+void
+rb_ihash_add_direct(struct rb_ihash_tbl **tblp, struct rb_ihash_node *ins)
+{
+    struct rb_ihash_tbl *tbl = *tblp;
+    st_index_t hval = tbl->type->hash(ins);
+    size_t pos = rb_ihash_binpos(tbl, hval);
+
+    rb_ihash_add_pos(tbl, ins, pos);
+    rb_ihash_added(tblp);
+}
+
+/* returns pointer to replaced node, 0 if nothing was replaced */
+struct rb_ihash_node *
+rb_ihash_insert(struct rb_ihash_tbl **tblp, struct rb_ihash_node *ins)
+{
+    struct rb_ihash_tbl *tbl = *tblp;
+    st_index_t hval = tbl->type->hash(ins);
+    struct rb_ihash_node **bins = rb_ihash_bins(tbl);
+    size_t i = rb_ihash_binpos(tbl, hval);
+    struct rb_ihash_node *last = NULL;
+    struct rb_ihash_node *cur = bins[i];
+
+    while (cur) {
+	if (tbl->type->cmp(ins, cur) == 0) {
+	    /* replace and return existing entry */
+	    ins->ihash_next = cur->ihash_next;
+	    if (last) last->ihash_next = ins;
+	    else bins[i] = ins;
+	    return cur;
+	}
+	last = cur;
+	cur = cur->ihash_next;
+    }
+    rb_ihash_add_pos(tbl, ins, i);
+    rb_ihash_added(tblp);
+    return 0;
+}
+
+/* returns pointer to detached node, 0 if nothing was attached */
+struct rb_ihash_node *
+rb_ihash_detach(struct rb_ihash_tbl *tbl, const struct rb_ihash_node *key)
+{
+    st_index_t hval = tbl->type->hash(key);
+    struct rb_ihash_node **bins = rb_ihash_bins(tbl);
+    size_t i = rb_ihash_binpos(tbl, hval);
+    struct rb_ihash_node *last = 0;
+    struct rb_ihash_node *cur = bins[i];
+
+    while (cur) {
+	if (tbl->type->cmp(key, cur) == 0) {
+	    if (last) last->ihash_next = cur->ihash_next;
+	    else bins[i] = cur->ihash_next;
+	    tbl->num_entries--;
+	    return cur;
+	}
+	last = cur;
+	cur = cur->ihash_next;
+    }
+
+    return 0;
+}
+
+int
+rb_ihash_update(struct rb_ihash_tbl **tblp, struct rb_ihash_node *upd,
+		rb_ihash_updater fn, void *arg)
+{
+    struct rb_ihash_tbl *tbl = *tblp;
+    st_index_t hval = tbl->type->hash(upd);
+    struct rb_ihash_node **bins = rb_ihash_bins(tbl);
+    size_t i = rb_ihash_binpos(tbl, hval);
+    struct rb_ihash_node *last = NULL;
+    struct rb_ihash_node *cur = bins[i];
+
+    while (cur) {
+	if (tbl->type->cmp(upd, cur) == 0) {
+	    struct rb_ihash_node *next = cur->ihash_next;
+
+	    switch (fn(&cur, upd, arg)) {
+	      case RB_IHASH_UPDATED:
+		cur->ihash_next = next; /* preserve linkage */
+		return 1;
+	      case RB_IHASH_DESTROYED: /* do we need to support this? */
+		if (last) last->ihash_next = next;
+		else bins[i] = 0;
+		return 1;
+	    }
+	}
+	last = cur;
+	cur = cur->ihash_next;
+    }
+
+    cur = 0;
+    switch (fn(&cur, upd, arg)) {
+      case RB_IHASH_UPDATED:
+	rb_ihash_add_pos(tbl, cur, i);
+	rb_ihash_added(tblp);
+	return 0;
+      case RB_IHASH_DESTROYED:
+	rb_bug("RB_IHASH_DESTROYED unexpected");
+    }
+    return 0;
+}
diff --git a/ihash.h b/ihash.h
new file mode 100644
index 0000000..f51378c
--- /dev/null
+++ b/ihash.h
@@ -0,0 +1,115 @@
+/*
+ * Hash table implementation for internal use inside Ruby.
+ * This is based on the container_of macro from ccan.
+ *
+ * Notes:
+ *
+ * - Users are expected to embed the rb_ihash_node struct and key
+ *   inside a main struct stored by users.  This reduces pointer chasing
+ *   and allows cache-warming even on missed lookups.
+ *
+ * - Users should wrap the container_of macro in a static inline to get the
+ *   stored struct pointer from the rb_ihash_node pointer
+ *
+ * - Does no allocation for entries, user is responsible for it
+ *
+ * - This is safe to use outside of GVL and calls no GVL-unsafe functions
+ *   besides rb_bug (in which case it's already too late).  Of course users
+ *   must manage their own locking.
+ */
+#ifndef RUBY_IHASH_H
+#define RUBY_IHASH_H 1
+#if defined(__cplusplus)
+extern "C" {
+#if 0
+} /* satisfy cc-mode */
+#endif
+#endif
+
+#include "ruby/ruby.h"
+#include "ruby/st.h" /* we use st_data_t and st_index_t data types */
+
+/* developers may define this on a per-source basis */
+#ifndef RB_IHASH_MAX_DENSITY
+#  define RB_IHASH_MAX_DENSITY (5)
+#endif
+
+/*
+ * each struct must have its own rb_ihash_node field inside it,
+ * use container_of to get the original struct ptr
+ */
+struct rb_ihash_node;
+struct rb_ihash_node {
+    struct rb_ihash_node *ihash_next;
+};
+
+enum rb_ihash_next {
+    RB_IHASH_CONTINUE = 0,
+    RB_IHASH_CHECK,
+    RB_IHASH_STOP,
+    RB_IHASH_DETACHED /* user must deallocate this manually */
+};
+
+enum rb_ihash_updated {
+    RB_IHASH_UPDATED = 0,
+    RB_IHASH_DESTROYED /* user already deallocated */
+};
+
+typedef int (*rb_ihash_compare)(const struct rb_ihash_node *,
+				const struct rb_ihash_node *);
+typedef st_index_t (*rb_ihash_compute)(const struct rb_ihash_node *);
+typedef enum rb_ihash_next (*rb_ihash_iterate)(struct rb_ihash_node *, void *);
+
+typedef enum rb_ihash_updated (*rb_ihash_updater)(struct rb_ihash_node **cur,
+						  struct rb_ihash_node *upd,
+						  void *arg);
+
+struct rb_ihash_type {
+    rb_ihash_compare cmp;
+    rb_ihash_compute hash;
+};
+
+struct rb_ihash_tbl {
+    const struct rb_ihash_type *type;
+    uint32_t num_entries;
+    uint32_t hash_mask;
+    char flexible_array[1];
+};
+
+struct rb_ihash_tbl *rb_ihash_new(const struct rb_ihash_type *, size_t);
+
+struct rb_ihash_node *
+rb_ihash_lookup(const struct rb_ihash_tbl *, const struct rb_ihash_node *);
+
+struct rb_ihash_node *
+rb_ihash_insert(struct rb_ihash_tbl **, struct rb_ihash_node *);
+
+void rb_ihash_add_direct(struct rb_ihash_tbl **, struct rb_ihash_node *);
+
+struct rb_ihash_node *
+rb_ihash_detach(struct rb_ihash_tbl *, const struct rb_ihash_node *);
+
+int rb_ihash_foreach(struct rb_ihash_tbl **, rb_ihash_iterate, void *);
+
+static inline void
+rb_ihash_free(struct rb_ihash_tbl *tbl)
+{
+    /*
+     * user must call rb_ihash_foreach with an iterator which frees
+     * and returns RB_IHASH_DETACH for each entry before calling this
+     */
+    xfree(tbl);
+}
+
+size_t rb_ihash_memsize(const struct rb_ihash_tbl *);
+
+int rb_ihash_update(struct rb_ihash_tbl **, struct rb_ihash_node *,
+		    rb_ihash_updater, void *arg);
+
+#if defined(__cplusplus)
+#if 0
+{ /* satisfy cc-mode */
+#endif
+}  /* extern "C" { */
+#endif
+#endif /* RUBY_IHASH_H */
-- 
2.0.0.rc0