the blog => anything goes

Take a look at the following short snippet of code.

  1: using System;
  2: 
  3: struct S
  4: {
  5:     public int X;
  6: }
  7: 
  8: class C
  9: {
 10:     /* More code here */
 11: }
 12: 
 13: class Test
 14: {
 15:     public static void Main()
 16:     {
 17:         C c = new C();
 18:         c.S.X = 1;
 19:     }
 20: }

Without knowing the type definition of C, can you tell whether the code will compile, much less work?

Turns out that you can’t. It depends on whether the S in c.S is defined as a field or a property.

class C
{
    public S S;
}

class C
{
    public S S { get; private set; }
}

The first type definition will compile, the second won’t (error CS1612: Cannot modify the return value of 'C.S' because it is not a variable)

Can you guess why?

Let’s assume the compiler does allow the second type definition to compile. Would you expect the value of X in the instance of S inside C to change? That is, what would be the output of

public static void Main()
{
    C c = new C();
    c.S.X = 1;
    Console.WriteLine(c.S.X);
}

If you’re expecting it to be 1, then you have just broken the value semantics of a struct, S might as well have been defined as a class. The above code is logically identical to

public static void Main()
{
    C c = new C();
    S temp = c.S;
    temp.X = 1;
    Console.WriteLine(c.S.X);
}

Because S is a struct, the property getter always returns a copy (temp), and changing the copy will have no effect on the original instance. With c.S.X = 1, you can’t access the copy either, so the only effect of executing that statement will be to make the poor developer’s eyes go wide as he steps through the code in the debugger, wondering why a simple field assignment refuses to work.

So, the C# compiler is being helpful here by not allowing this kind of code to compile.

Right, so why does it compile if S is defined as a field rather than a property? We’ll see why in the next post. Meanwhile, feel free to post why you think it works.

Ever since I happened to stumble upon this book on Data Mining, I've been hooked. So much so that I've been brushing up on statistics and probability distributions just to follow along the book.

I'm currently reading the chapter on classification using decision trees, and what appeals to me is the how the technique reduces huge sets of data (records) into simple models that can both describe the data and can predict the class of previously unseen records. If all that goes right above your head, here's a simple example.

P1	P2	Class (Result)
True	True	True
False	False	False
True	False	False
False	True	False

Given the above tabular values, can the computer figure out that it is the truth table for P1 ^ P2 (with ^ representing logical conjunction, not XOR) ? If it can, it has

1. A model that describes the data, i.e., the data is the conjunction of the two boolean variables.

2. An evaluator that can calculate the result, given P1 and P2, i.e., predict the class. Since all combination of values are already available, there are no unseen records in this case.

A decision tree for the above table looks like this visually :-

with green edges and red edges representing true and false values for the attribute represented by the node, respectively. As you can see, the non-leaf nodes each represent an attribute, with one edge for each possible value of that attribute. The leaf nodes represent the result (class). Since we are dealing with binary attributes, the decision tree turns out to be a binary tree. Note that you can find out the result of { P1 = True, P2 = True } by simply navigating the tree and reading the value of the leaf node ( green edge from P1 to P2, green edge from P2 to T, and then read the value, T = true).

This was so interesting that I actually wrote a generic decision tree builder in C# (download). It uses Hunt's Algorithm to build the decision tree and uses Entropy as the measure to select attributes. At the moment, it can work only on records with nominal attributes (attributes like enums whose values are limited to a finite set). After training, it returns a decision tree, which can then be exported to XML or can be used to predict classes for new records.

Enough of the theory, let's see it in action. Here's how code that uses my tree builder looks.

class TruthTableEntry : Record<bool>
{
    public bool P1 { get; set; }
    public bool P2 { get; set; }

    public override bool Equals(object obj)
    {
        var other = obj as TruthTableEntry;
        if (other == null)
            return false;

        return other.P1 == this.P1 && other.P2 == this.P2;
    }

    public override int GetHashCode()
    {
        return P1.GetHashCode() ^ P2.GetHashCode();
    }
}

static void Main(string[] args)
{
   TruthTableEntry[] table = 
   {
       new TruthTableEntry() { P1 = true, P2 = true, Class = true },
       new TruthTableEntry() { P1 = true, P2 = false, Class = false},
       new TruthTableEntry() { P1 = false, P2 = true, Class = false},
       new TruthTableEntry() { P1 = false, P2 = false, Class = false }
   };

   var tree = new TreeBuilder<TruthTableEntry, bool>().Train(table);
   string predicate = FormPredicate(tree.RootNode, "");
   Console.WriteLine(predicate);
}

The TruthTableEntry class represents a row in the truth table above, and an array of those records are given to the TreeBuilder instance's Train method. The decision tree returned by it is then translated into a predicate by the FormPredicate method. Here's how the tree looks in XML if you call Save on the tree.

<?xml version="1.0" encoding="utf-8"?>
<Node ParentConditionValue="" SplitAttribute="P1">
  <Node ParentConditionValue="True" SplitAttribute="P2">
    <Node ParentConditionValue="True" Class="True" />
    <Node ParentConditionValue="False" Class="False" />
  </Node>
  <Node ParentConditionValue="False" Class="False" />
</Node>

which exactly matches what we expected.

The FormPredicate method attempts to transform the tree into a predicate clause, as expressed mathematically in predicate logic. For the above tree, it returns

(P1 ^ P2) v (~P1 ^ False)

which when reduced through the laws of predicate logic

(P1 ^ P2) v (~P1 ^ False)

= (P1 ^ P2) v False (since False ^ P == False)

= (P1 ^ P2)         (since False v P == P)

And there you have it, the computer figured it out correctly. Yowza :)

If you aren't familiar with implementing the Dispose/Finalize pattern to clean up resources, stop and read this first. It is really important to get the implementation of the pattern right, or you'll run into a performance problem at best, or risk leaking and running out of resources at worst.

Assuming that you've implemented the pattern correctly for your types, how do you guarantee that Dispose is called on all finalizable types in your application? Sure, you have finalizers, but depending on them for cleanup is bad because

1. There is a definite cost to finalization. An object for which a finalizer runs requires an extra garbage collection cycle to get GC'ed.

2. Your finalizers may not run at all. If your application chews up resources in a way that doesn't trigger a garbage collection, you might run of resources and crash long before the GC (and the finalizer) decides to run.

Finding undisposed objects implementing finalizers becomes important then. Windbg with SOS has the !finalizequeue command that can show you objects that are ready for finalization. If you have only a few distinct types in that list that are created and used in very few places, !finalizequeue is all you need - just look for missing Dispose calls in those places, add them and you're done.

Oftentimes it isn't that simple though - a certain type could be used throughout your code base and hunting down missing Dispose calls on that type will quickly turn into an exercise in frustration. Wouldn't it be great if a tool could show you the list of finalized objects, along with the something that tells you where they were created and used?

Undisposed (http://undisposed.codeplex.com/) does exactly that. It uses the CLR profiling API to watch for finalizations and object allocations, and matches them to show you constructor stack traces for finalized objects. All you have to do is launch your application from Undisposed and then run your application through a set of scenarios exercising various code paths. Once your application is closed, Undisposed's Log Viewer (screenshot below) will open up, showing you the number of undisposed objects per type, with each type grouped by constructor stack trace.

If you do download the software, remember to register the Undisposed COM dll using

regsvr32 Undisposed.dll

The software is still in Alpha, so please treat it like any pre-release software. Based on my very limited testing, it works reasonably well when you give it a limited set of types - otherwise, it tends to slow down the host application a little too much.

I'm looking for feedback and ideas, so feel free to comment.

PS : The inspiration for Undisposed came from this forum post on CodeProject - that's when I realized I could automate the whole thing :)

I'll bet a hundred bucks that any entry level C++ interview or exam will somehow drift into questions about the pre and post increment operators. It's almost become a canonical, rite of passage sort of thing.

Now using the operators is one thing, overloading them for your own types is another. In C++, you write something like

class X {
    int val;
public:

    X() : val(0){ }

    X operator++() { val++; return *this; }
    X operator++(int) { X pX = *this; val++; return pX; };

    int Value() { return val; }
};

Fairly straightforward stuff - C++ uses the int overload to distinguish between pre and post, and the post increment overload copies itself before incrementing and returns the copy.

Now let's see how to do this in C#.

class X
{
    public int Value { get; set; }

    public static X operator ++(X p)
    {
        int x = p.Value;
        return new X() { Value = x + 1 };
    }
}

No, there's no separate overload for the other one - the same method works for both pre and post increment operations. The compiler does the work of generating code that exhibits correct pre and post increment behavior. For code like

X x = new X();
X y = x++;

it generates

X x = new X();
X y = x;
x = X.op_Increment(x);

and for code like

X x = new X();
X y = ++x;

it generates

X x = new X();
X y = x = X.op_Increment(x);

Nifty, eh?

But wait, did you notice the difference between the C++ and C# overload implementation? The C# overload does not modify the original at all and always returns a copy, whereas the C++ code always modifies the current instance and returns a copy only for the post increment overload. Looking at the generated code, it should be easy to understand why - the compiler can't do its magic if the overload tinkers with the original instance.

Did you notice that X is a reference type?

X x = newX();
Xy = x;

x++;

Given that x and y are referring to the same object after executing the second line, shouldn't the increment be visible from y as well? It doesn't happen though, because the overload returns a new instance that then gets assigned to x, leaving y referring to the "old" unmodified instance.

All this confusion will not arise if X is a value type. The assignment of x to y will create a copy, so there's no possibility of changes in x reflecting in y. And modifying the passed instance from within the operator overload will have no effect on the original instance either.

Moral of the story : watch out when overloading operators on reference types.

If you use Skype, do you know that you can program against it? Head over to developer.skype.com if you're interested. There's a COM API, one for Java and even one for Python.

Just to show how easy it is, we'll write a bot in .NET that will simply echo whatever is sent to it.

You first need to download Skype4COM, a COM library provided by Skype developers to control Skype.

Create a WinForms application in your favorite version of Visual Studio (>= 2005), and in the default Form class, paste the following piece of code

public partial class MainForm : Form
{
    Skype skype;
    Dictionary<string, Session> userSessions = new Dictionary<string, Session>();

    public MainForm()
    {
        InitializeComponent();
    }

    private void Form1_Load(object sender, EventArgs e)
    {
        skype = new SkypeClass();
        skype.Attach(5, false);
        skype.MessageStatus += new _ISkypeEvents_MessageStatusEventHandler(skype_MessageStatus);
    }

    void skype_MessageStatus(ChatMessage pMessage, TChatMessageStatus Status)
    {
        if (Status == TChatMessageStatus.cmsReceived)
        {
            string text = pMessage.Body;
            string response = "Echoing " + text;
            skype.SendMessage(pMessage.FromHandle, response);
        }
    }

    private void Form1_FormClosing(object sender, FormClosingEventArgs e)
    {
        skype.MessageStatus -= new _ISkypeEvents_MessageStatusEventHandler(skype_MessageStatus);
    }
}

Add a reference to Skype4COM and build the code. Make sure Skype is running before launching this application. You'll need to accept accessing Skype from this application by hitting the "Accept" button when Skype asks- the Skype developers put it in there to avoid malicious code taking control.

That's all there is to it. If you now send a message to the currently signed in user, you should get back the same message text prefixed by "Echoing".

There are a lot of other things you could do with the  library, but the documentation is pretty thin, so you'll have to experiment a bit to get things working.

Still, it's pretty neat and I can see plenty of situations where a bot running on Skype would be useful. Imagine chatting with your bot running on your home PC, asking it the list of running applications. Skype takes care of NAT, firewall and other network related issues for you. How cool would it be to ask your build server bot the version number of the previous week's build?

There are times when you feel really proud of yourselves; on top of the world, with no one in sight. And then there are times when you can't believe you did what you just did. Here's one of the latter :-

My task was to show a progress bar in our application. Nothing fancy there - just division of the operations to be performed into equal size chunks and Incrementing after completion of each task. Very straightforward indeed.

	int increment;

        private void Form_Load(object sender, EventArgs e)
        {
            int discreteOperationsCount = GetDiscreteOperationsCount();
            increment = (int)Math.Ceil((double)progressBar.Maximum / discreteOperationsCount);
        }

        private void OperationCompleted()
        {
            progressBar.Increment(increment);
        }

It worked great when I tested it with 5, 10, 20 operations. I was even pleased that I cast the numerator to double straightaway, as I was typing code.

Only until I found that the progress bar progresses too fast if the number of operations is more than 100. If the result of the division is less than 1, Math.Ceil pushes it up to 1, which means that the progress bar will be full when 100 (the default Maximum value) operations complete, regardless of the actual number of operations.

Doh.

Ok, I thought, so let's store increment as a double and call Increment with that number. It would have worked, but for the fact that Increment does not have any overloads - it only accepts an integer. Hmm.. what gives?

After a little bit of thought, I figured out a way - scale everything by the degree of precision needed. With a scaling factor of 10, the calculation now becomes

increment = Math.Ceil((double)progressBar.Maximum / discreteOperationsCount * 10);

If discreteOperationsCount is 520, for example, then increment would become (100 * 10) / 520 * 10 = 19. We still have an integer, but it is more precise than the one calculated earlier.

Of course, you could increase the scaling factor further, and the number of significant digits will also increase exponentially. But the progress bar will have to do some approximation when mapping progress to pixels on the screen, so beyond a point, the increase in precision doesn't pay off that much.

Like I said at the top of this post, I couldn't believe I missed testing with the number of operations greater than the progress bar's Maximum. Truly one of those 'doh' moments.

There have been a lot of blog posts about why calling Thread.Abort from one thread to abort another is a bad idea. If you're still wondering if it actually is that bad, you'll be convinced by the end of this blog post :).

The other day, I was investigating frequent hangs in our application on the production machine. The only clue was that the last logged exception was a ThreadAbortException. What made it interesting was that in some cases, the application continued to run fine after logging the exception.  As I continued to look at the log data, I realized that every time the application hung, the ThreadAbortException's stack trace had a particular third party library's method at the top of the stack. The conclusion was that the application hanged whenever the thread was aborted when executing the third party library's code.

Reflector and half an hour later, the reason for hanging became clear. The third party code looked like this :-

void DoX()
{
    Monitor.Enter(lockObj);
    //Do some interesting stuff
    Monitor.Exit(lockObj);
}

Now do you see why?  If the ThreadAbortException gets thrown after acquiring the lock but before releasing it, the lock gets orphaned and no other thread will be able to acquire it. Ever. The third party library is used heavily by our app, so any thread that calls DoX after the abort will hang forever.

OK, so let's set it right then.

void DoX()
{
    lock(lockObj)
    {
        //Do some interesting stuff
    }
}

The compiler will emit a try/finally block and will call Monitor.Exit from the finally block. That should solve the problem, right?

Maybe.

The CLR guarantees that it won't throw ThreadAbortExceptions when running finally blocks (and CERs and constructors), so once the finally block starts executing, we're safe. But what about if there is (JIT compiler generated) code that is run after the try block but before the finally block?

Even assuming there is no such code, things can still fail.

void DoY()
{
    using (StreamReader sr = new StreamReader("Test.txt"))
    {}
}

If a ThreadAbortException is thrown after the StreamReader constructor runs, but before the constructed instance gets assigned to the local variable (sr), then sr won't be disposed.

The bottom line is that it is really hard to write code that works properly in the face of ThreadAbortExceptions. And even if you somehow manage to write it, you can never be sure that all your external libraries are written to cope with it.

Moral of the story : Listen to all the good advice and don't call Thread.Abort from another thread :)

C++ itself is a pretty complex language, and C++/CLI, with its own baggage of things like handles and managed references doesn't make it easy to read or debug code at a glance. Here's a piece of code that had me head-scratching for a while.

enum class Options { Yes, No, Maybe};

void Func(Options ^g)
{
   Console::WriteLine(g == Options ::Yes);
}

void Func()
{
    Func(Options::Yes);
}

If you run the above piece of code, it will print False. Pretty weird huh?

It seems inexplicable, until you notice the caret sign (^) before g in the formal parameter declaration of Func. The caret symbol causes the enum to be boxed, and the == operator then does a reference comparison. Which will obviously fail, because a valid reference handle will never be zero. To verify that it is indeed comparing addresses, try changing the code to read  g->Equals(Options::Yes) - you'll find that it prints True. Of course, taking away the caret sign will work as well, and that is what the programmer intended in this particular case - the caret was a typo.

I'm surprised that the compiler doesn't offer much of a help here, not even a warning. Especially the part where it does a reference comparison between a handle and an int. The equivalent C# code

((object)g) == Options.Yes

fails with a compiler error.

With great power comes great responsibility, I guess :)

Implementing IEnumerable<T> can turn out to be tricky in certain cases. Consider the following code snippet

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            Consume(new List<string>() { "a", "b", "c" });
        }

        static void Consume<T>(IEnumerable<T> stream)
        {
            T t1 = stream.First();
            T t2 = stream.First();

            Console.WriteLine(t1.Equals(t2));
        }
    }
}

As you'd expect, it prints true. Each First() call results in a call to stream.GetEnumerator(), and each such enumerator returns elements from the beginning of the list, so calling First() twice returns the same (first) element. All good so far.

Here's a tiny class.

        class StringGenerator
        {
            int index;

            public string GetNext()
            {
                return (index++).ToString();
            }
        }

As you can see, it generates whole numbers as strings. Not very convenient to use though, wouldn't it be great if we can wrap it and make it enumerable?

        static IEnumerable<string> ConvertToEnumerable(StringGenerator g)
        {
            string item = null;

            while ((item = g.GetNext()) != null)
                yield return item;
        }

ConvertToEnumerable simply loops over the list of items generated and makes use of yield return to make it enumerable.

Great, now what does

        Consume(ConvertToEnumerable(new StringGenerator()));

print?

It prints false.

False? FALSE? Can you figure out the reason?

If you've read Raymond's posts on implementation of iterators, you should have figured it out by now. The crux of the problem is that all enumerators returned share the same instance of StringGenerator.  Calling First() twice results in two calls to GetNext() on the same StringGenerator instance, and the values returned will obviously be different. To verify that, try creating the StringGenerator instance inside the ConvertToEnumerable function - it will print true now.

This bit me when I wrote code that parsed stuff out of an IEnumerable<string> instance. The actual program read text from a file, so I had a ConvertToEnumerable routine just like the one above, except that it took TextReader as the parameter. The Consume method passed the constructed IEnumerable<T> instance to various methods (say Method1 and Method2), with the assumption that whatever Method1 read off the stream won't be read again by Method2.

As we saw just now, this works if Consume is passed an IEnumerable<T> constructed like the StringGenerator case. It fails badly if a List<string> is passed instead. Because I wanted the "read elements off the stream" behavior, I called GetEnumerator() once for the passed IEnumerable<T> and then changed the methods called by Consume to take that IEnumerator<T> instead of IEnumerable<T>. That made the code work correctly for both cases.

Moral : Make sure you understand the implications when yield returning items off a shared item source.

Where Am I, a Windows Mobile app that I was working on, is now available for download. You can get the binaries from http://www.codeplex.com/wami. There is still a lot of fit and finish work to be done, but with the core functionality working fine, I decided to let it out in the wild and get some feedback.

There is RouteLogger.exe, which runs on the mobile phone and records cell broadcast information to a log file, along with the time interval between successive broadcasts. RouteEditor.exe, which runs on the PC, allows you to group the logged location information into names of places that you can recognize readily. RouteEditor saves the information into route files, which can then be loaded by wami.exe, running on the mobile phone. Wami gets the current cell broadcast location, indexes into the route information, and estimates the time needed to reach the final destination and intermediate points along the way.

Oh, and Wami is open source, so you can take a peek at the source code if you're interested. This being my first Windows Mobile app, your comments about the application, its usability and the source code are most welcome.

This is one topic that keeps popping up every now and then. A lot of people seem to be curious about the performance implications of using one versus the other, and not unexpectedly, a lot of different answers come up.

To settle it once for all, here's a small program that uses both of them.

