C++ 为什么 range::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_isstd::vector<Chunk>和chunks_.size()was 大约为 500，循环执行了大约 100,000 次。第一个代码大约 500ms，第二个代码大约 30ms（包括所有其他代码，所以显然这部分是瓶颈）

这些是Chunk：

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

大部分差异是由于检查所用的时间造成的。在这两个示例中，您都有两个检查点：1. if (it == chunks_.end())和 2. if (!it->is_filled())。

第一个示例对容器的每个元素进行检查（在最坏的情况下），但在第二个示例中，对容器的所有元素进行第二次检查（在查找函数内）（同样在最坏的情况下），但第一个检查仅针对找到的迭代器进行检查。我认为你可以更改代码以遵循相同的过程。那么差异应该最小化。

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

编辑：基于范围的 for 循环是语法糖，对性能没有影响。感谢摩根。