Thread by @rickbrewPDN

If you drop the Count property from .NET's ICollection, ISet, IDictionary, then you can build up a really interesting LINQ-style query system. Where(), Intersect(), Except(), Union(), etc. ... all without any copying.

Select() isn't really doable though, since you'd need a mapping function in both directions, T -> TResult and TResult ->T, so that the outer query can ask the inner query if it has the T that maps to the TResult (and you only know which T to ask for if you have Func<TResult, T>)

In combination with some async / Task-based background flattening (basically Enumerable::ToDictionary()), I'm using this for some really good stuff in the upcoming Paint​.NET update.

Proving to be very helpful for reducing UI-thread stalls!

To be clear, you as the user of the app won't see a big difference just yet -- unless you're working with very large images, which do perform better.

However, this is going to be an important piece of tech for future upgrades to the rendering engine and app model.

An example of "helps reduce UI thread stalls": on the UI thread I often need to do things like, "redraw/delete all the tiles that are in this region of the image."

It's hard to do that fast, it needs for-loops that take awhile, and hard to do async (coordination craziness).

There can be 100s, or 1000s, or 10's of thousands of tiles. Just not doable on UI thread, and really hard to mask out these regions through conventional means.

Now I can just "push" a Where()-style query onto the top of my tile cache to filter out dirty/invalidated regions from future reads by the rendering code, while the background thread takes care of actually calling Dispose() on those tiles (bitmaps).

What else might this help with? Hmm ... this basically gives me the ability to take a snapshot of a Dictionary/Set in O(1) time.

Background thread can grab snapshot and then run off with it for something like ......... auto-save.

Auto-save/recovery is one of the top requested features in Paint​.NET right now, but I can't implement it without having a big modal dialog saying "PLZ WAIT FOR TEH AUTO-SAVING" every few minutes.

Fast snapshots of the data make this doable in background with no intrusion.

Immutable data structures aren't needed for all of this, but the contract (aka illusion!) of immutability is the key. I tried using the Immutable Collections library and it was a major disaster for allocation and GC perf. Being careful with regular Dictionary/HashSet much faster.

If you drop the Count property from .NET's ICollection, ISet, IDictionary, then you can build up a really interesting LINQ-style query system. Where(), Intersect(), Except(), Union(), etc. ... all without any copying.

Select() isn't really doable though, since you'd need a mapping function in both directions, T -> TResult and TResult ->T, so that the outer query can ask the inner query if it has the T that maps to the TResult (and you only know which T to ask for if you have Func<TResult, T>)

In combination with some async / Task-based background flattening (basically Enumerable::ToDictionary()), I'm using this for some really good stuff in the upcoming Paint​.NET update.

Proving to be very helpful for reducing UI-thread stalls!

To be clear, you as the user of the app won't see a big difference just yet -- unless you're working with very large images, which do perform better.

However, this is going to be an important piece of tech for future upgrades to the rendering engine and app model.

An example of "helps reduce UI thread stalls": on the UI thread I often need to do things like, "redraw/delete all the tiles that are in this region of the image."

It's hard to do that fast, it needs for-loops that take awhile, and hard to do async (coordination craziness).

There can be 100s, or 1000s, or 10's of thousands of tiles. Just not doable on UI thread, and really hard to mask out these regions through conventional means.

Now I can just "push" a Where()-style query onto the top of my tile cache to filter out dirty/invalidated regions from future reads by the rendering code, while the background thread takes care of actually calling Dispose() on those tiles (bitmaps).

What else might this help with? Hmm ... this basically gives me the ability to take a snapshot of a Dictionary/Set in O(1) time.

Background thread can grab snapshot and then run off with it for something like ......... auto-save.

Auto-save/recovery is one of the top requested features in Paint​.NET right now, but I can't implement it without having a big modal dialog saying "PLZ WAIT FOR TEH AUTO-SAVING" every few minutes.

Fast snapshots of the data make this doable in background with no intrusion.

Immutable data structures aren't needed for all of this, but the contract (aka illusion!) of immutability is the key. I tried using the Immutable Collections library and it was a major disaster for allocation and GC perf. Being careful with regular Dictionary/HashSet much faster.

Going back to the beginning: dropping Count is important because you really have no idea how many items are added/removed when you stack these LINQ-ish queries. Too expensive to compute, and you almost never actually need that information.

This is also proving useful for implementing caches that are based on WeakReference.

These types of caches always need a janitor -- enumerate everything, remove any WeakRef's that are now null. Takes time!

Now I push a Where() query, let background thread flatten it later.

This is the basics ... the struggle was in the interface, the fun is in the implementation

The first thing you do is build ISetView<T> wrapper for HashSet<T> or ISet<T>, and IDictionaryView<TKey, TValue> wapper for IDictionary<TKey, TValue>

And here's the Where query for ISetView<T> ... (created via an extension methods)

BTW it was super weird to first implement with Immutable collections, then run the VS2019 concurrency profiler:

"oh, I'm spending 30% time in the GC ... due to 100s of thousands of new allocations per second"

It was actually a major bottleneck for throughput! -- my CPU usage was only managing to hit 25% out of a 16-core Ryzen 3950X. Hit around 60% after various optimizations to eliminate allocations, including moving away from Immutable collections

CPU usage was very low because threads were spending most of their time in the sleeping state -- waiting on the poor GC to do its job

There's an interesting parallel with the Concurrent collections.

For some of them, such as C. Dictionary, accessing Count is VERY expensive, kinda like taking a heavy write lock. The internal accounting is loose here, to allow other operations to achieve their perf promises.

BTW pro tip: if you need high perf use of ConcurrentDictionary, DO NOT acccess the Count property! You'll regret it! Better to have your own wrapper that keeps track of it on the side with Interlocked::Increment()/Decrement().

Anyway it's fun to figure out what you can accomplish with collection classes/interfaces when you emphasize the performance of different operations.

As mentioned elsewhere, my LINQ-ish stuff can't do Count or Select() very fast. All sorts of other ops are fast instead.