Java vs C# algorithm execution

Question

I have N-queen problem written in Java and C#. You can find out more about 8-queen problem here.

Here is Java code:

package nqueens;
import java.util.Arrays;
public class NQueens {
  public static void main(String args[]) {
    int n = 13;
    int[] ploca = new int[n];
    postaviKraljicuNaPlocu(0, ploca);
  }
  private static void postaviKraljicuNaPlocu(int Ki, int[] ploca) {
    int n = ploca.length;
    if (Ki == n) {
      System.out.println(Arrays.toString(ploca));
    } else {
      for (int kolona = 0; kolona < n; kolona++) {
        if (jeLiSigurnoMjesto(kolona, Ki, ploca)) {
          ploca[Ki] = kolona;
          postaviKraljicuNaPlocu(Ki + 1, ploca);
          ploca[Ki] = -1;
        }
      }
    }
  }
  private static boolean jeLiSigurnoMjesto(int kolona, int Ki, int[] ploca) {
    for (int i = 0; i < Ki; i++) {
      if (ploca[i] == kolona) { 
        return false;
      }
      if (Math.abs(ploca[i] - kolona) == Math.abs(i - Ki)) {
        return false;
      }
    }
    return true;
  }
}

Here is C# code:

using System;
namespace nkraljica
{
    public class NKraljica
    {
        public static void Main(string[] args)
        {
            int n = 13;
            int[] ploca = new int[n];
            postaviKraljicuNaPlocu(0, ploca);
        }
        private static void postaviKraljicuNaPlocu(int Ki, int[] ploca)
        {
            int n = ploca.Length;
            if (Ki == n)
            {
                Console.WriteLine(string.Join("", ploca));
            }
            else
            {
                for (int kolona = 0; kolona < n; kolona++)
                {
                    if (jeLiSigurnoMjesto(kolona, Ki, ploca))
                    {
                        ploca[Ki] = kolona;
                        postaviKraljicuNaPlocu(Ki + 1, ploca);
                        ploca[Ki] = -1;
                    }
                }
            }
        }
        private static bool jeLiSigurnoMjesto(int kolona, int Ki, int[] ploca)
        {
            for (int i = 0; i < Ki; i++)
            {
                if (ploca[i] == kolona)
                {
                    return false;
                }
                if (Math.Abs(ploca[i] - kolona) == Math.Abs(i - Ki))
                {
                    return false;
                }
            }
            return true;
        }
    }
}

For N=13, Java code finishes in 1,7 second, but C# in 17,3 seconds. Why is difference so big?

Answer 1

To really get to the bottom of this, you need to profile the c# code to determine where it is spending time. In the past, I have used the dotTrace profiler successfully for tasks like this; Visual Studio also has a built-in profiler; and more recommendations can be found here.

For us to give much of an opinion on the time difference, you need to describe your build and run environments with some detail. Are you building debug or (hopefully) release? What versions of .Net and Visual Studio are you using? What version of Java, and what build tools?

That being said, I experimented with your c# code a bit in VS 2008 / .Net 3.5 / Release build, and found the following:

• Running with Visual Studio attached:
  • Total time to run your code is roughly 10.7 seconds, repeatably.
  • If I replace your calls to Console.WriteLine() with calls to save the results in a StringBuilder, the time is reduced to 4.9 seconds. Apparently Console.WriteLine is very slow!
  • If I simply eliminate the calls to Console.WriteLine() and replace them with a dummy, the time is barely changed. So StringBuilder is pretty fast.
  • If I replace the calls to Math.Abs() with an inline check, the time is reduced to 4.0 seconds. Possibly .Net is not optimizing or inlining the calls to Math.Abs() while Java does do so.
• Running from the command line, or otherwise without Visual Studio attached:
  • Total time using Console.WriteLine(): 9-10 seconds, repeatably.
  • Total time using StringBuilder logging: 3.0 seconds.
  • Total time using dummy logging: 3.0 seconds.
  • Total time with an inline version of Math.Abs(): 1.6 seconds.

From this, I conclude:

1. Running with Visual Studio attached can significantly slow things down even in release mode. (See also here.) Be sure to run both your Java and c# executables from the command line when timing performance.

2. Console.WriteLine() is slow -- slow enough that it dominates the time taken by your algorithm. The Java equivalent might be faster, and if so that could explain some of the difference.

3. Possibly Java is doing a better job at inlining or optimizing the calls to Math.Abs(). The improvement from manually inlining the calls is significant.

I don't have Java installed on my computer to run the comparisons myself.

Here's the code I used to do the testing:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Timers;
using System.Diagnostics;

namespace nkraljica
{
    public class NKraljicaMain
    {
        public static void Main(string[] args)
        {
            int n = 13;

            var stopwatch = new Stopwatch();

            stopwatch.Reset();
            stopwatch.Start();
            Abs.NKraljica.postaviKraljicuNaPlocu(n, Console.WriteLine);
            stopwatch.Stop();
            var consoleElapsed = stopwatch.Elapsed;

            stopwatch.Reset();
            stopwatch.Start();
            StringBuilder sb1 = new StringBuilder();
            Abs.NKraljica.postaviKraljicuNaPlocu(n, s => sb1.AppendLine(s));
            stopwatch.Stop();

            var sbElapsed = stopwatch.Elapsed;

            stopwatch.Reset();
            stopwatch.Start();
            string lastLine = null;
            Abs.NKraljica.postaviKraljicuNaPlocu(n, s => lastLine = s);
            stopwatch.Stop();

            var nologElapsed = stopwatch.Elapsed;

            stopwatch.Reset();
            stopwatch.Start();
            StringBuilder sb2 = new StringBuilder();
            Inline.NKraljica.postaviKraljicuNaPlocu(n, s => sb2.AppendLine(s));
            stopwatch.Stop();

            var inlineElapsed = stopwatch.Elapsed;

            Debug.Assert(sb1.ToString() == sb2.ToString());

            Console.WriteLine(string.Format("Console logging time = {0}", consoleElapsed));
            Console.WriteLine(string.Format("StringBuilder logging time = {0}", sbElapsed));
            Console.WriteLine(string.Format("Dummy logging time = {0}", nologElapsed));
            Console.WriteLine(string.Format("Inline Abs + StringBuilder logging time = {0}", inlineElapsed));

            Console.ReadLine();
        }
    }
}

namespace nkraljica.Abs
{
    public class NKraljica
    {
        public static void postaviKraljicuNaPlocu(int n, Action<string> reportFunc)
        {
            int[] ploca = new int[n];
            postaviKraljicuNaPlocu(0, ploca, reportFunc);
        }

        private static void postaviKraljicuNaPlocu(int Ki, int[] ploca, Action<string> reportFunc)
        {
            int n = ploca.Length;
            if (Ki == n)
            {
                reportFunc(ploca.Aggregate(new StringBuilder(), (sb, i) => sb.Append(i)).ToString());
            }
            else
            {
                for (int kolona = 0; kolona < n; kolona++)
                {
                    if (jeLiSigurnoMjesto(kolona, Ki, ploca))
                    {
                        ploca[Ki] = kolona;
                        postaviKraljicuNaPlocu(Ki + 1, ploca, reportFunc);
                        ploca[Ki] = -1;
                    }
                }
            }
        }
        private static bool jeLiSigurnoMjesto(int kolona, int Ki, int[] ploca)
        {
            for (int i = 0; i < Ki; i++)
            {
                if (ploca[i] == kolona)
                {
                    return false;
                }
                if (Math.Abs(ploca[i] - kolona) == Math.Abs(i - Ki))
                {
                    return false;
                }
            }
            return true;
        }
    }
}

namespace nkraljica.Inline
{
    public class NKraljica
    {
        public static void postaviKraljicuNaPlocu(int n, Action<string> reportFunc)
        {
            int[] ploca = new int[n];
            postaviKraljicuNaPlocu(0, ploca, reportFunc);
        }

        private static void postaviKraljicuNaPlocu(int Ki, int[] ploca, Action<string> reportFunc)
        {
            int n = ploca.Length;
            if (Ki == n)
            {
                reportFunc(ploca.Aggregate(new StringBuilder(), (sb, i) => sb.Append(i)).ToString());
            }
            else
            {
                for (int kolona = 0; kolona < n; kolona++)
                {
                    if (jeLiSigurnoMjesto(kolona, Ki, ploca))
                    {
                        ploca[Ki] = kolona;
                        postaviKraljicuNaPlocu(Ki + 1, ploca, reportFunc);
                        ploca[Ki] = -1;
                    }
                }
            }
        }
        private static bool jeLiSigurnoMjesto(int kolona, int Ki, int[] ploca)
        {
            for (int i = 0; i < Ki; i++)
            {
                if (ploca[i] == kolona)
                {
                    return false;
                }
                int diff1 = ploca[i] - kolona;
                int diff2 = i - Ki;
                if (diff1 == diff2 || diff1 == checked(-diff2))
                {
                    return false;
                }
            }
            return true;
        }
    }
}