From leitner@convergence.de Tue May 29 14:25:26 2001
Date: Tue, 29 May 2001 14:25:26 +0200
From: Felix von Leitner <leitner@convergence.de>
To: developers@convergence.de
Subject: =?iso-8859-1?Q?Spr=FCnge?= in C98: expect
Message-ID: <20010529142526.A26359@convergence.de>
Mail-Followup-To: developers@convergence.de
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
User-Agent: Mutt/1.3.16i
Status: RO
Content-Length: 2741
Lines: 74

Nachdem ich in der letzten Mail geschildert habe, daß Sprünge und
Sprungvorhersage sehr wichtig für die Performance sind, kommt hier noch
ein kleines praktisch unbekanntes gcc-Feature.  Tatsächlich ist es wohl
ein Feature von C9x (ich hab den Standard nicht greifbar), und bei gcc
ist es im Moment auch nicht unterstützt, aber im CVS-Snapshot der
Version 3.0 ist es drin.  Den hab ich gerade nicht hier, d.h. ich weiß
auch nicht, ob das tatsächlich ausgewertet wird oder erstmal nur vom
Parser verstanden wird, aber man kann in jedem Fall seinen Code schonmal
umstellen, wenn man möchte ;)

So, keine weiteren Disclaimer, hier ist die (widerliche) Syntax:

  while (foo>4) {

wird zu

  while (expect(foo>4,1))

Die erste Zahl ist ganz normal die Condition, die zweite Zahl ist was
man annimmt, d.h. 1 für "true" und 0 für "false".  D.h. die Idee ist,
daß man gcc so sagen kann, ob der Sprung wahrscheinlich genommen wird
oder nicht.

Was kann gcc damit theoretisch überhaupt machen?

  1. bei PowerPC sind im Sprung-Opcode ein paar Bits reserviert, mit
     denen man diese Information übertragen kann (tres cool!)

  2. bei anderen Prozessoren gibt es die Heuristik, daß ein Sprung nach
     vorne wahrscheinlich nicht genommen wird, und ein Sprung zurück
     wahrscheinlich genommen wird.  Die Begründung ist, daß ein Sprung
     nach vorne eine if-Anweisung ist und ein Sprung zurück eine
     Schleife.  D.h. wenn ich gcc sage, daß der Sprung nach vorne
     wahrscheinlich nicht genommen werden wird, könnte er aus

	  jne foo
	  ...
	foo:

     folgendes machen:

	  je tmp
	  jmp foo
	tmp:
	  ...
	foo:

     Ein nicht genommener Sprung kostet gewöhnlich maximal einen
     Taktzyklus.  Ein falsch vorhergesagter Sprung kann das zehnfache
     kosten.  Unter dem Strich ist das an zeitkritischen Schleifen ein
     guter Deal.

Was ist die praktische Relevanz davon?  Im Moment keine.  Aber man kann
seinen Code schonmal umstellen, indem man in irgendein globales
Include-File folgenden Code tut:

  #ifdef __GNUC__
  #if (__GNUC__ < 3)
  #define __builtin_expect(foo,bar) (foo)
  #define expect(foo,bar) (foo)
  #endif
  #endif

und dann hat man den gcc-Fall schonmal abgedeckt.  Oder man prüft das in
configure, natürlich. ;)  Die __builtin_expect Variante ist ein
gcc-Alleingang, der sagt, daß man __builtin_ vor Builtins tun kann, und
die werden dann genutzt, auch wenn man pedantic ANSI mode anschaltet und
-fno-builtins sagt.  Die glibc 2.2.3 benutzt __builtin_expect übrigens
bereits an der einen oder anderen Stelle.  Ich denke mal, es kostet
nicht viel, die Fehlerbehandlung damit als "unwahrscheinlich" zu
markieren.  Ich werde das bei der diet libc jedenfalls heute mal an ein
paar strategischen Stellen einbauen.

Felix