[eeps] EEP ???: Maps based set implementation

José Valim jose.valim@REDACTED
Wed Sep 18 17:22:06 CEST 2019


    Author: José Valim <jose(dot)valim(at)gmail(dot)com>
    Status: Draft
    Type: Standards Track
    Created: 18-Sep-2019
    Post-History:
****
EEP ???: Maps based set implementation
----

Abstract
========

This EEP proposes a maps-based set implementation and a group of BIFs
with the goal of providing a *de facto* sets implementation in Erlang/OTP.

Motivation
==========

In order to efficiently use sets in Erlang/OTP today, one has to
consider three different options:

  * `ordsets`
  * `gb_sets`
  * using maps as sets (such as `cerl_sets`)

For example, if you wish to perform unions/intersections/subtractions,
`ordsets` is generally the most efficient. For individual lookups,
`gb_sets` and "maps as sets" are preferred, although the latter has no
official API in Erlang/OTP. If you need a mixed profile, the best choice
becomes blurrier. Note there is also a `sets` module, but it is rarely a
viable option.

The current landscape with sets is not much different than the dictionary
landscape before Erlang/OTP 17. Luckily, once `maps` were added, `maps`
became the *de facto* dictionary in Erlang. The other dictionary-like
modules
may perform better under limited occasions but `maps` provide the best
profile in many scenarios and are a reasonable starting point (until a
need for benchmarking and profiling arises - if it ever arises).

The goal of this EEP is to propose a map-based sets solution with a group
of BIFs that will give developers a sets implementation that can be
generally
treated as the main set implementation in Erlang/OTP.

Rationale
=========

Dictionaries and sets implementation tend to walk side-by-side. Such as
`ordsets` and `orddict`, `gb_trees` and `gb_sets`. That's because you can
consider elements in a set to be keys in a dictionary, where you don't care
about the value for the keys.

Given we have dictionaries implemented as maps, could we have sets based
on maps? The answer is yes and there are two approaches. The first approach
is to provide a native data structure, implemented in C, with its own
syntax.
The advantage of said approach would be lower memory usage, but it has a
large
impact on the language and on the runtime. Therefore that's not the approach
we will pursue here.

The second approach, which this EEP advocates for, is to implement `sets`
on top of maps, as done by `cerl_sets`. In this scenario, the sets elements
are keys in the map and the values are empty lists (we chose empty lists
because they are very cheap to serialize).

Using "maps as sets" provide good performance characteristics today for
inserting, adding and deleting set elements, being faster than all other
implementations. However, in terms of memory usage, "maps as sets" use
almost two times more memory than `ordsets` (although note that the set
operations themselves may end-up using less memory). Compared to `gb_sets`,
"maps as sets" use less memory altogether.

But can "maps as sets" be as fast as `ordsets` for unions, intersections and
subtractions?

The good news is: **this is already true for unions**, which is equivalent
to
`maps:merge/2`. Benchmarks are available in the addendum and we can take the
following conclusions:

  1. when unioning integers elements, maps and ordsets take roughly the same
    time, with maps slightly ahead except in cases where we have to go from
    small maps to large maps

  2. when unioning tuples elements, maps are consistently faster, sometimes
    2 to 4 times, except in cases where we have to go from small maps to
large
    maps. This is expected, the more expensive it becomes to compare items,
    the more expensive `ordsets` become

This means that, if we could implement intersection and subtraction on top
of
maps, then it will likely be more efficient than ordsets, since intersection
and subtraction do not have the issue of map resizing.

A proof of concept was written for intersections using small and mixed maps
with positive results (see benchmarks in addendum). We can also see the new
intersections are consistently faster than `cerl_sets`. Unfortunately there
are no benchmarks for intersections between two large maps due to lack of C
expertise of this EEP author. The assumption, which should be verified, is
that intersecting large maps will be faster than intersecting large
`ordsets`.
Given the results seen in `maps:merge/2` and the fact that map resizing does
not happen on intersections, this assumption will likely turn out to be
true.

Therefore, if our goal is to make `maps` as fast as `ordsets` for those
operations, we need to implement new BIFs.

Specification
=============

"maps as sets" are generally more efficient than the existing set
implementations for checking, adding and deleting elements. However,
they are slower than `ordsets` in the following operations:

  * `from_list/1`
  * `is_subset/2`
  * `is_disjoint/2`
  * `intersection/2`
  * `subtract/2`

Therefore, if we want to have a *de facto* set implementation, the functions
above would have to implemented as BIFs. The first three provide only
partial
speed-ups compared to a pure Erlang implementation but the last two
operations
with provide drastic gains as NIFs. The last two operations are also the
most
complex to implement.

With the changes above, the only operations in "maps as sets" that won't be
as
fast or faster than "ordsets" is `to_list` and `fold`, since `ordsets` are
lists
internally.

Assuming the functionality above is validated as more performant (at least
for intersections and subtractions) and there is an interest in providing
said
functionality, the last question is: how should this functionality be
exposed?

Possible APIs for "maps as sets"
================================

### 1. Augment the maps module

If there is no interest in adding new module to OTP, the "maps" module could
be augmented to have set-based operations. In those cases, only the keys are
compared. The values can come from either the first or the second map.

While this approach will improve performance, the `intersection/2` and
`subtract/2`
APIs in `maps` are quite awkward. One alternative is to prefix those
operations
with the `key` prefix, such as `keyintersection`, to make it clear they are
about the intersection of keys. But perhaps a better approach altogether is
to define a separate module.

### 2. Add `mapsets` module

The `mapsets` module provide sets based on maps. The fact said sets are
based
on maps is part of the public API (i.e. they are not an opaque type),
exactly
like `ordsets`. The value for each key is the empty list to make sure sets
can
be cheapily serialized.

This new module would have 5 BIFs:

  * `mapsets:from_list/1`
  * `mapsets:intersection/2`
  * `mapsets:is_subset/2`
  * `mapsets:is_disjoint/2`
  * `mapsets:subtract/2`

The remaining APIs would be implemented on top of the maps API.

### 3. Change the `sets` module

Another option, similar to the above, is to leverage the fact the `sets`
type
is opaque and replace its implementation by "maps as sets". The advantagess
of
this approach is that everyone using `sets` today would get a performance
upgrade
and we would avoid adding a new module to Erlang/OTP. After all, there is
always
a risk that by adding a fourth option that unifies all three existing
options,
we will simply end-up with four options.

The downside of this approach is that, although the `sets` datastructure is
opaque, developers may have serialized it elsewhere, and therefore the
existing
data structure must still be supported. This means we would first need to
modify
the `sets` module to support both old sets and the new "maps as sets".
Support
for the old data structure can be removed only in future versions. We would
also
need to discuss an appropriate migration path.

Next Steps
==========

At the current stage, the proposal is a draft and not fully specified. In
particular, it is necessary to validate the implementation of some
operations
and benchmark them. It is also necessary to choose a relevant API for the
propose functionality.