namespace ConsoleApplication
{  
    class Program
    {
        static void Main()
        {
            Method1();
            Method2();
            Console.ReadLine();
            Method1();
            Method2();
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        static void Method1()
        {
            string s = "";
            DoNothing(s); 
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        static void Method2()
        {
            string s = string.Empty;
            DoNothing(s);
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        static void DoNothing(string s)
        {
            Console.WriteLine(s);
        }
    }
}

As you can see above, Method1 and Method2 call DoNothing, passing "" and string.Empty respectively. Now how do we compare these two? Easy, just look at the jitted code - after all, that's what is going to run on the machine.

We'll use Windbg to disassemble the code after the JITter did its job. And if you're wondering why Method1 and Method2 have been called twice, now you know why - the second time around, we can look at the JITted code that was generated as part of the first time execution of each of those methods.

So breaking into the debugger at Console.ReadLine() and dumping the method descriptors for Program

0:003> !Name2EE Sample.exe!ConsoleApplication.Program
...
MethodTable: 002a3048

0:003> !DumpMT -MD 002a3048
...
--------------------------------------
   Entry MethodDesc      JIT Name
...
00860070   002a3020      JIT ConsoleApplication.Program.Main()
008600a8   002a3028      JIT ConsoleApplication.Program.Method1()
00860100   002a3030      JIT ConsoleApplication.Program.Method2()
008600c8   002a3038      JIT ConsoleApplication.Program.DoNothing(System.String)
002ac021   002a3040     NONE ConsoleApplication.Program..ctor()

shows the method descriptors for all the methods in that class. Now, using !u to disassemble code for Method1

0:003> !u 002a3028
Normal JIT generated code
ConsoleApplication.Program.Method1()
Begin 008600a8, size d
008600a8 8b0d3c30e402    mov     ecx,dword ptr ds:[2E4303Ch] ("")
008600ae ff158c302a00    call    dword ptr ds:[2A308Ch] (ConsoleApplication.Program.DoNothing(System.String), mdToken: 06000004)
008600b4 c3              ret

and then for Method2

0:003> !u 002a3030
Normal JIT generated code
ConsoleApplication.Program.Method2()
Begin 00860100, size c
00860100 8b0d2c10e402    mov     ecx,dword ptr ds:[2E4102Ch] ("")
00860106 e8bdffffff      call    008600c8 (ConsoleApplication.Program.DoNothing(System.String), mdToken: 06000004)
0086010b c3              ret

shows that, surprise surprise, the generated assembly code is identical. The only difference is the address referenced in the mov instruction.

So there you have it - the JITter generates the same code whether you use String.Empty or "", and there should no difference in performance.

PS : It's interesting to note that the two addresses are different, even though the string contents are the same. Address 2E4303Ch in the disassembly for Method1 is the address referring to an interned string object with the content "". You can verify that by creating another string variable initialized to "" and disassembling that code - the same address (2E4303Ch) will be referenced there as well. What's surprising is that the address referenced in Method2 is different - which means the string object referenced by string.Empty is not the interned object. Wonder why - maybe because it's ngen'ned code?

This was one of the more challenging and interesting problems to debug in a while. When testing out code for an unrelated fix, I noticed that the application's handle count, as seen in the Handles column in Task Manager, kept rising steadily.

WinDbg, showed that the app was leaking thread handles.

0:003> !handle
1417 Handles
Type               Count
Event              452
Section            8
File               12
Port               2
Directory          3
Thread             916
Desktop            1
KeyedEvent         1 

Half expecting the code to hold references to dead threads, I dumped Thread objects in the GC heap.

0:003> !dumpheap -stat -type System.Threading.Thread
total 353 objects
Statistics:
      MT    Count    TotalSize Class Name
790fe284        2          144 System.Threading.ThreadAbortException
79124b74       32          640 System.Threading.ThreadHelper
791249e8       33         1056 System.Threading.ThreadStart
790fe704      286        16016 System.Threading.Thread
Total 353 objects

No luck there. This was perplexing - I knew the app created a lot of threads that do some work and die, but the Thread class is the only way the app deals with them, so if it's not Thread instances, who else was holding the handles open?

Realizing that barring a CLR bug, there must be some .NET object behind each handle, I dumped the entire GC heap, looking for types with the number of instances close to the number of handles.

 0:003> !dumpheap -stat
...
7912d9bc       25        54264 System.Collections.Hashtable+bucket[]
7b483294     1098        57096 System.Windows.Forms.CreateParams
7b48193c     1098        61488 System.Windows.Forms.Control+ControlNativeWindow
7912d8f8      544        72264 System.Object[]
7b48398c      819        85176 System.Windows.Forms.Application+MarshalingControl
7b4835ec      819       108108 System.Windows.Forms.Application+ThreadContext
0014c740       40       137064      Free
790fd8c4     7016       421636 System.String
Total 22730 objects

That number (819) of ThreadContext instances was pretty close to the number of open thread handles (916). Repeating the above exercise after letting the application run some more time confirmed the theory - the number of ThreadContext instances increased by almost the same extent as the number of open thread handles.

It should have been simple from now on - all that was left was to find the roots holding the ThreadContext instances and problem solved. 

0:003> !dumpheap -mt 7b4835ec
... 
0145b550 7b4835ec      132     
total 819 objects
Statistics:
      MT    Count    TotalSize Class Name
7b4835ec      819       108108 System.Windows.Forms.Application+ThreadContext
Total 819 objects

and then

 0:003> !gcroot 0145b550
 Note: Roots found on stacks may be false positives. Run "!help gcroot" for
more info.
Scan Thread 0 OSTHread 34c0
Scan Thread 2 OSTHread 34c8
DOMAIN(001546E8):HANDLE(Pinned):9f13f0:Root:02373030(System.Object[])->
013720f4(System.Collections.Hashtable)->
0142486c(System.Collections.Hashtable+bucket[])

Here's where the fun started. The main root was (System.Object[]), which indicated that the next object in the object graph (Hashtable) was a static member of some class. A search for static Hashtables in the application's source code turned up nothing. The only possibility then was the BCL - some class there must be holding a static Hashtable of ThreadContexts.

I got a lucky break there - Reflector showed that ThreadContext class had a static Hashtable and that it's constructor adds itself (this), to the hashtable. But who instantiates ThreadContexts? Reflector's "Analyze" command turned up too many method flows to go through one by one, so I decided to do it the other way - set up a breakpoint on ThreadContext's constructor and let the application run.

0:003> DumpMT -MD 7b4835ec
 EEClass: 7b483400
Module: 7b454000
Name: System.Windows.Forms.Application+ThreadContext
mdToken: 020001e4  (C:\WINDOWS\assembly\GAC_MSIL\System.Windows.Forms\2.0.0.0__b77a5c561934e089\System.Windows.Forms.dll)
BaseSize: 0x84
ComponentSize: 0x0
Number of IFaces in IFaceMap: 1
Slots in VTable: 64
--------------------------------------
MethodDesc Table
   Entry MethodDesc      JIT Name
...
7b664ad4   7b4a76b0   PreJIT System.Windows.Forms.Application+ThreadContext..ctor()
 and then
0:003> !bpmd -md 7b4a76b0   

MethodDesc = 7b4a76b0
Setting breakpoint: bp 7B06B934 [System.Windows.Forms.Application+ThreadContext..ctor()]

 When the breakpoint was hit, the stack looked like this

 !CLRStack 
OS Thread Id: 0x2c90 (3)
ESP       EIP     
0106ea74 7b06b934 System.Windows.Forms.Application+ThreadContext..ctor()
0106ea78 7b06b8cc System.Windows.Forms.Application+ThreadContext.FromCurrent()
0106ea80 7b06b885 System.Windows.Forms.WindowsFormsSynchronizationContext..ctor()
0106ea90 7b06b7b2 System.Windows.Forms.WindowsFormsSynchronizationContext.InstallIfNeeded()
0106eabc 7b06a09b System.Windows.Forms.Control..ctor(Boolean)
0106eb30 7b068f75 System.Windows.Forms.Label..ctor()
0106eb3c 00d5012b LanguageFeatures.Program.<Main>b__0()
0106eb44 793b0d1f System.Threading.ThreadHelper.ThreadStart_Context(System.Object)
0106eb4c 79373ecd System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object)
0106eb64 793b0c68 System.Threading.ThreadHelper.ThreadStart()
0106ed8c 79e7c74b [GCFrame: 0106ed8c]  

As the stack dump shows, the ThreadContext was created as part of System.Windows.Forms.Control's constructor to set the synchronization context of the thread to WindowsForms. The problem was that created context didn't die when the thread died. Some more poking around with Reflector showed that the instance is removed from static Hashtable when the thread receives a quit message (via Application.ExitThread, for example). The threads in the app were not pumping messages, so the ThreadContexts kept accumulating in the Hashtable, keeping the associated Thread handle open. Here's some code that demonstrates the problem.

class Program
{
   static void Main(string[] args)
   {
      while (true)
      {
         new Thread(delegate() { new System.Windows.Forms.Label(); }).Start();
         Thread.Sleep(100);
      }
   }
}

Bottomline - don't create controls from non-message pumping threads, especially if you create lots of threads over the lifetime of the application.

It seems obvious in retrospect, but in the application's case, it was not using the control visually, so it didn't really need WM_PAINT or the hundred other messages that a control needs to work. The fix was to move control creation to a GUI (message pumping) thread and then Invoke/BeginInvoke from the other threads.

That's my first Windows mobile application you're seeing below.

Most cellular service providers in India broadcast the location of the communicating cell tower to the phone. Where Am I (Wami) is a managed Windows Mobile application that uses the broadcast information to let you know where you are and when you will reach your destination. The screenshot above shows that I'm at INDIRA NAGAR, somewhere close to TIDEL PARK and that I'll reach home at 12:59 AM.

How does Wami do this? There's a sister application, RouteLogger, that automatically logs cell tower locations (INDIRA NAGAR, for e.g) along with the time taken to reach the current location from the previous location. You take the route log generated by RouteLogger, group the locations into broad categories that you can readily identify (TIDEL PARK, for e.g.) and then give those route details to Wami. Wami then uses that information, and the current cell tower location, to tell you where you are and when you will reach the final destination as well as intermediate locations.

I wrote this application to solve a specific problem - knowing my whereabouts when taking an overnight train. I travel to my hometown once a month and I usually choose to take an overnight train. When I wake up, I have no idea where I am or when the train will reach my hometown. Wami tells me both.

I figured that it will be useful to a lot of other people as well. The code is not ready for primetime yet, but I'll be releasing a beta version shortly. I'm also planning to set up a website that'll allow people to share route logs. If you are interested in Wami, please post a comment so I know and keep watching this space!

Tee is a cool function that "clones" enumerators whatever their current state is - it basically allows you to branch off an enumerator into as many enumerators as you want, all independent of each other.

 You can do something like

List<int> list = new List<int> { 1, 2, 3, 4, 5 };

IEnumerator<int> iterable1 = list.GetEnumerator();

IEnumerator<int> []teedIterables = Itertools.Tee(iterable1, 2);

foreach(int val in teedIterables[0])
{
   Console.WriteLine(val);
}

foreach(int val in teedIterables[1])
{
   Console.WriteLine(val);
}

// prints 1 2 3 4 5 1 2 3 4 5

If there was a iterable1.MoveNext() before the call to Tee, then the output would have been 2 3 4 5 2 3 4 5. The implementation proved to be pretty interesting - and complicated, partly because the C# compiler does not allow the yield statement inside anonymous methods. Here's the implementation.

public static IEnumerator<T>[] Tee<T>(IEnumerator<T> source, int count)
{
    List<T> tValues = new List<T>();
    IEnumerator<T>[] results = new IEnumerator<T>[count];

    for (int i = 0; i < count; ++i)
    {
       int currentLocation = 0;
       results [ i ] = CreateEnumerator(source, new EnumeratorState<T>() { CurrentLocation = currentLocation, TValues = tValues });
    }

    return results;
}

private static IEnumerator<T> CreateEnumerator<T>(IEnumerator<T> source, EnumeratorState<T> state)
{
   while (true)
   {
      if (state.CurrentLocation < state.TValues.Count)
      {
          yield return state.TValues[state.CurrentLocation++];
      }
      else
      {
         if (source.MoveNext())
         {
            state.TValues.Add(source.Current);
            state.CurrentLocation = state.TValues.Count;
            yield return source.Current;
         }
         else
         {
             break;
         }
      }
   }
}

class EnumeratorState<T>
{
   internal int CurrentLocation { get; set; }
   internal List<T> TValues { get; set; }
}

There's a fair bit of code involved, as you can see. The basic idea behind the implementation is to maintain a list as a backing store. Each teed off enumerator attempts to read from the list - if it hits the end of the list, it advances the original enumerator  and gets the current value, updates the list and returns that value. The rest of the code is plumbing to work around the inability to use yield inside an anonymous method. The code basically does what the compiler would have done - there's the EnumeratorState class to hold captured variables and a new instance of the class is created and passed to CreateEnumerator, which is in the place of the anonymous method.

Tee is that kind of function that is incredibly useful once you know you can do such a thing. Let's say you have an application that needs to process lines in a file, but the processing can happen in different contexts, independent of each other. Take for example, a log parser, that goes through each line in a file, looking for the start of an operation. The log parser notifies another component once it finds the start of the operation and proceeds through the file looking for the next operation. Normally, you'll solve the problem by adding the component to a list that gets notified after the parser reads each line. With Tee, you can simply tee off an enumerator and pass it to the other component - both the log parser and the component now have independent enumerators and can actually run in parallel. And you can tee off as many enumerators as there are components.

With that, we come to the end of this series of blog posts on implementing itertools in C#. The source code for all the functions implemented in the series is available at http://code.msdn.microsoft.com/itertools. 

Cycle

IEnumerable Cycle(IEnumerable iterable)

Cycle keeps cycling through the enumerator, that is, it cycles back to the first element when the enumerator is exhausted. You can use it like

IEnumerable<int> source = new List<int>() { 1, 2, 3};
foreach(int element in Itertools.Cycle(source))
{
   Console.WriteLine(element); // prints 1 2 3 1 2 3..
}

The implementation is again very straightforward - all we have to do is wrap the foreach over the iterable in an infinite loop. The outer loop while loop creates a new enumerator for every iteration, as foreach calls GetEnumerator() before looping over the returned enumerator.

public static IEnumerable<T> Cycle<T>(IEnumerable<T> iterable)
{
   while (true)
   {
      foreach (T t in iterable)
      {
          yield return t;
      }
   }
}

Zip

IEnumerable<T[]> Zip<T>(params IEnumerable<T>[] iterables)

Zip returns an enumerable array of elements, with each array containing one element per input iterator. The first array contains the first element of every iterator, the second array has every second element and so on.

IEnumerable<int> e1 = new List<int>() { 1, 2, 3};
IEnumerable<int> e2 = new List<int>() { 4, 5, 6};
IEnumerable<int[]> zippedValues = Itertools.Zip(e1, e2);
foreach(int[] arr in zippedValues)
{
   Console.WriteLine("{");
   foreach(int val in arr)
       Console.WriteLine(val);
   Console.WriteLine("}");
}

This prints {1,4}, {2,5}, {3,6}

The implementation is slightly more complex.

public static IEnumerable<T[]> Zip<T>(params IEnumerable<T>[] iterables)
{
   IEnumerator<T>[] enumerators = Array.ConvertAll(iterables, (iterable) => iterable.GetEnumerator());

    while (true)
    {
       int index = 0;
       T[] values = new T[enumerators.Length];

       foreach (IEnumerator<T> enumerator in enumerators)
       {
           if (!enumerator.MoveNext())
              yield break;

            values[index++] = enumerator.Current;
       }

       yield return values;
    }
}

The code gets enumerators for all the iterables, moves all enumerators forward, accumulates their current values into an array and yields the array. It does this until any one of the enumerators runs out of elements.

Next time, we'll look at Tee - an interesting function that also proved to be a little tricky to implement.

If you are a C# developer and haven't taken a look at the itertools python module so far, you owe it to yourself to learn about it. It's a module with functions that operate on what Python calls "iterables" (IEnumerable in C#). Go ahead, take a look at it before reading on.

This got me interested about implementing similar functions in C#, using IEnumerable<T>. I fired up VS 2008 and started cranking out the code, only to find that most of the itertools functions are already implemented as extension methods on IEnumerable<T> in .NET 3.5. Some of the functions even have the same name, like Repeat and TakeWhile. I found four functions that weren't directly available as IEnumerable<T> methods and decided to implement them. Let's take a look at them, one by one.

Chain

IEnumerable<T> Chain<T>(params IEnumerable<T>[] iterables)

Chain returns one flat view of all the enumerators chained together. IEnumerable<T>.Concat does the same thing, but you'll have to call it multiple times to chain more than one iterator. Chain can be used to do things like

IEnumerable<int> e1 = new List<int>() { 1, 2, 3};
IEnumerable<int> e2 = new List<int>() { 4, 5, 6};
IEnumerable<int> e3 = new List<int>() { 7, 8, 9};

IEnumerable<int> chained = Itertools.Chain(e1, e2, e3);

foreach(int element in chained)
{
   Console.WriteLine(element); // prints 1 2 3 4 5 6 7 8 9
}

The implementation is fairly straightforward, thanks to the incredibly useful yield statement.

public static IEnumerable<T> Chain<T>(params IEnumerable<T>[] iterables)
{
   foreach(IEnumerable<T> iterable in iterables)
   {
      foreach (T t in iterable)
      {
         yield return t;
      }
   }
}

The observer effect "refers to changes that the act of observing will make on the phenomenon being observed.". How infuriating would be a bug that demonstrates that effect - things work when you see them, don't when you don't?

There's this third party Winforms control I use that does a lot of custom painting. Think of it as a chart control that displays live stock data one stock at a time, with the stock changing every few minutes. Everything was ok, until I happened to see the chart all mixed up on a colleague's machine. On taking a closer look, I figured out that the images for the previous stock were not cleared by the control, before it drew them for the current stock.

Easy fix - it must be either incorrect data or the control failing to refresh, I thought. I checked the data, that was fine. Explicitly calling Refresh - nope, that didn't work either.

Hmm, I figured if I could reproduce this on my machine, I could attach a debugger and fix this. And that's where the fun started. It simply would not happen on my machine - no matter what I tried. Finally, out of desperation, I moved to a different screen that would hide the control as it was painting and sure enough, the painting was messed up when the control was visible again.

It was time to look at the source code for the control. The reason for the garbled painting was easy to find - the control caches the bitmap used for drawing. As newer data comes in, it draws them on top of the cached bitmap. For some reason, the cached bitmap was not getting invalidated when the stock changed. The invalidation of the cached bitmap is controlled by a flag. The flag is set when new data is coming in and is reset when the code hosting the control calls Reset.

My code is missing the Reset, I thought, but that should lead to garbled displays always, not just when the control is invisible. And then it struck me - the code doing the actual invalidation of the cached bitmap was inside the OnPaint method.

If the control happens to be visible when Reset is called, the painting code gets triggered, the flag is false and the bitmap is disposed. If it is invisible during Reset AND becomes visible only after new data starts flowing in, the flag would have been reset to true and the control would continue drawing on top of the cached bitmap, messing up the display.

The fix was to invalidate the cache inside Reset as well. 

Every now and then, you hit some problem that a programming language helps solve very cleanly. Here's the problem.

You are writing a series of functions that return a bool depending on some condition (predicates). Something like

bool Foo(State t);

Let's also assume that State is defined as

class State  { Color c; ... }

You have a set of colors, known at compile time, for which Foo should return true. How would you go about doing it?

You could pack the set of colors into an array and write Foo so that at runtime, it searches the color array and returns true if the color passed is in the array. Something like

bool Foo(State t) { return colors.IndexOf(t.Color) != -1; }

Assume that, for design reasons, it isn't really possible to allow access to colors from within Foo. Then what?

Anonymous methods and closures, of course. How about writing a function, that returns a Foo that returns true only if the color matches. Whew, that sounds confusing, but the code looks pretty simple.

Foo GenerateFoo(Color color) { return delegate(Color passedColor) { return color == passedColor; } }

You can then call GenerateFoo(Color.Red) to get a Foo that will return true only if it is called with Color.Red, call GenerateFoo(Color.Orange) to get one that returns true only if called with Color.Orange and so on.

Foo redFoo = GenerateFoo(Color.Red);
Foo orangeFoo = GenerateFoo(Color.Orange);
Console.WriteLine(redFoo(Color.Red)); // prints true
Console.WriteLine(redFoo(Color.Yellow)); // prints false

Nifty, eh?

There is a description of the bug here. The following piece of code demonstrates the bug.

    class Program
    {
        interface I
        {
            int X { get; set; }
        }

        struct S : I
        {
            public int X { get; set; }
        }

        static void Main(string[] args)
        {
            Func<S>();
        }

        static void Func<T>() where T : I, new()
        {
            var c = new T() { X = 1 };
            Console.WriteLine(c.X);
        }
    }

The code prints 0 instead of 1. The bug goes away if object initializers are not used - changing var c = new T() { X = 1 }; to var c = new T(); c.X = 1; will print 1.

I had assumed all along that object initializers were transformed into property setters at the source code level (or somewhere above IL). This bug doesn't help much to confirm that :)

Anyway, let's see what's causing the problem. Peeking into the generated IL, 

   .locals init (
        [0] !!T c,
        [1] !!T <>g__initLocal0,
        [2] !!T CS$0$0000)
        ... // Store zeroed out instance of S in locals[1]
    L_0022: ldloc.1 
    L_0023: box !!T
    L_0028: ldc.i4.1 
    L_0029: callvirt instance void CSharp3Test.Program/I::set_X(int32)
    L_002e: nop 
    L_002f: ldloc.1 
    L_0030: stloc.0 
    L_0031: ldloca.s c
    L_0033: constrained !!T
    L_0039: callvirt instance int32 CSharp3Test.Program/I::get_X()
    L_003e: call void [mscorlib]System.Console::WriteLine(int32)

