c't-Puzzle gelöst in (33 Zeilen) C

Dieses kleine C-Programm löst das Puzzle aus dem Artikel "Zusammengewürfelt, Puzzles mit dem Computer lösen" von Harald Bögeholz, c't 7/2003, Seite 230 (hier ist der Artikel, siehe auch www.ctpuzzle.de).

Quelltext | Anmerkungen | Optimierungen | Laufzeiten | Zukunft | Dateien | Kontakt

Änderungen / Ergänzungen

• 1. Mai 2003: So, der Einsendeschluss ist vorbei, daher habe ich eine neue Seite eingerichtet und meine Wettbewerbsversion zum Download bereitgestellt. Ansehen kann es sich jeder hier.
• 26. April 2003: Da sich mein Visual-C++ Compiler aus mir nicht erschliessbaren Gründen weigert, eine gut optimierte Version des Puzzle-Programms zu erzeugen, habe ich auf eine von Bruno Wöhrer zur Verfügung gestellten Version zurückgegriffen. Die Zeiten für die mir im Moment zur Verfügung stehenden Systeme habe ich geändert, die anderen Zeiten für die Visual-C++ Versionen entfernt, und die ctpuzzle_msc.exe Datei aktualisiert.
• 25. April 2003: Bruno Wöhrer hat mir neben Laufzeiten für seinen Celeron 1200 MHz auch die Laufzeiten auf einer SGI Indigo2 (MIPS R10000, 195 MHz) sowie einer IBM RS/6000 (PowerPC, 375 MHz) zur Verfügung gestellt. Ausserdem wiess er darauf hin, dass er mit Microsoft Visual C++ wesentlich bessere Ergebnisse erzielt; wahrscheinlich sind bei meiner Version die Compiler-Optimierungen nicht aktiviert. Ich werde mir den Microsoft-Compiler also nochmal vornehmen...
• 22. April 2003: In der heute erscheinenden c't sind Laufzeiten für das c't-Puzzle-Programm für den Intel Xeon 2,8 GHz und den Opteron Model 244 (Hammer) aufgeführt, mal unauffällig auf Seite 111 rechts oben hinschielen. Die Werte sind natürlich ab sofort auch in den Tabellen, wo sich mit dem Opteron jetzt schon vier echte 64-Bit-Prozessoren versammelt haben. Danke Harald Bögeholz!
• 19. April 2003: Thomas Richter hat das Programm auf einer "Sun Fire 480R, 64 bit, Sparc Ultra III Cu, 900 Mhz" übersetzt, und zwar einmal mit 64-Bit-Befehlen und einmal ohne, was einen interessanten Vergleich ermöglicht. Ausserdem fällt auf, dass die Sun das Problem sehr effizient lösen kann und mit Abstand am wenigsten Takte pro Versuch benötigt; ich musste sogar die Balkenlänge anpassen, aber zum Glück wird die Seite jetzt per PHP erzeugt, also war das kein Problem mehr.
• 19. April 2003: Achim Weber hat auf seinem Athlon XP 2600+ alle Versionen von meiner Seite mal durchprobiert, die Ergebnisse stehen in den Tabellen. Dass der höher getaktete Ahtlon XP 2700+ weniger Takte pro Versuch braucht liegt wahrscheinlich an unterschiedlichen Speicher-Timings?
• 11. April 2003: Hans-Bernhard Broeker hat das Programm unter Digital Unix 4.0 auf einer Alpha "MHz-Zahl leider nicht parat, sollte aber um die 500 liegen" laufen lassen, also auf einer 64-Bit CPU. Das Ergebnis ist zwar keine Katastrophe, aber "64 Bit == doppelt so schnell wie 32 Bit" stimmt hier sicherlich nicht; hatte ich auch nicht erwartet, aber vielleicht ein bisschen mehr Durchsatz...
  Nachtrag: Die Alpha hat nur 333 MHz, da sieht es doch schon wieder freundlicher aus für die 64-Bit-Welt, und es entspricht auch etwa meinen Vorstellungen. Ich habe zum bessern Vergleich der unterschiedlich getakteten Prozessoren auch noch eine Zeile mit Takten pro gelegtem Teil eingefügt, hier sieht die Alpha wesentlich besser aus als der P4, jetzt müîte diese nur noch etwas mehr Takt verkraften... achja, der Compiler auf der Alpha war übrigens DEC C V5.6-071, vielen Dank für die nachträgliche Information! Alle Informationen jetzt in 2 Tabellen