That said, if this proposal is viewed positively, the proposed next steps
are:

  1. Validate that intersections with maps is faster than with ordsets

  2. Choose the desired API for "maps as sets" (i.e. choose between 1.
extending
     `maps`, 2. adding `mapsets`, or 3. changing `sets`)

  3. Implement the chosen API in Erlang (most of the `cerl_sets`
implementation
     can be leveraged)

  4. Optimize the relevant operations as BIFs

The author of the EEP can help by implementating step 3.

Copyright
=========

This document has been placed in the public domain.

[EmacsVar]: <> "Local Variables:"
[EmacsVar]: <> "mode: indented-text"
[EmacsVar]: <> "indent-tabs-mode: nil"
[EmacsVar]: <> "sentence-end-double-space: t"
[EmacsVar]: <> "fill-column: 70"
[EmacsVar]: <> "coding: utf-8"
[EmacsVar]: <> "End:"
[VimVar]: <> " vim: set fileencoding=utf-8 expandtab shiftwidth=4
softtabstop=4: "


Addendum: Union benchmark results
=================================

### Unioning sets of integers

    Operating System: macOS
    CPU Information: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
    Number of Available Cores: 8
    Available memory: 16 GB
    Elixir 1.9.0
    Erlang 23-master

    Benchmark suite executing with the following configuration:
    warmup: 2 s
    time: 5 s
    memory time: 0 ns
    parallel: 1
    Estimated total run time: 8.40 min

    ##### With input a1 Interspersed (5) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           4.18 M      239.50 ns ±13926.78%           0 ns
       1000 ns
    3 ordsets:union        2.73 M      365.68 ns  ±8833.12%           0 ns
       1000 ns
    2 gb_sets:union        0.99 M     1008.99 ns  ±2897.13%        1000 ns
       2000 ns

    Comparison:
    1 maps:merge           4.18 M
    3 ordsets:union        2.73 M - 1.53x slower +126.19 ns
    2 gb_sets:union        0.99 M - 4.21x slower +769.49 ns

    ##### With input a2 Interspersed (10) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           3.60 M      277.93 ns  ±9122.84%           0 ns
       1000 ns
    3 ordsets:union        1.93 M      517.34 ns  ±5920.40%           0 ns
       1000 ns
    2 gb_sets:union        0.62 M     1624.47 ns  ±2115.84%        1000 ns
       3000 ns

    Comparison:
    1 maps:merge           3.60 M
    3 ordsets:union        1.93 M - 1.86x slower +239.41 ns
    2 gb_sets:union        0.62 M - 5.84x slower +1346.54 ns

    ##### With input a3 Interspersed (30) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union     1012.27 K        0.99 μs  ±4048.88%           1 μs
          2 μs
    1 maps:merge         318.99 K        3.13 μs   ±558.61%           3 μs
          7 μs
    2 gb_sets:union      270.93 K        3.69 μs   ±222.80%           3 μs
         12 μs

    Comparison:
    3 ordsets:union     1012.27 K
    1 maps:merge         318.99 K - 3.17x slower +2.15 μs
    2 gb_sets:union      270.93 K - 3.74x slower +2.70 μs

    ##### With input a4 Interspersed (50) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge        1149.76 K        0.87 μs  ±3450.02%           1 μs
          2 μs
    3 ordsets:union      584.09 K        1.71 μs  ±1716.00%           1 μs
          4 μs
    2 gb_sets:union      146.62 K        6.82 μs   ±311.32%           6 μs
         25 μs

    Comparison:
    1 maps:merge        1149.76 K
    3 ordsets:union      584.09 K - 1.97x slower +0.84 μs
    2 gb_sets:union      146.62 K - 7.84x slower +5.95 μs

    ##### With input a5 Interspersed (1000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge          71.57 K       13.97 μs   ±154.74%          12 μs
         44 μs
    3 ordsets:union       33.29 K       30.04 μs   ±134.28%          25 μs
         92 μs
    2 gb_sets:union        8.36 K      119.56 μs    ±52.83%         106 μs
        255 μs

    Comparison:
    1 maps:merge          71.57 K
    3 ordsets:union       33.29 K - 2.15x slower +16.07 μs
    2 gb_sets:union        8.36 K - 8.56x slower +105.58 μs

    ##### With input a6 Interspersed (100000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           275.98        3.62 ms    ±36.94%        2.75 ms
       7.26 ms
    3 ordsets:union        247.19        4.05 ms    ±14.63%        4.01 ms
       5.39 ms
    2 gb_sets:union         43.70       22.88 ms    ±28.56%       20.66 ms
      44.84 ms

    Comparison:
    1 maps:merge           275.98
    3 ordsets:union        247.19 - 1.12x slower +0.42 ms
    2 gb_sets:union         43.70 - 6.32x slower +19.26 ms

    ##### With input b1 Half-left (5) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union        5.14 M      194.71 ns  ±2814.44%           0 ns
       1000 ns
    1 maps:merge           4.80 M      208.36 ns ±20621.17%           0 ns
       1000 ns
    2 gb_sets:union        1.48 M      673.48 ns  ±4924.77%        1000 ns
       1000 ns

    Comparison:
    3 ordsets:union        5.14 M
    1 maps:merge           4.80 M - 1.07x slower +13.65 ns
    2 gb_sets:union        1.48 M - 3.46x slower +478.77 ns

    ##### With input b2 Half-left (10) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           4.42 M      226.29 ns  ±9473.44%           0 ns
       1000 ns
    3 ordsets:union        3.73 M      268.01 ns ±12800.39%           0 ns
       1000 ns
    2 gb_sets:union        0.87 M     1144.30 ns  ±2389.89%        1000 ns
       2000 ns

    Comparison:
    1 maps:merge           4.42 M
    3 ordsets:union        3.73 M - 1.18x slower +41.72 ns
    2 gb_sets:union        0.87 M - 5.06x slower +918.01 ns

    ##### With input b3 Half-left (30) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           2.64 M      378.92 ns ±12298.14%           0 ns
       1000 ns
    3 ordsets:union        1.70 M      589.31 ns  ±7472.62%           0 ns
       1000 ns
    2 gb_sets:union        0.43 M     2326.42 ns   ±393.28%        2000 ns
       4000 ns

    Comparison:
    1 maps:merge           2.64 M
    3 ordsets:union        1.70 M - 1.56x slower +210.39 ns
    2 gb_sets:union        0.43 M - 6.14x slower +1947.49 ns

    ##### With input b4 Half-left (50) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union     1365.15 K        0.73 μs  ±3249.86%           1 μs
          1 μs
    1 maps:merge         587.14 K        1.70 μs  ±1709.70%           1 μs
          3 μs
    2 gb_sets:union      254.37 K        3.93 μs   ±510.57%           3 μs
         16 μs

    Comparison:
    3 ordsets:union     1365.15 K
    1 maps:merge         587.14 K - 2.33x slower +0.97 μs
    2 gb_sets:union      254.37 K - 5.37x slower +3.20 μs

    ##### With input b5 Half-left (1000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge         130.95 K        7.64 μs    ±44.63%           7 μs
         25 μs
    3 ordsets:union      112.42 K        8.90 μs   ±271.51%           8 μs
         34 μs
    2 gb_sets:union       14.89 K       67.17 μs    ±81.58%          58 μs
     167.75 μs

    Comparison:
    1 maps:merge         130.95 K
    3 ordsets:union      112.42 K - 1.16x slower +1.26 μs
    2 gb_sets:union       14.89 K - 8.80x slower +59.54 μs

    ##### With input b6 Half-left (100000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           736.54        1.36 ms    ±13.50%        1.30 ms
       2.17 ms
    3 ordsets:union        424.33        2.36 ms    ±20.47%        2.28 ms
       3.81 ms
    2 gb_sets:union        111.06        9.00 ms    ±14.00%        8.64 ms
      14.87 ms

    Comparison:
    1 maps:merge           736.54
    3 ordsets:union        424.33 - 1.74x slower +1.00 ms
    2 gb_sets:union        111.06 - 6.63x slower +7.65 ms

    ##### With input c1 Half-right (5) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union        5.39 M      185.61 ns  ±3347.98%           0 ns
       1000 ns
    1 maps:merge           4.44 M      224.99 ns ±18210.87%           0 ns
       1000 ns
    2 gb_sets:union        1.38 M      726.62 ns  ±5484.65%        1000 ns
       2000 ns

    Comparison:
    3 ordsets:union        5.39 M
    1 maps:merge           4.44 M - 1.21x slower +39.37 ns
    2 gb_sets:union        1.38 M - 3.91x slower +541.01 ns

    ##### With input c2 Half-right (10) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           4.50 M      222.20 ns  ±6200.17%           0 ns
       1000 ns
    3 ordsets:union        3.66 M      273.47 ns ±11368.54%           0 ns
       1000 ns
    2 gb_sets:union        0.91 M     1097.73 ns  ±2497.65%        1000 ns
       2000 ns

    Comparison:
    1 maps:merge           4.50 M
    3 ordsets:union        3.66 M - 1.23x slower +51.26 ns
    2 gb_sets:union        0.91 M - 4.94x slower +875.52 ns

    ##### With input c3 Half-right (30) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           2.88 M      346.75 ns ±11287.26%           0 ns
       1000 ns
    3 ordsets:union        1.87 M      534.45 ns  ±5864.66%           0 ns
       1000 ns
    2 gb_sets:union        0.42 M     2353.46 ns   ±409.72%        2000 ns
       5000 ns

    Comparison:
    1 maps:merge           2.88 M
    3 ordsets:union        1.87 M - 1.54x slower +187.69 ns
    2 gb_sets:union        0.42 M - 6.79x slower +2006.70 ns

    ##### With input c4 Half-right (50) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union     1405.29 K        0.71 μs  ±4860.25%           1 μs
          2 μs
    1 maps:merge         541.91 K        1.85 μs  ±1461.20%           2 μs
          3 μs
    2 gb_sets:union      248.12 K        4.03 μs   ±526.17%           3 μs
         17 μs

    Comparison:
    3 ordsets:union     1405.29 K
    1 maps:merge         541.91 K - 2.59x slower +1.13 μs
    2 gb_sets:union      248.12 K - 5.66x slower +3.32 μs

    ##### With input c5 Half-right (1000) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union      117.05 K        8.54 μs   ±180.01%           8 μs
         32 μs
    1 maps:merge         106.28 K        9.41 μs   ±706.19%           8 μs
         28 μs
    2 gb_sets:union       14.62 K       68.38 μs    ±69.45%          59 μs
        149 μs

    Comparison:
    3 ordsets:union      117.05 K
    1 maps:merge         106.28 K - 1.10x slower +0.87 μs
    2 gb_sets:union       14.62 K - 8.00x slower +59.84 μs

    ##### With input c6 Half-right (100000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           447.90        2.23 ms    ±42.50%        1.81 ms
       6.07 ms
    3 ordsets:union        312.45        3.20 ms    ±35.75%        2.92 ms
       7.20 ms
    2 gb_sets:union        110.13        9.08 ms    ±14.75%        8.72 ms
      16.01 ms

    Comparison:
    1 maps:merge           447.90
    3 ordsets:union        312.45 - 1.43x slower +0.97 ms
    2 gb_sets:union        110.13 - 4.07x slower +6.85 ms

    ##### With input d1 Equal (5) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           4.03 M      248.00 ns ±13008.64%           0 ns
       1000 ns
    3 ordsets:union        3.41 M      293.08 ns ±11881.46%           0 ns
       1000 ns
    2 gb_sets:union        1.34 M      748.45 ns  ±5426.61%        1000 ns
       2000 ns

    Comparison:
    1 maps:merge           4.03 M
    3 ordsets:union        3.41 M - 1.18x slower +45.08 ns
    2 gb_sets:union        1.34 M - 3.02x slower +500.44 ns

    ##### With input d2 Equal (10) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union        3.33 M      300.31 ns  ±5298.85%           0 ns
       1000 ns
    1 maps:merge           2.81 M      355.61 ns ±14326.68%           0 ns
       1000 ns
    2 gb_sets:union        0.75 M     1337.84 ns  ±2488.47%        1000 ns
       4000 ns

    Comparison:
    3 ordsets:union        3.33 M
    1 maps:merge           2.81 M - 1.18x slower +55.30 ns
    2 gb_sets:union        0.75 M - 4.45x slower +1037.53 ns

    ##### With input d3 Equal (30) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           2.25 M      443.46 ns  ±8688.55%           0 ns
       1000 ns
    3 ordsets:union        1.46 M      683.82 ns  ±3817.58%        1000 ns
       1000 ns
    2 gb_sets:union        0.37 M     2686.18 ns   ±483.99%        2000 ns
       9000 ns

    Comparison:
    1 maps:merge           2.25 M
    3 ordsets:union        1.46 M - 1.54x slower +240.36 ns
    2 gb_sets:union        0.37 M - 6.06x slower +2242.72 ns

    ##### With input d4 Equal (50) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           1.50 M      668.83 ns   ±132.24%        1000 ns
       1000 ns
    3 ordsets:union        1.04 M      960.02 ns  ±4458.67%        1000 ns
       2000 ns
    2 gb_sets:union        0.22 M     4523.49 ns   ±196.98%        4000 ns
      18000 ns

    Comparison:
    1 maps:merge           1.50 M
    3 ordsets:union        1.04 M - 1.44x slower +291.19 ns
    2 gb_sets:union        0.22 M - 6.76x slower +3854.66 ns

    ##### With input d5 Equal (1000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge          81.92 K       12.21 μs    ±57.31%          11 μs
         32 μs
    3 ordsets:union       77.39 K       12.92 μs   ±129.75%          12 μs
         39 μs
    2 gb_sets:union       12.72 K       78.63 μs    ±43.08%          70 μs
        174 μs

    Comparison:
    1 maps:merge          81.92 K
    3 ordsets:union       77.39 K - 1.06x slower +0.71 μs
    2 gb_sets:union       12.72 K - 6.44x slower +66.43 μs

    ##### With input d6 Equal (100000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           646.20        1.55 ms    ±18.21%        1.45 ms
       2.86 ms
    3 ordsets:union        305.88        3.27 ms    ±16.73%        3.22 ms
       4.79 ms
    2 gb_sets:union         96.06       10.41 ms    ±18.09%        9.72 ms
      17.41 ms

    Comparison:
    1 maps:merge           646.20
    3 ordsets:union        305.88 - 2.11x slower +1.72 ms
    2 gb_sets:union         96.06 - 6.73x slower +8.86 ms

### Unioning sets of tuple-integers

    Operating System: macOS
    CPU Information: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
    Number of Available Cores: 8
    Available memory: 16 GB
    Elixir 1.9.0
    Erlang 23-master

    Benchmark suite executing with the following configuration:
    warmup: 2 s
    time: 5 s
    memory time: 0 ns
    parallel: 1
    Estimated total run time: 8.40 min

    ##### With input a1 Interspersed (5) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           2.93 M      341.36 ns  ±2603.07%           0 ns
       1000 ns
    3 ordsets:union        1.62 M      616.04 ns  ±4989.81%           0 ns
       1000 ns
    2 gb_sets:union        0.82 M     1219.38 ns  ±2533.38%        1000 ns
       2000 ns

    Comparison:
    1 maps:merge           2.93 M
    3 ordsets:union        1.62 M - 1.80x slower +274.68 ns
    2 gb_sets:union        0.82 M - 3.57x slower +878.02 ns

    ##### With input a2 Interspersed (10) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           2.02 M      494.89 ns  ±2798.11%           0 ns
       1000 ns
    3 ordsets:union        1.04 M      963.72 ns  ±2195.45%        1000 ns
       2000 ns
    2 gb_sets:union        0.50 M     2012.64 ns  ±1226.89%        2000 ns
       4000 ns

    Comparison:
    1 maps:merge           2.02 M
    3 ordsets:union        1.04 M - 1.95x slower +468.83 ns
    2 gb_sets:union        0.50 M - 4.07x slower +1517.75 ns

    ##### With input a3 Interspersed (30) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union      408.22 K        2.45 μs   ±828.38%           2 μs
          4 μs
    1 maps:merge         234.27 K        4.27 μs   ±330.95%           4 μs
         10 μs
    2 gb_sets:union      189.97 K        5.26 μs   ±643.32%           5 μs
         18 μs

    Comparison:
    3 ordsets:union      408.22 K
    1 maps:merge         234.27 K - 1.74x slower +1.82 μs
    2 gb_sets:union      189.97 K - 2.15x slower +2.81 μs

    ##### With input a4 Interspersed (50) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge         767.56 K        1.30 μs  ±1279.19%           1 μs
          2 μs
    3 ordsets:union      246.12 K        4.06 μs   ±267.03%           4 μs
         14 μs
    2 gb_sets:union      108.33 K        9.23 μs   ±255.73%           8 μs
         27 μs

    Comparison:
    1 maps:merge         767.56 K
    3 ordsets:union      246.12 K - 3.12x slower +2.76 μs
    2 gb_sets:union      108.33 K - 7.09x slower +7.93 μs

    ##### With input a5 Interspersed (1000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge          47.61 K       21.00 μs   ±196.69%          19 μs
         59 μs
    3 ordsets:union       12.38 K       80.76 μs    ±53.12%          73 μs
        193 μs
    2 gb_sets:union        6.04 K      165.68 μs    ±30.74%         152 μs
        309 μs

    Comparison:
    1 maps:merge          47.61 K
    3 ordsets:union       12.38 K - 3.84x slower +59.75 μs
    2 gb_sets:union        6.04 K - 7.89x slower +144.67 μs

    ##### With input a6 Interspersed (100000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           210.63        4.75 ms    ±35.35%        3.77 ms
       9.58 ms
    3 ordsets:union         74.84       13.36 ms    ±17.83%       12.73 ms
      18.51 ms
    2 gb_sets:union         54.06       18.50 ms    ±14.28%       17.83 ms
      24.21 ms

    Comparison:
    1 maps:merge           210.63
    3 ordsets:union         74.84 - 2.81x slower +8.61 ms
    2 gb_sets:union         54.06 - 3.90x slower +13.75 ms

    ##### With input b1 Half-left (5) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           4.49 M      222.57 ns  ±1774.31%           0 ns
       1000 ns
    3 ordsets:union        3.33 M      300.45 ns  ±6349.54%           0 ns
       1000 ns
    2 gb_sets:union        1.46 M      683.85 ns  ±2344.50%        1000 ns
       1000 ns

    Comparison:
    1 maps:merge           4.49 M
    3 ordsets:union        3.33 M - 1.35x slower +77.88 ns
    2 gb_sets:union        1.46 M - 3.07x slower +461.29 ns

    ##### With input b2 Half-left (10) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           2.48 M      402.60 ns  ±9495.69%           0 ns
       1000 ns
    3 ordsets:union        2.30 M      435.32 ns  ±1123.50%           0 ns
       1000 ns
    2 gb_sets:union        0.76 M     1318.82 ns   ±818.75%        1000 ns
       2000 ns

    Comparison:
    1 maps:merge           2.48 M
    3 ordsets:union        2.30 M - 1.08x slower +32.73 ns
    2 gb_sets:union        0.76 M - 3.28x slower +916.23 ns

    ##### With input b3 Half-left (30) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           1.54 M      648.33 ns  ±2884.79%           0 ns
       1000 ns
    3 ordsets:union        1.09 M      921.12 ns   ±734.80%        1000 ns
       2000 ns
    2 gb_sets:union        0.37 M     2728.75 ns   ±554.08%        2000 ns
       6000 ns

    Comparison:
    1 maps:merge           1.54 M
    3 ordsets:union        1.09 M - 1.42x slower +272.79 ns
    2 gb_sets:union        0.37 M - 4.21x slower +2080.42 ns

    ##### With input b4 Half-left (50) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union      734.80 K        1.36 μs   ±978.11%           1 μs
          3 μs
    1 maps:merge         439.62 K        2.27 μs  ±1429.61%           2 μs
          5 μs
    2 gb_sets:union      224.47 K        4.45 μs   ±213.29%           4 μs
         15 μs

    Comparison:
    3 ordsets:union      734.80 K
    1 maps:merge         439.62 K - 1.67x slower +0.91 μs
    2 gb_sets:union      224.47 K - 3.27x slower +3.09 μs

    ##### With input b5 Half-left (1000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge          76.01 K       13.16 μs   ±104.36%          12 μs
         35 μs
    3 ordsets:union       45.29 K       22.08 μs   ±125.57%          20 μs
         60 μs
    2 gb_sets:union       13.42 K       74.53 μs    ±44.00%          68 μs
        164 μs

    Comparison:
    1 maps:merge          76.01 K
    3 ordsets:union       45.29 K - 1.68x slower +8.93 μs
    2 gb_sets:union       13.42 K - 5.66x slower +61.37 μs

    ##### With input b6 Half-left (100000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           530.32        1.89 ms    ±18.53%        1.77 ms
       3.40 ms
    3 ordsets:union        139.97        7.14 ms    ±17.91%        7.01 ms
      11.23 ms
    2 gb_sets:union         91.51       10.93 ms    ±12.31%       10.34 ms
      15.62 ms

    Comparison:
    1 maps:merge           530.32
    3 ordsets:union        139.97 - 3.79x slower +5.26 ms
    2 gb_sets:union         91.51 - 5.80x slower +9.04 ms

    ##### With input c1 Half-right (5) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           4.46 M      224.32 ns  ±1730.97%           0 ns
       1000 ns
    3 ordsets:union        3.78 M      264.68 ns  ±3293.90%           0 ns
       1000 ns
    2 gb_sets:union        1.52 M      658.44 ns  ±1819.22%        1000 ns
       1000 ns

    Comparison:
    1 maps:merge           4.46 M
    3 ordsets:union        3.78 M - 1.18x slower +40.37 ns
    2 gb_sets:union        1.52 M - 2.94x slower +434.13 ns

    ##### With input c2 Half-right (10) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union        2.36 M      424.51 ns  ±2870.39%           0 ns
       1000 ns
    1 maps:merge           2.27 M      441.04 ns ±11548.99%           0 ns
       1000 ns
    2 gb_sets:union        0.80 M     1248.21 ns   ±948.08%        1000 ns
       2000 ns

    Comparison:
    3 ordsets:union        2.36 M
    1 maps:merge           2.27 M - 1.04x slower +16.53 ns
    2 gb_sets:union        0.80 M - 2.94x slower +823.70 ns

    ##### With input c3 Half-right (30) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           1.53 M      654.58 ns  ±2879.82%        1000 ns
       1000 ns
    3 ordsets:union        1.13 M      885.52 ns  ±2213.29%        1000 ns
       2000 ns
    2 gb_sets:union        0.37 M     2675.20 ns   ±502.40%        2000 ns
       5000 ns

    Comparison:
    1 maps:merge           1.53 M
    3 ordsets:union        1.13 M - 1.35x slower +230.94 ns
    2 gb_sets:union        0.37 M - 4.09x slower +2020.62 ns

    ##### With input c4 Half-right (50) #####
    Name                      ips        average  deviation         median
        99th %
    3 ordsets:union      747.48 K        1.34 μs  ±1222.85%           1 μs
          3 μs
    1 maps:merge         433.42 K        2.31 μs  ±1493.25%           2 μs
          4 μs
    2 gb_sets:union      223.83 K        4.47 μs   ±283.66%           4 μs
         13 μs

    Comparison:
    3 ordsets:union      747.48 K
    1 maps:merge         433.42 K - 1.72x slower +0.97 μs
    2 gb_sets:union      223.83 K - 3.34x slower +3.13 μs

    ##### With input c5 Half-right (1000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge          66.00 K       15.15 μs   ±321.69%          14 μs
         41 μs
    3 ordsets:union       44.62 K       22.41 μs   ±767.12%          20 μs
         60 μs
    2 gb_sets:union       13.20 K       75.74 μs    ±41.33%          70 μs
        161 μs

    Comparison:
    1 maps:merge          66.00 K
    3 ordsets:union       44.62 K - 1.48x slower +7.26 μs
    2 gb_sets:union       13.20 K - 5.00x slower +60.59 μs

    ##### With input c6 Half-right (100000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           428.32        2.33 ms    ±28.88%        2.06 ms
       4.05 ms
    3 ordsets:union        146.62        6.82 ms    ±18.71%        6.60 ms
      10.79 ms
    2 gb_sets:union         91.45       10.93 ms    ±13.58%       10.27 ms
      15.80 ms

    Comparison:
    1 maps:merge           428.32
    3 ordsets:union        146.62 - 2.92x slower +4.49 ms
    2 gb_sets:union         91.45 - 4.68x slower +8.60 ms

    ##### With input d1 Equal (5) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           3.61 M      276.63 ns  ±3338.58%           0 ns
       1000 ns
    3 ordsets:union        2.42 M      414.07 ns  ±3326.82%           0 ns
       1000 ns
    2 gb_sets:union        1.26 M      792.13 ns  ±1546.56%        1000 ns
       2000 ns

    Comparison:
    1 maps:merge           3.61 M
    3 ordsets:union        2.42 M - 1.50x slower +137.45 ns
    2 gb_sets:union        1.26 M - 2.86x slower +515.50 ns

    ##### With input d2 Equal (10) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           2.15 M      464.77 ns  ±8475.08%           0 ns
       1000 ns
    3 ordsets:union        1.88 M      531.65 ns   ±493.39%        1000 ns
       1000 ns
    2 gb_sets:union        0.69 M     1459.20 ns  ±1113.96%        1000 ns
       3000 ns

    Comparison:
    1 maps:merge           2.15 M
    3 ordsets:union        1.88 M - 1.14x slower +66.89 ns
    2 gb_sets:union        0.69 M - 3.14x slower +994.43 ns

    ##### With input d3 Equal (30) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge        1364.57 K        0.73 μs  ±4056.53%           1 μs
          1 μs
    3 ordsets:union      742.74 K        1.35 μs  ±1193.06%           1 μs
          2 μs
    2 gb_sets:union      307.17 K        3.26 μs   ±527.79%           3 μs
          8 μs

    Comparison:
    1 maps:merge        1364.57 K
    3 ordsets:union      742.74 K - 1.84x slower +0.61 μs
    2 gb_sets:union      307.17 K - 4.44x slower +2.52 μs

    ##### With input d4 Equal (50) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge         816.34 K        1.22 μs   ±168.59%           1 μs
          2 μs
    3 ordsets:union      451.06 K        2.22 μs  ±1119.27%           2 μs
          4 μs
    2 gb_sets:union      184.50 K        5.42 μs   ±200.77%           5 μs
         19 μs

    Comparison:
    1 maps:merge         816.34 K
    3 ordsets:union      451.06 K - 1.81x slower +0.99 μs
    2 gb_sets:union      184.50 K - 4.42x slower +4.19 μs

    ##### With input d5 Equal (1000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge          46.22 K       21.63 μs    ±39.65%          20 μs
         53 μs
    3 ordsets:union       26.20 K       38.17 μs    ±63.50%          35 μs
        101 μs
    2 gb_sets:union       10.24 K       97.66 μs    ±36.11%          90 μs
        199 μs

    Comparison:
    1 maps:merge          46.22 K
    3 ordsets:union       26.20 K - 1.76x slower +16.53 μs
    2 gb_sets:union       10.24 K - 4.51x slower +76.03 μs

    ##### With input d6 Equal (100000) #####
    Name                      ips        average  deviation         median
        99th %
    1 maps:merge           440.81        2.27 ms    ±12.79%        2.17 ms
       3.48 ms
    3 ordsets:union        126.12        7.93 ms    ±26.40%        7.11 ms
      13.85 ms
    2 gb_sets:union         73.86       13.54 ms    ±18.78%       12.89 ms
      19.27 ms

    Comparison:
    1 maps:merge           440.81
    3 ordsets:union        126.12 - 3.50x slower +5.66 ms
    2 gb_sets:union         73.86 - 5.97x slower +11.27 ms

