Saturday, November 29, 2008

Equality Now!

There are three primary ways to handle equality in .NET: overriding Object.Equals, overloading the == and != operators, and implementing IEquatable<T>. Framework Design Guidelines offers pretty good advice on when to use what. A quick summary:
  • If you want custom equality logic, whatever else you might do, override Object.Equals. This method is used by the various data structures in System.Collections (and elsewhere in the BCL) to determine equality. It's the first best way to do equality.
  • IEquatable<T> should be implemented by structs with custom equality. Because calling Object.Equals on a struct involves boxing, and the implementation for value types uses reflection (!!!!!), IEquatable<T> gets around both of those problems. When implementing IEquatable<T>, always override Object.Equals as well.
  • Operator overloading is a little bit tricky because it's really just a compiler feature. The compiler has a lookup rule for the operator implementation which takes the most derived types along the operands' type ancestry. Whereas Object.Equals is a virtual method whose overridden implementation will always be used, overloaded operators will only be used if both operands are of static (compile-time) types that are or derive from the types specified in the overload. Overloading operators is a matter of discretion. It's more commonly done with value than reference types. If you overload the equality operators, also override Equals (an implement IEquatable<T> if the type is a struct).
When you are just overriding Equals, here is the pattern I find works the best:

public override bool Equals (object obj)
{
  MyRefType mine = obj as MyRefType;
  return mine != null && /* custom equality logic here */;
}

If you want to overload operators and it's a reference type, here's the thing to do:

public override bool Equals (object obj)
{
  MyRefType mine = obj as MyRefType;
  return mine == this;
}

public static bool operator == (MyRefType mine1, MyRefType mine2)
{
  if (Object.ReferenceEquals (mine1, null)) {
    return Object.ReferenceEquals (mine2, null);
  }

  return !Object.ReferenceEquals (mine2, null) &&
  /* custom equality logic here /*;
}

public static bool operator != (MyRefType  mine1, MyRefType  mine2)
{
  return !(mine1 == mine2);
}

If you have a value type, here's the scenario without overriding the operators.

public override bool Equals (object obj)
{
  return obj is MyValueType && Equals ((MyValueType)obj);
}

public bool Equals (MyValueType mine)
{
  return /* custom equality logic here */
}

And here's the value type with operator overloads

public override bool Equals (object obj)
{
  return obj is MyValueType && Equals ((MyValueType)obj);
}

public bool Equals (MyValueType mine)
{
  return mine == this;
}

public static bool operator == (MyType mine1, MyType mine2)
{
  return /* custom equality logic here */
}

public static bool operator != (MyType  mine1, MyType  mine2)
{
  return !(mine1 == mine2);
}

The purpose of the above patterns is to centralize the equality logic in one place. You'll notice in the example which uses all three approaches, the == operator is the only place with actual equality logic. I find this just makes thing easier. If you want, you can have custom logic in the != overload (the logical inverse of ==), but that means you have to make changes in two places if you alter the equality logic, and it's really easy to make a mistake with logic operators.

Want to share your tips for equality? Have a better pattern? Leave a comment!

Wednesday, November 5, 2008

Advanced Topics in Inefficiency: Anonymous Methods

This is the first in what may be a series of posts on various theoretical (and not so theoretical) corner cases in common code. Despite being obtuse, these issues are useful to explore both to avoid inefficiencies and to better understand what's happening behind the code. Today's topic: anonymous methods.
class Foo()
{
    void Bar()
    {
        var thing1 = new Thing();
        var thing2 = new Thing();

        DoSomeStuff (() => thing1.Shimmy());
        DoOtherStuff(() => thing2.Shake());
    }
}
There is a potential memory problem with this method. It's not obvious from looking at the code, but both things must be garbage collected together. As long as there is an active reference to one, the other will live on as well. If 'Thing' is a heavy type, this could keep significant memory from being reclaimed on the heap. To better understand, let us look at how the C# compiler handles anonymous methods.

The above example demonstrates "local variable capture." This means local variables from the enclosing method body can be used inside closures (such as the two lambdas above). To accomplish this, the C# compiler shunts the values of the local variables to an object. The type of the object is generated by the compiler. In essence, the compiler turns the above code into this:
class Foo()
{
    class GeneratedTypeForMethodBar
    {
        public Thing thing1;
        public Thing thing2;

        public void AnonymousMethod1()
        {
            thing1.Shimmy();
        }

        public void AnonymousMethod2()
        {
            thing2.Shake();
        }
    }

    void Bar()
    {
        var closure_object =
            new GeneratedTypeForMethodBar();
        closure_object.thing1 = new Thing();
        closure_object.thing2 = new Thing();

        DoSomeStuff(closure_object.AnonymousMethod1);
        DoOtherStuff(closure_object.AnonymousMethod2);
    }
}
This is actually a very clever way of achieving local variable capture since it makes use of the CLI's pre-existing garbage collector to clean up the captured variables. The problem is, the compiler shunts all local variables to a single object. In our above example, the two anonymous methods do not reference any of the same local variables, but both local variables are stored in the same object. This can lead some captured variables to become prisoner variables: they are no longer needed, but they cannot be garbage collected. Suppose that our 'DoSomeStuff' method just invokes the delegate and returns. No problem. But now suppose that our 'DoOtherStuff' method holds on to the delegate, perhaps planing to invoke it later. Or suppose we were to return the second lambda, allowing the caller to hold the delegate as long as they please. That delegate holds a reference to the 'closure_object' which holds a reference to both Things, even though that delegate just needs 'thing2'. There is no way for any code to reach 'thing1' but it won't be garbage collected until we're done with 'thing2'.

Solution?

Well, we could modify the compiler to generate a type for each set of local variables that appear in only one anonymous method, like so:
class Foo()
{
    class GeneratedTypeForMethodBar1
    {
        public Thing thing1;

        public void AnonymousMethod()
        {
            thing1.Shimmy();
        }
    }

    class GeneratedTypeForMethodBar2
    {
        public Thing thing2;

        public void AnonymousMethod()
        {
            thing2.Shake();
        }
    }

    void Bar()
    {
        var closure_object1 =
            new GeneratedTypeForMethodBar1();
        closure_object1.thing1 = new Thing();

        var closure_object2 =
            new GeneratedTypeForMethodBar2();
        closure_object2.thing2 = new Thing();

        DoSomeStuff(closure_object1.AnonymousMethod);
        DoOtherStuff(closure_object2.AnonymousMethod);
    }
}
This poses problems as well. First of all, we are instantiating two (or more) generated-type objects rather than one. Object instantiation is not cheap and that could potentially slow down certain code. Also, this approach cannot be used to optimize more complex scenarios. Suppose we have five anonymous delegates, each referencing some of seven local variables like so: a {1 2} b {2 3} c {3 4 5} d {1 5 6} e {6 7}. In these situations we must default to the one-compiler-generated-type-for-everything approach.

Ultimately, the lesson here is just to be aware of these potential issues. If you find via profiling that objects are not being garbage collected and you make heavy use of anonymous methods, you might want to examine your closures to make sure this isn't causing the problem.

And what do people think about modifying the compiler as proposed above? Also, anyone who comes up with a better mechanism for local variable capture gets cool points. Double points if your solution doesn't require VM changes.

P.S. Thanks to Michael for help with this post.

Friday, October 10, 2008

Mono.Upnp: A Bun In The Oven

Aaron's post has piqued some interest, so I thought I'd give up the goods.

WTF
Mono.Upnp is a fully managed UPnP implementation. The client and server stacks are in separate libraries to give embedded devices a compact solution for either. The client library is a solid implementation of the UPnP standard designed to robustly cope with other, less compliant UPnP devices (seriously, no one actually implements the UPnP standard correctly. Especially not router manufacturers, may they die a thousand deaths). The client API is also highly extensible, allowing easy consumption of services which offer functionality not established in the spec. The server library offers developers an easy way to expose their services over UPnP: attributes indicate UPnP-visible members and the library handles all of the network plumbing. In addition, all of the official UPnP device and service APIs (the specs which sit on top of the UPnP architecture - for example, the MediaServer API) are wrapped both for client and server use.

Holy Shit!
Indeed. Well, almost. All of the above sounds great, but it's not done yet. In fact, it's still quite experimental. While I've made great progress in impressive screenshots, actually listening to your Banshee collection on a PS3 is still a few hack-o-thons off. But things are moving along nicely and I will certainly keep you up to date.

OK
In the mean time, curious monkeys can find the source in the mono-upnp module of the Mono SVN. Like I said, you shouldn't be using this code, but you're welcome to check it out.

Thursday, November 1, 2007

MemberExpression Question

Maybe someone can answer this for me. When C# is compiled into an Expression tree, the MemberInfo that is tied to a MemberExpression points to the most virtual/abstract definition of that member. For an example, take a look at this code. The Visitor class will print the declaring type of a member encountered in a MemberAccess Expression (ln 36). When ran in Orcas B2, it prints "BaseClass" rather than "ConcreteClass". Is this how it's supposed to behave? Does Mono behave this way? Is there a better way to get the MethodInfo of the concrete class than this:

// This goes in the Visitor.VisitMemberAccess method
MemberInfo mi = m.Expression.Type.GetMemeber(m.Member.Name)[0];

I ask because I'm looking for custom attributes which may only exist on the overridden members of the concrete classes.

Wednesday, October 31, 2007

Linq Me This Nut

The Banshee-to-Windows porting has been more or less done for a while and the code is about to be integrated into trunk. Since the end of the SoC, I've been occupying myself with a tangentially related project. Banshee talks to the MusicBrainz database to get metadata on CDs. Currently it calls into the unmanaged libmusicbrainz library which is both old and no fun. Enter musicbrainz-sharp, my new project to implement a fully managed API for MusicBrainz. It's a very nice OO encapsulation of MusicBrainz's XMLWebService and it's really easy to use:

Artist a = Artist.QuerySingle("The Magnetic Fields");
foreach(Release r in a.Releases)
    Console.WriteLine(r.Title);

Right now it lives in banshee's svn (thanks to Aaron for setting me up with autotools et al). The API is 90% done, the documentation is 90% written, and the unit tests are at about 50% coverage. It's been my intension to create a Linq provider when 3.5 comes out, but for whatever reason the urge overcame me today. I did a quick job which only supports very specific cases, but the following code now works like a charm in Orcas:

var query = from a in MB.Artists
            where a.Name == "Goodshirt"
            select a;

foreach(var artist in query) {
    Console.WriteLine(
artist);
    foreach(var release in artist.Releases) {
        Console.WriteLine("\t{0}", release);
        foreach(var track in release.Tracks)
            Console.WriteLine("\t\t{0}", track);
    }
}


I was muy excited. There's some boilerplate code involved with writing a Linq provider. I hope Microsoft adds some base classes to the API. Linq is balls awesome!

Sunday, August 5, 2007

Status Report Aug 5

This week:
  • CD Burning is done
  • CD Playback is done
  • NotifyAreaPlugin works with the Windows system tray
Things are really coming together. I'll have new screenshots soon but I've got to go to bed now. We're out of the native code woods... for now.

Tuesday, July 31, 2007

End of July Status

Here's the skinny on the Banshee port to Windows:
  • Major re-factoring of the audio CD code. I abstracted a bunch of Linux-specific code and implemented classes for Windows. Made some interfaces into abstract classes where helpful and re-jiggered some of the architecture.
    • The Cool Thing: It's all really pretty and audio CD detection works.
    • The Not Cool Thing: CD playback does not work. This is because Gstreamer on Windows doesn't handle cdda:/ URIs. This is because libcdio doesn't build on Windows. This is because, while it used to build on Windows, the Visual Studio solution has terrible bitrot. Solutions:
      • Build with Cygwin and...
        • Live with a dependency on cygwin0.dll, or
        • Find some way of circumventing cygwin dependencies (ideal).
      • Fix the Visual Studio solution. This consumed much of my time recently. I emailed the guy who previously maintained the VS solution, but he hasn't gotten back to me.
      • Write a new cdda handler for Gstreamer using the Win32 API. Ug.
  • Implementation of CD burning for Windows.
    • The Cool Thing: It's partially done (and was loads of fun), but I need to be able to test it to continue with the work.
    • The Not Cool Thing: I can't test it. This is because Banshee's Gstreamer transcoding code doesn't work. This is because it references libgnomevfs-2-0.dll and there is no libgnomevfs-2-0.lib against which to link and when I link against libgnomevfs-2-0.a, Visual Studio produces a malformed DLL which crashes upon loading. Solutions:
      • Build gnome-vfs with MSBuild. I gave that a try and it looks like a lot of work before it will work.
      • Contact whoever maintains Mono's Windows binaries and ask for their advice (ideal).
      • Remove the gnome-vfs code from libbanshee.
  • Improvements to importing from iTunes.
    • The Cool Thing: Following Jonathan Pryor's post on monodocer performance, I switched from XmlDocument to XmlTextReader. Much memory savings. Not a lot of speed savings (XML handling isn't a bottleneck).
    • The Not Cool Thing: Nothing. The code is faster and prettier.
  • Misc. Other Things:
    • I'm hoping the Gstreamer people will add a function export that I need: _gst_plugin_register_static. It's in the code but it just isn't exported for Windows. Waiting to hear back.
    • The CD reading and burning code are from code example sites. Both are just encapsulation of COM interfaces. I'm 99% sure the CD reading code is license compatible (I'm still looking into it), but the CD burning stuff defiantly isn't. I've contacted both authors to see if they will release the code under MIT/X11. Waiting to hear back. If I can't get clearance, I'll have to do the COM wrappings myself. Ug.
    • Gtk is slow on Windows. Even when not debugging. Aaron's new view model should make things much better.
    • Gstreamer is slow on Windows. It's fine most of the time, but when the CPU gets hammered, the audio will become choppy. This doesn't happen when using DirectSound in similar situations. I don't know yet if it's a significant problem.
I find I'm spending most of my time struggling with unmanaged code. When I tackle a new problem, like audio CDs, I hammer out the C# lickety split and have a great time. But then I hit a snag in native land (like the cdda/libcdio problem) and spend days trying to sort out the C libraries which is no fun. After a few days of wrestling with unmanaged code, I'll put it on the back burner and start on something else (CD burning or iTunes importing, for instance) but I really need to address these native issues. Tomorrow I'll start emailing around and see where I can get with cdda support in Gstreamer or gnomevfs linking on Windows. If you have info on this stuff, especially using Cygwin to build Windows stuff which is not Cygwin-dependent, please leave a comment.

Peace,
Scott.