• 11. April 2003: Die von Johannes Overmann verwendeten gcc-Optionen -O2 -fomit-frame-pointer -mcpu=pentiumpro -march=pentiumpro scheinen gerade auf Durons/Athlons einiges zu bringen, ich habe einige Zeiten in der Tabelle nach unten korrigieren können. Lustigerweise ist die gcc-Version auf dem Morgan-Duron jetzt ganz knapp schneller als die Intel-Compiler Version, aber das muss ich wohl nochmal in Ruhe überprüfen.
• 11. April 2003: Johannes Overmann hat mir die Zeit für seinen Athlon T-Bird 700 MHz zugemailt. Vielen Dank dafür. Ausserdem habe ich gemerkt, dass mein Duron ein 850er ist, kein 800er, und ich habe noch einige Laufzeiten für unterschiedliche Systeme, die hier noch so rumstehen, hinzugefügt. Siehe Tabelle
• 10. April 2003: Mein Mitbewohner Christoph B. hat es mal auf seinem Pentium IV 2.4 GHz auf der Arbeit laufen lassen, auch der ist langsamer als der Athlon-XP, obwohl er physikalisch 250 MHz höher getaktet ist, und man sieht des weiteren, dass 20% mehr Takt auch (fast) 20% mehr Leistung entsprechen, wie nicht anders zu erwarten. Siehe Tabelle
• 10. April 2003: Jemand hat einen Athlon XP 2700+ ! Danke Chess77 / Eiko, läuft unter 10 Minuten, siehe Tabelle
• 10. April 2003: Florian Pigorsch hat mir die Laufzeit für seinen Athlon MP 1.2 GHz zugemailt, der ist unter gcc genau so schnell wie der P4 2 GHz! Siehe Laufzeiten. Hat denn niemand einen Athlon XP 2700+ oder sowas?
• 10. April 2003: nach Hinweis von "puzzled" im Heiseforum die Compileroptionen für den gcc geändert, ist dadurch um 1:12 min schneller geworden. Tabelle und übersetzte Programmversion aktualisiert.
• 9. April 2003: .c - Quelltext-Datei und angezeigte Version waren nicht identisch, angezeigte Version geändert (war ja klar, dass sowas passieren muss...)
• 9. April 2003: Erste Version der Seite

Nochmal vielen Dank an alle, die sich die Mühe gemacht haben, das c't-puzzle-Programm auf Ihrer Hardware zu testen und mir die Ergebnisse zu schicken!

Quelltext

Hier ist erstmal der Quelltext (als .c-Datei oder als ausführbares Programm: siehe Dateien)

01: #include <stdio.h>
02: #include <stdlib.h>
03: #include <time.h>
04: #define C if
05: #define T void
06: #define P NULL
07: #define U while
08: #define Z break
09: #define S return
10: #define L typedef
11: #define E clock()
12: #define _ (double)
13: #define W continue
14: #define X(a,b) for(a=0;a<b;a++)
15: L int I;L long long B;I R[]={203,158,1625,151,214,91,4123,186,36867,587,94,601}
16: ,K,g[9],M[4][4];B*d[60],*k[12],e[12][1440],f;I A(I x,I y,I z){C(x<3&&y<4&&z<5&&
17: x>=0&&y>=0&&z>=0)S x+y*3+z*3*4;S-1;}B Y(I*v){I b;b=A(v[0],v[1],v[2]);S b!=-1?(B
18: )1<<b:0;}T G(I*v,I x,I y,I z,I u){v[0]=x;v[1]=y;v[2]=z;v[3]=u;}T H(I*v,I*w){I i
19: ;X(i,4)v[i]=w[i];}B J(B p,I a,I b,I c){I x,y,z,v[4];B u;u=0;X(x,3)X(y,4)X(z,5){
20: G(v,x,y,z,1);C(p&Y(v)){G(v,a?2-x:x,b?3-y:y,c?4-z:z,1);u|=Y(v);}}S u;}T V(I N){I
21: x,y,z,i,j,v[4],w[4];B p,s=0;X(x,3)X(y,4)X(z,2){C(!(1<<(x+y*3+z*12)&R[N]))W;G(v,
22: x,y,z,1);X(i,4){w[i]=0;X(j,4)w[i]+=v[j]*M[j][i];}p=Y(w);C(!p)S;s|=p;}i=0;U(p=e[
23: N][i]){C(p==s)Z;C(N==6&&(p==J(s,1,1,0)||p==J(s,1,0,1)||p==J(s,0,1,1))){C((s&-s)
24: >(p&-p))e[N][i]=s;Z;}i++;}C(!p){e[N][i++]=s;e[N][i]=0;}}T Q(B F,I w,B mi){B*m;I
25: N,n;U(F&mi){mi<<=1;w++;}C(w==60){C(!(++K%1000)){putchar('.');fflush(stdout);}S;
26: }m=d[w];U(*m){N=*m>>16;n=*m++&8191;C(k[N]){m+=n;W;}U(n--){C(!(*m&F)){k[N]=m;f++
27: ;Q(F|*m,w,mi);}m++;}k[N]=P;}}T O(T){I i,w,N,l,n,o,q,r;B*t,*h,p;g[2]=-1;g[5]=1;X
28: (N,12){X(l,6){H(M[0],&g[5-l]);X(n,6){H(M[1],&g[5-n]);C(l%3==n%3)W;X(o,3){q=(o+1
29: )%3;r=(o+2)%3;M[2][o]=M[0][q]*M[1][r]-M[0][r]*M[1][q];}X(o,3)X(q,4)X(r,5){G(M[3
30: ],o,q,r,1);V(N);}}}}X(w,60){t=d[w]=(B*)malloc(1500*sizeof(B));X(N,12){h=P;i=0;U
31: (p=e[N][i++]){C(!(((B)1<<w)&p))W;C((((B)1<<w)-1)&p)W;C(!h)h=t++;*t++=p;}C(h)*h=
32: (N<<16)|(t-h-1);}*t++=0;}Q(0,0,1);}int main(T){clock_t s=E;O();
33: printf("\n%d Loesungen, %.2fs, %.0f Tests\n",K,_(E-s)/CLOCKS_PER_SEC,_ f);S 0;}

Anmerkungen

Ich habe den Quelltext mit folgenden Compilern erfolgreich übersetzt:

• gcc version 3.2 20020927 (prerelease) unter Cygwin/Windows
• Intel(R) C++ Compiler for 32-bit applications, Version 7.0 Build 20021018Z
• Microsoft (R) 32-bit C/C++ Standard Compiler Version 12.00.8168 for 80x86 wenn man vorher long long durch __int64 ersetzt
• Logiciels/Informatique lcc-win32 version 3.8. Compilation date: Jan 16 2003 12:39:15

Wenn ich nicht irgendwo geschlampt habe, sollte es so unter ziemlich jedem C-Compiler übersetzbar sein, nur der Typ long long muî mindestens 64 Bit haben (und überhaupt vorhanden sein). Für einen vergleich der verschiedenen Compiler vergleiche die Tabelle Laufzeiten. Wenn jemand durch bessere Compiler-Switches was schnelleres hinbekommt, bitte ich um eine kurze Nachricht. Achja, mit dem Auge des liebenden Vaters kann man sicherlich auch über die ein oder andere Compiler-Warnung hinwegsehen, davon produziert das Programm evtl. doch einige...

Die Programmausgabe ist minimal, nach jeweils gefundenen 1000 Lösungen wird ein Punkt auf dem Bildschirm ausgegeben, und nachdem auf diese Weise einige Zeit vergangen ist (eine ungefähre Schätzung für das eigene System möge man der untenstehenden Tabelle entnehmen) und etwas mehr als 5 Zeilen auf einer 80 Zeichen breiten Konsole vollgeschrieben sind, wird die Anzahl gefundener Lösungen und benötigte Zeit in Sekunden ausgegeben, sowie die Anzahl der Aufrufe der rekursiven Lösungsfunktion.

