Enum.fetch/2 optimization for maps, negative indexes, out of bound indexes, empty enumerables, and enumerables with only one element.

1_enum_fetch_benchmarking_report.md

Optimize Enum.fetch/2 for maps, negative indexes, out of bound indexes, empty enumerables, and enumerables with only one element.

This function has been highly-optimized, through thorough benchmarking.

There were serious issues when dealing with big lists and maps when an out of bound or a negative index was given. Ex. fetching an out-of-bound index in a 1,000-element map, was reduced to 0.18% of the original item. Or same case with a 1,000-element list time was reduced to a 10,5%.

• Enumerables are no longer reversed when dealing with negative indexes. The much cheaper Enum.count/1 function is used now.

Benchmark are published here: [link to gists]

They have been done with lists and maps of the following configurations: 0, 1, 100, 1K, 100K, 1M elements, and indexes being 0 or positive and negative, retrieving first, middle, last elements and and out-of-bound indexes.

There is one remark to mention about the benchmarks. In list and maps with 1K, 100K, and 1M elements, it shouldn't take into acount the porcentages in the table when dealing with fist (negative index) and last (negative index). The worst case scenario for negative indexes in the previous implementation was when it was given the negative represenation of the first element in the enumerable. Since the list was reversed, it was the last element in the reversed this. But since the new implementation avoids using reverse, the worst case scenario from the previous implementation (the first element with negative index) should be compared to the worst case scenario (the last element with negative index), and the best case scenarios should be compared as well (the last element with negative index of previous implementation, with the first element with negative index of the current implementation).

To faciliate this a table is provided, that shows that in every single case the current implementation outperforms the previous one.

Elixir v1.3.1                                    | Elixir v1.4.0-dev

:"Enum.fetch/2: list, 1000 elements"
benchmark name      iterations   average time    | benchmark name      iterations   average time
last (neg index)       1000000   4.16 µs/op      | first (neg index)      5000000   1.59 µs/op
first (neg index)       500000   15.51 µs/op     | last (neg index)        500000   12.53 µs/op

:"Enum.fetch/2: list_big, 100000 elements"
last (neg index)         10000   349.24 µs/op    | first (neg index)        50000   146.11 µs/op
first (neg index)         5000   1428.20 µs/op   | last (neg index)          5000   1249.18 µs/op

:"Enum.fetch/2: list_huge, 1000000 elements"
last (neg index)           500   9655.58 µs/op   | first (neg index)         5000   1601.54 µs/op
first (neg index)          500   20617.46 µs/op  | last (neg index)           500   12761.61 µs/op

:"Enum.fetch/2: map, 1000 elements"
last (neg index)         50000   123.35 µs/op    | first (neg index)       200000   26.71 µs/op
first (neg index)        50000   123.22 µs/op    | last (neg index)         50000   94.47 µs/op

:"Enum.fetch/2: map_big, 100000 elements"
last (neg index)           500   12032.04 µs/op  | first (neg index)         1000   3228.43 µs/op
first (neg index)          500   12622.49 µs/op  | last (neg index)           500   10026.25 µs/op

:"Enum.fetch/2: map_huge, 1000000 elements"
last (neg index)            50   126813.58 µs/op | first (neg index)          100   32006.77 µs/op
first (neg index)           50   132636.08 µs/op | last (neg index)            50   107091.40 µs/op

Decrease in performace.

There are very few cases where performance was decreased.

:"Enum.fetch/2: list, 1000 elements"

 middle                      +3.91%
 first                       +4.00%

:"Enum.fetch/2: list_big, 100000 elements"

 last                        +1.25%   (1077.57 vs. 1091.07 µs/op)
 middle                      +1.37%   (543.61 vs. 551.08 µs/op)
 first                       +43.48%  (0.05 vs. 0.08 µs/op)

:"Enum.fetch/2: list_empty, 0 elements"

 middle                      +1.55%

:"Enum.fetch/2: list_huge, 1000000 elements"

 last                        +0.08%  (11518.49 vs. 11527.60 µs/op)
 first                       +30.74% (0.05 vs. 0.07 µs/op)

