Feature #1211: nested loop construct

• Status: Rejected
• Assignee: matz (Yukihiro Matsumoto)
• Target version: 2.0.0

[matz (Yukihiro Matsumoto)]

=begin
まつもと ゆきひろです

最近、AO Benchを見ています。http://lucille.atso-net.jp/aobench/
実行時間の1/3はGCが消費していて涙目。

それはそれとして、AO Benchの中には

 nphi.times do |j|
   ntheta.times do |i|

のような多重ループがあります。これを

nloop(nphi, ntheta) do |j,i|

というように書けたら、よりわかりやすく、かつ、やや高速なので
はないかと考えました。実際に実装したところ、AO Benchでは5%程
度実行時間が短縮されるようです。

検討事項は

• そもそも必要なのか。YARVではややブロック呼び出しが重い傾
  向があるので効果があったが、よりブロック呼び出しが軽量に
  なれば不要ではないか

• 名前。今回はnested loopということでnloopという名前で実装
  したが、もっと適切な名前があるかもしれない。妙な短縮形よ
  りも長くても記述的な名前を好む人も多いかも。Ruby(というか
  私)は前者を好む傾向はあるけど

• 他の案としてはloopが引数を取るようにして、nloop相当にす
  るというものがある。しかし、1.9のloopメソッドが持つ
  StopIteration例外でループ終了というセマンティックスと多
  重ループがうまくつながらなかったので、今回はやめておいた

などが考えられます。どう思いますか？

                             まつもと ゆきひろ /:|)

=end

[ko1 (Koichi Sasada)]

=begin
　ささだです．

Yukihiro Matsumoto wrote::

最近、AO Benchを見ています。http://lucille.atso-net.jp/aobench/
実行時間の1/3はGCが消費していて涙目。

　そこで，Flonum 最適化を...．

　あと，インスタンス変数のキャッシュを用いた最適化してねーじゃん，と最近
指摘されたので，近日中にやろうと思います．

それはそれとして、AO Benchの中には

nphi.times do |j|
  ntheta.times do |i|

のような多重ループがあります。これを

nloop(nphi, ntheta) do |j,i|

というように書けたら、よりわかりやすく、かつ、やや高速なので
はないかと考えました。実際に実装したところ、AO Benchでは5%程
度実行時間が短縮されるようです。

　こういうパターンが多くあるのなら，いいんでないでしょうか．でも，速度の
ために，ってのはあんまり Ruby 的じゃないような気がします（とか俺が言う
なって感じですか）．

• そもそも必要なのか。YARVではややブロック呼び出しが重い傾
  向があるので効果があったが、よりブロック呼び出しが軽量に
  なれば不要ではないか

　もうちょっと軽くなるようにしたいと思うんですがねぇ．あと，こういうのは
C で書くよりも Ruby で書いた方が速いかも．

あと，[ruby-dev:38058] に返事下さい．

--
// SASADA Koichi at atdot dot net

=end

[matz (Yukihiro Matsumoto)]

=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:38081] Re: [Feature:trunk] nested loop construct"
on Thu, 26 Feb 2009 03:43:31 +0900, SASADA Koichi [e-mail] writes:

|　そこで，Flonum 最適化を...．

完成度が高ければ反対はしません。でも自分でやるのは、私の手に
は負えません。どうせ使ってるのはlong=64bitでないマシンだし。

|　あと，インスタンス変数のキャッシュを用いた最適化してねーじゃん，と最近
|指摘されたので，近日中にやろうと思います．

期待してます。

|> nloop(nphi, ntheta) do |j,i|
|>
|> というように書けたら、よりわかりやすく、かつ、やや高速なので
|> はないかと考えました。実際に実装したところ、AO Benchでは5%程
|> 度実行時間が短縮されるようです。
|
|　こういうパターンが多くあるのなら，いいんでないでしょうか．

AO Benchのような画像系だと結構ありそうな気がします。普段その
系のプログラミングに縁がないんで自信はないですが。

|でも，速度の
|ために，ってのはあんまり Ruby 的じゃないような気がします（とか俺が言う
|なって感じですか）．

速度だけのためならそうなんですが、一応わかりやすそうな気がす
るというのもあるんで。

|> * そもそも必要なのか。YARVではややブロック呼び出しが重い傾
|> 向があるので効果があったが、よりブロック呼び出しが軽量に
|> なれば不要ではないか
|
|　もうちょっと軽くなるようにしたいと思うんですがねぇ．あと，こういうのは
|C で書くよりも Ruby で書いた方が速いかも．

そうか。ちょっとやってみよう。

|# あと，[ruby-dev:38058] に返事下さい．

しました。

                             まつもと ゆきひろ /:|)

=end

[matz (Yukihiro Matsumoto)]

=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:38083] Re: [Feature:trunk] nested loop construct"
on Thu, 26 Feb 2009 04:00:11 +0900, Yukihiro Matsumoto [e-mail] writes:

||　もうちょっと軽くなるようにしたいと思うんですがねぇ．あと，こういうのは
||C で書くよりも Ruby で書いた方が速いかも．
|
|そうか。ちょっとやってみよう。