Um die Sache nicht zu einfach zu machen, habe ich den Quelltext in Anlehnung an den "International Obfuscated C Code Contest" (www.ioccc.org) optimiert; wenn man ihn durch den Preprocessor laufen läît und anschlieîen vielleicht noch mit indent behandelt, ist er womöglich einigermassen verständlich, eine Garantie gebe ich darauf aber nicht...

Gut zwei Drittel des Quelltextes befassen sich übrigens nur mit der Erzeugung der möglichen Positionen der Steine, allerdings habe ich gerade diesen Teil sehr stark obfuscated. Wer sich fragt, wo denn überhaupt die Form der Steine im Quelltext auftaucht, möge mal das Array R etwas genauer unter die Lupe nehmen, dort sind die einzelnen Steine jeweils als 4 * 3 * 2 Bitfeld gespeichert.

Und ja, das ganze sieht wirklich so charmant aus wie Lisp ohne Klammern und auch ich stelle mir unter gutem Code etwas anderes vor (obwohl der Microsoft-Mitarbeiter, dem ich das vorgestern gezeigt habe, meinte, ich sollte unbedingt mal auf ein Vorstellungsgespräch vorbeikommen...), aber hier erfüllt es seinen Zweck.

Optimierungen

Da es mir vor allem auf die Länge des Quelltextes ankam, habe ich auf umfangreiche Optimierungen verzichtet und habe nur die Datenstrukturen etwas optimiert; dass meine "Laborversion" noch um einiges schneller ist, versteht sich von selbst :).

Die Laufzeit hängt sehr stark von zwei Faktoren ab, die sich in der Anzahl der Aufrufe der rekursiven Lösungsfunktion auswirken und somit der Anzahl der versuchsweise gesetzten Teile entsprechen.

Der erste Faktor ist Reihenfolge, in der versucht wird, den Quader zu füllen. -ndert man diese, kann sich die Geschwindigkeit ausgehend von dem in diesem Programm verwendeten Ansatz um mehrere Gröîenordnungen verschlechtern. Aus 20 Minuten werden dann schnell über 10 Stunden, da bei einer ungünstigen Strategie wesentlich mehr Teile gesetzt werden, bevor kein Teil mehr passt und bei einer anderen Lösung weiter gesucht wird. Wenn der eigene Lösungsversuch mehr als ca. 9 Milliarden Teile setzt um alle Lösungen zu finden, sollte man wirklich mal nachsehen, wie die Quaderkoordinaten auf das Bitfeld umgesetzt werden, da hiervon (bei einer versuchten Besetzung des Bitfelds von kleinsten Bit aufsteigend ausgehend) festgelegt wird, wie der Quader gefüllt wird...

Der zweite Faktor ist die zur Vermeidung symmetrischer Lösungen verwendete Methode. Stellt man es geschickt an, reduziert sich die Anzahl der Lösungsfunktionsaufrufe nochmal um den Faktor 2, also ist hier locker die Halbierung der Laufzeit drin. Grundsätzlich verschwinden die symmetrischen Lösungen erstmal recht einfach, wenn man von einem Stein (der selber keine Symmetrien haben sollte) von jeweils 4 Positionen des Steins im Quader, die unter Berücksichtigung der Symmetrien des Quaders selbst identisch sind, nur eine zuläît. Der entscheidende Faktor hier ist, welche man denn nimmt. Mit dem einfachen Ansatz, generell von einem Teil bestimmte Orientierungen auszuschliessen, kommt man auf (wenn ich mich richtig erinnere) 9 Milliarden Aufrufe, wenn man es etwas geschickter macht, auf 3,9 Milliarden. Hier kommt meine absolute Lieblingszeile des Programms ins Spiel, und zwar die Bedingung

if ( (s & -s) > (p & -p) ) {...}

(s und p sind jeweils zwei der oben erwähnten 4 Möglichkeiten). Wer die Konstruktion auf Anhieb versteht, hat sicherlich zu viel Zeit vor dem Assembler verbracht, bei mir habe ich damit 20 Zeilen while (bla) {...} ersetzen können.

Laufzeiten auf verschiedenen Systemen

So, jetzt kommt der interessante Teil. Wenn noch jemand andere Zeiten auf seinem System ermittelt oder bessere Compiler-Optionen findet :), ich bin sicherlich interessiert (Kontakt). Vor allem frage ich mich, ob der Einsatz einer "echten" 64-Bit CPU etwas bringt, aber leider habe ich hier keinen Zugriff auf Alphas, Suns, MIPSs oder sonstiges. Auch wollte mir AMD partout kein Opteron-Testsystem dafür zu Verfügung stellen...

Es fällt auf, dass der Abstand zwischen gcc und Intel C++ auf dem Pentium IV viel gröîer ist als auf dem Duron, und man kann ausserdem erahnen, warum Intel seinen eigenen Compiler gebaut hat, wenn man mal den Unterschied zu MS Visual C++ auf dem P4 betrachtet und dann an SPEC denkt. Man sollte allerdings auch berücksichtigen, dass die Geschwindigkeit des Puzzle-Programms im wesentlichen von der Geschwindigkeit von 64-bittigen Integer-Operationen bestimmt wird, ein Punkt, der bestimmt nicht ganz oben auf der Optimierungsliste der Compilerbauer steht.

Mich interessiert sehr, wie der Unterschied gcc zu Intel C++ auf dem Athlon XP aussieht, aber leider habe ich kein System zu Verfügung, vielleicht schicht mir ja jemand eine Mail (Kontakt)?

Nachtrag: Wie der Tabelle unschwer zu entnehmen ist, habe ich einige Mails erhalten und inzwischen eine ziemlich eindrucksvolle Aufstellung an unterschiedlichen Systemen. An Laufzeiten auf anderen (exotischen?) Rechnern bin ich aber immer noch interessiert und füge sie gerne hinzu.

Absolute Laufzeiten
System	Diverse	MS Visual C++ 6.0	GCC 3.2 / Cygwin	Intel C++ 7.0
Alle Zeiten in Minuten, die zweite Angabe ist die Anzahl der Lösungen pro Sekunde. Die Balken spiegeln die Leistung wider, nicht den Zeitverbrauch, d.h. ein längerer Balken entspricht einer besseren Leistung Fussnoten siehe 3. Tabelle
Pentium III 450 MHz	N/A	N/A	N/A	52:30, 130/s(4)  25%
Duron (Spitfire) 850 MHz	N/A	N/A	28:53, 237/s  46%	33:17, 205/s  40%
Athlon (T-Bird) 700 MHz	N/A	N/A	33:26, 204/s(7)  40%	N/A
Athlon 800 MHz	61:41, 111/s(2)  22%	N/A	27:45, 246/s  48%	27:04, 252/s  49%
Celeron(18) 1200 Mhz	39:53, 171/s  33%	19:36, 349/s(19)  68%	18:52, 362/s  71%	19:28, 351/s  68%
Duron (Morgan) 1.3 GHz	42:36, 160/s(2)  31%	N/A	18:15, 374/s  73%	18:21, 372/s  73%
Athlon MP 1.2 GHz	N/A	N/A	18:00, 380/s(3)  74%	N/A
Pentium IV(1) 2.0 GHz	36:58, 185/s(2)  36%	22:42, 301/s  59%	17:42, 386/s  75%	13:20, 512/s  100%
Pentium IV 2.4 GHz	N/A	N/A	15:04, 453/s(6)  88%	11:14, 608/s(6)  119%
Athlon XP 2600+(12) 2083 MHz	23:51, 286/s(12)  56%	N/A	10:58, 623/s(12)  122%	10:27, 654/s(12)  128%
Athlon XP 2700+(5) 2167 MHz	N/A	N/A	10:27, 654/s(5)  128%	9:54, 690/s(5)  135%
Intel SE7501WV2(13) Xeon 2,8 GHz	16:12, 422/s(13)  82%	N/A	N/A	N/A
Sun Fire 480R, 32 bit(11) Sparc Ultra III Cu, 900 Mhz	22:37, 302/s(11)  59%	N/A	N/A	N/A
IBM RS/6000(17) PowerPC, 375 MHz	61:27, 111/s(17)  22%	N/A	N/A	N/A
Newisys 2100(14) Opteron M244 1,8 GHz	12:23, 552/s(14)  108%	N/A	N/A	N/A
64-Bit-Prozessoren
SGI Indigo2(16) MIPS R10000, 195 MHz	78:12, 87/s(16)  17%	N/A	N/A	N/A
Ultrasparc III(9) 333? MHz	70:34, 97/s(9)  19%	N/A	N/A	N/A
Alpha(8) 333 MHz	67:00, 102/s(8)  20%	N/A	N/A	N/A
Sun Fire 480R, 64 bit(10) Sparc Ultra III Cu, 900 Mhz	18:42, 365/s(10)  71%	N/A	N/A	N/A
Newisys 2100(15) Opteron M244 1,8 GHz	9:45, 701/s(15)  137%	N/A	N/A	N/A

