3 ms·

> so it performs almost on par with the mutable dictionary. I notice you have a comment that says "This trie is now the fastest immutable dictionary I'm aware

by louthy 4y ago

> so it performs almost on par with the mutable dictionary. I notice you have a comment that says "This trie is now the fastest immutable dictionary I'm aware of". Unfortunately I have to make you aware that my implementation is faster, sorry! ;) Here's the add-items benchmark: BenchmarkDotNet=v0.13.5, OS=Windows 11 (10.0.22621.1265/22H2/2022Update/SunValley2) AMD Ryzen Threadripper PRO 3995WX 64-Cores, 1 CPU, 128 logical and 64 physical cores .NET SDK=6.0.300 [Host] : .NET 6.0.5 (6.0.522.21309), X64 RyuJIT AVX2 DefaultJob : .NET 6.0.5 (6.0.522.21309), X64 RyuJIT AVX2 | Method | N | Mean | |-------------------------- |------- |---------------:| | SysColImmutableDictionary | 100 | 32.315 μs | | SasaTrie | 100 | 8.007 μs | | SysColDictionary | 100 | 1.440 μs | | LangExtHashMap | 100 | 7.512 μs | |-------------------------- |------- |---------------:| | SysColImmutableDictionary | 1000 | 524.368 μs | | SasaTrie | 1000 | 140.537 μs | | SysColDictionary | 1000 | 17.395 μs | | LangExtHashMap | 1000 | 125.663 μs | |-------------------------- |------- |---------------:| | SysColImmutableDictionary | 10000 | 7,598.532 μs | | SasaTrie | 10000 | 2,055.220 μs | | SysColDictionary | 10000 | 301.683 μs | | LangExtHashMap | 10000 | 1,842.514 μs | |-------------------------- |------- |---------------:| | SysColImmutableDictionary | 100000 | 129,811.705 μs | | SasaTrie | 100000 | 46,752.702 μs | | SysColDictionary | 100000 | 6,103.999 μs | | LangExtHashMap | 100000 | 37,869.597 μs | * SysColImmutableDictionary = System.Collections.Immutable.ImmutableDictionary * SysColDictionary = System.Collections.Generic.Dictionary My other benchmarks are still running, so I won't share them all, but we actually trade blows, your ContainsKey appears to be faster, my collection iteration is twice as fast as yours. I suspect if I removed my struct wrapper it would be a bit quicker, but wouldn't be a real-world fair comparison. We're both much faster than Microsoft's ImmutableCollections though! I am certainly interested in what that technique is with the nested Node<Node<Node<Node<... and why it works. Do you have any more detail on that? You might also want to look into the data-structure I use: CHAMP [1]. I notice you use HAMT, CHAMP is a more efficient version of HAMT. It has better data-locality, which is much more efficient especially when working with value-types. With regards to the 'deriving' question: Yeah, I'm working on a more general solution now, as well as a way to do monad-transformers properly. I've also figured out a way to do infinite tail-recursion for my monadic types, which I'll be deploying in the next major update. [1] https://michael.steindorfer.name/publications/phd-thesis-efficient-immutable-collections.pdf https://michael.steindorfer.name/publications/phd-thesis-eff... * EDIT * Here's the full suite of benchmarks, but I've trimmed them down to just the 10,000 item tests and removed the error and deviations for clarity: +-----------------------+----------------+ | Add 10000 items (value type) | +-----------------------+----------------+ | SasaTrie | 2,055.220 μs | | LangExtHashMap | 1,842.514 μs | +-----------------------+----------------+ | Add 10000 items (reference type) | +-----------------------+----------------+ | SasaTrie | 2,988.663 μs | | LangExtHashMap | 2,905.552 μs | +-----------------------+----------------+ | ContainsKey (10000 value items map) | +-----------------------+----------------+ | SasaTrie | 173,215.0 ns | | LangExtHashMap | 235,577.2 ns | +-----------------------+----------------+ | ContainsKey (10000 reference map) | +-----------------------+----------------+ | SasaTrie | 518.789 μs | | LangExtHashMap | 549.952 μs | +-----------------------+----------------+ | Iterate (10000 value items map) | +-----------------------+----------------+ | SasaTrie | 457,819.0 ns | | LangExtHashMap | 227,632.7 ns | +-----------------------+----------------+ | Iterate (10000 references map) | +-----------------------+----------------+ | SasaTrie | 712,623.1 ns | | LangExtHashMap | 519,250.7 ns | +-----------------------+----------------+ | Random remove (10000 value items map) | +-----------------------+----------------+ | SasaTrie | 2,276,772.4 ns | | LangExtHashMap | 1,765,042.9 ns | +-----------------------+----------------+ | Random remove (10000 references map | +-----------------------+----------------+ | SasaTrie | 2,946.775 μs | | LangExtHashMap | 2,576.813 μs | +-----------------------+----------------+

deleted 4y ago
[deleted]
naasking 4y ago
Nice! I'm away for the weekend so will follow-up with an explanation of the nested generic when not on the phone if the following is unclear: the basic idea is that you inline the next level of the Trie into the previous level, thus collapsing the depth and removing some indirections. This slightly bloats the internal tree nodes but the leaves vastly outnumber the internal nodes, and since the leaves have been inlined one level up, it ends up compacting it somewhat. This is maybe clearer when starting with a struct-only design for the internal nodes and then performing the inlining as an optimization on that. Also wondering whether you checked the Trie from the latest repo or the older struct version I also linked. I think the struct version was a little faster but I switched for the aforementioned idiomatic reasons. I'll have to check out the CHAMP design for sure, I'm curious how it differs. Edit: I also recall that I didn't optimize iteration at all and that it was fairly inefficient, but can't really confirm now. I recall optimizing merge carefully though so that should perform well. Edit 2: forgot to mention that Node<...> generic is nested 6 times because that's the max depth of the trie for 32 bit keys with 32 element nodes.
- louthy 4y ago
  > Also wondering whether you checked the Trie from the latest repo or the older struct version I also linked I included Sasa.Collections 1.0.0-RC4 from Nu-Get. So I assume it's your latest version. I've added Sasa.Collections permanently to my benchmarks seeing as you're the first library to get close to the performance of the language-ext collections - I'd like to keep an eye on you, haha! Always good to have a bit of friendly competition :) > forgot to mention that Node<...> generic is nested 6 times because that's the max depth of the trie for 32 bit keys with 32 element nodes. Yep, I figured that one. Still I look at it and go 'huh?'. I've been looking at code all day though, so I'll have a proper look tomorrow when less tired.
  - naasking 4y ago
    Start with this representation: struct Node<TKey, TValue> { uint bitmap; KeyValuePair<TKey, TValue>[] entries; Node<TKey, TValue>[] children; // Node = Leaf of bitmap * children | Internal of bitmap * children // We inline that sum into a struct where // Leaf -> entries != null // Internal -> children != null } Now consider the case where leaves are somewhat sparse. That means the children arrays will have few entries, so instead of allocating a bunch of one-element arrays for children which themselves allocate a bunch of one-element arrays of values, just inline the value arrays in the parent. Now propagate that same idea for internal nodes all the way back to the root. Also, because these are all structs, the JIT should specialize the code generated for each level so it should be pretty fast. IIRC, the speed difference between the original and the inlined representation was noticeable but not crazy, but the memory use difference was considerable. This was all years ago though, first implementation was 2013.

by louthy 4y ago

deleted 4y ago

[deleted]

naasking 4y ago

Nice! I'm away for the weekend so will follow-up with an explanation of the nested generic when not on the phone if the following is unclear: the basic idea is that you inline the next level of the Trie into the previous level, thus collapsing the depth and removing some indirections. This slightly bloats the internal tree nodes but the leaves vastly outnumber the internal nodes, and since the leaves have been inlined one level up, it ends up compacting it somewhat. This is maybe clearer when starting with a struct-only design for the internal nodes and then performing the inlining as an optimization on that. Also wondering whether you checked the Trie from the latest repo or the older struct version I also linked. I think the struct version was a little faster but I switched for the aforementioned idiomatic reasons. I'll have to check out the CHAMP design for sure, I'm curious how it differs. Edit: I also recall that I didn't optimize iteration at all and that it was fairly inefficient, but can't really confirm now. I recall optimizing merge carefully though so that should perform well. Edit 2: forgot to mention that Node<...> generic is nested 6 times because that's the max depth of the trie for 32 bit keys with 32 element nodes.

louthy 4y ago
> Also wondering whether you checked the Trie from the latest repo or the older struct version I also linked I included Sasa.Collections 1.0.0-RC4 from Nu-Get. So I assume it's your latest version. I've added Sasa.Collections permanently to my benchmarks seeing as you're the first library to get close to the performance of the language-ext collections - I'd like to keep an eye on you, haha! Always good to have a bit of friendly competition :) > forgot to mention that Node<...> generic is nested 6 times because that's the max depth of the trie for 32 bit keys with 32 element nodes. Yep, I figured that one. Still I look at it and go 'huh?'. I've been looking at code all day though, so I'll have a proper look tomorrow when less tired.
- naasking 4y ago
  Start with this representation: struct Node<TKey, TValue> { uint bitmap; KeyValuePair<TKey, TValue>[] entries; Node<TKey, TValue>[] children; // Node = Leaf of bitmap * children | Internal of bitmap * children // We inline that sum into a struct where // Leaf -> entries != null // Internal -> children != null } Now consider the case where leaves are somewhat sparse. That means the children arrays will have few entries, so instead of allocating a bunch of one-element arrays for children which themselves allocate a bunch of one-element arrays of values, just inline the value arrays in the parent. Now propagate that same idea for internal nodes all the way back to the root. Also, because these are all structs, the JIT should specialize the code generated for each level so it should be pretty fast. IIRC, the speed difference between the original and the inlined representation was noticeable but not crazy, but the memory use difference was considerable. This was all years ago though, first implementation was 2013.