Wednesday, March 22, 2006 12:58 AM bart

Why I love .NET generics - a little comparison with Java

Discussions of the power of generics a pretty common in some groups. So in order to support my arguments in those discussions, I created a little quick-and-dirty demo of generics in Java and in C#/CLR concerning the boxing/unboxing issues. You probably know that boxing/unboxing of value types causes a serious performance hit. Needless to say that you just want generics to take this problem away, by using something like List<int> as kind of an improved version of int[] (but with variable length etc). Beside of that you also get type-safety and type-checking all the time, something you don't have when using a plain old ArrayList in .NET stuffed with int's all over the place.

 

Non-generic collections

The first difference between C# and Java is the way you can add value types to a non-generic collection. In Java you have to wrap those in a so-called wrapper class (e.g. Integer), whileas .NET has boxing/unboxing on the IL level directly (using box and unbox statements):

//new ArrayList().Add(1);
newobj instance void [mscorlib]System.Collections.ArrayList::.ctor() //instantiate ArrayList
ldc.i4.1 //load 1
box [mscorlib]System.Int32 //box it
callvirt instance int32 [mscorlib]System.Collections.ArrayList::Add(object) //put the object (= wrapper for integer 1) in the list

In Java you'd end up with some bytecode like this (I just took the dump of javap.exe -c because of my lack of manual bytecode generation maturity :-)):

//new ArrayList().add(new Integer(1));
class Box extends java.lang.Object{
Box();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   new     #2; //class java/util/ArrayList
   3:   dup
   4:   invokespecial   #3; //Method java/util/ArrayList."<init>":()V
   7:   new     #4; //class java/lang/Integer
   10:  dup
   11:  iconst_1
   12:  invokespecial   #5; //Method java/lang/Integer."<init>":(I)V
   15:  invokevirtual   #6; //Method java/util/ArrayList.add:(Ljava/lang/Object;)Z
   18:  pop
   19:  return
}

Notice I'm using J2SE 1.5 where ArrayList now is a generic collection which means versioning hell :-). Actually the compiler tells me for every use of a non-generic collection I'm writing unsafe code which is not my mistake but the (old) framework's:

Note: box.java uses unchecked or unsafe operations
Note: Recompile with -Xlint:unchecked for details.

<Intermezzo Title="The Java versioning hell">

I always like to stress .NET was built from ground up to support versioning of applications and portability of "old code" to a newer runtime without modifications thanks to various runtime constructs (side-by-side CLR versions; versioned assemblies; publisher policies and version redirects; etc) but also thanks to the well-thought design of e.g. C#, such as:

  • The lack of checked exceptions: in Java you can declare methods with a throws clause indicating the exceptions the method can throw and therefore which you should catch too. However, such a throws list can be incomplete over the course of time, especially when you are implementing an interface and your specific implementation can throw additional types of exceptions. Either you'd have to create a bunch of Exception subclasses to act as wrappers and deploy those alongside with the interface you've defined or you just fight the checked exception mechanism as a lazy developer by swallowing exceptions all the time using a catch-all block or by declaring every method of yours as throws Exception to get rid of the nasty compiler warnings.
  • Making methods not virtual by default, leading to a performance increase but also aiding in fighting against versioning troubles (assume you create a class B deriving from class A and add a method C to B - which will be virtual by default; then assume the new version of A also has a method called C with a similar signature, whoops - code broken) by requiring stuff such as virtual methods and overrides to be explicit.

I'm sure other examples exist, but let's keep it a short and clean. Not to talk about the "deprecated methods mantra" (although that happens to be an illness of most frameworks today).

</Intermezzo>

Back to our generics investigation in Java. Notice the generated code is actually creating an ArrayList instance without initial knowledge of the type it's going to "host". Later on generic things are done like this:

   15:  invokevirtual   #6; //Method java/util/ArrayList.add:(Ljava/lang/Object;)Z

meaning an object of type java.lang.Object is added to the collection (in this case an instance of Integer, see lines 11-12). In essence, the list doesn't have runtime knowledge of the target type which is the definition of a non-generic list (so, in Java the new generic ArrayList implements non-generic functionality too - as a form of backward compatibility - by setting the target type to the mother of all objects, java.lang.Object).

 

Generic collections

On to generic collections now. Assume the following piece of code in C#:

using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;

class Gen
{
   [DllImport("kernel32.dll")]
   internal static extern int QueryPerformanceCounter(out Int64 lpPerformanceCount);

