Waarom is std::find_if zo veel sneller dan een loop?

[ikt]

Ik heb een vector van tuples waarin ik wel of geen item heb. Met een simpele

code:

bool isPresentinAddonImages_loop(Hash hash) {
    for (auto addonImage : addonImages) {
        if (std::get<0>(addonImage) == hash)
            return true;
    }
    return false;
}

Kom je er wel doorheen. Bij een gevonden voorwerp stopt het loopje. Alles prima. Nu heb ik een STL-manier gevonden om hetzelfde te doen, maar het is minder duidelijk dan de loop:

code:

bool isPresentinAddonImages_STL(Hash hash) {
    return addonImages.end() != std::find_if(addonImages.begin(), addonImages.end(), [&hash](const std::tuple<Hash, int, int, int>& element) {
        return std::get<0>(element) == hash;
    });
}

Ik heb een testje gemaakt, en in bijna alle omstandigheden is de STL-manier vele malen sneller.
~2x zo snel met real-life data (50 items) (~6000 ns vs ~12000 ns)
~5x zo snel met de "redelijk dekkend gevulde" data (400 items) (~12000 ns vs 62000 ns)
~7x zo snel met een exotischere hoeveelheid data (2000 items) (~42000 ns vs 310000 ns).

De testcode is hier. Gewoon in VS te compileren. Naampjes en types zijn vanuit het originele project geplukt.

Context:
Ik heb een map met afbeeldingen met namen van voertuigen. Deze namen hash ik en koppel ik aan een texture-ID, breedte en hoogte om op een later moment te kunnen laten zien. De functie met het opzoeken wordt gebruikt nadat een thread klaar is met het opzoeken van nieuwe/veranderde bestanden (afbeeldingen), dus wordt niet elke frame gebruikt. Wel gebruik ik soortgelijke vectors op andere plaatsen, dus waarschijnlijk schakel ik over naar std::find(_if).

Maar hoe komt het dus dat std::find_if zo verschrikkelijk snel is?

[user109731]

Wat als je een reference gebruikt in je for-loop, auto& addonImage?

[ikt]

JanDM schreef op vrijdag 7 juli 2017 @ 18:18:
Wat als je een reference gebruikt in je for-loop, auto& addonImage?

Oh, nog niet aan gedacht!

De tijd bij 2000 items gaat van ~31000 ns naar ~22000 ns. Wel een verbetering, maar met std::find gaat het toch sneller.

Overigens lijkt me dit niet al te snugger

C++:

bool isPresentinAddonImages(Hash hash, std::_Vector_iterator<std::_Vector_val<std::_Simple_types<std::tuple<Hash ,int, int, int>>>> *addonImageIt) {
    auto addonImage = std::find_if(addonImages.begin(), addonImages.end(), [&hash](const std::tuple<Hash, int, int, int>& element) {
        return std::get<0>(element) == hash;
    });
    return addonImages.end() != addonImage;
}

[Morrar]

Lijkt me dat die STL varianten op low level geïmplementeerd zijn en dus enorm geoptimaliseerd. Daarnaast zullen ze waarschijnlijk goed geparalleliseerd kunnen worden, wat met een for loop niet (altijd) gaat. Check voor de grap eens de belasting van je cores als je de code op een vrij grote set draait.

[DataGhost]

Hangt van je implementatie af, als ik op Coliru run zie ik ook met 2000 maar ~10% verschil (5632 vs 6292). Verder zou je afhankelijk van de rest van je requirements en operaties wellicht een map kunnen gebruiken, als je weinig inserts doet en veel lookups kom je min of meer op O(log n) in plaats van O(n) worst-case.

edit:
ik heb dus je include windows.h weggehaald en DWORD aangepast naar uint32_t om 'm aan de gang te krijgen.

[ Voor 16% gewijzigd door DataGhost op 07-07-2017 18:40 ]

[expor]

Als ik een release build doe ipv. debug build (in VS) is de loop 2x zo snel als STL bij mij. Enige wijziging die ik gedaan heb op je example is const auto& in de foreach, maar zonder die wijziging krijg ik dezelfde resultaten in release build. Bij debug build maakt dat verschil nog wel veel uit.

Release: STL 903ns, loop 602ns (bij multiple runs krijg ik bijna altijd deze verhouding, maar ook met regelmaat beide 602ns)
Debug: STL 46336ns, loop 256650ns

[ Voor 255% gewijzigd door expor op 07-07-2017 21:14 ]

[DJMaze]

Hoe zit het dan met de snelheid van een while loop? zoiets als:

C++:

bool isPresentinAddonImages_while(Hash hash) {
    vector<int>::const_iterator itv = addonImages.begin();
    while (itv != addonImages.end()) {
        if (itv == hash)
            return true;
        ++itv;
    }
    return false;
}

[ Voor 14% gewijzigd door DJMaze op 08-07-2017 02:20 ]

[johnkeates]

Kijk even naar compiler flags, maar ook intermediate output. Ik weet niet of je LLVM kan gebruiken maar de IR is meestal wel duidelijk over hoe ver je code geoptimaliseerd is.

[ThomasG]

Het komt hoogst waarschijnlijk doordat jouw for loop gebruikt maakt van checked iterators (ofwel, het controleert elke keer iteratie van de lus ingaat of hij niet out of bounds is), waarbij std::find_if unchecked is (loop als while (begin != end). Checked is veiliger, maar langzamer.

Edit: Als ik de voorbeeld code van isPresentinAddonImages_loop aanpas, is de snelheid ongeveer het zelfde:

C++:

bool isPresentinAddonImages_loop(Hash hash) {
    auto begin = addonImages.begin();
    auto end = addonImages.end();

    // Let wel, `end` is unchecked; `while (begin != addonImages.end())` niet.
    while (begin != end) {
        if (std::get<0>(*begin) == hash)
            return true;
        begin++;
    }
    return false;
}

[ Voor 38% gewijzigd door ThomasG op 08-07-2017 18:39 ]