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.
In order to efficiently use sets in Erlang/OTP today, one has to consider three different options:
ordsetsgb_setscerl_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.
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:
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
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.
“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/1is_subset/2is_disjoint/2intersection/2subtract/2Therefore, 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?
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.
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/1mapsets:intersection/2mapsets:is_subset/2mapsets:is_disjoint/2mapsets:subtract/2The remaining APIs would be implemented on top of the maps API.
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
advantages 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.
This option is the one preferred by Erlang/OTP’s technical board. The
sets module will have two new functions sets:new/1 and sets:from_list/2
which accepts a version option. If {version, 2} is given, sets as
maps will be created. The remaining API in the sets module is made to
work with both new and old sets. Version 2 will become the default on
Erlang/OTP 26.
The implementation shall be done in three steps:
Update the sets module to support a version flag that returns
“maps as sets”
Remove cerl_sets from Erlang/OTP
Optimize the relevant operations as BIFs
This document has been placed in the public domain.
[VimVar]: <> “ vim: set fileencoding=utf-8 expandtab shiftwidth=4 softtabstop=4: “
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
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
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
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