Ephemerons in .NET and C#

Long time no post, and I'm just doing another because of a discussion on stackoverflow (in the comments) which got a bit off-topic.

So, like I mentioned in the last post, with .NET 4.0 we got ephemerons in the form of the ConditionalWeakTable class in the System.Runtime.CompilerServices namespace of mscorlib. This class is actually a collection of ephemerons hidden behind a dictionary-style API. The purpose of this class is to allow dynamic languages to 'attach' values to arbitrary objects, which also explains the choice of the namespace.

If you don't want to read through my last post I'll repeat the use-case of ephemerons and ConditionalWeakTable: the main problem is when you have a weak dictionary it could be possible that there is a reference chain from values in the weak dictionary to keys in the same weak dictionary. If those references form a cycle the "weakness" of the entries is effectively lost and the lifetime of the whole cycle is bound to the lifetime of the weak dictionary, which often is static and never collected at all.

Because these reference chains can be arbitrarily complex it is impossible to solve this cycle problem without help from the GC. Here is where ephemerons come into play, they effectively provide a way to specify conditional weak references: as long as the key is reachable, the value is also reachable. In other words, it is a way of saying "don't collect the value before the key".

So this problem is solved in .NET 4.0, great, but what if I want to roll my own weak dictionary because I don't like the behavior or API of ConditionalWeakTable? What if I want only a single ephemeron without the overhead of a collection? The implementation of the ConditionalWeakTable is based on a class called DependentHandle, however (unlike GCHandle and WeakReference) it is internal to mscorlib. Thats unfortunate, but as I said last time it is possible to replicate the implementation of DependentHandle (and thus ConditionalWeakTable) with some reflection trickery.

Of course this requires full trust and thus won't work on all .NET runtimes (silverlight, xbox, compact editions). Also it relies on implementation details of the .NET runtime so you need to check with every major update that your reflection code still works, fortunately this is easy since we'll only be relying on the names of four internal static methods, which can be easily checked to still exist.

