Last active
July 21, 2024 08:39
-
-
Save Qqwy/74653e58fddf3e69a7d5fd05065bca8a to your computer and use it in GitHub Desktop.
Elixir benchmark of different implementations of the 'subarray sum' problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Mix.install([ | |
:benchee, | |
{:okasaki, "~> 1.0"}, # <- used by Qqwy's Okasaki solution | |
:nx, # <- used by Qqwy's Nx solution | |
{:exla, "~> 0.5"}, # <- used by Qqwy's Nx solution | |
], | |
config: [nx: [default_backend: EXLA.Backend]] # <- used by Qqwy's Nx solution | |
) | |
inputs = %{ | |
"100" => {100, Enum.map(1..1_000, fn _ -> Enum.random(0..10) end)}, | |
"10_000" => {1000, Enum.map(1..10_000, fn _ -> Enum.random(0..100) end)}, | |
"1_000_000" => {10_000, Enum.map(1..1_000_000, fn _ -> Enum.random(0..10_000) end)} | |
} | |
defmodule Nikiiv do | |
@moduledoc """ | |
* Implement a method that will determinate if exists a range of | |
* non-negative elements in an array that sum up to a specific non- | |
* negative number | |
* | |
* Example 1 - targetSum 3, numbers = [1,7,1,1,1,5,6,1] - output true (the sum of the elements in range 2 to 4 is 3 | |
* Example 2 - targetSum 7, numbers = [0,4,5,1,8,9,12,3,1] - output false (no range sums to 7) | |
* | |
""" | |
def solution([h | t], target_sum) do | |
find_solution([h], t, h, target_sum) | |
end | |
defp find_solution(_, _, target_sum, target_sum) when target_sum > 0, do: :OK | |
defp find_solution(_, [0 | _], _, 0), do: :OK | |
defp find_solution(arr, [h | t], current_sum, target_sum) when current_sum < target_sum do | |
current_sum = current_sum + h | |
find_solution(arr ++ [h], t, current_sum, target_sum) | |
end | |
defp find_solution([h | t], right, current_sum, target_sum) when current_sum > target_sum do | |
current_sum = current_sum - h | |
find_solution(t, right, current_sum, target_sum) | |
end | |
defp find_solution([], [h | t], _, target_sum), do: find_solution([h], t, h, target_sum) | |
defp find_solution(_, [], current_sum, target_sum) when current_sum != target_sum do | |
:KO | |
end | |
defp find_solution([], [], _, _), do: :KO | |
end | |
defmodule Nikiiv2 do | |
def solve_problem(arr, target_sum) do | |
tarr = List.to_tuple(arr) | |
size = Kernel.length(arr) | |
current_sum = elem(tarr, 0) | |
left = 0 | |
right = 0 | |
solve(tarr, size, left, right, current_sum, target_sum) | |
end | |
defp solve(_, _, left, right, target_sum, target_sum) when left <= right, do: :ok | |
defp solve(tarr, size, left, right, _current_sum, target_sum) when left > right do | |
right = left | |
current_sum = elem(tarr, left) | |
solve(tarr, size, left, right, current_sum, target_sum) | |
end | |
defp solve(tarr, size, left, right, current_sum, target_sum) | |
when current_sum < target_sum and right < size - 1 do | |
right = right + 1 | |
current_sum = current_sum + elem(tarr, right) | |
solve(tarr, size, left, right, current_sum, target_sum) | |
end | |
defp solve(tarr, size, left, right, current_sum, target_sum) | |
when current_sum > target_sum and left <= right and left < size - 1 do | |
current_sum = current_sum - elem(tarr, left) | |
left = left + 1 | |
solve(tarr, size, left, right, current_sum, target_sum) | |
end | |
defp solve(_, _, _, _, current_sum, target_sum) when current_sum != target_sum, do: nil | |
end | |
defmodule Tomekowal do | |
@moduledoc """ | |
* Implement a method that will determinate if exists a range of | |
* non-negative elements in an array that sum up to a specific non- | |
* negative number | |
* | |
* Example 1 - targetSum 3, numbers = [1,7,1,1,1,5,6,1] - output true (the sum of the elements in range 2 to 4 is 3 | |
* Example 2 - targetSum 7, numbers = [0,4,5,1,8,9,12,3,1] - output false (no range sums to 7) | |
* | |
""" | |
def solution([h | t], target_sum) do | |
# start by taking first element as the current sublist | |
find_solution([h], t, h, target_sum) | |
end | |
# defp find_solution(current_sublist, rest_of_list, current_sum, target_sum) | |
# if target sum is zero, we require zero number somewhere | |
# it is not enough to simply say that zero element sublist has zero length | |
# NOTE: that edge case should be clarified because it complicates simple recursion | |
# in which empty range sums up to zero (even if there no zeros) | |
# we've found the sublist! | |
# NOTE: previous solution where `target_sum` was twice in parameters was perfectly fine and idiomatic | |
# However, in this particular example, I wanted to see three `when` clauses with `==`, `<` and `>` | |
defp find_solution(current_sublist, _rest_of_list, current_sum, target_sum) | |
when current_sum == target_sum and length(current_sublist) > 0, | |
do: :OK | |
# we need more, so we take add first element from the reset to the current sublist | |
# NOTE: this merges a case where the current sum is too low AND where current_sublist has zero elements and both current_sum and target_sum are 0 | |
defp find_solution(current_sublist, [h | t] = _rest_of_list, current_sum, target_sum) | |
when current_sum <= target_sum do | |
find_solution(current_sublist ++ [h], t, current_sum + h, target_sum) | |
end | |
# we are over target, so we drop first item from the current sublist | |
defp find_solution([h | t] = _current_sublist, rest_of_list, current_sum, target_sum) | |
when current_sum > target_sum do | |
find_solution(t, rest_of_list, current_sum - h, target_sum) | |
end | |
defp find_solution(_, _, _, _), do: :KO | |
end | |
defmodule Stefanluptak do | |
@doc """ | |
iex> Sublist.find([1, 2, 3], 3) | |
0..1 | |
iex> Sublist.find([1, 7, 1, 1, 1, 5, 6, 1], 3) | |
2..4 | |
iex> Sublist.find([0, 4, 5, 1, 8, 9, 12, 3, 1], 7) | |
nil | |
""" | |
def find(list, sum, offset \\ 0) | |
def find([], _sum, _offset), do: nil | |
def find([_head | tail] = list, sum, offset) do | |
list | |
|> Enum.scan(0, &Kernel.+/2) | |
|> Enum.find_index(&(&1 == sum)) | |
|> case do | |
nil -> | |
find(tail, sum, offset + 1) | |
index -> | |
Range.new(offset, index + offset) | |
end | |
end | |
end | |
defmodule M100phlecs do | |
def solution([num | rst], target) do | |
q = :queue.new() | |
find(rst, :queue.in(num, q), num, target) | |
end | |
defp find([], _, _, _), do: nil | |
defp find([num | rst], q, sum, target) when sum == target do | |
if :queue.is_empty(q), do: find(rst, :queue.in(num, q), num, target), else: :ok | |
end | |
defp find([num | rest], q, sum, target) when sum < target, | |
do: find(rest, :queue.in(num, q), sum + num, target) | |
defp find(lst, q, sum, target) when sum > target do | |
{{:value, prev}, q} = :queue.out(q) | |
find(lst, q, sum - prev, target) | |
end | |
end | |
defmodule Eksperimental do | |
@moduledoc """ | |
Implement a function that will determinate if exists a range consecutive of | |
non-negative elements in an list, that sum up to a specific non-negative number. | |
""" | |
@type element :: non_neg_integer() | |
@type element_list :: nonempty_list(element()) | |
@type sum :: non_neg_integer() | |
defguardp is_non_neg_integer(term) when is_integer(term) and term >= 0 | |
@doc """ | |
Determinate whether consecutive number of non-negative integers in an list | |
sum up to a specific non-negative number. Returns `true` if this condition is | |
met, otherwise returns `false`. | |
## Examples | |
# The sum of the elements in range 2 to 4 is 3 | |
iex> Coding.valid?([1,7,1,1,1,5,6,1], 3) | |
true | |
# No range sums to 7 | |
iex> Coding.valid?([0,4,5,1,8,9,12,3,1], 7) | |
false | |
""" | |
@spec valid?(element_list(), sum()) :: boolean() | |
def valid?(list, target_sum) | |
when is_list(list) and list != [] and is_non_neg_integer(target_sum) and target_sum >= 0 do | |
result = | |
Enum.reduce_while(list, [], fn | |
# If element is target_sum, we immediately return | |
^target_sum, _acc -> | |
{:halt, true} | |
element, acc -> | |
case sum_list(acc, element, target_sum) do | |
true -> | |
{:halt, true} | |
new_list -> | |
{:cont, [element | new_list]} | |
end | |
end) | |
case result do | |
true -> true | |
list when is_list(list) -> false | |
end | |
end | |
@spec sum_list( | |
nonempty_list(sum()), | |
element(), | |
sum() | |
) :: true | list() | |
defp sum_list(list, element, target_sum) | |
when is_list(list) and is_non_neg_integer(element) and is_non_neg_integer(target_sum) do | |
Enum.reduce_while(list, [], fn sum, acc -> | |
case sum(sum, element, target_sum) do | |
{:halt, true} -> | |
# We abort inmediately | |
{:halt, true} | |
{:halt, _sum} -> | |
# We do not include this result | |
{:cont, acc} | |
# This is an optimization. | |
# We don't need to store 0 | |
{:cont, 0} -> | |
{:cont, acc} | |
{:cont, sum} -> | |
# We add this result | |
{:cont, [sum | acc]} | |
end | |
end) | |
end | |
@spec sum( | |
nonempty_list(sum()), | |
element(), | |
sum() | |
) :: true | list() | |
defp sum(sum, element, target_sum) when sum + element == target_sum, | |
do: {:halt, true} | |
defp sum(sum, element, target_sum) when sum + element < target_sum, | |
do: {:cont, sum + element} | |
defp sum(sum, element, _target_sum), | |
do: {:halt, sum + element} | |
end | |
defmodule Wanton7 do | |
@moduledoc """ | |
* Implement a method that will determinate if exists a range of | |
* non-negative elements in an array that sum up to a specific non- | |
* negative number | |
* | |
* Example 1 - targetSum 3, numbers = [1,7,1,1,1,5,6,1] - output true (the sum of the elements in range 2 to 4 is 3 | |
* Example 2 - targetSum 7, numbers = [0,4,5,1,8,9,12,3,1] - output false (no range sums to 7) | |
* | |
""" | |
def solution([h | t], target_sum) do | |
find_solution(1, [h], t, h, target_sum) | |
end | |
defp find_solution(_, _, _, target_sum, target_sum) when target_sum > 0, do: :OK | |
defp find_solution(_, _, [0 | _], _, 0), do: :OK | |
defp find_solution(size, arr, [h | t], current_sum, target_sum) when current_sum < target_sum do | |
current_sum = current_sum + h | |
find_solution(size + 1, [h | arr], t, current_sum, target_sum) | |
end | |
defp find_solution(size, arr, right, current_sum, target_sum) when current_sum > target_sum do | |
size = size - 1 | |
current_sum = current_sum - Enum.at(arr, size) | |
find_solution(size, arr, right, current_sum, target_sum) | |
end | |
defp find_solution(0, _, [h | t], _, target_sum), do: find_solution(1, [h], t, h, target_sum) | |
defp find_solution(_, _, [], current_sum, target_sum) when current_sum != target_sum, do: :KO | |
defp find_solution(0, _, [], _, _), do: :KO | |
end | |
defmodule Wanton72 do | |
def solution([h | t] = arr, target_sum) do | |
find_solution(1, arr, t, h, target_sum) | |
end | |
defp find_solution(_, _, _, target_sum, target_sum) when target_sum > 0, do: :OK | |
defp find_solution(_, _, [0 | _], _, 0), do: :OK | |
defp find_solution(size, arr, [h | t], current_sum, target_sum) when current_sum < target_sum do | |
current_sum = current_sum + h | |
find_solution(size + 1, arr, t, current_sum, target_sum) | |
end | |
defp find_solution(size, [h | t], right, current_sum, target_sum) when current_sum > target_sum do | |
current_sum = current_sum - h | |
find_solution(size - 1, t, right, current_sum, target_sum) | |
end | |
defp find_solution(0, _, [h | t] = right, _, target_sum) do | |
find_solution(1, right, t, h, target_sum) | |
end | |
defp find_solution(_, _, [], current_sum, target_sum) when current_sum != target_sum, do: :KO | |
defp find_solution(0, _, [], _, _), do: :KO | |
end | |
defmodule Qqwy do | |
def valid?(list, target) do | |
do_valid?(target, list, list, 0, 0) | |
end | |
defp do_valid?(target, _, _, current, length) when current == target and length > 0, do: true | |
defp do_valid?(_, [], _, _, _), do: false | |
defp do_valid?(_, _, [], _, _), do: false | |
defp do_valid?(target, [h | hs], [l | ls], current, length) do | |
cond do | |
current <= target -> | |
do_valid?(target, hs, [l | ls], current + h, length + 1) | |
current >= target -> | |
do_valid?(target, [h | hs], ls, current - l, length - 1) | |
end | |
end | |
end | |
defmodule QqwyOkasaki do | |
@moduledoc """ | |
A straight-up 1:1 port of 100phlecs' solution but using queues from Okasaki library | |
instead of Erlang's `:queue` module. | |
Unfortunately, benchmarking shows that there is (a constant time) overhead, | |
probably because of the extra Elixir struct wrapping the queue, and dispatching happening through protocols. | |
""" | |
def solution([num | rst], target, queue_implementation \\ Okasaki.Implementations.ConstantQueue) do | |
q = Okasaki.Queue.empty(implementation: queue_implementation) | |
find(rst, Okasaki.Queue.insert(q, num), num, target) | |
end | |
defp find(lst, q, sum, target) when sum == target do | |
case {lst, Okasaki.Queue.empty?(q)} do | |
{[], true} -> | |
nil | |
{[num | rst], true} -> | |
find(rst, Okasaki.Queue.insert(q, num), num, target) | |
{_, false} -> | |
:ok | |
end | |
end | |
defp find([num | rest], q, sum, target) when sum < target, | |
do: find(rest, Okasaki.Queue.insert(q, num), sum + num, target) | |
defp find(lst, q, sum, target) when sum > target do | |
{:ok, {prev, q}} = Okasaki.Queue.remove(q) | |
find(lst, q, sum - prev, target) | |
end | |
defp find([], _, _, _), do: nil | |
end | |
defmodule QqwyNx do | |
import Nx.Defn | |
@moduledoc """ | |
A fun implementation using Nx tensors. | |
Not actually fast, since the problem is not SIMD-friendly and JIT-compilation | |
has a significant overhead when used on small input collections. | |
""" | |
def valid?(list, target) do | |
found = | |
do_valid?(target, Nx.tensor([0 | list], backend: EXLA.Backend)) | |
|> Nx.to_number | |
found == 1 | |
end | |
defn do_valid?(target, tensor) do | |
sums = Nx.cumulative_sum(tensor) | |
{_, _, _, _, found} = | |
while {target, sums, lower_index = 0, higher_index = 1, found = 0}, | |
(not found) and higher_index < Nx.flat_size(sums) | |
do | |
h = sums[higher_index] | |
l = sums[lower_index] | |
cond do | |
h - l == target and lower_index < higher_index -> | |
# Answer found: short-circuit | |
found = 1 | |
{target, sums, lower_index, higher_index, found} | |
h - l <= target -> | |
# Below target: add next element to window | |
higher_index = higher_index + 1 | |
{target, sums, lower_index, higher_index, found} | |
h - l >= target -> | |
# Above target: remove oldest element from window | |
lower_index = lower_index + 1 | |
{target, sums, lower_index, higher_index, found} | |
true -> | |
# Unreachable but Nx compiler requires it | |
{target, sums, lower_index, higher_index, found} | |
end | |
end | |
found | |
end | |
end | |
Benchee.run( | |
%{ | |
"nikiiv" => fn {sum, list} -> Nikiiv.solution(list, sum) end, | |
"nikiiv2" => fn {sum, list} -> Nikiiv2.solve_problem(list, sum) end, | |
"tomekowal" => fn {sum, list} -> Tomekowal.solution(list, sum) end, | |
"stefanluptak" => fn {sum, list} -> Stefanluptak.find(list, sum) end, | |
"100phlecs" => fn {sum, list} -> M100phlecs.solution(list, sum) end, | |
"eksperimental" => fn {sum, list} -> Eksperimental.valid?(list, sum) end, | |
"qqwy_okasaki_constant" => fn {sum, list} -> QqwyOkasaki.solution(list, sum, Okasaki.Implementations.ConstantQueue) end, | |
"qqwy_okasaki_amortized" => fn {sum, list} -> QqwyOkasaki.solution(list, sum, Okasaki.Implementations.AmortizedQueue) end, | |
"qqwy_okasaki_erlang" => fn {sum, list} -> QqwyOkasaki.solution(list, sum, Okasaki.Implementations.ErlangQueue) end, | |
"qqwy_nx" => fn {sum, list} -> QqwyNx.valid?(list, sum) end, | |
"qqwy" => fn {sum, list} -> Qqwy.valid?(list, sum) end, | |
"wanton7" => fn {sum, list} -> Wanton7.solution(list, sum) end, | |
"wanton72" => fn {sum, list} -> Wanton72.solution(list, sum) end, | |
}, | |
inputs: inputs, | |
warmup: 0.5, | |
time: 1, | |
memory_time: 1, | |
reduction_time: 1 | |
) | |
➜ elixir benchmarks.exs
Operating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 16 GB
Elixir 1.15.0
Erlang 25.0
Benchmark suite executing with the following configuration:
warmup: 500 ms
time: 1 s
memory time: 1 s
reduction time: 1 s
parallel: 1
inputs: 100, 10_000, 1_000_000
Estimated total run time: 2.27 min
Benchmarking 100phlecs with input 100 ...
Benchmarking 100phlecs with input 10_000 ...
Benchmarking 100phlecs with input 1_000_000 ...
Benchmarking eksperimental with input 100 ...
Benchmarking eksperimental with input 10_000 ...
Benchmarking eksperimental with input 1_000_000 ...
Benchmarking nikiiv with input 100 ...
Benchmarking nikiiv with input 10_000 ...
Benchmarking nikiiv with input 1_000_000 ...
Benchmarking nikiiv2 with input 100 ...
Benchmarking nikiiv2 with input 10_000 ...
Benchmarking nikiiv2 with input 1_000_000 ...
Benchmarking qqwy with input 100 ...
Benchmarking qqwy with input 10_000 ...
Benchmarking qqwy with input 1_000_000 ...
Benchmarking qqwy_nx with input 100 ...
14:33:07.171 [info] TfrtCpuClient created.
Benchmarking qqwy_nx with input 10_000 ...
Benchmarking qqwy_nx with input 1_000_000 ...
Benchmarking qqwy_okasaki_amortized with input 100 ...
Benchmarking qqwy_okasaki_amortized with input 10_000 ...
Benchmarking qqwy_okasaki_amortized with input 1_000_000 ...
Benchmarking qqwy_okasaki_constant with input 100 ...
Benchmarking qqwy_okasaki_constant with input 10_000 ...
Benchmarking qqwy_okasaki_constant with input 1_000_000 ...
Benchmarking qqwy_okasaki_erlang with input 100 ...
Benchmarking qqwy_okasaki_erlang with input 10_000 ...
Benchmarking qqwy_okasaki_erlang with input 1_000_000 ...
Benchmarking stefanluptak with input 100 ...
Benchmarking stefanluptak with input 10_000 ...
Benchmarking stefanluptak with input 1_000_000 ...
Benchmarking tomekowal with input 100 ...
Benchmarking tomekowal with input 10_000 ...
Benchmarking tomekowal with input 1_000_000 ...
Benchmarking wanton7 with input 100 ...
Benchmarking wanton7 with input 10_000 ...
Benchmarking wanton7 with input 1_000_000 ...
Benchmarking wanton72 with input 100 ...
Benchmarking wanton72 with input 10_000 ...
Benchmarking wanton72 with input 1_000_000 ...
##### With input 100 #####
Name ips average deviation median 99th %
qqwy 4272.33 K 0.23 μs ±52.28% 0.25 μs 0.38 μs
wanton72 4209.73 K 0.24 μs ±39.10% 0.25 μs 0.38 μs
100phlecs 1413.34 K 0.71 μs ±1352.57% 0.58 μs 0.92 μs
wanton7 756.03 K 1.32 μs ±897.87% 1.21 μs 1.46 μs
nikiiv 750.64 K 1.33 μs ±563.77% 1.25 μs 1.58 μs
tomekowal 734.15 K 1.36 μs ±497.97% 1.25 μs 1.54 μs
qqwy_okasaki_erlang 345.05 K 2.90 μs ±352.25% 2.67 μs 4.33 μs
qqwy_okasaki_amortized 336.25 K 2.97 μs ±250.51% 2.88 μs 3.21 μs
nikiiv2 295.09 K 3.39 μs ±67.50% 3.29 μs 3.83 μs
qqwy_okasaki_constant 270.46 K 3.70 μs ±319.20% 3.42 μs 4.92 μs
eksperimental 113.38 K 8.82 μs ±154.92% 8.17 μs 40 μs
stefanluptak 1.48 K 677.72 μs ±16.20% 667.33 μs 818.48 μs
qqwy_nx 0.0477 K 20956.23 μs ±5.44% 20558.48 μs 25253.79 μs
Comparison:
qqwy 4272.33 K
wanton72 4209.73 K - 1.01x slower +0.00348 μs
100phlecs 1413.34 K - 3.02x slower +0.47 μs
wanton7 756.03 K - 5.65x slower +1.09 μs
nikiiv 750.64 K - 5.69x slower +1.10 μs
tomekowal 734.15 K - 5.82x slower +1.13 μs
qqwy_okasaki_erlang 345.05 K - 12.38x slower +2.66 μs
qqwy_okasaki_amortized 336.25 K - 12.71x slower +2.74 μs
nikiiv2 295.09 K - 14.48x slower +3.15 μs
qqwy_okasaki_constant 270.46 K - 15.80x slower +3.46 μs
eksperimental 113.38 K - 37.68x slower +8.59 μs
stefanluptak 1.48 K - 2895.44x slower +677.49 μs
qqwy_nx 0.0477 K - 89531.96x slower +20956.00 μs
Memory usage statistics:
Name average deviation median 99th %
qqwy 0 KB ±0.00% 0 KB 0 KB
wanton72 0 KB ±0.00% 0 KB 0 KB
100phlecs 5.20 KB ±0.00% 5.20 KB 5.20 KB
wanton7 1.16 KB ±0.00% 1.16 KB 1.16 KB
nikiiv 13.52 KB ±0.00% 13.52 KB 13.52 KB
tomekowal 13.52 KB ±0.00% 13.52 KB 13.52 KB
qqwy_okasaki_erlang 9.34 KB ±0.00% 9.34 KB 9.34 KB
qqwy_okasaki_amortized 9.62 KB ±0.00% 9.62 KB 9.62 KB
nikiiv2 0 KB ±0.00% 0 KB 0 KB
qqwy_okasaki_constant 11.13 KB ±0.00% 11.13 KB 11.13 KB
eksperimental 57.15 KB ±0.00% 57.15 KB 57.15 KB
stefanluptak 387.20 KB ±0.00% 387.20 KB 387.20 KB
qqwy_nx 12714.51 KB ±0.02% 12715.55 KB 12719.06 KB
Comparison:
qqwy 0 KB
wanton72 0 KB - 1.00x memory usage +0 KB
100phlecs 5.20 KB - ∞ x memory usage +5.20 KB
wanton7 1.16 KB - ∞ x memory usage +1.16 KB
nikiiv 13.52 KB - ∞ x memory usage +13.52 KB
tomekowal 13.52 KB - ∞ x memory usage +13.52 KB
qqwy_okasaki_erlang 9.34 KB - ∞ x memory usage +9.34 KB
qqwy_okasaki_amortized 9.62 KB - ∞ x memory usage +9.62 KB
nikiiv2 0 KB - 1.00x memory usage +0 KB
qqwy_okasaki_constant 11.13 KB - ∞ x memory usage +11.13 KB
eksperimental 57.15 KB - ∞ x memory usage +57.15 KB
stefanluptak 387.20 KB - ∞ x memory usage +387.20 KB
qqwy_nx 12714.51 KB - ∞ x memory usage +12714.51 KB
Reduction count statistics:
Name average deviation median 99th %
qqwy 77 ±0.00% 77 77
wanton72 76 ±0.00% 76 76
100phlecs 475 ±0.00% 475 475
wanton7 896 ±0.00% 896 896
nikiiv 324 ±0.00% 324 324
tomekowal 325 ±0.00% 325 325
qqwy_okasaki_erlang 1414 ±0.00% 1414 1414
qqwy_okasaki_amortized 1173 ±0.00% 1173 1173
nikiiv2 439 ±0.00% 439 439
qqwy_okasaki_constant 1139 ±0.00% 1139 1139
eksperimental 5109 ±0.00% 5109 5109
stefanluptak 121249 ±0.00% 121249 121249
qqwy_nx 811508.05 ±0.13% 811185 815392
Comparison:
qqwy 77
wanton72 76 - 0.99x reduction count -1
100phlecs 475 - 6.17x reduction count +398
wanton7 896 - 11.64x reduction count +819
nikiiv 324 - 4.21x reduction count +247
tomekowal 325 - 4.22x reduction count +248
qqwy_okasaki_erlang 1414 - 18.36x reduction count +1337
qqwy_okasaki_amortized 1173 - 15.23x reduction count +1096
nikiiv2 439 - 5.70x reduction count +362
qqwy_okasaki_constant 1139 - 14.79x reduction count +1062
eksperimental 5109 - 66.35x reduction count +5032
stefanluptak 121249 - 1574.66x reduction count +121172
qqwy_nx 811508.05 - 10539.07x reduction count +811431.05
##### With input 10_000 #####
Name ips average deviation median 99th %
wanton72 5403.52 K 0.185 μs ±38.37% 0.167 μs 0.29 μs
qqwy 5305.83 K 0.188 μs ±84.23% 0.167 μs 0.29 μs
100phlecs 2157.44 K 0.46 μs ±1217.80% 0.42 μs 0.58 μs
wanton7 958.76 K 1.04 μs ±1150.24% 0.92 μs 1.13 μs
nikiiv 929.89 K 1.08 μs ±668.00% 1 μs 1.29 μs
tomekowal 678.60 K 1.47 μs ±599.21% 1.04 μs 5.21 μs
qqwy_okasaki_erlang 471.32 K 2.12 μs ±384.63% 2 μs 2.33 μs
qqwy_okasaki_amortized 421.06 K 2.37 μs ±442.91% 2.29 μs 2.63 μs
qqwy_okasaki_constant 330.69 K 3.02 μs ±502.10% 2.75 μs 3.83 μs
eksperimental 134.32 K 7.44 μs ±234.34% 6.67 μs 38.67 μs
nikiiv2 26.69 K 37.46 μs ±61.26% 39 μs 51.71 μs
stefanluptak 0.26 K 3853.09 μs ±6.45% 3823.07 μs 4040.31 μs
qqwy_nx 0.0564 K 17733.98 μs ±5.05% 17346.58 μs 21416.13 μs
Comparison:
wanton72 5403.52 K
qqwy 5305.83 K - 1.02x slower +0.00341 μs
100phlecs 2157.44 K - 2.50x slower +0.28 μs
wanton7 958.76 K - 5.64x slower +0.86 μs
nikiiv 929.89 K - 5.81x slower +0.89 μs
tomekowal 678.60 K - 7.96x slower +1.29 μs
qqwy_okasaki_erlang 471.32 K - 11.46x slower +1.94 μs
qqwy_okasaki_amortized 421.06 K - 12.83x slower +2.19 μs
qqwy_okasaki_constant 330.69 K - 16.34x slower +2.84 μs
eksperimental 134.32 K - 40.23x slower +7.26 μs
nikiiv2 26.69 K - 202.42x slower +37.28 μs
stefanluptak 0.26 K - 20820.23x slower +3852.90 μs
qqwy_nx 0.0564 K - 95825.89x slower +17733.80 μs
Memory usage statistics:
Name average deviation median 99th %
wanton72 0 KB ±0.00% 0 KB 0 KB
qqwy 0 KB ±0.00% 0 KB 0 KB
100phlecs 3.96 KB ±0.00% 3.96 KB 3.96 KB
wanton7 0.92 KB ±0.00% 0.92 KB 0.92 KB
nikiiv 11.02 KB ±0.00% 11.02 KB 11.02 KB
tomekowal 11.02 KB ±0.00% 11.02 KB 11.02 KB
qqwy_okasaki_erlang 7.24 KB ±0.00% 7.24 KB 7.24 KB
qqwy_okasaki_amortized 7.48 KB ±0.00% 7.48 KB 7.48 KB
qqwy_okasaki_constant 9.13 KB ±0.00% 9.13 KB 9.13 KB
eksperimental 46.35 KB ±0.00% 46.35 KB 46.35 KB
nikiiv2 0 KB ±0.00% 0 KB 0 KB
stefanluptak 2967.06 KB ±0.00% 2967.06 KB 2967.06 KB
qqwy_nx 11293.81 KB ±0.01% 11293.92 KB 11296.37 KB
Comparison:
wanton72 0 KB
qqwy 0 KB - 1.00x memory usage +0 KB
100phlecs 3.96 KB - ∞ x memory usage +3.96 KB
wanton7 0.92 KB - ∞ x memory usage +0.92 KB
nikiiv 11.02 KB - ∞ x memory usage +11.02 KB
tomekowal 11.02 KB - ∞ x memory usage +11.02 KB
qqwy_okasaki_erlang 7.24 KB - ∞ x memory usage +7.24 KB
qqwy_okasaki_amortized 7.48 KB - ∞ x memory usage +7.48 KB
qqwy_okasaki_constant 9.13 KB - ∞ x memory usage +9.13 KB
eksperimental 46.35 KB - ∞ x memory usage +46.35 KB
nikiiv2 0 KB - 1.00x memory usage +0 KB
stefanluptak 2967.06 KB - ∞ x memory usage +2967.06 KB
qqwy_nx 11293.81 KB - ∞ x memory usage +11293.81 KB
Reduction count statistics:
Name average deviation median 99th %
wanton72 61 ±0.00% 61 61
qqwy 62 ±0.00% 62 62
100phlecs 219 ±0.00% 219 219
wanton7 706 ±0.00% 706 706
nikiiv 101 ±0.00% 101 101
tomekowal 102 ±0.00% 102 102
qqwy_okasaki_erlang 814 ±0.00% 814 814
qqwy_okasaki_amortized 620 ±0.00% 620 620
qqwy_okasaki_constant 772 ±0.00% 772 772
eksperimental 3814 ±0.00% 3814 3814
nikiiv2 3687 ±0.00% 3687 3687
stefanluptak 923069 ±0.00% 923069 923069
qqwy_nx 825682.49 ±0.19% 825310 830201
Comparison:
wanton72 61
qqwy 62 - 1.02x reduction count +1
100phlecs 219 - 3.59x reduction count +158
wanton7 706 - 11.57x reduction count +645
nikiiv 101 - 1.66x reduction count +40
tomekowal 102 - 1.67x reduction count +41
qqwy_okasaki_erlang 814 - 13.34x reduction count +753
qqwy_okasaki_amortized 620 - 10.16x reduction count +559
qqwy_okasaki_constant 772 - 12.66x reduction count +711
eksperimental 3814 - 62.52x reduction count +3753
nikiiv2 3687 - 60.44x reduction count +3626
stefanluptak 923069 - 15132.28x reduction count +923008
qqwy_nx 825682.49 - 13535.78x reduction count +825621.49
##### With input 1_000_000 #####
Name ips average deviation median 99th %
wanton72 13.49 K 74.14 μs ±2.81% 74.13 μs 79.95 μs
qqwy 12.67 K 78.90 μs ±4.57% 79.33 μs 83.04 μs
tomekowal 6.51 K 153.59 μs ±37.01% 149.58 μs 224.16 μs
nikiiv 6.51 K 153.62 μs ±36.85% 152.21 μs 177.45 μs
100phlecs 5.59 K 178.82 μs ±33.56% 177.46 μs 198.25 μs
wanton7 4.35 K 229.73 μs ±30.08% 224.58 μs 310.48 μs
eksperimental 1.73 K 577.66 μs ±35.37% 497 μs 1121.22 μs
qqwy_okasaki_amortized 1.25 K 801.76 μs ±17.34% 792.71 μs 907.51 μs
qqwy_okasaki_constant 1.11 K 900.52 μs ±16.05% 889.00 μs 1001.37 μs
qqwy_okasaki_erlang 0.89 K 1120.28 μs ±23.66% 1078.62 μs 1518.26 μs
nikiiv2 0.21 K 4661.71 μs ±16.51% 4206.83 μs 7317.24 μs
qqwy_nx 0.00015 K 6882592.79 μs ±0.00% 6882592.79 μs 6882592.79 μs
stefanluptak 0.00000 K336956857.20 μs ±0.00%336956857.20 μs336956857.20 μs
Comparison:
wanton72 13.49 K
qqwy 12.67 K - 1.06x slower +4.76 μs
tomekowal 6.51 K - 2.07x slower +79.44 μs
nikiiv 6.51 K - 2.07x slower +79.48 μs
100phlecs 5.59 K - 2.41x slower +104.68 μs
wanton7 4.35 K - 3.10x slower +155.59 μs
eksperimental 1.73 K - 7.79x slower +503.52 μs
qqwy_okasaki_amortized 1.25 K - 10.81x slower +727.62 μs
qqwy_okasaki_constant 1.11 K - 12.15x slower +826.38 μs
qqwy_okasaki_erlang 0.89 K - 15.11x slower +1046.14 μs
nikiiv2 0.21 K - 62.88x slower +4587.57 μs
qqwy_nx 0.00015 K - 92831.87x slower +6882518.65 μs
stefanluptak 0.00000 K - 4544847.56x slower +336956783.06 μs
Memory usage statistics:
Name Memory usage
wanton72 0 MB
qqwy 0 MB - 1.00x memory usage +0 MB
tomekowal 0.40 MB - ∞ x memory usage +0.40 MB
nikiiv 0.40 MB - ∞ x memory usage +0.40 MB
100phlecs 1.18 MB - ∞ x memory usage +1.18 MB
wanton7 0.30 MB - ∞ x memory usage +0.30 MB
eksperimental 2.21 MB - ∞ x memory usage +2.21 MB
qqwy_okasaki_amortized 2.54 MB - ∞ x memory usage +2.54 MB
qqwy_okasaki_constant 2.88 MB - ∞ x memory usage +2.88 MB
qqwy_okasaki_erlang 2.37 MB - ∞ x memory usage +2.37 MB
nikiiv2 0 MB - 1.00x memory usage +0 MB
qqwy_nx 3235.34 MB - ∞ x memory usage +3235.34 MB
stefanluptak 148456.41 MB - ∞ x memory usage +148456.41 MB
**All measurements for memory usage were the same**
Reduction count statistics:
Name average deviation median 99th %
wanton72 19.56 K ±0.00% 19.56 K 19.56 K
qqwy 19.56 K ±0.00% 19.56 K 19.56 K
tomekowal 29.34 K ±0.00% 29.34 K 29.34 K
nikiiv 29.34 K ±0.00% 29.34 K 29.34 K
100phlecs 79.94 K ±0.32% 79.97 K 80.73 K
wanton7 163.27 K ±0.00% 163.27 K 163.27 K
eksperimental 239.54 K ±0.21% 239.65 K 240.88 K
qqwy_okasaki_amortized 218.31 K ±0.10% 218.28 K 218.95 K
qqwy_okasaki_constant 272.71 K ±0.16% 272.56 K 274.43 K
qqwy_okasaki_erlang 265.57 K ±0.08% 265.45 K 266.45 K
nikiiv2 99.64 K ±0.88% 99.53 K 106.20 K
qqwy_nx 213890.61 K ±0.00% 213890.61 K 213890.61 K
stefanluptak 49206910.82 K ±0.00% 49206910.82 K 49206910.82 K
Comparison:
wanton72 19.56 K
qqwy 19.56 K - 1.00x reduction count +0.00100 K
tomekowal 29.34 K - 1.50x reduction count +9.78 K
nikiiv 29.34 K - 1.50x reduction count +9.78 K
100phlecs 79.94 K - 4.09x reduction count +60.38 K
wanton7 163.27 K - 8.35x reduction count +143.72 K
eksperimental 239.54 K - 12.25x reduction count +219.98 K
qqwy_okasaki_amortized 218.31 K - 11.16x reduction count +198.75 K
qqwy_okasaki_constant 272.71 K - 13.94x reduction count +253.15 K
qqwy_okasaki_erlang 265.57 K - 13.58x reduction count +246.01 K
nikiiv2 99.64 K - 5.09x reduction count +80.08 K
qqwy_nx 213890.61 K - 10936.78x reduction count +213871.05 K
stefanluptak 49206910.82 K - 2516076.64x reduction count +49206891.26 K
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Elixir forum topic where this discussion started: https://elixirforum.com/t/learning-idiomatic-elixir-q1/57934/22
Updated version of https://gist.github.com/stefanluptak/e4920d0bd85b44cec44a97f833e1ed57