Java vs. C#

[Gregor]

Kingruedis Code mit den genannten Compiler-Optionen :

1,2 GHz         1,6 GHz
Array                :        130             120
Zufallszahlen        :       1502            1162
sortieren            :       1412            1101
String erzeugen      :     103999           76490
Speichern            :       5158            3165
Wurzel berechnen     :        561             460

...bei mir schwanken die Ergebnisse übrigens von mal zu mal recht stark. Wenn mir etwas komisch vorkommt, dann mache ich die Messung immer nochmal. Hier war z.B. das "Wurzel berechnen" bei einer Mesung sehr langsam (4026).

Ich zeige gleich mal meine Java-Version, bei der ich die Stringerzeugung per Hand mache. Vielleicht hilft die Version, das in C++ effizienter zu implementieren.

EDIT : Die txt-Datei hat hier übrigens nur 15MB!

[ Dieser Beitrag wurde am 11.10.2002 um 14:00 Uhr von Gregor editiert. ]

[Gregor]

2. Java-Variante (per Hand String + Sortieren)

1,2 GHz         1,6 GHz
Array                :        190             181
Zufallszahlen        :       4677            3495
sortieren            :       2683            2013
String erzeugen      :       2784            2093
Speichern            :       2844            2844
Wurzel berechnen     :        181             130

Komischerweise wirken sich die MHz hier garnicht auf die Geschwindigkeit des Speicherns aus.

der Code :
[java]
import java.util.;
import java.io.;

public class Benchmark2
{
public Benchmark2 ()
{
}

private final static byte [] digits = {'0','1','2','3','4','5','6','7','8','9'};

private final static byte [] DigitTens = {
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
'2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
'3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
'4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
'5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
'6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
'7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
'8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
'9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
} ;

private final static byte [] DigitOnes = {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
} ;

public static void main (String[] args)
{
long [] times = new long [7];
int i;
int arrayLength = 5000000;
times [0] = System.currentTimeMillis ();
// Array erzeugen
int [] array = new int [arrayLength];
double [] doubleArray = new double [arrayLength];
times [1] = System.currentTimeMillis ();
// Zufallszahlen erzeugen
Random rand = new Random();
for (i = 0 ; i < arrayLength ; ++i)
{
array[i] = rand.nextInt ();
doubleArray[i] = rand.nextDouble ();
}
times [2] = System.currentTimeMillis ();
// Array sortieren
sort (array);
times [3] = System.currentTimeMillis ();
// Zahlen des Arrays in einen großen String verwandeln (jede Zeile eine Zahl)
byte [] byteArray = new byte [arrayLength * 12];
int pos = 0;
int currentStringPos;
byte [] tempString;
for (i = 0 ; i < array.length ; ++i)
{
pos = addIntegerToString (array[i], byteArray, pos);
byteArray [pos] = '\n';
++pos;
}
times [4] = System.currentTimeMillis ();
// String in eine Datei abspeichern
BufferedOutputStream stream;
try
{
stream = new BufferedOutputStream (new FileOutputStream ("test.txt"));
stream.write (byteArray,0,pos);
stream.close ();
}
catch (IOException e)
{
System.out.println ("FEHLER FEHLER FEHLER FEHLER FEHLER");
}
times [5] = System.currentTimeMillis ();
// Wurzeln berechnen
for (i = 0 ; i < doubleArray.length ; ++i)
{
doubleArray[i] = Math.sqrt(doubleArray[i]);
}
times [6] = System.currentTimeMillis ();
// Ausgabe der Zeiten
System.out.println ("Array erzeugen : " + String.valueOf (times[1]-times[0]) + "ms");
System.out.println ("Zufallszahlen erzeugen : " + String.valueOf (times[2]-times[1]) + "ms");
System.out.println ("Sortieren : " + String.valueOf (times[3]-times[2]) + "ms");
System.out.println ("String (anhängen) : " + String.valueOf (times[4]-times[3]) + "ms");
System.out.println ("Speichern : " + String.valueOf (times[5]-times[4]) + "ms");
System.out.println ("Wurzeln berechnen : " + String.valueOf (times[6]-times[5]) + "ms");
}

private final static int addIntegerToString(int i, byte [] string, int currentPos)
{
int q, r, charPos ;
charPos = 12 ;
byte buf [] = new byte [charPos] ;
byte sign = 0 ;

if (i == Integer.MIN_VALUE)
{
buf = new byte [] {'0','-','2','1','4','7','4','8','3','6','4','8'};
charPos = 1;
}
else
{
if (i < 0)
{
sign = '-' ;
i = -i ;
}

// Generate two digits per iteration
while ( i >= 65536 )
{
q = i / 100 ;
// really: r = i - (q * 100) ;
r = i - ((q << 6) + (q << 5) + (q << 2)) ;
i = q ;
buf [--charPos] = DigitOnes [r] ;
buf [--charPos] = DigitTens [r] ;
}

// Fall thru to fast mode for smaller numbers
// assert(i <= 65536, i);
for (;;)
{
q = (i * 52429) >>> (16+3) ;
r = i - ((q << 3) + (q << 1)) ; // r = i-(q*10) ...
buf [--charPos] = digits [r] ;
i = q ;
if (i == 0) break ;
}
if (sign != 0)
{
buf [--charPos] = sign ;
}
}

int end = 12 - charPos+currentPos;
for (;currentPos < end ; ++currentPos, ++charPos)
{
string [currentPos] = buf[charPos];
}
return currentPos;
}

private final static void sort (int [] a)
{
quickSort (a,0,a.length-1);
}

private final static void quickSort (int [] a, int begin, int end)
{
int i=begin,j=end;
int pivotElement = a[((end + begin) >>> 1)];
int temp = 0;
while (i < j)
{
while (a[i] < pivotElement) ++i;
while (a[j] > pivotElement) --j;
if (a[i] == (temp = a[j]))
{
++i;
continue;
}
a[j] = a[i];
a[i] = temp;
if (a[i] != pivotElement) ++i;
else
{
temp = ((j-i) >>> 1) + i;
a[i] = a[temp];
a[temp] = pivotElement;
}
if (a[j] != pivotElement) --j;
else
{
temp = ((j-i) >>> 1) + i;
a[j] = a[temp];
a[temp] = pivotElement;
}
}
if ((temp = j - begin) > 18) quickSort (a,begin,j-1);
else if (temp > 1) insertionSort (a,begin,j-1);
if ((temp = end - j) > 18) quickSort (a,j+1,end);
else if (temp > 1) insertionSort (a,j+1,end);
}

private final static void insertionSort (int [] a, int begin, int end)
{
int j, b;
int temp;
int i = begin;
while (i != end)
{
++i;
temp = a[i];
b = i;
j = i - 1;
while (temp < a[j])
{
a[b] = a[j];
b = j;
--j;
if (b == begin) break;
}
a[b] = temp;
}
}
}[/code]

[Helium]

#ifdef NO_VECTOR
      intArray[i]    = static_cast<int>(std::numeric_limits<int>::max() * rand() / RAND_MAX + 1.0);
      doubleArray[i] = (std::numeric_limits<double>::max() * rand() / RAND_MAX + 1.0);
      #else
      intArray.push_back(static_cast<int>(std::numeric_limits<int>::max() * std::rand() / RAND_MAX + 1.0));
      doubleArray.push_back(std::numeric_limits<double>::max() * std::rand() / RAND_MAX + 1.0);
      #endif

Stand irgendwo lege ein Feld der Große arrayLength und hänge hinten ein paar Zufalszahlen an? oder was soll das push_back???

Und ich habe grade einfach mahl versucht das ganze auf dem MSVC laufenzulassen. Ging natürlich nicht, weil bei dem nur etwa die hälfte im richtigen Namensraum steht. Und der hat extrem langsame stringstreams. Deshalb habe ich das ganze mal an den MSVC angepast und dann folgende Ergebnisse bekommen

211
434
886
49859
99813
3897

nicht grade toll. Ich habe aber grade nur diesen dämlichen Compiler da. *heul*. Könnte mal jemand den Code hier ausprobieren:

#include <iostream>   
#include <cmath>      
#include <ctime>      
#include <fstream>    
#include <algorithm>
#include <functional>
#include <limits>
#include <sstream>    
#include <deque>
#ifndef NO_VECTOR
#include <vector>
#endif

using namespace std;

inline const string to_string(int x)
{
   stringstream tmp;
   tmp << x;
   return tmp.str();
}

#ifdef WIN32
#  include <windows.h>
#  ifdef _MSC_VER 
#    undef max
#  endif
#else
#  include <sys/time.h>
#endif

int main()
{
#ifdef WIN32
   DWORD times[7];  
#else
   struct timeval times[7];
   struct timezone tz;
#endif
   const size_t arrayLength=5000000;  
   size_t i=0;

   //Arrays erzeugen  
#ifdef WIN32
   times[0] = GetTickCount();
#else
   gettimeofday(×[0], &tz);
#endif
#ifdef NO_VECTOR
   int * intArray=new int[arrayLength];
   double * doubleArray=new double[arrayLength];
#else
   vector<int> intArray(arrayLength);
   vector<double> doubleArray(arrayLength);
#endif
#ifdef WIN32
   times[1] = GetTickCount();
#else
   gettimeofday(×[1], &tz);
#endif

   cout << "Array erzeugt" << endl;

   //Zufallszahlen
   srand( (unsigned int)0 );
   for(;i<arrayLength;++i)
   {
      intArray[i]    = static_cast<int>(std::numeric_limits<int>::max() * rand() / RAND_MAX + 1.0);
      doubleArray[i] = (std::numeric_limits<double>::max() * rand() / RAND_MAX + 1.0);
   }
#ifdef WIN32
   times[2] = GetTickCount();
#else
   gettimeofday(×[2], &tz);
#endif

   cout << "Zufallszahlen erzeugt" << endl;

   //Sortieren
#ifdef NO_VECTOR
   sort(&intArray[0], &intArray[arrayLength-1]);
#else
   sort(intArray.begin(), intArray.end());
#endif
#ifdef WIN32
   times[3] = GetTickCount();
#else
   gettimeofday(×[3], &tz);
#endif

   cout << "Sortiert" << endl;

   //int to char

   deque<string> schlange;
   ostringstream stringBuffer;

   for(i=0; i<arrayLength; ++i)
   {
      schlange.push_back(to_string(intArray[i]));
      schlange.push_back("\n");
   }
#ifdef WIN32
   times[4] = GetTickCount();
#else
   gettimeofday(×[4], &tz);
#endif

   cout << "An String angehaengt" << endl;

   //string in Datei schreiben
   ofstream out("demo.txt");
   if(!out.is_open())
   {
      std::cerr << "Fehler" << std::endl;
#ifdef NO_VECTOR
      delete[] intArray;
      delete[] doubleArray;
#endif
      return 1;
   }

   for (deque<string>::iterator it = schlange.begin(); it != schlange.end(); ++it)
      out << *it;

   out.close();
#ifdef WIN32
   times[5] = GetTickCount();
#else
   gettimeofday(×[5], &tz);
#endif

   cout << "In Datei geschreiben" << endl;

   //Wurzeln berechnen
   for(i=0; i<arrayLength; ++i)
   {
      doubleArray[i] = sqrt(doubleArray[i]);
   }

#ifdef WIN32
   times[6] = GetTickCount();
#else
   gettimeofday(×[6], &tz);
#endif

   cout << "Wurzeln berechnet" << endl;

   //Ausgabe:
#ifdef WIN32
   cout << "Array erzeugen: " 
      << (times[1] - times[0])
      << std::endl;
   cout << "Zufallszahlen erzeugen: "
      << (times[2] - times[1])
      << std::endl;
   cout << "Sortieren: "
      << (times[3] - times[2])
      << std::endl;
   cout << "String anhaengen: "
      << (times[4] - times[3])
      << std::endl;
   cout << "Speichern: "
      << (times[5] - times[4])
      << std::endl;
   cout << "Wurzeln berechnen: "
      << (times[6] - times[5])
      << std::endl;
#else
   cout << "Array erzeugen: " 
      << (times[1].tv_usec - times[0].tv_usec)
      << std::endl;
   cout << "Zufallszahlen erzeugen: "
      << (times[2].tv_usec - times[1].tv_usec)
      << std::endl;
   cout << "Sortieren: "
      << (times[3].tv_usec - times[2].tv_usec)
      << std::endl;
   cout << "String anhaengen: "
      << (times[4].tv_usec - times[3].tv_usec)
      << std::endl;
   cout << "Speichern: "
      << (times[5].tv_usec - times[4].tv_usec)
      << std::endl;
   cout << "Wurzeln berechnen: "
      << (times[6].tv_usec - times[5].tv_usec)
      << std::endl;
#endif

#ifdef NO_VECTOR
   delete[] intArray;
   delete[] doubleArray;
#endif

   return 0;
}

[Helium]

Oh fuck, der schreibt nur einsen in die Datei.

Oh mal sehen

numeric_limits<int>::max() * rand() / RAND_MAX + 1.0

int * int / int + double

die erste multiplikation kann einen überlauf erzeugen. Die division teilt durch eine Zahl, die meist numeric_limits<int>::max() entspricht, also kommt 0 raus und 0 + 1 == 1

ersetzt

numeric_limits<int>::max() * rand() / RAND_MAX + 1.0

durch

static_cast<double>(numeric_limits<int>::max()) * rand() / RAND_MAX + 1.0

dann sollte es gehen

[Gregor]

Original erstellt von Helium:
**Oh fuck, der schreibt nur einsen in die Datei.
**

BAH! ...jetzt muss ich das Programm nochmal testen!

[Gregor]

Heliums Code mit den genannten Compiler-Optionen :

Es gab noch stärkere Schwankungen, als sonst. Die Ergebnisse können also nur als Anhaltspunkt genommen werden. Die erzeugte Datei scheint mehr oder weniger die richtige Größe zu haben, allerdings enthält sie ungefähr 2,5MB zu viel (vielleicht "\r\n" statt "\n"? ...sollte aber nicht viel ausmachen)

1,2 GHz         1,6 GHz
Array                :        130             120
Zufallszahlen        :       1142             861
sortieren            :       1422            1072
String erzeugen      :     147612          110609
Speichern            :      23464           27679
Wurzel berechnen     :       1182            1052

Gerade die Werte beim Speichern und bei den Wurzeln scheinen nicht der tatsächlichen Performance zu entsprechen. Die Größenordnung sollte aber stimmen. ...bei den Wurzeln habe ich (vor den Veränderungen) aber schon Messungen gemacht, die nur etwa die halbe Zeit benötigt hatten.

[rüdiger]

mach am besten 3 Messungen und nimm den Durchschnittswert, da kann sich ja immer etwas ändern, durch swapping etc.

eigentlich wär es am besten in dem Programm den Test 3 mal zu machen, da man dann vom L2 Cache profitieren kann.

[Gregor]

Ich habe eh mehrmals gemessen und habe dann die schlechtesten Meßergebnisse weggeworfen. Das Problem ist, dass Windows bei mir immer etwas im Hintergrund macht. ...das liegt aber nicht an Programmen, die ich nebenher laufen habe.

Wenn das erste C++-Programm kommt, bei dem kein Schritt länger als 10 Sekunden dauert, mache ich meinetwegen eine Mittelwertbildung über 10 Durchläufe.

...ich denke aber nicht, dass man da vom L2-Cache profitieren kann.

[Helium]

hast du zufällig bock dir die SGI-STL-Version runter zu laden. Mich würde mal interessieren, wie die Sich zu der von dir verwendeten verhält. Bei der Dinkumware scheinen deques etwas effektiver zu sein, als bei deiner (Siehe mein MSVC ergebnis. Warum haben wir in der Schule eigentlich nur diesen scheiß-Compiler?)
Das andere ergebnis beim in die Dateischreiben liegt wohl daran, dass meine Dateigröße stimmt.
Das mit den wurzeln ist möglicherweise unfair. Je größe die Zahl, desto länger dauert es die Wurzel zu berechnen. Und bei mir kamen meistens sehr große Zahlen raus.

[Gregor]

Bei Java werden nur double-Zahlen zwischen 0 und 1 erzeugt. ...kannst du ja bei dir anpassen.

Sag mal, wo man sich die SGI-STL-Version runterladen kann. Vielleicht mache ich das. ...ansonsten kannst du ja auch MinGW runterladen und dann mal berichten, ob es da starke Unterschiede gibt. ...aber egal, ob das etwas besser implementiert ist : Das wird nicht einen Faktor 10 und höher ausmachen.

[ Dieser Beitrag wurde am 12.10.2002 um 20:34 Uhr von Gregor editiert. ]

[Helium]

http://www.sgi.com/tech/stl/

[Gast]