Elixir Enum.at()がどれだけ遅いか。そしてMap

Elixir Enum.at()がどれだけ遅いか。そしてMap

1. はじめに

日常の業務では、使用している端末のセキュリティの関係で、
仕事で使用するプログラミング言語や開発環境が限定されがちなのですが、

他言語も利用しないと、忘れがちになるので、
週末などは、Leetcodeで複数の言語での書き比べに取り組んでいます。

https://leetcode.com/
https://github.com/NobuyukiInoue/LeetCode

配列が用意されている言語では、
index番号を指定しての配列の参照、書き換えは高速ですが、

Elixirにおいて配列の代替として利用されるListは、
内部構造が線形リストとなっており、Enum.at()でのindex番号を指定しての参照も非常に低速で、

他言語からElixirへの移植の際には、index番号を指定しての取得をどう減らすか、
別の処理にどう置き換えるかが重要になってきます。
Elixir界隈では、Listの代わりにMapを作成して参照する、という手法もよく見聞きします。

実際に、どれほどの速度差があるのかの比較を行ってみました。

Elixirでは、MapのほかにHashDictなるものもありましたが、廃止される予定なので、検証は割愛。

この記事の公開予定は12/17でしたが、、他にもネタが見つかったので公開しよっかな。

2. 実行環境

まずは速度比較の検証環境です。

項目	値
OS	macOS Sonoma 14.1.2
CPU	Apple M1
メモリ	8GB
Elixir	Elixir 1.15.6, Mix 1.15.6

3. List/Mapの事前準備とソースコード

ソースコードは、
https://github.com/NobuyukiInoue/exListMapSpeedtest
に配置してます。

3-1. Listの作成

処理時間の計測に先立って、指定した要素数（今回の実験では10万個）のListを用意します。
各要素の値は乱数で0-9までの値をセットしています。

    :rand.seed(:exs1024, :os.timestamp)

    arr_size = 1_00_000

    # create List nums.
    nums = for _ <- 0..arr_size - 1 do (:rand.uniform 10) - 1 end

    # nums = [4, 5, 4, 2, 0, 4, 0, 3, 0, ....]

3-2. Mapへの変換

また、後述のMapでの参照の速度比較のために、
作成したListの各要素を値、keyを先頭からのindex番号として、
Mapも作成しておきます。

   map_nums = 
      Enum.reduce(nums, {0, %{}}, fn num, {i, res} ->
        {i + 1, Map.put(res, i, num)}
      end) |> elem(1)

   # nums_map = %{0: 4, 1: 5, 2: 4, 3: 2, 4: 0, ...}

4. 実験した方法

List, Mapそれぞれ、for、Enum.reduce(), 自作の再帰関数など、
同一のList、Mapから各要素の値を取得した際の処理時間を計測しました。

後続の処理はCPU等の内部キャッシュによる速度向上の影響を受けやすいため、
4-1〜4-8の処理を３回繰り返し、それぞれ処理時間を出力させています。

4-1. forで各要素を１つずつ取得する（戻り値はすべての要素を含むリスト）

forの中で、各要素を１つずつ取得します。forの中での取得なので、戻り値はすべての要素を含むリストになります。
（３回目の）10万個の取得時間は 0.002[s]でした。

それなりの大きさのListの参照であっても、先頭からの順次読み出しは、後述の Enum.at() を使っての各要素の取得と比べると、高速です。

他言語と比べてませんが、10万程度だと、こんなもんでしょうね。
後述のindex番号での取得では時間がかかるので、この記事では要素数10万個を基準に比較しています。

  @spec get_for(nums :: [integer]) :: [integer]
  def get_for(nums) do
    for num <- nums do
      num
    # "num = " <> Integer.to_string(num) |> IO.puts()
    end
  end

4-2. forでindex番号を１つずつ増やして各要素を参照する（戻り値はすべての要素を含むリスト）

forの中で、Enum.at()を使ってindex番号を指定して参照を繰り返します。

（３回目の）10万個の取得時間は 7.293[s]でした。

かなりの処理時間がかかっている様子が解ります。

なお、他の方法も含め、ブロック内で、別の変数に代入する無駄な処理をしていますが、
IO.puts()で出力するためのもので、不要だったら削除しても構いません。
あえて、意味のない代入処理をしています。

  @spec get_for_with_enum_at(nums :: [integer]) :: [integer]
  def get_for_with_enum_at(nums) do
    for i <- 0..Enum.count(nums) - 1 do
      _ = Enum.at(nums, i)
  #   "nums[" <> Integer.to_string(i) <> "] = " <> Integer.to_string(Enum.at(nums, i)) |> IO.puts()
    end
  end

4-3. Enum.reduce()で各要素を１つずつ取り出す（戻り値は末尾のindex番号）