:"Enum.fetch/2: list_single, 1 elements"

 last                        +7.12%  (0.06 vs. 0.06 µs/op)

:"Enum.fetch/2: map, 1000 elements"

 first                       +2.47%
 middle                      +3.15%

When the decrease is > 5%, the absolute difference is maximum 0.03 µs/op.

2_enum_fetch_benchmarking_output.txt

$ exenv local stable; mix bench bench/enum_fetch_bench.exs -d 3
Elixir v1.3.1
Settings:
  duration:      3.0 s
...
Finished in 757.99 seconds

## :"Enum.fetch/2: list, 1000 elements"
benchmark name            iterations   average time 
first                      100000000   0.07 µs/op
last (neg index)             1000000   4.16 µs/op
middle                       1000000   5.29 µs/op
middle (neg index)            500000   9.51 µs/op
last                          500000   11.17 µs/op
out of bound                  500000   14.55 µs/op
out of bound (neg index)      500000   15.08 µs/op
first (neg index)             500000   15.51 µs/op
## :"Enum.fetch/2: list_big, 100000 elements"
benchmark name            iterations   average time 
first                      100000000   0.05 µs/op
last (neg index)               10000   349.24 µs/op
middle                         10000   543.61 µs/op
middle (neg index)             10000   915.03 µs/op
last                            5000   1077.57 µs/op
out of bound (neg index)        5000   1409.95 µs/op
first (neg index)               5000   1428.20 µs/op
out of bound                    5000   1516.51 µs/op
## :"Enum.fetch/2: list_empty, 0 elements"
benchmark name            iterations   average time 
middle                     100000000   0.04 µs/op
first                      100000000   0.04 µs/op
middle (neg index)         100000000   0.04 µs/op
first (neg index)          100000000   0.04 µs/op
last                       100000000   0.10 µs/op
out of bound (neg index)   100000000   0.11 µs/op
last (neg index)           100000000   0.11 µs/op
out of bound               100000000   0.11 µs/op
## :"Enum.fetch/2: list_huge, 1000000 elements"
benchmark name            iterations   average time 
first                      100000000   0.05 µs/op
middle                          1000   5806.65 µs/op
last (neg index)                 500   9655.58 µs/op
last                             500   11518.49 µs/op
middle (neg index)               500   15704.18 µs/op
first (neg index)                500   20617.46 µs/op
out of bound (neg index)         500   20639.87 µs/op
out of bound                     500   21364.84 µs/op
## :"Enum.fetch/2: list_single, 1 elements"
benchmark name            iterations   average time 
middle (neg index)         100000000   0.05 µs/op
middle                     100000000   0.05 µs/op
last                       100000000   0.06 µs/op
first                      100000000   0.06 µs/op
first (neg index)          100000000   0.06 µs/op
out of bound (neg index)   100000000   0.12 µs/op
out of bound               100000000   0.12 µs/op
last (neg index)           100000000   0.12 µs/op
## :"Enum.fetch/2: map, 1000 elements"
benchmark name            iterations   average time 
first                         200000   24.95 µs/op
middle                        100000   63.73 µs/op
last                           50000   101.52 µs/op
middle (neg index)             50000   116.69 µs/op
out of bound                   50000   122.02 µs/op
first (neg index)              50000   123.22 µs/op
last (neg index)               50000   123.35 µs/op
out of bound (neg index)       50000   127.60 µs/op
## :"Enum.fetch/2: map_big, 100000 elements"
benchmark name            iterations   average time 
first                           1000   3107.29 µs/op
middle                          1000   7089.51 µs/op
last                             500   10400.96 µs/op
last (neg index)                 500   12032.04 µs/op
first (neg index)                500   12622.49 µs/op
middle (neg index)               500   12914.07 µs/op
out of bound (neg index)         500   13086.58 µs/op
out of bound                     500   13662.79 µs/op
## :"Enum.fetch/2: map_empty, 0 elements"
benchmark name            iterations   average time 
first                      100000000   0.20 µs/op
middle                     100000000   0.20 µs/op
first (neg index)          100000000   0.20 µs/op
middle (neg index)         100000000   0.21 µs/op
last (neg index)           100000000   0.28 µs/op
last                       100000000   0.28 µs/op
out of bound               100000000   0.30 µs/op
out of bound (neg index)   100000000   0.30 µs/op
## :"Enum.fetch/2: map_huge, 1000000 elements"
benchmark name            iterations   average time 
first                            100   33172.71 µs/op
middle                           100   73311.04 µs/op
last                              50   107712.06 µs/op
last (neg index)                  50   126813.58 µs/op
first (neg index)                 50   132636.08 µs/op
middle (neg index)                50   133777.04 µs/op
out of bound                      50   141114.96 µs/op
out of bound (neg index)          50   142693.90 µs/op
## :"Enum.fetch/2: map_single, 1 elements"
benchmark name            iterations   average time 
first                       10000000   0.31 µs/op
middle (neg index)          10000000   0.32 µs/op
middle                      10000000   0.34 µs/op
first (neg index)           10000000   0.35 µs/op
last (neg index)            10000000   0.40 µs/op
out of bound (neg index)    10000000   0.42 µs/op
last                        10000000   0.46 µs/op
out of bound                10000000   0.53 µs/op


