Welche Variante arbeitet Effizienter

Shor-ty

Hallo zusammen,
ich hätte eine Frage bezüglich 'welche Methode arbeitet effizienter'. Dazu folgender kleiner Testcode (die Namespace lass ich mal weg):

#define forAll(Field, i) for (auto& i : Field);    // Reference
#define forMap(Field, i) for (auto  i : Field);    // No reference

//- Die Simikolon sind im Code nicht - das war ein Fehler von mir beim Tippen

map<string, double> myMap;

myMap["H2"] = 1;
myMap["O2"] = 1;
myMap["HO"] = 2;
myMap["CO"] = -1;

vector<string> species;

species.push_back("H2");
species.push_back("O2");
species.push_back("HO");
species.push_back("CO");

//- Variante 1
forAll(species, s)
{
    Info<< s << " = " << myMap.at(s) << endl;
}

//- Variante 2
forMap(myMap, entry)
{
    Info<< entry->first << " = " << entry->second << endl;
}

Die zweite Variante bietet den Vorteil, dass die Einträge auch definitiv vorhanden sind. Wenn bspw. in meinem species Container eine chemische Spezies ist, die nicht in der map ist, dann bekomm ich nen Fehler (auch klar); kommt aber bei mir nicht vor da das alles sauber ist (: . Allerdings weiß ich nicht welche Methode effizienter ist, da ich bei dem #define forMap keine Referenz habe sondern eine Kopie erstelle (sofer ich das richtig sehe). Bezüglich Effizienz gehts mir hauptsächlich darum, welche schneller arbeitet. Auch wenn das hier recht banal ist, wird das in meinem Programm mehrere hunder-tausend mal durchgeführt (iterativer Verbrennungslöser). Vielleicht hättet ihr ja noch andere Anregungen.

Um das Beispiel auf meine Anwendung zu übertragen (nur für das bessere Verständnis):

Variante 1

AFC::scalar AFC::ChemistryCalc::dH
(
    const int& r,
    const scalar& T,
    const List<word>& species
    const map<word, scalar>& nu,
    const Thermo& thermo
) const
{   
    scalar dH{0};

    forAll(species, s)
    {
        dH += thermo.H(s, T) * nu.at(s);
    }

    return dH;
}

Variante 2

AFC::scalar AFC::ChemistryCalc::dH
(
    const int& r,
    const scalar& T,
    const map<word, scalar>& nu,
    const Thermo& thermo
) const
{   
    scalar dH{0};

    forMap(nu, s)
    {
        dH += thermo.H(s->first, T) * s->second;
    }

    return dH;
}

Grüße Tobi

Was hindert dich im Mapfall daran, const auto& zu verwenden?
O(n log n) vs O(n) - was ist da wohl schneller?

1. denken
2. messen

Deine Makros sind - ach was solls, ich reg mich nur auf.

volkard

endl ist schlecht.

Shor-ty

manni66 schrieb:

Was hindert dich im Mapfall daran, const auto& zu verwenden?
O(n log n) vs O(n) - was ist da wohl schneller?

1. denken
2. messen

Deine Makros sind - ach was solls, ich reg mich nur auf.

Hi Manni,

du kannst mir gerne Vorschläge für die Makros geben. Ich bin leider nicht so ein Spezialist, wenns um solche Sachen geht, daher Frage ich ja. Auch wenn du dich aufregst (das sicherlich nicht meine Intension ist), danke für die Rückmeldung bezüglich const auto&. Das const hat bei mir gefehlt (ich Idiot).

Übrigens ohne konstruktive Aussagen bezüglich den Makros, kann ich auch nicht weiter lernen.

Ich werde beide Varianten mal "messen". Ich nehme an du meintest damit einfach, ein paar tausend Berechnungen und die Zeit messen.

@vokard, "endl" war nur gedanklich gedacht. Natürlich geb ich da nichts aus (siehe den Code weiter unten).

Th69

Der Code dürfte doch gar nicht kompilieren, da die Makros falsch deklariert sind (Semikolon am Ende)!
Und ich würde hier auch "const auto&" nehmen.

Shor-ty schrieb:

du kannst mir gerne Vorschläge für die Makros geben.

Was bringen dir die Macros, außer dass man erst mal nachgucken muss, was wirklich passiert? Also: lass diese Macros komplett weg! Noch dazu: bei Macros kann man leicht viel falsch machen. Ist das Semikolon zum Beispiel richtig?

Das const hat bei mir gefehlt (ich Idiot).

Vor allem fehlt dir auch das & bei dem forMap. Aber wie gesagt, wozu überhaupt als Macro?

Der Punkt ist doch, dass eines deiner Macros für Referenzen ist und das andere nicht, während die Namen aber nahelegen, dass das eine für "All" und das andere für Maps ist. Damit hat das aber nix zu tun.

Was spricht gegen:

for (const auto &entry : myMap) {
    Info<< entry->first << " = " << entry->second << endl;
}

Jeder weiß sofort, was gemeint ist. Niemand muss ein Macro nachgucken (auch du nicht).

Shor-ty

Hey, danke für die Antwort.
Die Makros stehen nicht direkt in der cpp Datei. Die steht in einer anderen Header Datei und sollte nur dem Zweck dienen zu veranschaulichen, was forAll und forMap steht. Ein Simikolon kommt da nicht hin, wie du schon erwähnt hast (Fehler beim Tippen von mir) (http://www.cplusplus.com/doc/tutorial/preprocessor/)

Das mit dem const hab ich jetzt umgesetzt weil ich da nen Denkfehler hatte. Den Code hatte ich von Stack-Overflow, als ich nach C++ loop through map using auto gesucht hatte. Da war das angegeben:

Using auto greatly simplifies the loop for C++11 : for(auto iterator = m.begin(); iterator != m.end(); iterator++)

Das es letztlich so viel einfach ist:

#define forMap(Field, i) for (const auto& i : Field)

Ist mir auch klar. Vielleicht war das die Sache, wieso sich Manni so aufgeregt hat. Wenn ja, dann verständlich. Und das Fehlende & sollte dann auch noch rein.

@wob, das mit dem forMap hab ich eingeführt da es mit dem forAll nicht geklappt hat. Allerdings kann ich das ja jetzt wieder umändern und nur ein Makro für alle Felder benutzen. Wie du erwähnt hast ist die Intension schon die, dass das forAll für alle gilt. Das man den Code direkt schreiben kann, und damit das leserlicher wird, stimm ich zu. Allerdings hab ich sehr viele von diesen forAll Sachen, die ich nicht jedesmal ausschreiben will. Daher das Makro (wenn auch nicht ganz sauber bis jetzt). Die Intension war definitiv das es nur ein Makro gibt, dass durch jeglichen Container etc. durchlaufen kann. Mit den maps hatte ich Probleme, daher hab ich das so schnell festgelegt, aufgrund der oben genannten Nennung in stack-overflow.

Mit den maps bin ich nicht so bewandert aber sehe einige große Vorteile bei meinen Berechnungen, daher bau ich gerade die maps mit ein. Auf anhieb ging das mit dem forAll nicht, daher hatte ich das mit dem forMap eingeführt, das ich ja jetzt durch eure Beiträge wieder rauswerfen kann und zudem das forAll verwenden werde.

Shor-ty

wob & Manni,

danke für eure Auskunft und dem Vorschlag const auto& zu verwenden. Hier noch die Korrektur (kein Pointer):

for (const auto& entry : myMap)
{
    Info<< entry.first << " = " << entry.second << endl;
}

Ein kleiner Test, wie es Manni vorgeschlagen hat:

int main()
{
    map<string, double> myMap;

    myMap["H2"] = 1;
    myMap["O2"] = 1;
    myMap["HO"] = 2;
    myMap["CO"] = -1;

    vector<string> species;

    species.push_back("H2");
    species.push_back("O2");
    species.push_back("HO");
    species.push_back("CO");

    const std::clock_t s1 = clock();
    for (int i=0; i< 2000000; i++)
    {
        //- Variante 1
        forAll(species, s)
        {
            scalar tmp{0};

            tmp *= myMap.at(s);
        }
    } 

    const scalar execTime = (clock()-s1) / (scalar) CLOCKS_PER_SEC; 
    Info<< "Time for Variante 1 = " << execTime << endl;

    const std::clock_t s2 = clock();
    for (int i=0; i< 2000000; i++)
    {
        //- Variante 2 (von stack-overflow)
        for(auto iterator = myMap.begin(); iterator != myMap.end(); iterator++)
        {
            scalar tmp{0};

            tmp *= iterator->second;
        }
    }

    const scalar execTime2 = (clock()-s2) / (scalar) CLOCKS_PER_SEC; 
    Info<< "Time for Variante 2  = " << execTime2 << endl;

    const std::clock_t s3 = clock();
    for (int i=0; i< 2000000; i++)
    {
        //- Variante 3 mit const auto& (Referenz)
        for (const auto& entry : myMap)
        {
            scalar tmp{0};

            tmp *= entry.second;
        }
    }

    const scalar execTime3 = (clock()-s3) / (scalar) CLOCKS_PER_SEC; 
    Info<< "Time for Variante 3  = " << execTime3 << endl;

    return 0;
}

Das Ergebnis ist eindeutig:

Time for Variante 1 = 3.3366
Time for Variante 2  = 2.23083
Time for Variante 3  = 1.24089

Danke an alle.

Kompilierst du mit angeschalteten Optimierungen?

Der Unterschied zwischen Variante 2 und 3 überrascht.

Wenn du

for(auto iterator = myMap.begin(); iterator != myMap.end(); iterator++)

durch

auto e = myMap.end();
for(auto iterator = myMap.begin(); iterator != e; ++iterator)

ersetzt, bekommst du dann immer noch einen Unterschied? Ansonsten sollten Variante 2 und 3 identisch sein. Eigentlich sollte der Optimierer das end hoffentlich automatisch aus der Loop ziehen können und das Post-Increment -> Pre-Increment kann er hoffentlich auch erkennen.

Über Variante 1 brauchen wir wohl nicht zu sprechen... Angenommen, du möchtest ein Telefonbuch abschreiben. Zusätzlich hast du eine Liste aller Namen. Was ist wohl schneller: das Telefonbuch durchzugehen und zeilenweise abzuschreiben oder die Namensliste durchzugehen und für jeden Namen im Telefonbuch nachzuschlagen (und das Telefonbuch danach wieder zuzuklappen).

Hallo wob,

ich bin nicht so in der Thematik drin wie du aber der Optimierer scheint beides nicht zu erkennen. Weder pre-post noch das end. Ich kompiliere ohne Optimierungen. Hier die Erweiterungen:

int main()
{
    const std::clock_t startTime = clock();
    map<string, double> myMap;

    myMap["H2"] = 1;
    myMap["O2"] = 1;
    myMap["HO"] = 2;
    myMap["CO"] = -1;

    vector<string> species;

    species.push_back("H2");
    species.push_back("O2");
    species.push_back("HO");
    species.push_back("CO");

    const std::clock_t s1 = clock();
    for (int i=0; i< 2000000; i++)
    {
        //- Variante 1
        forAll(species, s)
        {
            scalar tmp{0};

            tmp *= myMap.at(s);
        }
    }

    const scalar execTime = (clock()-s1) / (scalar) CLOCKS_PER_SEC;
    Info<< "Time for Variante 1 = " << execTime << endl;

    const std::clock_t s2 = clock();
    for (int i=0; i< 2000000; i++)
    {
        //- Variante 2 (von stack-overflow)
        for(auto iterator = myMap.begin(); iterator != myMap.end(); iterator++)
        {
            scalar tmp{0};

            tmp *= iterator->second;
        }
    }

    const scalar execTime2 = (clock()-s2) / (scalar) CLOCKS_PER_SEC;
    Info<< "Time for Variante 2  = " << execTime2 << endl;

    const std::clock_t s3 = clock();
    for (int i=0; i< 2000000; i++)
    {
        //- Variante 3 mit const auto& (Referenz)
        for (const auto& entry : myMap)
        {
            scalar tmp{0};

            tmp *= entry.second;
        }
    }

    const scalar execTime3 = (clock()-s3) / (scalar) CLOCKS_PER_SEC;
    Info<< "Time for Variante 3  = " << execTime3 << endl;

    Info<< "\nAnalyse wob\n";

    const std::clock_t s4 = clock();
    auto e = myMap.end();
    for (int i=0; i< 2000000; i++)
    {
        //- Variante 4, Vorschlag von wob (pre-increment + end)
	for(auto iterator = myMap.begin(); iterator != e; ++iterator)
        {
            scalar tmp{0};

            tmp *= iterator->second;
        }
    }

    const scalar execTime4 = (clock()-s4) / (scalar) CLOCKS_PER_SEC;
    Info<< "Time for Variante 4  = " << execTime4 << endl;

    const std::clock_t s5 = clock();
    for (int i=0; i< 2000000; i++)
    {
        //- Variante 5, post increment
	for(auto iterator = myMap.begin(); iterator != e; iterator++)
        {
            scalar tmp{0};

            tmp *= iterator->second;
        }
    }

    const scalar execTime5 = (clock()-s5) / (scalar) CLOCKS_PER_SEC;
    Info<< "Time for Variante 5  = " << execTime5 << endl;

    const std::clock_t s6 = clock();
    for (int i=0; i< 2000000; i++)
    {
        //- Variante 6, pre increment
	for(auto iterator = myMap.begin(); iterator != myMap.end(); ++iterator)
        {
            scalar tmp{0};

            tmp *= iterator->second;
        }
    }

    const scalar execTime6 = (clock()-s6) / (scalar) CLOCKS_PER_SEC;
    Info<< "Time for Variante 6  = " << execTime6 << endl;
}

Time for Variante 1 = 3.35009
Time for Variante 2  = 2.15383
Time for Variante 3  = 1.22922

Analyse wob

Time for Variante 4  = 1.04706   // End und pre increment manual
Time for Variante 5  = 1.53507   // post increment with given end manual
Time for Variante 6  = 1.65135   // pre increment manual

Jede Messung ohne Optimizer ist witzlos.

Ein guter Optimizer dürfte dein Testprogramm zu Nichts zusammenschrumpeln, da du die Ergebnisse der Berechnungen nicht verwendest.

Richtig messen ist auch nicht unbedingt trivial.

Was auch immer du erreichen willst - sieht stark nach Mikrooptimierung aus

1. ohne das du in deinen Benchmarks die "Werte" wenigstens in einer Dummy-Variable oder sowas addierst und das am Ende mit printf/main()-return ausgibts sieht du nur dem Optimierer bei der Arbeit zu - und wenn dir das nichts sagt ist der ganze Test völlig sinnfrei

2. bei diesen Wenigen Keys wird die linear Suche in einem Vector wohl immer schneller sein