Enum.reduce() を使って各要素を順番に参照します。参考までにindex番号のカウントも行っています。
（３回目の）10万個の取得時間は 0.0[s]でした。

4-1 の for と比較すると、戻り値は末尾の値のみなので、その分、処理速度が速いですね。
なお、4-1と同様に、Enum.reduce()でリストを返す手もありますが、あまり意味がないので今回はやってません。

  @spec get_Enum_reduce_each(nums :: [integer]) :: integer
  def get_Enum_reduce_each(nums) do
    Enum.reduce(nums, 0, fn num, i ->
      _ = num
  #   "nums[" <> Integer.to_string(i) <> "] = " <> Integer.to_string(num) |> IO.puts()
      i + 1
    end)
  end

4-4. Enum.reduce()でindex番号を１つずつ増やして各要素を参照する（戻り値は末尾の要素）

Enum.reduce()の引数としてindex番号のリストを渡し、Enum.at()を使って参照を繰り返します。
（３回目の）10万個の取得時間は 7.377[s]でした。

4-2. 同様に、かなり処理時間がかかったことが解ります。
4-2. のforでEnum.at()を使って参照する方法とほぼ同じ処理時間です。

  @spec get_Enum_reduce_with_enum_at(nums :: [integer]) :: integer
  def get_Enum_reduce_with_enum_at(nums) do
    Enum.reduce(0..Enum.count(nums) - 1, 0, fn i, _ ->
      num = Enum.at(nums, i)
  #   "nums[" <> Integer.to_string(i) <> "] = " <> Integer.to_string(num) |> IO.puts()
      num
    end)
  end

4-5. 再帰関数で各要素を１つずつ参照する（戻り値は末尾のindex番号）

自作の再帰関数を作成して、先頭から１つずつ取得します。
（３回目の）10万個の取得時間は 0.0[s]でした。

自作の再帰関数での先頭からの順次読み出しも、Enum.reduce()同様に非常に高速です。

  @spec get_recurse_main(nums :: [integer]) :: integer
  def get_recurse_main(nums) do
    get_recurse(0, nums)
  end

  @spec get_recurse(i :: integer, nums :: [integer]) :: integer
  def get_recurse(i, []) do
    i + 1
  end

  def get_recurse(i, [head | tail]) do
    _ = head
    get_recurse(i + 1, tail)
  end

4-6. 再帰関数で各要素を１つずつ参照する（戻り値はすべての要素を含むリスト）

自作の再帰関数を作成して、先頭から１つずつ取得します。
（３回目の）10万個の取得時間は 8.593[s]でした。

Enum.at()を利用するよりも、さらに遅くなっています。

  @spec get_list_at_all(nums :: [integer]) :: [integer]
  def get_list_at_all(nums) do
    for i <- 0..Enum.count(nums) - 1 do
      num = get_list_at(nums, i)
  #   "nums[" <> Integer.to_string(i) <> "] = " <> Integer.to_string(num) |> IO.puts()
      num
    end
  end

  @spec get_list_at(nums :: [integer], target_index :: integer) :: integer
  def get_list_at([head | _], target_index) when target_index == 0 do
    head
  end

  def get_list_at([_ | tail], target_index) do
    get_list_at(tail, target_index, 1)
  end

  @spec get_list_at(nums :: [integer], target_index :: integer, i :: integer) :: integer
  def get_list_at([head | _], target_index, i) when i == target_index do
    head
  end

  def get_list_at([_ | tail], target_index, i) do
    get_list_at(tail, target_index, i + 1)
  end

4-7. Mapでindex番号をkeyとして取得(forを利用)（戻り値はすべての要素を含むリスト）

ListからMapへの変換処理で、0.025[s]かかりましたが、
Mapでの（３回目の）10万個の取得時間は 0.0004[s]でした。

Mapへの変換処理が必要であることも考慮する必要はありますが、それでも、
Enum.at()を参照した処理の7-8秒台と比べると、桁違いに速いです。

  @spec get_map_for(nums_map :: %{}) :: [integer]
  def get_map_for(nums_map) do
    for i <- 0..map_size(nums_map)-1 do
      num = Map.get(nums_map, i)
  #   "nums[" <> Integer.to_string(i) <> "] = " <> Integer.to_string(num) |> IO.puts()
      num
    end
  end

4-8. Mapでindex番号をkeyとして取得(Enum.reduce()を利用)（戻り値は末尾の要素）

ListからMapへの変換処理は3-6と共通です。（0.025[s]）
Mapでの（３回目の）10万個の取得時間は 0.0002[s]でした。

4-7. の処理では、結果はListとして返されますが、今回の処理では末尾の値しか返していませんので、 4-7. の処理よりも高速になっています。

  @spec get_map_reduce(nums_map :: %{}) :: integer
  def get_map_reduce(nums_map) do
    Enum.reduce(0..map_size(nums_map)-1, 0, fn i, _ ->
      num = Map.get(nums_map, i)
  #   "nums[" <> Integer.to_string(i) <> "] = " <> Integer.to_string(num) |> IO.puts()
      num
    end)
  end

5. 結果

それぞれの方法での３回の計測結果をまとめると、以下のとおりです。

項目	１回目	2回目	３回目
4-1. forで１つずつ各要素を取得する （戻り値はすべての要素を含むリスト）	0.002 [s]	0.001 [s]	0.002 [s]
4-2. forでindex番号を１つずつ増やして各要素を参照する （戻り値はすべての要素を含むリスト）	7.388 [s]	7.38 [s]	7.293 [s]
4-3. Enum.reduce()で各要素を１つずつ取り出す （戻り値は末尾のindex番号）	0.0 [s]	0.0 [s]	0.0 [s]
4-4. Enum.reduce()でindex番号を１つずつ増やして各要素を参照する （戻り値は末尾の要素）	7.332 [s]	7.305 [s]	7.377 [s]
4-5. 再帰関数で各要素を１つずつ参照する （戻り値は末尾のindex番号）	0.0 [s]	0.0 [s]	0.0 [s]
4-6. 再帰関数で各要素を１つずつ参照する （戻り値はすべての要素を含むリスト）	8.467 [s]	8.64 [s]	8.593 [s]
ListからMapを生成する	0.025 [s]	-	-
4-7. Mapでindex番号をkeyとして取得(forを利用) （戻り値はすべての要素を含むリスト）	0.006 [s]	0.004 [s]	0.004 [s]
4-8. Mapでindex番号をkeyとして取得(Enum.reduce()を利用) （戻り値は末尾の要素）	0.002 [s]	0.002 [s]	0.002 [s]

実行結果例

##-------------------------------------------##
## 1 th results.
##-------------------------------------------##
1. for each               time : 0.002 [s]
2. for with Enum.at()     time : 7.388 [s]
3. reduce each            time : 0.0 [s]
4. reduce with Enum.at()  time : 7.332 [s]
5. recurse (head)         time : 0.0 [s]
6. get_list_at()          time : 8.467 [s]

List to Map transration time : 0.025 [s]
7. Map by for             time : 0.006 [s]
8. Map by Enum.reduce()   time : 0.002 [s]

##-------------------------------------------##
## 2 th results.
##-------------------------------------------##
1. for each               time : 0.001 [s]
2. for with Enum.at()     time : 7.38 [s]
3. reduce each            time : 0.0 [s]
4. reduce with Enum.at()  time : 7.305 [s]
5. recurse (head)         time : 0.0 [s]
6. get_list_at()          time : 8.64 [s]

List to Map transration time : 0.025 [s]
7. Map by for             time : 0.004 [s]
8. Map by Enum.reduce()   time : 0.002 [s]

##-------------------------------------------##
## 3 th results.
##-------------------------------------------##
1. for each               time : 0.002 [s]
2. for with Enum.at()     time : 7.293 [s]
3. reduce each            time : 0.0 [s]
4. reduce with Enum.at()  time : 7.377 [s]
5. recurse (head)         time : 0.0 [s]
6. get_list_at()          time : 8.593 [s]

List to Map transration time : 0.025 [s]
7. Map by for             time : 0.004 [s]
8. Map by Enum.reduce()   time : 0.002 [s]

2023/12/6 追記）
Bencheeを利用してのベンチマーク結果も追加しました。

• 要素数が1000の場合

