Adventskalender 20. Dezember 2024 - NQueens

[mn77de]

Einleitung
Heute kommt das Türchen mit der vmtl. längsten Vorbereitungszeit
Und gleich vorweg ... mich faszinieren Programmiersprachen und Algorithmen.

Eigentlich ging es am 19.7.2009 los, als auf Heise folgender Artikel erschien: 26-Damen-Problem gelöst
Und nein, das Damenproblem hat nichts mit Frauen zu tun

Es geht hier um eine schachmathematische Problemstellung:

Wie viele Möglichkeiten gibt es, um 'n' Damen auf einem Schachfeld der Größe 'n x n' so zu positionieren, dass sie einander weder diagonal, noch senkrecht, noch waagrecht schlagen können.

Weitere Infos kann man auf Wikipedia nachlesen: Wikipedia - Damenproblem

Damals fand ich die Problemstellung eine gute Fingerübung, weshalb ich spontan einen möglichst effizienten Algorithmus entwickelte.
Als weiteren Schritt fing ich an, diesen Quellcode in verschiedene Sprachen zu übersetzen. Welche Sprache ist wohl die schnellste?

Es ist einem meist nicht bewusst, aber man hat mit Debian heutzutage wirklich viele, qualitative und teils sehr mächtige Programmiersprachen sofort zur Hand!

Mein Projekt ist nun quasi ein Benchmark für diese Programmiersprachen. Einerseits lässt sich die Geschwindigkeit testen, andererseits kann auch die Übersichtlichkeit und Einfachheit verglichen werden.

Klarstellung
Es mag sicherlich noch einen effizienteren Lösungsansatz geben, als den von mir gewählten. Gerade mit nebenläufigen Prozessen und der Verteilung auf mehrere CPU's, sollte da heutzutage noch einiges möglich sein.
Teils lässt sich auch der Quellcode noch optimieren, ich bin natürlich nicht in allen Sprachen so richtig fit.
Ebenso sind meine Geschwindigkeitstests nur relativ zu werten und wurden nicht unter "Laborbedingungen" durchgeführt.
Auch fehlen noch einige Sprachen, wie z.B. Lisp.

Es gibt noch bissl zu tun

Trotzdem bietet mein Projekt die Möglichkeit für ein paar Vergleiche.

Geschwindigkeit
Hier nun die bei mir und mit einem i7-11700 ermittelten Ergebnisse:

Alle Werte sind in Sekunden. Eine Sprache schied aus dem Test aus, sobald sie für die Aufgabe mehr als 20 Sekunden benötigte.

EDIT: Aufgrund von Eurem Feedback wurden mittlerweile viele Optimierungen vorgenommen. Die Grafik wurde entsprechend aktualisiert.

And the winners are: Fortran, C, Go, Vala, Rust !!!

Da Groovy hier interpretiert gestartet wird, ist dies eine ordentliche Leistung. Auch Julia ist als interpretierte Sprache richtig flott. Wobei z.B. Lua eine ultrakurze Startgeschwindigkeit hat.
Faszinierend finde ich, dass die Java-VM echt flott ist!

Das Schlusslicht bildet die Bash, welche für solche Aufgaben aber auch nicht wirklich gemacht ist.

Übersichtlichkeit / Einfachheit
Eine gute Lesbarkeit ist bei einer Programmiersprache generell sehr sinnvoll. Ebenso ist ein kompakter Quellcode von Vorteil, da er Schreibarbeit erspart.


Natürlich lassen sich die einzelnen Programme kompakter schreiben, aber hier geht es um die übliche und gut lesbare Schreibweise.
Interessant ist auch, ob eine Programmiersprache sehr viele Sonderzeichen und Klammern benötigt. So etwas kann die Lesbarkeit erschweren, wie z.B. bei Perl.
Leerzeichen, Zeilenumbrüche und Tabs werden bei der Prozentzahl übrigens ignoriert.

Die einzelnen Programme können hier betrachtet werden: nqueens.mn77.de
Das gesamte Projekt liegt auf GitLab und ist relativ übersichtlich strukturiert: https://gitlab.com/MN77/nqueens

