CODEWITHSUNDEEP
c++performancec++11vectorset
user2296145
user2296145

Reputation: 378

Why is a binary search over a sorted vector is slower than std::set find?

Here you can see the code, run it and see the times.

http://rextester.com/MNQZS47293

I get similar results on my machine (using the same version of MSVC), the lookup in the vector is slower than in the std::set.

I would expect the sorted vector version to be faster, due to better locality of the data (more cache friendly). In the worse case, I would expect them to be similar, because they both perform a binary search, but I cannot understand why the std::set is much faster than the sorted vector version.

Thank you very much

Edit: Sorry, I pasted the wrong link (I modified the code but forgot to copy the link) the old code was using an unordered_set, this code is using a set, and the question remains the same: Why is the binary search over a sorted vector slower than over a set? I've noticed that if the number of elements is large enough, then the sorted vector is faster, but I still cannot understand why the set can outperform the sorted vector for any number of elements.

Upvotes: 1

Views: 1330

Answers (2)

Captain Giraffe
Captain Giraffe

Reputation: 14705

For the updated question:

-O1 and -O2 gives the same performance for the two methods.

-Ox slows down the vector version.

Why this is, you need to look at the disassembly or at the details of the -Ox level. It has nothing to do with the algorithmic properties of set.find and lower_bound/binary_search.

Regarding the locality of data. A binary_search and a set::find has for reasonable implementations exactly the same locality of data. The set might even win with the data being read in a left-to-right fashion.

Upvotes: 1

Arun
Arun

Reputation: 20393

The linked code seem to use unordered_set, not set.

unordered_set is a hash table. There the search is not binary search. There, search performance depends on the hash function and the load factor.

Upvotes: 3

Related Questions