Warum delphi lahmer als c++?

[alzaimar]

Zitat von Olli:

Mehr Code bedeutet auch, daß es länger dauert ihn auszuführen (es sei denn irgendwelche Schleifen wurden linearisiert, was durchaus vorkommen kann).

Nee.

Gegenbeispiel:
Boyer-Moore Pattern Matching (ca. 30 Zeilen) vs. naives Suchen (3 Zeilen)... Boyer-Moore ist viel viel schneller.

[Olli]

Zitat von alzaimar:

Gegenbeispiel:
Boyer-Moore Pattern Matching (ca. 30 Zeilen) vs. naives Suchen (3 Zeilen)... Boyer-Moore ist viel viel schneller.

Wie funzt denn "naives Suchen" nach alzaimar in 3 Zeilen? Lasse mich ja gern belehren, aber ich habe ja nicht ohne Grund Schleifen ausgeklammert. Und der Umkehrschluß ist natürlich augenfällig. Wenn innerhalb einer Schleife eine Anweisung steht und die Schleife aber eine Million Male aufgerufen wird, ist die Schleife logischerweise langsamer als eine Schleife mit 10 Anweisungen die nur 1000mal ausgeführt wird (unter der Annahme alle Anweisungen kosten gleichviel Zeit). Also bitte mehr Details. Ausnahmsweise bezog sich meine Angabe nämlich nicht auf "mehr" im Sinne von Dateigröße

Achso: "Zeilen" in HLLs zu vergleichen und daraus die Codelänge welche ausgeführt wird abzuleiten ist etwas gewagt

Nachtrag: Hah, ich glaube ich weiß woher das Mißverständnis rührt. Vermutlich wegen meiner Erwähnung der Linearisierung, richtig? Das ist natürlich ein Feature des Binärcodes und beeinflußt damit die Größe der Datei. Aber das "mehr" war wirklich auf die Ausführung gemünzt.

[alzaimar]

Zitat von Olli:

Zitat von alzaimar:

Gegenbeispiel:
Boyer-Moore Pattern Matching (ca. 30 Zeilen) vs. naives Suchen (3 Zeilen)... Boyer-Moore ist viel viel schneller.

Wie funzt denn "naives Suchen" nach alzaimar in 3 Zeilen?

Z.B. so (Suche die 'Needle' im 'Haystack'):

Delphi-Quellcode:

For i:=1 to length (Haystack)-Length(Needle)+1 do
  For j:=1 to Length (Needle) do
    If Haystack[i+j-1] = Needle[j] Then 
      Found := True;

Entschuldigung, sind 4 Zeilen. In C, Fortran, ASM etc. ist der Code nicht wesentlich komplexer.

"Naives Suchen" (oder Brute Force) ist eine gängige Bezeichung für dieses Verfahren. Ein Weiteres nennt sich übrigens "Not so naive".

Hier z.B. ein Pattern-Matching ("Reverse-Factor") der einem die Kinnlade runterklappen lässt , die Implementierung einer Graph-Klasse ist noch nichtmal dabei)... Aber schnell ist er trotzdem:
(Aus "Charras & Lecroq, Exact String Matching Algorithms")

Code:

void buildSuffixAutomaton(char *x, int m, Graph aut) {
   int i, art, init, last, p, q, r;
   char c;
  
   init = getInitial(aut);
   art = newVertex(aut);
   setSuffixLink(aut, init, art);
   last = init;
   for (i = 0; i < m; ++i) {
      c = x[i];
      p = last;
      q = newVertex(aut);
      setLength(aut, q, getLength(aut, p) + 1);
      setPosition(aut, q, getPosition(aut, p) + 1);
      while (p != init &&
             getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, p, c, q);
         setShift(aut, p, c, getPosition(aut, q) -
                             getPosition(aut, p) - 1);
         p = getSuffixLink(aut, p);
      }
      if (getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, init, c, q);
         setShift(aut, init, c,
                  getPosition(aut, q) -
                  getPosition(aut, init) - 1);
         setSuffixLink(aut, q, init);
      }
      else
         if (getLength(aut, p) + 1 ==
             getLength(aut, getTarget(aut, p, c)))
            setSuffixLink(aut, q, getTarget(aut, p, c));
         else {
            r = newVertex(aut);
            copyVertex(aut, r, getTarget(aut, p, c));
            setLength(aut, r, getLength(aut, p) + 1);
            setSuffixLink(aut, getTarget(aut, p, c), r);
            setSuffixLink(aut, q, r);
            while (p != art &&
                   getLength(aut, getTarget(aut, p, c)) >=
                   getLength(aut, r)) {
               setShift(aut, p, c,
                        getPosition(aut,
                                    getTarget(aut, p, c)) -
                        getPosition(aut, p) - 1);
               setTarget(aut, p, c, r);
               p = getSuffixLink(aut, p);
            }
         }
      last = q;
   }
   setTerminal(aut, last);
   while (last != init) {
      last = getSuffixLink(aut, last);
      setTerminal(aut, last);
   }
}


char *reverse(char *x, int m) {
   char *xR;
   int i;
 
   xR = (char *)malloc((m + 1)*sizeof(char));
   for (i = 0; i < m; ++i)
      xR[i] = x[m - 1 - i];
   xR[m] = '\0';
   return(xR);
}
 
 
int RF(char *x, int m, char *y, int n) {
   int i, j, shift, period, init, state;
   Graph aut;
   char *xR;
 
   /* Preprocessing */
   aut = newSuffixAutomaton(2*(m + 2), 2*(m + 2)*ASIZE);
   xR = reverse(x, m);
   buildSuffixAutomaton(xR, m, aut);
   init = getInitial(aut);
   period = m;
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      i = m - 1;
      state = init;
      shift = m;
      while (i + j >= 0 &&
             getTarget(aut, state, y[i + j]) !=
             UNDEFINED) {
         state = getTarget(aut, state, y[i + j]);
         if (isTerminal(aut, state)) {
            period = shift;
            shift = i;
         }
         --i;
      }
      if (i < 0) {
         OUTPUT(j);
         shift = period;
      }
      j += shift;
   }
}

Ich habe tatsächlich überlesen, das Du Schleifen explizit ausklammerst...

Egal: Natürlich benötigen 10000 Op-codes i.R. länger als 3

[Der_Unwissende]

Zitat von Olli:

...(unter der Annahme alle Anweisungen kosten gleichviel Zeit).

Was ja an sich schon eine viel zu allgemeine Annahme ist. Einfaches Beispiel das mir einfallen würde wäre die Multiplikation von Matrizen. Hat man mehrere Matrizen, die miteinander multipliziert werden, so würde man naiv einfach die in der Reihenfolge Multiplizieren, in der sie übergeben werden. Jetzt ist die Multiplikation aber Assoziativ, man kann also hier (bei geeigneten Matrizen) die Reihenfolge der Multiplikation verändern, also einfach einzelne Produkte vor anderen bilden. Das möchte ich jetzt gar nicht weiter ausführen, denke alzaimar und Olli kennen die unterschiedliche Laufzeit (andere natürlich auch!, die die sie nicht kennen finden sicher schnell was in der Theoretischen Informatik dazu). Jedenfalls wird hier vor sortiert, indem die Dimensionen der Matrizen verglichen wird (mehr Anweisungen als die naive Multiplikation), da sich aber die Anzahl von Multiplikationen und Additionen verändert, kann somit eine Optimierung vom Programmierer erreicht werden.

Wichtig ist es natürlich zu beachten, dass eben nicht jeder Befehl gleich lange dauert (@Olli ich denke das ist Dir schon klar!). Nur kostet jede Division doch immer noch >> mehr als eine einfache Addition.

Aber klar, unter der Einfachen Annahme, dass man eine unterschiedliche Anzahl von gleich teuren Befehlen hat, werden natürlich die geringeren Kosten günstiger sein

[alzaimar]

Unterm Strich bleibt eine (banale Erkenntnis):

Das Verfahren ist wichtig, nicht die Sprache.

In der untersten Ebene sind die optimierenden Compiler/Sprachen besser eeignet, also Hochsprachen.

Bernhard Geyer hat schon treffend angemerkt, das auch bei hochoptimierten Elops (Pos, StrCopy etc.) eine normale Anwendung nur um ein paar Prozente profitiert.

[Olli]

Zitat von Der_Unwissende:

Wichtig ist es natürlich zu beachten, dass eben nicht jeder Befehl gleich lange dauert (@Olli ich denke das ist Dir schon klar!). Nur kostet jede Division doch immer noch >> mehr als eine einfache Addition.

Nunja, da ich beruflich programmiere und Reverse Engineering betreibe ... jupp, ist mir klar. Ich wollte dies nur als theoretische Annahme einführen damit die Komplexität nicht unnötig ansteigt. Das unterscheidet bekanntlich Modelle von der realen Welt

Das Beispiel von überladenen Operatoren und Matrizen (Vektor und/oder Skalarprodukt) ist hier ein gutes Beispiel. Der Code ist intuitiv und supergut lesbar, aber die Operatoren selber sind auch zu implementieren. Sie müssen allerdings nicht für den Programmierer sichtbar sein. Ergo kann eine solche simple Zeile HLL-Code gut und gern ein kleines C-Programm in der Komplexität übertreffen ohne mehr Zeilen zu haben.

Zitat von alzaimar:

Delphi-Quellcode:

For i:=1 to length (Haystack)-Length(Needle)+1 do
  For j:=1 to Length (Needle) do
    If Haystack[i+j-1] = Needle[j] Then 
      Found := True;

Wo ist die Abbruchbedingung? (Scherz!)

Zitat von alzaimar:

Code:

void buildSuffixAutomaton(char *x, int m, Graph aut) {
   int i, art, init, last, p, q, r;
   char c;
  
   init = getInitial(aut);
   art = newVertex(aut);
   setSuffixLink(aut, init, art);
   last = init;
   for (i = 0; i < m; ++i) {
      c = x[i];
      p = last;
      q = newVertex(aut);
      setLength(aut, q, getLength(aut, p) + 1);
      setPosition(aut, q, getPosition(aut, p) + 1);
      while (p != init &amp;&amp;
             getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, p, c, q);
         setShift(aut, p, c, getPosition(aut, q) -
                             getPosition(aut, p) - 1);
         p = getSuffixLink(aut, p);
      }
      if (getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, init, c, q);
         setShift(aut, init, c,
                  getPosition(aut, q) -
                  getPosition(aut, init) - 1);
         setSuffixLink(aut, q, init);
      }
      else
         if (getLength(aut, p) + 1 ==
             getLength(aut, getTarget(aut, p, c)))
            setSuffixLink(aut, q, getTarget(aut, p, c));
         else {
            r = newVertex(aut);
            copyVertex(aut, r, getTarget(aut, p, c));
            setLength(aut, r, getLength(aut, p) + 1);
            setSuffixLink(aut, getTarget(aut, p, c), r);
            setSuffixLink(aut, q, r);
            while (p != art &amp;&amp;
                   getLength(aut, getTarget(aut, p, c)) >=
                   getLength(aut, r)) {
               setShift(aut, p, c,
                        getPosition(aut,
                                    getTarget(aut, p, c)) -
                        getPosition(aut, p) - 1);
               setTarget(aut, p, c, r);
               p = getSuffixLink(aut, p);
            }
         }
      last = q;
   }
   setTerminal(aut, last);
   while (last != init) {
      last = getSuffixLink(aut, last);
      setTerminal(aut, last);
   }
}

Igittigitt. Variablen nicht initialisiert. Variablen außerhalb des allernötigsten Bereichs deklariert *brrr*

Nee, aber mal ernst, uns ist allen klar warum sowas schneller geht. Und das ist nicht wegen der fehlenden Abbruchbedingung ...

Zitat von alzaimar:

Egal: Natürlich benötigen 10000 Op-codes i.R. länger als 3

Jupp, mein Punkt war halt, daß man bei einer Schleife ja die Instruktionen innerhalb der Schleife pro Durchlauf einmal ausführen muß. Ergo dürfte die Binärdatei kleiner sein als bei deinem Algo, jedoch werden netto mehr Instruktionen vom Prozessor ausgeführt.

Ich muß echt an meinem Ausdruck feilen. Zu lange im Ausland

Gruß aus dem (nicht vom Internet abgeschnittenen) Reykjavik,

[alzaimar]

Zitat von Olli:

Zitat von alzaimar:

Code:

void buildSuffixAutomaton(char *x, int m, Graph aut) ...

Igittigitt. Variablen nicht initialisiert. Variablen außerhalb des allernötigsten Bereichs deklariert *brrr*

Nicht so schnell schießen (welche Variablen sind denn nicht initialisiert?), lieber nochmals den Code checken oder direkt bei Charras & Lecroq beschweren.

[Olli]

Zitat von alzaimar:

Zitat von Olli:

Zitat von alzaimar:

Code:

void buildSuffixAutomaton(char *x, int m, Graph aut) ...

Igittigitt. Variablen nicht initialisiert. Variablen außerhalb des allernötigsten Bereichs deklariert *brrr*

Nicht so schnell schießen (welche Variablen sind denn nicht initialisiert?), lieber nochmals den Code checken oder direkt bei Charras & Lecroq beschweren.

Also, ich initialisiere Variablen wenn möglich immer direkt bei der Deklaration und deklariere sie so spät wie möglich (i.e. so kurz wie möglich vor der ersten Benutzung). Das wird von C++ und C99 unterstützt.

Diese Methode hat mehrere Vorteile:
1. Wenn es sich bei der Variablen um ein Stackobjekt handelt, hast du den Aufwand des ctor-Aufrufs erst ab der Zeile mit der Deklaration&Initialisierung. Bei komplexen Objekten kann das einen Unterschied machen.
2. Variablen haben immer einen Standardwert.
3. Baut man zuvor eine Verzweigung (manche benutzen gern goto *würg*) ein, kann nicht hinter der Verzweigung die Variable benutzt werden (wenn sie nur im nächstnötigen Scope liegt) oder zumindest nicht uninitialisiert benutzt werden.

Das sind sozusagen kostenlose Codeverbesserungen die als "Stilmittel" automatisch bestimmte durchaus gängige Fehler vermeiden. Aber keine Angst, ich kenne auch Code der sich partout nicht dran hält und Menschen die noch partout C92 programmieren wollen

War also nicht so ernst gemeint wie du es scheinbar aufgefaßt hast

[alzaimar]

Zitat von Olli:

... von C++ und C99 ... die noch partout C92 programmieren wollen ...

Ich kenn nur C64

Ach, und Code auf Seiten von Universitäten sind meist interessant und selten schnell ('Optimizing is beyond the scope of this article'). Die haben's eben nicht drauf.