From: nobu.nakada@... Date: 2002-01-18T13:05:08+09:00 Subject: [ruby-dev:15709] Re: method cache なかだです。 At Thu, 17 Jan 2002 22:46:54 +0900, Takaaki Tateishi wrote: > 僕が想定していたのは違って，次のような感じにしておけば > 良いなと思っていました．damageを受けたmidを*全部*保存し > ておくのです． > > struct damaged_entry { > ID mid; > struct damaged_entry *mid; > } > static struct damaged_entry *cache_damage[CACHE_SIZE]; > /* あとはご想像におまかせ… */ > > そのため，ひょっとして速度は多少落ちるかと思っていましたので… これは要するにハッシュですね。検索とクリア/解放のオーバーヘッド でトントンぐらいになるかもと思いましたが、以外とそうでもないよ うです。試してみた感じではカウントより速いかも知れません。 > 中田さんの方法だと，異なるIDに対して同じスロットが使われた時 > にやっぱり問題になる気がしますがどうなのでしょう? 二つ目のほうは間違ってますね。 > そして，先ほど僕もつけてしまっていましたが，/* is it in the > method cache? */ のコメントの後ろではキャッシュが変更されて > いないのでCACHE_DAMAGEは必要ないかもしれません． そうですね。結局CACHE_DAMAGE()はrb_get_method_body()の最初の一ヶ 所だけになりそうです。 > 中田さんのものを参考にして多少変えてみました．カウントする方 > 法だとこんな感じでしょうか? ついでにmidを全部st_tableで保存しておくのも試してみました。 type1がカウント、type2がst_tableを使ったハッシュ、type3が自前で 実装したハッシュです。 かなり恣意的なテストですが、これで見る限りでは、キャッシュをク リアしない場合はほぼどれでも誤差の範囲、キャッシュのクリアは type2 ≒ type3 > type1 >> origといったところでしょうか。 require 'rubyunit' class TestCache < TestCase def nothing end def with_cache(count) count.times {nothing} end def with_clear(range) class << self; self; end.module_eval do meth = proc {} range.each do |mid| define_method(mid, meth) remove_method(mid) end end end def test_cache_1000 with_cache(1000) end def test_cache_10000 with_cache(10000) end def test_clear_1000 with_clear("a000".."a999") end def test_clear_10000 with_clear("a0000".."a9999") end end orig TestCache#test_cache_1000 . Time: 0.002333 OK (1/1 tests 0 asserts) type1 TestCache#test_cache_1000 . Time: 0.002386 OK (1/1 tests 0 asserts) type2 TestCache#test_cache_1000 . Time: 0.002394 OK (1/1 tests 0 asserts) type3 TestCache#test_cache_1000 . Time: 0.002399 OK (1/1 tests 0 asserts) orig TestCache#test_cache_10000 . Time: 0.017194 OK (1/1 tests 0 asserts) type1 TestCache#test_cache_10000 . Time: 0.01665 OK (1/1 tests 0 asserts) type2 TestCache#test_cache_10000 . Time: 0.016749 OK (1/1 tests 0 asserts) type3 TestCache#test_cache_10000 . Time: 0.017005 OK (1/1 tests 0 asserts) orig TestCache#test_clear_1000 . Time: 0.079843 OK (1/1 tests 0 asserts) type1 TestCache#test_clear_1000 . Time: 0.037267 OK (1/1 tests 0 asserts) type2 TestCache#test_clear_1000 . Time: 0.024166 OK (1/1 tests 0 asserts) type3 TestCache#test_clear_1000 . Time: 0.024435 OK (1/1 tests 0 asserts) orig TestCache#test_clear_10000 . Time: 0.790927 OK (1/1 tests 0 asserts) type1 TestCache#test_clear_10000 . Time: 0.28626 OK (1/1 tests 0 asserts) type2 TestCache#test_clear_10000 . Time: 0.236766 OK (1/1 tests 0 asserts) type3 TestCache#test_clear_10000 . Time: 0.240431 OK (1/1 tests 0 asserts) Index: eval.c =================================================================== RCS file: /cvs/ruby/src/ruby/eval.c,v retrieving revision 1.246 diff -u -2 -p -r1.246 eval.c --- eval.c 2002/01/17 08:04:57 1.246 +++ eval.c 2002/01/18 03:38:12 @@ -188,4 +188,76 @@ struct cache_entry { /* method hash tab static struct cache_entry cache[CACHE_SIZE]; +#if CACHE_DAMAGE_TYPE == 1 +static int cache_damage[CACHE_SIZE]; +#define Init_cache() ((void)0) +#define CACHE_DAMAGE(id) (cache_damage[(id)&CACHE_MASK]++) +#define CACHE_UNDAMAGE(id) ((cache_damage[(id)&CACHE_MASK] == 1) ? (cache_damage[(id)&CACHE_MASK] = 0) : 0) +#define CACHE_DAMAGED_P(id) (cache_damage[(id)&CACHE_MASK]) +#define CACHE_CLEAR_DAMAGE() memset(cache_damage, 0, sizeof cache_damage) +#elif CACHE_DAMAGE_TYPE == 2 +static st_table *cache_damage; +#define Init_cache() (cache_damage = st_init_numtable_with_size(CACHE_SIZE)) +#define CACHE_DAMAGE(id) st_insert(cache_damage, (char *)(id), NULL) +#define CACHE_UNDAMAGE(id) ((void)(id)) +#define CACHE_DAMAGED_P(id) st_delete(cache_damage, (char **)&(id), NULL) +#define CACHE_CLEAR_DAMAGE() st_cleanup_safe(cache_damage, 0) +#elif CACHE_DAMAGE_TYPE == 3 +struct damaged_entry { + ID mid; + struct damaged_entry *next; +}; +static struct damaged_entry *cache_damage[CACHE_SIZE]; +#define Init_cache() ((void)0) +#define CACHE_DAMAGE(id) damage(id) +#define CACHE_UNDAMAGE(id) ((void)(id)) +#define CACHE_DAMAGED_P(id) damaged_p(id) +#define CACHE_CLEAR_DAMAGE() clear_damage() +static void damage _((ID id)); +static int damaged_p _((ID id)); +static void clear_damage _((void)); +static void damage(id) + ID id; +{ + struct damaged_entry *ent, **entp = &cache_damage[id & CACHE_MASK]; + for (ent = *entp; ent; ent = ent->next) { + if (ent->mid == id) return; + } + ent = ALLOC(struct damaged_entry); + ent->mid = id; + ent->next = *entp; + *entp = ent; +} +static int damaged_p(id) + ID id; +{ + struct damaged_entry *ent = cache_damage[id & CACHE_MASK]; + for (; ent; ent = ent->next) { + if (ent->mid == id) return 1; + } + return 0; +} +static void clear_damage() +{ + struct damaged_entry **ent = cache_damage, **end = cache_damage + CACHE_SIZE; + for (; ent < end; ent++) { + struct damaged_entry *ptr = *ent; + if (ptr) { + do { + struct damaged_entry *next = ptr->next; + free(ptr); + ptr = next; + } while (ptr); + *ent = NULL; + } + } +} +#else +#define Init_cache() ((void)0) +#define CACHE_DAMAGE(id) ((void)(id)) +#define CACHE_UNDAMAGE(id) ((void)(id)) +#define CACHE_DAMAGED_P(id) (1) +#define CACHE_CLEAR_DAMAGE() ((void)0) +#endif + void rb_clear_cache() @@ -198,4 +270,5 @@ rb_clear_cache() ent++; } + CACHE_CLEAR_DAMAGE(); } @@ -206,4 +279,6 @@ rb_clear_cache_by_id(id) struct cache_entry *ent, *end; + if (!CACHE_DAMAGED_P(id)) return; + CACHE_UNDAMAGE(id); ent = cache; end = ent + CACHE_SIZE; while (ent < end) { @@ -263,4 +338,5 @@ rb_get_method_body(klassp, idp, noexp) struct cache_entry *ent; + CACHE_DAMAGE(id); if ((body = search_method(klass, id, &origin)) == 0 || !body->nd_body) { /* store empty info in cache */ @@ -1040,4 +1116,5 @@ ruby_init() Init_stack(0); Init_heap(); + Init_cache(); PUSH_SCOPE(); ruby_scope->local_vars = 0; -- --- 僕の前にBugはない。 --- 僕の後ろにBugはできる。 中田 伸悦