Taktfrequenzbereinigte Leistung
System	Diverse	MS Visual C++ 6.0	GCC 3.2 / Cygwin	Intel C++ 7.0
Takte/V: Anzahl der Takte, die pro gelegtem Teil im Mittel benötigt wird; diese Größe ist (theoretisch) unabhängig von der Taktfrequenz und ermöglicht daher (in Grenzen), die Effizienz unterschiedlich getakteter CPUs direkt zu vergleichen. Die Balken sind relativ zum Kehrwert der benötigten Takte skaliert, d.h. ein längerer Balken entspricht einer schnelleren Bearbeitung. Fussnoten siehe 3. Tabelle
Pentium III 450 MHz	N/A	N/A	N/A	357 T/s(4)  113%
Duron (Spitfire) 850 MHz	N/A	N/A	371 T/s  109%	428 T/s  94%
Athlon (T-Bird) 700 MHz	N/A	N/A	354 T/s(7)  114%	N/A
Athlon 800 MHz	746 T/s(2)  54%	N/A	336 T/s  120%	327 T/s  123%
Celeron(18) 1200 Mhz	723 T/s  56%	356 T/s(19)  113%	342 T/s  118%	353 T/s  114%
Duron (Morgan) 1.3 GHz	837 T/s(2)  48%	N/A	359 T/s  112%	361 T/s  112%
Athlon MP 1.2 GHz	N/A	N/A	327 T/s(3)  123%	N/A
Pentium IV(1) 2.0 GHz	1118 T/s(2)  36%	686 T/s  59%	535 T/s  75%	403 T/s  100%
Pentium IV 2.4 GHz	N/A	N/A	547 T/s(6)  74%	408 T/s(6)  99%
Athlon XP 2600+(12) 2083 MHz	751 T/s(12)  54%	N/A	345 T/s(12)  117%	329 T/s(12)  122%
Athlon XP 2700+(5) 2167 MHz	N/A	N/A	342 T/s(5)  118%	324 T/s(5)  124%
Intel SE7501WV2(13) Xeon 2,8 GHz	686 T/s(13)  59%	N/A	N/A	N/A
Sun Fire 480R, 32 bit(11) Sparc Ultra III Cu, 900 Mhz	308 T/s(11)  131%	N/A	N/A	N/A
IBM RS/6000(17) PowerPC, 375 MHz	348 T/s(17)  116%	N/A	N/A	N/A
Newisys 2100(14) Opteron M244 1,8 GHz	337 T/s(14)  120%	N/A	N/A	N/A
64-Bit-Prozessoren
SGI Indigo2(16) MIPS R10000, 195 MHz	231 T/s(16)  175%	N/A	N/A	N/A
Ultrasparc III(9) 333? MHz	355 T/s(9)  113%	N/A	N/A	N/A
Alpha(8) 333 MHz	337 T/s(8)  119%	N/A	N/A	N/A
Sun Fire 480R, 64 bit(10) Sparc Ultra III Cu, 900 Mhz	254 T/s(10)  158%	N/A	N/A	N/A
Newisys 2100(15) Opteron M244 1,8 GHz	265 T/s(15)  152%	N/A	N/A	N/A

Compiler-Optionen

Und hier die verwendeten Compiler-Switches:

• -O -p6 -unused -Zp8 für llc-win32
• /O2 /G5 /Gs /Zi für MS Visual C++
• -Wall -O2 -mcpu=pentium4 -march=pentium4 -fomit-frame-pointer -falign-functions=8 für den gcc / Cygwin, vorgeschlagen von "Puzzled" in diesem Forumsbeitrag.
  Zusatz: zumindest auf Durons/Athlons besser -O2 -fomit-frame-pointer -mcpu=pentiumpro -march=pentiumpro verwenden, sollte ein gutes Stück schneller sein
