Loyc.Collections comparison?

[qwertie]

Hmm, I wonder if you were aware of Loyc.Collections when you started this project. I don't see a discussion in the readme of what kind of implementation you used, so I kind of wonder if it's the same as mine.

My collection types are mostly "semi-persistent" data structures, making them a bit different than standard persistent data structures - fundamentally more powerful, but possibly a bit slower in their immutable mode. I expect them to be faster than immutable data structures when used mutably, though. I'm curious if you'd be interested in adding Loyc.Collections to your benchmark comparison.

[dadhi]

@qwertie Hi there,

I don't see a discussion in the readme of what kind of implementation you used

I am using AVL trees (in the current version) with some optimizations to minimize memory traffic when re-balancing the tree.
Plus when adding the value I am creating the entry once - it won't be destroyed when adding the new entries or during the rebalance. That's mean the entry is fixed in memory, so I may assign the actual entry value later or CAS swap the value if needed. And that lessens the immutability of the structure but provides the useful feature of faster entry addition, and the immutability is still here if you need to, just don't assign the value directly.

But... in the newer version, I am switching to the 2-3-4 tree variant, which is more memory efficient (no need to store the Height for the balancing) and has a more straightforward addition implementation. Plus it has more fan-out property storing more than 1 entry per node.

I'm curious if you'd be interested in adding Loyc.Collections to your benchmark comparison.

What will be the better collection e.g. BDictionary<K,V> to compare? I am using the Type as the key for benchmark, the type of value is a string but it should not matter.

[qwertie]

AVL trees, eh? Should use significantly less memory than the red-black trees in SortedDictionary - they put a bool in their node class which is a big deal for memory usage, as it consumes 64 bits on a 64-bit processor. (edit: duh, my memory failed me, AVL also requires an integer height field per node.)

My collections, truth be told, were optimized more for low memory consumption (and flexibility) than speed - possibly due to some trauma I suffered in the DOS 640K era? Low memory is a major strength of B+trees, which the A-Lists are based on. But I did put some effort into performance as well.

If you've set up your benchmarks appropriately (whether it be with a test function that accepts IDictionary<K,V> or some LeMP-generated code to avoid interface-call overhead) it should be straightforward to test multiple collections with the same piece of code... I guess I would like to see benchmarks of VList/WList (if you are doing any IList benchmarks), BDictionary and the hash tries Set<T>, MSet<T>, Map<K,V>, MMap<K,V>. But here's a summary of the main collection types. This summary ought to be on my own web page, come to think of it:

IList<T> implementations

• AList<T>: O(log N) insert, delete, indexer. Slower than List<T> except for insert/delete in random locations in a large list. There is a variant IndexedAList<T> that sacrifices both memory and speed in exchange for fast mapping from items to their index in the list. Optimized for large lists. Sacrifices some speed for flexibility.
• SparseAList<T>: similar to AList<T> but can have "empty spaces" between elements, which don't consume memory and appear to have default(T) as their value
• VList<T>: an immutable data structure invented by Phil Bagwell. My implementation pretends to be mutable (struct implementing IList<T>) and remains the basis for Loyc trees, but I never bothered to benchmark it. I don't expect great performance from it due to a memory-saving optimization for small lists that is only necessary in the first place due to limitations of .NET, i.e. if I were writing this in C++ it would run obviously faster.
• WList<T>: the mutable class form of VList<T>. Conversions between WList and VList are O(1) with COW behavior
• InternalList<T>: specialized alternative to List<T>, slightly less memory + slightly faster in special cases.*
• DList<T>: optimized for use as a circular deque, 2x as fast as List<T> for random insertion/delete when list is large.*
  * InternalList and DList are in Loyc.Essentials rather than Loyc.Collections.

ISet<T>/ISetImm<T> implementations

• Set<T>: immutable set (hash tree with fan-out of 16); mutator methods return a new version
• MSet<T>: mutable set. Conversions between Set and MSet are O(1) with COW behavior

IDictionary<K,V> / persistent dictionary implementations

