Skip to content

Instantly share code, notes, and snippets.

@jack-pappas
Last active December 31, 2015 21:49
Show Gist options
  • Save jack-pappas/8049561 to your computer and use it in GitHub Desktop.
Save jack-pappas/8049561 to your computer and use it in GitHub Desktop.
Performance comparison of immutable set implementations for .NET.
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)
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)
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment