INFO: Dieses Forum nutzt Cookies...
Cookies sind für den Betrieb des Forums unverzichtbar. Mit der Nutzung des Forums erklärst Du dich damit einverstanden, dass wir Cookies verwenden.

Es wird in jedem Fall ein Cookie gesetzt um diesen Hinweis nicht mehr zu erhalten. Desweiteren setzen wir Google Adsense und Google Analytics ein.

Antwort schreiben 
 
Themabewertung:
  • 0 Bewertungen - 0 im Durchschnitt
  • 1
  • 2
  • 3
  • 4
  • 5
Laufzeitverhalten
13.05.2015, 16:05
Beitrag #1
Laufzeitverhalten
Moin zusammen. Ich habe ein paar Entdeckungen bzgl. der Laufzeit eines Algorithmus gemacht, die ich nicht ganz verstehe:

Ich habe eine Funktion geschrieben, die im Wesentlichen die Werte zweier Arrays multipliziert und das Produkt über alle Indizes addiert. Soweit so einfach.

Schreibe ich die Funktion in den den Hauptsketch und rufe sie in setup auf, hat sie eine Durchlaufzeit von 330µs (Arduino Due). Schreibe ich die Funktion in einen eigenen Tab und rufe sie ohne sonstige Veränderungen in setup auf, so läuft sie nur 190µs. Schreibe ich die Funktion in eine library, so läuft sie 380µs.

Dass die library länger braucht ist schade, aber das kann ich noch verstehen. Warum aber ist der zweite Fall so viel schneller als die anderen beiden?


Eine damit verbundene Frage: Ich habe beim Aufruf der Funktion etwas mit call-by-reference und call-by-value der verschiedenen Parameter gespielt und ebenfalls verschiedene Laufzeiten erhalten. Insbesondere war dabei call-by-reference nicht immer schneller, wie ich eigentlich vermutet hatte, da keine lokale Kopie angelegt werden muss.

Kann wer insgesamt auf die Sprünge helfen oder Literatur empfehlen, welche Formalitäten für eine Laufzeitminimierung einzuhalten sind?

Beste Grüße,
Laura Heart
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren
13.05.2015, 16:16
Beitrag #2
RE: Laufzeitverhalten
(13.05.2015 16:05)Laura schrieb:  Moin zusammen. Ich habe ein paar Entdeckungen bzgl. der Laufzeit eines Algorithmus gemacht, die ich nicht ganz verstehe:
Hi,
es kommt da immer auf Details an. Am besten, Du lieferst mal das Coding, inklusive das Coding, mit welchem Du die Laufzeit misst.
Bei den Call-By-Reference vs. Call-By-Value kommt es auch darauf an, was für einen Datentyp die referenzierten Werte haben. Wenn Du z.B. nur ein Byte hast und das per Call-By-Reference übergibst, dann muss das System zwei bis vier Byte kopieren (ich glaube, es gibt keinen 64-Bit-Arduino, oder?).
Außerdem kostet die Dereferenzierung auch Zeit. D.h. je öfter man zugreift, desto schneller dürfte Call-By-Value werden.
Bei Arrays muss man noch beachten, dass ja nur ein Zeiger auf das erste Element übergeben wird. Wenn man dann nochmal Call-By-Reference macht, dann ist das ein Zeiger auf einen Zeiger.
Gruß,
Thorsten

Falls ich mit einer Antwort helfen konnte, wuerde ich mich freuen, ein paar Fotos oder auch ein kleines Filmchen des zugehoerigen Projekts zu sehen.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren
13.05.2015, 16:45
Beitrag #3
RE: Laufzeitverhalten
Hi,

die Zeit messe ich so:

Code:
Serial.println(micros());
funktionsaufruf();
Serial.println(micros());

Mir ist bewusst dass das keine statistisch gesicherte Messung ist. Deiner Anmerkung bzgl. Zeiger auf Zeiger und der Zeit fürs Dereferenzieren bin ich nachgegangen und habe das per call-by-reference übergebene Array zu in ein lokales abgelegt zunächst ohne dieses zu verwenden. Dies hat die Laufzeit um 70µs gesenkt (alles mehrfach gemessen). Sobald ich das lokale Array dann aber tatsächlich verwendet habe zur Bildung der Summe von Produkten mittels for-Schleife, hat dies die Laufzeit gegenüber der ursprünglichen Variante des Zugriffs per doppelten Zeiger sogar noch erhöht. Ich bin sehr verwundert.

Gleiches passiert, wenn das Array Membervariable eines Objektes ist. call-by-reference des gesamten Objektes ist schneller als call-by-value des gesamten Objektes. Speichere ich das Array dann in einem lokalen Array ohne dies tatsächlich zu verwenden, so ist dies am schnellsten.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren
13.05.2015, 17:09 (Dieser Beitrag wurde zuletzt bearbeitet: 13.05.2015 17:44 von HaWe.)
Beitrag #4
RE: Laufzeitverhalten
Zitat:Speichere ich das Array dann in einem lokalen Array ohne dies tatsächlich zu verwenden, so ist dies am schnellsten.

