<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">

<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
 /* Font Definitions */
 @font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:Tahoma;
        panose-1:2 11 6 4 3 5 4 4 2 4;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0cm;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";
        color:black;}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
p
        {mso-style-priority:99;
        mso-margin-top-alt:auto;
        margin-right:0cm;
        mso-margin-bottom-alt:auto;
        margin-left:0cm;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";
        color:black;}
span.EmailStyle18
        {mso-style-type:personal-reply;
        font-family:"Calibri","sans-serif";
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;
        font-size:10.0pt;}
@page Section1
        {size:612.0pt 792.0pt;
        margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.Section1
        {page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1" />
 </o:shapelayout></xml><![endif]-->
</head>

<body bgcolor=white lang=EN-US link=blue vlink=purple>

<div class=Section1>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Hi there,<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>I experience the same kind of numbers with your code, but you
are comparing two different things.<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>A more elaborated and fair comparison does show that you can
sort very very quick in C# and very very slow in C if you want to. <o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Using the same dataset, I get<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>C with pointers&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
: 0.016 s<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>C with array in stead of pointers&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;:
7.86 s<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>C# Microsoft your quicksort&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:
10.68 s<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>C# mono win&nbsp; &nbsp;&nbsp;your quicksort&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
: 13.84 s<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>C# Microsoft Array.Sort &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:
0.015 s<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>C# mono win Array.Sort &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:
0.031 s<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>This is realy not bad for C# or for mono.<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>It would be interesting to see your quicksort with pointers in
C#.<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Bart<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<div>

<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'>

<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif";
color:windowtext'>From:</span></b><span style='font-size:10.0pt;font-family:
"Tahoma","sans-serif";color:windowtext'> mono-list-bounces@lists.ximian.com
[mailto:mono-list-bounces@lists.ximian.com] <b>On Behalf Of </b>Yury Serdyuk<br>
<b>Sent:</b> 28 February 2008 14:51<br>
<b>To:</b> mono-list@lists.ximian.com<br>
<b>Subject:</b> [Mono-list] C# program in 2000 times slower than equivalent
Cprogram<o:p></o:p></span></p>

</div>

</div>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

<p class=MsoNormal>&nbsp;&nbsp; <o:p></o:p></p>

<p><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Hi!</span><o:p></o:p></p>

<p>I have 2 implementations of Quicksort algorithm in C# and C++:<o:p></o:p></p>

<p>&nbsp;<o:p></o:p></p>

<div>

<div>

<div>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

</div>

<p>#include &lt;ctime&gt;<br>
#include &lt;string&gt;<br>
#include &lt;iostream&gt;<br>
#include &lt;iomanip&gt;<o:p></o:p></p>

<p>using namespace std;<o:p></o:p></p>

<p>int read_data ( string filename, unsigned &amp;N, int* &amp;data )<br>
{<br>
&nbsp;FILE&nbsp;&nbsp;&nbsp; *fd;<br>
&nbsp;size_t&nbsp; i;<o:p></o:p></p>

<p>&nbsp;fd = fopen ( filename.c_str(), &quot;r&quot; );<br>
&nbsp;if ( !fd ) {<br>
&nbsp; cerr &lt;&lt; &quot;Couldn't open file &quot; &lt;&lt; filename &lt;&lt;
endl;<br>
&nbsp;}<o:p></o:p></p>

<p>&nbsp;fscanf ( fd, &quot;%u&quot;, &amp;N );<br>
&nbsp;data = new int [ N ];<o:p></o:p></p>

<p>&nbsp;for ( i = 0; i &lt; N; i++ )<br>
&nbsp; fscanf ( fd, &quot;%d&quot;, &amp;data[i] );<o:p></o:p></p>

<p>&nbsp;fclose (fd);<o:p></o:p></p>

<p>&nbsp;return 0;<br>
}<o:p></o:p></p>

<p>void quicksort (int* first, int* last )<br>
{<br>
&nbsp;int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *k, *l;<br>
&nbsp;int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; pivot;<br>
&nbsp;int tmp;<o:p></o:p></p>

<p>&nbsp;if ( first &gt;= last )<br>
&nbsp; return;<o:p></o:p></p>

<p>&nbsp; pivot&nbsp;&nbsp;&nbsp;&nbsp; = *first;<o:p></o:p></p>

<p>&nbsp; k&nbsp; = first + 1;<br>
&nbsp; l&nbsp; = last;<o:p></o:p></p>

<p>&nbsp; while ( ( *k &lt;= pivot ) &amp;&amp; ( k &lt; last ) )<br>
&nbsp;&nbsp; k++;<br>
&nbsp; while ( *l &gt; pivot )<br>
&nbsp;&nbsp; l--;<o:p></o:p></p>

<p>&nbsp; while ( k &lt; l ) {<br>
&nbsp;&nbsp; //swap ( *k, *l );<br>
&nbsp;&nbsp; tmp = *k;<br>
&nbsp;&nbsp; *k&nbsp; = *l;<br>
&nbsp;&nbsp; *l&nbsp; = tmp;<o:p></o:p></p>

<p>&nbsp;&nbsp; do k++; while ( *k &lt;= pivot );<br>
&nbsp;&nbsp; do l--; while ( *l &gt; pivot );<br>
&nbsp; }<o:p></o:p></p>

<p>&nbsp; //swap ( *first, *l );<br>
&nbsp; tmp&nbsp;&nbsp;&nbsp;&nbsp; = *first;<br>
&nbsp; *first&nbsp; = *l;<br>
&nbsp; *l&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = tmp;<o:p></o:p></p>

<p>&nbsp; quicksort ( first, l - 1);<br>
&nbsp; quicksort ( l + 1, last );<o:p></o:p></p>

<p>}<o:p></o:p></p>

<p>int main ( int argc, char* arv[] )<br>
{<br>
&nbsp; unsigned&nbsp;&nbsp; N;<br>
&nbsp; int*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; data;<br>
&nbsp; int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ret;<o:p></o:p></p>

<p>&nbsp; clock_t&nbsp;&nbsp;&nbsp; t0, t1;<o:p></o:p></p>

<p>&nbsp; t0 = clock();<br>
&nbsp; ret = read_data ( &quot;InputData.in&quot;, N, data );<br>
&nbsp; if ( ret ) {<br>
&nbsp;&nbsp; return 1;<br>
&nbsp; }<br>
&nbsp; t1 = clock();<br>
&nbsp; cout &lt;&lt; &quot;read_data &quot; &lt;&lt; (double)(t1 -
t0)/CLOCKS_PER_SEC &lt;&lt; endl;<o:p></o:p></p>

<p>&nbsp; t0 = clock();<br>
&nbsp; quicksort ( data, data + N - 1 );<br>
&nbsp; t1 = clock();<br>
&nbsp; cout &lt;&lt; &quot;sort &quot; &lt;&lt; fixed &lt;&lt; setprecision (
10 ) &lt;&lt; (double)(t1 - t0)/CLOCKS_PER_SEC &lt;&lt; endl;<o:p></o:p></p>

<p>&nbsp; delete[] data;<o:p></o:p></p>

<p>&nbsp; return 0;<o:p></o:p></p>

<p>}<o:p></o:p></p>

</div>

</div>

<div>

<div>

<div>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

</div>

<p>using System;<br>
using System.IO;<o:p></o:p></p>

<p>public class QuicksortSimple&nbsp; {<o:p></o:p></p>

<p>&nbsp;public static int[]&nbsp;&nbsp;&nbsp; x;<o:p></o:p></p>

<p>&nbsp;public static void Main ( String[] args )&nbsp;&nbsp; {<o:p></o:p></p>

<p>&nbsp; int i;<o:p></o:p></p>

<p>&nbsp; FileStream&nbsp;&nbsp; fs = new FileStream (
&quot;InputData.in&quot;, FileMode.Open, FileAccess.Read );<br>
&nbsp; StreamReader sr = new StreamReader ( fs );<o:p></o:p></p>

<p>&nbsp; int&nbsp;&nbsp; N = System.Convert.ToInt32 ( sr.ReadLine() );<br>
&nbsp; Console.WriteLine ( &quot;N = &quot; + N );<o:p></o:p></p>

<p>&nbsp; x = new int [ N ];<o:p></o:p></p>

<p>&nbsp; DateTime&nbsp; dt1 = DateTime.Now;<o:p></o:p></p>

<p>&nbsp; for ( i = 0; i &lt; N; i++ )<br>
&nbsp;&nbsp; x [ i ] = System.Convert.ToInt32 ( sr.ReadLine() );<o:p></o:p></p>

<p>&nbsp; DateTime&nbsp; dt2 = DateTime.Now;<br>
&nbsp; Console.WriteLine ( &quot;read_data : &quot; + (dt2-dt1).TotalSeconds );<br>
&nbsp; sr.Close();<br>
&nbsp; fs.Close();<o:p></o:p></p>

<p>&nbsp; dt1 = DateTime.Now;<o:p></o:p></p>

<p>&nbsp; local_quicksort ( 0, x.Length - 1 );<o:p></o:p></p>

<p>&nbsp; dt2 = DateTime.Now;<o:p></o:p></p>

<p>&nbsp; Console.WriteLine ( &quot;sort time : &quot; + (dt2-dt1).TotalSeconds
);<o:p></o:p></p>

<p>&nbsp;}<o:p></o:p></p>

<p>&nbsp;public static void local_quicksort ( int first, int last ) {<o:p></o:p></p>

<p>&nbsp; int&nbsp;&nbsp; k, l;<br>
&nbsp; int&nbsp;&nbsp; tmp;<o:p></o:p></p>

<p>&nbsp; if ( first &gt;= last )<br>
&nbsp;&nbsp; return;<o:p></o:p></p>

<p>&nbsp; int&nbsp; pivot = x [ first ];<o:p></o:p></p>

<p>&nbsp; k&nbsp;&nbsp;&nbsp;&nbsp; = 1;<br>
&nbsp; l&nbsp;&nbsp;&nbsp;&nbsp; = last;<o:p></o:p></p>

<p>&nbsp; while ( x [ k ] &lt;= pivot &amp;&amp; k &lt; last )<br>
&nbsp;&nbsp; k++;<br>
&nbsp; while ( x [ l ] &gt; pivot )<br>
&nbsp;&nbsp; l--;<o:p></o:p></p>

<p>&nbsp; while ( k &lt; l ) {<o:p></o:p></p>

<p>&nbsp;&nbsp; tmp&nbsp;&nbsp;&nbsp;&nbsp; = x [ l ];<br>
&nbsp;&nbsp; x [ l ] = x [ k ];<br>
&nbsp;&nbsp; x [ k ] = tmp;<o:p></o:p></p>

<p>&nbsp;&nbsp; do k++;<br>
&nbsp;&nbsp;&nbsp; while ( x [ k ] &lt;= pivot );<br>
&nbsp;&nbsp; do l--;<br>
&nbsp;&nbsp;&nbsp; while ( x [ l ] &gt; pivot );<o:p></o:p></p>

<p>&nbsp; }<o:p></o:p></p>

<p>&nbsp; tmp&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = x [ l ];<br>
&nbsp; x [ l ]&nbsp;&nbsp;&nbsp;&nbsp; = x [ first ];<br>
&nbsp; x [ first ] = tmp;<o:p></o:p></p>

<p>&nbsp; local_quicksort ( first, l - 1 );<br>
&nbsp; local_quicksort ( l + 1, last&nbsp;&nbsp; );<o:p></o:p></p>

<p>&nbsp;}<o:p></o:p></p>

<p>}<o:p></o:p></p>

<p class=MsoNormal>&nbsp;&nbsp; &lt;&gt;<br>
<br>
<o:p></o:p></p>

</div>

</div>

<p class=MsoNormal>&lt;&gt;Running them gives:<br>
<br>
[serdyuk@skif Quicksort]$ ./quicksort2<br>
read_data 0.06<br>
sort 0.0100000000<br>
<br>
[serdyuk@skif Quicksort]$ mono QuicksortSimple.exe<br>
N = 100000<br>
Elapsed time : 20.815316<br>
<br>
[serdyuk@skif Quicksort]$ mono -V<br>
Mono JIT compiler version 1.2.6 (tarball)<br>
Copyright (C) 2002-2007 Novell, Inc and Contributors. <a
href="http://www.mono-project.com">www.mono-project.com</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
TLS:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; __thread<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
GC:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Included
Boehm (with typed GC)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
SIGSEGV:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; normal<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Notifications: epoll<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Architecture:&nbsp; x86<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
Disabled:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; none&nbsp; <o:p></o:p></p>

<p>&nbsp;<o:p></o:p></p>

<p>Why?<o:p></o:p></p>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

<p>A code to generate an input file for both programs is as following:<o:p></o:p></p>

<div>

<div>

<p>using System.IO;<o:p></o:p></p>

<p class=MsoNormal>using System;<o:p></o:p></p>

<p>public class FileWriter {<o:p></o:p></p>

<p>&nbsp;public static void Main ( String[] args )&nbsp;&nbsp; {<o:p></o:p></p>

<p>&nbsp; int&nbsp;&nbsp;&nbsp; N = 100000;<br>
&nbsp;&nbsp;<o:p></o:p></p>

<p>&nbsp; FileStream&nbsp;&nbsp; fs = new FileStream (
&quot;InputData.in&quot;, FileMode.Create, FileAccess.Write );<o:p></o:p></p>

<p>&nbsp; StreamWriter sw = new StreamWriter ( fs );<o:p></o:p></p>

<p>&nbsp; Random&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; rand = new Random();<o:p></o:p></p>

<p>&nbsp; sw.WriteLine ( N );<o:p></o:p></p>

<p>&nbsp; for ( int i = 0; i &lt; N; i++ )<br>
&nbsp;&nbsp; sw.WriteLine ( rand.Next( 10000 ) );<o:p></o:p></p>

<p>&nbsp; sw.Close();<br>
&nbsp; fs.Close();<o:p></o:p></p>

<p>&nbsp;}<o:p></o:p></p>

<p class=MsoNormal>&lt;&gt;} <br>
<br>
<o:p></o:p></p>

</div>

</div>

<p>&nbsp;<o:p></o:p></p>

<p>Thanks.<o:p></o:p></p>

</div>

<DIV>&nbsp;</DIV><br>DISCLAIMER(S):<br><br>http://www.etro.vub.ac.be/disclaimer<br>http://www.eqcologic.be/disclaimer</body>

</html>