Performance comparison of immutable set implementations for .NET.

results1.txt

Results from running PerfComparison (https://github.com/jack-pappas/fs-core-optimized)
Random set density parameter: 0.850000
RNG seed: 246071284
----

Warming up...done.

Create Random Set<int> (n=1000000)
FSharp.Core (Original)  : 5250.775900 (ms)
FSharp.Core (Optimized) : 5239.608900 (ms)
ExtCore (Patricia Trie) : 4495.043800 (ms)
ExtCore (HashSet)       : 5217.785400 (ms)
ImmutableHashSet        : 3218.777800 (ms)
ImmutableSortedSet      : 1271.942300 (ms)

Create Random Set<int64> (n=1000000)
FSharp.Core (Original)  : 5260.672800 (ms)
FSharp.Core (Optimized) : 5510.903600 (ms)
ExtCore (Patricia Trie) : 5177.820500 (ms)
ExtCore (HashSet)       : 5066.390500 (ms)
ImmutableHashSet        : 3466.240000 (ms)
ImmutableSortedSet      : 816.275900 (ms)

Union Random Set<int> (n=1000, N=10000)
FSharp.Core (Original)  : 80567.349000 (ms)
FSharp.Core (Optimized) : 73981.062400 (ms)
ExtCore (Patricia Trie) : 51803.766100 (ms)
ExtCore (HashSet)       : 55912.926800 (ms)
ImmutableHashSet        : 120090.948300 (ms)
ImmutableSortedSet      : 100744.783900 (ms)

Union Random Set<int64> (n=1000, N=10000)
FSharp.Core (Original)  : 94756.231700 (ms)
FSharp.Core (Optimized) : 88011.669200 (ms)
ExtCore (Patricia Trie) : 161813.288500 (ms)
ExtCore (HashSet)       : 50137.016400 (ms)
ImmutableHashSet        : 122098.560100 (ms)
ImmutableSortedSet      : 107702.225000 (ms)

Intersect Random Set<int> (n=1000, N=10000)
FSharp.Core (Original)  : 1.775700 (ms)
FSharp.Core (Optimized) : 2.065800 (ms)
ExtCore (Patricia Trie) : 1.706500 (ms)
ExtCore (HashSet)       : 3.634100 (ms)
ImmutableHashSet        : 7188.837800 (ms)
ImmutableSortedSet      : 4643.198700 (ms)

Intersect Random Set<int64> (n=1000, N=10000)
FSharp.Core (Original)  : 2.062800 (ms)
FSharp.Core (Optimized) : 2.055500 (ms)
ExtCore (Patricia Trie) : 3.824400 (ms)
ExtCore (HashSet)       : 5.866800 (ms)
ImmutableHashSet        : 7159.951700 (ms)
ImmutableSortedSet      : 5153.509300 (ms)

results2.txt

Results from running PerfComparison (https://github.com/jack-pappas/fs-core-optimized)
Random set density parameter: 0.850000
RNG seed: 2009430690
----

Warming up...done.

Create Random Set<int> (n=1000000)
FSharp.Core (Original)  : 5102.144000 (ms)
FSharp.Core (Optimized) : 4860.057500 (ms)
ExtCore (Patricia Trie) : 3782.368100 (ms)
ExtCore (HashSet)       : 4362.101000 (ms)
ImmutableHashSet        : 3341.686800 (ms)
ImmutableSortedSet      : 1233.917400 (ms)

Create Random Set<int64> (n=1000000)
FSharp.Core (Original)  : 5192.650800 (ms)
FSharp.Core (Optimized) : 5181.521700 (ms)
ExtCore (Patricia Trie) : 4902.459900 (ms)
ExtCore (HashSet)       : 4315.031500 (ms)
ImmutableHashSet        : 3516.871900 (ms)
ImmutableSortedSet      : 739.669200 (ms)

Union Random Set<int> (n=1000, N=10000)
FSharp.Core (Original)  : 84861.454400 (ms)
FSharp.Core (Optimized) : 74948.634600 (ms)
ExtCore (Patricia Trie) : 55889.758600 (ms)
ExtCore (HashSet)       : 50862.873800 (ms)
ImmutableHashSet        : 118575.328100 (ms)
ImmutableSortedSet      : 94145.174800 (ms)

Union Random Set<int64> (n=1000, N=10000)
FSharp.Core (Original)  : 96220.899500 (ms)
FSharp.Core (Optimized) : 85079.045700 (ms)
ExtCore (Patricia Trie) : 150984.358200 (ms)
ExtCore (HashSet)       : 47187.795500 (ms)
ImmutableHashSet        : 125570.637600 (ms)
ImmutableSortedSet      : 110561.357100 (ms)

Intersect Random Set<int> (n=1000, N=10000)
FSharp.Core (Original)  : 1.784600 (ms)
FSharp.Core (Optimized) : 1.636600 (ms)
ExtCore (Patricia Trie) : 1.612700 (ms)
ExtCore (HashSet)       : 3.538600 (ms)
ImmutableHashSet        : 8879.417900 (ms)
ImmutableSortedSet      : 4678.573300 (ms)

Intersect Random Set<int64> (n=1000, N=10000)
FSharp.Core (Original)  : 1.663900 (ms)
FSharp.Core (Optimized) : 2.044400 (ms)
ExtCore (Patricia Trie) : 3.849600 (ms)
ExtCore (HashSet)       : 5.818600 (ms)
ImmutableHashSet        : 9664.006800 (ms)
ImmutableSortedSet      : 5026.474300 (ms)

results3.txt

Results from running PerfComparison (https://github.com/jack-pappas/fs-core-optimized)
Random set density parameter: 0.466471
RNG seed: 1706225589
----

Warming up...done.

Create Random Set<int> (n=1000000)
FSharp.Core (Original)  : 5129.190000 (ms)
FSharp.Core (Optimized) : 4819.770100 (ms)
ExtCore (Patricia Trie) : 3763.738100 (ms)
ExtCore (HashSet)       : 4326.340300 (ms)
ImmutableHashSet        : 3242.192600 (ms)
ImmutableSortedSet      : 817.685900 (ms)

Create Random Set<int64> (n=1000000)
FSharp.Core (Original)  : 5139.630900 (ms)
FSharp.Core (Optimized) : 5356.512700 (ms)
ExtCore (Patricia Trie) : 4893.781900 (ms)
ExtCore (HashSet)       : 4388.491700 (ms)
ImmutableHashSet        : 3581.977900 (ms)
ImmutableSortedSet      : 776.583600 (ms)

Union Random Set<int> (n=1000, N=10000)
FSharp.Core (Original)  : 79167.470900 (ms)
FSharp.Core (Optimized) : 73955.493800 (ms)
ExtCore (Patricia Trie) : 55332.259100 (ms)
ExtCore (HashSet)       : 52176.678800 (ms)
ImmutableHashSet        : 120117.010500 (ms)
ImmutableSortedSet      : 95280.560600 (ms)

Union Random Set<int64> (n=1000, N=10000)
FSharp.Core (Original)  : 89886.272400 (ms)
FSharp.Core (Optimized) : 83796.816100 (ms)
ExtCore (Patricia Trie) : 148573.575000 (ms)
ExtCore (HashSet)       : 49433.347200 (ms)
ImmutableHashSet        : 118066.079500 (ms)
ImmutableSortedSet      : 105642.999900 (ms)

Intersect Random Set<int> (n=1000, N=10000)
FSharp.Core (Original)  : 1.978700 (ms)
FSharp.Core (Optimized) : 1.747100 (ms)
ExtCore (Patricia Trie) : 1.632300 (ms)
ExtCore (HashSet)       : 4.020200 (ms)
ImmutableHashSet        : 7248.876900 (ms)
ImmutableSortedSet      : 4707.198800 (ms)

Intersect Random Set<int64> (n=1000, N=10000)
FSharp.Core (Original)  : 1.655800 (ms)
FSharp.Core (Optimized) : 1.610100 (ms)
ExtCore (Patricia Trie) : 3.522800 (ms)
ExtCore (HashSet)       : 5.557500 (ms)
ImmutableHashSet        : 7169.551200 (ms)
ImmutableSortedSet      : 4856.082000 (ms)