• Map<K,V>: immutable map (hash tree with fan-out of 16); mutator methods return a new version
• MMap<K,V>: mutable set. Conversions between Map and MMap are O(1) with COW behavior
• BDictionary<K,V>: a sorted mutable dictionary with O(1) cloning and ability to Freeze(). Using this type as if it were an immutable dictionary, by cloning it after each modification, is not particularly efficient due to the large-ish node sizes; it's more efficient if you change several elements between each call to Clone(). To some extent, this holds true for Map/MMap/Set/MSet also. This type also trades some speed for flexibility (it is not just a dictionary but also an IReadOnlyList<KeyValuePair<K,V>>, and it has a change notification event, and did I mention the freezable COW?)
• The Compact Patricia Tries implement IDictionary<K,V> for specific types of K (CPIntTrie for long, CPStringTrie for string, CPByteTrie for byte[]). CPTries are hybrid set/map types (more efficient set behavior is obtained when most/all values are null). They are ideal for holding very large collections of URLs in memory, due to their ability to adaptively share common prefixes. Depending on the data distribution, it may also be very memory-efficient for large collections of integers. However, due to limitations of .NET, CPTries are not particularly fast. This type is located in Loyc.Utilities rather than Loyc.Collections.

Other

• BList<T> - a sorted bag (duplicates are allowed)
• BMultiMap<K,V> - a sorted bag of key-value pairs which uses less memory and is much more convenient to use than the alternative, SortedDictionary<K, List<V>>. Like BDictionary and AList, BList and BMultiMap sacrifice some speed in order to provide more flexibility to the user.

This list leaves out the adapters such as Bijection<K1,K2>, MaxHeap<T>, DictionaryWithChangeEvents<K,V> and ListSlice<T>, which wrap around other collections.

[qwertie]

when adding the value I am creating the entry once - it won't be destroyed when adding the new entries or during the rebalance.

In a standard "immutable" (persistent) collection, I don't see how this works. I mean - I haven't looked at your API so this is pseudocode -

var d1 = new ImmutableDictionary<int,int>();
var d2 = d1.With(5, 5);
var d3 = d2.With(1, 1);
var d4 = d3.With(9, 9);

if (5,5) is the tree root, in d2 it has no children, in d3 it has one child and in d4 it has two children. So it seems you need to create three nodes containing (5,5). No?

[dadhi]

@qwertie

So it seems you need to create three nodes containing (5,5). No?

Yes and No - there is the Tree Node with {Entry, Left, Right, Height} and there is the Entry with { Hash, Key, Value }.
The entry once allocated won't change:

So in the pseudocode:

var d1 = new ImmutableDictionary<int,int>();
var e = new Entry<int, int>(5);
var d2 = d1.With(e);
var d3 = d2.With(1, 1);
// later
e.Value = 5;
// or better
Interlocked.Exchange(ref e.Value, 5);

There is other API sugar to help, e.g.:

var d2 = d1.With(5); // create the entry with key/hash 5 and the default value.

// later when we want to construct the value we don't need to modify the tree anymore... 
// making the tree updates independent and fast
var e = d2.GetSurePresentEntry(5);
Interlocked.CompareExchange(ref e.Value, CreateValue(), 0); // or do other types of optimistic updates or retries

[qwertie]

I think you're saying only keys are immutable, not values?

Anyway, after writing out my list of collection classes I realize they'd all lose to yours under the conditions of your benchmark... so I withdraw my suggestion to test them. Your benchmarks stop at 10,000 but for the ALists (including BDictionary), 10,000 is where they hit their stride. BDictionary shines as a mutable type at a million elements:

Even when I optimized for small lists, I tended to optimize for size rather than speed... take the VList<T> used in Loyc trees, for instance. In Loyc trees, the most common list sizes are 0, 1 and 2, and I envisioned people would use them for large projects with perhaps millions of nodes held in memory at once, so I wanted to limit small lists to a single heap object (or 0 heap objects for 0-size lists) which meant my node class couldn't use an array (as the array would live in a separate heap object than the root node). Of course, the reality was nothing like that, after eight years nobody's got a million LNodes in memory at once. So I expect to pay a speed penalty for using a specialized two-item heap object without an array and I totally earned it, haha.

[dadhi]

@qwertie I also wanted to note that the implementation is really matter. Despite that AVL trees are used by me, by Microsoft BCL Immutable collections and also by F# Map type, the benchmark shows the difference. I myself have switched 3 or 4 implementations, improving both speed and memory.

[dadhi]

Though ultimately I am targeting the collections with less than 10000 items.
I don't see the immutable structures to shine beyond that - allocations are starting eating the performance.

Also, I am optimizing for the even smaller collections - so the map with 10 items should hold less and operate faster than the 100 items map.