$ exenv local master; mix bench bench/enum_fetch_bench.exs -d 3
Elixir v1.4.0-dev (8c03175)
Settings:
  duration:      3.0 s
...
Finished in 667.2 seconds

## :"Enum.fetch/2: list, 1000 elements"
benchmark name            iterations   average time 
first                      100000000   0.07 µs/op
out of bound                 5000000   1.51 µs/op
out of bound (neg index)     5000000   1.54 µs/op
first (neg index)            5000000   1.59 µs/op
middle                       1000000   5.49 µs/op
middle (neg index)           1000000   7.15 µs/op
last                          500000   10.96 µs/op
last (neg index)              500000   12.53 µs/op
## :"Enum.fetch/2: list_big, 100000 elements"
benchmark name            iterations   average time 
first                      100000000   0.08 µs/op
out of bound (neg index)       50000   143.25 µs/op
first (neg index)              50000   146.11 µs/op
out of bound                   50000   147.09 µs/op
middle                         10000   551.08 µs/op
middle (neg index)             10000   693.68 µs/op
last                            5000   1091.07 µs/op
last (neg index)                5000   1249.18 µs/op
## :"Enum.fetch/2: list_empty, 0 elements"
benchmark name            iterations   average time 
first (neg index)          100000000   0.03 µs/op
out of bound (neg index)   100000000   0.03 µs/op
out of bound               100000000   0.03 µs/op
last                       100000000   0.03 µs/op
last (neg index)           100000000   0.03 µs/op
first                      100000000   0.03 µs/op
middle (neg index)         100000000   0.03 µs/op
middle                     100000000   0.04 µs/op
## :"Enum.fetch/2: list_huge, 1000000 elements"
benchmark name            iterations   average time 
first                      100000000   0.07 µs/op
first (neg index)               5000   1601.54 µs/op
out of bound (neg index)        5000   1621.54 µs/op
out of bound                    5000   1635.92 µs/op
middle                          1000   5696.14 µs/op
middle (neg index)              1000   7226.22 µs/op
last                             500   11527.60 µs/op
last (neg index)                 500   12761.61 µs/op
## :"Enum.fetch/2: list_single, 1 elements"
benchmark name            iterations   average time 
out of bound               100000000   0.04 µs/op
out of bound (neg index)   100000000   0.04 µs/op
middle (neg index)         100000000   0.05 µs/op
last (neg index)           100000000   0.05 µs/op
first (neg index)          100000000   0.05 µs/op
first                      100000000   0.05 µs/op
middle                     100000000   0.05 µs/op
last                       100000000   0.06 µs/op
## :"Enum.fetch/2: map, 1000 elements"
benchmark name            iterations   average time 
out of bound (neg index)   100000000   0.23 µs/op
out of bound               100000000   0.23 µs/op
first                         200000   25.56 µs/op
first (neg index)             200000   26.71 µs/op
middle (neg index)            100000   62.29 µs/op
middle                        100000   65.74 µs/op
last                           50000   94.21 µs/op
last (neg index)               50000   94.47 µs/op
## :"Enum.fetch/2: map_big, 100000 elements"
benchmark name            iterations   average time 
out of bound               100000000   0.24 µs/op
out of bound (neg index)   100000000   0.24 µs/op
first                           1000   3022.68 µs/op
first (neg index)               1000   3228.43 µs/op
middle                          1000   6777.83 µs/op
middle (neg index)              1000   6779.12 µs/op
last                             500   9997.00 µs/op
last (neg index)                 500   10026.25 µs/op
## :"Enum.fetch/2: map_empty, 0 elements"
benchmark name            iterations   average time 
out of bound (neg index)   100000000   0.05 µs/op
middle (neg index)         100000000   0.05 µs/op
last (neg index)           100000000   0.05 µs/op
middle                     100000000   0.05 µs/op
out of bound               100000000   0.05 µs/op
first                      100000000   0.05 µs/op
last                       100000000   0.05 µs/op
first (neg index)          100000000   0.06 µs/op
## :"Enum.fetch/2: map_huge, 1000000 elements"
benchmark name            iterations   average time 
out of bound (neg index)   100000000   0.26 µs/op
out of bound               100000000   0.27 µs/op
first                            100   31679.96 µs/op
first (neg index)                100   32006.77 µs/op
middle                           100   69809.32 µs/op
middle (neg index)               100   71394.64 µs/op
last (neg index)                  50   107091.40 µs/op
last                              50   107561.20 µs/op
## :"Enum.fetch/2: map_single, 1 elements"
benchmark name            iterations   average time 
out of bound               100000000   0.07 µs/op
last (neg index)           100000000   0.07 µs/op
out of bound (neg index)   100000000   0.07 µs/op
middle (neg index)         100000000   0.09 µs/op
first (neg index)          100000000   0.09 µs/op
first                      100000000   0.09 µs/op
middle                     100000000   0.09 µs/op
last                       100000000   0.09 µs/op