やってみました。残念ながら50%くらい遅くなってオリジナルより
も低速でした。

オリジナル: 262秒
nloop(C版): 249秒
nloop(Ruby): 375秒

ブロック呼び出しはRubyからの方が速いのですが、それよりもメソッ
ド呼び出しの少なさの方が効くようです。Ruby版nloopの作りが悪い
せいかもしれません

def nloop(*args, &block)
helper = ->(args, buf, offset, block) {
limit = args[offset]
if (offset+1 == args.size)
limit.times do|i|
buf[offset] = i
block.yield *buf
end
else
limit.times do|i|
buf[offset] = i
helper.(args, buf, offset+1, block)
end
end
}
helper.(args, [], 0, block)
end

=end

[ko1 (Koichi Sasada)]

=begin
Yukihiro Matsumoto wrote::

def nloop(*args, &block)
helper = ->(args, buf, offset, block) {
limit = args[offset]
if (offset+1 == args.size)
limit.times do|i|
buf[offset] = i
block.yield *buf
end
else
limit.times do|i|
buf[offset] = i
helper.(args, buf, offset+1, block)
end
end
}
helper.(args, [], 0, block)
end

　うわー，はじめてみました． -> とか .() とか．

def nloop *args
str = ''
h = lambda{|i|
next "yield #{(0...i).map{|e| "v#{e}"}.join(', ')}\n"
if args.length == 0

 str << "v#{i} = 0; while v#{i} < #{args.shift}\n"
 str << h.call(i+1)
 str << "v#{i} = v#{i}.succ;end\n"
 ''

}
h.call(0)
eval(str)
end

require 'benchmark'
max = 10000
Benchmark.bm{|x|
x.report{
max.times{|i|
max.times{|j|
}
}
}
x.report{
nloop(max, max){|i, j|
}
}
}

ruby 1.9.1p0 (2009-02-02 revision 21960) [i386-mswin32_90]
t.rb:12: warning: useless use of a variable in void context
user system total real
15.039000 0.000000 15.039000 ( 13.957000)
12.105000 0.031000 12.136000 ( 11.492000)

ruby 1.8.7 (2008-12-11 revision 20371) [i386-mswin32_90]
t.rb:12: warning: useless use of a variable in void context
user system total real
10.671000 0.016000 10.687000 ( 10.642000)
t.rb:13:in nloop': (eval):3:in nloop': no block given (LocalJumpError)
from t.rb:26:in eval' from t.rb:13:in nloop'
from t.rb:26
from c:/tmp/ruby_1_8/lib/ruby/1.8/benchmark.rb:293:in measure' from c:/tmp/ruby_1_8/lib/ruby/1.8/benchmark.rb:380:in report'
from t.rb:25
from c:/tmp/ruby_1_8/lib/ruby/1.8/benchmark.rb:177:in benchmark' from c:/tmp/ruby_1_8/lib/ruby/1.8/benchmark.rb:207:in bm'
from t.rb:18

1. あれー，1.8.7 のほうが times{times{}} が速い　なんでー？
2. eval() の中から yield 出来ないんだっけ？

Debian etch/amd64

ruby 1.9.2dev (2009-02-26 trunk 22636) [x86_64-linux]
user system total real
7.840000 0.000000 7.840000 ( 7.836987)
7.900000 0.000000 7.900000 ( 7.900081)

ruby 1.8.5 (2006-08-25) [x86_64-linux]
user system total real
30.340000 12.900000 43.240000 ( 43.247637)
../trunk/test.rb:8:in <<': can't convert nil into String (TypeError) from ../trunk/test.rb:8:in nloop'
from ../trunk/test.rb:8:in call' from ../trunk/test.rb:8:in nloop'
from ../trunk/test.rb:12:in call' from ../trunk/test.rb:12:in nloop'
from ../trunk/test.rb:26
from /usr/lib/ruby/1.8/benchmark.rb:293:in measure' from /usr/lib/ruby/1.8/benchmark.rb:377:in report'
from ../trunk/test.rb:25
from /usr/lib/ruby/1.8/benchmark.rb:177:in benchmark' from /usr/lib/ruby/1.8/benchmark.rb:207:in bm'
from ../trunk/test.rb:18

3. 1.9 でも times{times{}} のほうが速い−．なんでー？
4. 1.8.7 とバックトレースが違う−．

--
// SASADA Koichi at atdot dot net

=end

[matz (Yukihiro Matsumoto)]

=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:38085] Re: [Feature:trunk] nested loop construct"
on Thu, 26 Feb 2009 05:16:41 +0900, SASADA Koichi [e-mail] writes:

|ruby 1.9.1p0 (2009-02-02 revision 21960) [i386-mswin32_90]
|t.rb:12: warning: useless use of a variable in void context
| user system total real
| 15.039000 0.000000 15.039000 ( 13.957000)
| 12.105000 0.031000 12.136000 ( 11.492000)

手元で実行したらこんな感じでした。

