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

Siraaj Khandkar siraaj@REDACTED
Fri Sep 20 18:00:52 CEST 2019


Thanks! It is I that was not reading hard enough and missed that line :)

On Fri, Sep 20, 2019 at 11:32 AM José Valim
<jose.valim@REDACTED> wrote:
>
> The proposal says:
>
> > Note there is also a `sets` module, but it is rarely a viable option.
>
> I personally couldn't find a scenario where "sets" was more performant than any of the other alternatives so in terms of comparisons, it is not relevant. But maybe I was not looking at it hard enough.
>
> José Valim
> www.plataformatec.com.br
> Skype: jv.ptec
> Founder and Director of R&D
>
>
> On Fri, Sep 20, 2019 at 5:22 PM Siraaj Khandkar <siraaj@REDACTED> wrote:
>>
>> Is there a reason for omission of sets module from the comparison?
>>
>>
>> On Wed, Sep 18, 2019 at 2:00 PM José Valim
>> <jose.valim@REDACTED> wrote:
>> >
>> >     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
>> > _______________________________________________
>> > eeps mailing list
>> > eeps@REDACTED
>> > http://erlang.org/mailman/listinfo/eeps



More information about the eeps mailing list