Subject: [PATCH 2/2] string.c: convert fstring implementation to ihash

From: Eric Wong <[email-masked]>
Date: Wed, 14 May 2014 23:24:14 +0000

This results in ~100K[1] memory savings on start up (with RubyGems
loaded) with no user-visible changes.

While this is not the best example of potential ihash-related memory
savings, there is zero-visible impact related to the loss of hash
ordering from this change.

Per-fstring entry overhead is now 24 bytes per-entry on 64-bit,
half of the previous 48 bytes from st_table_entry_t.

[1] as measured by the time(1) command on eglibc 2.13-38+deb7u1
    (Debian 7.0 on x86-64)
---
 common.mk |   3 +-
 string.c  | 115 +++++++++++++++++++++++++++++++++++++++++++++++---------------
 2 files changed, 89 insertions(+), 29 deletions(-)

diff --git a/common.mk b/common.mk
index 47f32f1..39a03b8 100644
--- a/common.mk
+++ b/common.mk
@@ -758,7 +758,8 @@ st.$(OBJEXT): {$(VPATH)}st.c $(RUBY_H_INCLUDES)
 strftime.$(OBJEXT): {$(VPATH)}strftime.c $(RUBY_H_INCLUDES) \
   {$(VPATH)}timev.h $(ENCODING_H_INCLUDES)
 string.$(OBJEXT): {$(VPATH)}string.c $(RUBY_H_INCLUDES) {$(VPATH)}re.h \
-  {$(VPATH)}regex.h $(ENCODING_H_INCLUDES) {$(VPATH)}internal.h $(PROBES_H_INCLUDES)
+  {$(VPATH)}regex.h $(ENCODING_H_INCLUDES) {$(VPATH)}internal.h $(PROBES_H_INCLUDES) \
+  {$(VPATH)}ihash.h
 struct.$(OBJEXT): {$(VPATH)}struct.c $(RUBY_H_INCLUDES) {$(VPATH)}internal.h
 thread.$(OBJEXT): {$(VPATH)}thread.c {$(VPATH)}eval_intern.h \
   $(RUBY_H_INCLUDES) {$(VPATH)}gc.h $(VM_CORE_H_INCLUDES) \
diff --git a/string.c b/string.c
index c589c80..ed680c4 100644
--- a/string.c
+++ b/string.c
@@ -15,7 +15,9 @@
 #include "ruby/re.h"
 #include "ruby/encoding.h"
 #include "internal.h"
+#include "ihash.h"
 #include "probes.h"
+#include "ccan/container_of/container_of.h"
 #include <assert.h>
 
 #define BEG(no) (regs->beg[(no)])
@@ -173,28 +175,52 @@ mustnot_broken(VALUE str)
     }
 }
 
-static int fstring_cmp(VALUE a, VALUE b);
+static int fstring_cmp(const struct rb_ihash_node *,
+			const struct rb_ihash_node *);
 
-static st_table* frozen_strings;
+static struct rb_ihash_tbl* frozen_strings;
+struct fstring {
+    VALUE fstr;
+    st_index_t hashval;
+    struct rb_ihash_node fstr_node;
+};
+
+struct fstring *
+fstring_of(const struct rb_ihash_node *node)
+{
+    return container_of(node, struct fstring, fstr_node);
+}
+
+static st_index_t
+fstring_hash(const struct rb_ihash_node *ptr)
+{
+    return fstring_of(ptr)->hashval; /* precomputed */
+}
 
