c++为什么ranges::find_if这么快?

Question

我修改了这个代码:

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;
}
}

:

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;
}

和在gcc 11.2 -O3、MSVC 19.32/Ox中，第二个版本几乎快了20倍。(没有其他代码更改)

chunks_为std::vector<Chunk>,chunks_.size()约为500，循环执行约100,000次。第一个代码约为500ms，第二个代码约为30ms(包括所有其他代码，因此显然这部分是瓶颈)

这些是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_;
};

为什么编译器优化std::ranges::find_if这么快?

Answer 1

差异主要是由于检查所用的时间不同。在这两个例子中，你有两个检查点:if (it == chunks_.end())和2。if (!it->is_filled()).

第一个例子检查容器的每个元素(在最坏的情况下)，但在第二个例子中，第二次检查(在find函数中)是对容器的所有元素进行的(同样是在最坏的情况下)，但第一次检查只对查找到的迭代器进行。我认为您可以更改代码以遵循相同的过程。那么差额应该最小化。

此外，find算法使用基于范围的for循环，这比传统的for循环略快。

编辑:基于范围的for循环是语法糖，对性能没有影响。多亏了Morgan。