From: SASADA Koichi <ko1@...>
Date: 2015-04-16T05:19:36+09:00
Subject: [ruby-dev:48942] Boost creating big array from Range#map

小ネタ（没ネタ）です。

単に配列を作るのに比べて、大きな Range の map が遅かったので、ちょっと考
えてみたんですが、空配列から push するのが遅いのかな、と思ったので、size
がわかる場合には、最初に空の配列を作るとき、capa をそのサイズにすると、
ちょっとはマシになるかと思いまして。

やってみると、

bench1
                           user     system      total        real
Array.new(1000000)     0.050000   0.000000   0.050000 (  0.045718)
Array.new(10000000)    0.440000   0.000000   0.440000 (  0.450678)
Array.new(100000000)   4.520000   0.080000   4.600000 (  4.609407)
(1..1000000).map       0.060000   0.000000   0.060000 (  0.061653)
(1..10000000).map      0.590000   0.010000   0.600000 (  0.944142)
(1..100000000).map     6.020000   0.180000   6.200000 (  6.873744)

が、

(1..1000000).map       0.060000   0.010000   0.070000 (  0.058909)
(1..10000000).map      0.880000   0.020000   0.900000 (  0.898898)
(1..100000000).map     5.790000   0.050000   5.840000 (  5.850037)

こうなりました。大きいときに、若干速くなってるかな、という程度ですが...。

　小さい enum について、map をすると、逆に遅くなってしまいました。

bench2
                           user     system      total        real
Array.new(1)           2.530000   0.000000   2.530000 (  2.532221)
(1..1).map (before)    2.140000   0.000000   2.140000 (  2.143456)
(1..1).map (after)     2.930000   0.000000   2.930000 (  2.926502)

　というわけで、無しですね。Range#size を毎回まともに呼び出しているから
だろうなあ。Range#size を、わざわざ最適化するのも何だし。


Index: enum.c
===================================================================
--- enum.c	(revision 50322)
+++ enum.c	(working copy)
@@ -443,10 +443,17 @@
 enum_collect(VALUE obj)
 {
     VALUE ary;
+    VALUE size = enum_size(obj, Qnil, Qnil);

     RETURN_SIZED_ENUMERATOR(obj, 0, 0, enum_size);

-    ary = rb_ary_new();
+    if (FIXNUM_P(size)) {
+	ary = rb_ary_new_capa(FIX2INT(size));
+    }
+    else {
+	ary = rb_ary_new();
+    }
+
     rb_block_call(obj, id_each, 0, 0, collect_i, ary);

     return ary;


# bench1
require 'benchmark'
i = 0
s = 6
e = 8
Benchmark.bm(20){|x|
  (s..e).each{|n|
    x.report("Array.new(#{10 ** n})"){
      Array.new(10 ** n){|x|
        true
      }
    }
  }

  (s..e).each{|n|
    x.report("(1..#{10**n}).map"){
      m = (1..(10**n)).map{
        true
      }
    }
  }
}

# bench2
require 'benchmark'

n = 10_000_000
Benchmark.bm(20){|x|
  x.report("Array.new(1)"){
    n.times{
      Array.new(1){|x|
        true
      }
    }
  }

  x.report("(1..1).map"){
    n.times{
      m = (1..1).map{
        true
      }
    }
  }
}

-- 
// SASADA Koichi at atdot dot net