-static const struct st_hash_type fstring_hash_type = {
+static const struct rb_ihash_type fstring_hash_type = {
     fstring_cmp,
-    rb_str_hash,
+    fstring_hash,
 };
 
-static int
-fstr_update_callback(st_data_t *key, st_data_t *value, st_data_t arg, int existing)
+static enum rb_ihash_updated
+fstr_update_callback(struct rb_ihash_node **cur_node,
+		     struct rb_ihash_node *upd_node, void *unused)
 {
-    VALUE *fstr = (VALUE *)arg;
-    VALUE str = (VALUE)*key;
+    struct fstring *upd = fstring_of(upd_node);
+    struct fstring *ins;
+    VALUE str;
 
-    if (existing) {
-	/* because of lazy sweep, str may be unmarked already and swept
+    if (*cur_node) {
+	const struct fstring *cur = fstring_of(*cur_node);
+
+	/* because of lazy sweep, cur->fstr may be unmarked already and swept
 	 * at next time */
-	rb_gc_resurrect(*fstr = *key);
-	return ST_STOP;
+	rb_gc_resurrect(upd->fstr = cur->fstr);
+	return RB_IHASH_UPDATED;
     }
 
+    /* create new node */
+    str = upd->fstr;
     if (STR_SHARED_P(str)) {
 	/* str should not be shared */
 	str = rb_enc_str_new(RSTRING_PTR(str), RSTRING_LEN(str), STR_ENC_GET(str));
@@ -204,42 +230,58 @@ fstr_update_callback(st_data_t *key, st_data_t *value, st_data_t arg, int existi
 	str = rb_str_new_frozen(str);
     }
     RBASIC(str)->flags |= RSTRING_FSTR;
+    ins = ALLOC(struct fstring);
+    ins->hashval = upd->hashval;
+    upd->fstr = ins->fstr = str;
+    *cur_node = &ins->fstr_node; /* trigger insert */
 
-    *key = *value = *fstr = str;
-    return ST_CONTINUE;
+    return RB_IHASH_UPDATED;
 }
 
 VALUE
 rb_fstring(VALUE str)
 {
-    VALUE fstr = Qnil;
+    struct fstring fstr;
     Check_Type(str, T_STRING);
 
     if (!frozen_strings)
-	frozen_strings = st_init_table(&fstring_hash_type);
+	frozen_strings = rb_ihash_new(&fstring_hash_type, 0);
 
     if (FL_TEST(str, RSTRING_FSTR))
 	return str;
 
-    st_update(frozen_strings, (st_data_t)str, fstr_update_callback, (st_data_t)&fstr);
-    return fstr;
+    fstr.fstr = str;
+    fstr.hashval = rb_str_hash(str);
+    rb_ihash_update(&frozen_strings, &fstr.fstr_node, fstr_update_callback, 0);
+    return fstr.fstr;
 }
 
-static int
-fstring_set_class_i(st_data_t key, st_data_t val, st_data_t arg)
+static enum rb_ihash_next
+fstring_set_class_i(struct rb_ihash_node *node, void *arg)
 {
-    RBASIC_SET_CLASS((VALUE)key, (VALUE)arg);
-    return ST_CONTINUE;
+    VALUE klass = (VALUE)arg;
+    struct fstring *fstr = fstring_of(node);
+
+    RBASIC_SET_CLASS((VALUE)fstr->fstr, klass);
+    return RB_IHASH_CONTINUE;
 }
 
 static int
-fstring_cmp(VALUE a, VALUE b)
+fstring_cmp(const struct rb_ihash_node *na, const struct rb_ihash_node *nb)
 {
-    int cmp = rb_str_hash_cmp(a, b);
+    struct fstring *a = fstring_of(na);
+    struct fstring *b = fstring_of(nb);
+    int cmp;
+
+    if (a->hashval != b->hashval) {
+	return 1;
+    }
+
+    cmp = rb_str_hash_cmp(a->fstr, b->fstr);
     if (cmp != 0) {
 	return cmp;
     }
-    return ENCODING_GET(b) - ENCODING_GET(a);
+    return ENCODING_GET(b->fstr) - ENCODING_GET(a->fstr);
 }
 
 static inline int
@@ -907,12 +949,29 @@ rb_free_tmp_buffer(volatile VALUE *store)
     if (s) rb_str_clear(s);
 }
 
+static void
+fstring_delete(VALUE str)
+{
+    struct fstring fstr;
+    struct rb_ihash_node *node;
+
+    fstr.fstr = str;
+    fstr.hashval = rb_str_hash(str);
+    node = rb_ihash_detach(frozen_strings, &fstr.fstr_node);
+    if (node) {
+	struct fstring *del = fstring_of(node);
+	xfree(del);
+    }
+    else {
+	rb_bug("RSTRING_FSTR consistency error"); /* do we need this? */
+    }
+}
+
 void
 rb_str_free(VALUE str)
 {
     if (FL_TEST(str, RSTRING_FSTR)) {
-	st_data_t fstr = (st_data_t)str;
-	st_delete(frozen_strings, &fstr, NULL);
+	fstring_delete(str);
     }
 
     if (!STR_EMBED_P(str) && !FL_TEST(str, STR_SHARED)) {
@@ -8883,5 +8942,5 @@ Init_String(void)
     rb_define_method(rb_cSymbol, "encoding", sym_encoding, 0);
 
     if (frozen_strings)
-	st_foreach(frozen_strings, fstring_set_class_i, rb_cString);
+	rb_ihash_foreach(&frozen_strings, fstring_set_class_i, (void *)rb_cString);
 }
-- 
2.0.0.rc0