00-README.md

The following module can be placed in the root level of elixir-lang/elixir and executed using the following:

bin/elixirc keyword_delete_bench.ex && erl -noshell -pa . -pa lib/elixir/ebin -s 'keyword_delete_bench'

Example (minimized output):

## count=100000, size=10
[h] delete_v0/2:     1.56 μs (avg),   353.70 gc/μs (avg),    41.13 reds/μs (avg)
[m] delete_v0/2:     1.91 μs (avg),   296.56 gc/μs (avg),    38.38 reds/μs (avg)
[h] delete_v1/2:     2.13 μs (avg),   232.77 gc/μs (avg),    19.46 reds/μs (avg)
[m] delete_v1/2:     1.16 μs (avg),   406.83 gc/μs (avg),    16.46 reds/μs (avg)
[h] delete_v2/2:     1.10 μs (avg),   580.03 gc/μs (avg),    17.61 reds/μs (avg)
[m] delete_v2/2:     1.20 μs (avg),   560.04 gc/μs (avg),    17.38 reds/μs (avg)
[h] delete_v3/2:     1.10 μs (avg),   583.97 gc/μs (avg),    18.62 reds/μs (avg)
[m] delete_v3/2:     1.01 μs (avg),   349.55 gc/μs (avg),     5.99 reds/μs (avg)
[h] delete_v4/2:     2.15 μs (avg),   230.79 gc/μs (avg),    19.43 reds/μs (avg)
[m] delete_v4/2:     1.00 μs (avg),   350.56 gc/μs (avg),     5.99 reds/μs (avg)
## count=100000, size=100
[h] delete_v0/2:     6.80 μs (avg),   292.74 gc/μs (avg),    73.88 reds/μs (avg)
[m] delete_v0/2:     6.85 μs (avg),   293.00 gc/μs (avg),    72.89 reds/μs (avg)
[h] delete_v1/2:     3.77 μs (avg),   514.05 gc/μs (avg),    98.71 reds/μs (avg)
[m] delete_v1/2:     2.30 μs (avg),   205.54 gc/μs (avg),    59.24 reds/μs (avg)
[h] delete_v2/2:     3.32 μs (avg),  1061.19 gc/μs (avg),    61.16 reds/μs (avg)
[m] delete_v2/2:     3.31 μs (avg),  1073.99 gc/μs (avg),    60.90 reds/μs (avg)
[h] delete_v3/2:     3.53 μs (avg),   997.14 gc/μs (avg),    55.78 reds/μs (avg)
[m] delete_v3/2:     1.01 μs (avg),   348.60 gc/μs (avg),     5.98 reds/μs (avg)
[h] delete_v4/2:     3.80 μs (avg),   509.64 gc/μs (avg),    90.84 reds/μs (avg)
[m] delete_v4/2:     1.01 μs (avg),   349.54 gc/μs (avg),     5.99 reds/μs (avg)
## count=100000, size=10000
[h] delete_v0/2:   303.92 μs (avg),   527.75 gc/μs (avg),   134.67 reds/μs (avg)
[m] delete_v0/2:   305.38 μs (avg),   525.28 gc/μs (avg),   134.01 reds/μs (avg)
[h] delete_v1/2:   129.10 μs (avg),  1242.00 gc/μs (avg),   157.09 reds/μs (avg)
[m] delete_v1/2:   141.72 μs (avg),     3.36 gc/μs (avg),    71.43 reds/μs (avg)
[h] delete_v2/2:   122.49 μs (avg),  2310.56 gc/μs (avg),    96.92 reds/μs (avg)
[m] delete_v2/2:   122.97 μs (avg),  2301.67 gc/μs (avg),    96.52 reds/μs (avg)
[h] delete_v3/2:   150.64 μs (avg),  1878.88 gc/μs (avg),    77.73 reds/μs (avg)
[m] delete_v3/2:    20.90 μs (avg),    17.03 gc/μs (avg),     0.29 reds/μs (avg)
[h] delete_v4/2:   161.10 μs (avg),   995.29 gc/μs (avg),   125.84 reds/μs (avg)
[m] delete_v4/2:    20.76 μs (avg),    17.15 gc/μs (avg),     0.29 reds/μs (avg)

keyword_delete_bench.ex

