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`.
MODIFY
include/mruby.h
include/mruby.h
@@ -239,7 +239,6 @@ typedef struct mrb_state {
#endif
mrb_sym symidx;
- struct kh_n2s *name2sym; /* symbol hash */
struct symbol_name *symtbl; /* symbol table */
size_t symcapa;

MODIFY
src/symbol.c
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);
}
/**********************************************************************

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`.