Einfluss verschiedener Blockgrößen/Variablentypen

Hallo zusammen,

das Informatik-Forum geht in den Archivmodus, genaue Informationen kann man der entsprechenden Ankündigung entnehmen. Als Dankeschön für die Treue bekommt man von uns einen Gutscheincode (informatikforum30) womit man bei netzliving.de 30% auf das erste Jahr sparen kann. (Genaue Infos sind ebenfalls in der Ankündigung)

Vielen Dank für die Treue und das Verständnis!

    Hallo Forum!
    Ich habe einen Algorithmus der verschiedene Bitoperationen (shift, XOR, AND) gebraucht. Es muss eine Bitmatrix bearbeitet werden. Dazu werden die einzelnen Bits in Blöcke gepackt. Ich habe verschiedene Blockgrößen getestet (UINT8, 16, 32, 64). Es ergab sich folgende Reihenfolge was die Schnelligkeit des Algorithmus betrifft:

    UINT32 - am schnellsten
    UINT16
    UINT64
    UINT8 - am langsamsten

    Ich habe einen 32Bit Prozessor. Damit kann ich mir noch erklären weshalb der 32 Bit-Algorithmus am schnellsten arbeitet. Die Blöcke werden "so wie sie sind" vom Prozessor bearbeitet. Aber wie kann ich mir den Rest der Reihenfolge erklären? Was würde der Prozessor machen, wenn er z.B. mit 16-Bit-Speicherzellen (bzw. variablen) arbeiten muss?
    Beim UINT64 könnte ich mir noch vorstellen, dass der Prozessor den Block ersteinmal in zwei Hälften teilt und das kostet dementsprechend Zeit.

    Ich bin noch Schüler und habe leider noch keine Detailkenntnisse was solche spezifischen Sachen angeht. Vielleicht gibt es ja welche unter euch, die sich da auskennen?

    stell dir vor du hast einen sandhaufen (deine daten), eine schaufel (deine variablenbreite) und einen mischmaschine (deine CPU). pro mischvorgang braucht deine CPU eben gewisse zyklen die _fix_ sind, die mischmaschine von mir aus 5 minuten.
    jetzt ueberleg dir mit welcher schaufel du die mischmaschine am besten auslasten kannst. zb 8bit breite schaufel. du schaufelst von deinem sandhaufen nur sehr wenig weg, trotzdem brauch die mischmaschine aber 5 minuten pro vorgang. wenn du gleich 32 bit rein schaufelst, lastest du deine mischmaschine sehr gut aus, besser als zb mit 16 bit. und fuer 64 bit ist eben deine mischmaschine zu klein ;)

    Danke, diese Verbildlichung ist echt genial!!!
    Jetzt muss ich nur noch herausfinden was die CPU genau mit 64 Bit macht(um herauszufinden warum dies schneller ist als UINT8). Kann man dabei von irgendeiner konstanten Zeit ausgehen die benötigt wird um eine 64-Bit-Schaufel so vorzubereiten, dass daraus zwei 32-Bit schaufeln werden? Und wenn ja, wie macht das die CPU im Detail?

    Ich habe da noch eine kleine Frage. Ich bin gerade dabei die Operationen in dem Algorithmus auszuzählen. So langsam verstehe ich auch, was eine "größere Schaufel" rechnerisch bedeutet. Jedenfalls habe ich XOR, AND, OR und SHIFT als Bitoperationen. Dann gibt es Multiplikationen, Divisionen und Additionen. Dabei weiß ich nicht wie ich Vergleiche zählen soll (also z.b. A == B oder A > b)? Also wie lange dauern Vergleiche und fallen diese überhaupt ins Gewicht? Und gilt für Wertzuweisungen das gleiche(z.b. A = B;)? Wie schnell verhalten sind Wertzuweisungen?
    Ich nehme mal an Divisionen dauern am längsten. Danach kommen Multiplikationen und schließlich Additionen. Die Bitoperationen XOR, AND, OR sind wohl etwa gleichlang und relativ fix. SHIFT soll angeblich am schnellsten sein.
    Ich habe mir mal ein Experiment ausgedacht, bei dem ich die Operationen etwa vergleichen könnte.
    Z.B. messe ich die Zeit für
    for(int i = 0; i < grosseZahl; i++)
    a = OPERATION b;

    Dann dividiere ich durch "grosseZahl" und erhalte etwa die Zeit für eine Operationen. Damit ließen sich doch die Operationen fair vergleichen, oder?

    Zitat von Blubberblase

    Und dann weiß ich nicht wie ich Vergleiche zählen soll (also z.b. A == B oder A > b)? Also wie lange dauern Vergleiche und fallen diese überhaupt ins Gewicht?


    Solche Vergleiche sind im Prinzip Subtraktionen, wobei nur das Vorzeichen des Ergebnisses betrachtet wird.

    Zitat

    Ich nehme mal an Divisionen dauern am längsten. Danach kommen Multiplikationen und schließlich Additionen.


    Plausibel.

    Zitat

    Die Bitoperationen XOR, AND, OR sind wohl etwa gleichlang und relativ fix. SHIFT soll angeblich am schnellsten sein.


    Shift sollte eher komplexer sein als die anderen Bitoperationen. Shift ist schneller als Multiplikation und Division mit konstanten Zweierpotenzen und wird da (überflüssigerweise) manchmal als Ersatz empfohlen, vielleicht meinst du das.

    Zitat

    Ich habe mir mal ein Experiment ausgedacht, bei dem ich die Operationen etwa vergleichen könnte.
    Z.B. messe ich die Zeit für
    for(int i = 0; i < grosseZahl; i++)
    a = OPERATION b;


    Neben der Operation, die du da messen willst, hast du auch noch gleich viele Vergleiche, Sprünge und Erhöhungen von i; das stört alles. Besser wäre sowas:

    Code
    for (int i = 0; i < N; i++)
{
    a1 = OP b1;
    a2 = OP b2;
    ...
    an = OP bn;
}


    Je mehr verschiedene ai und bi, d.h. je mehr Wiederholungen der Operation innerhalb des Schleifenkörpers, umso genauer sollte die Messung sein, da die anderen Operationen weniger ins Gewicht fallen. [Edit: Das geht aber nur auf Prozessoren mit vielen Registern gut, sonst mißt man Speicher- und Cache-Effekte mit.] Und dann sollte man noch darauf achten, daß der Compiler die Schleife nicht optimiert.

    Darf man fragen, warum du das alles wissen willst? Falls die Antwort ist, um schnelleren Code zu schreiben: Falsche Antwort.

    Blubberblase:
    so vom gefuehl her hast du schon recht, eine division ist zum beispiel in HW recht kostspielig. sonst kommt es sehr auf die architektur an was wirklich vor geht. moderne CPUs rechnen einen ganzen berg an instruktionen in einem zyklus. dann muss man noch aufpassen was der compiler aus deinem programm wirklich macht. "denkt der compiler" oder "denkt die HW"? und das ganze zusammenspiel, dann noch mit caches, ist ein eigenes aufgabengebiet fuer sich. die WCET (worst case execution time) zu bestimmen ist bei modernen architekturen nicht mehr so einfach. stichwort "caches" und "pipelining". wenn du interesse daran hast, dann kann ich dir folgende folien ans herz legen, ich fand die VO seinerzeit recht lehrreich:
    http://ti.tuwien.ac.at/rts/teaching/courses/cavo/

    beim stoppen musst du aufpassen. wenn du sozusagen die zeit nimmst wenn das prog startet und dann wenn es endet, dann ist den aussagen nicht umbedingt zu trauen. was wenn zum beispiel ein prozess mit hoeherer prioritaet daher kommt und dein test im scheduler verhungert?

    Danke für die hilfreichen Antworten!
    Die Folien werde ich mir alle mal anschauen. Ich wollte ursprünglich den Algorithmus schneller machen, aber das hat sich als schwierig erwiesen. Es handelt sich um einen Gaussalgorithmus im der Gruppe GF2. Urpsprünglich wollte ich die Komplexität senken mit einer Methode von Strassen. Sie basiert darauf, dass man mehr Additionen und weniger Multiplikationen benötigt. Allerdings nützt das in der Gruppe GF2 recht wenig. Denn XOR und AND Operationen nehmen sich ja nicht viel und dementsprechend würde das keine Beschleunigung bringen...