Bruteforcer - Geschwindigkeitsoptimierung in C++

A

AceKiller73

0
Hi,
ich beschäftige mich zur Zeit mit der Programmierung eines BruteForcers.
Diesbezüglich will ich lernen, wie C++ Code auf Geschwindigkeit optimiert wird.
Allerdings habe ich nur wenig Ahnung, welche Anweisungen in C++ z.B. viel Zeit und welche wenig brauchen.
Mir ist klar, dass z.B. Aufrufe von Methoden, zB der STL einiges an Zeit kosten können und das man möglichlist lowlevel (im sinne von Benutzung weniger fertiger Klassen) programmieren sollte.

Ich habe folgenden Code im Internet gefunden:
Code: 
public void GenPasswords ()
    {
      char[] code = new char[10]; // Einmal mit maximal grösse anlegen

      for (int TestSize = 1 ; TestSize < 11 ; TestSize++)
      {
        for (int Index = 0 ; Index < TestSize ; Index++)
          code[Index] = 'a';

        do
        {
          TestPassword (code, TestSize);
        } while (OneUp (code, TestSize, 0));
      }
    }

    public bool OneUp (char[] code, int maxsize, int pos)
    {
      if (pos == maxsize)
        return false;

      code[pos]++;

      if (code[pos] <= 'z')
        return true;

      code[pos] = 'a';
     
      return OneUp (code, pos+1);
    }
Der Vorteil dieses Algorithmus ist seine Variablität. Er mit jeder gewünschten Länge von Zeichen umgehen.

Wäre es (für feste Zeichenlängen) besser einfach alles in mehrere Schleifen zu packen?
Code: 
int main(void)
 {
  for (int a = 0;a <= 99;a++)
   for(int b = 0;b <= 99;b++)  
     std::cout << a << b << std::endl;

  return 0;    
 }
Natürlich müsste man dann mehrere Funktionen für unterschiedliche Längen proggen, aber wenn man dadurch eine Geschwindigkeitsvorteil hat wäre das doch von Nutzen?

Schließlich müssen beim oberen Beispiel immer char[] code, int maxsize, int pos usw im Speicher reserviert und beschrieben werden...
Das kostet doch Zeit oder?

Wäre nett wenn jemand das kurz erörtern könnte.

MFG
Ace
 
Hallo,
hab mir deinen Code nicht angeguckt, hier ab paar Tipps:

1. Es gibt nicht schlimmeres als Sprünge. Funktionsaufrufe unbedingt vermeiden und möglichst viel mit dem precompiler arbeiten.
Ein einziger Sprung kann die Performance extrem ruinieren.
Dazu gehören auch if-Anweisungen, im kritischen Part sollten keine if-Anweisungen auftauchen.
Auch Schleifen, bedingt durch den Sprung, sind extrem langsam. Deswegen sollte man Schleifen entrollen, d.h. entsprechend oft seinen Programmcode hinschreiben.

z.B. würde:
Code: 
for (int a = 0;a <= 99;a++)
   for(int b = 0;b <= 99;b++)  
       funk(a,b);

Viel schneller so aussehen:
funk(0,0);
funk(0,1);
funk(0,2);
...
funk(99,99);

Da das bei 99*99 per Hand nicht geht, kann man dies maschinell machen. Evt. macht dies auch der Compiler für dich (siehe Punkt 2).

Sonst kann man auch den Schleifenrumpf vergrößern:

Code: 
for (int a = 0;a <= 99;a++)
   for(int b = 0;b <= 99;b+=11)  {
       funk(a,b);
       funk(a,b+1);
       funk(a,b+2);
       ...
      funk(a,b+10);
   }

Hier gab es bereits mal das Thema, finde es aber gerade nicht wieder. Ich glaube CDW hatte damals ganz nette Artikel dazu hier gelinkt. Vielleicht findet ja jemand den Thread

2. Sofern du gcc vernwendest, nutze den Parameter -O3. Dieser wirkt ware Wunder.
GCC optimiert dir dann sehr viel, z.B. werden Funktionsaufrufe emlimiert und ähnliches.
So kann man sich z.B. von 400k MD5 Hashs/Sek auf 3,5 Mio MD5 Hashs/Sek steigern, mit dem selben Code (der schon ordentlich optimiert war).
 
Erstmal vielen Dank. Du hast mir schon sehr geholfen.

Ja ich benutze gcc und ich ich glaube diese Option wird mir schon deutlich weiterhelfen.

Ich habe noch ein paar Fragen:

Sollte man immer wenn möglich Konstanten (const - Objekte) benutzen? Sind diese irgendwie schneller?

Ist das "Anlegen" von Variablen zur Laufzeit sinnvoll oder sollte man besser alle Variablen außerhalb von Funktionen oder Schleifen deklarieren?

Bringt inline Assembler Geschwindigkeitsvorteile oder wird der Code schon durch den Compiler optimiert?

In welcher Sprache sind die schnellsten BruteForcer geschrieben? Gibt es dazu Code?

MFG
Ace

Edit: Danke CDW für den Link... Werde ich auch mal durchstöbern
 
Original von Elderan
1. Es gibt nicht schlimmeres als Sprünge. Funktionsaufrufe unbedingt vermeiden und möglichst viel mit dem precompiler arbeiten.
Zum Vergrößern anklicken....

Wenn man inline verwendet, bläst sich die Anwendung dann zwar ziemlich auf, ist sie dann aber auch wesentlich schneller?
 
Hallo,
Original von benediktibk
Original von Elderan
1. Es gibt nicht schlimmeres als Sprünge. Funktionsaufrufe unbedingt vermeiden und möglichst viel mit dem precompiler arbeiten.
Zum Vergrößern anklicken....

Wenn man inline verwendet, bläst sich die Anwendung dann zwar ziemlich auf, ist sie dann aber auch wesentlich schneller?
Zum Vergrößern anklicken....
ja deutlich.

Wie gesagt, es gibt nicht schlimmeres als Sprünge.

Dies hängt mit der Architektur der CPU zusammen. Moderne CPUs verwenden sogenanntes Pipelining, d.h., es werden mehrere Befehle gleichzeitig abgearbeitet (ähnlich wie bei der Essensausgabe, Person 1 tut auf deinen Teller Kartoffeln, gibt den Teller weiter, Person 2 haut dir ein Stück Fleisch trauf, Person 3 macht dann das Gemüse auf den Teller, so können 3 Personen gleichzeitig bedient werden).

Dazu unterteilt die CPU einen Maschinenbefehl in mehrere Einheiten/Stufen, z.B. Instruction fetch, decoding, Execution und Write Back (bei echten CPUs vermutlich noch deutlich mehr).
Pro Takt wird dann einmal diese Stufe abgearbeitet und der Befehl in die nächste Stufe übergeben.
Das bedeutet also, der Befehle 2, 3, 4 usw. werden schon ausgeführt, bevor der Befehle 1 überhaupt abgearbeitet ist.
Da so eine CPU aber nicht in den Zukunft gucken kann, werden die Befehle einfach nacheinander geladen, also es wird einfach die Befehle 1-4 in die CPU geladen.

Das Problem ist nun, wenn der Befehl 1 nun ein Sprung ist, so wird dies erst in der obigen Pipeline im Execution-Schritt festgestellt, in der Pipeline befinden sich aber schon Befehl 2 und 3.
Da aber Befehl 1 nun ein Sprung war, dürfen Befehl 2 und 3 nicht mehr ausgeführt werden. Deswegen muss die gesamte Pipeline geleert werden (Pipeline-Flush) und neu initialisiert werden, was natürlich unheimlich viel Zeit braucht.

Wenn man also eine entrollte Schleife hat, so kann die Pipeline immer schön durchlaufen und ihre ganze Mächtigkeit ausspielen.
Verwendet man stattdessen Schleifen, dann können evt. 2 Befehle in der Pipeline ausgeführt werden, dann kommt der Sprung, die gesamte Pipeline muss geleert werden und neu initialisiert werden, was sehr viel Zeit braucht.


Es kommt aber noch schlimmer: Eine CPU ist extrem viel schneller getaktet als der Datenspeicher, so dass ein Zugriff auf den Hauptspeicher Ewigkeiten braucht.
Deswegen liest die CPU das abzuarbeitende Programm immer in Blöcken ein, 'sende mir die Daten mit der Speicheradresse von 13200 bis 13400', so dass eben keine Verzögerung für den Zugriff auf den Hauptspeicher entsteht.

Steht aber nun aber an der Speicheradresse 13206 ein Sprung auf den Speicherbereich 14040, so muss die CPU wieder auf den Hauptspeicher zugreifen, was unglaublich lange dauert.

Bei Schleifen ist dies nicht so das große Problem, da diese recht kompakt sind und oft in einem Rutsch ausgelesen werden, verwendet man aber Funktionsaufrufe kann sowas eben passieren.
Hat man z.B. in der Schleife beispielsweise 5 Funktionsaufrufe, kann es gut angehen, dass die CPU pro Durchlauf mehrere male auf den Hauptspeicher zugreifen muss (mit dem Cache wird viel gutgemacht).

Deswegen sollte man auch immer auf den Precompiler zurückgreifen und möglichst keine Funktionen aufrufen (sofern die nicht eh weg optimiert werden vom compiler)

Hoffe das hilft weiter.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben