implementation details? Are there some operations that are slow?

[bjoli]

Hi there!

I have been fiddling around with the immutable collections, and one piece of code (that ended up being my fault!) was very slow. That made me go looking for implementation details to get some kind of overview of how the data structures work, just to be certain I didn't do the language-ext version of python-people-making-lisp-code-quadratic.

I couldn't find any except for reading the code. Are there any resources that I missed?

Best regards
Linus

[louthy]

Not completely sure what you're asking here? Are you asking for implementation details? Or general information on immutable data-structures? You mention 'immutable collections', are you talking generally, or about the immutable collections in language-ext, or the Microsoft ImmtuableCollections library?

Some general info on the language-ext immutable collection types:

• The last time I checked, language-ext has the most optimal immutable collection types in the .NET ecosystem (You can run the LanguageExt.Benchmarks to compare them against Microsoft's ImmutableCollections -- I haven't run them for a while, but we should still be good)
• The most optimal list type is Seq<A>
• The most optimal set type is HashSet<A>
• The most optimal key/value type is HashMap<K, V>
• Seq<A> is (I believe) a unique approach to immutable list design, which can approach mutable list speeds for transformation (adding and consing) and iteration.
• HashSet<A> and HashMap<K, V> uses the CHAMP trie hash map data structure (Compressed Hash Array Map Trie), which is state-of-the-art
• Set<A> and Map<K, V> use AVL trees, so are not as good in terms of cache locality, but are obviously sorted trees, which have ordered-read performance benefits.
• Lst<A> also uses an AVL tree. This makes it very good for insertions, but nowhere near as fast as Seq for everything else. So, only use Lst<A> if you need to do insertions in the middle of a sequence.
• Arr<A> is a simple immutable wrapper around C# mutable arrays. I've started adding slicing, adding, consing, and other transformational behaviours. But, transformations can be expensive if each operation needs to generate a new backing array: so you should only transform arrays if either the arrays are small or performance isn't important.
• Seq<A> can be both strict and lazy. When a lazy Seq<A> is consumed, it caches its values, which means you can't use it for infinite lazy streams. For infinite lazy streams, use Iterable<A>. It's billed as a better IEnumerable. I am currently doing an overhaul of it, so that it supports boths synchronous and asynchronous lazy streams. Overall it should have similar performance to any other lazy stream with plenty of additional bells and whistles (like trait implementations).
• IterableNE<A> is another collection I'm working on right now, which is a non-empty version of Iterable<A>.
  • If I find bandwidth, I'll do non-empty versions of all the collection-types where it makes sense.
• RefSeq<A> this is another collection that I'm working on. It's currently in the stack-parsec-prototype - it is implemented in the same way as the strict Seq<A> type, but with the backing data all stored entirely on the stack (ref struct). This will allow for unbelievable performance, but still work like a regular immutable type.
  • I'm going to try and bring in more of this to-the-metal functionality (like the stack based parser-combinators)
• Then there's the streaming structures which have varying levels of abstraction. Which I can go into if you like?
• There is a wiki entry that discusses performance and has some benchmark results for the main collection types. I have pasted the relevant section below...

Immutable AVL trees

Some of the collection types in language-ext use a self-balancing AVL tree as its backing store. They are:

• Set<A>
• Map<A, B>
• Lst<A>

Immutable AVL trees work by only updating the nodes in the tree that are directly affected by an insertion or deletion.

If you have a root A and two child nodes to the left and right of B and C respectively then adding D to the tree (which should be assigned to the right of C) will create a new C with the updated reference to D and then create a new A with an updated reference to the new C. The B branch is unaffected.

This means that the total cost of insertion or removal is n allocations where n is the depth of the tree (it's a self balancing tree so it's a function of the number of items in the tree). And so there is some cost to transforming an immutable tree structure, but it's not true that an entirely new tree needs to be built for each operation.

Iterating and reading of any of the immutable AVL backed structures will be as fast as doing so with the mutable versions in the BCL (Dictionary, SortedDictionary, HashSet, etc.)

Note also that that all of these AVL backed types can be initialised with an IEnumerable of any flavour and the initial tree will be built (in the constructor) with mutable tree that becomes locked (immutable) before you get the reference back from the constructor. This allows for a very efficient instantiation of the relevant collection.

Compressed Hash Array Map Trie (CHAMP)

HashMap<K, V> and HashSet<A> are, by far, the most efficient key based collection types. Internally, they use the state-of-the-art Compressed Hash Array Map Trie (CHAMP) data structure. It brings some significant performance gains over Microsoft's System.Collections.Immutable.ImmutableDictionary<K, V> which is the closest type to the lang-ext HashMap.

Type	10,000 Add operations	10,000 random access operations	Enumeration of a 10,000 item collection
HashMap<K, V>	200 ns / op	1 ns / op	1 ns / op
ImmutableDictionary<T>	700 ns / op	1 ns / op	100 ns / op

Type	100,000 Add operations	100,000 random access operations	Enumeration of a 100,000 item collection
HashMap<K, V>	500 ns / op	80 ns / op	100 ns / op
ImmutableDictionary<T>	1160 ns / op	60 ns / op	180 ns / op

Type	1,000,000 Add operations	1,000,000 random access operations	Enumeration of a 1,000,000 item collection
HashMap<K, V>	651 ns / op	72 ns / op	63 ns / op
ImmutableDictionary<T>	1402 ns / op	93 ns / op	204 ns / op

The closest type in the BCL is Dictionary<T> - which still outperforms the HashMap type, but I think you can see we're looking at high performance types here. It is especially the case when the collection sizes are below the 65,536 range. They're fast at all sizes, but has outstanding performance for what is the most common use-cases. Even for the heavier and most difficult use case (millions of add operations), we're still seeing 1.5 million operations per second.

Lst<A> and Seq<A>

You should always use Seq<A> for the maximum performance. The only time that doesn't make sense is if you need to transform a list by setting or inserting an element at an index which isn't 0 or the end of the collection. Because Lst<A> uses an immutable AVL tree behind the scenes insertion can be done without incurring a big cost (see the previous section). However, Seq<A> uses a contiguous array that can only be appended or prepended to. This is great for cache efficiency when iterating over a large number of items (which is where AVL trees suffer).

Adding new items to a Seq<A> can cause the array to fill up and so when that happens it generates a new array, double the size, and copies the old array to the new - leaving enough room to grow into. This obviously has a cost to it, but I'd say this is the accepted method of doing a list in .NET as this is the way that List<T> works in the BCL. If you have two separate references to the same Seq<A>:

   var x = Seq(1,2,3,4,5);
   var y = x;

... and append or prepend items to both references:

   x = 0.Cons(x);
   y = 1.Cons(y);

... then the second append or prepend will clone the Seq (maintaining the immutable integrity of the collection).

After that cloning, future operations on either Seq will have their own internal arrays, no sharing. This can be seen as branching of the structures.

Seq<A> compared to System.Collections.Generic.List<T>

In terms of outright performance List<T> from the .NET BCL (which isn't thread-safe) is about twice at fast at adding items (if you use Cons for the Seq<A>, three times if you use Add). Cons is super-slow with List<T> though, I assume it's not optimised for this, so we won't hold it against it, although I suspect most people don't realise how poor the Insert performance is for List<T>

System.Collections.Generic.List<T> cons equivalent is Insert(0, x).

Below is a table that shows the relative performance per-operation for each type.

Type	Add	Cons | Insert(0,x)	Enumeration
Seq<A>	29.5 ns / op	20 ns / op	10.0 ns / op
List<T>	11 ns / op	10320 ns / op	16.1 ns / op

This is pretty amazing for an immutable, thread-safe, lock-free, type that can support appending and prepending with very similar performance benefits to List<T> as well as supports at-most-once lazy streaming. We're still looking at 33-50 million write operations per-second and enumeration that's faster than the mutable counterpart.

One thing to note is that Seq<A> also supports laziness. If you're enumerating a lazy sequence then you're looking at 54 ns / op, or about 18.5 million operations per-second. Once the lazy stream has been enumerated once then it is cached and will have the same performance as the table above.

[bjoli]

Sorry. English is not my first language. I am curious about implementation details of the various data structures in language-ext. AVL trees and CHAMP (cool. Mad respect!) is enough for me to know when I should use them. But Seq? Seq is backed by an array. Ok, now I know that. What happens if I have a Seq of huge items, take the tail or skip a few items and let the old reference be garbage collected. Are the unused elements cleared in some way? Is the Seq copied if I assign the tail to a different variable?

These are perhaps dumb questions, but they are good examples of the kind of information I tried to find. I don't want to write code by guessing the performance characteristics of the code. Even the most general data structures have gotchas. Like, how is thread safety ensured? Does it limit conses to the same thread ID? If so, how does it work with async flows where you might end up on a different thread?

These are the kind of questions I would like to be able to read about before having to figure them out when I already have 10k lines of code. Edit: oh, and that enumeration benchmark comparison, is that with foreach? That forces generation checks, and makes foreach on lists slow ( and to my knowledge, these check cannot be elided). If you know you are not mutating the list from under you, a regular for loop is a LOT faster. You can iterate over deep trees faster than you can foreach over a List

Once again, mad respect for writing a CHAMP hashmap. I tried implementing them after reading the Steindorfer and Vinju paper in 2016, but could never figure the kinks out.

Best regards
Linus

[louthy]

Once again, mad respect for writing a CHAMP hashmap. I tried implementing them after reading the Steindorfer and Vinju paper in 2016, but could never figure the kinks out.

Yeah, it's quite hard to get it right and then to optimise it [to the extent I have done] makes the code pretty damn ugly.

Hence the warning:

///////////////////////////////////////////////////////////////////////////////////////////
//
// NOTE: Here be dragons!  The code below is has been optimised for performace.  Yes, it's 
//       ugly, yes there's repetition, but it's all to squeeze the last few nanoseconds of 
//       performance out of the system.  Don't hate me ;)
//

So, I hope I never need to change it!!! ;-)

But Seq? Seq is backed by an array. Ok, now I know that. What happens if I have a Seq of huge items, take the tail or skip a few items and let the old reference be garbage collected. Are the unused elements cleared in some way? Is the Seq copied if I assign the tail to a different variable?

With Seq<A> I keep meaning to write a paper on it, it is novel (I believe), but I haven't done enough digging to see if there's prior art. I take inspiration from the way the mutable System.Collections.Generic.List<T> works in the .NET Framework. It is also backed by an array that starts off small and then doubles in size (and copies) as the backing array runs out of space. You get exponentially further away from the next expansion boundary each time. So the 'grow events' become less frequent.

The benefit of the System.Collections.Generic.List<T> approach is cache locality. Everything is in an array and so iteration is as fast as it can possibly be. The downside is the doubling and copy events, which although pretty fast overall, are much slower than the regular add cost. And insertions are extremely slow in List<T>. Presumably, Microsoft have put a reasonable amount of effort into deciding the best 'most general' list, so presumably this is 'state of the art' in terms of a general purpose mutable list.

The other approaches to lists: linked-lists or binary-trees have poor data-locality. Singly linked-lists are OK for consing, but not adding (or vice versa), it's extremely fast to create a new list-node, but we have no control over where the node is allocated. , Doubly-linked lists are problematic for immutable structures. And binary trees are slower to add or cons a new node and gets slower as the list grows, has locality issues, but does support insertions.

It's not possible to take that mutable 'doubling array' concept directly into the immutable world, because it requires a backing-array that mutates in-place as the list grows. We don't want to have to clone the entire array on every Add or Cons.

I make a few assertions about working with lists (either mutable or immutable):

1. The vast majority of list processing happens on a single thread.
2. The vast majority of list processing is of relatively small lists (say, less than 100,000 items).
3. The vast majority of list mutation (transformation) is via prepending (consing) or appending.
4. The majority of lists (even immutable ones) are processed beginning to end or via random-access. That is, there's less sharing of immutable heads.
   • This is less true than 1, 2 and 3, but still enough of a truism that we should take it into consideration when optimising.

So, if head sharing and cross-thread head sharing is rare, but iteration and random access is common, then optimising for that makes sense. And optimising for appending and consing should be the priority on the mutation (transformation) side.

That's Seq<A>. It takes all of those into account an optimises for the most common use-cases (the System.Collections.Generic.List<T> of language-ext).

When a Seq<A> is constructed, it starts off with a small backing array: A[8]. The first element goes at index 4. Positions 3, 2, 1, and 0 will be where Cons values grow into (like a mutable list) and 5, 6, 7, will be where the the Add values are inserted.