   [DllImport("kernel32.dll")]
   internal static extern int QueryPerformanceFrequency(out Int64 lpPerformanceCount);

   public static void Main()
   {
      long begin;
      QueryPerformanceCounter(out begin);

      List<int> lst = new List<int>();

      for (int i = 0; i < 1000000; i++)
         lst.Add((i % 2 == 0 ? 1 : -1));

      int sum = 0;
      foreach (int i in lst)
         sum += i;

      long end;
      QueryPerformanceCounter(out end);

      Console.WriteLine(GetSecondsElapsed(begin, end)); //UPDATED 03/24/06 - forgot GetSecondsElapsed call
   }

   static decimal GetSecondsElapsed(long start, long stop)
   {
      long queryFrequency;
      QueryPerformanceFrequency(out queryFrequency);
      decimal result = Convert.ToDecimal(stop - start) / Convert.ToDecimal(queryFrequency);
      return Math.Round(result, 6);
   }
}

The core code is indicated in bold. First of all, notice the generic collections are living in System.Collections.Generic, not fighting with the non-generic brothers and sisters in System.Collections, actually leading to 100% backward compatibility without nasty compiler warnings telling how bad the framework was in the past because of the lack of generics and how you - as an innocent developer - have to be blamed of having written such code ever :P (talking the Java-way). Don't bother about the perf counting stuff in order to get an accurate timing result.

The real fun is over here:

      List<int> lst = new List<int>();

      for (int i = 0; i < 1000000; i++)
         lst.Add((i % 2 == 0 ? 1 : -1));

      int sum = 0;
      foreach (int i in lst)
         sum += i;

First of all, we create a generic list containing int's. Notice no wrappers are needed. Further on, the list is filled with stuff that's retrieved again and used in a sum (avoiding overflow by taking only 1 and -1 values). In IL this results in:

  IL_0009:  newobj     instance void class [mscorlib]System.Collections.Generic.List`1<int32>::.ctor() // List<int> lst = new List<int>();
  IL_000e:  stloc.1            // List<int> lst = new List<int>();
  IL_000f:  ldc.i4.0           // for (int i = 0; i < 1000000; i++)
  IL_0010:  stloc.2            // for (int i = 0; i < 1000000; i++)
  IL_0011:  br.s       IL_0027 // jump to begin of loop
  IL_0013:  ldloc.1            // keep lst object reference on the stack needed for instruction IL_001d
  IL_0014:  ldloc.2            // i % 2 == 0 ? 1 : -1
  IL_0015:  ldc.i4.2           // i % 2 == 0 ? 1 : -1
  IL_0016:  rem                // i % 2 == 0 ? 1 : -1
  IL_0017:  brfalse.s  IL_001c // i % 2 == 0 ? 1 : -1
  IL_0019:  ldc.i4.m1          // i % 2 == 0 ? 1 : -1
  IL_001a:  br.s       IL_001d // short branch
  IL_001c:  ldc.i4.1           // i % 2 == 0 ? 1 : -1
  IL_001d:  callvirt   instance void class [mscorlib]System.Collections.Generic.List`1<int32>::Add(!0) // lst.Add(...);
  IL_0022:  nop                // debugger breakpoint helper instruction
  IL_0023:  ldloc.2            // for (int i = 0; i < 1000000; i++) ~ for (int i = 0; i < 1000000; i = i + 1)
  IL_0024:  ldc.i4.1           // for (int i = 0; i < 1000000; i++) ~ for (int i = 0; i < 1000000; i = i + 1)
  IL_0025:  add                // for (int i = 0; i < 1000000; i++) ~ for (int i = 0; i < 1000000; i = i + 1)
  IL_0026:  stloc.2            // for (int i = 0; i < 1000000; i++) ~ for (int i = 0; i < 1000000; i = i + 1)
  IL_0027:  ldloc.2            // for (int i = 0; i < 1000000; i++)
  IL_0028:  ldc.i4     0xf4240 // for (int i = 0; i < 1000000; i++)
  IL_002d:  clt                // for (int i = 0; i < 1000000; i++)
  IL_002f:  stloc.s    V_5     // for (int i = 0; i < 1000000; i++) // temporary boolean
  IL_0031:  ldloc.s    V_5     // for (int i = 0; i < 1000000; i++) // temporary boolean
  IL_0033:  brtrue.s   IL_0013 // jump to loop body
  IL_0035:  ldc.i4.0           // int sum = 0;
  IL_0036:  stloc.3            // int sum = 0;
  IL_0037:  nop                // debugger breakpoint helper instruction
  IL_0038:  ldloc.1    // foreach (int i in lst) ~ int i = 0; for (List<int>.Enumerator e = lst.GetEnumerator(); e.MoveNext(); i = e.Current)
  IL_0039:  callvirt   instance valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<!0> class [mscorlib]System.Collections.Generic.List`1<int32>::GetEnumerator()
                       // foreach (int i in lst) ~ int i = 0; for (List<int>.Enumerator e = lst.GetEnumerator(); e.MoveNext(); i = e.Current)
  IL_003e:  stloc.s    V_6
                       // foreach (int i in lst) ~ int i = 0; for (List<int>.Enumerator e = lst.GetEnumerator(); e.MoveNext(); i = e.Current)
  .try
  {
    IL_0040:  br.s       IL_004e // begin iterator loop
    IL_0042:  ldloca.s   V_6
                         // foreach (int i in lst) ~ int i = 0; for (List<int>.Enumerator e = lst.GetEnumerator(); e.MoveNext(); i = e.Current)
    IL_0044:  call       instance !0 valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<int32>::get_Current()
                         // foreach (int i in lst) ~ int i = 0; for (List<int>.Enumerator e = lst.GetEnumerator(); e.MoveNext(); i = e.Current)
    IL_0049:  stloc.2    // foreach (int i in lst) ~ int i = 0; for (List<int>.Enumerator e = lst.GetEnumerator(); e.MoveNext(); i = e.Current)
    IL_004a:  ldloc.3    // sum += i; ~ sum = sum + i;
    IL_004b:  ldloc.2    // sum += i; ~ sum = sum + i;
    IL_004c:  add        // sum += i; ~ sum = sum + i;
    IL_004d:  stloc.3    // sum += i; ~ sum = sum + i;
    IL_004e:  ldloca.s   V_6
                         // foreach (int i in lst) ~ int i = 0; for (List<int>.Enumerator e = lst.GetEnumerator(); e.MoveNext(); i = e.Current)
    IL_0050:  call       instance bool valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<int32>::MoveNext()
                         // foreach (int i in lst) ~ int i = 0; for (List<int>.Enumerator e = lst.GetEnumerator(); e.MoveNext(); i = e.Current)
    IL_0055:  stloc.s    V_5 // temporary boolean
    IL_0057:  ldloc.s    V_5 // temporary boolean
    IL_0059:  brtrue.s   IL_0042 // iterator loop - jump to begin
    IL_005b:  leave.s    IL_006c // leave try block
  }  // end .try
  finally
  {
    IL_005d:  ldloca.s   V_6 // stuff to support Enumerator : IDisposable
    IL_005f:  constrained. valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<int32>
    IL_0065:  callvirt   instance void [mscorlib]System.IDisposable::Dispose()
    IL_006a:  nop        // debugger breakpoint helper instruction
    IL_006b:  endfinally // end of SEH block
  }  // end handler
  IL_006c:  nop // debugger breakpoint helper instruction

The result of the execution is 41 ms.

On to the equivalent in Java:

import java.util.*;

class Gen
{
   public static void main(String[] args)
   {
      long begin = System.currentTimeMillis();

      //List<int> lst; //won't compile
      List<Integer> lst = new ArrayList<Integer>();

      for (int i = 0; i < 1000000; i++)
         lst.add((i % 2 == 0 ? 1 : -1));

      int sum = 0;
      for (int i = 0; i < lst.size(); i++)
         sum += lst.get(i);

      long end = System.currentTimeMillis();
      System.out.println(end - begin);
   }
}

Notice you need to use the wrapper class again to instantiate the generic collection, although the add(...) method is intelligent enough to do wrapping itself. Needless to say the lack of enumerator language support leads to less elegant code :P. Investigate the .class file using the javap.exe tool which comes with the J2SE SDK:

class Gen extends java.lang.Object{
Gen();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   invokestatic    #2; //Method java/lang/System.currentTimeMillis:()J
   3:   lstore_1
   4:   new     #3; //class java/util/ArrayList
   7:   dup
   8:   invokespecial   #4; //Method java/util/ArrayList."<init>":()V
   11:  astore_3
   12:  iconst_0
   13:  istore  4
   15:  iload   4
   17:  ldc     #5; //int 1000000
   19:  if_icmpge       50
   22:  aload_3
   23:  iload   4
   25:  iconst_2
   26:  irem
   27:  ifne    34
   30:  iconst_1
   31:  goto    35
   34:  iconst_m1
   35:  invokestatic    #6; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
   38:  invokeinterface #7,  2; //InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
   43:  pop
   44:  iinc    4, 1
   47:  goto    15

   50:  iconst_0
   51:  istore  4
   53:  iconst_0
   54:  istore  5
   56:  iload   5
   58:  aload_3
   59:  invokeinterface #8,  1; //InterfaceMethod java/util/List.size:()I
   64:  if_icmpge       92
   67:  iload   4
   69:  aload_3
   70:  iload   5
   72:  invokeinterface #9,  2; //InterfaceMethod java/util/List.get:(I)Ljava/lang/Object;
   77:  checkcast       #10; //class java/lang/Integer
   80:  invokevirtual   #11; //Method java/lang/Integer.intValue:()I
   83:  iadd
   84:  istore  4
   86:  iinc    5, 1
   89:  goto    56

   92:  invokestatic    #2; //Method java/lang/System.currentTimeMillis:()J
   95:  lstore  5
   97:  getstatic       #12; //Field java/lang/System.out:Ljava/io/PrintStream;
   100: lload   5
   102: lload_1
   103: lsub
   104: invokevirtual   #13; //Method java/io/PrintStream.println:(J)V
   107: return
}

Both blocks have been indicated in colors. Notice the boxing stuff:

   35:  invokestatic    #6; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;

and the unboxing stuff:

   72:  invokeinterface #9,  2; //InterfaceMethod java/util/List.get:(I)Ljava/lang/Object;
   77:  checkcast       #10; //class java/lang/Integer
   80:  invokevirtual   #11; //Method java/lang/Integer.intValue:()I

which is introduced automatically. And finally as you can see the generic parameter is just java.lang.Object:

   38:  invokeinterface #7,  2; //InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z

   72:  invokeinterface #9,  2; //InterfaceMethod java/util/List.get:(I)Ljava/lang/Object;

Execution times tell very much about this approach: 301 ms, a factor 7.3 (worse) compared to the CLR-equivalent. (UPDATED 03/24/06 - Modified the orginal - wrong - result based on the GetSecondsElapsed code.)

 

Conclusion

Generics in .NET are not an artificial construct like in Java and really lead to the generation of new types at runtime (or at ngen-time to be complete) significantly increasing performance especially when working with value types that don't require boxing/unboxing anymore. Using this basic test you come to the conclusion that .NET is 7.3 times faster than Java. Stay tuned for more stuff on generics somewhere in the near future.

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

Filed under: ,

Comments

# A few comments from 'The Other Side'

Thursday, March 23, 2006 8:14 AM by Koen Serry

a few comments from 'The Other Side'

I've been reading your blog since I'm doing occasionally stuff in .net, but java is where my heart is. But this entry gave me the creeps so I couldn't resist commenting on it.

If you're using JDK5 (and it seems you did) you may have noticed that new ArrayList().add(1) actually works. So boxing and unboxing has made it into Java too (Although I'm not sure this is a good thing).
Second the collections framework in java is imho far better than .net, first of all there is no common interface for (non-)generic collections in .Net. So System.Collection.Arraylist doesn't implement System.Collection.Collection or whatever, like they do in java. This would actually allow components to be written that take collections as an interface, regardless of how they're implemented. Or to have open source alternatives, that could turn out to be faster/lighter.
On the backwards compatibility, while it's true SUN could have opted for putting them in a seperate package, they didn't. And quite frankly It doesn't even bother me that the compiler warns me about it, since I can either disable them or use generics. What this has to do with versioning hell is a big question mark for me. Java hasn't suffered from versioning hell like .net does. We do however have our own issues like ClassNotFoundExceptions, ClassLoaders and stuff.
Although things have improved since the 'COM' days, I don't know about something like class loaders in .net that allows usage of separate versions of the same package in the same program. And then we didn't discuss about the backwards compatibility between .Net2.0 and 1.(0|1) which is if you ask me questionable.
As far as startup time is concerned, well the statement that .net is 2,2 times faster than java based on a simple program like that, where the JVM has the disadvantage of not being partially loaded into memory already, I'll leave that to you.


# Performance measurement in .NET 2.0 - the birth of Stopwatch

Friday, March 24, 2006 5:53 PM by B# .NET Blog

In my post about generics a couple of days ago (see http://community.bartdesmet.net/blogs/bart/archive/2006/03/22/3831.aspx,...

# re: Why I love .NET generics - a little comparison with Java

Wednesday, April 12, 2006 8:53 PM by bart

A few comments on the "The Other Side" comment posted by Koen Serry earlier.

First of all, thanks for reading my blog and providing comments. However, a few reactions.

1. I'm a little in doubt about how far boxing goes in the latest Java version. For instance, the following works in C#:

class Boxing
{
 public static void Main()
 {
   int i = 123;
   object o = i;
   int j = (int) i;
 }
}

but the following doesn't in Java:

class Boxing
{
 public static void main(String[] args)
 {
   int i = 123;
   Object o = i;
   int j = (int) o;
 }
}

As the matter in fact, both worlds have a very different way of boxing. In the CLI, we have value types that can be boxed to a reference type for use in collections etc. The CLI contains a definition for both box and unbox and effectively, the C# code above uses box to do "object o = i;". In Java, the compiler tricks the same behavior by calling Integer.valueOf (see javap.exe output for the code above). This is just taking the "boxing logic" out of the hands of the developer and bringing to a smarter compiler. But boxing and unboxing do not make their way to the Java runtime.

2. For what the collections API is concerned, I agree the API in .NET is lighter than the one in Java, but I haven't come across a point where I needed additional functionality. Maybe "small is beautiful"? The question is how much functionality you can really interface across all kinds of collections. It doesn't work out very well for Dictionary <-> List for example. What do contains(Object) mean for a Map (containsKey or containsValue)? In .NET, the ICollection interface is stripped down to the bare minimum and it's up to interfaces such as IList or IDictionary to define real functionality. And for me, creating an "über interface" to all of those collections would be overkill and look somewhat cumbersome. Beside the fact that collections "contain" something, the way of adding items and retrieving those is simply different (List <-> Dictionary <-> Queue <-> Stack <-> ...). It might just be a different way of reasoning where the Java folks want to do as much as they can through interfaces (why does one need "managed function pointers" aka delegates when you can have Runnable-stuff or *Listener stuff to do it in a much more cumbersome way?). To put it another way, when designing a piece of software I'm deciding for instance whether I need an index-based collection or not. If I want to write generic code, this brings me (in this case) to IList. And if I want to be able to iterate over a collection I end up with IEnumerable. In the end, I think it's a matter of taste.

3. What the backward compatibility is concerned, the short answer is that .NET runtimes run side-by-side thanks to the startup-shim. Further on, an assembly is bound to a runtime by means of the referenced version of mscorlib. If you configure your application using a binding policy (which comes down to making a change in the .config file for the app) you can redirect those bindings to newer versions of dependent assemblies. However, such a redirect is not recommended. The idea is - again - straightforward. Either you choose to use the old version of the runtime (mscoree.dll will redirect the _CorExeMain request to the right instance of mscorwks.dll for you) and keep the existing binaries, or you want to migrate the the new version of the runtime and recompile stuff for the new runtime to make sure nothing is broken. In the future, we'll likely see a clean separation between CLR versions, BCL versions and VS tools versions.

4. On the versioning hell stuff, Java doesn't have a notion of application versions in the core of the runtime. In .NET, assembly names are made up of an assembly name, a culture, a version and a public key token (depending on whether the assemblies are strong named or not). .NET is completely built around the idea of versionable assemblies, up to the level of the GAC. So, if you don't have versions you might say you don't have versioning troubles as well. But when looking at things such as "checked exceptions" in Java, one can't impossibly deny the sword of Damocles you're creating over there. Some interesting articles on this subject have been written by Bruce Eckel and Anders Heijlsberg. Check those out!

5. I'm not talking about "startup time", I'm talking about running time of an application. JIT compilation will kick in only once for the called methods (e.g. the methods on List). As the matter in fact, I changed the original post because there was a little bug in my perf counting code. My renewed statement is that .NET is 7.3 times faster than Java on this piece of code. Also notice I'm not calculating the "outer run time" of the app, which I could have done using perf measurement of a process' running time (using Process.Start or so). I'm calculating the running time inside the application to rule out any delays caused by loading the runtime itself. So, I'm just measuring the time to add 1,000,000 integers to the list and summing those up.

I'm sorry to make you creep, but this is just my 5cts. The richness of the CLI is the wonderful world I'm living in and I could argue about pros and cons for many many hours. But it's up to the readers to make their decision.

-Bart