the blog => anything goes

Wami 0.1 released

2008-07-02T16:25:28Z

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.

String.Empty versus "" - The real deal

2008-06-27T13:36:00Z

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?

The case of the leaking thread handles

2008-05-29T18:15:00Z

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.

Where Am I

2008-05-05T19:19:00Z

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!

Itertools for C# - Tee

2008-05-05T17:03:00Z

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.

Itertools for C# - Cycle and Zip

2008-04-26T05:21:00Z

Continuing our implementation of Python iterator functions in C#, we'll implement Cycle and Zip this time.

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;
      }
   }
}

The Python cycle function has a slightly different behavior - it caches elements in the iterable the first time around and then iterates over the cache after that. This means that changes to the collection will not be visible to the users of the cycle function, but only if the changes happen after cycle starts returning elements from its cache.

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.

Itertools for C#

2008-04-13T18:47:00Z

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;
      }
   }
}

Next up is the Cycle method. We'll see how it works in the next blog post.

The Observer Effect

2008-03-30T21:48:00Z

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.

Not just a function : Generating functions

2008-02-12T15:29:00Z

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?

C# 3.0 compiler bug - Using object initializers, generics and value types

2007-12-26T17:44:00Z

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.

But then how does doing the initialization in two steps (var c = new T(); c.X = 1) work. The answer - Two step initialization does not use boxing when setting the value of X. Here's how the generated IL looks.

   .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?

More greasemonkeying with IRCTC

2007-12-26T08:09:00Z

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?

Mucking around with instance field initializers - Part 2

2007-12-23T18:20:00Z

We saw in Part 1 that C# doesn't allow an instance field initializer to refer another field in the class. Before trying to figure out why, let's first see if this is a restriction imposed by C#, rather than by the CLR.

Some disassembling and reassembling later, this is what the new IL code looks like.

    IL_0000:  ldarg.0
    IL_0001:  ldc.i4.1
    IL_0002:  stfld      int32 ConsoleApplication1.Program::x
    IL_0007:  ldarg.0
    IL_0008:  ldarg.0
    IL_000b:  ldfld      int32 ConsoleApplication1.Program::x
    IL_0009:  ldc.i4.1
    IL_000a:  add
    IL_000c:  stfld      int32 ConsoleApplication1.Program::y
    IL_000d:  ldarg.0
    IL_000e:  ldfld      int32 ConsoleApplication1.Program::y
    IL_000f:  call       void [mscorlib]System.Console::WriteLine(int32)

It's basically the same code in Part 1, except for the initialization of y. Instead of initializing y to 2, the code tries to load this.x, add 1 to it, store the result in y (y = x + 1) and then print out the result. The call to the constructor of System.Object comes next, but I've left that out for clarity.

Guess what, it works! The code assembles, checks out with peverify and runs fine, printing the value 2.

So, it looks like the CLR does not have any problems accessing other instance fields when initializing them. Then why doesn't the C# compiler like them?

How about fields inherited from a base class? If C# doesn't have the instance field initializer restriction, then the following piece of code should compile . What do you expect the value of y to be?

    class A
    {
        protected int x = 1;
    }

    class B : A
    {
        int y = x + 1;
        B() { Console.WriteLine(y); }
    }

1? 2? It depends on where the C# compiler puts the instance field initialization code. According to the current spec, it's placed before the call to the base class constructor, which means that y will be initialized to 1. Suddenly, the derived class now gets to access uninitialized base class state. Not good at all.

You could argue that the compiler knows about inherited fields and therefore can apply the restriction only to those fields - but that would add a nasty special case to the "you-cannot-reference-during-instance-field-initialization" list. I don't think it will be intuitive either - a typical programmer will be surprised if a "Move to base class" refactor suddenly breaks working code.

Static fields don't have this problem - they aren't really "inherited". Which could be why the compiler allows static field initializers to reference other fields.

What do you think?

Mucking around with instance field initializers - Part 1

2007-12-06T13:02:00Z

What do you think of the following piece of code?

    class Program
    {
        int x = 1;
        int y = x + 1;
    }

Looks simple, except that it doesn't compile (error CS0236: A field initializer cannot reference the non-static field, method, or property 'Program.x')

Try making x and y static - the code will compile fine now. I have been trying to find out why - so far, I haven't got a clue. Just in case it's not obvious, I do know that moving y = x + 1 into the body of Program's constructor will get me what I want, but I was (and am) curious to know why field initializers, and only instance field initializers, aren't allowed to access non-static fields.

The C# spec says that field initializers "correspond to a sequence of assignments that are executed immediately upon entry to any one of the instance constructors", just before the call to the base class constructor. When I generated IL for Program's constructor after replacing y = x + 1 with y = 2, it looked like this

    L_0000: ldarg.0 
    L_0001: ldc.i4.1 
    L_0002: stfld int32 ConsoleApplication1.Program::x
    L_0007: ldarg.0 
    L_0008: ldc.i4.2 
    L_0009: stfld int32 ConsoleApplication1.Program::y
    L_000e: ldarg.0 
    L_000f: call instance void [mscorlib]System.Object::.ctor()
    L_0014: nop 
    L_0015: ret

The generated IL matches with the spec - 1 and 2 are stfld'ed into x and y before calling the base class constructor (System.Object::.ctor()).

The C# spec also says that a field initializer is not allowed to reference the this pointer - " variable initializer for an instance field cannot reference the instance being created." It doesn't say why though.

The IL shown above clearly indicates that this (ldarg.0) is valid when storing 1 and 2 into x and y. So why doesn't C# allow y = x + 1?

I initially wondered if that rule is to prevent code like this

    class Program
    {
        int x = y + 1;
        int y = x + 1;
    }

but then, the C# spec clearly says that the variable initializers will be run in "textual" order. If you combine that with the fact that x and y will be assigned their default values even before their variable initializers run, you'll see that the above code should run fine, resulting in x = 1 (because y is zero) and y = 2. You can make x and y static and run the code, you will see the same result.

So again, why? Can you figure out why? We'll do some more digging into this in the next post.

Type inference != Dynamic typing

2007-11-19T16:27:00Z

Local variable type inferencing is a new feature in C# 3.5 - a very "handy" one, in that it saves a lot of typing. Basically, it lets you do

var dict = new Dictionary<string, List<int, Dictionary<int, string>>>();

instead of

Dictionary<string, List<int, Dictionary<int, string>>> dict = Dictionary<string, List<int, Dictionary<int, string>>>();

That's pretty cool, but remember, C# is still a statically typed language. dict is statically bound to the type Dictionary<string, List<int, Dictionary<int, string>>> and you cannot change it. You cannot do

dict = Dictionary<int, string>();

in the same method. The compiler will complain that the type on the RHS is not convertible to the statically bound type of dict.

Contrast this to a dynamically typed language like Javascript, which also uses the var keyword to declare variables.

var x = 1;x = new Array();
x = "23";

Or to Python

x = 42x = def fn(z) : return z + 1

In such languages, variables (x, in our example) simply act as placeholders and get bound to the type of the value they are holding at the moment. In the first example, x is holding an integer after executing the first line. After executing the second line, it's holding an array. If the same two lines of code were to be written in a statically typed language, the second line would be correct only if an array is somehow convertible to an int.

The point of the post - don't be misled by the var keyword. The variable it declares is still a good old statically typed variable.

Greasemonkeying around with IRCTC

2007-11-10T13:26:00Z

