From: SASADA Koichi <ko1@...>
Date: 2010-09-27T23:27:11+09:00
Subject: [ruby-dev:42304] Re: [Ruby 1.9-Bug#3696][Closed] Fwd: [ruby-list:47272] case when   	整数と実数の比較 (ruby 1.9)

　ささだです。

　この件があって、opt_case_dispatch を見ていたんですが、ヒットしないとき
の挙動について、少し考えてみました。

　ヒットしないとき（型がこの最適化できる型じゃなかった、もしくは値が違っ
た）ときは、st_foreach で === を行い、case/when を実現しています。です
が、いくつかの理由から（たぶん）、=== を順に行うバイトコードも（無駄に）
生成されています。つまり、opt_case_dispatch から、単に抜けるだけでも、き
ちんと === をするわけです。

　さて、どっちが速いのか、と調べたところ、st_foreach よりも、バイトコー
ド実行に任せたほうが若干速いことがわかりました。st_foreach でたどるリス
トが長ければ長いほど、その傾向が顕著であることがわかりました。

　理由は、foreach でたどるよりも VM でたどる方が速いとか、そういうのだと
思います。

　というわけで、その報告と、修正をお送りします。


　何度も同じハッシュに対して Hash#each するようなコードは eval で展開し
ちゃった方が速いかもね、という知見でもありますが、さてそういうケースはど
れだけあるんだろうか？

mswin32
http://www.atdot.net/fp_store/f.0tse9l/file.graph.png

linux32 (on VirtualBox)
http://www.atdot.net/fp_store/f.7tse9l/file.graph.png

グラフは、
横軸が「失敗する when の数（st_foreach でたどる回数）」
縦軸が「実行時間（秒）」
です。

ちなみに、もちろんヒットするときは when の数は関係なく速いです。


テストコード：
require 'benchmark'

n = 10_000_000
Benchmark.bm{|x|
  [true, false, Object.new].each{|obj|
    20.times{|i|
      ary = (0..i).to_a
      obj = i if obj == true
      x.report("#{obj}\t#{i+1}"){
        eval %Q{
          n.times{
            case obj
            when #{ary.join(", ")}
              # ignore
            else
              # ignore
            end
          }
        }
      }
    }
  }
}

パッチ：

Index: insns.def
===================================================================
--- insns.def	(revision 29350)
+++ insns.def	(working copy)
@@ -1281,20 +1281,8 @@
 	    }
 	    break;
 	}
-      default: { /* fall through (else) */
-	struct opt_case_dispatch_i_arg arg;
-
-	arg.obj = key;
-	arg.label = -1;
-	st_foreach(RHASH_TBL(hash), opt_case_dispatch_i, (st_data_t)&arg);
-
-	if (arg.label != -1) {
-	    JUMP(arg.label);
-	}
-	else {
-	    JUMP(else_offset);
-	}
-      }
+      default:
+	break;
     }
 }

Index: vm_insnhelper.c
===================================================================
--- vm_insnhelper.c	(revision 29350)
+++ vm_insnhelper.c	(working copy)
@@ -1699,22 +1699,3 @@
     return Qundef;
 }

-struct opt_case_dispatch_i_arg {
-    VALUE obj;
-    int label;
-};
-
-static int
-opt_case_dispatch_i(st_data_t key, st_data_t data, st_data_t p)
-{
-    struct opt_case_dispatch_i_arg *arg = (void *)p;
-
-    if (RTEST(rb_funcall((VALUE)key, idEqq, 1, arg->obj))) {
-	arg->label = FIX2INT((VALUE)data);
-	return ST_STOP;
-    }
-    else {
-	return ST_CONTINUE;
-    }
-}
-

-- 
// SASADA Koichi at atdot dot net