$ mix bench.cmp -d percent
bench/snapshots/2016-07-06_11-04-00.snapshot vs
bench/snapshots/2016-07-06_11-15-30.snapshot

## :"Enum.fetch/2: list, 1000 elements"
out of bound (neg index)    -89.82%
first (neg index)           -89.73%
out of bound                -89.65%
middle (neg index)          -24.77%
last                        -1.84%
middle                      +3.91%
first                       +4.00%
last (neg index)            +201.28%

## :"Enum.fetch/2: list_big, 100000 elements"
out of bound                -90.30%
out of bound (neg index)    -89.84%
first (neg index)           -89.77%
middle (neg index)          -24.19%
last                        +1.25%
middle                      +1.37%
first                       +43.48%
last (neg index)            +257.69%

## :"Enum.fetch/2: list_empty, 0 elements"
out of bound                -69.37%
last (neg index)            -69.00%
out of bound (neg index)    -68.77%
last                        -67.09%
first (neg index)           -20.96%
first                       -10.62%
middle (neg index)          -9.16%
middle                      +1.55%

## :"Enum.fetch/2: list_huge, 1000000 elements"
out of bound                -92.34%
first (neg index)           -92.23%
out of bound (neg index)    -92.14%
middle (neg index)          -53.99%
middle                      -1.90%
last                        +0.08%
first                       +30.74%
last (neg index)            +32.17%

## :"Enum.fetch/2: list_single, 1 elements"
out of bound                -65.43%
out of bound (neg index)    -64.94%
last (neg index)            -56.09%
first (neg index)           -4.39%
first                       -2.52%
middle (neg index)          -1.20%
middle                      -0.54%
last                        +7.12%

## :"Enum.fetch/2: map, 1000 elements"
out of bound (neg index)    -99.82%
out of bound                -99.81%
first (neg index)           -78.33%
middle (neg index)          -46.61%
last (neg index)            -23.41%
last                        -7.20%
first                       +2.47%
middle                      +3.15%

