9

I'm new to C# and have run into a problem with the following code (I have the target framework as 4.5 and I've added a reference to System.Numerics):

using System;
using System.Numerics;

namespace Test
{
    class Program
    {
        static BigInteger Gcd(BigInteger x, BigInteger y)
        {
            Console.WriteLine("GCD {0}, {1}", x, y);
            if (x < y) return Gcd(y, x);
            if (x % y == 0) return y;
            return Gcd(y, x % y);
        }

        static void Main(string[] args)
        {
            BigInteger a = 13394673;
            BigInteger b = 53578691;
            Gcd(a, b);
        }
    }
}

When the release build is started with debugging (F5 in Visual Studio - and a break-point at the end of program so I can see the output), I get the following output:

GCD 13394673, 53578691
GCD 53578691, 13394673
GCD 13394673, 13394672
GCD 13394672, 1

However, when the release build is started without debugging (Ctrl-F5), I get the following:

GCD 13394673, 53578691
GCD 53578691, 53578691

Strangely if I add a Console.ReadLine() at the end of the program it works as expected!

Any ideas what is causing this? Thanks.

Phil Sturges
  • 173
  • 5
  • 3
    Welcome to a [Heisenbug](https://en.wikipedia.org/wiki/Heisenbug) – Yuval Itzchakov Jun 30 '15 at 11:50
  • Hmm... I can't reproduce this in VS2015 - I'm seeing the first output in both cases. – Jon Skeet Jun 30 '15 at 11:52
  • LINQPad behaves the same way - depending on whether you enable or disable optimization. Interesting. (Running on Win 7, .NET 4.5.1) – germi Jun 30 '15 at 11:52
  • I can reproduce this in Visual Studio 2012. Very interesting. – Baldrick Jun 30 '15 at 11:54
  • Stick a `Thread.Sleep(1000);` at the end, it works consistently too. – Baldrick Jun 30 '15 at 12:00
  • Maybe it's because there's no code that can possibly use the return value, so it does some weird optimization? Having `Console.WriteLine(Gcd(a, b));` as the last line produces consistent behavior. – Baldrick Jun 30 '15 at 12:03
  • Adding `Console.WriteLine("test");` three times in `Gcd` also helps (twice isn't enough). Strange. – germi Jun 30 '15 at 12:03
  • http://stackoverflow.com/questions/2345534/c-sharp-xna-visual-studio-difference-between-release-and-debug-modes/2345645#2345645 see Eric Lippert's answer – daryal Jun 30 '15 at 12:05
  • @daryal: Hmm.. but surely BigInteger behavior shouldn't be affected by that? – Baldrick Jun 30 '15 at 12:06
  • @Baldrick I do not know about the internals of BigInteger but it seems like a similar issue. I guess BigInteger uses floating point arithmetic internally. – daryal Jun 30 '15 at 12:08
  • interesting.. but unable to reproduce in VS2012 or VS2013 – Chaitanya Gadkari Jun 30 '15 at 12:09
  • http://stackoverflow.com/a/2225670/3959541 – Chaitanya Gadkari Jun 30 '15 at 12:20
  • Thanks for the quick replies everyone. For completeness, I'm on VS2013 and you need to be using the release build to see the problem. I'm not clear on the optimization differences you get when you start with or without debugging... as this is the release build in both cases - would there be different code 'running' depending on how I start it? – Phil Sturges Jun 30 '15 at 12:24

1 Answers1

11

This is an x64 jitter optimizer bug in .NET 4.0 through 4.5.2. Characterizing it is fairly difficult, the codegen is pretty heavy due to the BigInteger usage. The x64 jitter has had a history of optimizer bugs for struct types, like BigInteger, so that's the probable underlying cause. The combination with the possible tail-call optimization in this method is the most likely trigger.

I would normally recommend reporting such a bug, but the days of this jitter are numbered. Microsoft decided to retire it and rewrite it completely. Available in .NET 4.6 - VS2015, the project code name was RyuJIT. It doesn't have this bug.

Several possible workarounds:

Project + Properties, Build tab, Platform target = x86. That forces the program to run in 32-bit mode and use the x86 jitter, it doesn't have this bug.

Or disable optimization for this method with an attribute:

  using System.Runtime.CompilerServices;
  ...
    [MethodImpl(MethodImplOptions.NoOptimization)]
    static BigInteger Gcd(BigInteger x, BigInteger y) {
        // etc...
    }

Which is fine, the heavy lifting is in the BigInteger class so disabling the optimization isn't going to affect execution time.

Hans Passant
  • 922,412
  • 146
  • 1,693
  • 2,536
  • @HansPassant, okay I had target set to any CPU and preffered 32bit, so I could not reproduce the bug. changed the target and reproduced the bug. But still it was reproduced only using VS2013 and not VS2012. – Chaitanya Gadkari Jun 30 '15 at 12:51
  • @HansPassant I'm very new to C# so it is a bit disappointing to run into a bug like this (at least it wasn't intermittent) - would you say C# was 'buggy' compared to C++? – Phil Sturges Jun 30 '15 at 12:59
  • 1
    Hehe, yes, you are unlucky :) Newbie programmers do have a knack for it, nobody actually writes code like this. Note that this kind of code also easily crashes with this site's name, make the numbers big enough and you'll fall over on a StackOverflowException. Which is not a bug. C++ compilers have many bugs as well, C# holds up well in general. The jitter optimizer was written in C++ :) – Hans Passant Jun 30 '15 at 13:12
  • http://blogs.msdn.com/b/vcblog/archive/2015/07/01/c-compiler-front-end-fixes-in-vs2015.aspx – Hans Passant Jul 03 '15 at 23:32