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