Addendum: Intersection benchmark results
========================================

### Intersection of sets of integers

    Operating System: macOS
    CPU Information: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
    Number of Available Cores: 8
    Available memory: 16 GB
    Elixir 1.9.0
    Erlang 23-master

    Benchmark suite executing with the following configuration:
    warmup: 2 s
    time: 5 s
    memory time: 0 ns
    parallel: 1
    Estimated total run time: 6.53 min

    ##### With input a1 Interspersed (5) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          5.64 M      177.31 ns  ±8960.73%
    0 ns        1000 ns
    3 ordsets:intersection          4.58 M      218.18 ns  ±1955.05%
    0 ns        1000 ns
    2 gb_sets:intersection          1.85 M      541.24 ns  ±3690.38%
    0 ns        1000 ns
    0 cerl_sets:intersection        1.81 M      551.00 ns  ±6378.03%
    0 ns        1000 ns

    Comparison:
    1 mapsets:intersection          5.64 M
    3 ordsets:intersection          4.58 M - 1.23x slower +40.87 ns
    2 gb_sets:intersection          1.85 M - 3.05x slower +363.93 ns
    0 cerl_sets:intersection        1.81 M - 3.11x slower +373.69 ns

    ##### With input a2 Interspersed (10) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          3.87 M      258.37 ns  ±8156.88%
    0 ns        1000 ns
    3 ordsets:intersection          3.25 M      307.69 ns   ±995.12%
    0 ns        1000 ns
    0 cerl_sets:intersection        1.35 M      742.45 ns  ±4916.42%
 1000 ns        1000 ns
    2 gb_sets:intersection          1.20 M      833.71 ns  ±3535.59%
 1000 ns        1000 ns

    Comparison:
    1 mapsets:intersection          3.87 M
    3 ordsets:intersection          3.25 M - 1.19x slower +49.32 ns
    0 cerl_sets:intersection        1.35 M - 2.87x slower +484.09 ns
    2 gb_sets:intersection          1.20 M - 3.23x slower +575.34 ns

    ##### With input a3 Interspersed (30) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          2.37 M        0.42 μs  ±7530.28%
    0 μs           1 μs
    3 ordsets:intersection          1.57 M        0.64 μs   ±571.54%
    1 μs           1 μs
    0 cerl_sets:intersection        0.63 M        1.60 μs  ±1704.57%
    1 μs           3 μs
    2 gb_sets:intersection          0.57 M        1.74 μs  ±1508.42%
    2 μs           3 μs

    Comparison:
    1 mapsets:intersection          2.37 M
    3 ordsets:intersection          1.57 M - 1.51x slower +0.21 μs
    0 cerl_sets:intersection        0.63 M - 3.79x slower +1.17 μs
    2 gb_sets:intersection          0.57 M - 4.13x slower +1.32 μs

    ##### With input b1 Half-left (5) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          7.81 M      128.06 ns  ±3031.39%
    0 ns        1000 ns
    3 ordsets:intersection          6.10 M      163.95 ns   ±819.87%
    0 ns        1000 ns
    2 gb_sets:intersection          1.91 M      524.17 ns  ±3574.70%
    0 ns        1000 ns
    0 cerl_sets:intersection        1.73 M      578.18 ns  ±5060.91%
    0 ns        1000 ns

    Comparison:
    1 mapsets:intersection          7.81 M
    3 ordsets:intersection          6.10 M - 1.28x slower +35.89 ns
    2 gb_sets:intersection          1.91 M - 4.09x slower +396.11 ns
    0 cerl_sets:intersection        1.73 M - 4.51x slower +450.12 ns

    ##### With input b2 Half-left (10) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          5.34 M      187.35 ns  ±6435.27%
    0 ns        1000 ns
    3 ordsets:intersection          3.50 M      285.53 ns  ±8907.47%
    0 ns        1000 ns
    0 cerl_sets:intersection        1.25 M      801.68 ns  ±2618.59%
 1000 ns        1000 ns
    2 gb_sets:intersection          1.15 M      865.97 ns  ±3771.19%
 1000 ns        1000 ns

    Comparison:
    1 mapsets:intersection          5.34 M
    3 ordsets:intersection          3.50 M - 1.52x slower +98.18 ns
    0 cerl_sets:intersection        1.25 M - 4.28x slower +614.33 ns
    2 gb_sets:intersection          1.15 M - 4.62x slower +678.63 ns

    ##### With input b3 Half-left (30) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          3.12 M        0.32 μs ±10505.28%
    0 μs           1 μs
    3 ordsets:intersection          1.79 M        0.56 μs  ±5943.47%
    0 μs           1 μs
    0 cerl_sets:intersection        0.60 M        1.66 μs  ±1650.01%
    1 μs           3 μs
    2 gb_sets:intersection          0.57 M        1.77 μs  ±1510.44%
    2 μs           3 μs

    Comparison:
    1 mapsets:intersection          3.12 M
    3 ordsets:intersection          1.79 M - 1.74x slower +0.24 μs
    0 cerl_sets:intersection        0.60 M - 5.17x slower +1.34 μs
    2 gb_sets:intersection          0.57 M - 5.51x slower +1.45 μs

    ##### With input b4 Half-left (50) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          1.41 M        0.71 μs  ±4451.88%
    1 μs           1 μs
    3 ordsets:intersection          1.32 M        0.76 μs  ±4422.37%
    1 μs           1 μs
    2 gb_sets:intersection          0.37 M        2.72 μs   ±719.29%
    2 μs           5 μs
    0 cerl_sets:intersection        0.31 M        3.26 μs   ±464.70%
    3 μs           5 μs

    Comparison:
    1 mapsets:intersection          1.41 M
    3 ordsets:intersection          1.32 M - 1.07x slower +0.0487 μs
    2 gb_sets:intersection          0.37 M - 3.82x slower +2.01 μs
    0 cerl_sets:intersection        0.31 M - 4.59x slower +2.55 μs

    ##### With input c1 Halt-right (5) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          8.50 M      117.64 ns  ±3751.50%
    0 ns        1000 ns
    3 ordsets:intersection          4.96 M      201.70 ns  ±1008.33%
    0 ns        1000 ns
    0 cerl_sets:intersection        2.66 M      375.86 ns  ±7893.27%
    0 ns        1000 ns
    2 gb_sets:intersection          1.99 M      501.60 ns  ±5740.59%
    0 ns        1000 ns

    Comparison:
    1 mapsets:intersection          8.50 M
    3 ordsets:intersection          4.96 M - 1.71x slower +84.06 ns
    0 cerl_sets:intersection        2.66 M - 3.20x slower +258.22 ns
    2 gb_sets:intersection          1.99 M - 4.26x slower +383.96 ns

    ##### With input c2 Halt-right (10) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          5.61 M      178.32 ns  ±6353.45%
    0 ns        1000 ns
    3 ordsets:intersection          3.27 M      305.53 ns  ±8831.03%
    0 ns        1000 ns
    0 cerl_sets:intersection        1.61 M      619.53 ns  ±5512.50%
    0 ns        1000 ns
    2 gb_sets:intersection          1.20 M      830.39 ns  ±3587.38%
 1000 ns        1000 ns

    Comparison:
    1 mapsets:intersection          5.61 M
    3 ordsets:intersection          3.27 M - 1.71x slower +127.21 ns
    0 cerl_sets:intersection        1.61 M - 3.47x slower +441.21 ns
    2 gb_sets:intersection          1.20 M - 4.66x slower +652.07 ns

    ##### With input c3 Halt-right (30) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          3.02 M        0.33 μs ±10877.75%
    0 μs           1 μs
    3 ordsets:intersection          1.76 M        0.57 μs  ±6736.07%
    0 μs           1 μs
    0 cerl_sets:intersection        0.83 M        1.20 μs  ±2066.14%
    1 μs           2 μs
    2 gb_sets:intersection          0.56 M        1.80 μs  ±1442.53%
    2 μs           3 μs

    Comparison:
    1 mapsets:intersection          3.02 M
    3 ordsets:intersection          1.76 M - 1.71x slower +0.24 μs
    0 cerl_sets:intersection        0.83 M - 3.61x slower +0.87 μs
    2 gb_sets:intersection          0.56 M - 5.41x slower +1.46 μs

    ##### With input c4 Half-right (50) #####
    Name                               ips        average  deviation
  median         99th %
    3 ordsets:intersection          1.42 M        0.70 μs  ±4101.38%
    1 μs           1 μs
    1 mapsets:intersection          1.31 M        0.77 μs  ±5155.14%
    1 μs           1 μs
    0 cerl_sets:intersection        0.48 M        2.07 μs  ±1105.13%
    2 μs           3 μs
    2 gb_sets:intersection          0.37 M        2.69 μs   ±793.20%
    2 μs           5 μs

    Comparison:
    3 ordsets:intersection          1.42 M
    1 mapsets:intersection          1.31 M - 1.09x slower +0.0618 μs
    0 cerl_sets:intersection        0.48 M - 2.95x slower +1.37 μs
    2 gb_sets:intersection          0.37 M - 3.82x slower +1.98 μs

    ##### With input d1 Equal (5) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          4.61 M      216.84 ns  ±4985.98%
    0 ns        1000 ns
    3 ordsets:intersection          3.44 M      290.38 ns  ±9494.06%
    0 ns        1000 ns
    0 cerl_sets:intersection        1.62 M      618.37 ns  ±5703.54%
    0 ns        1000 ns
    2 gb_sets:intersection          1.48 M      677.41 ns  ±4388.76%
 1000 ns        1000 ns

    Comparison:
    1 mapsets:intersection          4.61 M
    3 ordsets:intersection          3.44 M - 1.34x slower +73.54 ns
    0 cerl_sets:intersection        1.62 M - 2.85x slower +401.53 ns
    2 gb_sets:intersection          1.48 M - 3.12x slower +460.57 ns

    ##### With input d2 Equal (10) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          3.96 M      252.22 ns ±10397.76%
    0 ns        1000 ns
    3 ordsets:intersection          2.95 M      338.84 ns  ±8900.72%
    0 ns        1000 ns
    0 cerl_sets:intersection        1.16 M      862.62 ns  ±3981.08%
 1000 ns        1000 ns
    2 gb_sets:intersection          0.90 M     1112.16 ns  ±2553.42%
 1000 ns        2000 ns

    Comparison:
    1 mapsets:intersection          3.96 M
    3 ordsets:intersection          2.95 M - 1.34x slower +86.61 ns
    0 cerl_sets:intersection        1.16 M - 3.42x slower +610.40 ns
    2 gb_sets:intersection          0.90 M - 4.41x slower +859.94 ns

    ##### With input d3 Equal (30) #####
    Name                               ips        average  deviation
  median         99th %
    1 mapsets:intersection          2.31 M        0.43 μs  ±8998.97%
    0 μs           1 μs
    3 ordsets:intersection          1.49 M        0.67 μs  ±3628.66%
    1 μs           1 μs
    0 cerl_sets:intersection        0.52 M        1.94 μs   ±965.82%
    2 μs           3 μs
    2 gb_sets:intersection          0.42 M        2.38 μs   ±878.07%
    2 μs           4 μs

    Comparison:
    1 mapsets:intersection          2.31 M
    3 ordsets:intersection          1.49 M - 1.55x slower +0.24 μs
    0 cerl_sets:intersection        0.52 M - 4.48x slower +1.51 μs
    2 gb_sets:intersection          0.42 M - 5.50x slower +1.95 μs

