+972 52-548-6969
What about F# collections?
time to read 6 min | 1127 words
After disqualifying the BCL immutable collections for performance, I decided that I probably also need to look at the F# collection package, to see if they do any better.
I referenced the FSharp.Core dll and wrote the following:
1: private static FSharpMap<long, object> FSharpAdd(int iterations)2: {3: var dic = MapModule.Empty<long, object>();4:5: var sp = Stopwatch.StartNew();6: var rnd = new Random(32);7: for (int i = 0; i < iterations; i++)8: {9: foreach (var item in Enumerable.Range(rnd.Next(0, i), Math.Max(i * 2, 16)))10: {11: dic = dic.Add(item, null);12: }13: }14:15: Console.WriteLine(sp.Elapsed + " Adding items, fsharp map");16:17: return dic;18: }
As I was writing this post, the code is running, and I have had time to do some emails, writing the entire post, check the CPU status, and it is still running. It is likely going to be worse than the immutable collections scenario.
That make sense, since in the immutable collection scenario we had the ability to do many mutations all at once (using SetItems, which isn’t available on the FSharpMap).
However, it clocks in at just over 1 hour and 16 minutes, making it the slowest contender overall.
Comments
This whas the reason why FHolm dropped IronJS AFAIK. see http://ironjs.wordpress.com/
sorry: here is the link http://ironjs.wordpress.com/2012/04/19/why-not-f/
seq {1 .. n} |> FSharpx.Collections.Vector.ofSeq
is five times slower than .NET Dictionary but five times faster than
seq {1 .. n} |> Seq.map (fun x -> x, n ) |> Map.ofSeq
Great minds think alike, fools never differ...
http://ayende.com/blog/164769/safelist-safedictionary-fast-immutable-structures#comment17
Interesting F# was so bad!
.Net's generic Dictionary type is implemented as a hash table. The non-generic version is aptly called Hashtable which clears up any ambiguity. F#'s map is implemented as an AVL tree which is an entirely different data structure with different performance characteristics and use cases.
Hash tables have significantly better fill rate performance than AVL trees, as this post shows, nobody should be surprised.
F# is a statically typed language just as C# is. In F# you can use the generic Dictionary type if fill rate is important just like you would in C#. The F# library also includes some basic immutable data structures like list, set and map which can be used when appropriate.
On top of the basic built-in immutable data structures, the F# open source community has created a number of open source libraries that provide different data structures that can be applied to different scenarios. For example I'd recommend looking at ExtCore https://github.com/jack-pappas/ExtCore/tree/master/ExtCore
For an introduction to immutable data structures I'd recommend taking a look at Chris Osaki's Purely Functional Data Structures book: http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504
If your scenario is to create a read-only lookup data structure which you write a large set of data to once, I'd recommend using the .Net Dictionary class (a hash table) and wrapping it with a ReadOnlyDictionary (from System.Collections.ObjectModel).
Philip, My scenario is needing an immutable data structure.
I don't understand why you require an immutable data structure.
I can see that you require thread safety due to your transactional approach to modifications but you've immediately ruled out mutable structures in favour of immutability. There are ways of achieving what you want with mutable structures (unless I'm missing something).
Ayende, as an F# developer and long-time reader of your blog, I'm rather disappointed to see how casually you dismissed F#; having implemented my own library of immutable collections in F# (as Phil Trelford mentioned in his comment), I'd like to point out a few issues with your benchmarks/comparisons to clear F#'s reputation here.
1) Comparing the immutable collections in FSharp.Core and the Microsoft.Bcl.Immutable package is not a fair comparison. The reason for this is that the Set and Map implementations in Bcl.Immutable are implemented using Red-Black trees, while those in FSharp.Core are implemented using AVL trees. That's an important distinction, because insertion -- the only thing your benchmark measures -- is slower for AVL trees than for RB trees because AVL trees have a stronger notion of "balanced", so they use additional steps to enfore that; the benefit is that once the tree is constructed, lookups are faster in AVL trees than for RB trees. In other words, if your application has a low (inserts+deletes)/lookups ratio, an AVL tree will provide better performance; otherwise, an RB tree is better.
I wrote up an answer about this on StackOverflow earlier this year: http://stackoverflow.com/questions/16216439/whats-the-difference-between-immutablesortedset-and-fsharp-set
2) The Bcl.Immutable package does have an interesting feature for optimizing multiple mutations to a collection. Admittedly the F# Core library doesn't have this feature, but given the performance gains it offers in certain scenarios, I think it's something we'll consider adding in a future version of F#. It would be interesting if your benchmark showed how much of a performance gain that feature offers over the "naive" case of adding elements one at a time.
3) The Map and Set types in the standard FSharp.Core library aren't particularly well-optimized; for most use cases they're plenty performant, but they have a few inefficiencies which can be magnified in certain scenarios and result in a large performance degredation. One of these inefficiencies is that the standard Map and Set types create a new tree when you insert a key/value or value (respectively) which already exists in the collection; this creates additional work for the GC and you also end up paying the cost of rebalancing the tree for no reason. Unfortunately, your benchmark ran into exactly this scenario.
I implemented fixes for these edge cases some time ago and implemented a few simple benchmarks much like your own. To see the performance improvement plus some additional comparisons against a few other immutable collections types (including the Bcl.Immutable collections), please see the 'PerfComparison' project here: https://github.com/jack-pappas/fs-core-optimized
I've done a few test runs of the PerfComparison project and posted the results if you want to have a quick look: https://gist.github.com/jack-pappas/8049561
4) I've implemented my own library of immutable collections and other useful F# bits, called ExtCore (https://github.com/jack-pappas/ExtCore). You might consider trying out my HashMap implementation for your project; it's already quite fast, and there's still some room for further improvement if necessary. Note that it currently uses the standard F# Map internally when resolving hash collisions, so it's still partially susceptable to the issue I described above -- please keep that in mind when benchmarking. If you find it to your liking but you need that extra bit of performance, please let me know and I'll replace the internal uses of the standard F# Map with my optimized version.
If ExtCore.HashMap doesn't meet your needs, consider the Vector implementation in Solid (https://github.com/GregRos/Solid). I haven't had a chance to try it myself but heard it's very fast.
I hope that helps to clear a few things up about why you saw the results you did. In general, F# is very fast -- it's been used by a number of banks and trading firms to implement parts of their trading systems, and I've met (or know personally) a number of F# developers using it for high-performance web apps or data science; I doubt any of that would be possible if F# were really "slow".
If you have any other questions, please check out the F# Open Source group (https://groups.google.com/forum/?fromgroups#!forum/fsharp-opensource). There have been a number of discussions recently around benchmarking data structures (whether written in F# or not), and if you're interested in building a comprehensive benchmark to choose the best data structure for your application, I encourage you to email the group -- I'm sure a number of people would be interested in collaborating with you on such a project.
Roger -- That article is often used as evidence of F# being "slow", which is really unfortunate because the reason IronJS is slow is that the code is poorly written -- in other words, if you took the same code and ported it to C#, C++, Java, etc., it'd be just as slow. I've heard some discussions in the F# community about spending some time fixing up the code just to refute that article, but I don't think anyone's gotten around to doing it yet.
Jack, I don't really care for the historical reasons. I needed a collection that is fast for my stated usage scenario. I tested this, and it doesn't work. This is the beginning and the end of this.
I'll say that the collection performance of an environment is usually really important for overall system performance. Collections being one of the most common data types.
Hi Ayende,
I wrote a little collection for you. It is based upon the F# Map. I believe it satisfies your requirements:
http://fssnip.net/l8
However, it sounds as though you want a concurrent dictionary like the ConcurrentDictionary provided with .NET. That provides stronger thread safety guarantees than my HashMap and it is slightly faster. If so, immutable collections are a red herring.
Cheers, Jon.
Jon, That is great, except for the fact that you are not doing immutability. You are replacing the mapped value in the array.
That means that if you have:
Tx 1 -> Get the page table Tx 2-> Modify the page table Tx 1 -> Read from page table
Tx 1 will see the changes made by tx 2. And I don't need concurrent dictionary, I need Tx 1 to have a stable and fixed view of the world.
I see. I misunderstood your requirements. You want readers to have a snapshop of the dictionary that doesn't change when subsequent writes are done.
If I've understood your requirements correctly this time, you can actually solve your problem using a concurrent dictionary as well. Specifically, you can use time-stamping to maintain a time-line for each key. The concurrent dictionary maps from key to timeline and the timeline maps from timestamp to value. Reading the latest version from a timeline can be O(1) so you're really only paying for the read in the concurrent dictionary which is relatively fast.
I've written a simple implementation here and it appears to be 10x slower than a Dictionary at writing and 2.5x slower at reading. In comparison, your linked dictionary is 4x slower at writing and 16x slower at reading. I believe you are interested in read performance more than write performance so this concurrent dictionary of timelines approach might be of interest...
Cheers, Jon.
This highlights an issue we are trying to be address with NPerfRunner (https://github.com/Orcomp/NPerfRunner).
NPerfRunner and NPerf.Fixtures (https://github.com/Orcomp/NPerf.Fixtures) in particular is intended to be project maintained by the community to keep standard performance fixtures that are fair and unbiased. And allow new implementations of an algorithm or datastructure to be compared against existing ones with minimal effort.
The is already an IDictionary fixture implemented (https://github.com/Orcomp/NPerf.Fixtures/blob/master/src/NPerf.Fixture.IDictionary/IDictionaryPerfs.cshere), which should cover most cases discussed here. If anyone is interested in extending this fixture or adding new methods to compare, please send us a pull request.
Comment preview