Weird performance difference between std::unordered_set::find and std::find

Question

I tried comparing performance of std::unordered_set::find and std::find. Contrary to my expectation and rule https://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-algorithm.html std::find was significantly faster

quick-bench with unordered_set

quick-bench screen

unorder_set contains ints so hash shouldn't be an issue. std::set::find acts as expected and is faster than std::find.

quick-bench with set Can anyone please explain this behaviour? Thank you

My guess is that your `std::unordered_set` is way too small for its advantageous time complexity to actually come in handy (it has only 12 elements). It's widely known that hash-sets/hash-maps have high constant factors, which could be the reason why `std::find` is running quicker than `std::unordered_set::find` for the input size of 12. Maybe try benchmarking over a larger set of elements? — Telescope, Jan 09 '21 at 01:23
12 items is way, way too short. The smarter searching algorithm doesn't have enough time to pay off the extra overhead that eventually makes it faster.. — user4581301, Jan 09 '21 at 01:26
Also, the ["rule"](https://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-algorithm.html) page linked in the post is about "*methods can take advantage of the order of the elements*", which doesn't exactly apply to `unordered_set`. — dxiv, Jan 09 '21 at 01:28
Similar to the point made in dxiv's comment: [Why is processing a sorted array faster than processing an unsorted array?](https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array) — user4581301, Jan 09 '21 at 01:30
@user4581301 It's not really related in this case. In your question, they were iterating over the same number of value. In a mine in a theory, we should have calculated hash quickly and go almost directly to the location in set find, while in std::find we have to iterate over every element till we reach the result. — Igor, Jan 09 '21 at 15:57
The takeaway from the link should be the more predictable the accesses, the faster the program could be. Ordered data like that in a linear search is pretty much, next, next, next.... The prediction is always right, so the program builds up a lot of inertia that the hash table needs to overcome in order to be faster. — user4581301, Jan 09 '21 at 17:43
@user4581301 There is nothing to be predicably about in internal find method. It goes directly to the answer. There is no iteration to predict. — Igor, Jan 09 '21 at 20:11

Jerry Coffin · Accepted Answer · 2021-01-09T07:18:53.190

Some of this also depends on the hardware and the implementation. But to get a clearer idea of what's going on, it can be useful to graph the time taken for a number of different sizes with each.

For this test, I used Microsoft's compiler, so some difference from clang/llvm isn't particularly surprising. Just for grins, I threw in an extra, testing std::lower_bound (after sorting the array, of course) in addition to find, set, and unordered_set.

I also did the testing a bit differently, generating random numbers to fill the container, and a set of 1000 random values to search for in the container. That's (probably) responsible for the less than linear growth at the right end for std:find. Microsoft's random number generator only has a 15-bit range, so with 100,000 elements, we're going to hit every value it can generate well before we've generated 100,000 values, so in the last test, the searching was limited by the range of values we could generate rather than the size of the array.

I suppose if I were ambitious, I'd rewrite it using a better random number generator with a larger range, but I think this is enough to establish the trends, and give a pretty good idea of the expected result from that modification.

Edit: corrected misalignment of data pasted into spreadsheet.

score 2 · Answer 2 · answered Jan 09 '21 at 02:13

The problem is that you chose a set that was too small.

Here is an example with a 1000 elements.

#include <unordered_set>
#include <set>

const static std::unordered_set<int> mySet {
0,
1,
2,
...
998,
999
};

static void UsingSetFind(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    auto it = mySet.find(435);
    benchmark::DoNotOptimize(it);
  }
}
// Register the function as a benchmark
BENCHMARK(UsingSetFind);

static void UsingStdFind(benchmark::State& state) {
  // Code before the loop is not measured
  for (auto _ : state) {
    auto it = std::find(mySet.begin(), mySet.end(), 345);
    benchmark::DoNotOptimize(it);
  }
}
BENCHMARK(UsingStdFind);

The difference is amazing

mySet.find(435)

Will search it like it was a hash table, really quick. While

std::find(mySet.begin(), mySet.end(), 345);

Will go 1 by 1.

`const static std::unordered_set mySet = [](){ std::unordered_set res; for (int i = 0; i != 1000; ++i) {res.insert(i); } return res; }();` instead of manually filling the set :) — Jarod42, Jan 12 '21 at 22:50

Weird performance difference between std::unordered_set::find and std::find

2 Answers2