ruby 1.9.2dev (2009-02-25 trunk 22621) [i686-linux]
user system total real
8.920000 0.020000 8.940000 ( 9.038252) # while
9.440000 0.000000 9.440000 ( 9.791861) # C版
10.270000 0.010000 10.280000 ( 10.388291) # ささだ版
43.400000 0.080000 43.480000 ( 43.973651) # まつもと版

関数的プログラミング遅すぎ。さらに涙目。

|ruby 1.8.7 (2008-12-11 revision 20371) [i386-mswin32_90]
|t.rb:12: warning: useless use of a variable in void context
| user system total real
| 10.671000 0.016000 10.687000 ( 10.642000)
|t.rb:13:in nloop': (eval):3:in nloop': no block given (LocalJumpError)
| from t.rb:26:in eval' | from t.rb:13:in nloop'
| from t.rb:26
| from c:/tmp/ruby_1_8/lib/ruby/1.8/benchmark.rb:293:in measure' | from c:/tmp/ruby_1_8/lib/ruby/1.8/benchmark.rb:380:in report'
| from t.rb:25
| from c:/tmp/ruby_1_8/lib/ruby/1.8/benchmark.rb:177:in benchmark' | from c:/tmp/ruby_1_8/lib/ruby/1.8/benchmark.rb:207:in bm'
| from t.rb:18
|
|1. あれー，1.8.7 のほうが times{times{}} が速い　なんでー？

なんででしょう？

|2. eval() の中から yield 出来ないんだっけ？

できるはずです。

def doo
eval("yield 42")
end
doo{|x| p x} # => 42

なんでだろう。evalの中でさらにevalするから？

                             まつもと ゆきひろ /:|)

=end

[yugui (Yuki Sonoda)]

=begin
Yuguiです。

On 2/26/09 3:33 AM, Yukihiro Matsumoto wrote:

検討事項は

• 名前。今回はnested loopということでnloopという名前で実装
  したが、もっと適切な名前があるかもしれない。妙な短縮形よ
  りも長くても記述的な名前を好む人も多いかも。Ruby(というか
  私)は前者を好む傾向はあるけど

Array#productがカルテシアン積なので、それに合わせてEnumerator#productで

nphi.product(ntheta).each {} や
(nphi * ntheta).each {}

というのはどうですか?　非常に直感的だと感じます。

--
Yugui [e-mail]
http://yugui.jp
私は私をDumpする

=end

[kou (Kouhei Sutou)]

=begin
須藤です。

In [e-mail]
"[ruby-dev:38095] Re: [Feature:trunk] nested loop construct" on Thu, 26 Feb 2009 17:18:15 +0900,
"Akinori MUSHA" [e-mail] wrote:

At Thu, 26 Feb 2009 14:52:05 +0900,
Yugui wrote:

On 2/26/09 3:33 AM, Yukihiro Matsumoto wrote:

検討事項は

• 名前。今回はnested loopということでnloopという名前で実装
  したが、もっと適切な名前があるかもしれない。妙な短縮形よ
  りも長くても記述的な名前を好む人も多いかも。Ruby(というか
  私)は前者を好む傾向はあるけど

Array#productがカルテシアン積なので、それに合わせてEnumerator#productで

nphi.product(ntheta).each {} や

　インスタンスメソッド形式は、(Array#zip 等でも感じることですが)
3つ以上あるときに、本来対等な関係にも関わらず

v1.product(v2, v3)

とか

v, *vs = *vectors
v.product(*vs)

と「主」を立てないといけないのがどうも気に入らないんですよね。

「対象とするv全体」が「主」っぽい気がするので、
[v1, v2, v3].product
がいいなぁと思いました。

=end

[matz (Yukihiro Matsumoto)]

=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:38094] Re: [Feature:trunk] nested loop construct"
on Thu, 26 Feb 2009 14:52:05 +0900, "Yugui (Yuki Sonoda)" [e-mail] writes:

|Array#productがカルテシアン積なので、それに合わせてEnumerator#productで
|
|nphi.product(ntheta).each {} や
|(nphi * ntheta).each {}
|
|というのはどうですか?　非常に直感的だと感じます。

私がイメージしていたのは単純な多重ループなので、productとか配
列の積とかは、むしろやりたいこととの距離が遠い気がします。ま
た、カルテシアン積を導入するのであれば、Vectorとかのような別
のクラスが望ましいような気がします。Enumeratorに必要な気はあ
んまりしません。

=end

[marcandre (Marc-Andre Lafortune)]

• Category set to core
• Assignee set to matz (Yukihiro Matsumoto)

=begin

=end

[znz (Kazuhiro NISHIYAMA)]

• Status changed from Open to Assigned
• Target version set to 2.0.0
• Start date set to 02/26/2009

=begin

=end

[kosaki (Motohiro KOSAKI)]

• Status changed from Assigned to Rejected

三年前の高速化ネタを蒸し返すのも不毛なのでCloseしますね。たぶん今計り直すと全然違う結果が得られる気がするので新チケットで最初から議論しなおしたほうがマシでしょう