Elixirで速度を追い求めるときのプログラミングスタイル

9114 ワード
Elixir Elixir テキストリンク

この記事はElixir Advent Calendar 2020の18日目の記事です。

昨日は @tamanugi さんの「AtCoder用のmixタスクを作ってみた」でした。

さて遅れましたが，今回は「Elixirで速度を追い求めるときのプログラミングスタイル」をお送りします。

追記: 「Elixirで速度を追い求めるときのプログラミングスタイル PartⅡ，Pelemayの近況もあるよ」， @kentaro さんによる 「Enum.mapと再帰スタイルの比較、ふたたび（末尾再帰版）」 も参照ください。末尾再帰にすると高速になります。

リスト操作について

  • リストの先頭から要素を取り出すときと，リストの先頭・末尾に要素を追加するのは高速に出来ます。
  • リストから要素を取り出すとき，末尾から取り出すと多大な時間をロスします。

Enum.reverse/1によるリストの反転は，List.delete_at/2で末尾を削除するよりは高速に実行できます。

検証コード

bench/list_add_bench.exs
defmodule ListAddBench do
  use Benchfella

  @list Enum.to_list(1..1_000_000)

  bench "add head" do
    [:a | @list]
  end

  bench "add tail" do
    @list ++ [:a]
  end
end
bench/list_pop_bench.exs
defmodule ListPopBench do
  use Benchfella

  @list Enum.to_list(1..1_000_000)

  bench "pop head" do
    fn [_head | tail] -> tail end.(@list)
  end

  bench "pop tail" do
    List.delete_at(@list, -1)
  end
end
bench/list_reverse_bench.exs
defmodule ListReverseBench do
  use Benchfella

  @list Enum.to_list(1..1_000_000)

  bench "reverse" do
    Enum.reverse(@list)
  end
end

結果

## ListAddBench
benchmark iterations   average time 
add tail  1000000000   0.01 µs/op
add head  1000000000   0.01 µs/op
## ListPopBench
benchmark iterations   average time 
pop head   100000000   0.02 µs/op
pop tail          50   35337.48 µs/op
## ListReverseBench
benchmark iterations   average time 
reverse          200   8831.18 µs/op

(iMac Pro調べ)

Enum.mapと再帰スタイルは，ほとんど差がない

lib/high_performance_programming.ex
defmodule HighPerformanceProgramming do
  def r_map([], _func), do: []
  def r_map([head | tail], func) do
    [func.(head) | r_map(tail, func)]
  end
end
bench/enum_bench.exs
defmodule EnumBench do
  use Benchfella

  @list Enum.to_list(1..1_000_000)

  bench "Enum.map" do
    Enum.map(@list, & &1 * 2)
  end

  bench "recursive" do
    HighPerformanceProgramming.r_map(@list, & &1 * 2)
  end
end

結果

## EnumBench
benchmark  iterations   average time 
Enum.map           50   55004.48 µs/op
recursive          50   55315.28 µs/op

ほとんど誤差ですね。

2018年ごろに検証したときには再帰スタイルの方が速かったのですけどね！ 変わるものですね。

まとめ

  • リストへの要素の追加は先頭からでも末尾からでも極めて高速
  • リストの先頭からの要素の取り出しは高速
  • List.delete_at/2を使って無理矢理リストの末尾から要素を取り出すと極めて低速
  • リストの走査には，Enum.map/2を使うのが推奨。以前に比べてパフォーマンス面も改善したようなので，再帰スタイルをあえて使う理由がないです。

明日19日目のElixir Advent Calendar 2020は @a_utsuki さんの「Elixirで竹内関数を計測してみた」です。よろしくお願いします。

本研究成果は、科学技術振興機構研究成果展開事業研究成果最適展開支援プログラム A-STEP トライアウト JPMJTM20H1 の支援を受けた。

コンピュータプログラムの思考論理(8)-charの本当の意味
c++rapidxmlの使用