Wieso ist std::find_if langsamer, wenn das gesuchte Prädikat nicht existiert?

Guten Abend,

mir ist heute aufgefallen, dass der std::find_if Algorithmus deutlich schneller ist, wenn sich ein gesuchtes Prädikat im Container befindet. Jetzt wollte ich euch mal fragen, wieso das so ist, bzw. an was das liegen könnte? Ich hätte erwartet, dass es genau andersherum ist.

#include <iostream>
#include <algorithm>
#include <chrono>
#include <iterator>
#include <vector>
using namespace std;

class stopwatch
{
	private:
    	chrono::time_point<chrono::high_resolution_clock> start;
    	chrono::time_point<chrono::high_resolution_clock> stop;
	public:
    	void start_watch()
    	{
        	start = chrono::high_resolution_clock::now();
    	}
    	void stop_watch()
    	{
        	stop = chrono::high_resolution_clock::now();
    	}
		unsigned elapsed() const
    	{
        	return chrono::duration_cast<std::chrono::microseconds>(stop-start).count();
    	}
};

struct variable
{
	unsigned id;
};
typedef vector<variable> container;
typedef container::iterator p;
container vars;

class find_by_id
{
	private:
		unsigned id;
	public:
		find_by_id(unsigned id) : id(id) {}
		bool operator()(const variable& var)
		{
			return var.id==id;
		}
};

vector<p> get_variables(const vector<unsigned>& wanted)
{
	vector<p> iters;
	for(vector<unsigned>::const_iterator it=wanted.cbegin(); it!=wanted.cend(); ++it)
	{
		p iter = find_if(vars.begin(),vars.end(),find_by_id(*it));

		if( iter!=vars.end())
			iters.push_back(iter);
	}
	return iters;
}

int main()
{
	stopwatch watch;
	const unsigned size = 100000; // 100.000

	// Variablen erzeugen.
	for(unsigned i=0; i<size; ++i)
	{
		variable var = {i};
		vars.push_back(var);
	}

	// Suche nach Variablen, die existieren.
	cout << '\n' << "Suche nach Variablen, die existieren...";
	vector<unsigned> wanted_existing;
	for(unsigned i=0; i<10000; ++i)
	{
		wanted_existing.push_back(8);
	}
	watch.start_watch();
	vector<p> wanted_vars = get_variables(wanted_existing);
	watch.stop_watch();

	cout << '\n' << "gefunden       : " << wanted_vars.size();
	cout << '\n' << "benoetigte zeit: " << watch.elapsed() << " microseconds";

	cout << '\n' << '\n';

	// Suche nach Variablen, die nicht existieren.
	cout << '\n' << "Suche nach Variablen, die nicht existieren...";
	vector<unsigned> wanted_not_existing;
	for(unsigned i=0; i<10000; ++i)
	{
		wanted_not_existing.push_back(-8);
	}
	watch.start_watch();
	wanted_vars = get_variables(wanted_not_existing);
	watch.stop_watch();

	cout << '\n' << "gefunden       : " << wanted_vars.size();
	cout << '\n' << "benoetigte zeit: " << watch.elapsed() << " microseconds";

	return 0;
}

Wenn ich in einem vector mit 100.000 Elementen nach 10.000 Prädikaten suche, die existieren, vergehen 2 Millisekunden. Existieren die 10.000 Prädikate jedoch nicht, vergehen 7 Sekunden.

Eckdaten:
- GCC 4.6.1 32-bit
- keine Optimierung
- Win7 64 bit
- i5-2500

Danke im Voraus.

Nymer

C++ Reference schrieb:

An iterator to the first element in the range for which the application of pred to it does not return false (zero).
If pred is false for all elements, the function returns last.

Das wäre mal meine Vermutung: Einmal wird fast sofort aufgehört, beim anderem Mal immer komplett durchgegangen.

(Ohne mit deinen Code im Detail angeguckt zu Haben.)

Fehlerhafte Optimierung (-O0) und doof gewählter Suchwert. Wie schnell kannst du 10000 mal hintereinander einen Wert finden, der an 9. Stelle in einem 100000 Elemente fassenden Vector liegt?
Ersetze 8 durch 80000, und kompiliere mit -march=native -O2, dann kommt das raus:

Suche nach Variablen, die existieren...
gefunden       : 10000
benoetigte zeit: 278698 microseconds

Suche nach Variablen, die nicht existieren...
gefunden       : 0
benoetigte zeit: 344645 microseconds

asc

Gugelmoser schrieb:

- keine Optimierung

Grundsätzlich: Performancevergleiche ohne Optimierungen sind ebenso Realitätsfern wie Messungen im Debugmodus.

Zeus

Find element in range
Returns an iterator to the first element in the range [first,last) for which applying pred to it, is true.

First Element is found, else go through range.
Erstes Element ist gefunden, sonst durchsuche den ganze Range.

Sobald ein Element gefunden ist, hört die Suche auf.

Sone

Zeus schrieb:

Sobald ein Element gefunden ist, hört die Suche auf.

Das ist ja mal sowas von selbstverständlich.
Tatsächlich muss immer Optimiert werden, weil Entwickler bei entsprechenden Entscheidungen immer annehmen das Optimiert wird.

Wenn du schnell wissen willst, ob ein Objekt existiert, dann ist ein Vector vermutlich der falsche Container.

Nymer schrieb:

Einmal wird fast sofort aufgehört, beim anderem Mal immer komplett durchgegangen.

Zeus schrieb:

First Element is found, else go through range. Erstes Element ist gefunden, sonst durchsuche den ganze Range.
Sobald ein Element gefunden ist, hört die Suche auf.

Ja natürlich, jetzt sehe ich es auch :). Danke, dass ihr Licht in die Sache gebracht habt.

arghonaut schrieb:

und kompiliere mit -march=native -O2

Danke für den Hinweis.