People without access to reflection (or who don't want to use it) can obviously still use ConditionalWeakTable to create ephemerons. You can even chose between creating one table for each ephemeron you need, or sharing the table and just adding entries, since each entry is an ephemeron independant of the others in the table.

Implementation of DependentHandle

So, for those who are left, we can now finally get to the details on how to do the reflection magic to create your own ephemerons, DependentHandle and ConditionalWeakTable. We want maximum performance and minimum memory usage, so we don't just reflect into the constructor of DependentHandle: since it's a struct it would be boxed, and we would need to use reflection for any method call, which is not nice - but we can do better.

The trick is to know that DependentHandle is itself just a wrapper around the native runtime, much like GCHandle is for weak references. Internally it uses an IntPtr as a handle and static methods to talk with the native runtime. So if we could access those static methods we could roll our own DependentHandle. To get the best performance we'll use reflection to lookup the methods and then turn them into delegates. This allows the JIT to optimize calls to the reflected methods and is almost as fast as if you called the method directly.

To do the reflection magic we need a delegate signature which we can use to access the runtime implementation, as well as the function names. We can find these with from the .NET reference source, by using some decompiler, or just doing plain reflection to see what methods and fields are defined on ConditionalWeakTable and DependentHandle. Then we can use Delegate.CreateDelegate to create a delegate for the static method.

The four static methods we need are:

• void nInitialize(object primary, object secondary, out IntPtr dependentHandle)
• void nGetPrimary(IntPtr dependentHandle, out object primary)
• void nGetPrimaryAndSecondary(IntPtr dependentHandle, out object primary, out object secondary)
• void nFree(IntPtr dependentHandle)

Their function should be obvious, 'primary' is the key and 'secondary' is the value. While the primary reference is alive the secondary reference also is forced to stay alive. What is not obvious is what happens if the primary reference is collected; in this case the ephemeron is 'reset' by the runtime/gc and sets the primary and secondary refrence to null. Note that ephemerons are immutable from the managed side, you specify the key/value when you create it, so if you want to change either you need to recreate the handle (this behavior is like GCHandle for weak references).

Like we have WeakReference for GCHandle we wouldn't want to use DependentHandle directly. Instead we'd build a wrapper around it, like WeakReference is a wrapper around GCHandle. I've chosen to call it Ephemeron and provided a non-generic version (like WeakReference) and a generic version atop of it.

Note that this wrapper is tricky to get right because for some of the high-level functionality like changing keys we need multiple calls into the runtime, so we need to be careful for race conditions. My implementation is derived from WeakReference by looking at the .NET reference source and generalizing it to cover a key-value pair instead of a plain value. I added a lot comments to the implementation to document the race conditions.

So enough of the talk, I've added the implementation to my repository where I have the weak delegate implementation, here are the direct links: direct link to sourcecode and direct link to download.

True Weak Keyed Dictionary

Hi again,
Sorry for the lack of updates, but I think I'll be switching to a 2-month update interval for now.

So on to the actual topic. Recently I stumbled across a hidden gem in the .NET 4.0 CLR, an implementation of a weak keyed dictionary referenced by comments in the MEF source code. Their comments described problems with weak dictionaries I wasn't aware of, even though I have implemented some myself in the past. Becoming curious I searched a bit and actually found two blog posts with further information: in the IKVM blog and the CLR-Team blog. In the following I'll explain a bit about what I figured out.

If you ever tried to build a weak dictionary in C# (or any other .NET language) you may have found it's a bit tricky. In particular .NET is lacking a lightweight mechanism to notify you when entries in your dictionary are collected.

Let's assume we want a weak-keyed dictionary, meaning the keys of the dictionary are held in weak references. Once a key has been collected we define the associated value to be no longer (logically) reachable. That means we ideally should remove it, and if we don't we should at least skip it for iterations.

Now there is one heavyweight way to get notifications about the collection of keys, that is instead of putting a key into an odinary weak reference we put it into a class with a finalizer (maybe that could be a subclass of the WeakReference, didn't check if that's possible). Unless the dictionary is globally accessible the keys need a back-reference to the dictionary, so they can remove themselves when their finalizer is called. There are few more pitfalls, like having to make finalizers thread safe (they could be called in parallel on a runtime with multiple finalizer threads).

If you don't want the finalizer and/or back-references in the keys there are alternatives. You can regularly iterate over the dictionary entries to find entries whose keys were GC'ed. This collection step can be done either when accessing the dictionary or by a separate thread. In either way you need to fine-tune the frequency of collections to match your usage patterns of the dictionary. What you are doing is effectively runnig your own GC restricted to the dictionary ;-)

However all of those solutions have a serious bug, they don't work for arbitrary values. In particular they will fail in presence of cycles: that is, if a value, directly or indirectly, can lead back to its key. Since the dictionary has strong references on its values, this chain of references leading back to the key makes it strongly referenced, causing it to be never even considered for GC!

In fact, this problem is actually impossible to solve outside of the GC. However it is well-known and there exists a theoretical solution: ephemerons. It is just what we need to describe our problem to the runtime and let the GC handle it. If our dictionary entries were ephemerons then the values would not be considered strong references while the GC looks if the key can be collected.

The gem I found is that ephemerons were "secretly" added in .NET 4. I call it "secretly" because the actual ephemerons are an internal type in mscorlib called DependentHandle, so you can't use them directly without some reflection trickery. The only purpose they were added is to allow implementation of a true weak-keyed dictionary which works even in the presence of cycles. Luckily this class is actually public, it is called ConditionalWeakTable and lives in System.Runtime.CompilerServices (also mscorlib). The original intention of this class is to allow attaching arbitrary values to objects, because that is part of dynamic languages like Python or Ruby. But I think that shouldn't stop anyone who needs a true weak-keyed dictionary - or just wants to attach arbitrary values to objects in C# ;-)