Each Seq<A> structure has a flag for CanAdd that is Interlocked.CompareExchanged when you perform an Add(value) operation on the structure. If the CompareExchange succeeds, then it means nobody has ever done an Add operation on the Seq<A> before. And so, we can just mutate the backing array, lock the structure, and create a new Seq<A> with the same backing array, same start index, and an updated count (+1).

So, other than the time taken in the CompareExchange, this means adding an element to a Seq<A> is as fast as adding an element to a mutable list. So, you could imagine building a list in a loop, adding, adding, adding, ... and each time we're just mutating an array in-place.

There is an equivalent flag for CanCons, which follows the same pattern. So each end of the Seq<A> has its own 'lock'.

The thing to be aware of: if you Add or Cons to a Seq<A> that has already been added to or consed. Then a clone of the Seq<A> must be made before performing the Add or Cons to maintain the immutable semantics of the type.

So, the call I've made here is that we are much more likely to be repeatedly adding to a constantly updating Seq<A> head rather than continually applying Add or Cons to the same head.

A same head Add looks like this:

var xs = toSeq(Range(0,1000000000)).Strict();  // Create a billion item sequence
var ys = xs.Add(1);                            // Very fast
var zs = xs.Add(1);                            // Needs to clone the original backing array before adding 

The other hits are the array doubling as the backing array runs out of space. The alternative is Lst<A> which is an AVL tree, it has similar performance to Microsoft's ImmutableList<T> and doesn't have growing events or cloning events, It is more consistent overall, but generally slower, whereas Seq<A> is much faster the most common use-cases with occasional spikes for less common use-cases.

What happens if I have a Seq of huge items, take the tail or skip a few items and let the old reference be garbage collected.

The backing-array will be shared with the new instances. The only way the old backing array will be dropped is if subsequent usages of the tail or skip instances cause a grow-event or clone-event, orphaning the original reference.

You could avoid this by cloning the instance. For example:

var xs = toSeq(Range(0,1000000000)).Strict();  // Create a billion item sequence
var ys = xs.Take(1);                           // Even when `xs` goes out of scope, we still have a
                                               // reference to a billion-item backing-array.

Seq<int> zs = [..ys.AsSpan()];                 // Clones just the elements you're using
                                               // allowing old references to collect

Are the unused elements cleared in some way?

No, adding a destructor to Seq instances would be problematic for shared usage. The only list structure which would automatically drop unused elements would be Lst<A>.

Is the Seq copied if I assign the tail to a different variable?

No.

Like, how is thread safety ensured?

Through atomic updates using Interlocked.CompareExchange.

Does it limit conses to the same thread ID?

No.

If so, how does it work with async flows where you might end up on a different thread?

The thread is completely irrelevant, as with all immutable data-structures, the only thing to be aware of is the cloning that happens when adding or consing to the same head (as detailed before). So, if you're creating 10 threads and sending the same Seq<A> to each, then you can iterate them as fast as a mutable collection, you can perform random-access as fast as a mutable collection, but if you Add or Cons, then the first Add and Cons will be cheap, but the second thread to do so will incur a cloning cost.

Again, you could chose to use Lst<A> in that scenario.

So pick your poison basically!

Apropos of nothing, I have an idea for a potential improvement to Seq<A> and that is to manage multiple-arrays, all calculated to be up to the current OS page-size. Then they could still benefit from locality, but also allow for more efficient cloning (you'd only ever have to clone that maximum of one-page), and would allow for GC culling of old pages.

It's a more complex structure, but might pay dividends. It is straying away from the core ideas of Seq<A> though, so this may even be a better Lst<A>, it would have to be an n-tree structure rather than a binary-tree. Anyway, food for thought, if I ever get the time.

Optimisation is a bit of a nerd passion of mine (which may be surprising coming from someone so into pure functional programming). I am particularly fascinated by how to make pure functional programming as close to imperative performance as I can make it. So, I'm always open to ideas, as long as the surface remains elegant and easy to use.

[bjoli]

This is the kind of info I wanted. Thank you. Had I started using this as a list in scheme or f sharp, that shared array backing would most certainly have me creating a memory leak soooner or later :)

Thank you for taking the time to answer me.

[HernanFAR]

Reading the questions and answers this discussion make me feel again like my first year in the software world but in a very good way. I feel like a child in a big world with rivers and lakes to explore.

I mostly have practical experience because I just have the basic formal training from when I was in the equivalent of "high-school" in Chile, around 2014 to 2018. It was a "Telecommunications Medium Technician", but they did touch Programming topics, specificly web and I fell in love with it. After that I started working inmediatly in software development, and learn a lot until 2024, when a was feeling that I get too close to the celling.

And maybe I did, but only in Chile. I throught that Vertical Slices Architecture, Domain Driven Design and a very Object Oriented Programming thinking was the answer to the even the most difficult/complex problems or workflows that my clients have send me. I think that I'm good enough in domain modeling, use case understanding, workflow composing, managing technical debt, making code that works, but also reads, feels and seems good.

But I was feeling trapped, I was still feeling that the celling was to close to me. Until I get to this repository, and slowly the rules of the game change. Learn about functional programming, and more "formal-concepts" with this library is definitly an experience that I recommend.

It may be a little light (it's a big one to me), but this discussion is a very good start-point to do a deep research of more "theorical" concepts (like concurrency, performance) and the ussual problems that programmers have when getting "las manos en la masa" and how more experienced people resolve those problems, for people in a similar context of mine this repository can be even game changing

Merry christmas @louthy, you're an inspiration, and currently my inspiration.

[louthy]

Merry christmas @louthy, you're an inspiration, and currently my inspiration.

@HernanFAR Wow, that's extremely kind of you, and your story is actually quite close to my own. Especially the moment of enlightenment.

I think to a certain extent you need to have the scars and the war stories of real-world software engineering to have that enlightenment. You can think functional programming is right because of something you learned at college, or you can think it's right because suddenly everything starts to 'feel right' in real-world code. It takes a bit of time to get your brain to switch to FP thinking 'by default' after being in the imperative mindset for so long, but eventually you think FP first, and that's when everything becomes easier.

In terms of performance work, that's completely different story, and very much my 'origin story' of writing 6502 assembler on my first 8-bit computer (2 Mhz CPU with 32k of RAM) back in 1985. You had to understand the machine at a fundamental level to get the best out of it. I took that into a career in the games industry where I needed to squeeze the last few nanoseconds out of a Playstation, or whatever console I was writing an engine for. You gain an intuition for performance tuning, outside of the standard Big-O complexity notation, which is hard to come by any other way than just doing ... over and over again.

I do get a buzz from tweaking the algorithms and data-structures to squeeze the last bit of performance out of the machine. But, if the past two decades of building a 10 million+ line SaaS app has informed me of anything, it's that code complexity creeps up on you and is then quite hard to solve. The most important thing is to have maintainable code. Outright performance at the expense of maintainability is often a fools errand.

Obviously, with a library like this, I need to try and achieve both... which isn't always easy! But hopefully my effort translates into more maintainable code for everyone that uses this library, it's what I started the project for.

Anyway, thanks again for the kind words. Merry Christmas to you too 👍

[HernanFAR]

Yeah, a library performance is pretty important, but maintainable code is even more. Thats what I like about this library, is so full of small and-not-so-small yet powerful features that can be composed in million ways! My brain just does not stop giving me ideas of what can I do, and I like that

I'll feel again the complexities of making something by myself soon. I'm learning Language-Ext not only because of Functional Programming, is because I was developing a framework to my company. It's specialized in the way that we work in my company using dotnet, so... kinda like the afore mencioned patterns (CQRS, DDD, Vertical Slices) with mostly tactics and styles of mine ('cause I'm the most experienced of the crew, so most of them are in training with me, trained by me or just influenced).

But... I'm the kind of person that if we need to refactor the whole app to acomplish the objetive, we hare going to do that. So, in short, I did 3 major refactorings in the source code, and since I start learning this library, the development is in stop until I get it right. With my current knowledge of this library I might be ready for a 4th one, but I doubt that

Also, I kinda want to finish a almost all of my ideas for domain-monads for basic yet-atomic actions to rapidly compose full use cases with ease, but with the segurity that compiler errors give instead of runtime exceptions or brain errors, but free time is not my highest number

Anyway, thanks for your time Louthy, have a very nice day :)