 Can you spot the problem now?

You can see that at L_0023, S is boxed and the boxed instance is used to make the virtual call to set X. You can also see that the boxed instance is not stored in any of the local variables, the callvirt instruction pops it off the stack and then it's gone. To load the value of X, the callvirt instruction is given a reference to c (locals[0]), which contains the unboxed instance of the struct. Which is why we are getting a 0 (the default value), instead of 1. Essentially, the compiler is generating the equivalent IL for something like 

   S s = new S();
   I i = s;
   i.X = 10;
   Console.WriteLine(s.X);

This again prints 0 instead of 10, because i is assigned a different (boxed) instance of S and therefore changing i.X doesn't change s.X.

   .locals init (
        [0] !!T c,
        [1] !!T CS$0$0000)
    L_0021: stloc.0 
    L_0022: ldloca.s c
    L_0024: ldc.i4.1 
    L_0025: constrained !!T
    L_002b: callvirt instance void CSharp3Test.Program/I::set_X(int32)
    L_0030: nop 
    L_0031: ldloca.s c
    L_0033: constrained !!T
    L_0039: callvirt instance int32 CSharp3Test.Program/I::get_X()
    L_003e: call void [mscorlib]System.Console::WriteLine(int32)

The box instruction is gone, instead, the compiler has generated a constrained prefix for the callvirt instruction. MSDN says that

"When a callvirt method instruction has been prefixed by constrained  thisType, the instruction is executed as follows:

• If thisType is a reference type (as opposed to a value type) then ptr is dereferenced and passed as the 'this' pointer to the callvirt of method.

• If thisType is a value type and thisType implements method then ptr is passed unmodified as the 'this' pointer to a call  method instruction, for the implementation of method by thisType.

• ...
  

 "

In other words, the address of the instance is passed as the this parameter to the call method - no boxing at all. If you'd looked carefully enough, the getter for X uses the constrained prefix, even in our buggy IL (the first listing).

That explains the bug then, but opens up another question. If virtual dispatch can be done for a value type without boxing, then why not do it that way for

   S s = new S();
   I i = s;
   i.X = 10;

 as well? Mind you, virtual dispatch doesn't mean anything for value types, as they cannot derive from or derived by anything else, so any callvirt instruction on value types can be treated as a straight call instruction. The constrained prefix does exactly this, after making sure that this is a value type. So why not use it for all virtual calls? Performance (not many value types implementing interfaces)?

What do you think? 

I'm glad that a lot of people found AJAXAvailability useful. For people who haven't heard about it, AJAXAvailability is a Greasemonkey script for IRCTC's website that loads availability information asynchronously and shows it in the availability table, right alongside the list of trains (more information here).

Mani suggested that the ability to sort the availability table based on departure time would be useful. That seemed like a nice idea, so here it is - SortItOut, a Greasemonkey script that modifies the availability table and makes the header texts clickable. Clicking on one of the headers, say "Departure time", sorts the table by the values in that column, in ascending order.Greasemonkey script to do that.

Clicking on the same header again will sort the table in descending order. 

You can sort by any column, except the one with radio buttons ("Select"). This script also works nicely with AJAXAvailability, in that it allows you to sort the table even when availability information is loading (unless you are sorting the table by availability information, of course). 

To install the script, install Greasemonkey first (if you haven't already), navigate to SortItOut and click Install. The next time you visit IRCTC's website and go to the "Plan My Travel" page, the script gets loaded and runs automatically.

That's all, folks - the rest of the post is about the technical details of how the script works, feel free to skip it if you're not interested.

The script works by getting the availability table's DOM object through an XPath expression and replacing the cells of the first row with dynamically created anchor elements. The click event of those elements are hooked up to a function that then sorts the table, based on the column's values. The sort function is pretty simple - it creates an array of objects, one object per row. Each object holds a reference to it's row and a reference to the value of the column in that row, on which the sort must be done.

The script then uses the Array.sort library function to do the sorting and then rearranges the rows in the table based on the sorted result. There are quite a few ways of rearranging the table -

1. Replace the existing HTML in each row with the HTML of the row to-be

2. Remove all rows in the table and create new rows and cells, based on the sorted output.

3. Use Greasemonkey's insertBefore to switch around "TR" DOM objects.

The first approach wouldn't work with AJAXAvailability. That script stores references to "TD" DOM elements, for updating availability information in the AJAX callback. Replacing the innerHTML of the table's rows would create new TD objects, breaking that script. There was another subtle problem when I tried doing this - my sorted array and the actual table hold references to the same TR DOM objects, so replacing the HTML in the table would also affect the sorted output.

The second approach will not work for the same reason - new TD elements will be created, and the AJAXAvailability script will update the now obsolete TD elements.

The third approach works because no new objects are created, existing TR objects are shunted around, based on the sorted output. This was also the simplest to code as well. Doesn't it feel great, when the best solution is the simplest and cleanest one as well?