Phänomen: Rechenzeit Funktionsaufrufe

[ab (Gast)]

Hallo Zusammen,

bin in den letzten Tagen auf ein Problem gestoßen, das ich mir nicht 
erklären kann. Vielleicht hat jemand von euch eine Idee.

Ich habe Rechenzeitmessungen durchgeführt und es hat sich 
herausgestellt, dass die Funktion beim ersten Aufruf mindestens doppelt 
so lang wie bei den weiteren Aufrufen. Es wird kein Initialisierungscode 
oder ähnliches durchlaufen. Gemessen wurde die Rechenzeit sowohl mit 
internem Timer als auch mit Oszilloskop an einem Pin. Ich habe es an 
zwei Prozessoren (ARM9, Nios) mit zwei Entwicklungsumgebungen probiert. 
Messungen wurden z.T. mit un ohne Cache gemacht. Es ändert sich zwar 
einiges an den Absolutwerten und auch das Verhältnis, allerdings ist der 
erste Aufruf IMMER signifikant länger.

Bisher ist mir so etwas nie aufgefallen, weiß jemand, was der Grund 
dafür ist?

Mfg
Alex

[Hellseher (Gast)]

In Zeile 12 das if umformulieren .

[B. S. (bestucki)]

Der Hellseher spricht die richtige Problematik an:
- Welche Programmiersprache?
- Welcher Compiler?
- Welcher Code? (Minimalbeispiel)
- Betrifft es alle Funktionen oder nur die eine?
- Andere besondere Umstände? (z.B. Interrupts die dazwischenfunken)

[Uwe (Gast)]

NAja die heutigen CPUs sind halt ganz schön komplex und eigenlich nicht 
mehr echtzeitfähig (deterministisch). Da sind halt nicht nur chaes 
sondern auch noch Sprungvorhersage Einheiten drinne. Es könnte halt sein 
das er beim ersten durchlauf merkt an welchen Stellen wieoft, wohin 
verzweigt wurde und er beim zweitenmal da schon weiß.

[Peter II (Gast)]

Uwe schrieb:
> Es könnte halt sein
> das er beim ersten durchlauf merkt an welchen Stellen wieoft, wohin
> verzweigt wurde und er beim zweitenmal da schon weiß.

nein die Künstliche Intelligenz ist in den aktuellen CPUs noch nicht 
enthalten. Cache könnte zwar eine auswirkung haben, aber die 
Sprungvorhersage ist meines wissens nicht lernfähig.

[Falk B. (falk)]

@ Uwe (Gast)

>NAja die heutigen CPUs sind halt ganz schön komplex

Ja.

>und eigenlich nicht
>mehr echtzeitfähig (deterministisch).

uhhh, da weden aber zwei völlig verschiedene Sachen zusammengerührt.

Auch komplexeste CPUs arbeiten VOLLKOMMEN deterministisch.

http://de.wikipedia.org/wiki/Determinismus_%28Algorithmus%29

Denn sonst würden sie nicht funktionieren. Das Problem ist jedoch, dass 
die Vorhersage über das Verhalten sehr komplex geworden ist und damit in 
vielen Anwendungen, die exaktes Zeitverhalten fordern, praktisch kaum 
vorhergesagt werden kann, es gibt zuviele Einflußgrößen und 
Übegrangsmöglichkeiten. Deutlich einfachere Automaten sind eben deutlich 
leichter und damit praktisch nutzbar vorhersagbar.

[Jan H. (j_hansen)]

Peter II schrieb:
> nein die Künstliche Intelligenz ist in den aktuellen CPUs noch nicht
> enthalten. Cache könnte zwar eine auswirkung haben, aber die
> Sprungvorhersage ist meines wissens nicht lernfähig.

Da sagt der Wikipedia-Artikel zur SPrungvorhersage aber etwas anderes.

[ab (Gast)]

Ups Sorry :-D.. Ich dachte ich hab alle Infos eingefügt.

Programmiersprache: C
Compiler: IAR 6.40 für die Tests auf dem ARM9, Nios II IDE 9.0SP2 GCC 
für den Nios
Betrifft alle Funktionen die ich ausprobiert habe. Also so an die 15.
Interrupts waren beim NIOS komplett aus, auf dem ARM war der 
Funktionsaufruf aus einem Interrupt mit der höchsten Priorität

Im folgenden Beispielcode mit einer Dummy Funktion. ACKh_OFF und ACKh_ON 
setzt den Output.

volatile xy;
void testfcn(void)
{
    int i=0;
    int k=0;
    int array[100];
    for(i=0;i<1;i++)
    {
        xy=i;
        array[0]=i;
        array[0]=xy;
    }
        for(k=0;k<1;k++)
    {
        xy=k;
        array[1]=k;
        array[1]=xy;
    }
}

int main()
{ 
    int i=0;
    ACKh_OFF;
    for(i=0;i<50;i++)
    {
      ACKh_OFF;
    }
    while (1)
    {
      ACKh_ON;
      testfcn();
      ACKh_OFF;
    }
  return 0;
}

Ich hoffe jetzt sinds genügend Infos?

Gruß
Alex

[Läubi .. (laeubi)]

Peter II schrieb:
> aber die Sprungvorhersage ist meines wissens nicht lernfähig.

Dann besser dein Wissen doch einfach auf: 
http://en.wikipedia.org/wiki/Branch_predictor

[Peter II (Gast)]

Läubi .. schrieb:
> Dann besser dein Wissen doch einfach auf:
> http://en.wikipedia.org/wiki/Branch_predictor

habe ich gerade nachgeholt. Die Frage ist ob diese CPU denn soetwas 
schon hat. Und das danach eine funktion doppelt so schnell ist nur wegen 
der Sprungvorhersage ist nun doch sehr unrealistisch.

[ab (Gast)]

Der verwendete NiosII/f hat "Dynamic branch prediction". ARM9 muss ich 
noch prüfen

[Läubi .. (laeubi)]

Der NIOS-II hat sowas, ARM vermutlich auch, die "Funktion" wird wohl 
komplett wegoptimiert, sodass ausschließlich der Rücksprung in der while 
zählt, und der wird sehr wohl von einem branchpredict profitieren (sogar 
wenn es nur ein sehr simpler 'last-taken' ist und kein statischer).

[Uwe (Gast)]

> uhhh, da weden aber zwei völlig verschiedene Sachen zusammengerührt.
Ich meinte deterministisches Zeitverhalten

[Der (Gast)]

Läubi .. schrieb:
> die "Funktion" wird wohl
> komplett wegoptimiert, sodass ausschließlich der Rücksprung in der while
> zählt

Daher sollte die Funktion ein paar volatiles enthalten.

[Peter II (Gast)]

Der schrieb:
> Daher sollte die Funktion ein paar volatiles enthalten.

hat sie doch

[ab (Gast)]

volatile ist vorhanden (siehe oben). Funktion wird nicht wegoptimiert. 
Ich habe den Assembler code vom NIOS angeschaut.

[Der (Gast)]

Peter II schrieb:
> Der schrieb:
>> Daher sollte die Funktion ein paar volatiles enthalten.
>
> hat sie doch

Stimmt, das habe ich übersehen.

[Peter D. (peda)]

volatile xy;
void testfcn(void)
{
    int i=0;
    int k=0;
    int array[100];
    for(i=0;i<1;i++)
    {
        xy=i;
        array[0]=i;
        array[0]=xy;
    }
        for(k=0;k<1;k++)
    {
        xy=k;
        array[1]=k;
        array[1]=xy;
    }
}

Der Compiler sollte das so optimieren:

volatile xy;
void testfcn(void)
{
        xy=0;
        xy;
        xy=0;
        xy;
}

Da ist also kaum Code übrig und dann ist der Cache laufzeit 
entscheidend.

[Peter II (Gast)]

nach der optimierung sollte eigentlich gar kein Sprung mehr vorhanden 
sein

> for(i=0;i<1;i++)

wird wohl komplett aufgelöst werden.

[ab (Gast)]

Ihr habt recht, ich hatte aber auch schon andere Werte > 1 drin.

Was die Cache Laufzeit angeht: da habe ich auch schon Tests dazu 
gemacht. Hatte am Anfang der Funktion eine Schleife die für einige 
Zyklen nichts gemacht hat, dann das Ausgangs-Bit getoggelt, und dann den 
eigentlichen Algorithmus abgearbeitet. So müsste ja der Cache wieder 
gefüllt sein, oder?

Werd mich mal eingehend mit der Branch prediction beschäftien. 
Vielleicht ist das wirklich die Lösung...

Sonnige Grüße aus dem Süden
Alex

[Ulrich (Gast)]

Eine mögliche Ursache könnten die lokalen Variablen: Das Reeservieren 
von Speicher für die loaklen Variablen kann davon abhängen was vorher an 
Speicher genutzt wurde.

Ohne sich den erzeugten ASM Code anzusehen ist das ganze aber ein 
relativ wildes raten.

[Peter II (Gast)]

Ulrich schrieb:
> Eine mögliche Ursache könnten die lokalen Variablen: Das Reeservieren
> von Speicher für die loaklen Variablen kann davon abhängen was vorher an
> Speicher genutzt wurde.

lokale Variabel werden doch auf den Stack gelegt, dabei ist egal was 
vorher vorhanden war.

[Läubi .. (laeubi)]

ab schrieb:
> So müsste ja

Warum? Man sollte, wenn man irgendwas messen will (und erst recht wenn 
man auf scheinbare Widersprüche trifft) verifizieren.
Die komplette Architektur des NIOS-II ist dokumentiert, auch Caches, 
Branch-Predict und man kann das ganze sogar simulieren lassen... Also 
kein Grund zu spekulieren.

Der schrieb:
> Stimmt, das habe ich übersehen

Ich auch, trotzdem ist die Laufzeit konstant wie Peter Dannegger 
schriebt, vermutlich wird sogar der Funktionsaufruf wegoptimiert, selbst 
bei > 1 kann der Compiler durch loop-unrolling Sprünge vermeiden.

ab schrieb:
> eine Schleife die für einige Zyklen nichts gemacht hat

Wenn wirklich "nichts" gemacht wird, wird auch diese wegoptimiert, auch 
ist hier weniger der Instructioncache interessant sondern der 
Branch-Predict.

[ab (Gast)]

Ich wollte nur kurz informieren, dass es der (Instruction) Cache war, 
der hier die Unterschiede in der Rechenzeit verursacht hat. Bei komplett 
abgeschaltetem Cache oder Aufruf anderweitiger Funktionen, die zu einer 
Cache-Umwälzung geführt haben, war die Rechenzeit für die 
Funktionsaufrufe gleich (langsam).

Danke für die Unterstützung hier im Forum!

Gruß
Alex