Skip to content

Instantly share code, notes, and snippets.

@methodmissing

methodmissing/bench_with_memoized_obj_hash.txt

Created January 10, 2010 22:05
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save methodmissing/273812 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save methodmissing/273812 to your computer and use it in GitHub Desktop.
Download ZIP
Memoized obj hash values - ree 187-248
Raw
bench_with_memoized_obj_hash.txt
methodmissing:rubyenterpriseedition187-248 lourens$ ./ruby -Ilib obj_hash_bench.rb
Rehearsal ---------------------------------------------------
Hash#[:array] 0.030000 0.000000 0.030000 ( 0.030316)
Hash#[:bignum] 0.030000 0.000000 0.030000 ( 0.027775)
Hash#[:hash] 0.030000 0.000000 0.030000 ( 0.030893)
Hash#[:numeric] 0.030000 0.000000 0.030000 ( 0.030195)
Hash#[:range] 0.030000 0.000000 0.030000 ( 0.029430)
Hash#[:time] 0.030000 0.000000 0.030000 ( 0.029966)
Hash#[:rexp] 0.030000 0.000000 0.030000 ( 0.029690)
Hash#[:string] 0.030000 0.000000 0.030000 ( 0.032869)
Hash#[:struct] 0.030000 0.000000 0.030000 ( 0.029657)
------------------------------------------ total: 0.270000sec
user system total real
Hash#[:array] 0.030000 0.000000 0.030000 ( 0.029903)
Hash#[:bignum] 0.030000 0.000000 0.030000 ( 0.028384)
Hash#[:hash] 0.030000 0.000000 0.030000 ( 0.030309)
Hash#[:numeric] 0.030000 0.000000 0.030000 ( 0.030462)
Hash#[:range] 0.030000 0.000000 0.030000 ( 0.029502)
Hash#[:time] 0.030000 0.000000 0.030000 ( 0.030113)
Hash#[:rexp] 0.030000 0.000000 0.030000 ( 0.029499)
Hash#[:string] 0.030000 0.000000 0.030000 ( 0.033322)
Hash#[:struct] 0.020000 0.000000 0.020000 ( 0.029190)
Raw
bench_without_memoized_obj_hash.txt
methodmissing:rubyenterpriseedition187-248 lourens$ ./ruby -Ilib obj_hash_bench.rb
Rehearsal ---------------------------------------------------
Hash#[:array] 0.120000 0.000000 0.120000 ( 0.121220)
Hash#[:bignum] 0.030000 0.000000 0.030000 ( 0.027572)
Hash#[:hash] 0.140000 0.000000 0.140000 ( 0.147341)
Hash#[:numeric] 0.030000 0.000000 0.030000 ( 0.035678)
Hash#[:range] 0.060000 0.000000 0.060000 ( 0.062380)
Hash#[:time] 0.040000 0.000000 0.040000 ( 0.035004)
Hash#[:rexp] 0.040000 0.000000 0.040000 ( 0.037965)
Hash#[:string] 0.040000 0.000000 0.040000 ( 0.048828)
Hash#[:struct] 0.040000 0.000000 0.040000 ( 0.034160)
------------------------------------------ total: 0.540000sec
user system total real
Hash#[:array] 0.120000 0.000000 0.120000 ( 0.121400)
Hash#[:bignum] 0.030000 0.000000 0.030000 ( 0.028326)
Hash#[:hash] 0.150000 0.000000 0.150000 ( 0.148170)
Hash#[:numeric] 0.030000 0.000000 0.030000 ( 0.035752)
Hash#[:range] 0.060000 0.000000 0.060000 ( 0.063136)
Hash#[:time] 0.030000 0.000000 0.030000 ( 0.034874)
Hash#[:rexp] 0.040000 0.000000 0.040000 ( 0.038298)
Hash#[:string] 0.050000 0.000000 0.050000 ( 0.048600)
Hash#[:struct] 0.040000 0.000000 0.040000 ( 0.034489)
Raw
gistfile1.txt
diff --git a/array.c b/array.c
index 89f74d0..8535cae 100644
--- a/array.c
+++ b/array.c
@@ -15,6 +15,7 @@
#include "ruby.h"
#include "util.h"
#include "st.h"
+#include "hash_cache.h"
VALUE rb_cArray;
static ID id_cmp;
@@ -61,7 +62,7 @@ rb_ary_modify(ary)
VALUE ary;
{
VALUE *ptr;
-
+ COND_EXPIRE_CACHED_OBJ_HASH(ary);
rb_ary_modify_check(ary);
if (FL_TEST(ary, ELTS_SHARED)) {
ptr = ALLOC_N(VALUE, RARRAY(ary)->len);
@@ -2703,17 +2704,17 @@ recursive_hash(ary, dummy, recur)
{
long i, h;
VALUE n;
-
if (recur) {
return LONG2FIX(0);
}
-
+ GET_CACHED_OBJ_HASH(ary);
h = RARRAY(ary)->len;
for (i=0; i<RARRAY(ary)->len; i++) {
h = (h << 1) | (h<0 ? 1 : 0);
n = rb_hash(RARRAY(ary)->ptr[i]);
h ^= NUM2LONG(n);
}
+ CACHE_OBJ_HASH(ary,h);
return LONG2FIX(h);
}
diff --git a/bignum.c b/bignum.c
index 8e27369..f102652 100644
--- a/bignum.c
+++ b/bignum.c
@@ -12,6 +12,7 @@
#include "ruby.h"
#include "rubysig.h"
+#include "hash_cache.h"
#include <math.h>
#include <float.h>
@@ -2230,11 +2231,13 @@ rb_big_hash(x)
{
long i, len, key;
BDIGIT *digits;
+ GET_CACHED_OBJ_HASH(x);
key = 0; digits = BDIGITS(x); len = RBIGNUM(x)->len;
for (i=0; i<len; i++) {
key ^= *digits++;
}
+ CACHE_OBJ_HASH_DIRECT(x,key);
return LONG2FIX(key);
}
diff --git a/gc.c b/gc.c
index 8c1c6d6..5c7d31a 100644
--- a/gc.c
+++ b/gc.c
@@ -18,6 +18,7 @@
#include "node.h"
#include "env.h"
#include "re.h"
+#include "hash_cache.h"
#include <stdio.h>
#include <setjmp.h>
#include <math.h>
@@ -1919,6 +1920,7 @@ static int
obj_free(obj)
VALUE obj;
{
+ st_data_t hsh;
switch (BUILTIN_TYPE(obj)) {
case T_NIL:
case T_FIXNUM:
@@ -1927,7 +1929,7 @@ obj_free(obj)
rb_bug("obj_free() called for broken object");
break;
}
-
+ FREE_CACHED_OBJ_HASH(obj);
if (FL_TEST(obj, FL_EXIVAR)) {
rb_free_generic_ivar((VALUE)obj);
}
diff --git a/hash.c b/hash.c
index 8086e22..2902f6e 100644
--- a/hash.c
+++ b/hash.c
@@ -16,6 +16,7 @@
#include "st.h"
#include "util.h"
#include "rubysig.h"
+#include "hash_cache.h"
#ifdef __APPLE__
#include <crt_externs.h>
@@ -28,6 +29,7 @@ static void
rb_hash_modify(hash)
VALUE hash;
{
+ COND_EXPIRE_CACHED_OBJ_HASH(hash);
if (!RHASH(hash)->tbl) rb_raise(rb_eTypeError, "uninitialized Hash");
if (OBJ_FROZEN(hash)) rb_error_frozen("hash");
if (!OBJ_TAINTED(hash) && rb_safe_level() >= 4)
@@ -81,14 +83,19 @@ VALUE
rb_hash(obj)
VALUE obj;
{
+ long hash;
+ GET_CACHED_OBJ_HASH(obj);
VALUE hval = rb_funcall(obj, id_hash, 0);
retry:
switch (TYPE(hval)) {
case T_FIXNUM:
+ CACHE_OBJ_HASH(obj,FIX2LONG(hval));
return hval;
case T_BIGNUM:
- return LONG2FIX(((long*)(RBIGNUM_DIGITS(hval)))[0]);
+ hash = ((long*)(RBIGNUM_DIGITS(hval)))[0];
+ CACHE_OBJ_HASH(obj,hash);
+ return LONG2FIX(hash);
default:
hval = rb_to_int(hval);
diff --git a/hash_cache.h b/hash_cache.h
new file mode 100644
index 0000000..c29b049
--- /dev/null
+++ b/hash_cache.h
@@ -0,0 +1,41 @@
+#ifndef HASH_CACHE_H
+#define HASH_CACHE_H
+#include "st.h"
+
+RUBY_EXTERN st_table *rb_obj_hash_cache;
+
+#define LIKELY_CACHE_OBJ_HASH FL_USER6
+#define CACHED_OBJ_HASH FL_USER7
+#define FREE_CACHED_OBJ_HASH(obj) do {\
+ if FL_TEST(obj,CACHED_OBJ_HASH){ \
+ st_lookup(rb_obj_hash_cache, (st_data_t)obj, &hsh); \
+ st_delete(rb_obj_hash_cache, (st_data_t*)obj, &hsh); \
+ } \
+} while (0)
+#define EXPIRE_CACHED_OBJ_HASH(obj) FREE_CACHED_OBJ_HASH(obj)
+#define COND_EXPIRE_CACHED_OBJ_HASH(obj) do {\
+ st_data_t hsh; \
+ if FL_TEST(obj,CACHED_OBJ_HASH){ \
+ EXPIRE_CACHED_OBJ_HASH(obj); \
+ FL_UNSET(obj,CACHED_OBJ_HASH); \
+ } \
+} while (0)
+#define CACHE_OBJ_HASH_DIRECT(obj,val) do {\
+ st_add_direct(rb_obj_hash_cache, (st_data_t)obj, (st_data_t)val); \
+ FL_SET(obj,CACHED_OBJ_HASH); \
+} while (0)
+#define CACHE_OBJ_HASH(obj,val) do {\
+ if(FL_TEST(obj,LIKELY_CACHE_OBJ_HASH)){ \
+ CACHE_OBJ_HASH_DIRECT(obj,val); \
+ }else{ \
+ FL_SET(obj,LIKELY_CACHE_OBJ_HASH); \
+ } \
+} while (0)
+#define GET_CACHED_OBJ_HASH(obj) do {\
+ st_data_t cached_hash; \
+ if FL_TEST(obj,CACHED_OBJ_HASH){ \
+ st_lookup(rb_obj_hash_cache, (st_data_t)obj, &cached_hash); \
+ return LONG2FIX(cached_hash); \
+ } \
+} while (0)
+#endif
\ No newline at end of file
diff --git a/numeric.c b/numeric.c
index 634c2eb..c6091e2 100644
--- a/numeric.c
+++ b/numeric.c
@@ -12,6 +12,7 @@
#include "ruby.h"
#include "env.h"
+#include "hash_cache.h"
#include <ctype.h>
#include <math.h>
#include <stdio.h>
@@ -892,7 +893,7 @@ flo_hash(num)
double d;
char *c;
int i, hash;
-
+ GET_CACHED_OBJ_HASH(num);
d = RFLOAT(num)->value;
if (d == 0) d = fabs(d);
c = (char*)&d;
@@ -900,6 +901,7 @@ flo_hash(num)
hash = (hash * 971) ^ (unsigned char)c[i];
}
if (hash < 0) hash = -hash;
+ CACHE_OBJ_HASH_DIRECT(num,(long)hash);
return INT2FIX(hash);
}
diff --git a/range.c b/range.c
index 864ca9f..4f1a43c 100644
--- a/range.c
+++ b/range.c
@@ -11,6 +11,7 @@
**********************************************************************/
#include "ruby.h"
+#include "hash_cache.h"
VALUE rb_cRange;
static ID id_cmp, id_succ, id_beg, id_end, id_excl;
@@ -212,13 +213,13 @@ range_hash(range)
{
long hash = EXCL(range);
VALUE v;
-
+ GET_CACHED_OBJ_HASH(range);
v = rb_hash(rb_ivar_get(range, id_beg));
hash ^= v << 1;
v = rb_hash(rb_ivar_get(range, id_end));
hash ^= v << 9;
hash ^= EXCL(range) << 24;
-
+ CACHE_OBJ_HASH_DIRECT(range,hash);
return LONG2FIX(hash);
}
diff --git a/re.c b/re.c
index f2ac99f..4898935 100644
--- a/re.c
+++ b/re.c
@@ -12,6 +12,7 @@
#include "ruby.h"
#include "re.h"
#include <ctype.h>
+#include "hash_cache.h"
VALUE rb_eRegexpError;
@@ -1533,7 +1534,7 @@ rb_reg_hash(re)
{
int hashval, len;
char *p;
-
+ GET_CACHED_OBJ_HASH(re);
rb_reg_check(re);
hashval = RREGEXP(re)->ptr->options;
len = RREGEXP(re)->len;
@@ -1542,7 +1543,7 @@ rb_reg_hash(re)
hashval = hashval * 33 + *p++;
}
hashval = hashval + (hashval>>5);
-
+ CACHE_OBJ_HASH_DIRECT(re,(long)hashval);
return INT2FIX(hashval);
}
diff --git a/ruby.h b/ruby.h
index 4d003a8..84652cb 100644
--- a/ruby.h
+++ b/ruby.h
@@ -785,4 +785,4 @@ void ruby_native_thread_kill _((int));
} /* extern "C" { */
#endif
-#endif /* ifndef RUBY_H */
+#endif /* ifndef RUBY_H */
\ No newline at end of file
diff --git a/string.c b/string.c
index 69430c6..05d06b3 100644
--- a/string.c
+++ b/string.c
@@ -14,6 +14,7 @@
#include "ruby.h"
#include "re.h"
+#include "hash_cache.h"
#define BEG(no) regs->beg[no]
#define END(no) regs->end[no]
@@ -27,9 +28,9 @@
VALUE rb_cString;
-#define STR_TMPLOCK FL_USER1
-#define STR_ASSOC FL_USER3
-#define STR_NOCAPA (ELTS_SHARED|STR_ASSOC)
+#define STR_TMPLOCK FL_USER1
+#define STR_ASSOC FL_USER3
+#define STR_NOCAPA (ELTS_SHARED|STR_ASSOC)
#define RESIZE_CAPA(str,capacity) do {\
REALLOC_N(RSTRING(str)->ptr, char, (capacity)+1);\
@@ -508,6 +509,7 @@ void
rb_str_modify(str)
VALUE str;
{
+ COND_EXPIRE_CACHED_OBJ_HASH(str);
if (!str_independent(str))
str_make_independent(str);
}
@@ -882,7 +884,11 @@ rb_str_hash(str)
register long len = RSTRING(str)->len;
register char *p = RSTRING(str)->ptr;
register int key = 0;
-
+ st_data_t cached_key;
+ if FL_TEST(str,CACHED_OBJ_HASH){
+ st_lookup(rb_obj_hash_cache, str, &cached_key);
+ return (int)cached_key;
+ }
#if defined(HASH_ELFHASH)
register unsigned int g;
@@ -908,6 +914,7 @@ rb_str_hash(str)
}
key = key + (key>>5);
#endif
+ CACHE_OBJ_HASH(str,key);
return key;
}
diff --git a/struct.c b/struct.c
index 9417c1c..8e15f91 100644
--- a/struct.c
+++ b/struct.c
@@ -12,6 +12,7 @@
#include "ruby.h"
#include "env.h"
+#include "hash_cache.h"
VALUE rb_cStruct;
@@ -153,6 +154,7 @@ static void
rb_struct_modify(s)
VALUE s;
{
+ COND_EXPIRE_CACHED_OBJ_HASH(s);
if (OBJ_FROZEN(s)) rb_error_frozen("Struct");
if (!OBJ_TAINTED(s) && rb_safe_level() >= 4)
rb_raise(rb_eSecurityError, "Insecure: can't modify Struct");
@@ -812,13 +814,14 @@ rb_struct_hash(s)
{
long i, h;
VALUE n;
-
+ GET_CACHED_OBJ_HASH(s);
h = rb_hash(rb_obj_class(s));
for (i = 0; i < RSTRUCT(s)->len; i++) {
h = (h << 1) | (h<0 ? 1 : 0);
n = rb_hash(RSTRUCT(s)->ptr[i]);
h ^= NUM2LONG(n);
}
+ CACHE_OBJ_HASH(s,h);
return LONG2FIX(h);
}
diff --git a/time.c b/time.c
index 5cd1c9e..aab92d6 100644
--- a/time.c
+++ b/time.c
@@ -14,6 +14,7 @@
#include <sys/types.h>
#include <time.h>
#include <errno.h>
+#include "hash_cache.h"
#ifdef HAVE_UNISTD_H
#include <unistd.h>
@@ -63,6 +64,7 @@ static void
time_modify(time)
VALUE time;
{
+ COND_EXPIRE_CACHED_OBJ_HASH(time);
rb_check_frozen(time);
if (!OBJ_TAINTED(time) && rb_safe_level() >= 4)
rb_raise(rb_eSecurityError, "Insecure: can't modify Time");
@@ -1047,9 +1049,10 @@ time_hash(time)
{
struct time_object *tobj;
long hash;
-
+ GET_CACHED_OBJ_HASH(time);
GetTimeval(time, tobj);
hash = tobj->tv.tv_sec ^ tobj->tv.tv_usec;
+ CACHE_OBJ_HASH(time,hash);
return LONG2FIX(hash);
}
diff --git a/variable.c b/variable.c
index 53143ca..666b7f5 100644
--- a/variable.c
+++ b/variable.c
@@ -20,6 +20,7 @@
st_table *rb_global_tbl;
st_table *rb_class_tbl;
+st_table *rb_obj_hash_cache;
static ID autoload, classpath, tmp_classpath;
void
@@ -27,6 +28,7 @@ Init_var_tables()
{
rb_global_tbl = st_init_numtable();
rb_class_tbl = st_init_numtable();
+ rb_obj_hash_cache = st_init_numtable();
autoload = rb_intern("__autoload__");
classpath = rb_intern("__classpath__");
tmp_classpath = rb_intern("__tmp_classpath__");
Raw
obj_hash_bench.rb
require "benchmark"
ObjArray = %w(a b c d e)
ObjBignum = 3233232322233323
ObjHash = { :a => 'a', :b => 'b', :c => 'c' }
ObjNumeric = 12.337869
ObjRange = 'a'..'z'
ObjTime = Time.now
ObjRexp = /[\d]{1,3}:[\d]{1,3}/
ObjString = 'a' * 100
ObjStruct = Struct.new(:a,:b,:c,:d,:e,:f,:g,:h)
HASH = { ObjArray => :array,
ObjBignum => :bignum,
ObjHash => :hash,
ObjNumeric => :numeric,
ObjRange => :range,
ObjTime => :time,
ObjRexp => :rexp,
ObjString => :string,
ObjStruct => :struct, }
TESTS = 100_000
Benchmark.bmbm do |results|
results.report("Hash#[:array]") { TESTS.times { HASH[ObjArray] } }
results.report("Hash#[:bignum]") { TESTS.times { HASH[ObjBignum] } }
results.report("Hash#[:hash]") { TESTS.times { HASH[ObjHash] } }
results.report("Hash#[:numeric]") { TESTS.times { HASH[ObjNumeric] } }
results.report("Hash#[:range]") { TESTS.times { HASH[ObjRange] } }
results.report("Hash#[:time]") { TESTS.times { HASH[ObjTime] } }
results.report("Hash#[:rexp]") { TESTS.times { HASH[ObjRexp] } }
results.report("Hash#[:string]") { TESTS.times { HASH[ObjString] } }
results.report("Hash#[:struct]") { TESTS.times { HASH[ObjStruct] } }
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment