[Mono-list] C# program in 2000 times slower than equivalent C program

[Yury Serdyuk]

Hi!

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

 


#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;

}


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:

[serdyuk at skif Quicksort]$ ./quicksort2
read_data 0.06
sort 0.0100000000

[serdyuk at skif Quicksort]$ mono QuicksortSimple.exe
N = 100000
Elapsed time : 20.815316

[serdyuk at skif Quicksort]$ mono -V
Mono JIT compiler version 1.2.6 (tarball)
Copyright (C) 2002-2007 Novell, Inc and Contributors. www.mono-project.com
        TLS:           __thread
        GC:            Included Boehm (with typed GC)
        SIGSEGV:       normal
        Notifications: epoll
        Architecture:  x86
        Disabled:      none 

 

Why?


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

using System.IO;

using System;

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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-list/attachments/20080228/0f169dc9/attachment.html