February 2007 - Posts

Last week, I introduced C# 2.0 to a few academic people who had prior exposure to C, C++ and Java. Does language matter is an often heard question. Well, in the world of .NET, the importance of language choice has somewhat blurred but richness of languages still is a great decision factor, certainly for general-purpose languages.

Typical samples of developer convenience in the world of C# include the foreach loop, nullable types, generics, etc. One more dark feature is the principle of iterators and lazyness however; the typical example of an even number generator and the explanation of a finate state automaton isn't the best approach to introduce this feature...

So, I came up with another (more academic) sample: the Pascal triangle. For those who're not familiar with this concept, it looks as follows:

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

Basically, each number inside the triangle (i.e. without the borders that always contain 1) is the sum of the two numbers above it. And yes, it has its use (beside of a geeky wallpaper layout for math freaks): every row indicates the coefficients of the mixed products of a and b when calculating (a+b)^n (Binomium of Newton).

So, here's the code:

1 using System; 2 using System.Collections.Generic; 3 4 class Pascal 5 { 6 static void Main() 7 { 8 foreach (uint[] row in GetPascalTriangle()) 9 { 10 Print(row); 11 Console.ReadKey(); 12 } 13 } 14 15 static void Print(uint[] row) 16 { 17 foreach (uint e in row) 18 Console.Write("{0}\t", e); 19 Console.WriteLine(); 20 } 21 22 static IEnumerable<uint[]> GetPascalTriangle() 23 { 24 uint[] row = new uint[1] { 1 }; 25 26 for(int n = 2; ; n++) 27 { 28 yield return row; 29 30 uint[] nrow = new uint[n]; 31 Array.Copy(row, nrow, n-1); 32 for (int i = 1; i < n; i++) 33 nrow[i] += row[i-1]; 34 row = nrow; 35 } 36 } 37 }

The code above produces something like this:

If you want to know how iterators work, check out my former post on C# 2.0 Iterators.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

This quiz was derived from an old piece of code I reviewed for a student's project somewhere in the past. Actually, I was doing some perf-related work today, so I thought it might be useful to have a little quiz around this. Below is the code (reduced in size) of a matrix implementation in C#. Using operator overloads, it supports various operations of which I only kept the multiplication operation (implemented in a very naive way):

using System; using System.Diagnostics; class Matrix { private double[,] m; public Matrix(int dim0, int dim1) { m = new double[dim0,dim1]; } public int Height { get { return m.GetLength(0); } } public int Width { get { return m.GetLength(1); } } public double this[int x, int y] { get { return m[x,y]; } set { m[x,y] = value; } } public static Matrix operator*(Matrix m1, Matrix m2) { if (m1.Width != m2.Height) throw new InvalidOperationException("Matrices should have compatible dimensions for multiplication."); Matrix m = new Matrix(m1.Height, m2.Width); for(int i = 0; i < m.Height; i++) { for(int j = 0; j < m.Width; j++) { m[i,j] = 0; for (int k = 0; k < m1.Width; k++) m[i,j] += m1[i,k] * m2[k,j]; } } return m; } } class Program { static void Main() { Random rand = new Random(); Matrix m1 = new Matrix(20,30); for (int i = 0; i < m1.Height; i++) for (int j = 0; j < m1.Width; j++) m1[i,j] = rand.Next(-100,100); Matrix m2 = new Matrix(30,40); for (int i = 0; i < m2.Height; i++) for (int j = 0; j < m2.Width; j++) m2[i,j] = rand.Next(-100,100); Matrix r = null; Stopwatch sw = new Stopwatch(); sw.Start(); for (int k = 0; k < 10000; k++) r = m1 * m2; sw.Stop(); Console.WriteLine(sw.Elapsed); } }

Question:

  1. Measure the execution time of the code fragment above on your machine (compile with debugging disabled and optimization enabled, i.e. using csc /o).
  2. Perform optimizations to the code (warning: the code should - duh - still produce the same multiplication result r). You can touch everything except for the Program::Main method.
  3. Go back to 1.

Feel free to break the loop above at any time if you're satisfied with the result. What's the speed-up factor you can realize? (Tip: You even might want to change something in the process steps 1-3 outlined above to realize a performance boost...)  A follow-up post to this quiz question will follow later. Enjoy!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

A little different quiz approach today; starting from IL :-). The question is pretty simple: when does the C# compiler emit a call instruction instead of a callvirt instruction?

A little sample to illustrate the non-trivial character of this question:

1 class Call 2 { 3 static void Main() 4 { 5 C c = new C(); 6 c.Do(); 7 c.DoIt(); 8 } 9 } 10 11 class C 12 { 13 public void Do() {} 14 public virtual void DoIt() {} 15 }

This piece of code will contain two callvirt instructions: one for c.Do() (line 6) and one for c.DoIt() (line 7). A side-question you might ask yourself is why the compiler doesn't emit a call instruction for the non-virtual method call on line 6. Stay tuned for the answer (or find it out yourself :-)).

Have fun!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Last week, I was doing an introduction session on C# for students with a Java background. There were quite some interesting discussions around the why and how of properties, indexers, operator overloads, events, delegates, attributes, etc compared to "equivalents" in Java. I won't repeat this discussion over here again but would like to pay a bit attention to another difference: virtual versus non-virtual methods. Today, I read the following question on a discussion list for .NET:

Anybody know why methods aren't virtual by default in .NET?
It seems like a really bad default to have all methods non-virtual.

Basically, in Java methods are virtual by default, unless you declare them as "final". In C#, it's the other way around: methods are non-virtual by default, unless you declare them as "virtual". The reasons why are pointed out by Anders Hejlsberg on Artima.

In this post, I just wanted to put the performance aspect in perspective by means of a little demo app:

1 using System; 2 using System.Diagnostics; 3 4 class Virt 5 { 6 public virtual void Do() {} 7 public void DoIt() {} 8 9 static void Main() 10 { 11 Virt v = new Virt(); 12 13 Stopwatch sw = new Stopwatch(); 14 sw.Start(); 15 for (int i = 0; i < 1000000000; i++) 16 v.DoIt(); 17 sw.Stop(); 18 Console.WriteLine(sw.Elapsed); 19 20 sw.Reset(); 21 sw.Start(); 22 for (int i = 0; i < 1000000000; i++) 23 v.Do(); 24 sw.Stop(); 25 Console.WriteLine(sw.Elapsed); 26 } 27 }

Make a little estimate of the figures (relative to each other) printed out on lines 18 and 25. You might be a little surprised... (Tip: do compile the code fragments once with the /o csc.exe flag too and observe the difference)

For ILDASM freaks, here are the IL equivalents of both methods:

.method public hidebysig newslot virtual instance void Do() cil managed { // Code size 2 (0x2) .maxstack 8 IL_0000: nop IL_0001: ret } // end of method Virt::Do .method public hidebysig instance void DoIt() cil managed { // Code size 2 (0x2) .maxstack 8 IL_0000: nop IL_0001: ret } // end of method Virt::DoIt

The words public, instance, void, virtual, cil and managed should be self-explanatory.

The hidebysig thing means "hide by signature" (in contrast to "hide by name" semantics which you find in languages like C++). Hidebysig isn't used by the runtime itself, but is used by language compilers and tools to see what has to be hidden (in this case, Do and DoIt will hide methods lower in the class hierarchy which have the same signature, i.d. void <name>() - in this specific case there's nothing to hide because the base class is just System.Object).

On the virtual method Do there's another keyword that might be a bit non-intuitive at first sight, newslot. This keyword is used to indicate that a new virtual method is introduced, which adds a new entry to the vtable. Assume you're overriding the method in some subclass, then there won't be a newslot declaration.

Question: Predict the IL method signatures of all Do methods below:

class Virt2 : Virt { public override void Do() {} } class Virt3 : Virt { public new void Do() {} } class Virt4 : Virt { public new virtual void Do() {} } class Virt5 : Virt { public sealed override void Do() {} }

Another question: On the caller's side (i.e. Virt::Main), which types of calls will be emitted (call or callvirt) for C# code lines 16 and 23? And why? (Note: you might be amazed/confused if you see it ;-)).

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

A question of one of my blog readers: what about multiple workflows calling into the same Local Communication Service concerning possible threading and synchronization issues.

Consider the following scenario. Assume you have one WorkflowRuntime in your host application, together with one registered Local Communication Service defined by the following interface contract:

[ExternalDataExchange] interface IBar { void Bar(int i); void Foo(int i); }

Assume Workflow1 relies on the Bar method while Workflow2 relies on the Foo method, with both workflow definitions like the following:

The whileActivity1 has a condition that evaluatues true at all times (read: endless loop). The sequenceActivity1 acts as the container for a set of activities in the body of the loop, and wraps the callExternalMethodActivity1 (that calls the Bar and Foo method for Workflow1 and Workflow2 respectively) as well as the delayActivity1 (that has a 1 second and a 3 second delay for Workflow1 and Workflow2 respectively).

Next, assume the following host application code (note: there's a little issue in the code below since I'm running more than one workflow and the waitHandle would be set upon completion of one of both, causing the app to terminate - since both workflows won't ever terminate due to the endless loop, this doesn't cause further problems in this particular demo):

1 class Program 2 { 3 static void Main(string[] args) 4 { 5 using(WorkflowRuntime workflowRuntime = new WorkflowRuntime()) 6 { 7 AutoResetEvent waitHandle = new AutoResetEvent(false); 8 workflowRuntime.WorkflowCompleted += delegate(object sender, WorkflowCompletedEventArgs e) {waitHandle.Set();}; 9 workflowRuntime.WorkflowTerminated += delegate(object sender, WorkflowTerminatedEventArgs e) 10 { 11 Console.WriteLine(e.Exception.Message); 12 waitHandle.Set(); 13 }; 14 15 ExternalDataExchangeService edx = new ExternalDataExchangeService(); 16 workflowRuntime.AddService(edx); 17 edx.AddService(new MyService()); 18 19 WorkflowInstance instance1 = workflowRuntime.CreateWorkflow(typeof(TestConcurrency.Workflow1)); 20 instance1.Start(); 21 22 WorkflowInstance instance2 = workflowRuntime.CreateWorkflow(typeof(TestConcurrency.Workflow2)); 23 instance2.Start(); 24 25 waitHandle.WaitOne(); 26 } 27 } 28 }

where MyService implements the IBar interface:

class MyService : IBar { public void Bar(int n) { for (int i = 0; i < 100; i++) { Thread.Sleep(10); Console.Write('#'); } } public void Foo(int n) { for (int i = 0; i < 100; i++) { Thread.Sleep(10); Console.Write('@'); } } }

Question: Predict the console output of the workflow execution above. Tip: what about adding [MethodImpl(MethodImplOptions.Synchronized)] to the method declarations? What about inspecting the ManagedThreadId property of the Thread.CurrentThread in both methods?

Happy threading!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

One of the new features in .NET Framework 3.5 is the new namespace System.Numeric that lives in System.Core.dll. It's a pretty lonesome place for a class to be defined in: System.Numeric's only citizen at this very moment is BigInteger. But how happy it is to be there :-) A little tale...

Everyone knows the mathematical ! operator for factorials. Recursively it is defined as a unary operator on natural numbers:

0! = 1
n! = n * (n-1)! for n > 0

which can be implemented using a simple loop:

int res = 1; for (int i = 2; i <= n; i++) res *= i; return res;

The bottleneck? Take a look at the type of res, which is int (aka System.Int32). Further than 12! you won't get without overflowing. Replacing the type by long instead of int won't help us much further: after calculating 20! we're out of luck (question: would uint or ulong bring us any further?). Luckily BigInteger is here to help us out. A sample:

1 using System; 2 using System.Numeric; 3 4 namespace ConsoleApplication1 5 { 6 class Program 7 { 8 static void Main(string[] args) 9 { 10 FactorialWithInt32(); 11 FactorialWithInt64(); 12 FactorialWithBigInteger(); 13 } 14 15 static void FactorialWithInt32() 16 { 17 int res = 1; 18 19 try 20 { 21 checked 22 { 23 for (int n = 2; ; n++) 24 Console.WriteLine("{0}! = {1}", n, res *= n); 25 } 26 } 27 catch { } 28 } 29 30 static void FactorialWithInt64() 31 { 32 long res = 1; 33 34 try 35 { 36 checked 37 { 38 for (int n = 2; ; n++) 39 Console.WriteLine("{0}! = {1}", n, res *= n); 40 } 41 } 42 catch { } 43 } 44 45 static void FactorialWithBigInteger() 46 { 47 BigInteger res = 1; 48 49 try 50 { 51 checked 52 { 53 for (int n = 2; ; n++) 54 Console.WriteLine("{0}! = {1}", n, res *= n); 55 } 56 } 57 catch { } 58 } 59 } 60 }

The checked keyword performs overflowing checks and is needless in the FactorialWithBigInteger sample; BigInteger won't run out of juice pretty soon (basically, a BigInteger is an abstraction of an array of integer values together with a sign, with overloads for typical integer operators). So, if you ever need to deal with large (I mean really large!) integers, BigInteger might be something for you. However, keep in mind that BigIntegers are slower in use (after all, it has to deal with much more data than a simple add operation) so unless you really need to keep a large value, stay away from it.

A few notes

What do I need to run the sample? Answer: download the January 07 CTP of Orcas

Where is System.Core.dll? Answer: take a look at %windir%\Microsoft.NET\Framework\v3.5.11209

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Probably you did know already that Windows XP SP2, Windows Server 2003 and Windows Vista have a component called http.sys to handle HTTP requests.

Basically, http.sys is a kernel-mode listener that has intrinsic knowledge of HTTP. Different parties can register with this listener to have requests forwarded to them. Typical examples nowadays include IIS 6 and SQL Server 2005 (for Web Service functionality). The result? An increase throughput (kernel-mode caching), a more reliable architecture and a decreased footprint on the system (no need to install IIS to do - for example - SQLXML kind of stuff since SQL Server can hook directly into http.sys).

Enough theory. Did you know your managed code application can take advantage of all this goodness right away? Discover System.Net.HttpListener right away. This sample shows the basic concepts:

1 using System; 2 using System.Collections; 3 using System.Collections.Specialized; 4 using System.IO; 5 using System.Net; 6 using System.Reflection; 7 using System.Text; 8 using System.Threading; 9 10 class Program 11 { 12 static void Main() 13 { 14 HttpListener listener = new HttpListener(); 15 listener.Prefixes.Add("http://*:8080/"); 16 listener.Start(); 17 Console.WriteLine("Listening..."); 18 for(;;) 19 { 20 HttpListenerContext ctx = listener.GetContext(); 21 new Thread(new Worker(ctx).ProcessRequest).Start(); 22 } 23 } 24 25 class Worker 26 { 27 private HttpListenerContext context; 28 29 public Worker(HttpListenerContext context) 30 { 31 this.context = context; 32 } 33 34 public void ProcessRequest() 35 { 36 string msg = context.Request.HttpMethod + " " + context.Request.Url; 37 Console.WriteLine(msg); 38 39 StringBuilder sb = new StringBuilder(); 40 sb.Append("<html><body><h1>" + msg + "</h1>"); 41 DumpRequest(context.Request, sb); 42 sb.Append("</body></html>"); 43 44 byte[] b = Encoding.UTF8.GetBytes(sb.ToString()); 45 context.Response.ContentLength64 = b.Length; 46 context.Response.OutputStream.Write(b, 0, b.Length); 47 context.Response.OutputStream.Close(); 48 } 49 50 private void DumpRequest(HttpListenerRequest request, StringBuilder sb) 51 { 52 DumpObject(request, sb); 53 } 54 55 private void DumpObject(object o, StringBuilder sb) 56 { 57 DumpObject(o, sb, true); 58 } 59 60 private void DumpObject(object o, StringBuilder sb, bool ulli) 61 { 62 if (ulli) 63 sb.Append("<ul>"); 64 65 if (o is string || o is int || o is long || o is double) 66 { 67 if(ulli) 68 sb.Append("<li>"); 69 70 sb.Append(o.ToString()); 71 72 if(ulli) 73 sb.Append("</li>"); 74 } 75 else 76 { 77 Type t = o.GetType(); 78 foreach (PropertyInfo p in t.GetProperties(BindingFlags.Public | BindingFlags.Instance)) 79 { 80 sb.Append("<li><b>" + p.Name + ":</b> "); 81 object val = null; 82 83 try 84 { 85 val = p.GetValue(o, null); 86 } 87 catch {} 88 89 if (val is string || val is int || v