[eeps] EEP ???: Maps based set implementation
José Valim
jose.valim@REDACTED
Wed Sep 18 17:22:06 CEST 2019
Author: José Valim <jose(dot)valim(at)gmail(dot)com>
Status: Draft
Type: Standards Track
Created: 18-Sep-2019
Post-History:
****
EEP ???: Maps based set implementation
----
Abstract
========
This EEP proposes a maps-based set implementation and a group of BIFs
with the goal of providing a *de facto* sets implementation in Erlang/OTP.
Motivation
==========
In order to efficiently use sets in Erlang/OTP today, one has to
consider three different options:
* `ordsets`
* `gb_sets`
* using maps as sets (such as `cerl_sets`)
For example, if you wish to perform unions/intersections/subtractions,
`ordsets` is generally the most efficient. For individual lookups,
`gb_sets` and "maps as sets" are preferred, although the latter has no
official API in Erlang/OTP. If you need a mixed profile, the best choice
becomes blurrier. Note there is also a `sets` module, but it is rarely a
viable option.
The current landscape with sets is not much different than the dictionary
landscape before Erlang/OTP 17. Luckily, once `maps` were added, `maps`
became the *de facto* dictionary in Erlang. The other dictionary-like
modules
may perform better under limited occasions but `maps` provide the best
profile in many scenarios and are a reasonable starting point (until a
need for benchmarking and profiling arises - if it ever arises).
The goal of this EEP is to propose a map-based sets solution with a group
of BIFs that will give developers a sets implementation that can be
generally
treated as the main set implementation in Erlang/OTP.
Rationale
=========
Dictionaries and sets implementation tend to walk side-by-side. Such as
`ordsets` and `orddict`, `gb_trees` and `gb_sets`. That's because you can
consider elements in a set to be keys in a dictionary, where you don't care
about the value for the keys.
Given we have dictionaries implemented as maps, could we have sets based
on maps? The answer is yes and there are two approaches. The first approach
is to provide a native data structure, implemented in C, with its own
syntax.
The advantage of said approach would be lower memory usage, but it has a
large
impact on the language and on the runtime. Therefore that's not the approach
we will pursue here.
The second approach, which this EEP advocates for, is to implement `sets`
on top of maps, as done by `cerl_sets`. In this scenario, the sets elements
are keys in the map and the values are empty lists (we chose empty lists
because they are very cheap to serialize).
Using "maps as sets" provide good performance characteristics today for
inserting, adding and deleting set elements, being faster than all other
implementations. However, in terms of memory usage, "maps as sets" use
almost two times more memory than `ordsets` (although note that the set
operations themselves may end-up using less memory). Compared to `gb_sets`,
"maps as sets" use less memory altogether.
But can "maps as sets" be as fast as `ordsets` for unions, intersections and
subtractions?
The good news is: **this is already true for unions**, which is equivalent
to
`maps:merge/2`. Benchmarks are available in the addendum and we can take the
following conclusions:
1. when unioning integers elements, maps and ordsets take roughly the same
time, with maps slightly ahead except in cases where we have to go from
small maps to large maps
2. when unioning tuples elements, maps are consistently faster, sometimes
2 to 4 times, except in cases where we have to go from small maps to
large
maps. This is expected, the more expensive it becomes to compare items,
the more expensive `ordsets` become
This means that, if we could implement intersection and subtraction on top
of
maps, then it will likely be more efficient than ordsets, since intersection
and subtraction do not have the issue of map resizing.
A proof of concept was written for intersections using small and mixed maps
with positive results (see benchmarks in addendum). We can also see the new
intersections are consistently faster than `cerl_sets`. Unfortunately there
are no benchmarks for intersections between two large maps due to lack of C
expertise of this EEP author. The assumption, which should be verified, is
that intersecting large maps will be faster than intersecting large
`ordsets`.
Given the results seen in `maps:merge/2` and the fact that map resizing does
not happen on intersections, this assumption will likely turn out to be
true.
Therefore, if our goal is to make `maps` as fast as `ordsets` for those
operations, we need to implement new BIFs.
Specification
=============
"maps as sets" are generally more efficient than the existing set
implementations for checking, adding and deleting elements. However,
they are slower than `ordsets` in the following operations:
* `from_list/1`
* `is_subset/2`
* `is_disjoint/2`
* `intersection/2`
* `subtract/2`
Therefore, if we want to have a *de facto* set implementation, the functions
above would have to implemented as BIFs. The first three provide only
partial
speed-ups compared to a pure Erlang implementation but the last two
operations
with provide drastic gains as NIFs. The last two operations are also the
most
complex to implement.
With the changes above, the only operations in "maps as sets" that won't be
as
fast or faster than "ordsets" is `to_list` and `fold`, since `ordsets` are
lists
internally.
Assuming the functionality above is validated as more performant (at least
for intersections and subtractions) and there is an interest in providing
said
functionality, the last question is: how should this functionality be
exposed?
Possible APIs for "maps as sets"
================================
### 1. Augment the maps module
If there is no interest in adding new module to OTP, the "maps" module could
be augmented to have set-based operations. In those cases, only the keys are
compared. The values can come from either the first or the second map.
While this approach will improve performance, the `intersection/2` and
`subtract/2`
APIs in `maps` are quite awkward. One alternative is to prefix those
operations
with the `key` prefix, such as `keyintersection`, to make it clear they are
about the intersection of keys. But perhaps a better approach altogether is
to define a separate module.
### 2. Add `mapsets` module
The `mapsets` module provide sets based on maps. The fact said sets are
based
on maps is part of the public API (i.e. they are not an opaque type),
exactly
like `ordsets`. The value for each key is the empty list to make sure sets
can
be cheapily serialized.
This new module would have 5 BIFs:
* `mapsets:from_list/1`
* `mapsets:intersection/2`
* `mapsets:is_subset/2`
* `mapsets:is_disjoint/2`
* `mapsets:subtract/2`
The remaining APIs would be implemented on top of the maps API.
### 3. Change the `sets` module
Another option, similar to the above, is to leverage the fact the `sets`
type
is opaque and replace its implementation by "maps as sets". The advantagess
of
this approach is that everyone using `sets` today would get a performance
upgrade
and we would avoid adding a new module to Erlang/OTP. After all, there is
always
a risk that by adding a fourth option that unifies all three existing
options,
we will simply end-up with four options.
The downside of this approach is that, although the `sets` datastructure is
opaque, developers may have serialized it elsewhere, and therefore the
existing
data structure must still be supported. This means we would first need to
modify
the `sets` module to support both old sets and the new "maps as sets".
Support
for the old data structure can be removed only in future versions. We would
also
need to discuss an appropriate migration path.
Next Steps
==========
At the current stage, the proposal is a draft and not fully specified. In
particular, it is necessary to validate the implementation of some
operations
and benchmark them. It is also necessary to choose a relevant API for the
propose functionality.
That said, if this proposal is viewed positively, the proposed next steps
are:
1. Validate that intersections with maps is faster than with ordsets
2. Choose the desired API for "maps as sets" (i.e. choose between 1.
extending
`maps`, 2. adding `mapsets`, or 3. changing `sets`)
3. Implement the chosen API in Erlang (most of the `cerl_sets`
implementation
can be leveraged)
4. Optimize the relevant operations as BIFs
The author of the EEP can help by implementating step 3.
Copyright
=========
This document has been placed in the public domain.
[EmacsVar]: <> "Local Variables:"
[EmacsVar]: <> "mode: indented-text"
[EmacsVar]: <> "indent-tabs-mode: nil"
[EmacsVar]: <> "sentence-end-double-space: t"
[EmacsVar]: <> "fill-column: 70"
[EmacsVar]: <> "coding: utf-8"
[EmacsVar]: <> "End:"
[VimVar]: <> " vim: set fileencoding=utf-8 expandtab shiftwidth=4
softtabstop=4: "
Addendum: Union benchmark results
=================================
### Unioning sets of integers
Operating System: macOS
CPU Information: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.9.0
Erlang 23-master
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
Estimated total run time: 8.40 min
##### With input a1 Interspersed (5) #####
Name ips average deviation median
99th %
1 maps:merge 4.18 M 239.50 ns ±13926.78% 0 ns
1000 ns
3 ordsets:union 2.73 M 365.68 ns ±8833.12% 0 ns
1000 ns
2 gb_sets:union 0.99 M 1008.99 ns ±2897.13% 1000 ns
2000 ns
Comparison:
1 maps:merge 4.18 M
3 ordsets:union 2.73 M - 1.53x slower +126.19 ns
2 gb_sets:union 0.99 M - 4.21x slower +769.49 ns
##### With input a2 Interspersed (10) #####
Name ips average deviation median
99th %
1 maps:merge 3.60 M 277.93 ns ±9122.84% 0 ns
1000 ns
3 ordsets:union 1.93 M 517.34 ns ±5920.40% 0 ns
1000 ns
2 gb_sets:union 0.62 M 1624.47 ns ±2115.84% 1000 ns
3000 ns
Comparison:
1 maps:merge 3.60 M
3 ordsets:union 1.93 M - 1.86x slower +239.41 ns
2 gb_sets:union 0.62 M - 5.84x slower +1346.54 ns
##### With input a3 Interspersed (30) #####
Name ips average deviation median
99th %
3 ordsets:union 1012.27 K 0.99 μs ±4048.88% 1 μs
2 μs
1 maps:merge 318.99 K 3.13 μs ±558.61% 3 μs
7 μs
2 gb_sets:union 270.93 K 3.69 μs ±222.80% 3 μs
12 μs
Comparison:
3 ordsets:union 1012.27 K
1 maps:merge 318.99 K - 3.17x slower +2.15 μs
2 gb_sets:union 270.93 K - 3.74x slower +2.70 μs
##### With input a4 Interspersed (50) #####
Name ips average deviation median
99th %
1 maps:merge 1149.76 K 0.87 μs ±3450.02% 1 μs
2 μs
3 ordsets:union 584.09 K 1.71 μs ±1716.00% 1 μs
4 μs
2 gb_sets:union 146.62 K 6.82 μs ±311.32% 6 μs
25 μs
Comparison:
1 maps:merge 1149.76 K
3 ordsets:union 584.09 K - 1.97x slower +0.84 μs
2 gb_sets:union 146.62 K - 7.84x slower +5.95 μs
##### With input a5 Interspersed (1000) #####
Name ips average deviation median
99th %
1 maps:merge 71.57 K 13.97 μs ±154.74% 12 μs
44 μs
3 ordsets:union 33.29 K 30.04 μs ±134.28% 25 μs
92 μs
2 gb_sets:union 8.36 K 119.56 μs ±52.83% 106 μs
255 μs
Comparison:
1 maps:merge 71.57 K
3 ordsets:union 33.29 K - 2.15x slower +16.07 μs
2 gb_sets:union 8.36 K - 8.56x slower +105.58 μs
##### With input a6 Interspersed (100000) #####
Name ips average deviation median
99th %
1 maps:merge 275.98 3.62 ms ±36.94% 2.75 ms
7.26 ms
3 ordsets:union 247.19 4.05 ms ±14.63% 4.01 ms
5.39 ms
2 gb_sets:union 43.70 22.88 ms ±28.56% 20.66 ms
44.84 ms
Comparison:
1 maps:merge 275.98
3 ordsets:union 247.19 - 1.12x slower +0.42 ms
2 gb_sets:union 43.70 - 6.32x slower +19.26 ms
##### With input b1 Half-left (5) #####
Name ips average deviation median
99th %
3 ordsets:union 5.14 M 194.71 ns ±2814.44% 0 ns
1000 ns
1 maps:merge 4.80 M 208.36 ns ±20621.17% 0 ns
1000 ns
2 gb_sets:union 1.48 M 673.48 ns ±4924.77% 1000 ns
1000 ns
Comparison:
3 ordsets:union 5.14 M
1 maps:merge 4.80 M - 1.07x slower +13.65 ns
2 gb_sets:union 1.48 M - 3.46x slower +478.77 ns
##### With input b2 Half-left (10) #####
Name ips average deviation median
99th %
1 maps:merge 4.42 M 226.29 ns ±9473.44% 0 ns
1000 ns
3 ordsets:union 3.73 M 268.01 ns ±12800.39% 0 ns
1000 ns
2 gb_sets:union 0.87 M 1144.30 ns ±2389.89% 1000 ns
2000 ns
Comparison:
1 maps:merge 4.42 M
3 ordsets:union 3.73 M - 1.18x slower +41.72 ns
2 gb_sets:union 0.87 M - 5.06x slower +918.01 ns
##### With input b3 Half-left (30) #####
Name ips average deviation median
99th %
1 maps:merge 2.64 M 378.92 ns ±12298.14% 0 ns
1000 ns
3 ordsets:union 1.70 M 589.31 ns ±7472.62% 0 ns
1000 ns
2 gb_sets:union 0.43 M 2326.42 ns ±393.28% 2000 ns
4000 ns
Comparison:
1 maps:merge 2.64 M
3 ordsets:union 1.70 M - 1.56x slower +210.39 ns
2 gb_sets:union 0.43 M - 6.14x slower +1947.49 ns
##### With input b4 Half-left (50) #####
Name ips average deviation median
99th %
3 ordsets:union 1365.15 K 0.73 μs ±3249.86% 1 μs
1 μs
1 maps:merge 587.14 K 1.70 μs ±1709.70% 1 μs
3 μs
2 gb_sets:union 254.37 K 3.93 μs ±510.57% 3 μs
16 μs
Comparison:
3 ordsets:union 1365.15 K
1 maps:merge 587.14 K - 2.33x slower +0.97 μs
2 gb_sets:union 254.37 K - 5.37x slower +3.20 μs
##### With input b5 Half-left (1000) #####
Name ips average deviation median
99th %
1 maps:merge 130.95 K 7.64 μs ±44.63% 7 μs
25 μs
3 ordsets:union 112.42 K 8.90 μs ±271.51% 8 μs
34 μs
2 gb_sets:union 14.89 K 67.17 μs ±81.58% 58 μs
167.75 μs
Comparison:
1 maps:merge 130.95 K
3 ordsets:union 112.42 K - 1.16x slower +1.26 μs
2 gb_sets:union 14.89 K - 8.80x slower +59.54 μs
##### With input b6 Half-left (100000) #####
Name ips average deviation median
99th %
1 maps:merge 736.54 1.36 ms ±13.50% 1.30 ms
2.17 ms
3 ordsets:union 424.33 2.36 ms ±20.47% 2.28 ms
3.81 ms
2 gb_sets:union 111.06 9.00 ms ±14.00% 8.64 ms
14.87 ms
Comparison:
1 maps:merge 736.54
3 ordsets:union 424.33 - 1.74x slower +1.00 ms
2 gb_sets:union 111.06 - 6.63x slower +7.65 ms
##### With input c1 Half-right (5) #####
Name ips average deviation median
99th %
3 ordsets:union 5.39 M 185.61 ns ±3347.98% 0 ns
1000 ns
1 maps:merge 4.44 M 224.99 ns ±18210.87% 0 ns
1000 ns
2 gb_sets:union 1.38 M 726.62 ns ±5484.65% 1000 ns
2000 ns
Comparison:
3 ordsets:union 5.39 M
1 maps:merge 4.44 M - 1.21x slower +39.37 ns
2 gb_sets:union 1.38 M - 3.91x slower +541.01 ns
##### With input c2 Half-right (10) #####
Name ips average deviation median
99th %
1 maps:merge 4.50 M 222.20 ns ±6200.17% 0 ns
1000 ns
3 ordsets:union 3.66 M 273.47 ns ±11368.54% 0 ns
1000 ns
2 gb_sets:union 0.91 M 1097.73 ns ±2497.65% 1000 ns
2000 ns
Comparison:
1 maps:merge 4.50 M
3 ordsets:union 3.66 M - 1.23x slower +51.26 ns
2 gb_sets:union 0.91 M - 4.94x slower +875.52 ns
##### With input c3 Half-right (30) #####
Name ips average deviation median
99th %
1 maps:merge 2.88 M 346.75 ns ±11287.26% 0 ns
1000 ns
3 ordsets:union 1.87 M 534.45 ns ±5864.66% 0 ns
1000 ns
2 gb_sets:union 0.42 M 2353.46 ns ±409.72% 2000 ns
5000 ns
Comparison:
1 maps:merge 2.88 M
3 ordsets:union 1.87 M - 1.54x slower +187.69 ns
2 gb_sets:union 0.42 M - 6.79x slower +2006.70 ns
##### With input c4 Half-right (50) #####
Name ips average deviation median
99th %
3 ordsets:union 1405.29 K 0.71 μs ±4860.25% 1 μs
2 μs
1 maps:merge 541.91 K 1.85 μs ±1461.20% 2 μs
3 μs
2 gb_sets:union 248.12 K 4.03 μs ±526.17% 3 μs
17 μs
Comparison:
3 ordsets:union 1405.29 K
1 maps:merge 541.91 K - 2.59x slower +1.13 μs
2 gb_sets:union 248.12 K - 5.66x slower +3.32 μs
##### With input c5 Half-right (1000) #####
Name ips average deviation median
99th %
3 ordsets:union 117.05 K 8.54 μs ±180.01% 8 μs
32 μs
1 maps:merge 106.28 K 9.41 μs ±706.19% 8 μs
28 μs
2 gb_sets:union 14.62 K 68.38 μs ±69.45% 59 μs
149 μs
Comparison:
3 ordsets:union 117.05 K
1 maps:merge 106.28 K - 1.10x slower +0.87 μs
2 gb_sets:union 14.62 K - 8.00x slower +59.84 μs
##### With input c6 Half-right (100000) #####
Name ips average deviation median
99th %
1 maps:merge 447.90 2.23 ms ±42.50% 1.81 ms
6.07 ms
3 ordsets:union 312.45 3.20 ms ±35.75% 2.92 ms
7.20 ms
2 gb_sets:union 110.13 9.08 ms ±14.75% 8.72 ms
16.01 ms
Comparison:
1 maps:merge 447.90
3 ordsets:union 312.45 - 1.43x slower +0.97 ms
2 gb_sets:union 110.13 - 4.07x slower +6.85 ms
##### With input d1 Equal (5) #####
Name ips average deviation median
99th %
1 maps:merge 4.03 M 248.00 ns ±13008.64% 0 ns
1000 ns
3 ordsets:union 3.41 M 293.08 ns ±11881.46% 0 ns
1000 ns
2 gb_sets:union 1.34 M 748.45 ns ±5426.61% 1000 ns
2000 ns
Comparison:
1 maps:merge 4.03 M
3 ordsets:union 3.41 M - 1.18x slower +45.08 ns
2 gb_sets:union 1.34 M - 3.02x slower +500.44 ns
##### With input d2 Equal (10) #####
Name ips average deviation median
99th %
3 ordsets:union 3.33 M 300.31 ns ±5298.85% 0 ns
1000 ns
1 maps:merge 2.81 M 355.61 ns ±14326.68% 0 ns
1000 ns
2 gb_sets:union 0.75 M 1337.84 ns ±2488.47% 1000 ns
4000 ns
Comparison:
3 ordsets:union 3.33 M
1 maps:merge 2.81 M - 1.18x slower +55.30 ns
2 gb_sets:union 0.75 M - 4.45x slower +1037.53 ns
##### With input d3 Equal (30) #####
Name ips average deviation median
99th %
1 maps:merge 2.25 M 443.46 ns ±8688.55% 0 ns
1000 ns
3 ordsets:union 1.46 M 683.82 ns ±3817.58% 1000 ns
1000 ns
2 gb_sets:union 0.37 M 2686.18 ns ±483.99% 2000 ns
9000 ns
Comparison:
1 maps:merge 2.25 M
3 ordsets:union 1.46 M - 1.54x slower +240.36 ns
2 gb_sets:union 0.37 M - 6.06x slower +2242.72 ns
##### With input d4 Equal (50) #####
Name ips average deviation median
99th %
1 maps:merge 1.50 M 668.83 ns ±132.24% 1000 ns
1000 ns
3 ordsets:union 1.04 M 960.02 ns ±4458.67% 1000 ns
2000 ns
2 gb_sets:union 0.22 M 4523.49 ns ±196.98% 4000 ns
18000 ns
Comparison:
1 maps:merge 1.50 M
3 ordsets:union 1.04 M - 1.44x slower +291.19 ns
2 gb_sets:union 0.22 M - 6.76x slower +3854.66 ns
##### With input d5 Equal (1000) #####
Name ips average deviation median
99th %
1 maps:merge 81.92 K 12.21 μs ±57.31% 11 μs
32 μs
3 ordsets:union 77.39 K 12.92 μs ±129.75% 12 μs
39 μs
2 gb_sets:union 12.72 K 78.63 μs ±43.08% 70 μs
174 μs
Comparison:
1 maps:merge 81.92 K
3 ordsets:union 77.39 K - 1.06x slower +0.71 μs
2 gb_sets:union 12.72 K - 6.44x slower +66.43 μs
##### With input d6 Equal (100000) #####
Name ips average deviation median
99th %
1 maps:merge 646.20 1.55 ms ±18.21% 1.45 ms
2.86 ms
3 ordsets:union 305.88 3.27 ms ±16.73% 3.22 ms
4.79 ms
2 gb_sets:union 96.06 10.41 ms ±18.09% 9.72 ms
17.41 ms
Comparison:
1 maps:merge 646.20
3 ordsets:union 305.88 - 2.11x slower +1.72 ms
2 gb_sets:union 96.06 - 6.73x slower +8.86 ms
### Unioning sets of tuple-integers
Operating System: macOS
CPU Information: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.9.0
Erlang 23-master
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
Estimated total run time: 8.40 min
##### With input a1 Interspersed (5) #####
Name ips average deviation median
99th %
1 maps:merge 2.93 M 341.36 ns ±2603.07% 0 ns
1000 ns
3 ordsets:union 1.62 M 616.04 ns ±4989.81% 0 ns
1000 ns
2 gb_sets:union 0.82 M 1219.38 ns ±2533.38% 1000 ns
2000 ns
Comparison:
1 maps:merge 2.93 M
3 ordsets:union 1.62 M - 1.80x slower +274.68 ns
2 gb_sets:union 0.82 M - 3.57x slower +878.02 ns
##### With input a2 Interspersed (10) #####
Name ips average deviation median
99th %
1 maps:merge 2.02 M 494.89 ns ±2798.11% 0 ns
1000 ns
3 ordsets:union 1.04 M 963.72 ns ±2195.45% 1000 ns
2000 ns
2 gb_sets:union 0.50 M 2012.64 ns ±1226.89% 2000 ns
4000 ns
Comparison:
1 maps:merge 2.02 M
3 ordsets:union 1.04 M - 1.95x slower +468.83 ns
2 gb_sets:union 0.50 M - 4.07x slower +1517.75 ns
##### With input a3 Interspersed (30) #####
Name ips average deviation median
99th %
3 ordsets:union 408.22 K 2.45 μs ±828.38% 2 μs
4 μs
1 maps:merge 234.27 K 4.27 μs ±330.95% 4 μs
10 μs
2 gb_sets:union 189.97 K 5.26 μs ±643.32% 5 μs
18 μs
Comparison:
3 ordsets:union 408.22 K
1 maps:merge 234.27 K - 1.74x slower +1.82 μs
2 gb_sets:union 189.97 K - 2.15x slower +2.81 μs
##### With input a4 Interspersed (50) #####
Name ips average deviation median
99th %
1 maps:merge 767.56 K 1.30 μs ±1279.19% 1 μs
2 μs
3 ordsets:union 246.12 K 4.06 μs ±267.03% 4 μs
14 μs
2 gb_sets:union 108.33 K 9.23 μs ±255.73% 8 μs
27 μs
Comparison:
1 maps:merge 767.56 K
3 ordsets:union 246.12 K - 3.12x slower +2.76 μs
2 gb_sets:union 108.33 K - 7.09x slower +7.93 μs
##### With input a5 Interspersed (1000) #####
Name ips average deviation median
99th %
1 maps:merge 47.61 K 21.00 μs ±196.69% 19 μs
59 μs
3 ordsets:union 12.38 K 80.76 μs ±53.12% 73 μs
193 μs
2 gb_sets:union 6.04 K 165.68 μs ±30.74% 152 μs
309 μs
Comparison:
1 maps:merge 47.61 K
3 ordsets:union 12.38 K - 3.84x slower +59.75 μs
2 gb_sets:union 6.04 K - 7.89x slower +144.67 μs
##### With input a6 Interspersed (100000) #####
Name ips average deviation median
99th %
1 maps:merge 210.63 4.75 ms ±35.35% 3.77 ms
9.58 ms
3 ordsets:union 74.84 13.36 ms ±17.83% 12.73 ms
18.51 ms
2 gb_sets:union 54.06 18.50 ms ±14.28% 17.83 ms
24.21 ms
Comparison:
1 maps:merge 210.63
3 ordsets:union 74.84 - 2.81x slower +8.61 ms
2 gb_sets:union 54.06 - 3.90x slower +13.75 ms
##### With input b1 Half-left (5) #####
Name ips average deviation median
99th %
1 maps:merge 4.49 M 222.57 ns ±1774.31% 0 ns
1000 ns
3 ordsets:union 3.33 M 300.45 ns ±6349.54% 0 ns
1000 ns
2 gb_sets:union 1.46 M 683.85 ns ±2344.50% 1000 ns
1000 ns
Comparison:
1 maps:merge 4.49 M
3 ordsets:union 3.33 M - 1.35x slower +77.88 ns
2 gb_sets:union 1.46 M - 3.07x slower +461.29 ns
##### With input b2 Half-left (10) #####
Name ips average deviation median
99th %
1 maps:merge 2.48 M 402.60 ns ±9495.69% 0 ns
1000 ns
3 ordsets:union 2.30 M 435.32 ns ±1123.50% 0 ns
1000 ns
2 gb_sets:union 0.76 M 1318.82 ns ±818.75% 1000 ns
2000 ns
Comparison:
1 maps:merge 2.48 M
3 ordsets:union 2.30 M - 1.08x slower +32.73 ns
2 gb_sets:union 0.76 M - 3.28x slower +916.23 ns
##### With input b3 Half-left (30) #####
Name ips average deviation median
99th %
1 maps:merge 1.54 M 648.33 ns ±2884.79% 0 ns
1000 ns
3 ordsets:union 1.09 M 921.12 ns ±734.80% 1000 ns
2000 ns
2 gb_sets:union 0.37 M 2728.75 ns ±554.08% 2000 ns
6000 ns
Comparison:
1 maps:merge 1.54 M
3 ordsets:union 1.09 M - 1.42x slower +272.79 ns
2 gb_sets:union 0.37 M - 4.21x slower +2080.42 ns
##### With input b4 Half-left (50) #####
Name ips average deviation median
99th %
3 ordsets:union 734.80 K 1.36 μs ±978.11% 1 μs
3 μs
1 maps:merge 439.62 K 2.27 μs ±1429.61% 2 μs
5 μs
2 gb_sets:union 224.47 K 4.45 μs ±213.29% 4 μs
15 μs
Comparison:
3 ordsets:union 734.80 K
1 maps:merge 439.62 K - 1.67x slower +0.91 μs
2 gb_sets:union 224.47 K - 3.27x slower +3.09 μs
##### With input b5 Half-left (1000) #####
Name ips average deviation median
99th %
1 maps:merge 76.01 K 13.16 μs ±104.36% 12 μs
35 μs
3 ordsets:union 45.29 K 22.08 μs ±125.57% 20 μs
60 μs
2 gb_sets:union 13.42 K 74.53 μs ±44.00% 68 μs
164 μs
Comparison:
1 maps:merge 76.01 K
3 ordsets:union 45.29 K - 1.68x slower +8.93 μs
2 gb_sets:union 13.42 K - 5.66x slower +61.37 μs
##### With input b6 Half-left (100000) #####
Name ips average deviation median
99th %
1 maps:merge 530.32 1.89 ms ±18.53% 1.77 ms
3.40 ms
3 ordsets:union 139.97 7.14 ms ±17.91% 7.01 ms
11.23 ms
2 gb_sets:union 91.51 10.93 ms ±12.31% 10.34 ms
15.62 ms
Comparison:
1 maps:merge 530.32
3 ordsets:union 139.97 - 3.79x slower +5.26 ms
2 gb_sets:union 91.51 - 5.80x slower +9.04 ms
##### With input c1 Half-right (5) #####
Name ips average deviation median
99th %
1 maps:merge 4.46 M 224.32 ns ±1730.97% 0 ns
1000 ns
3 ordsets:union 3.78 M 264.68 ns ±3293.90% 0 ns
1000 ns
2 gb_sets:union 1.52 M 658.44 ns ±1819.22% 1000 ns
1000 ns
Comparison:
1 maps:merge 4.46 M
3 ordsets:union 3.78 M - 1.18x slower +40.37 ns
2 gb_sets:union 1.52 M - 2.94x slower +434.13 ns
##### With input c2 Half-right (10) #####
Name ips average deviation median
99th %
3 ordsets:union 2.36 M 424.51 ns ±2870.39% 0 ns
1000 ns
1 maps:merge 2.27 M 441.04 ns ±11548.99% 0 ns
1000 ns
2 gb_sets:union 0.80 M 1248.21 ns ±948.08% 1000 ns
2000 ns
Comparison:
3 ordsets:union 2.36 M
1 maps:merge 2.27 M - 1.04x slower +16.53 ns
2 gb_sets:union 0.80 M - 2.94x slower +823.70 ns
##### With input c3 Half-right (30) #####
Name ips average deviation median
99th %
1 maps:merge 1.53 M 654.58 ns ±2879.82% 1000 ns
1000 ns
3 ordsets:union 1.13 M 885.52 ns ±2213.29% 1000 ns
2000 ns
2 gb_sets:union 0.37 M 2675.20 ns ±502.40% 2000 ns
5000 ns
Comparison:
1 maps:merge 1.53 M
3 ordsets:union 1.13 M - 1.35x slower +230.94 ns
2 gb_sets:union 0.37 M - 4.09x slower +2020.62 ns
##### With input c4 Half-right (50) #####
Name ips average deviation median
99th %
3 ordsets:union 747.48 K 1.34 μs ±1222.85% 1 μs
3 μs
1 maps:merge 433.42 K 2.31 μs ±1493.25% 2 μs
4 μs
2 gb_sets:union 223.83 K 4.47 μs ±283.66% 4 μs
13 μs
Comparison:
3 ordsets:union 747.48 K
1 maps:merge 433.42 K - 1.72x slower +0.97 μs
2 gb_sets:union 223.83 K - 3.34x slower +3.13 μs
##### With input c5 Half-right (1000) #####
Name ips average deviation median
99th %
1 maps:merge 66.00 K 15.15 μs ±321.69% 14 μs
41 μs
3 ordsets:union 44.62 K 22.41 μs ±767.12% 20 μs
60 μs
2 gb_sets:union 13.20 K 75.74 μs ±41.33% 70 μs
161 μs
Comparison:
1 maps:merge 66.00 K
3 ordsets:union 44.62 K - 1.48x slower +7.26 μs
2 gb_sets:union 13.20 K - 5.00x slower +60.59 μs
##### With input c6 Half-right (100000) #####
Name ips average deviation median
99th %
1 maps:merge 428.32 2.33 ms ±28.88% 2.06 ms
4.05 ms
3 ordsets:union 146.62 6.82 ms ±18.71% 6.60 ms
10.79 ms
2 gb_sets:union 91.45 10.93 ms ±13.58% 10.27 ms
15.80 ms
Comparison:
1 maps:merge 428.32
3 ordsets:union 146.62 - 2.92x slower +4.49 ms
2 gb_sets:union 91.45 - 4.68x slower +8.60 ms
##### With input d1 Equal (5) #####
Name ips average deviation median
99th %
1 maps:merge 3.61 M 276.63 ns ±3338.58% 0 ns
1000 ns
3 ordsets:union 2.42 M 414.07 ns ±3326.82% 0 ns
1000 ns
2 gb_sets:union 1.26 M 792.13 ns ±1546.56% 1000 ns
2000 ns
Comparison:
1 maps:merge 3.61 M
3 ordsets:union 2.42 M - 1.50x slower +137.45 ns
2 gb_sets:union 1.26 M - 2.86x slower +515.50 ns
##### With input d2 Equal (10) #####
Name ips average deviation median
99th %
1 maps:merge 2.15 M 464.77 ns ±8475.08% 0 ns
1000 ns
3 ordsets:union 1.88 M 531.65 ns ±493.39% 1000 ns
1000 ns
2 gb_sets:union 0.69 M 1459.20 ns ±1113.96% 1000 ns
3000 ns
Comparison:
1 maps:merge 2.15 M
3 ordsets:union 1.88 M - 1.14x slower +66.89 ns
2 gb_sets:union 0.69 M - 3.14x slower +994.43 ns
##### With input d3 Equal (30) #####
Name ips average deviation median
99th %
1 maps:merge 1364.57 K 0.73 μs ±4056.53% 1 μs
1 μs
3 ordsets:union 742.74 K 1.35 μs ±1193.06% 1 μs
2 μs
2 gb_sets:union 307.17 K 3.26 μs ±527.79% 3 μs
8 μs
Comparison:
1 maps:merge 1364.57 K
3 ordsets:union 742.74 K - 1.84x slower +0.61 μs
2 gb_sets:union 307.17 K - 4.44x slower +2.52 μs
##### With input d4 Equal (50) #####
Name ips average deviation median
99th %
1 maps:merge 816.34 K 1.22 μs ±168.59% 1 μs
2 μs
3 ordsets:union 451.06 K 2.22 μs ±1119.27% 2 μs
4 μs
2 gb_sets:union 184.50 K 5.42 μs ±200.77% 5 μs
19 μs
Comparison:
1 maps:merge 816.34 K
3 ordsets:union 451.06 K - 1.81x slower +0.99 μs
2 gb_sets:union 184.50 K - 4.42x slower +4.19 μs
##### With input d5 Equal (1000) #####
Name ips average deviation median
99th %
1 maps:merge 46.22 K 21.63 μs ±39.65% 20 μs
53 μs
3 ordsets:union 26.20 K 38.17 μs ±63.50% 35 μs
101 μs
2 gb_sets:union 10.24 K 97.66 μs ±36.11% 90 μs
199 μs
Comparison:
1 maps:merge 46.22 K
3 ordsets:union 26.20 K - 1.76x slower +16.53 μs
2 gb_sets:union 10.24 K - 4.51x slower +76.03 μs
##### With input d6 Equal (100000) #####
Name ips average deviation median
99th %
1 maps:merge 440.81 2.27 ms ±12.79% 2.17 ms
3.48 ms
3 ordsets:union 126.12 7.93 ms ±26.40% 7.11 ms
13.85 ms
2 gb_sets:union 73.86 13.54 ms ±18.78% 12.89 ms
19.27 ms
Comparison:
1 maps:merge 440.81
3 ordsets:union 126.12 - 3.50x slower +5.66 ms
2 gb_sets:union 73.86 - 5.97x slower +11.27 ms
Addendum: Intersection benchmark results
========================================
### Intersection of sets of integers
Operating System: macOS
CPU Information: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.9.0
Erlang 23-master
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
Estimated total run time: 6.53 min
##### With input a1 Interspersed (5) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 5.64 M 177.31 ns ±8960.73%
0 ns 1000 ns
3 ordsets:intersection 4.58 M 218.18 ns ±1955.05%
0 ns 1000 ns
2 gb_sets:intersection 1.85 M 541.24 ns ±3690.38%
0 ns 1000 ns
0 cerl_sets:intersection 1.81 M 551.00 ns ±6378.03%
0 ns 1000 ns
Comparison:
1 mapsets:intersection 5.64 M
3 ordsets:intersection 4.58 M - 1.23x slower +40.87 ns
2 gb_sets:intersection 1.85 M - 3.05x slower +363.93 ns
0 cerl_sets:intersection 1.81 M - 3.11x slower +373.69 ns
##### With input a2 Interspersed (10) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 3.87 M 258.37 ns ±8156.88%
0 ns 1000 ns
3 ordsets:intersection 3.25 M 307.69 ns ±995.12%
0 ns 1000 ns
0 cerl_sets:intersection 1.35 M 742.45 ns ±4916.42%
1000 ns 1000 ns
2 gb_sets:intersection 1.20 M 833.71 ns ±3535.59%
1000 ns 1000 ns
Comparison:
1 mapsets:intersection 3.87 M
3 ordsets:intersection 3.25 M - 1.19x slower +49.32 ns
0 cerl_sets:intersection 1.35 M - 2.87x slower +484.09 ns
2 gb_sets:intersection 1.20 M - 3.23x slower +575.34 ns
##### With input a3 Interspersed (30) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 2.37 M 0.42 μs ±7530.28%
0 μs 1 μs
3 ordsets:intersection 1.57 M 0.64 μs ±571.54%
1 μs 1 μs
0 cerl_sets:intersection 0.63 M 1.60 μs ±1704.57%
1 μs 3 μs
2 gb_sets:intersection 0.57 M 1.74 μs ±1508.42%
2 μs 3 μs
Comparison:
1 mapsets:intersection 2.37 M
3 ordsets:intersection 1.57 M - 1.51x slower +0.21 μs
0 cerl_sets:intersection 0.63 M - 3.79x slower +1.17 μs
2 gb_sets:intersection 0.57 M - 4.13x slower +1.32 μs
##### With input b1 Half-left (5) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 7.81 M 128.06 ns ±3031.39%
0 ns 1000 ns
3 ordsets:intersection 6.10 M 163.95 ns ±819.87%
0 ns 1000 ns
2 gb_sets:intersection 1.91 M 524.17 ns ±3574.70%
0 ns 1000 ns
0 cerl_sets:intersection 1.73 M 578.18 ns ±5060.91%
0 ns 1000 ns
Comparison:
1 mapsets:intersection 7.81 M
3 ordsets:intersection 6.10 M - 1.28x slower +35.89 ns
2 gb_sets:intersection 1.91 M - 4.09x slower +396.11 ns
0 cerl_sets:intersection 1.73 M - 4.51x slower +450.12 ns
##### With input b2 Half-left (10) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 5.34 M 187.35 ns ±6435.27%
0 ns 1000 ns
3 ordsets:intersection 3.50 M 285.53 ns ±8907.47%
0 ns 1000 ns
0 cerl_sets:intersection 1.25 M 801.68 ns ±2618.59%
1000 ns 1000 ns
2 gb_sets:intersection 1.15 M 865.97 ns ±3771.19%
1000 ns 1000 ns
Comparison:
1 mapsets:intersection 5.34 M
3 ordsets:intersection 3.50 M - 1.52x slower +98.18 ns
0 cerl_sets:intersection 1.25 M - 4.28x slower +614.33 ns
2 gb_sets:intersection 1.15 M - 4.62x slower +678.63 ns
##### With input b3 Half-left (30) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 3.12 M 0.32 μs ±10505.28%
0 μs 1 μs
3 ordsets:intersection 1.79 M 0.56 μs ±5943.47%
0 μs 1 μs
0 cerl_sets:intersection 0.60 M 1.66 μs ±1650.01%
1 μs 3 μs
2 gb_sets:intersection 0.57 M 1.77 μs ±1510.44%
2 μs 3 μs
Comparison:
1 mapsets:intersection 3.12 M
3 ordsets:intersection 1.79 M - 1.74x slower +0.24 μs
0 cerl_sets:intersection 0.60 M - 5.17x slower +1.34 μs
2 gb_sets:intersection 0.57 M - 5.51x slower +1.45 μs
##### With input b4 Half-left (50) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 1.41 M 0.71 μs ±4451.88%
1 μs 1 μs
3 ordsets:intersection 1.32 M 0.76 μs ±4422.37%
1 μs 1 μs
2 gb_sets:intersection 0.37 M 2.72 μs ±719.29%
2 μs 5 μs
0 cerl_sets:intersection 0.31 M 3.26 μs ±464.70%
3 μs 5 μs
Comparison:
1 mapsets:intersection 1.41 M
3 ordsets:intersection 1.32 M - 1.07x slower +0.0487 μs
2 gb_sets:intersection 0.37 M - 3.82x slower +2.01 μs
0 cerl_sets:intersection 0.31 M - 4.59x slower +2.55 μs
##### With input c1 Halt-right (5) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 8.50 M 117.64 ns ±3751.50%
0 ns 1000 ns
3 ordsets:intersection 4.96 M 201.70 ns ±1008.33%
0 ns 1000 ns
0 cerl_sets:intersection 2.66 M 375.86 ns ±7893.27%
0 ns 1000 ns
2 gb_sets:intersection 1.99 M 501.60 ns ±5740.59%
0 ns 1000 ns
Comparison:
1 mapsets:intersection 8.50 M
3 ordsets:intersection 4.96 M - 1.71x slower +84.06 ns
0 cerl_sets:intersection 2.66 M - 3.20x slower +258.22 ns
2 gb_sets:intersection 1.99 M - 4.26x slower +383.96 ns
##### With input c2 Halt-right (10) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 5.61 M 178.32 ns ±6353.45%
0 ns 1000 ns
3 ordsets:intersection 3.27 M 305.53 ns ±8831.03%
0 ns 1000 ns
0 cerl_sets:intersection 1.61 M 619.53 ns ±5512.50%
0 ns 1000 ns
2 gb_sets:intersection 1.20 M 830.39 ns ±3587.38%
1000 ns 1000 ns
Comparison:
1 mapsets:intersection 5.61 M
3 ordsets:intersection 3.27 M - 1.71x slower +127.21 ns
0 cerl_sets:intersection 1.61 M - 3.47x slower +441.21 ns
2 gb_sets:intersection 1.20 M - 4.66x slower +652.07 ns
##### With input c3 Halt-right (30) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 3.02 M 0.33 μs ±10877.75%
0 μs 1 μs
3 ordsets:intersection 1.76 M 0.57 μs ±6736.07%
0 μs 1 μs
0 cerl_sets:intersection 0.83 M 1.20 μs ±2066.14%
1 μs 2 μs
2 gb_sets:intersection 0.56 M 1.80 μs ±1442.53%
2 μs 3 μs
Comparison:
1 mapsets:intersection 3.02 M
3 ordsets:intersection 1.76 M - 1.71x slower +0.24 μs
0 cerl_sets:intersection 0.83 M - 3.61x slower +0.87 μs
2 gb_sets:intersection 0.56 M - 5.41x slower +1.46 μs
##### With input c4 Half-right (50) #####
Name ips average deviation
median 99th %
3 ordsets:intersection 1.42 M 0.70 μs ±4101.38%
1 μs 1 μs
1 mapsets:intersection 1.31 M 0.77 μs ±5155.14%
1 μs 1 μs
0 cerl_sets:intersection 0.48 M 2.07 μs ±1105.13%
2 μs 3 μs
2 gb_sets:intersection 0.37 M 2.69 μs ±793.20%
2 μs 5 μs
Comparison:
3 ordsets:intersection 1.42 M
1 mapsets:intersection 1.31 M - 1.09x slower +0.0618 μs
0 cerl_sets:intersection 0.48 M - 2.95x slower +1.37 μs
2 gb_sets:intersection 0.37 M - 3.82x slower +1.98 μs
##### With input d1 Equal (5) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 4.61 M 216.84 ns ±4985.98%
0 ns 1000 ns
3 ordsets:intersection 3.44 M 290.38 ns ±9494.06%
0 ns 1000 ns
0 cerl_sets:intersection 1.62 M 618.37 ns ±5703.54%
0 ns 1000 ns
2 gb_sets:intersection 1.48 M 677.41 ns ±4388.76%
1000 ns 1000 ns
Comparison:
1 mapsets:intersection 4.61 M
3 ordsets:intersection 3.44 M - 1.34x slower +73.54 ns
0 cerl_sets:intersection 1.62 M - 2.85x slower +401.53 ns
2 gb_sets:intersection 1.48 M - 3.12x slower +460.57 ns
##### With input d2 Equal (10) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 3.96 M 252.22 ns ±10397.76%
0 ns 1000 ns
3 ordsets:intersection 2.95 M 338.84 ns ±8900.72%
0 ns 1000 ns
0 cerl_sets:intersection 1.16 M 862.62 ns ±3981.08%
1000 ns 1000 ns
2 gb_sets:intersection 0.90 M 1112.16 ns ±2553.42%
1000 ns 2000 ns
Comparison:
1 mapsets:intersection 3.96 M
3 ordsets:intersection 2.95 M - 1.34x slower +86.61 ns
0 cerl_sets:intersection 1.16 M - 3.42x slower +610.40 ns
2 gb_sets:intersection 0.90 M - 4.41x slower +859.94 ns
##### With input d3 Equal (30) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 2.31 M 0.43 μs ±8998.97%
0 μs 1 μs
3 ordsets:intersection 1.49 M 0.67 μs ±3628.66%
1 μs 1 μs
0 cerl_sets:intersection 0.52 M 1.94 μs ±965.82%
2 μs 3 μs
2 gb_sets:intersection 0.42 M 2.38 μs ±878.07%
2 μs 4 μs
Comparison:
1 mapsets:intersection 2.31 M
3 ordsets:intersection 1.49 M - 1.55x slower +0.24 μs
0 cerl_sets:intersection 0.52 M - 4.48x slower +1.51 μs
2 gb_sets:intersection 0.42 M - 5.50x slower +1.95 μs
### Unioning sets of tuple-integers
Operating System: macOS
CPU Information: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.9.0
Erlang 23-master
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
Estimated total run time: 4.90 min
##### With input a1 Interspersed (5) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 2.53 M 394.70 ns ±7692.39%
0 ns 1000 ns
3 ordsets:intersection 2.12 M 471.60 ns ±1021.75%
0 ns 1000 ns
2 gb_sets:intersection 1.30 M 768.44 ns ±2657.04%
1000 ns 1000 ns
Comparison:
1 mapsets:intersection 2.53 M
3 ordsets:intersection 2.12 M - 1.19x slower +76.90 ns
2 gb_sets:intersection 1.30 M - 1.95x slower +373.75 ns
##### With input a2 Interspersed (10) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 1.96 M 510.95 ns ±2509.15%
0 ns 1000 ns
3 ordsets:intersection 1.30 M 770.06 ns ±676.65%
1000 ns 1000 ns
2 gb_sets:intersection 0.81 M 1240.22 ns ±1388.14%
1000 ns 2000 ns
Comparison:
1 mapsets:intersection 1.96 M
3 ordsets:intersection 1.30 M - 1.51x slower +259.11 ns
2 gb_sets:intersection 0.81 M - 2.43x slower +729.27 ns
##### With input a3 Interspersed (30) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 845.89 K 1.18 μs ±2713.20%
1 μs 2 μs
3 ordsets:intersection 495.26 K 2.02 μs ±164.49%
2 μs 3 μs
2 gb_sets:intersection 324.61 K 3.08 μs ±718.13%
3 μs 5 μs
Comparison:
1 mapsets:intersection 845.89 K
3 ordsets:intersection 495.26 K - 1.71x slower +0.84 μs
2 gb_sets:intersection 324.61 K - 2.61x slower +1.90 μs
##### With input b1 Half-left (5) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 4.66 M 214.57 ns ±1896.59%
0 ns 1000 ns
3 ordsets:intersection 3.62 M 276.50 ns ±1465.48%
0 ns 1000 ns
2 gb_sets:intersection 1.73 M 577.07 ns ±5041.95%
0 ns 1000 ns
Comparison:
1 mapsets:intersection 4.66 M
3 ordsets:intersection 3.62 M - 1.29x slower +61.94 ns
2 gb_sets:intersection 1.73 M - 2.69x slower +362.51 ns
##### With input b2 Half-left (10) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 2.92 M 342.24 ns ±9961.99%
0 ns 1000 ns
3 ordsets:intersection 2.09 M 478.76 ns ±5507.02%
0 ns 1000 ns
2 gb_sets:intersection 0.96 M 1043.40 ns ±2396.75%
1000 ns 2000 ns
Comparison:
1 mapsets:intersection 2.92 M
3 ordsets:intersection 2.09 M - 1.40x slower +136.53 ns
2 gb_sets:intersection 0.96 M - 3.05x slower +701.17 ns
##### With input b3 Half-left (30) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 1.72 M 580.48 ns ±4998.64%
0 ns 1000 ns
3 ordsets:intersection 1.01 M 989.96 ns ±2850.03%
1000 ns 2000 ns
2 gb_sets:intersection 0.44 M 2292.44 ns ±981.37%
2000 ns 4000 ns
Comparison:
1 mapsets:intersection 1.72 M
3 ordsets:intersection 1.01 M - 1.71x slower +409.48 ns
2 gb_sets:intersection 0.44 M - 3.95x slower +1711.96 ns
##### With input b4 Half-left (50) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 902.32 K 1.11 μs ±1892.28%
1 μs 2 μs
3 ordsets:intersection 710.61 K 1.41 μs ±1793.08%
1 μs 2 μs
2 gb_sets:intersection 282.62 K 3.54 μs ±495.73%
3 μs 11 μs
Comparison:
1 mapsets:intersection 902.32 K
3 ordsets:intersection 710.61 K - 1.27x slower +0.30 μs
2 gb_sets:intersection 282.62 K - 3.19x slower +2.43 μs
##### With input c1 Halt-right (5) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 4.70 M 212.66 ns ±1573.58%
0 ns 1000 ns
3 ordsets:intersection 3.77 M 265.19 ns ±1597.40%
0 ns 1000 ns
2 gb_sets:intersection 1.76 M 567.11 ns ±4249.42%
0 ns 1000 ns
Comparison:
1 mapsets:intersection 4.70 M
3 ordsets:intersection 3.77 M - 1.25x slower +52.53 ns
2 gb_sets:intersection 1.76 M - 2.67x slower +354.45 ns
##### With input c2 Halt-right (10) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 3.14 M 318.35 ns ±7626.82%
0 ns 1000 ns
3 ordsets:intersection 2.23 M 449.20 ns ±5268.98%
0 ns 1000 ns
2 gb_sets:intersection 0.99 M 1014.32 ns ±2177.84%
1000 ns 2000 ns
Comparison:
1 mapsets:intersection 3.14 M
3 ordsets:intersection 2.23 M - 1.41x slower +130.85 ns
2 gb_sets:intersection 0.99 M - 3.19x slower +695.97 ns
##### With input c3 Halt-right (30) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 1.78 M 560.38 ns ±5118.91%
0 ns 1000 ns
3 ordsets:intersection 1.01 M 989.13 ns ±2292.17%
1000 ns 2000 ns
2 gb_sets:intersection 0.44 M 2294.68 ns ±981.21%
2000 ns 4000 ns
Comparison:
1 mapsets:intersection 1.78 M
3 ordsets:intersection 1.01 M - 1.77x slower +428.75 ns
2 gb_sets:intersection 0.44 M - 4.09x slower +1734.30 ns
##### With input c4 Half-right (50) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 875.40 K 1.14 μs ±1770.92%
1 μs 2 μs
3 ordsets:intersection 703.96 K 1.42 μs ±1911.40%
1 μs 3 μs
2 gb_sets:intersection 294.25 K 3.40 μs ±488.43%
3 μs 6 μs
Comparison:
1 mapsets:intersection 875.40 K
3 ordsets:intersection 703.96 K - 1.24x slower +0.28 μs
2 gb_sets:intersection 294.25 K - 2.98x slower +2.26 μs
##### With input d1 Equal (5) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 3.29 M 303.69 ns ±9348.28%
0 ns 1000 ns
3 ordsets:intersection 2.19 M 455.98 ns ±5799.97%
0 ns 1000 ns
2 gb_sets:intersection 1.15 M 869.11 ns ±3884.46%
1000 ns 2000 ns
Comparison:
1 mapsets:intersection 3.29 M
3 ordsets:intersection 2.19 M - 1.50x slower +152.29 ns
2 gb_sets:intersection 1.15 M - 2.86x slower +565.41 ns
##### With input d2 Equal (10) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 2.93 M 341.11 ns ±3839.65%
0 ns 1000 ns
3 ordsets:intersection 1.85 M 540.08 ns ±2436.90%
0 ns 1000 ns
2 gb_sets:intersection 0.72 M 1388.21 ns ±1540.59%
1000 ns 2000 ns
Comparison:
1 mapsets:intersection 2.93 M
3 ordsets:intersection 1.85 M - 1.58x slower +198.97 ns
2 gb_sets:intersection 0.72 M - 4.07x slower +1047.11 ns
##### With input d3 Equal (30) #####
Name ips average deviation
median 99th %
1 mapsets:intersection 1395.63 K 0.72 μs ±4359.84%
1 μs 1 μs
3 ordsets:intersection 744.64 K 1.34 μs ±1845.56%
1 μs 2 μs
2 gb_sets:intersection 302.52 K 3.31 μs ±672.80%
3 μs 10 μs
Comparison:
1 mapsets:intersection 1395.63 K
3 ordsets:intersection 744.64 K - 1.87x slower +0.63 μs
2 gb_sets:intersection 302.52 K - 4.61x slower +2.59 μs
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/eeps/attachments/20190918/5136b254/attachment.htm>
More information about the eeps
mailing list