From 02fbb2c21134ad0e8df0b723a4b11f7d7e21edcd Mon Sep 17 00:00:00 2001
From: "Yukihiro \"Matz\" Matsumoto" <matz@ruby.or.jp>
Date: Thu, 24 Jan 2019 17:57:12 +0900
Subject: Remove symbol hash table from `mrb_state` structure.

Use linear search instead. Number of symbols is usually small (<1K), so
we don't need performance boost from hash tables. In our benchmark
measurement, hash tables consumes 790KB for `build/full-debug/mrbtest`.
---
 src/symbol.c | 69 +++++++++++++++++++++---------------------------------------
 1 file changed, 24 insertions(+), 45 deletions(-)

(limited to 'src')

diff --git a/src/symbol.c b/src/symbol.c
index bed918241..bebbb8e85 100644
--- a/src/symbol.c
+++ b/src/symbol.c
@@ -19,24 +19,6 @@ typedef struct symbol_name {
   const char *name;
 } symbol_name;
 
-static inline khint_t
-sym_hash_func(mrb_state *mrb, mrb_sym s)
-{
-  khint_t h = 0;
-  size_t i, len = mrb->symtbl[s].len;
-  const char *p = mrb->symtbl[s].name;
-
-  for (i=0; i<len; i++) {
-    h = (h << 5) - h + *p++;
-  }
-  return h;
-}
-#define sym_hash_equal(mrb,a, b) (mrb->symtbl[a].len == mrb->symtbl[b].len && memcmp(mrb->symtbl[a].name, mrb->symtbl[b].name, mrb->symtbl[a].len) == 0)
-
-KHASH_DECLARE(n2s, mrb_sym, mrb_sym, FALSE)
-KHASH_DEFINE (n2s, mrb_sym, mrb_sym, FALSE, sym_hash_func, sym_hash_equal)
-/* ------------------------------------------------------ */
-
 static void
 sym_validate_len(mrb_state *mrb, size_t len)
 {
@@ -45,24 +27,31 @@ sym_validate_len(mrb_state *mrb, size_t len)
   }
 }
 
+static mrb_sym
+find_symbol(mrb_state *mrb, const char *name, uint16_t len)
+{
+  mrb_sym i;
+  symbol_name *sname;
+
+  /* search for a symbol */
+  for (i=1; i<=mrb->symidx; i++) {
+    sname = &mrb->symtbl[i];
+    if (sname->len == len && memcmp(sname->name, name, len) == 0) {
+      return i;
+    }
+  }
+  return 0;
+}
+
 static mrb_sym
 sym_intern(mrb_state *mrb, const char *name, size_t len, mrb_bool lit)
 {
-  khash_t(n2s) *h = mrb->name2sym;
-  symbol_name *sname = mrb->symtbl; /* symtbl[0] for working memory */
-  khiter_t k;
   mrb_sym sym;
-  char *p;
+  symbol_name *sname;
 
   sym_validate_len(mrb, len);
-  if (sname) {
-    sname->lit = lit;
-    sname->len = (uint16_t)len;
-    sname->name = name;
-    k = kh_get(n2s, mrb, h, 0);
-    if (k != kh_end(h))
-      return kh_key(h, k);
-  }
+  sym = find_symbol(mrb, name, len);
+  if (sym > 0) return sym;
 
   /* registering a new symbol */
   sym = ++mrb->symidx;
@@ -78,13 +67,12 @@ sym_intern(mrb_state *mrb, const char *name, size_t len, mrb_bool lit)
     sname->lit = TRUE;
   }
   else {
-    p = (char *)mrb_malloc(mrb, len+1);
+    char *p = (char *)mrb_malloc(mrb, len+1);
     memcpy(p, name, len);
     p[len] = 0;
     sname->name = (const char*)p;
     sname->lit = FALSE;
   }
-  kh_put(n2s, mrb, h, sym);
 
   return sym;
 }
@@ -116,25 +104,18 @@ mrb_intern_str(mrb_state *mrb, mrb_value str)
 MRB_API mrb_value
 mrb_check_intern(mrb_state *mrb, const char *name, size_t len)
 {
-  khash_t(n2s) *h = mrb->name2sym;
-  symbol_name *sname = mrb->symtbl;
-  khiter_t k;
+  mrb_sym sym;
 
   sym_validate_len(mrb, len);
-  sname->len = (uint16_t)len;
-  sname->name = name;
-
-  k = kh_get(n2s, mrb, h, 0);
-  if (k != kh_end(h)) {
-    return mrb_symbol_value(kh_key(h, k));
-  }
+  sym = find_symbol(mrb, name, len);
+  if (sym > 0) return mrb_symbol_value(sym);
   return mrb_nil_value();
 }
 
 MRB_API mrb_value
 mrb_check_intern_cstr(mrb_state *mrb, const char *name)
 {
-  return mrb_check_intern(mrb, name, (mrb_int)strlen(name));
+  return mrb_check_intern(mrb, name, strlen(name));
 }
 
 MRB_API mrb_value
@@ -166,13 +147,11 @@ mrb_free_symtbl(mrb_state *mrb)
     }
   }
   mrb_free(mrb, mrb->symtbl);
-  kh_destroy(n2s, mrb, mrb->name2sym);
 }
 
 void
 mrb_init_symtbl(mrb_state *mrb)
 {
-  mrb->name2sym = kh_init(n2s, mrb);
 }
 
 /**********************************************************************
-- 
cgit v1.2.3