可変個引数処理のパフォーマンス比較

Lua

Lua で可変個引数を処理する方法には、主に三通りあります。
すなわち、再帰によって行う方法、テーブルを作る方法、標準関数selectを使う方法です：

-- 再帰版
do
  local function add_impl_( x, y, ... )
    if y == nil then return x end
    return add_impl_( x + y, ... )
  end
  
  function add( ... )
    return add_impl_( ... )
  end
end

-- テーブル版
do
  local ipairs = ipairs
  
  function add( x, ... )
    for _, y in ipairs{...} do
      x = x + y
    end
    return x
  end
end

-- select版
do
  local select = select
  
  function add( x, ... )
    local n = select( "#", ... )
    for i = 1, n do
      local y = select( i, ... )
      x = x + y
    end
    return x
  end
end

さて、これらの中で、最も高速に処理が出来るのは何か、
というのが気になったので、実測して確かめることにしました。


以下のコードで測定します：

・util.lua

-- ベンチマーク用ユーティリティ

-- 関数 f(...) を n 回実行するのにかかった時間を測定する
do
  local clock = os.clock
  
  function time( n, f, ... )
    local t = clock()
    
    for i = 1, n do
      local x = f(...)
    end
    
    return clock() - t
  end
end

-- 関数 f(...) を一秒間に何回実行出来るか測定する
do
  local time = time
  local collectgarbage = collectgarbage
  
  function benchmark( f, ... )
    -- 予め GC を呼ぶ
    collectgarbage("collect")
    
    local step = 1000  -- 最低 1000 回は実行される
    
    local n = 0
    local t = 0
    while true do
      t = t + time( step, f, ... )
      n = n + step
      
      if t >= 1 then break end
      
      -- 次の実行ではステップを倍にする
      step = step * 2
    end
    
    return n / t
  end
end

-- 数値を丸める
do
  local floor = math.floor
  function round(x)
    return floor( x + 0.5 )
  end
end

-- ベンチマークして表示する
do
  local print = print
  local round = round
  
  function show_benchmark( name, f, ... )
    print( name, round( benchmark( f, ... ) ) )
  end
end

・vararg.lua

-- 可変個引数を、テーブルを作った上で ipairs でイテレーションするか
-- それとも select でイテレーションするか、再帰を使うか
-- どれが一番高速？

-- 全ての引数を加算する関数で調べる

-- pack version
do
  local ipairs = ipairs
  
  function pack_ver( x, ... )
    for _, y in ipairs{...} do
      x = x + y
    end
    return x
  end
end

-- select version
do
  local select = select
  
  function select_ver( x, ... )
    local n = select( "#", ... )
    for i = 1, n do
      local y = select( i, ... )
      x = x + y
    end
    return x
  end
end

-- recursion version
do
  local function impl_( x, y, ... )
    if y == nil then return x end
    return impl_( x + y, ... )
  end
  
  function recursion_ver( ... )
    return impl_( ... )
  end
end

-- 引数リストを作る
function createList(n)
  local t = {}
  for i = 1, n do
    t[i] = i
  end
  return t
end

-- 計測開始
-- ライブラリを読み込む
require "util"

-- 計測用の関数
function doit(n)
  local t = createList(n+1)
  
  show_benchmark( "pack\t"..n, pack_ver, unpack(t) )
  
  show_benchmark( "select\t"..n, select_ver, unpack(t) )
  
  show_benchmark( "rec\t"..n, recursion_ver, unpack(t) )
  
end

-- 速度を安定させる
show_benchmark( "id", function(...) return ... end )

-- まず全く開かない場合
doit(0)

-- 1 から 1024 まで測定する
local n = 1
while n <= 1024 do
  doit(n)
  n = n * 2
end

結果：

id	10700849
pack	0	703576
select	0	4599102
rec	0	4441974
pack	1	523810
select	1	2730000
rec	1	2789510
pack	2	467093
select	2	1817940
rec	2	1541416
pack	4	408800
select	4	1139121
rec	4	1213397
pack	8	314462
select	8	661280
rec	8	641782
pack	16	223488
select	16	297439
rec	16	236330
pack	32	139497
select	32	125123
rec	32	94494
pack	64	80482
select	64	42000
rec	64	42000
pack	128	44304
select	128	12305
rec	128	14327
pack	256	23065
select	256	3369
rec	256	3763
pack	512	11574
select	512	889
rec	512	1000
pack	1024	5742
select	1024	211
rec	1024	266


結論：

  • 再帰と select のパフォーマンスは殆ど同じ
  • select は引数の数が少ない時に有利
  • テーブルを作った場合は引数が多くても安定する
  • だいたい数十個を境にパフォーマンスが入れ替わる

というわけで、普通の関数では select か再帰を使っていくほうがよさそうです。