## :"Enum.fetch/2: map_big, 100000 elements"
out of bound (neg index)    -100.00%
out of bound                -100.00%
first (neg index)           -74.42%
middle (neg index)          -47.51%
last (neg index)            -16.67%
middle                      -4.40%
last                        -3.88%
first                       -2.72%

## :"Enum.fetch/2: map_empty, 0 elements"
out of bound (neg index)    -83.00%
out of bound                -82.07%
last (neg index)            -81.24%
last                        -80.58%
middle (neg index)          -74.43%
middle                      -73.55%
first                       -72.88%
first (neg index)           -72.43%

## :"Enum.fetch/2: map_huge, 1000000 elements"
out of bound (neg index)    -100.00%
out of bound                -100.00%
first (neg index)           -75.87%
middle (neg index)          -46.63%
last (neg index)            -15.55%
middle                      -4.78%
first                       -4.50%
last                        -0.14%

## :"Enum.fetch/2: map_single, 1 elements"
out of bound                -86.15%
out of bound (neg index)    -82.28%
last (neg index)            -81.77%
last                        -80.65%
first (neg index)           -75.05%
middle                      -74.26%
middle (neg index)          -72.99%
first                       -72.27%

enum_fetch_bench.exs

defmodule Data do
  @terms [ :list, :list_empty, :list_single, :list_big, :list_huge,
           :map, :map_empty, :map_single, :map_big, :map_huge,
         ]

  @range -499..500
  @range_big -49_999..50_000
  @range_huge -499_999..500_000
  @list @range |> Enum.to_list
  @list_empty []
  @list_single [1]
  @list_big @range_big |> Enum.to_list
  @list_huge @range_huge |> Enum.to_list
  @map @list |> Enum.map(fn(v) -> {v, v} end) |> Enum.into(%{})
  @map_empty %{}
  @map_single %{1 => 1}
  @map_big @list_big |> Enum.map(fn(v) -> {v, v} end) |> Enum.into(%{})
  @map_huge @list_huge |> Enum.map(fn(v) -> {v, v} end) |> Enum.into(%{})

  def terms,
    do: @terms


  def get_term(:range),
    do: @range
  def get_term(:range_big),
    do: @range_big

  def get_term(:list),
    do: @list
  def get_term(:list_empty),
    do: []
  def get_term(:list_single),
    do: [1]
  def get_term(:list_big),
    do: @list_big
  def get_term(:list_huge),
    do: @list_huge

  def get_term(:map),
    do: @map
  def get_term(:map_empty),
    do: %{}
  def get_term(:map_single),
    do: %{1 => 1}
  def get_term(:map_big),
    do: @map_big
  def get_term(:map_huge),
    do: @map_huge
end

defmodule EnumFetchBench do
  import Data

  IO.puts "Elixir v#{System.build_info[:build]}"
  for term_name <- terms() do
    count = Enum.count(get_term(term_name))

    defmodule :"Enum.fetch/2: #{term_name}, #{count} elements" do
      use Benchfella
      # import Data

      @term_name term_name
      # @count get_term(term_name) |> Enum.count
      @count count
      @last @count - 1
      @middle @last |> div(2)
      @middle_neg abs(@middle) * -1
      @past @count + 1_000
      @past_neg abs(@count + 1_000) * -1

      bench "first" do
        @term_name |> get_term |> Enum.fetch(0)
      end

      bench "first (neg index)" do
        @term_name |> get_term |> Enum.fetch(-(@last))
      end

      bench "middle" do
        @term_name |> get_term |> Enum.fetch(@middle)
      end

      bench "middle (neg index)" do
        @term_name |> get_term |> Enum.fetch(@middle_neg)
      end

      bench "last" do
        @term_name |> get_term |> Enum.fetch(@last)
      end

      bench "last (neg index)" do
        @term_name |> get_term |> Enum.fetch(-1)
      end

      bench "out of bound" do
        @term_name |> get_term |> Enum.fetch(@past_neg)
      end

      bench "out of bound (neg index)" do
        @term_name |> get_term |> Enum.fetch(@past_neg)
      end
    end
  end
end