Date: Sun, 11 Mar 2001 00:33:55 +0100 Subject: Obskure Compiler-Optimierungsprobleme: Aliasing Liebe Zielgruppe, Aliasing ist ein großes Problem. Es verhindert in vielen Fällen, daß Compiler anständig optimieren können. Das Problem sieht man ganz gut an folgender Funktion: void f (int ip1[], int ip2[]) { int i; for (i = 0; i < 9; ++i) { ip1[i + 1] = ip2[i] + ip2[i + 1]; } } Das Problem hierbei ist, daß der Compiler nicht wissen kann, ob ip1 und ip2 überlappen. Diese Funktion ist so gewählt, daß der Spezialfall von ip1 == ip2 gerade Probleme macht. Was passiert hier also? Der Compiler muß annehmen, daß ip2[i] im nächsten Schleifendurchlauf nicht mehr das ip2[i+1] aus dem letzten Schleifendurchlauf ist, und muß sie daher ständig neu laden. Konkret hat sich damit die Anzahl der Loads verdoppelt. Gut, ist nicht so schlimm, weil sich das in den Caches abspielt, aber das Problem ist klar. Diese Art von Funktion wird in typischen Texten zu Aliasing gerne zitiert, aber sie erscheint den meisten Programmieren zu abstrakt oder speziell, als daß sie ihren Code wiedererkennen würden. Aber nehmen wir mal an, daß man über mehrere Indirektionen an anderen Zeigern herumpopelt. foo->bar->a=baz->a; foo->bar->b=baz->b; foo->bar->c=baz->c; foo->bar->d=baz->d; Ich bin mir sicher, diese Art von Code haben wir alle schonmal geschrieben. Nun, was hat das eine mit dem anderen zu tun? Welche Art von Code würde man erwarten? Man würde denken, daß der Compiler foo->bar und baz in je ein Register tut und dann die Elemente relativ zu dem Register kopiert. Das tut der Compiler aber nicht. Er dereferenziert foo->bar jedes Mal neu. Warum? Weil eine der Zuweisungen foo oder foo->bar überschreiben könnte. Klar, das kommt normalerweise nicht vor. Oder sagen wir mal: eher selten. Stellt sich die Frage: was kann man tun? In dem foo->bar Fall kann man sich behelfen, indem man einen temporären Zeiger nimmt, foo->bar in diesen schreibt, und dann mit diesem Zeiger statt mit foo->bar operiert. Damit der Compiler auch sicher weiß, daß dieser temporäre Zeiger niemals Ziel von Pointer Aliasing sein wird, kann man ihn "register" deklarieren, d.h. etwa so: register struct blah* temp=foo->bar; Bei neueren gcc-Versionen gibt es auch eine Option -fstrict-aliasing, die dem Compiler mitteilt, daß er immer davon ausgehen kann, daß kein Aliasing zwischen fremden Typen auftritt, d.h. daß ein Store eines Ints einen Zeiger überschreiben wird, aber das ist bei typischen Quellen erschreckend häufig eine Fehlannahme (insbesondere Netzwerk-Code und Bitpfriemeleien verstoßen hiergegen gerne und häufig). Wer mal dem Linux Kernel beim Kompilieren zuschaut, wird feststellen, daß dort sogar explizit -fno-strict-aliasing gesagt wird. Um das ganze mal in Perspektive zu rücken: viel Performance spart man in "normalem" Code damit nicht. D.h. die gtk-Leute müssen sich jetzt nicht hinsetzen und den Code durchgehen, die Geschwindigkeit der GUI-Toolkits ist nicht wegen Aliasing-Problemen so schlecht ;-} Aber in Code, der über Arrays iteriert, wie z.B. bei DirectFB oder Code, der viel mit Vektoren umgeht (Raytracer, Simulationen) verschlingen Aliasing-Probleme einen substantiellen Teil der Performance. Das ist übrigens auch der Grund, wieso die Numeriker traditionell FORTRAN benutzen - keine Pointer -> kein Aliasing -> keine Probleme. Felix PS: Die nächste Version des C-Standards ("C9X") hat ein Schlüsselwort "restrict", mit dem man sagen kann, daß ein Pointer keinen anderen aliasen wird. gcc 3.0 wird restrict implementieren (die CVS-Snapshots von gcc haben es schon).