defmodule :keyword_delete_bench do
  @compile :inline_list_funcs

  def start() do
    :io.setopts([{:binary, true}, {:encoding, :unicode}])
    run(1_000_00)
    :erlang.halt()
  end

  def run(count) do
    run(count, 10)
    run(count, 100)
    run(count, 10000)
  end

  defp run(count, size) do
    run(1000, size, "warm up")
    run(1000, size, nil)
    run(count, size, nil)
  end

  defp run(count, size, label) when is_integer(count) and count > 0 do
    case label do
      nil ->
        :io.format('## count=~w, size=~w~n', [count, size])

      _ ->
        :io.format('## count=~w, size=~w (~s)~n', [count, size, label])
    end

    keywords = make_keywords(size)
    hits = {:"k#{size}", size}
    miss = {:"k#{size + 1}", size + 1}

    _ =
      measure(count, "delete_v0/2", keywords, hits, miss, fn kv, {key, _} ->
        :keyword_delete_bench.delete_v0(kv, key)
      end)

    _ =
      measure(count, "delete_v1/2", keywords, hits, miss, fn kv, {key, _} ->
        :keyword_delete_bench.delete_v1(kv, key)
      end)

    _ =
      measure(count, "delete_v2/2", keywords, hits, miss, fn kv, {key, _} ->
        :keyword_delete_bench.delete_v2(kv, key)
      end)

    _ =
      measure(count, "delete_v3/2", keywords, hits, miss, fn kv, {key, _} ->
        :keyword_delete_bench.delete_v3(kv, key)
      end)

    _ =
      measure(count, "delete_v4/2", keywords, hits, miss, fn kv, {key, _} ->
        :keyword_delete_bench.delete_v4(kv, key)
      end)

    :ok
  end

  defp make_keywords(0) do
    Keyword.new()
  end

  defp make_keywords(size) when is_integer(size) and size > 0 do
    make_keywords(size, [])
  end

  defp make_keywords(0, keywords) do
    keywords
  end

  defp make_keywords(value, keywords) do
    key = :"k#{value}"
    make_keywords(value - 1, [{key, value} | keywords])
  end

  defp measure(count, label, keywords, hits, miss, fun) do
    _ = measure(count, <<"[h] ", label::binary(), ?:>>, keywords, hits, fun)
    _ = measure(count, <<"[m] ", label::binary(), ?:>>, keywords, miss, fun)
    :ok
  end

  defp measure(count, label, keywords, pair, fun) do
    :io.format('~s', [:string.left(:binary.bin_to_list(label), 24)])
    parent = self()

    child =
      spawn(fn ->
        me = self()

        tracer =
          spawn_link(fn ->
            _ = :erlang.trace(me, true, [:garbage_collection, {:tracer, self()}])
            tracer_loop(me, 0)
          end)

        {_tmin, _tmax, tacc, _rmin, _rmax, _racc, _dmin, _dmax, dacc} =
          measure_loop(count, me, nil, keywords, pair, fun, nil)

        :erlang.garbage_collect(me)

        tracer_ref = Process.monitor(tracer)
        send(tracer, {:get_collected_memory, me, tracer_ref})

        tracer_memory =
          receive do
            {:DOWN, ^tracer_ref, _, _, _} ->
              0

            {^tracer_ref, memory} when is_integer(memory) ->
              memory
          end

        tavg = tacc / count
        # ravg = racc / count
        davg = dacc / count
        hacc = tracer_memory * :erlang.system_info(:wordsize)
        havg = hacc / tacc
        # msec = tacc / 1000
        :io.format('~ts ~ts, ~ts ~ts, ~ts ~ts~n', [
          # :string.right(:erlang.integer_to_list(tmax), 14),
          :string.right(
            :binary.bin_to_list(:erlang.iolist_to_binary(:io_lib.format('~.2f', [tavg]))),
            8
          ),
          "μs (avg)",
          # :string.right(:erlang.integer_to_list(hacc), 14),
          :string.right(
            :binary.bin_to_list(:erlang.iolist_to_binary(:io_lib.format('~.2f', [havg]))),
            8
          ),
          "gc/μs (avg)",
          :string.right(
            :binary.bin_to_list(:erlang.iolist_to_binary(:io_lib.format('~.2f', [davg]))),
            8
          ),
          "reds/μs (avg)"
        ])

        send(parent, {me, :ok})
      end)

    receive do
      {^child, :ok} ->
        :ok
    end
  end

  defp measure_loop(0, _me, stat, _keywords, _pair, _fun, _result) do
    stat
  end

  defp measure_loop(count, me, nil, keywords, pair, fun, nil) do
    ta = :erlang.monotonic_time()
    {:reductions, ra} = :erlang.process_info(me, :reductions)
    result = fun.(keywords, pair)
    {:reductions, rb} = :erlang.process_info(me, :reductions)
    tb = :erlang.monotonic_time()
    r = rb - ra
    t = max(:erlang.convert_time_unit(tb - ta, :native, :microsecond), 1)
    d = r / t
    stat = {t, t, t, r, r, r, d, d, d}
    measure_loop(count - 1, me, stat, keywords, pair, fun, result)
  end

  defp measure_loop(
         count,
         me,
         {tmin, tmax, tacc, rmin, rmax, racc, dmin, dmax, dacc},
         keywords,
         pair,
         fun,
         result
       ) do
    ta = :erlang.monotonic_time()
    {:reductions, ra} = :erlang.process_info(me, :reductions)
    new_result = fun.(keywords, pair)
    {:reductions, rb} = :erlang.process_info(me, :reductions)
    tb = :erlang.monotonic_time()
    ^result = new_result
    r = rb - ra
    t = max(:erlang.convert_time_unit(tb - ta, :native, :microsecond), 1)
    d = r / t
    {tmin, tmax, tacc} = update_stat({tmin, tmax, tacc}, t)
    {rmin, rmax, racc} = update_stat({rmin, rmax, racc}, r)
    {dmin, dmax, dacc} = update_stat({dmin, dmax, dacc}, d)
    stat = {tmin, tmax, tacc, rmin, rmax, racc, dmin, dmax, dacc}
    measure_loop(count - 1, me, stat, keywords, pair, fun, result)
  end

  defp update_stat({xmin, xmax, xacc}, x) do
    xmin = min(xmin, x)
    xmax = max(xmax, x)
    xacc = xacc + x
    {xmin, xmax, xacc}
  end

  defp tracer_loop(pid, acc) do
    receive do
      {:get_collected_memory, reply_to, ref} ->
        send(reply_to, {ref, acc})
        exit(:normal)

      {:trace, ^pid, :gc_minor_start, info} ->
        tracer_wait_gc_end(pid, :gc_minor_end, acc, Keyword.fetch!(info, :heap_size))

      {:trace, ^pid, :gc_major_start, info} ->
        tracer_wait_gc_end(pid, :gc_major_end, acc, Keyword.fetch!(info, :heap_size))

      :done ->
        exit(:normal)
    end
  end

  defp tracer_wait_gc_end(pid, tag, acc, mem_before) do
    receive do
      {:trace, ^pid, ^tag, info} ->
        mem_after = Keyword.fetch!(info, :heap_size)
        tracer_loop(pid, acc + mem_before - mem_after)
    end
  end

  # Implementations

  @compile {:inline, delete_v0: 2}
  def delete_v0(keywords, key) when is_list(keywords) and is_atom(key) do
    :lists.filter(fn {k, _} -> k != key end, keywords)
  end

  @compile {:inline, delete_v1: 2}
  def delete_v1(keywords, key) when is_list(keywords) and is_atom(key) do
    delete_v1_key(keywords, key, _deleted? = false)
  catch
    :not_deleted -> keywords
  end

  defp delete_v1_key([{key, _} | rest], key, _deleted?), do: delete_v1_key(rest, key, true)

  defp delete_v1_key([{_, _} = pair | rest], key, deleted?),
    do: [pair | delete_v1_key(rest, key, deleted?)]

  defp delete_v1_key([], _key, _deleted? = true), do: []
  defp delete_v1_key([], _key, _deleted? = false), do: throw(:not_deleted)

  @compile {:inline, delete_v2: 2}
  def delete_v2(keywords, key) when is_list(keywords) and is_atom(key) do
    delete_v2_key(keywords, key, [])
  end

  defp delete_v2_key([{key, _} | tail], key, heads) do
    delete_v2_key(tail, key, heads)
  end

  defp delete_v2_key([{_, _} = pair | tail], key, heads) do
    delete_v2_key(tail, key, [pair | heads])
  end

  defp delete_v2_key([], _key, heads) do
    :lists.reverse(heads)
  end

  @compile {:inline, delete_v3: 2}
  def delete_v3(keywords, key) when is_list(keywords) and is_atom(key) do
    cond do
      :lists.keymember(key, 1, keywords) -> delete_v3_key(keywords, key, [])
      true -> keywords
    end
  end

  defp delete_v3_key([{key, _} | tail], key, heads) do
    delete_v3_key(tail, key, heads)
  end

  defp delete_v3_key([{_, _} = pair | tail], key, heads) do
    delete_v3_key(tail, key, [pair | heads])
  end

  defp delete_v3_key([], _key, heads) do
    :lists.reverse(heads)
  end

  @compile {:inline, delete_v4: 2}
  def delete_v4(keywords, key) when is_list(keywords) and is_atom(key) do
    case :lists.keymember(key, 1, keywords) do
      true -> delete_v4_key(keywords, key)
      _ -> keywords
    end
  end

  defp delete_v4_key([{key, _} | tail], key) do
    delete_v4_key(tail, key)
  end

  defp delete_v4_key([{_, _} = pair | tail], key) do
    [pair | delete_v4_key(tail, key)]
  end

  defp delete_v4_key([], _key) do
    []
  end
end