Der Businesscard Raytracer

vorhergehende Artikel in: C und C++
27.04.2023

Ich fand neulich einen Artikel, den ich als äußerst interessant einstufte und mit dem ich mich ein wenig näher beschäftigte um ihn nachzuvollziehen.

Der Artikel dreht sich um ein Stück C++ Code, das - obwohl er leserlich auf die Rückseite einer Visitenkarte passt - ein vollständiges Programm zum Raytracing einer im Programm festverdrahteten Szene ist und daraus eine Bitmapgraphik rendern kann. Der Code sieht zunächst erst einmal so aus, als ob er dem Obfuscated C-Code Contest entsprungen wäre:

 <stdlib.h>   // card > aek.ppm
 <stdio.h>
 <math.h>
typedef int i;typedef float f;struct v{
f x,y,z;v operator+(v r){return v(x+r.x
,y+r.y,z+r.z);}v operator*(f r){return
v(x*r,y*r,z*r);}f operator%(v r){return
x*r.x+y*r.y+z*r.z;}v(){}v operator^(v r
){return v(y*r.z-z*r.y,z*r.x-x*r.z,x*r.
y-y*r.x);}v(f a,f b,f c){x=a;y=b;z=c;}v
operator!(){return*this*(1/sqrt(*this%*
this));}};i G[]={247570,280596,280600,
249748,18578,18577,231184,16,16};f R(){
return(f)rand()/RAND_MAX;}i T(v o,v d,f
&t,v&n){t=1e9;i m=0;f p=-o.z/d.z;if(.01
<p)t=p,n=v(0,0,1),m=1;for(i k=19;k--;)
for(i j=9;j--;)if(G[j]&1<<k){v p=o+v(-k
,0,-j-4);f b=p%d,c=p%p-1,q=b*b-c;if(q>0
){f s=-b-sqrt(q);if(s<t&&s>.01)t=s,n=!(
p+d*t),m=2;}}return m;}v S(v o,v d){f t
;v n;i m=T(o,d,t,n);if(!m)return v(.7,
.6,1)*pow(1-d.z,4);v h=o+d*t,l=!(v(9+R(
),9+R(),16)+h*-1),r=d+n*(n%d*-2);f b=l%
n;if(b<0||T(h,l,t,n))b=0;f p=pow(l%r*(b
>0),99);if(m&1){h=h*.2;return((i)(ceil(
h.x)+ceil(h.y))&1?v(3,1,1):v(3,3,3))*(b
*.2+.1);}return v(p,p,p)+S(h,r)*.5;}i
main(){printf("P6 512 512 255 ");v g=!v
(-6,-16,0),a=!(v(0,0,1)^g)*.002,b=!(g^a
)*.002,c=(a+b)*-256+g;for(i y=512;y--;)
for(i x=512;x--;){v p(13,13,13);for(i r
=64;r--;){v t=a*(R()-.5)*99+b*(R()-.5)*
99;p=S(v(17,16,8)+t,!(t*-1+(a*(R()+x)+b
*(y+R())+c)*16))*3.5+p;}printf("%c%c%c"
,(i)p.x,(i)p.y,(i)p.z);}}

Übersichtlicher wird er zum Beispiel hier dargestellt.

Das Bild, das bei seiner Ausführung entsteht, sieht wie folgt aus:

Screenshot Ergebnis des BusinessCard Raytracer

Der Artikel beschreibt, wie ausgehend vom ursprünglichen Quelltext versucht wird, die Performanz immer weiter zu steigern. Ich war neugierig, wie sich mein schon etwas angejahrter Prozessor dabei schlagen würde und versuchte, die Zeiten mit unterschiedlichen Compiler-Optimierungsstufen zu messen, ohne irgend etwas am Quelltext geändert zu haben.

Ich staunte nicht schlecht: Ohne jede Optimierung dauerte die Ausführung 1m10,266s. Mit Optimierung -O1 wurde die Anwendung schon merklich schneller: 0m35,703s. Aber mit Optimierung -O3 sauste sie völlig ungebremst zu atemberaubenden 0m6,578s. Und so sehr ich inzwischen Java mag - das geht nur mit C(++)!

Und bei diesem Gedanken überlegte ich, dass es doch möglich sein musste, diesen Code nach Java zu transponieren und dann dort einige Experimente durchzuführen. Glücklicherweise musste ich das nicht mehr selbst tun: Hier fand ich bereits das fertige Programm als Java-Code vor - jemand anderes war bereits auf die Idee gekommen!

Der Autor der Java-Variantebekennt auch gleich freimütig, dass er keine Performanceoptimieruengen vorgenommen hat und weist darauf hin, dass zum Beispiel jede der Operationen auf den Vektoren immer einen neuen Vektor erzeugt und das evtl. nicht gut ist für die Performance, da diese riesige Menge von Objekten der GarbageCollector zu sehr stressen könnte - ein Szenario, dass ich aus eigener Erfahrung nur zu gut kenne!

Also zählte ich zunächst einmal die Instanzen der Vektor-Klasse bei einem einmaligen Durchlauf - stolze 4117203763! Ein Durchlauf der Java-Version dauerte auf dem Rechner, mit dem ich bereits die Experimente mit der ursprünglichen C++-Variante durchgeführt hatte 00:00:12.727817 - also nur etwa doppelt so lange, wie die mitels -O3 optimierte Version - nicht schlecht!

Ich ging nun systematisch daran, die Stellen, an denen neue Instanzen nicht wirklich benötigt wurden durch Varianten der Methoden zu ersetzen, die die übergebene Instanz lediglich modifizierten. Nachdem ich das an einigen Stellen getan hatte, konnte ich die Anzahl erzeugter Instanzen während eines Durchlaufs auf 2045497739 drücken - musste aber mit Erstaunen feststellen, dass sich die Laufzeit von rund 12 Sekunden auf über 16 Sekunden erhöht hatte - eine Steigerung um 33%!

Nachdem ich nach der Ursache suchte, kam ich nach einiger Zeit darauf, die in-Place-Methoden wieder gegen die Varianten mit Erzeugung einer neuen Instanz zu ersetzen und war völlig perplex, als ich feststellen musste, dass diese Varianten schneller waren. So ersetzte ich etwa

V3f scale(float r)
{
	x*=r;
	y*=r;
	z*=r;
	return this;
}

nur an der Stelle der mit Abstand häufigsten Nutzung durch

V3f scaleAndNew(float r)
{
	return new V3f(x * r, y * r, z * r);
}

Durch diese eine Änderung ergab sich eine Laufzeit von nunmehr wieder nur noch 00:00:13.034734 bei einer Gesamtzahl erzeugter Vektor-Instanzen von 2087374555!

Faszinierend - zumal ich absolut nicht sehen konnte, was an der in-Place-Variante so schlimme Performancestrafen nach sich ziehen sollte!

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

Neueste Artikel

  • SQL Funktionen in SQLite als BeanShell-Scripts

    Ich habe bereits hin und wieder über Erweiterungen der sQLshell berichtet, die bestimmte spezifische, proprietäre Features des jeweiligen DBMS in der sQLshell verfügbar machen.

    Weiterlesen...
  • Spieleengine IX

    Es gibt seit Ewigkeiten mal wieder Neues von meiner eigenen Spieleengine!

    Weiterlesen...
  • Neue Version plantumlinterfaceproxy napkin look

    Es gibt eine neue Version des Projektes plantumlinterfaceproxy - Codename napkin look.

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier - meine öffentlichen GitLab-Repositories finden sich dagegen hier.