c++ why ranges::find_if is so fast

Question

I changed this code:

auto it = chunks_.begin();
for (;; ++it) {
  if (it == chunks_.end()) {
    chunks_.emplace_back();
    alloc_chunk_ = &chunks_.back();
    break;
  }
  if (!it->is_filled()) {
    alloc_chunk_ = &*it;
    break;
  }
}

to this:

auto it = std::ranges::find_if(
            chunks_, [](const auto &chunk) { return !chunk.is_filled(); });
if (it == chunks_.end()) {
   chunks_.emplace_back();
   alloc_chunk_ = &chunks_.back();
} else {
   alloc_chunk_ = &*it;
}

and in both gcc 11.2 -O3, MSVC 19.32 /Ox, the second version was almost 20 times faster. (there was no other code change)

chunks_ is std::vector, and chunks_.size() was approximately 500, and the loop was executed for roughly 100,000 times. The first code was about 500ms, the second code was about 30ms (including all other codes, so clearly this part was the bottleneck)

These are Chunks:

struct Chunk {
    // ... other details ... 

    [[nodiscard]] bool is_filled() const { return !blocks_available_; }

    unsigned char data_[num_blocks_];
    unsigned char first_available_ = 0;
    unsigned char blocks_available_ = num_blocks_;
  };

Why the compiler optimizes std::ranges::find_if so fast?

user_6608708 · Answer

Most of difference is because of the time used for checking. In both example you have two check points: 1. if (it == chunks_.end()) and 2. if (!it->is_filled()).

The first example does this checks for every element of the container, (in worst case) but in the second example, the second check (inside the find function) is done for all elements of the container (again in worst case) but the first check is done just for the found iterator. I think you can change the code to follow same course. Then the difference should be minimized.

In addition the find algorithm uses range based for loop which is slightly faster than conventional for loops.

Edit: range based for-loops are syntactic sugar, has no impact on performance. Thanks to Morgan.

c++ why ranges::find_if is so fast

1 Answers