From: wanabe <s.wanabe@...>
Date: 2009-02-05T01:43:08+09:00
Subject: [ruby-dev:37908] Re: 配列の重複検出用Hashの使いまわし

ワナベです。

2009/02/04 14:45 wanabe <s.wanabe@gmail.com>:
> 2009/02/04 13:34 Tanaka Akira <akr@fsij.org>:
>> In article <8964790c0902032007n708f1587je29b391281bf5932@mail.gmail.com>,
>>  wanabe <s.wanabe@gmail.com> writes:
>>
>>> ruby-1.9では配列内の重複要素の検出のために
>>> 内部でHashオブジェクトが生成されますが、
>>> これをスレッドローカルに保存して使いまわすことで
>>> オブジェクト生成とGCの回数を減らすパッチを書きました。
>>
>> Hash の操作をすると hash や eql? メソッドを呼びますが、その
>> 中でまた重複要素の検出が必要になることはないのでしょうか。
>
> ご指摘ありがとうございます。
> 確かにそういったケースでは問題がありました。失礼しました。
>
> $ ./ruby -e 'class Foo;def hash;[]|[];return super;end;end;a=[Foo.new,
> Foo.new];p a,a|[]'
> [#<Foo:0xbfda98>, #<Foo:0xbfda80>]
> []

使用済みHashオブジェクトを配列に保存して
そこから使いまわすように書き直しました。

$ ./ruby -e 'class Foo;def hash;[]|[];return super;end;end;a=[Foo.new,
Foo.new];p a,a|[]'
[#<Foo:0xbff0b8>, #<Foo:0xbff0a0>]
[#<Foo:0xbff0b8>, #<Foo:0xbff0a0>]

$ ./ruby -Ilib ../bm_array_overlap.rb
      user     system      total        real
&  3.547000   0.032000   3.579000 (  3.671875)
|  5.422000   0.109000   5.531000 (  6.765625)
-  3.468000   0.047000   3.515000 (  4.312500)
 --- with thread ---
& 18.157000  23.281000  41.438000 ( 52.609375)
| 20.546000  22.984000  43.530000 ( 55.109375)
- 21.016000  23.969000  44.985000 ( 57.359375)
 --- GC.disable ---
&  3.765000   0.047000   3.812000 (  4.093750)
|  5.641000   0.078000   5.719000 (  5.828125)
-  3.531000   0.078000   3.609000 (  3.687500)


Index: array.c
===================================================================
--- array.c     (revision 22029)
+++ array.c     (working copy)
@@ -2866,9 +2866,24 @@
 static VALUE
 ary_make_hash(VALUE ary1, VALUE ary2)
 {
-    VALUE hash = rb_hash_new();
+    VALUE hash;
     long i;

+    hash = rb_thread_local_aref(rb_thread_current(),
+                               rb_intern("ary_overlap_check_hash_set"));
+    if (hash == Qnil) {
+       rb_thread_local_aset(rb_thread_current(),
+                            rb_intern("ary_overlap_check_hash_set"),
+                            rb_ary_new());
+    } else {
+       hash = rb_ary_pop(hash);
+       if (hash != Qnil) {
+           rb_funcall(hash, rb_intern("clear"), 0);
+       }
+    }
+    if (hash == Qnil) {
+       hash = rb_hash_new();
+    }
     for (i=0; i<RARRAY_LEN(ary1); i++) {
        rb_hash_aset(hash, RARRAY_PTR(ary1)[i], Qtrue);
     }
@@ -2880,6 +2895,14 @@
     return hash;
 }

+static inline void
+ary_recycle_hash(VALUE hash)
+{
+    VALUE list = rb_thread_local_aref(rb_thread_current(),
+                                     rb_intern("ary_overlap_check_hash_set"));
+    rb_ary_push(list, hash);
+}
+
 /*
  *  call-seq:
  *     array - other_array    -> an_array
@@ -2906,6 +2929,7 @@
        if (st_lookup(RHASH_TBL(hash), RARRAY_PTR(ary1)[i], 0)) continue;
        rb_ary_push(ary3, rb_ary_elt(ary1, i));
     }
+    ary_recycle_hash(hash);
     return ary3;
 }

@@ -2940,6 +2964,7 @@
            rb_ary_push(ary3, v);
        }
     }
+    ary_recycle_hash(hash);

     return ary3;
 }
@@ -2978,6 +3003,7 @@
            rb_ary_push(ary3, v);
        }
     }
+    ary_recycle_hash(hash);
     return ary3;
 }

@@ -3013,6 +3039,7 @@
        }
     }
     ARY_SET_LEN(ary, j);
+    ary_recycle_hash(hash);

     return ary;
 }


-- 
ワナベ