Friday, March 4, 2011

Unexpected rounding errors with the C# compiler

I've recently discovered a small problem in the C# compiler that can cause unexpected precision loss when working with floating point numbers. The basic function looks like this:
double sum(double[] elements)
{
double sum = 0;
foreach(float f in elements)
sum += f;
return sum;
}

The problem is that the loop variable f is of type float rather than type double. The reason that this is a problem is that I expect the foreach statement to be semantically equivalent to a standard for loop when used on an array. In other words, it should do the same as this code:
double sum(double[] elements)
{
double sum = 0;
for(int i = 0; i < elements.Length; i++)
{
float f = elements[i];
sum += f;
}
return sum;
}


If you try to compile the above code, the compiler will give the error:
Cannot implicitly convert type 'double' to 'float'. An explicit conversion exists (are you missing a cast?).
This error is indeed correct, as the conversion from the array element to the loop variable f will cause a loss of precision.

You could argue that the assignment is redundant and that the sum variable could be updated without assigning anything to the loop variable. But inspecting the the CIL output of the compilation reveals that it does indeed convert it to single precision before using the variable (line 11+12, label L_0016 + L_0017):

0 L_0000: nop
1 L_0001: ldc.r8 0
2 L_000a: stloc.0
3 L_000b: nop
4 L_000c: ldarg.0
5 L_000d: stloc.3
6 L_000e: ldc.i4.0
7 L_000f: stloc.s V_4
8 L_0011: br.s 23 -> ldloc.s V_4
9 L_0013: ldloc.3
10 L_0014: ldloc.s V_4
11 L_0016: ldelem.r8
12 L_0017: conv.r4

13 L_0018: stloc.1
14 L_0019: ldloc.0
15 L_001a: ldloc.1
16 L_001b: conv.r8
17 L_001c: add
18 L_001d: stloc.0
19 L_001e: ldloc.s V_4
20 L_0020: ldc.i4.1
21 L_0021: add
22 L_0022: stloc.s V_4
23 L_0024: ldloc.s V_4
24 L_0026: ldloc.3
25 L_0027: ldlen
26 L_0028: conv.i4
27 L_0029: clt
28 L_002b: stloc.s V_5
29 L_002d: ldloc.s V_5
30 L_002f: brtrue.s 9 -> ldloc.3
31 L_0031: ldloc.0
32 L_0032: stloc.2
33 L_0033: br.s 34 -> ldloc.2
34 L_0035: ldloc.2
35 L_0036: ret


The explanation for this is that I have a common misconception about what the foreach loop does, as it actually inserts typecasts as well, meaning that the foreach loop gets expanded to:
double sum(double[] elements)
{
double sum = 0;
for(int i = 0; i < elements.Length; i++)
{
float f = (float)elements[i];
sum += f;
}
return sum;
}


Which explains the conversion and the lack of compile time errors. This does allow some more flexibility in the type system, but it also allows you to do completely unsafe things, such as declare the input type as object[] elements and the program will compile anyway. This is probably an issue that made the use of ArrayList more bearable back when generics were not yet implemented, so it seemed like a good idea at the time.

For me, this means that the compact notation that is given by foreach is now trumped by its drawbacks. The only remedy for now seems to be to use the var keyword in all foreach loops to ensure that the automatic type conversion is removed. Unfortunately this solution is only available for C# 3.0 and newer.

No comments: