List<T>.ForEach vs foreach(…)


A thread came up yesterday on the C# newsgroup about when to use the “normal” foreach
and when to use List<T>.ForEach (assuming, of course, that one is dealing with a
List<T> in the first place). Obviously there are readability issues, but we ended up focusing
on performance. (Isn’t that telling in its own right? How often is the iteration part rather than
the body going to dominate and be a significant bottleneck? Anyway, I digress.)



So, I wrote a small benchmark, and Patrick asked me to blog about it. I’ve refactored the test I posted on the newsgroup and added a couple more tests as suggested by Willy Denoyette. The source code is a little bit unwieldy (and frankly tedious) to include in this blog post – download it if you’re interested.



The test basically creates a list of strings, each being “x”. Each test case iterates through the
list a fixed number of times, keeping a running total of the lengths of strings it sees. The result
is checked and the time taken is reported. This is what the individual tests do:


  • LanguageForEach just uses foreach (string x in list) in the obvious way.
  • NewDelegateEachTime uses an anonymous method as the parameter to List.ForEach<T>, where that method captures a different variable each “outer” iteration. That means a new delegate has to be created each time.
  • CachedDelegate creates a single delegate and uses that for all calls to List<T>.ForEach.
  • LanguageForEachWithCopy1 copies the list to an array each “outer” iteration, and then uses foreach over that array.
  • LanguageForEachWithCopy2 copies the list to an array once at the start of the test, and then uses foreach over that array.


Here are the results, with a few different test cases (all doing the same amount of work overall). I shall attempt to tabulate them a bit better when I get some time :)


Test parameters: Size=10000000; Iterations=100
Test 00:00:11.8251914: LanguageForEach
Test 00:00:05.3463387: NewDelegateEachTime
Test 00:00:05.3238162: CachedDelegate
Test 00:00:22.1342570: LanguageForEachWithCopy1
Test 00:00:03.7493164: LanguageForEachWithCopy2



Test parameters: Size=1000000; Iterations=1000
Test 00:00:11.8163135: LanguageForEach
Test 00:00:05.3392333: NewDelegateEachTime
Test 00:00:05.3334596: CachedDelegate
Test 00:00:26.9471681: LanguageForEachWithCopy1
Test 00:00:03.5251209: LanguageForEachWithCopy2



Test parameters: Size=100000; Iterations=10000
Test 00:00:11.6576344: LanguageForEach
Test 00:00:05.2225531: NewDelegateEachTime
Test 00:00:05.2066938: CachedDelegate
Test 00:00:16.2563401: LanguageForEachWithCopy1
Test 00:00:03.0949064: LanguageForEachWithCopy2



Test parameters: Size=100; Iterations=10000000
Test 00:00:12.2547105: LanguageForEach
Test 00:00:04.9791093: NewDelegateEachTime
Test 00:00:04.6191521: CachedDelegate
Test 00:00:06.0731525: LanguageForEachWithCopy1
Test 00:00:02.8182444: LanguageForEachWithCopy2

The LanguageForEachWithCopy1 results surprised me, as I’d really expected the performance to go up as the number of iterations went up. It seems it’s cheaper to copy a short list many times than a long list a few times…

Singletons and inheritance

For a long time, when people have asked about having inheritance and singletons, I’ve stated flatly that a singleton can’t be derived from. It stops being a singleton at that point. Even if the class is internal and you can prove that no other classes in the assembly do derive from the singleton and break the pattern’s effect, it’s still not a genuine singleton.


It was only when I was thinking about one of the comments about my enhanced enums proposal that I realised there’s an alternative approach. You can derive from a singleton as nested types of the Singleton itself and still keep the private constructor. That means that the singleton nature is still contained within the body of the text which declares the singleton class, even though that text actually declares more classes. Indeed, the singleton itself can even be abstract. Here’s an example:


using System;

public abstract class DataProvider
{
    static DataProvider instance = CreateDataProvider();
    
    public static DataProvider Instance
    {
        get { return instance; }
    }
    
    // Note that nested classes can call private members
    private DataProvider() {}

    public abstract void Connect();
    
    static DataProvider CreateDataProvider()
    {
        // Use Oracle on a Sunday, SQL Server otherwise
        if (DateTime.Now.DayOfWeek==DayOfWeek.Sunday)
        {
            return new OracleProvider();
        }
        else
        {
            return new SqlServerProvider();
        }
    }
    
