[ruby-dev:15709] Re: method cache

なかだです。

At Thu, 17 Jan 2002 22:46:54 +0900,
Takaaki Tateishi <[e-mail]> 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はできる。
    中田 伸悦