fsharp/fsharp — pull request #219 by jack-pappas (2013-12-27 19:27:27+00:00)
Title: Optimized Map and Set implementations

I've heavily modified the implementations of the underlying data structure (AVL tree) and corresponding operations for the F# `Map` and `Set` types to increase their performance. Importantly, the public-facing members and module functions are identical to the existing implementation, and this implementation also passes all of the unit tests provided in `src/fsharp/FSharp.Core.Unittests`.

I implemented some very basic benchmarks to compare my optimized implementation against the existing implementation and some other immutable collection implementations; you can run these yourself by cloning the [jack-pappas/fs-core-optimized](https://github.com/jack-pappas/fs-core-optimized) repository and building/running the PerfComparison project. The benchmark is randomized and not currently designed for repeatability, so results vary from run-to-run, but I've run it several times and posted the results here: https://gist.github.com/jack-pappas/8049561

A quick run-down of the optimizations I've implemented:

* When inserting an element which already exists in the tree, the existing implementation creates a new tree anyway. This inhibits performance because it puts unnecessary strain on the GC and requires the balancing checks to run when rebuilding the tree; also, by creating new trees each time, the existing implementation is unable to effectively take advantage of structure-sharing optimizations (more on this below). This optimized implementation only creates a new tree when inserting/deleting/modifying an element would actually alter the tree. This optimization makes set-based operations (e.g., `insert`, `union`, `difference`) much faster for cases where the sets overlap.
* This implementation takes advantage of the aforementioned structure-sharing optimizations by using reference/physical equality checks to implement equality/comparison functions which are *much* faster in certain cases (specifically, where one instance has been derived from another instance, so they share some/all of their underlying tree). Along with a few other small optimizations to the comparison functions, this optimization greatly improves the speed of nested sets (i.e., `Set>`).
* The existing implementation uses 3 node types, while the optimized implementation uses 2. By eliminating the node type representing a single element, we can take advantage of the F# compiler optimization which represents a nullary case with the `null` literal. This makes the `match` statements in the code faster, since they can be implemented by a simple null-check (a single instruction on most CPU architectures).
* The fields in the `Node` case have been re-ordered so that in most cases, the field layout will be more efficient, reducing the number of packing bytes needed to align the fields correctly and allowing for more efficient (i.e., faster) CPU instructions to be used to fetch them from memory. Note that reducing the size of the nodes in memory also allows more of the tree to stay resident in the CPU cache, which also helps to increase performance (especially when paired with the structure-sharing optimizations).

One other improvement I've included here is that the debugger proxy types for `Map` and `Set` now return a simple array of `KeyValuePair<_,_>`, just like a number of the built-in .NET collection types. This has a *huge* advantage, in that it makes the contents of a `Map` or `Set` much easier to inspect within the Visual Studio debugger (and probably the Xamarin Studio / MonoDevelop debuggers too). As far as I can tell, there is no loss in performance either, and I've tested it with some reasonably large `Map` and `Set` instances (10k+ elements).