Das wundert mich nicht. Wink
Arrays (oder alle sonstige Variablen (!!) ), denen nur Werte zugewiesen werden, die aber nie verwendet werden, werden (häufig ? meist? immer?) vom C-Compiler komplett herausoptimiert, d.h. der Code wird faktisch gelöscht.
Aber selbst wenn sie verwendet werden, kann es passieren, dass der Compiler sie anfangs durch Konstanten ersetzt und spätere Änderungen einfach nicht mehr berücksichtigt.
Willst du dies vermeiden, musst du sie als
volatile
deklarieren.
Gerade für Geschwindigkeitsmessungen ist das essentiell !!

also z.B.

Code:
volatile int16_t   iarray[500];
volatile float     farray[500];
volatile int32_t   ivar, jvar, kvar;

Beispiele (aus dem web: http://de.wikipedia.org/wiki/Volatile_%2...matik%29):

ohne den Zusatz volatile könnte der Compiler die Schleife im folgenden Programmausschnitt durch eine einfache Endlosschleife ersetzen und die Variable status wegoptimieren:

Code:
static volatile int status = 0;

void poll_status( void )
{
    while ( status == 0 )
        ;
}

In folgendem Beispiel könnte ohne volatile ein optimierender Compiler die bedingte Anweisung mit der Grußformel eliminieren.

Code:
#include <stdio.h>
#include <setjmp.h>

jmp_buf env;

int main ()
{
   volatile int a = 0;

   if (setjmp (env)){
      if (a)
     puts ("Hello World");
      return 0;
   }

   a = 1;

   longjmp (env, 1);
}
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren
13.05.2015, 18:11
Beitrag #5
RE: Laufzeitverhalten
Hallo Laura,
könntest Du mal das Coding zeigen? Textuelle Beschreibungen neigen dazu, Missverständnisse zu erzeugen.
Gruß,
Thorsten

Falls ich mit einer Antwort helfen konnte, wuerde ich mich freuen, ein paar Fotos oder auch ein kleines Filmchen des zugehoerigen Projekts zu sehen.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren
18.05.2015, 08:23
Beitrag #6
RE: Laufzeitverhalten
Hallo,

volatile hatte ich tatsächlich vorher nicht beachtet, danke für den Hinweis. Es führt jedoch zu keiner sichtbaren Veränderung in meinem Beispiel.

Der Code hat folgende Pseudostruktur:

Code:
void fkt(int A, int B){
//void fkt(int *A, int *B){
//void fkt(int &A, int &B){

//int lokalA = A ; int lokalB = B; //Pseudo!

for (int i = 0; i<100; i++){

for (int j = 0; j < 100; j++){

//Arraymultiplikationen und Summen von A und B oder lokalA und lokalB

}
}
}

Wie beschrieben treten hier bei den verschiedenen Varianten wie oben angedeutet sehr unterschiedliche Laufzeiten auf, wobei der Compiler der IDE die letzte Variante nur zulässt, wenn in der library verpackt, sicherlich mit gutem Grund. lokalA und lokalB stellen die bereits erwähnte lokale Kopie dar, deren anlegen ohne Verwendung im unteren Teil die Laufzeit verkürzt, Verwendung im unteren Teil aber die Laufzeit erhöht.[/code]
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren
18.05.2015, 08:58 (Dieser Beitrag wurde zuletzt bearbeitet: 18.05.2015 09:42 von HaWe.)
Beitrag #7
RE: Laufzeitverhalten
hallo,
ein wirklich kompletter Code, jetzt inkl. "volatile" Deklaration aller Variablen, wäre schön. Der Teufel ist bekanntlich ein Eichhörnchen...

Ansonsten verweise ich zur Syntax auf meinen HaWe Brickbench-Test,
http://www.mindstormsforum.de/viewtopic....772#p64772
der bereits auch für Arduino AVR (Mega) + ARM (Due) implementiert ist (allerdings werden für den Arraysort-Test lange Arrays verwendet, die den Uno-Speicher übersteigen und der daher für den Uno auskommentiert werden müsste). Du könntest deine Routinen ggf. auch darauf anwenden.

Arduino-Brickbench-Test-Sourcecode s. hier:
http://www.mindstormsforum.de/viewtopic....=15#p65463
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren
18.05.2015, 13:30
Beitrag #8
RE: Laufzeitverhalten
Hi,
wie HaWe schon angedeutet hat, kann man damit nicht viel anfangen. Koenntest Du mal folgendes liefern: (Mindestens) zwei komplette Sketche, inklusive des Codings, das die Laufzeiten misst. Also wirklich den ganzen Kram, den Du auf den Arduino laedst. Dazu dann noch eine Beschreibung, welche der Versionen wie schnell ist.
Dann kann man vielleicht was sagen.
Gruss,
Thorsten

Falls ich mit einer Antwort helfen konnte, wuerde ich mich freuen, ein paar Fotos oder auch ein kleines Filmchen des zugehoerigen Projekts zu sehen.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren
Antwort schreiben 


Gehe zu:


Benutzer, die gerade dieses Thema anschauen: 1 Gast/Gäste