    // Note that there’s no need to make the constructors
    // for the nested types non-public, as the classes
    // themselves are private to DataProvider.
    
    class OracleProvider : DataProvider
    {
        public override void Connect()
        {
            Console.WriteLine (“Connecting to Oracle”);
        }
    }

    class SqlServerProvider : DataProvider
    {
        public override void Connect()
        {
            Console.WriteLine (“Connecting to SQL Server”);
        }
    }
}

I’m not suggesting you should actually use a singleton for a data provider like this – it just seemed like a simple example to demonstrate the point.


It is easy to validate that the singleton only allows one instance of DataProvider to ever be constructed. (This version isn’t fully lazy, but that could be added if desired.)


It looks like I’ll have to revise my statement about inheritance from now on…

ICloneable? Not quite…

I don’t usually post personal news on my blog, but this is fairly major. Some of you may know that my wife, Holly, is pregnant. What you won’t know – and what we didn’t know until today – was that we’re having twins. Eek! A lovely surprise, if somewhat scary. For those of you who like piccies, the scans are on my web site…


Now if you’ll excuse me, I think I’ll go and lie down. And to think I was going to write up C# 2.0 features tonight…


Nice doc comment idea

I’ve just been reading the transcript of a whiteboard session with Anders Hejlsberg and one of the questions is really, really good:


Question: My problem is I’ve got these XML doc comments that are duplicated. I just strip off one. I guess it would be a neat language feature to be able to somehow indicate this is my primary- my big method, right? With all the parameters. Then the other ones are just going to borrow that XML doc comment.


Hejlsberg: Yes, okay. Now that I think is- that’s not a bad idea. That yes, they should be able to share the documentation. I can sympathize with that.


That’s not just “not a bad idea”. That’s a fantastic idea. When I was writing the BitConverter and BinaryReader etc equivalents in my miscellaneous utility library the doc comments for the overloads took significantly longer to write than the actual code. (Most of the code was just each overload calling a “master” routine.) Now, sometimes that comment won’t be exactly the same for each overload; sometimes there’ll effectively be placeholders: “Converts the specified ${type} value into ${n} bytes” or whatever. I don’t know exactly how this could be done elegantly (and I’m not actually suggesting the ${token} syntax!), but it’s something that should be strongly considered for a later version of C#. It could make life a lot simpler in some cases.

Enhanced enums in C#


This will be an evolving post, hopefully. (If no-one comments on it, it probably
won’t change unless I come up with better ideas myself.) Since working on a Java
project last year, I’ve been increasingly fed up with C#’s enums. They’re really
not very object oriented: they’re not type-safe (you can cast from one enum to
another via a cast to their common underlying type), they don’t allow any
behaviour to be specified, etc. They’re just named constant integral values.
Until I played with Java 1.5’s enum support, that wouldn’t have struck me as being
a problem, but (at least in some cases) enums can give you so much more. This post
is a feature proposal for C# 4.0. (I suspect the lid for this kind of thing is closed
on 3.0.)


What’s the basic idea?



Instead of being a fixed set of integral values, imagine if enums were a fixed set of
objects. They could have behaviour (and state of sorts), just like other objects – the
only difference would be that there’d only ever be one instance for each value. When
I say they could have “state of sorts” I mean that two values of an enum could differ
in just what they represented. For instance, imagine an enumeration of coins – I’ll use
US coins for convenience for most readers. Each value in the enum would have a name
(Cent, Nickel, Dime, Quarter, Dollar) and a monetary value in cents (1, 5, 10, 25, 100
respectively). Each might have a colour property too, or the metal they’re made of. That’s
the kind of state I mean. In fact, there’s nothing in the proposal below to say that the
state within an enum has to stay the same. I’d recommend that it did stay the same,
but maybe someone’s got an interesting use case where mutable enums would be useful.
(Actually, it’s not terribly hard to think of an example where the underlying state mutates
even if it doesn’t appear to from a public property point of view – some properties could
be lazily initialised if they might take time to compute.)



As well as properties, the enum type could have methods, just as other types do. For instance,
an enumeration of available encryption types may have methods to encrypt data. (I’m giving
fairly general examples here – in my experience, the actual enums you might use tend to be
very domain-specific, and as such don’t make good examples. I’m also trying to steer well
clear of risking giving away any intellectual property owned by my employer.)



Now, consider the possibilities available when you bring polymorphism into the picture. Not
every implementation of a method has to be the same. Some enum values may be instances of
a type derived from the top-most one. This would be limited at compile-time to make enums
fixed – you couldn’t derive from an enum type in the normal way, so you’d
always know that if you had a reference to an instance of the enum type, you’d got one of
the values specified by the enum.


What’s the syntax?



I propose a syntax which for the simplest of cases looks very much like normal enumerations,
just with class enum instead of enum:


public class enum Example
{
    FirstValue,
    SecondValue;
}


Note the semi-colon at the end of the list of values. This could perhaps be optional,
but when using the power of “class enums” (as I’ll call them for now) in a non-trivial way,
you’d need them anyway to tell the compiler you’d reached the end of the list of values,
and other type members were on the way. The next step is to introduce a constructor and
a property:


public class enum Coins
{
    Cent(1),
    Nickel(5),
    Dime(10),
    Quarter(25),
    Dollar(100);
    
    // Instance variable representing the monetary value
    readonly int valueInCents;
    
    // Constructor - all enum constructors are private
    // or protected
    Coins(int valueInCents)
    {
        this.valueInCents = valueInCents;
    }
    
    public int ValueInCents
    {
        get { return valueInCents; }
    }
}


Now, there would actually be some significant compiler magic going on at this point. Each of
the generated constructor calls would actually have an extra parameter – the name of the value. That
parameter would be present in every generated constructor, and if no constructors were declared, a protected
constructor would be generated which took just that parameter. Each constructor would implicitly
call the base constructor which would stash the name away and make it available through a Name
property (and no doubt through calls to ToString() too). What’s the base class in this case?
System.ClassEnum or some such. This could be an ordinary type as far as the CLR is concerned,
although language compilers would be as well to prevent direct derivation from it. This leaves room for
some compilers to allow types which aren’t really enums to derive from it, but does have the advantage
of not requiring a CLR change. Whenever you use someone else’s code you’re always taking a certain amount on
trust anyway, so arguably it’s not an awful risk. More about the services of System.ClassEnum
later…



The next piece of functionality is to have some members with overridden behaviour. The canonical example
of this is simple arithmetic operations – addition, subtraction, division and multiplication. The enumeration
contains a value for each operation, and has an Eval method to perform the operation. Here’s
what it would look like in C#:


public class enum ArithmeticOperation
{
    Addition
    {
        public override int Eval(int x, int y)
        {
            return x+y;
        }
    },
    
    Subtraction
    {
        public override int Eval(int x, int y)
        {
            return x-y;
        }
    },
    
    Multiplication
    {
        public override int Eval(int x, int y)
        {
            return x*y;
        }
    },
    
    Division
    {
        public override int Eval(int x, int y)
        {
            return x/y;
        }
    };
    
    public abstract int Eval(int x, int y);
}


Sometimes, you may wish to save a bit of space and specify the implementation of
a method as a delegate – especially if the method would otherwise be abstract (i.e.
there was no “common” implementation which most values would use). Here, C#’s
anonymous method syntax helps:


public class enum ArithmeticOperation
{    
    delegate int Int32Operation (int x, int y);
    
    Addition (delegate (int x, int y) { return x+y; }),
    Subtraction (delegate (int x, int y) { return x-y; }),
    Multiplication (delegate (int x, int y) { return x*y; }),
    Division (delegate (int x, int y) { return x/y; });
        
    Int32Operation op;
    
    ArithmeticOperation (Int32Operation op)
    {
        this.op = op;
    }
    
    public int Eval (int x, int y)
    {
        return op(x, y);
    }
}


That’s still a bit clumsy, of course – let’s try with lambda function syntax instead:


public class enum ArithmeticOperation
{    
    Addition ( (x,y) => x+y),
    Subtraction ( (x,y) => x-y),
    Multiplication ( (x,y) => x*y),
    Division ( (x,y) => x/y);
        
    Func<int, int> op;
    
    ArithmeticOperation (Func<int,int> op)
    {
        this.op = op;
    }
    
    public int Eval (int x, int y)
    {
        return op(x, y);
    }
}


Now we’re really cooking! Of course, some of the time you’ll be able to provide a single implementation for most values,
which only some values will want to override. Something like:


public class enum InputType
{
    Integer,
    String,
    Date
    {
        // Default implementation isn't quite good enough for us
        public override string Format(object o)
        {
            return ((DateTime)o).ToString("yyyyMMdd");
        }
    };
    
    // Default implementation of formatting
    public virtual string Format(object o)
    {
        return o.ToString();
    }
}


So far, this is all quite similar to Java’s enums in appearance. Java’s enums also come with an ordinal
(the position of declaration within the enum) automatically, but in my experience this is as much of a
pain as it is a blessing. In particular, as that ordinal can’t be specified in the source code, if you
have other code relying on specific values (e.g. to pass data across a web-service) you have to leave
bogus values in the list in order to keep the ordinals of the later values the same. Java also only
allows you to specify the constructors in “top-most” enum. This can occasionally be a nuisance. Let’s extend
the enum above to include DateTime and Time – both of which need the same kind of
“special” formatting. In Java, you’d have to override Format in three different places, like
this:


public class enum InputType
{
    Integer,
    String,
    DateTime
    {
        public override string Format(object o)
        {
            return ((System.DateTime)o).ToString("yyyyMMdd HH:mm:ss");
        }
    },
    Date
    {
        public override string Format(object o)
        {
            return ((System.DateTime)o).ToString("yyyyMMdd");
        }
    },
    Time
    {
        public override string Format(object o)
        {
            return ((System.DateTime)o).ToString("HH:mm:ss");
        }
    };
    
    public virtual string Format(object o)
    {
        return o.ToString();
    }
}


I would propose that enum values could reuse each other’s implementations, possibly
parameterising them via constructors. The above could be rewritten as:


public class enum InputType
{
    Integer,
    String,
    DateTime("yyyyMMdd HH:mm:ss")
    {
        string formatSpecifier;
        
        protected DateTime(string formatSpecifier)
        {
            this.formatSpecifier = formatSpecifier;
        }
        
        public override string Format(object o)
        {
            return ((System.DateTime)o).ToString(formatSpecifier);
        }
    },
    Date : DateTime("yyyyMMdd"),
    Time : DateTime("HH:mm:ss");
    
    public virtual string Format(object o)
    {
        return o.ToString();
    }
}

If Date wanted to further specialise the class (e.g. if another method needed overriding), it could add implementation there too. Note that the DateTime constructor does not explicitly call any constructor. In this case, an implicit call to the InputType constructor which took only the name parameter would be made. Explicit calls to base class constructors could be included in the normal way – the extra parameter would be entirely hidden from the source code. Only protected constructors could be called by derived types in the normal way.


Switch


Switch statements would appear in exactly the same way they do now. (Possibly without the qualification (e.g. case Time: instead of case InputType.Time:. The code is more readable without the qualification, and is unambiguous, but it would be inconsistent with the current handling of switch cases for “normal” enums.) The implementation would work a lot like strings – either using the equivalent of a sequence of if statements or building a map behind the scenes. This is where keeping something like Java’s ordinals would speed things up, but then I would at least want something like an attribute to be able to specify the value in source code to avoid the problems described in Java earlier. Note that only reference equality needs to be checked in any of these cases, as only one instance of any value would be created.


Static field initializers and static constructors


Java has restrictions on where you can use static fields in enums, because the static field initializers are executed after the enum values have been created. Static fields are useful in a surprising number of circumstances, mostly getting at an enum value dynamically by something other than name. The rules for this would need to be considered carefully – sometimes it’s useful to have code which will be run after the enums have all been set up; other times you want it beforehand (so you can use the static fields during initialization, e.g. to add a value to a map).


Other features


Like Java, there could be an EnumSet<T> type which would be the equivalent of using FlagsAttribute on normal enums. Indeed, the compiler could even generate operator overloads to make this look nicer.


In Java, some enums with many values overriding many methods can end up being pretty large. In C#, of course, we can use partial types to split the whole enum definition over several files. (Some may object to this, others not – it would be available if you wanted it.)


Open questions


  • The potential abuse problem mentioned earlier
  • Serialization/deserialization would need to know to use the previously set up values
  • Should identifying values (like Java ordinals) be present, if only for switch performance?

I suspect there are other things I haven’t thought of, but with any luck this will be food for thought.