<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>