### Unioning sets of tuple-integers

    Operating System: macOS
    CPU Information: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
    Number of Available Cores: 8
    Available memory: 16 GB
    Elixir 1.9.0
    Erlang 23-master

    Benchmark suite executing with the following configuration:
    warmup: 2 s
    time: 5 s
    memory time: 0 ns
    parallel: 1
    Estimated total run time: 4.90 min

    ##### With input a1 Interspersed (5) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        2.53 M      394.70 ns  ±7692.39%
  0 ns        1000 ns
    3 ordsets:intersection        2.12 M      471.60 ns  ±1021.75%
  0 ns        1000 ns
    2 gb_sets:intersection        1.30 M      768.44 ns  ±2657.04%
 1000 ns        1000 ns

    Comparison:
    1 mapsets:intersection        2.53 M
    3 ordsets:intersection        2.12 M - 1.19x slower +76.90 ns
    2 gb_sets:intersection        1.30 M - 1.95x slower +373.75 ns

    ##### With input a2 Interspersed (10) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        1.96 M      510.95 ns  ±2509.15%
  0 ns        1000 ns
    3 ordsets:intersection        1.30 M      770.06 ns   ±676.65%
 1000 ns        1000 ns
    2 gb_sets:intersection        0.81 M     1240.22 ns  ±1388.14%
 1000 ns        2000 ns

    Comparison:
    1 mapsets:intersection        1.96 M
    3 ordsets:intersection        1.30 M - 1.51x slower +259.11 ns
    2 gb_sets:intersection        0.81 M - 2.43x slower +729.27 ns

    ##### With input a3 Interspersed (30) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection      845.89 K        1.18 μs  ±2713.20%
  1 μs           2 μs
    3 ordsets:intersection      495.26 K        2.02 μs   ±164.49%
  2 μs           3 μs
    2 gb_sets:intersection      324.61 K        3.08 μs   ±718.13%
  3 μs           5 μs

    Comparison:
    1 mapsets:intersection      845.89 K
    3 ordsets:intersection      495.26 K - 1.71x slower +0.84 μs
    2 gb_sets:intersection      324.61 K - 2.61x slower +1.90 μs

    ##### With input b1 Half-left (5) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        4.66 M      214.57 ns  ±1896.59%
  0 ns        1000 ns
    3 ordsets:intersection        3.62 M      276.50 ns  ±1465.48%
  0 ns        1000 ns
    2 gb_sets:intersection        1.73 M      577.07 ns  ±5041.95%
  0 ns        1000 ns

    Comparison:
    1 mapsets:intersection        4.66 M
    3 ordsets:intersection        3.62 M - 1.29x slower +61.94 ns
    2 gb_sets:intersection        1.73 M - 2.69x slower +362.51 ns

    ##### With input b2 Half-left (10) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        2.92 M      342.24 ns  ±9961.99%
  0 ns        1000 ns
    3 ordsets:intersection        2.09 M      478.76 ns  ±5507.02%
  0 ns        1000 ns
    2 gb_sets:intersection        0.96 M     1043.40 ns  ±2396.75%
 1000 ns        2000 ns

    Comparison:
    1 mapsets:intersection        2.92 M
    3 ordsets:intersection        2.09 M - 1.40x slower +136.53 ns
    2 gb_sets:intersection        0.96 M - 3.05x slower +701.17 ns

    ##### With input b3 Half-left (30) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        1.72 M      580.48 ns  ±4998.64%
  0 ns        1000 ns
    3 ordsets:intersection        1.01 M      989.96 ns  ±2850.03%
 1000 ns        2000 ns
    2 gb_sets:intersection        0.44 M     2292.44 ns   ±981.37%
 2000 ns        4000 ns

    Comparison:
    1 mapsets:intersection        1.72 M
    3 ordsets:intersection        1.01 M - 1.71x slower +409.48 ns
    2 gb_sets:intersection        0.44 M - 3.95x slower +1711.96 ns

    ##### With input b4 Half-left (50) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection      902.32 K        1.11 μs  ±1892.28%
  1 μs           2 μs
    3 ordsets:intersection      710.61 K        1.41 μs  ±1793.08%
  1 μs           2 μs
    2 gb_sets:intersection      282.62 K        3.54 μs   ±495.73%
  3 μs          11 μs

    Comparison:
    1 mapsets:intersection      902.32 K
    3 ordsets:intersection      710.61 K - 1.27x slower +0.30 μs
    2 gb_sets:intersection      282.62 K - 3.19x slower +2.43 μs

    ##### With input c1 Halt-right (5) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        4.70 M      212.66 ns  ±1573.58%
  0 ns        1000 ns
    3 ordsets:intersection        3.77 M      265.19 ns  ±1597.40%
  0 ns        1000 ns
    2 gb_sets:intersection        1.76 M      567.11 ns  ±4249.42%
  0 ns        1000 ns

    Comparison:
    1 mapsets:intersection        4.70 M
    3 ordsets:intersection        3.77 M - 1.25x slower +52.53 ns
    2 gb_sets:intersection        1.76 M - 2.67x slower +354.45 ns

    ##### With input c2 Halt-right (10) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        3.14 M      318.35 ns  ±7626.82%
  0 ns        1000 ns
    3 ordsets:intersection        2.23 M      449.20 ns  ±5268.98%
  0 ns        1000 ns
    2 gb_sets:intersection        0.99 M     1014.32 ns  ±2177.84%
 1000 ns        2000 ns

    Comparison:
    1 mapsets:intersection        3.14 M
    3 ordsets:intersection        2.23 M - 1.41x slower +130.85 ns
    2 gb_sets:intersection        0.99 M - 3.19x slower +695.97 ns

    ##### With input c3 Halt-right (30) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        1.78 M      560.38 ns  ±5118.91%
  0 ns        1000 ns
    3 ordsets:intersection        1.01 M      989.13 ns  ±2292.17%
 1000 ns        2000 ns
    2 gb_sets:intersection        0.44 M     2294.68 ns   ±981.21%
 2000 ns        4000 ns

    Comparison:
    1 mapsets:intersection        1.78 M
    3 ordsets:intersection        1.01 M - 1.77x slower +428.75 ns
    2 gb_sets:intersection        0.44 M - 4.09x slower +1734.30 ns

    ##### With input c4 Half-right (50) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection      875.40 K        1.14 μs  ±1770.92%
  1 μs           2 μs
    3 ordsets:intersection      703.96 K        1.42 μs  ±1911.40%
  1 μs           3 μs
    2 gb_sets:intersection      294.25 K        3.40 μs   ±488.43%
  3 μs           6 μs

    Comparison:
    1 mapsets:intersection      875.40 K
    3 ordsets:intersection      703.96 K - 1.24x slower +0.28 μs
    2 gb_sets:intersection      294.25 K - 2.98x slower +2.26 μs

    ##### With input d1 Equal (5) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        3.29 M      303.69 ns  ±9348.28%
  0 ns        1000 ns
    3 ordsets:intersection        2.19 M      455.98 ns  ±5799.97%
  0 ns        1000 ns
    2 gb_sets:intersection        1.15 M      869.11 ns  ±3884.46%
 1000 ns        2000 ns

    Comparison:
    1 mapsets:intersection        3.29 M
    3 ordsets:intersection        2.19 M - 1.50x slower +152.29 ns
    2 gb_sets:intersection        1.15 M - 2.86x slower +565.41 ns

    ##### With input d2 Equal (10) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection        2.93 M      341.11 ns  ±3839.65%
  0 ns        1000 ns
    3 ordsets:intersection        1.85 M      540.08 ns  ±2436.90%
  0 ns        1000 ns
    2 gb_sets:intersection        0.72 M     1388.21 ns  ±1540.59%
 1000 ns        2000 ns

    Comparison:
    1 mapsets:intersection        2.93 M
    3 ordsets:intersection        1.85 M - 1.58x slower +198.97 ns
    2 gb_sets:intersection        0.72 M - 4.07x slower +1047.11 ns

    ##### With input d3 Equal (30) #####
    Name                             ips        average  deviation
median         99th %
    1 mapsets:intersection     1395.63 K        0.72 μs  ±4359.84%
  1 μs           1 μs
    3 ordsets:intersection      744.64 K        1.34 μs  ±1845.56%
  1 μs           2 μs
    2 gb_sets:intersection      302.52 K        3.31 μs   ±672.80%
  3 μs          10 μs

    Comparison:
    1 mapsets:intersection     1395.63 K
    3 ordsets:intersection      744.64 K - 1.87x slower +0.63 μs
    2 gb_sets:intersection      302.52 K - 4.61x slower +2.59 μs
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/eeps/attachments/20190918/5136b254/attachment.htm>


More information about the eeps mailing list