Mit folgendem Befehl kann es übrigens auf den Rechner geladen werden:

Code: Alles auswählen

git clone https://gitlab.com/MN77/nqueens

Schlusswort
Das Ziel des heutigen Türchens ist es, auf die vielen Programmiersprachen in Debian hinzuweisen.
Jede der heute genannten Sprachen hat ihre Berechtigung und es gibt ganz spezifische Anwendungsfälle dafür.
Das Damenproblem ist natürlich nicht für alle der optimale Anwendungsfall.

Was sind Eure Lieblings-Programmiersprachen?
Ist eine Sprache dabei, die ihr noch nicht kennt?
Welche Sprachen sollten noch unbedingt aufgenommen werden?
Gibt es Optimierungen, die ihr vornehmen würdet?

Und ja, meine eigene Programmiersprache "JayMo" hat sich hier rein gemogelt, obwohl sie nicht im Debian-Repo verfügbar ist.

Ich wünsche Euch viel Spaß beim Stöbern, entdecken, ausprobieren und programmieren.

[Liffi]

Sehr witziges Projekt muss ich sagen. Mich überrascht vermutlich das Ergebnis von C am meisten. Da würde mich interessieren, ob da jemand mit ein bisschen C-Wissen das noch verbessern kann.
Auch bei Rust und C++ würde ich noch Potential erwarten.

[uname]

Auch von mir Danke für das Thema. Ich habe mir mal die JavaScript-Version angeschaut und einen Zähler für die rekursive Funktion solve eingebaut. Benutzt du überall Rekursion? Ist die Anzahl der Funktionsaufrufe der rekursiven Funktion bei allen Programmiersprachen gleich?

Code: Alles auswählen

N=1: Anzahl der Lösungen: 1, Anzahl der Funktionsaufrufe: 2
N=2: Anzahl der Lösungen: 0, Anzahl der Funktionsaufrufe: 3
N=3: Anzahl der Lösungen: 0, Anzahl der Funktionsaufrufe: 6
N=4: Anzahl der Lösungen: 2, Anzahl der Funktionsaufrufe: 17
N=5: Anzahl der Lösungen: 10, Anzahl der Funktionsaufrufe: 54
N=6: Anzahl der Lösungen: 4, Anzahl der Funktionsaufrufe: 153
N=7: Anzahl der Lösungen: 40, Anzahl der Funktionsaufrufe: 552
N=8: Anzahl der Lösungen: 92, Anzahl der Funktionsaufrufe: 2057
N=9: Anzahl der Lösungen: 352, Anzahl der Funktionsaufrufe: 8394
N=10: Anzahl der Lösungen: 724, Anzahl der Funktionsaufrufe: 35539
N=11: Anzahl der Lösungen: 2680, Anzahl der Funktionsaufrufe: 166926
N=12: Anzahl der Lösungen: 14200, Anzahl der Funktionsaufrufe: 856189

[mn77de]

Benutzt du überall Rekursion? Ist die Anzahl der Funktionsaufrufe der rekursiven Funktion bei allen Programmiersprachen gleich?

Zum besseren Vergleich habe ich versucht, den Code für alle Sprachen möglichst ähnlich zu halten. Somit sollte die Anzahl der Funktionsaufrufe überall gleich sein, ja.
Lass mich gerne wissen, wenn du eine schnellere Möglichkeit findest.

[uname]

Ich habe mal mit Hilfe einer KI versucht beim Damenproblem die genannte Koroutine von Niklaus Wirth zu verwenden. Bein meinem Test mit JavaScript von 1 bis 13 jedoch ohne Berechnung der zusätzlichen Schleifenzähler war die Version mit der Koroutine 10 Mal langsamer (extra Zeitausgabe vorher und nachher eingebaut). Aber das lag vielleicht auch nur an JavaScript oder der KI. Vielleicht hat die alternative Lösung aber weniger Speicher benötigt. Das habe ich nicht geprüft.

[wanne]

Ein wenig verwundert bin ich von C, aber sicherlich gibt es hier noch Optimierungsmöglichkeiten.