If you really want to roll your own weak dictionary or need ephemerons for some other purpose you could implement your own ephemerons using reflection to call into the runtime. This works because the runtime methods are static and operate on IntPtr instead of a DependentHandle, so you can use reflection to get hold of those static methods and turn them into delegates (that's faster than using reflection-invoke on each call). Of course always keep in mind that internal types can change names/methods between runtime versions, so those trick may require to be fixed every now and then.

True weak delegates (Part 2)

Again a month was over faster than I thought. This time I'll try to explain my solution to true weak delegates, which works in all scenarios. First I'll explain the reference graph for the normal scenario.

The event source is the object which holds the event to which a listener subscribes a delegate as event handler. Here we are interested in an event handler which needs the listener to operate, so C# will capture a reference in the delegates closure object.

Note that from the description in my last post there actually is a reference from the delegate to the closure object which isn't shown in the diagram. However you can't make that reference weak because then the closure object would become garbage right away (only the delegate knows about it!).

From the diagram you can nicely see the reference chain from the event source through the delegate and its closure back to the listener, which will keep the listener alive as long as the event source stays alive. The reference from the listener to the delegate is optional in the sense that you only really need it if you want to unsubscribe from the event source.

The reference from the closure to the listener isn't always direct, it could go through a chain of references, too. This means the only place where we have any hope to replace the reference by a weak one is the part from the event source to the delegate.

Ideally the .NET framework would provide a way to subscribe to an event by keeping the reference from event to delegate weak, but as it doesn't we need to be insert another layer of indirection to have any chance at all. Consider the following modified diagram:

Here we've separated the reference from event source to delegate by inserting another object which I've called weak closure. I could've called it weak delegate, but since it stores more data and doesn't inherit from delegate I figured calling it weak closure might be less confusing.

So, let's analyze the diagram to understand how it works.

The most important thing you notice is that the strong reference chain from event source to listener is broken by a weak reference (the dotted arrow). Once all other references to the listener and delegate go away it means both can be collected (but not the weak closure).

If we can tolerate the fact that the weak closure stays subscribed when the delegate and listener went away then we don't need a link from the weak closure to the event source; but if we provide such a link (either weak or strong) then the weak closure can unsubscribe itself. When the event is raised the next time it will notice the delegate went away and can use its reference back to the event source to unsubscribe itself.

Another thing to notice is that the listener now is required to hold a reference to the delegate. While this may seem strange at first it does make sense, because if the listener doesn't hold a reference to the delegate then the only reference is the weak reference, meaning the delegate will be collected right away. The reference to the weak closure is optional because (like before) you only need it if you want to explicitely unsubscribe.

One minor detail which may be missed is the effect of the backreference from the weak closure to the event source. Like said before it is requied to auto-unsubscribe when the listener/delegate goes away. However, if it is a strong reference this means we now can have a chain from the listener over the weak closure to the event source!

This means we have the inverse scenario from which we started, now the event source can't be collected while the listener stays alive. It is easily fixed by weakening the reference from the weak closure to the event source. However, often it doesn't matter that the event source will be kept alive, and it may be worth to save the overhead of a second weak reference.


If you have been wondering why I unsubscribe from the weak closure instead of using a finalizer, this is intentional. Finalizers run on a separate thread and depending on how the event source is coded it may not be safe to unsubscribe asynchronously, but if you know that it is safe for your event source it would be alright to use a finalizer to unsubscribe when the delegate goes away.

I've setup a mercurial repository at https://code.weltkante.de containing my weak closure implementation and some samples. Direct link to sourcecode. Direct link to download. Note that the API isn't exactly nice, I've written most of it a long time ago, you could probably use some more tricks to make the sytax nicer. For ideas you should look at the article I linked last time, it shows some nice syntax tricks to capture event subscription.

True weak delegates (Part 1)

This is the first of a two part series about weak delegates (including weak events, but delegates are more general than events). I'll start with explaining the problem in this part.

In C# it's easy to get a reference to a function or method, called a delegate. You declare the signature and the framework generates a type which is able to wrap a function or method with a matching signature.

There's also the concept of events where you can register and unregister delegates. Unless you implement the accessor methods yourself the framework will combine registered delegates into a multicast delegate, which is basically a list of delegates. When you register a delegate with an event it's just put into that list. When the event is triggered a snapshot of the current list is taken and all delegates in the snapshot are called in order. (This may be important if you try to unregister from within an event handler; but that's offtopic.)

Note that I'm aware that this explanation is oversimplifying events, but I think it's accurate to the semantics, and I don't need the actual implementation details for this post.

Now every once in a while the problem comes up that the lifetime of the event source and the event listener differs. The strongest form of lifetime differences happen when you got events on a static class: since the list of delegates used to implement the event is also static it will never go away. Any delegate stored in such a static event will stay in there until you unregister it.

For example take System.Windows.Forms.Application which holds such static events. To make the example more concrete, the Idle event is something you'd likely subscribe to only for a short while, eg. while a certain Form is open. However, the delegate you registered may have a reference back to that Form - so unless you unregister it the Form will never be garbage collected (even if you properly dispose it).

Why would a delegate need a reference back to another object? Well, the most prominent reason is that it's a member method of that object; when the method is invoked there needs to be some object used for the 'this' variable. Because the 'this' variable is not part of the signature it won't be provided by the event source, so it has to come from somewhere else. The only solution is for the framework to store a reference in the delegate and use it when the method is called.

If you do some research you can figure out that there are three 'kinds' of delegates:
- static methods don't need a context so they don't store any reference
- member methods need to store the 'this' variable
- closures (see below) need to store all variables from their surrounding context

What are closures? That's the thing you create when you write inline delegates in C#, either via lambda expressions or 'delegate' keyword. All variables accessed from inside such a closure need to be stored in a place where they are still available when the closure is actually executed. The C# compiler automatically generates a class to hold those variables. Note that the C# compiler is smart enough to turn closures into member methods or even static methods where possible.

So for case #2 you get a reference back to your class, and case #3 is even worse because you get reference to an arbitrary set of classes, depending on the code of the delegate.

The idea of weak delegates is that those references should be weak, ie. if the event listener is no longer reachable except through its registered event handlers it should be collected and the event handlers be unregistered.

Available solutions differ greatly in which cases they handle, most general-purpose solutions only handle case #2 well. There are also solutions which handle all cases but require modifying the event source, something which is not always possible - this is in fact what WPF does with a lot of its core event sources.

I won't go into detail with the existing solutions as there is a great overview found on the web. Next time I'll post about my approach on the problem, which is able to cover all three cases without modification of the event source, ie. it always works. (Obviously this solution doesn't come for free, but you can chose what sort of overhead you want.)

Mutable strings in C#

It's about a month since my last post and I've not yet finished my next one, so I'm making a quick filler and talk a bit about mutable strings in C#.

When you come from another programming language (in particular C/C++) to C# you may notice that strings are immutable. So when you have to do string manipulations you naturally wonder what the C# way is to do it. When you look around you may find several alternatives:

• Using char arrays
• Using pointers (with char or byte arrays as buffers)
• Using StringBuilder

Once you figured that out you probably can't help to notice the lack of standard string methods for all of those except the StringBuilder. This should already give you a hint what the 'right thing' is for C#. Still, when browsing the web, it seems some people feel uncomfortable by using a class named "StringBuilder" when they "just" need a mutable string. So some may be tempted to bite the bullet and make their own functions for mutable strings based on char arrays or pointers.

Don't do that.

There's a reason why C# doesn't provide any string methods based on arrays - that's because StringBuilder is the .NET mutable string class. It just seems it got a name which suggests it's something more expensive, but really, it's not much more than a mutable string.

The most prominent intuition of StringBuilder being expensive is probably that you have to call ToString() to get a string back out of it. As far as I know it's not documented in the MSDN but this method does not actually copy the string. StringBuilder implements^[1] copy-on-write, which means that it can just return its internal buffer as if it were an immutable string - only the next time you call one of the modifying methods on StringBuilder it will actually make the copy. So for the most common use-case, building a string from scratch and converting it into an immutable string, there is no copy required at all (assuming you started with a large enough buffer).

The other common use-case of mutable strings is to take an existing string, modify it, and then work with the modified string. StringBuilder can't do that without making a copy. If you construct the StringBuilder initialized to an immutable string it will wait with making the copy until you actually try to modify it, but once you do that there is no way around the copy operation; after all someone may still hold a reference to the immutable string, so you can't just change the content behind its back. That's not unlike C/C++ either, if you get passed a const-string you also can't change it and have to work on a copy.

If you want to take a look at how copy-on-write is implemented on StringBuffer you can look at the Mono source or download the Rotor 2.0 sourcecode from Microsoft (look at clr\src\bcl\system\text\stringbuilder.cs).

There are a few other things to mention about the StringBuilder class, in particular Microsoft added a safety-net for multithreaded access to StringBuilder. When a StringBuilder object is accessed by a different thread it will work on a copy of the buffer and take over ownership. This is something to be aware of when you write multithreaded applications, as you don't want to hand a StringBuilder around between threads. I guess they added this safety measure due to ASP.NET which does a lot of string building and multithreading, if anything went wrong there it would be pretty much impossible to debug. If you are worried about the performance of this, as long as you keep the StringBuilder on one thread the overhead is minimal and will likely be shadowed by the actual string operations. Of course this is an implementation detail of the Microsoft CLR, if you look at Mono they don't seem to care about thread-safety of StringBuilder; if you access it from multiple threads (simultanously) you'll likely get string corruption and possibly a segfault.

Another thing that sometimes is recommended is reusing a StringBuilder by resetting its Length to zero. Because it was usually overlooked that you can do that .NET 4 added a Clear() method which does just that. However I wouldn't recommend going out of your way and cache StringBuilders for reusing them because most of the time you'll have called ToString anyways and the buffer ownership was transferred to the immutable string. (This means setting Length to zero or calling Clear() is still fast, but once you start building your string you need a new buffer anyways.)

So what is the conclusion about StringBuilder? I'd definitely recommend to use it in favor of any other technique, copy-on-write makes ToString about as fast as it can get. If you really need more speed you should go to mixed mode C++/CLI and write the corresponding code with native strings, anything else is not worth the trouble. This is mostly because in C++/CLI you can call the optimized native C string functions, which you probably can't beat in C# even if you use pointers (they do crazy things like taking address alignment into consideration).

[1] This is only verified for Mono and the Microsoft CLR as in the Rotor 2.0 source. However other variants of the Microsoft CLR are highly likely to behave the same.

WPF Rounded Border

I've been watching WPF for a while, the 3.5 and earlier versions I consider unusable, mostly because the totally broken VisualStudio designer support. (You could just as well type the xaml in notepad if you tried anything more complicated than a simple feature demo.) With the 4.0 release it finally gets into the "almost usable" area for me - still way too many bugs/oversights/missing features - but you can get something done.

One of the things I've hit is the clipping issue when using a border decorator. The decorator is an easy way to add a border around a WPF element and it has a useful corner-radius setting to make borders with round corners. The problem is that it renders the border below the content and without clipping. Here's an example when using a round border on an image - left is what you get with the border decorator, right is what you actually want.

 

There are a few workarounds on the web: OpacityMask + VisualBrush, which is easy to do and always works, but pretty slow. If you got several of them and you have to care about speed it's not good enough. Setting Clip on child elements was suggested in this thread and there is a good implementation on codeplex (you can play with the silverlight version online). However, as the original code snippet from the forum thread says in a comment, you lose the ability to bind or animate the clip property. Also it looks like that silverlight demo has some glitches for certain border settings - not sure where they come from.

What put me on the right track was a comment in this blog post - Dmitrij Zaharov suggested to override GetLayoutClip. Some reasearch led me to this overview of WPF clipping. So if I understood that correctly I can override GetLayoutClip and it will not interfere with the Clip property of the child elements - great.

So I came up with this small decorator class which does the clipping:
(The right image above shows it in action.)

public class RoundRectClip: Decorator
{
    public static readonly DependencyProperty CornerRadiusProperty = Border.CornerRadiusProperty;
    public static readonly DependencyProperty BorderThicknessProperty = Border.BorderThicknessProperty;

    static RoundRectClip()
    {
        Border.CornerRadiusProperty.AddOwner(typeof(RoundRectClip));
        Border.BorderThicknessProperty.AddOwner(typeof(RoundRectClip));
    }

    public CornerRadius CornerRadius
    {
        get { return (CornerRadius)GetValue(Border.CornerRadiusProperty); }
        set { SetValue(Border.CornerRadiusProperty, value); }
    }

    public Thickness BorderThickness
    {
        get { return (Thickness)GetValue(Border.BorderThicknessProperty); }
        set { SetValue(Border.BorderThicknessProperty, value); }
    }

    protected override Geometry GetLayoutClip(Size layoutSlotSize)
    {
        Rect borderRect = new Rect(0, 0, layoutSlotSize.Width, layoutSlotSize.Height);
        double radius = CornerRadius.TopLeft - 0.5 * BorderThickness.Left;
        Geometry borderClip = new RectangleGeometry(borderRect, radius, radius);
        borderClip.Freeze();

        Geometry baseClip = base.GetLayoutClip(layoutSlotSize);
        if(baseClip == null)
            return borderClip;

        CombinedGeometry mergedClip = new CombinedGeometry(
            GeometryCombineMode.Intersect, baseClip, borderClip);

        mergedClip.Freeze();
        return mergedClip;
    }
}

I don't inherit from Border because if I do then the clipping applies to the border as well, while I only want to clip the children. So when you want to use it, you have to place a normal border decorator and put a RoundRectClip inside the Border, and the actual content in the RoundRectClip:

<Border BorderBrush="Silver" BorderThickness="8" CornerRadius="16">
    <my:RoundRectClip BorderThickness="8" CornerRadius="16">
        <Rectangle Fill="Red"/>
    </my:RoundRectClip>
</Border>

You could probably generalize that by putting it into a control template for a content control, but I'm not fluent enough in WPF to get that working (yet) - when I tried it the border was just missing.

Some implementation notes:

For the off-chance that the base class does clipping of its own I'm calling the base implementation and intersect it when necessary. It usually just returns null, unless you do something strange like setting ClipToBorder - in any case the base class only can do rectangular clipping, so it doesn't help much, but I wanted to respect its clipping for compatibility.

For those not used to WPF, note that you should call Freeze on anything inheriting from Freezable before handing it to WPF (well, if you don't plan to modify it later). Otherwise it will make a copy before passing it off to the render thread, to ensure you don't change it behind its back.

Also I should mention I've kept it really simple, so there is a lot of stuff missing. The border decorator allows for different radius sizes on each corner, and different thickness on each edge - I'm just using the first of the values when building the clipping. If you need different values eg. because you only have round corners on the top corners, you can adjust by building a more complicated clipping geometry.

When looking at the base class implementation of GetLayoutClip with reflector I also noticed it handles UseLayoutRounding - which I'm not doing. So if you enabled layout rounding (which you should usually do for sharper graphics, instead of using SnapsToDevicePixels) then you need to round the width and height of the incoming parameters to a multiple of the desktop DPI resolution (which is 1.0 for the default 96 DPI).

If you need any of that more advanced stuff you probably should use reflector or the Microsoft reference source to look into FrameworkElement.GetLayoutClip and Border.GenerateGeometry.

Introduction

Welcome to my blog, I'm just starting out so don't expect too much ;)


Why this blog? The actual reason to start one was that I needed a place where I can link to, eg. from profiles. Since I've also got a few things I wanted to write about for a while a blog seemed useful enough to me. I'll mostly post about programming topics for now, my current target is for about one post a month, maybe two if I got a multi-post topic and enough free time.


Just to get through with it, here is my introduction.

My name is Tobias Käs and I'm from germany, working as a programmer for a small software company. Mostly I'm not using my real name when posting on the net, if I'm posting in a forum I'm usually using Zarat as an alias. However I've seen more than once that this name was already used, so don't expect every 'Zarat' you see to be me ;) The alias itself has no meaning, it was a random name I've used in a game for a while, and it sticked.

I'm mostly working with C# and Visual Studio these days, but I also have experience on C/C++, both on Windows and Linux. The areas I'm working on are very broad: I'm covering web programming (Asp.Net), native and managed Windows programming, low level graphics programming (DirectX/OpenGL), and of course a lot of general-purpose programming. My interests (as far as programming goes) are twofold: one is graphics, even though I'm not an artist at all I like working with low level graphic APIs; the other is automation, scripting languages, code generation and the like - anything that helps me avoid to repeatedly write the same code in different variations.