Author:
José Valim <jose(dot)valim(at)gmail(dot)com>
Status:
Final/24.0 Implemented in OTP version 24.0
Type:
Standards Track
Created:
18-Sep-2019

EEP 50: 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 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.

Implementation steps #

The implementation shall be done in three steps:

  1. Update the sets module to support a version flag that returns “maps as sets”

  2. Remove cerl_sets from Erlang/OTP

  3. Optimize the relevant operations as BIFs

Copyright #

This document has been placed in the public domain.

[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