Naja, das gcc ohne optimierung zu verwenden finde ich schon massiv unfair. Das speichert da literally jede Variable nach jeder Zeile in den RAM um sie dann wieder da auszulesen. Der Cache fängt da einiges ab aber im Zweifelsfall sind das halt zig CPU-Zyklen pro Zeile warteizeit auf den RAM. Für ein Benchmark gehört da IMHO mindestens ein -O3 hin. Zumal go über doppelt so lange braucht, wenn man Optimierung abschaltet, die da halt per default an und nicht aus ist.
-O3 -funroll-all-loops ist bei mir für die 15 Damen 3s schneller als die go Variante 7.469s vs. 10.129s mit Optimierung. clang ist nur mit -O3 schneller als die go Variante 7.629s.
Daneben ist bools zu verwenden halt extrem ineffizient. Auf der anderen Seite ist Bitbangig halt ein viel komplexeres unterfangen und dann kein vergleichbarer Algorithmus mehr. Das ist leider halt immer das Problem bei Programmierspracheinvergleichen.
Die was Programmiersprachen unterschiedlich schnell macht ist ja die übliche Nutzung und ein bisschen Compilerunterschiede. Wenn man einem gleich funktionierenden Compiler den gleichen Algorithmus in unterschiedlichen Sprachen übergibt sollte ja der selbe assembler raus kommen. Aber die übliche Nutzung ist halt sehr geschmacksspezifisch. Daneben ist die Idee der bash halt, dass man andere tools aufruft und niemals selber rechnet. Kann ja nicht mal floats. In sofern ist ja jede deiner Lösungen eine Bash-Lösung.

[mn77de]

Für ein Benchmark gehört da IMHO mindestens ein -O3 hin.

Danke für den Hinweis. Entsprechend habe ich nun für C, C++ und Vala jeweils ein "-Ofast" verwendet, was die Ausführungsgeschwindigkeit doch extrem beschleunigt. Ein "-Ofast" war auch schneller als "-O3 -funroll-all-loops", auch wenn die Kompilierung nun angeblich nicht mehr Standard-Konform ist.

Entsprechend sind nun Go, C und Vala führend!
Wobei Go bei mir immer noch am schnellsten ist, wenn auch nur ganz minimal.

Vielleicht gibt es bei anderen Sprachen auch noch solche Optimierungen ... ?

[hikaru]

Auch Fortran sollte mit Optimierung wieder auf C-Level sein.

[mn77de]

Auch Fortran sollte mit Optimierung wieder auf C-Level sein.

Wuhuuu!
Fortran hat mit "-Ofast" gerade deutlich alle anderen, inkl. Go und C, überholt.

Okay, weiter so ... wo gibt es noch Optimierungsmöglichkeiten?

[tobo]

fpc mit -O4 verkürzt die Zeit um 1/4.

[paedubucher]

Da fehlt noch Rust; wäre sicherlich ein Versuch wert. Ich müsste mich zuerst einmal mit dem Problem selber befassen. Mal schauen, was die Festtage zeitlich so hergeben...

Das Türchen zeigt sehr schön, dass es hlifreich sein kann, sich immer wieder mit dem gleichen Problem aber in einem unterschiedlichen Medium (Programmiersprache) zu befassen. Über die Zeit hat sich bei dir einiges angesammelt, respekt!

[wanne]

Lua kann auch mehr. Der "normale" interpreter ist auf möglichst kleine Startzeiten optimiert.
luajit ist für anspruchsvollere Programme die bessere Wahl. Viertelt bei mir die Zeit.

Rein Theoretisch kann man lua auch compilieren. Leider supported der luajit aus Debian compilierten Code für Lua5.1. Das genutzte ::continue:: wird aber erst ab Lua5.2 unterstützt. Ändert sowieso kaum was an der Laufzeit, da lua sowieso super schnell compiliert.

[wanne]