$ ./main 1000 true
nable_Bench = true
enable_puts = false
arr_size = 1000
nums = [5, 5, 0, 4, 2, 8, 0, ...
List to Map finished.
List to Map transration time : 0.0 [s]
Wait ... create output string from Map.
nums_map = %{0: 5, 1: 5, 2: 0, 3: 4, 4: 2, 5: 8, 6: 0, ...
...
...
Could not check if protocols are consolidated. Running as escript? Defaulting to they are consolidated.
Operating System: macOS
CPU Information: Apple M1
Number of Available Cores: 8
Available memory: 8 GB
Elixir 1.15.6
Erlang 26.0.2

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 10 s
memory time: 2 s
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 1.87 min

Benchmarking for ...
Benchmarking for_with_enum_at ...
Benchmarking get_list_at ...
Benchmarking get_map_for ...
Benchmarking get_map_reduce ...
Benchmarking recurse ...
Benchmarking reduce_each ...
Benchmarking reduce_with_enum_at ...

Name                          ips        average  deviation         median         99th %
recurse                  690.30 K        1.45 μs    ±14.41%        1.42 μs        1.58 μs
reduce_each              248.42 K        4.03 μs   ±117.24%        4.13 μs        4.46 μs
for                       98.74 K       10.13 μs   ±176.76%        9.88 μs       15.67 μs
get_map_reduce            71.88 K       13.91 μs    ±48.74%       13.83 μs       14.33 μs
get_map_for               59.58 K       16.78 μs    ±25.06%       16.58 μs       18.96 μs
reduce_with_enum_at        1.40 K      716.71 μs     ±0.97%      716.52 μs      748.85 μs
for_with_enum_at           1.38 K      723.18 μs     ±3.29%      719.75 μs      777.64 μs
get_list_at                1.26 K      793.45 μs     ±1.48%      791.50 μs      844.25 μs

Comparison:
recurse                  690.30 K
reduce_each              248.42 K - 2.78x slower +2.58 μs
for                       98.74 K - 6.99x slower +8.68 μs
get_map_reduce            71.88 K - 9.60x slower +12.46 μs
get_map_for               59.58 K - 11.59x slower +15.34 μs
reduce_with_enum_at        1.40 K - 494.74x slower +715.26 μs
for_with_enum_at           1.38 K - 499.21x slower +721.73 μs
get_list_at                1.26 K - 547.72x slower +792.00 μs

Memory usage statistics:

Name                   Memory usage
recurse                        0 KB
reduce_each                    0 KB - 1.00x memory usage +0 KB
for                        15.63 KB - ∞ x memory usage +15.63 KB
get_map_reduce             0.102 KB - ∞ x memory usage +0.102 KB
get_map_for                15.73 KB - ∞ x memory usage +15.73 KB
reduce_with_enum_at        15.73 KB - ∞ x memory usage +15.73 KB
for_with_enum_at           31.35 KB - ∞ x memory usage +31.35 KB
get_list_at                15.73 KB - ∞ x memory usage +15.73 KB

**All measurements for memory usage were the same**

• 要素数が100000の場合

$ ./main 100000 true
nable_Bench = true
enable_puts = false
arr_size = 100000
...
...
（中略）
...
Could not check if protocols are consolidated. Running as escript? Defaulting to they are consolidated.
Operating System: macOS
CPU Information: Apple M1
Number of Available Cores: 8
Available memory: 8 GB
Elixir 1.15.6
Erlang 26.0.2

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 10 s
memory time: 2 s
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 1.87 min

Benchmarking for ...
Benchmarking for_with_enum_at ...
Benchmarking get_list_at ...
Benchmarking get_map_for ...
Benchmarking get_map_reduce ...
Benchmarking recurse ...
Benchmarking reduce_each ...
Benchmarking reduce_with_enum_at ...

Name                          ips        average  deviation         median         99th %
recurse                   6831.67      0.00015 s    ±20.58%      0.00015 s      0.00015 s
reduce_each               2297.86      0.00044 s    ±12.02%      0.00045 s      0.00046 s
for                        914.53      0.00109 s     ±5.72%      0.00113 s      0.00120 s
get_map_reduce             418.92      0.00239 s    ±25.79%      0.00228 s      0.00462 s
get_map_for                364.69      0.00274 s     ±9.70%      0.00272 s      0.00342 s
reduce_with_enum_at         0.134         7.44 s     ±0.06%         7.44 s         7.44 s
for_with_enum_at            0.133         7.53 s     ±0.53%         7.53 s         7.56 s
get_list_at                 0.116         8.62 s     ±0.12%         8.62 s         8.63 s

Comparison:
recurse                   6831.67
reduce_each               2297.86 - 2.97x slower +0.00029 s
for                        914.53 - 7.47x slower +0.00095 s
get_map_reduce             418.92 - 16.31x slower +0.00224 s
get_map_for                364.69 - 18.73x slower +0.00260 s
reduce_with_enum_at         0.134 - 50824.41x slower +7.44 s
for_with_enum_at            0.133 - 51442.60x slower +7.53 s
get_list_at                 0.116 - 58892.05x slower +8.62 s

Memory usage statistics:

Name                   Memory usage
recurse                        0 MB
reduce_each                    0 MB - 1.00x memory usage +0 MB
for                         1.53 MB - ∞ x memory usage +1.53 MB
get_map_reduce           0.00010 MB - ∞ x memory usage +0.00010 MB
get_map_for                 1.53 MB - ∞ x memory usage +1.53 MB
reduce_with_enum_at         1.53 MB - ∞ x memory usage +1.53 MB
for_with_enum_at            3.05 MB - ∞ x memory usage +3.05 MB
get_list_at                 1.53 MB - ∞ x memory usage +1.53 MB

**All measurements for memory usage were the same**

4. まとめ

数個程度の参照であれば、Enum.at()を利用しても良いかと思いますが、
大量の要素を取得する必要がある場合、Enum.at()を多用すると、かなりの処理時間がかかります。

どうしてもindex番号を指定してListから各要素を大量に取得する必要がある場合は、Mapの利用を検討しましょう。