Krautkanal.com

Veröffentlicht am 2015-08-09 21:44:55 in /prog/

/prog/ 7538: Sprungvorhersage vs. indirekter Funktionsaufruf

antongenkin Avatar
antongenkin:#7538

Hallo Bernds,

Bernd spielt mit dem Gedanken, einen kleinen Interpreter mit Bytecode zu bauen. Er hat schon gehört, dass das Interpretieren der einzelnen Anweisungen mittels


for(anweisung in anweisungen):
  switch (anweisungen)
    case add:
      ...
    case div:
      ...
    case bla:
      ...
    ...


unnötig langsam sein könnte.

Bernd hat zu dem Thema nur irgendwelche komischen Hacks mittels computed gotos und Assembler gefunden, die er nicht gehen möchte, falls Schöneres möglich ist.

Das Nächstschönere (aber schon hässliche), was Bernd eingefallen ist, ist, die Anweisungen vor dem Ausführen in Funktionszeiger umzuwandeln, die auf parameter- und rückgabelose Funktionen wie z.B. add(), div(), etc. zeigen, die aber den Interpreterkontext kennen.

Diese könnten dann einfach per


for(anweisung in anweisungen):
  anweisung()


aufgerufen werden.

Jetzt weiß Bernd aber, dass Zeiger eine gewisse Größe (4 bis 8 mal so groß, wie normale char-Anweisungen?) haben und dass indirekte Funktionsaufrufe auch nicht umsonst sind.

Hat Bernd hiermit schon mal experimentiert und falls ja, was war das Ergebnis? Ist es gangbar?
Gibt es etwas, was dagegen spricht?

Oder ist das etwas, was man dann gegebenfalls mit einem Profiler untersuchen muss?

olgary Avatar
olgary:#7539

Dieser Bernd hat das mal bei dem dosbox normal core (nicht der dyncore) probiert. Dieser ist mit switch programmiert. Ich habe das auf Funktionspointeraufrufe umgestellt. Ergebnis: Etwas langsamer.

Ich glaube ganz leicht schneller als switch ist nur computed goto.

andina Avatar
andina:#7540

>>7539
Das hat Bernd befürchtet. Seie jener Bernd bedankt!

ggavrilo Avatar
ggavrilo:#7544

Warum sollte ein switch/case zu langsam sein? Allein von der Logik auf Prozessorebene kann ich mir nichts schnelleres vorstellen.

Am besten wäre es natürlich, wenn man die branch prediction beeinflussen kann, aber dann bist du wohl bei deinem computed goto.

shoaib253 Avatar
shoaib253:#7546

>>7544
Bernd sagte nicht zu langsam, sondern unnötig langsam.

axel_gillino Avatar
axel_gillino:#7547

>>7544
Nun, Bernd sieht es mittlerweile, so, dass das Problem eh nicht so krass ist, wie es schien, und dieser Artikel https://hal.inria.fr/hal-01100647/document impliziert, dass die CPUs noch etwas besser darin geworden sind.

Die in dem Zusammenhang genannten 10 - 20% an Leistungszuwachs sind es Bernd nicht wert, schlechtere Sprachen/GNU-Standardfeatures/verhunzten Code in Kauf zu nehmen.

to_soham Avatar
to_soham:#7552

Wie schon gesagt, sind Funktionszeiger langsamer als switch-Statements. Dazu ein Artikel, über den ich neulich mal gestolpert bin:
http://embeddedgurus.com/stack-overflow/2014/03/replacing-nested-switches-with-multi-dimensional-arrays-of-pointers-to-functions/

Eben gesehen, auf dem gleichen Blog: Aus Wartungsgründen sollte man auf die switch-Syntax verzichten und explizit if-else-Blöcke schreiben:
http://embeddedgurus.com/stack-overflow/2010/04/efficient-c-tip-12-be-wary-of-switch-statements/

BTW: Sprungvorhersagen haben bei meinem letzten Projekt komischerweise versagt.

keyuri85 Avatar
keyuri85:#7556

>>7552
>BTW: Sprungvorhersagen haben bei meinem letzten Projekt komischerweise versagt.

Wie meint Bernd dies? Dies waren aber keine kleinen ARMs oder Microcontroller, oder?

canapud Avatar
canapud:#7560

Gibt es irgendeinen Grund, daß OP es besser wissen will als der Compilierer? Die haben schon ganz interessante Techniken dafür eingebaut.

Man könnte ja darüber nachdenken, es ihm besonders leicht zu machen, aber ist ja nicht das Problem dieses Bernds hier.

Komputierte Gotos oder ähnliche Sperenzchen dürften jedenfalls ungeheuer langsam sein. Jedesmal ein Pipeline Neustart, grandios.

yassiryahya Avatar
yassiryahya:#7561

>>7560
this.

Wenn möglich (keine Lücken zB) wird das switch statment doch sowieso zu einem Array von pointern zu den code stellen.

hampusmalmberg Avatar
hampusmalmberg:#7569

>>7556
>Wie meint Bernd dies? Dies waren aber keine kleinen ARMs oder Microcontroller, oder?
Nee, war schon ein relativ moderner Computer. Bin OP von >>7396
Ich habe echt keine Ahnung, wie das passieren konnte, aber eine Anweisung, die (ich hab's nachgerechnet) in 99.9% der Fälle die selbe Abzweigung nimmt, hat die Methode gleich doppelt so lange brauchen lassen.

Shriiiiimp Avatar
Shriiiiimp:#7570

Dafür hat gcc so Pseudoanweisungen, du kannst also vermerken, daß der eine Zweig sehr wahrscheinlich ist.

johnriordan Avatar
johnriordan:#7573

>>7570
Wurde in dem Thread vorgeschlagen, war allerdings kein GCC.

thierrymeier_ Avatar
thierrymeier_:#7615

>>7560
>Gibt es irgendeinen Grund, daß OP es besser wissen will als der Compilierer?

Darf man Michael "Mike" Pall trauen, saugen Compilierer, wenn es um die compilisierung von Interpretern geht, da dies kein alltägliches Szenario ist...

mfacchinello Avatar
mfacchinello:#7626

Bytes kommen per Stream rein und Fallunterscheidung steht an?
Sowas braucht man ja NIE! Niemand hat die Absicht, ein PDF oder sonstwie strukturierte Datei einzulesen!