Hier eine schnelle C++-Variante. Nicht schön. Aber schnell. Sowohl zu schreiben wie auch zum ausführen. Nutzt dann aber wirklich ne abgewandelte Form. (Bitbanging, Threads, funktionaler, mit fester Länge.)
Kann man quasi 1:1 nach Java und mit wenig Abwandlung nach C (und vermutlich viele andere Sprachen) übertragen.
War sehr enttäuscht dass ich am Ende doch selbst entscheiden muss wo ich neue Threads starte. Dass async selbst entscheiden können soll, wann das passiert war der Grund warum ich nach C++ gegangen bin.
Kann man sicher noch verschönern.
pastebin/?mode=view&s=42281

[wanne]

Während es bei der ursprünglcihen Variante nichts aus gemacht hat, läuft die jetzige mit -march=native ~20% schneller. 32Bit läuft über doppelt so langsam. Soviel zu dem Quatsch, dass amd64 keinen Vorteil hat, wenn man den RAM nicht braucht.

Btw: Wie oft führst du eigentlich aus um die Sekunden zu ermitteln? Bei mir variieren die Zeiten um fast ein drittel, was auf deiner Liste den Unterschied ~10 Plätze Unterschied macht. Liegt aber vermutlich auch an der heterogenen Architektur meines i5-12600KF

Btw2. meinem i5-12600KF alle single-core Varianten ähnlich schnell wie dein i7-11700. Das ist IMHO ziemlich peinlich.

[wanne]

OCaml unter debian frisst natürlich auch -O3!
pypy3 ist hier 4 mal so schnell wie CPyhton3.

[kalle123]

NQueens. Danke dafür

Zuletzt 'richtig' programmiert vor fast 50 Jahren in FORTRAN IV. Aber die Implementierung in gfortran und auch yabasic, vielleicht auch lua werde ich mir mal anschauen.

Ob ich da noch was kapiere ?? Mal schauen.

Grüße KH

[mn77de]

Vielen Dank für Eure Rückmeldungen!

Ich habe heute einige Geschwindigkeitsoptimierungen vorgenommen, wenn vorhanden wird nun "-Ofast" bzw. "-O3" verwendet.

Das Ergebnis hat sich dadurch natürlich grundlegend verändert!
Die Grafik ist nun aktualisiert.

[mn77de]

OCaml unter debian frisst natürlich auch -O3!
pypy3 ist hier 4 mal so schnell wie CPyhton3.

Ja, allerdings wurde OCaml bei mir mit O3 langsamer

pypy3, danke für den Hinweis, teste ich noch.

Btw: Wie oft führst du eigentlich aus um die Sekunden zu ermitteln? Bei mir variieren die Zeiten um fast ein drittel, was auf deiner Liste den Unterschied ~10 Plätze Unterschied macht. Liegt aber vermutlich auch an der heterogenen Architektur meines i5-12600KF

Die Tests habe ich in der Regel je 3x ausgeführt, wobei es hier generell nur geringe Abweichungen gibt.

[hikaru]

Soviel zu dem Quatsch, dass amd64 keinen Vorteil hat, wenn man den RAM nicht braucht.

Es kommt auf das Szenario an. In den meisten realen Szenarien wartet die CPU >99,9% ihrer Zyklen auf Nutzereingaben. Und dann macht es wirklich keinen Unterschied, ob man i686 oder amd64 als Befehlssatz nutzt.

In synthetischen Benchmarks wie diesem hier sieht das aber anders aus. Der amd64(v1)-Befehlssatz bildet weitgehend die Fähigkeiten des Athlon 64 von 2003 ab und beinhaltet gegenüber i686, welcher die Fähigkeiten des Pentium Pro von 1995 abbildet, mehr als nur die 64bit-Erweiterung. Die zweitprominenteste dieser Erweiterungen dürfte SSE2 sein, welche allein schon für einen Performance-Schub in diesem Benchmark(!) sorgen dürfte.

Wenn du mit --march=native compilierst, dann bist du bei deiner CPU nicht nur bei amd64v1, sondern jenseits von amd64v4, was weitere Erweiterungen beinhaltet. Der Nachteil ist halt, dass dein Binary auf meiner CPU (i5-5600U, amd64v3) nicht mehr läuft.

Genau wegen der Granularität der Befehlssätze verschiedener CPUs macht man bei Gentoo so einen Bohei darum, seine eigenen Binaries selbst zu compilieren.