[Update 1/21/2008: Updated the script to handle availability URL change by IRCTC developers. If you've already installed the script, uninstall it (Tools->Greasemonkey->ManageUserScripts, select AJAXAvailability and click Uninstall), and install the updated script from the same location (http://senthil.thecoder.googlepages.com/ajaxavailability.user.js)]

For those of you who have not heard about Greasemonkey, it is a Firefox extension that "allows you to customize the way a webpage displays using small bits of JavaScript.". IRCTC (http://www.irctc.co.in/) is Indian Railways's website for booking tickets. While a huge improvement over standing in queue at railway stations, I would not consider it to be a well designed site - it doesn't stand up to heavy user load, and the interface is not very user friendly. For one, the HTML is absolutely nasty, with multiple <html> tags, multiple elements with the same id, etc.. For what I think is a bandwidth strapped site, the HTML has lots and lots of unnecessary whitespace and commented out HTML and it doesn't even use gzip encoding.

Enough ranting about that - Greasemonkey can't help there. What it can do is help manipulate the UI. My first target was the "Plan My Travel" page. After entering the source and destination stations, date of travel etc. and hitting "Find Trains", the page shows the list of trains that run between the stations on that day. So far, so good. Now, to book tickets on a train, the user selects a train and hits "Book Ticket". However, the user would typically have to check availability of tickets before proceeding to book them. The page makes it frustratingly difficult to do that - checking availability for a train takes two clicks, and worse, the availability information shows up on a new window, forcing the user to switch back and forth between the windows.

I decided to write a Greasemonkey script to show availability information right alongside the list of trains. I did not want to slow down loading of the page though, so I decided to do AJAX style dynamic loading of availability information. Here's how the page looks after enabling the script.

Notice how the new column blends in seamlessly with the rest of the page.

For the technically inclined, the script works by first adding a column to the train details table. It uses a XPath expression to get the list of train numbers from the HTML content and then queries availability information from the server by generating the same query string that a click on the "Show Availability" button generates. The difference is that it does it automatically for all trains in the page and that it uses GM_xmlhttpRequest to do the query asynchronously - which means that the script queries availability for trains (almost) simultaneously.

From here, it's fairly simple - another XPath expression "screen scrapes" the availability string from the HTML content returned by the server and there is some code to update the cell's contents with the string. The script handles failures also - for HTTP failures, it retries the request and for other kind of failures, it shows a "Query Failed" link, which, when clicked, shows the actual error in a messagebox (another XPath expression takes care of scraping the error text).

To install the script, install Greasemonkey first (if you haven't already), navigate to http://senthil.thecoder.googlepages.com/ajaxavailability.user.js 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.

While you're at it, you might also find SortItOut, a script for sorting the availability table (shown above), useful.

Hope you guys find the scripts useful.

Mixing generics and polymorphism

2007-10-14T16:29:00Z

Polymorphism, which attempts to hide differences in implementation, and generics, which attemtps to highlight them by providing exact information about types, don't seem to mix very well. Consider the following fairly common pattern.

        class Base
        {
        }

        class Derived : Base
        {
        }

        abstract class Manipulator
        {
            List<Base> list;

            public Manipulator(List<Base> list)
            {
                this.list = list;
            }
         }

        class BaseManipulator : Manipulator
        {
            public BaseManipulator(List<Base> list)
                : base(list)
            { }
        }

        class DerivedManipulator : Manipulator
        {
            public DerivedManipulator(List<Derived> list)
                : base(list)
            { }
        }

        public static void Main()
        {
            List<Derived> list = new List<Derived>();
            list.Add(new Derived());
            DerivedManipulator d = new DerivedManipulator(list);
        }

The code above will not compile - the compiler complains that List<Derived> cannot be converted to List<Base> in DerivedManipulator's constructor. Which seems kindof strange, given that Derived[] is implicitly convertible to Base[]. But what would happen if implicit conversion occurred with generics?

List<Derived> derivedList = new List<Derived>();
List<Base> baseList = derivedList;
baseList.Add(new Base());
Derived d = derivedList[0]; // BOOM

All hell will break loose. The type safety that generics offer will disappear, obviating the very need for generics.

What can be done then? We could make Manipulator a generic class, taking the type of the List as a generic parameter and make DerivedManipulator derive from Manipulator<Derived>. But then we are only shifting the problem - treating Manipulators polymorphically becomes impossible then.

There seems to be a basic impedance mismatch between polymorphism and generics. Does anyone know of a better way to solve the problem?

GC::PleaseRunWhenProcessRunningOutOfMemory()

2007-07-05T02:01:00Z

I don't think anybody except the guys who coded the GC knows the list of triggers for garbage collection. I believe it's not part of the CLR spec and I guess that was a deliberate decision to allow implementors flexibility in their GC algorithms. That said, there are some situations which leave one confounded as to why the heck the GC doesn't run. Take a look at the following program.

#include "stdafx.h"
#include "windows.h"

using namespace System;

ref class Allocator
{
	LPVOID ptr;
public:
	Allocator()
	{
		ptr = VirtualAlloc(NULL, 1024 * 1024 * 1024, MEM_RESERVE, PAGE_EXECUTE_READWRITE);
		
		if (ptr == NULL)
			Console::WriteLine("Virtual Alloc failed");
		else
			Console::WriteLine("Allocated unmanaged memory");
	}

	!Allocator()
	{
		VirtualFree(ptr, 0, MEM_RELEASE);
	}
};

int main(array<System::String ^> ^args)
{
	array<byte> ^bigArray = gcnew array<byte>(1024 * 1024 * 1024);
	Allocator ^allocator = gcnew Allocator();
}

Allocator reservers 1 GB of virtual memory in its constructor and releases it in its finalizer. The main method instantiates a big managed byte array with 1 GB elements and then instantiates an instance of Allocator.

Without the notion of GC, this is obviously going to fail as Windows limits user address space in a process to around 1.5 GB. With GC, however, I would expect this to run, because bigArray can be GC'ed before executing VirtualAlloc (on Release builds).

Unfortunately it doesn't. The GC doesn't seem to care about unmanaged memory allocations and therefore sits idle when VirtualAlloc runs - this causes VirtualAlloc to fail. Insert a GC::Collect between the two lines in main and it all runs fine.

I ran into a variant of this issue the other day and was left with no option but to force GC explicitly using GC::Collect. I later read about GC::AddMemoryPressure and GC::RemoveMemoryPressure and those work perfect for these scenarios. Just put a AddMemoryPressure call before allocating a big chunk of unmanaged memory (with the corresponding RemoveMemoryPressure) and the GC kicks in.

	Allocator()
	{
                  GC::AddMemoryPressure(1024 * 1024 * 1024);
		ptr = VirtualAlloc(NULL, 1024 * 1024 * 1024, MEM_RESERVE, PAGE_EXECUTE_READWRITE);
		
		if (ptr == NULL)
		   Console::WriteLine("Virtual Alloc failed");
		else
		   Console::WriteLine("Allocated unmanaged memory");
	}

	!Allocator()
	{
		VirtualFree(ptr, 0, MEM_RELEASE);
                  GC::AddRemovePressure(1024 * 1024 * 1024);
	}

It didn't help in my case though, as the unmanaged allocations were occuring in a third party component we had no control over.

The quirky ?:

2007-05-19T18:03:00Z

If there was ever a poll conducted for the most favorite C# operator, I'd guess the conditional operator ?:, also known as the ternary operator, will win hands down. I find it to be one of those tools that make things shorter and clearer at the same time. But how well do you know the operator?

What do you think is wrong with the following piece of code?

    interface IDoer {}

    class ADoer : IDoer { }
    class BDoer : IDoer { }
    class Program
    {
        static void Main(string[] args)
        {
            bool flag = bool.Parse(args[0]);
            IDoer doer = flag ? new ADoer() : new BDoer();
        }
    }

Looks straightforward, doesn't it? Yet, this does not compile; the error being

error CS0173: Type of conditional expression cannot be determined because there is no implicit conversion between 'ADoer' and 'BDoer'

The C# spec says that the two expressions that appear on either side of the : must be one of the following

Both of them should be of the same type
The first one should be convertible to the second
The second one should be convertible to the first

In the above case, ADoer and BDoer are both convertible to IDoer (because they implement IDoer), but because neither of them is implicitly convertible to the other, compilation fails. It doesn't matter to the compiler that the result of the expression is always convertible to IDoer, all it cares about is the deduction of the type of the ternary expression.

I guess this is one of those places where static typing gets in the way of the developer, instead of helping him. You win some, you lose some :)

Playing with IronPython

2007-05-12T06:25:00Z

I've been dabbling with IronPython for the last few days, trying to host it and use it as a scripting engine. I have to say that I'm impressed. The hosting API is incredibly simple to use and Mike Stall's blog served as a handy reference.

One thing I wanted my scripts to do was to access private and internal members of types in the hosting application. I found that the command line python interpreter (ipy.exe) had a -X:PrivateBinding switch to allow access to private and internal members using the <type>_<type>__memberName convention (which seems to be the standard python name mangling for private members).

However, I couldn't find an easy way to do that from the hosting application. It was time to download the source code and figure out how the command line option got translated in code. It turned out to be pretty simple, there is a static class Options, which has properties for most of the command line options. From the hosting application, all you have to do is set the corresponding property before initializing the PythonEngine.

void Initialize()
{
   Options.PrivateBinding = true;
   pythonEngine = new PythonEngine();
}

Add logs to the start and end of methods

2007-05-12T06:23:00Z

MethodLogger is a macro I wrote that adds log statements at the beginning and ending of all methods in the current document in Visual Studio. Unzip the file, load it in Visual Studio using Tools->Macros->Load Macro Project, open the appropriate C# file and then run the LogMethodStartAndEnd macro. It transforms

class SomeClass
{
    public void SomeMethod()
    {
        MessageBox.Show("Doodly doodly Doo");
    }
}

class SomeClass
{
    public void SomeMethod()
    {
        Console.WriteLine("Start of SomeClass.SomeMethod()");
        try
        {
            MessageBox.Show("Doodly doodly Doo");
        }
        finally
        {
            Console.WriteLine("End of SomeClass.SomeMethod()");
        }
    }
}

The code, written in VB .NET (which seems to be the only supported language for writing macros?) uses Visual Studio's automation interface to get the code model for the currently open file. It then walks through all the methods, figures out the starting and ending points of each method and inserts the appropriate statements, with the most significant part being the method signature. It does a very basic check (finds the first non-empty, non comment line and checks if it's the same as the text to be logged) to make sure it doesn't modify methods it has already added logs to - when the user runs the macro twice, for example.

It should be fairly simple to change Console.WriteLine to something else - right clicking on LogMethodStartAndEnd and selecting Edit should take you to the Macro Editor IDE and lines 92, 93 contain the text to be inserted at the start and end of each method.