none
C# program in 2000 times slower than equivalent C program RRS feed

  • Question

  • Hi!

    I have 2 implementations of Quicksort algorithm in C# and C++:

     

    Code Snippet

    #include <ctime>
    #include <string>
    #include <iostream>
    #include <iomanip>

    using namespace std;

    int read_data ( string filename, unsigned &N, int* &data )
    {
     FILE    *fd;
     size_t  i;

     fd = fopen ( filename.c_str(), "r" );
     if ( !fd ) {
      cerr << "Couldn't open file " << filename << endl;
     }

     fscanf ( fd, "%u", &N );
     data = new int [ N ];

     for ( i = 0; i < N; i++ )
      fscanf ( fd, "%d", &data[i] );

     fclose (fd);

     return 0;
    }

    void quicksort (int* first, int* last )
    {
     int       *k, *l;
     int       pivot;
     int tmp;

     if ( first >= last )
      return;

      pivot     = *first;

      k  = first + 1;
      l  = last;

      while ( ( *k <= pivot ) && ( k < last ) )
       k++;
      while ( *l > pivot )
       l--;

      while ( k < l ) {
       //swap ( *k, *l );
       tmp = *k;
       *k  = *l;
       *l  = tmp;

       do k++; while ( *k <= pivot );
       do l--; while ( *l > pivot );
      }

      //swap ( *first, *l );
      tmp     = *first;
      *first  = *l;
      *l      = tmp;

      quicksort ( first, l - 1);
      quicksort ( l + 1, last );

    }

    int main ( int argc, char* arv[] )
    {
      unsigned   N;
      int*       data;
      int        ret;

      clock_t    t0, t1;

      t0 = clock();
      ret = read_data ( "InputData.in", N, data );
      if ( ret ) {
       return 1;
      }
      t1 = clock();
      cout << "read_data " << (double)(t1 - t0)/CLOCKS_PER_SEC << endl;

      t0 = clock();
      quicksort ( data, data + N - 1 );
      t1 = clock();
      cout << "sort " << fixed << setprecision ( 10 ) << (double)(t1 - t0)/CLOCKS_PER_SEC << endl;

      delete[] data;

      return 0;

    }

     

     

     

    Code Snippet

    using System;
    using System.IO;

    public class QuicksortSimple  {

     public static int[]    x;

     public static void Main ( String[] args )   {

      int i;

      FileStream   fs = new FileStream ( "InputData.in", FileMode.Open, FileAccess.Read );
      StreamReader sr = new StreamReader ( fs );

      int   N = System.Convert.ToInt32 ( sr.ReadLine() );
      Console.WriteLine ( "N = " + N );

      x = new int [ N ];

      DateTime  dt1 = DateTime.Now;

      for ( i = 0; i < N; i++ )
       x [ i ] = System.Convert.ToInt32 ( sr.ReadLine() );

      DateTime  dt2 = DateTime.Now;
      Console.WriteLine ( "read_data : " + (dt2-dt1).TotalSeconds );
      sr.Close();
      fs.Close();

      dt1 = DateTime.Now;

      local_quicksort ( 0, x.Length - 1 );

      dt2 = DateTime.Now;

      Console.WriteLine ( "sort time : " + (dt2-dt1).TotalSeconds );

     }

     public static void local_quicksort ( int first, int last ) {

      int   k, l;
      int   tmp;

      if ( first >= last )
       return;

      int  pivot = x [ first ];

      k     = 1;
      l     = last;

      while ( x [ k ] <= pivot && k < last )
       k++;
      while ( x [ l ] > pivot )
       l--;

      while ( k < l ) {

       tmp     = x [ l ];
       x [ l ] = x [ k ];
       x [ k ] = tmp;

       do k++;
        while ( x [ k ] <= pivot );
       do l--;
        while ( x [ l ] > pivot );

      }

      tmp         = x [ l ];
      x [ l ]     = x [ first ];
      x [ first ] = tmp;

      local_quicksort ( first, l - 1 );
      local_quicksort ( l + 1, last   );

     }

    }

     

     

    Running them gives:

     

    K:\Tmp\>Quicksort
    read_data 0.078
    sort 0.0160000000

    K:\Tmp\>QuicksortSimple
    N = 100000
    read_data : 0,078125
    sort time : 35,1875

     

    Why?

    First of all, this is a question to the developers in Microsoft.

     

    A code to generate an input file for both programs is as following:

     

    Code Snippet

    using System;
    using System.IO;

    public class FileWriter {

     public static void Main ( String[] args )   {

      int    N = 100000;
      

      FileStream   fs = new FileStream ( "InputData.in", FileMode.Create, FileAccess.Write );

      StreamWriter sw = new StreamWriter ( fs );

      Random       rand = new Random();

      sw.WriteLine ( N );

      for ( int i = 0; i < N; i++ )
       sw.WriteLine ( rand.Next( 10000 ) );

      sw.Close();
      fs.Close();

     }

     

     

    Thanks.

     

    Thursday, February 28, 2008 1:37 PM

Answers

  • Sorry, it was my bug in program:

     

    Code Snippet

    public static void local_quicksort ( int first, int last ) {

      int   k, l;
      int   tmp;

      if ( first >= last )
       return;

      int  pivot = x [ first ];

      k     = 1;    //  IT"S a BUG:  k = first + 1 is needed  !!!

     

     

     

    Friday, February 29, 2008 11:09 AM

All replies

  • Hi,

     

    Have you taken into account JIT compilation time?

    During first call JIT compiler perfroms compilation of Main and local_quicksort methods.

     

     

    Thursday, February 28, 2008 2:25 PM
  • I suspect your performance is getting destroyed by those repeated static field accesses.  Due to the AppDomains feature of .NET, accessing static fields is slower than one might expect.  Multiply that by the dozens of times you're doing it for each call to local_quicksort and performance becomes terrible.

    Change your algorithm to pass the array as a parameter and you should see a very nice boost in speed.

    -Ryan / Kardax
    Thursday, February 28, 2008 5:15 PM
  • Sorry, it was my bug in program:

     

    Code Snippet

    public static void local_quicksort ( int first, int last ) {

      int   k, l;
      int   tmp;

      if ( first >= last )
       return;

      int  pivot = x [ first ];

      k     = 1;    //  IT"S a BUG:  k = first + 1 is needed  !!!

     

     

     

    Friday, February 29, 2008 11:09 AM