[GregorS]

Welche Sprachen sollten noch unbedingt aufgenommen werden?

Ich plädiere für Brainfuck!

Oder Piet.

[wanne]

Die compile.sh für ocaml hat noch ne kaputte #!-Zeile.

Ich plädiere für

Ich tippe mn77de nimmt pull requets an. Wo wir dabei sind, vielleicht sollte ich mal meinen alten Github-Account wieder rausholen, statt hier die ganze Zeit zu posten.

[schorsch_76]

Hab einen Merge Request erstellt der die C++ Performance erhöht. std::vector<bool> ist relativ ineffizient.

https://gitlab.com/MN77/nqueens/-/merge_requests/1
https://gitlab.com/MN77/nqueens/-/merge ... b8a66aaaa6

Bei mir schaut das dann so aus:

Code: Alles auswählen

georg@hammerhead:/tmp/nqueens/c++$ time ./run.sh 16
Solving: n=16
Result:  14772512

real    0m53,031s
user    0m52,978s
sys     0m0,012s
georg@hammerhead:/tmp/nqueens/c++$ cd ../c
georg@hammerhead:/tmp/nqueens/c$ time ./run.sh 16
Solving: n=16
Result:  14772512

real    0m56,884s
user    0m56,872s
sys     0m0,004s

[mn77de]

Wenn du mit --march=native compilierst, dann bist du bei deiner CPU nicht nur bei amd64v1, sondern jenseits von amd64v4, was weitere Erweiterungen beinhaltet. Der Nachteil ist halt, dass dein Binary auf meiner CPU (i5-5600U, amd64v3) nicht mehr läuft.

Genau wegen der Granularität der Befehlssätze verschiedener CPUs macht man bei Gentoo so einen Bohei darum, seine eigenen Binaries selbst zu compilieren.

Vielen Dank für diese gute Erklärung!
Vielleicht sollte ich die kompilierten Binaries besser nicht ins Repo packen

Mit "march=native" gab es wirklich nochmal einen Geschwindigkeitsschub, wenn auch keinen besonders großen. Außer bei Fortran und Vala, da wurde das Programm bei mir dadurch langsamer ... ???

Welche Sprachen sollten noch unbedingt aufgenommen werden?

Ich plädiere für Brainfuck!
Oder Piet.

Piet kannte ich noch nicht
Brainfuck, absolut ...

Wobei solche Sprachen, mal abgesehen von den abenteuerlichen Eigenheiten, einfach nicht dafür geeignet sind, komplexe Algorithmen und rekursive Backtracking-Probleme umzusetzen.

Die compile.sh für ocaml hat noch ne kaputte #!-Zeile.

Ich tippe mn77de nimmt pull requets an.

Danke, ist korrigiert. Alles was ins Projekt passt, sehr gerne

Hab einen Merge Request erstellt der die C++ Performance erhöht. std::vector<bool> ist relativ ineffizient.

Danke dir, hab es mit aufgenommen. Wobei dies jetzt nur C++ war, was nun alle anderen überholt hat.

Das hat ja fast was von einem Wettrennen

[mn77de]

Hier eine schnelle C++-Variante.
pastebin/?mode=view&s=42281

Halleluja ... N=17 in 24 Sekunden!!!

Und vmtl. würde dies mit der Bitset-Lösung von Schorsch nochmal einen Boost bringen.

Momentan ist das ganze Projekt auf Single-Thread ausgelegt, was es einfach und relativ vergleichbar macht. Ich bin aber am Überlegen, die Parallellisierung ist auf jeden Fall interessant.

[schorsch_76]

Vielleicht sollte ich die kompilierten Binaries besser nicht ins Repo packen

Ja, die gehören nicht in ein Quellcode Repo

Hab einen Merge Request erstellt der die C++ Performance erhöht. std::vector<bool> ist relativ ineffizient.

Danke dir, hab es mit aufgenommen. Wobei dies jetzt nur C++ war, was nun alle anderen überholt hat.

Das hat ja fast was von einem Wettrennen

Bin gespannt was noch für Optimierungen gepostet werden Ich glaube wanne könnte noch was für C bringen