• /Ox /Wall /Zi /Qipo /Qwd1418 /Qwd1419 für den Intel C++
  Hier bring übrigens /Qwx nichts (wird sogar ein gutes Stück langsamer), und passt daher wunderbar zu /O3, was auch höchstens den Stromverbrauch erhöht

Zukunft

MMX / SSE / SSE2

MMX und Konsorten sind in diesem Zusammenhang ein ganz trauriges Thema. Eigentlich hört es sich ja optimal an, 64/128-bittige Register, AND und OR ist auch möglich... nur leider hat Intel keine effiziente Möglichkeit vorgesehen, ein Register auf 0 zu testen, es sei denn, ich habe was grundlegendes übersehen. Das Beste, was mir dazu eingefallen ist:

pcmpeqb  mm3, mm7    // mm3 ist auf 0 zu testen, mm7 ist Konstante 0
pmovmskb eax, mm3    // die höchsten Bits aller 8 Bytes aus mm3 nach al
inc      al          // wenn al=ff war ist al+1 = 0 => zero flag
jnz      nicht0      // Schleife

oder wahlweise

packssdw mm3, mm3    // oberes und unteres DWORD von mm3 zusammenfassen
movd     edx, mm3    // und nach edx
test     edx, edx    // auf 0 testen
jnz      nicht0      // Schleife

Ich weiss schon gar nicht mehr, was davon langsamer war, ist aber beides kaum zu empfehlen. Eine Möglichkeit, hier irgendwas halbwegs der Intention von SIMD entsprechenden einzubauen, habe ich noch nicht gefunden, vielleicht probiere ich später mal mit SSE2 und 128-bittigen Registern rum, dann liessen sich immerhin 2 Steine gleichzeitig testen. Meine einzige Hoffnung in Bezug auf MMX bleibt, dass ein zweiter Thread mit MMX (oder SSE2, SSE ohne 2 ist nur Floating Point, also hier nutzlos) auf einem Pentium IV mit Hyperthreading andere Funktionseinheiten der CPU auslastet und daher mehr Gewinn bringt als ein zweiter Thread mit normaler Integer-Arithmetik, womit wir auch schon beim nächsten Punkt wären:

Hyperthreading

Hier werde ich sicherlich noch was versuchen, leider habe ich kein Testsystem, und mal eben einen Pentium IV mit 3 GHz werde ich mir dafür auch nicht zulegen. Bis jetzt habe ich aber noch keine Zeile Thread-Code geschrieben, auch wenn ich hier kein grosses Problem sehe, zumindest auf einem Multiprozessor-System dürfte das mit nahezu 90% skalieren, mit Hyperthreading läît sich da schlecht eine Voraussage treffen.

Dateien

• ctpuzzle.c, der Quelltext ⁽¹⁾, 1.759 Bytes
• ctpuzzle_icl.exe, mit Intel C++ übersetzt, 69 KB
• ctpuzzle_gcc.exe ⁽²⁾, mit gcc 3.2 / Cygwin übersetzt 88 KB
• ctpuzzle_msc.exe, mit Microsoft Visual C++ übersetzt, 65 KB
  ohne Compiler-Optimierungen, sehr langsam!
• ctpuzzle_vc5.exe, von Bruno Wöhrer mit Visual C++ 5.0 übersetzt, 49 KB
• ctpuzzle_vc6.exe, von Bruno Wöhrer mit Visual C++ 6.0 übersetzt, 36 KB
• ctpuzzle_vc7.exe, von Bruno Wöhrer mit Visual C++ 7.0 übersetzt, 44 KB
• ctpuzzle_lcc.exe, mit lcc-win32 übersetzt, 12 KB
• ctpuzzle.zip, alle Dateien in einem ZIP-Archiv, 150 KB

¹ wahlweise gleich ctpuzzle_ms.c für MS Visual C++ (mit __int64 statt long long)
² benötigt cygwin1.dll (443 KB), wenn nicht schon vorhanden

Kontakt

Ich, Uli Schuhmacher, bin per eMail unter epsilon0@ixcase.com erreichbar. Ansonsten verweise ich hier noch auf das c't-Forum zum oben erwähnten Artikel: Forum