copy_if 对比保存序列和使用复制

Question

为什么 copy_if 比复制

工作得慢

我目前正在研究我的 OpenGL 图形引擎。我试图找出将大量对象传递给 GPU 以进行实例化绘制的最佳方法。对我来说最大的问题是有些对象可能会死，所以我创建了一个小测试。

这是我正在测试的一个简单结构（在实际应用中它是位置 + 颜色等）

struct foo
{
   bool is_active = false;
   float value = 0.0f;
};

在此之后我创建了这些容器：

// All data
std::vector<foo> data_vector;
// Data that is only active
std::vector<foo> active_vector;
using distance_t = vector<foo>::iterator::difference_type;
// List of segments, so that if we have 10 elements where
// only the 5th is not active it is going to look like that
// { {0,5}, {6, 10} }
std::list<pair<distance_t, distance_t>> active_segments;

为向量中的 1,000,000 个元素预留 space。用所有真值填充 data_vector。为了忽略分配时间，也填充了列表。并用 high_resolution_clock

测试了这 3 个复制函数的速度

// First method
// For all true values *active_segments* has only one element with 
// {0, 1000000}
for_each(active_segments.begin(), active_segments.end(), 
              [&active_vector, data_vector](auto current)
    {
      copy(data_vector.begin() + current.first, 
      data_vector.begin() + current.second, 
      std::back_inserter(active_vector));
    });

// Second method
copy_if(data_vector.begin(), data_vector.end(),
        std::back_inserter(active_vector), 
        [](const foo &current)
        {
           return current.is_active;
        });

// Third method
copy(data_vector.begin(), data_vector.end(), 
     std::back_inserter(active_vector));

显然 copy 是最快的，为 18024 微秒。但令我惊讶的是 copy_if 比第一种方法（33278 微秒）更快（27777 微秒）。

我不明白为什么会这样。我想有一些额外的内存分配但提高了复制速度，但结果我的方法即使在最佳条件下也更慢。

Answer 1

在我看来，您有（至少）两个导致问题的因素的组合。

第一个是真正的问题：在您的 lambda 中，您通过值而不是通过引用来捕获 data_vector，因此您要复制整个输入数组，然后将数据从该副本复制到结果。

第二个主要针对基准测试：缓存预热。如果我修复 lambda 以便它通过引用捕获，您的方法 1 仍然运行s 比其他两种方法慢得多。但是如果我在它前面添加一个简单的缓存预热循环：

for (int i = 0; i < size; i++)
    active_vector.push_back(data_vector[i]);

...然后我可以运行之后的所有三个，并且它们都运行的速度足够接近相同的速度，以至于我无法再确定一个比另一个快。

另一方面，我相信这也表明整个练习有点毫无意义——尽管 copy_if 理论上应该比 copy 慢一点（在每个元素上基础），我找不到两者之间的任何显着差异。我怀疑在大多数情况下，内存带宽是限制因素，而用于确定是否复制某些内容的额外处理时间只是在噪音中丢失了。事实上，有时，第二个版本（使用 copy_if）最快，第三个（使用 copy）最慢：

method 1:   3,295us
method 2:   3,178us
method 3:   3,839us

只是为了它的价值，这里是我运行它的代码：

#include <algorithm>
#include <chrono>
#include <iostream>
#include <vector>
#include <list>
#include <utility>

struct foo
{
    bool is_active = true;
    float value = 0.0f;
};

int main() {

    const int size = 1'000'000;

    std::cout.imbue(std::locale(""));

    // All data
    std::vector<foo> data_vector(size);
    // Data that is only active
    std::vector<foo> active_vector;

    using distance_t = std::vector<foo>::iterator::difference_type;
    // List of segments, so that if we have 10 elements where
    // only the 5th is not active it is going to look like that
    // { {0,5}, {6, 10} }
    std::vector<std::pair<distance_t, distance_t>> active_segments;

    using namespace std::chrono;

    // Warm the cache:
    for (int i = 0; i < size; i++)
        active_vector.push_back(data_vector[i]);

    {
        active_segments.emplace_back(0, size);

        active_vector.clear();
        active_vector.reserve(size);
        auto begin = high_resolution_clock::now();

        for_each(active_segments.begin(), active_segments.end(),
            [&active_vector, &data_vector](auto current)
        {
            copy(data_vector.begin() + current.first,
                data_vector.begin() + current.second,
                std::back_inserter(active_vector));
        });
        auto end = high_resolution_clock::now();

        std::cout << "method 1:   " << duration_cast<microseconds>(end - begin).count() << "us\n";
    }

    {
        active_vector.clear();
        active_vector.reserve(size);
        auto begin = high_resolution_clock::now();
        // Second method
        copy_if(data_vector.begin(), data_vector.end(),
            std::back_inserter(active_vector),
            [](const foo &current)
        {
            return current.is_active;
        });
        auto end = high_resolution_clock::now();
        std::cout << "method 2:   " << duration_cast<microseconds>(end - begin).count() << "us\n";
    }

    {
        active_vector.clear();
        active_vector.reserve(size);
        auto begin = high_resolution_clock::now();
        copy(data_vector.begin(), data_vector.end(),
            std::back_inserter(active_vector));
        auto end = high_resolution_clock::now();

        std::cout << "method 3:   " << duration_cast<microseconds>(end - begin).count() << "us\n";
    }
}

还有一点可能应该考虑：您还需要 data_vector 中不再活跃的元素吗？如果您不再需要它们，可以使用 std::remove_if 将所有活动元素移动到集合的开头，然后从那里擦除到结尾。

auto e = std::remove_if(data_vector.begin(), data_vector.end(), 
                       [](auto const &e) {return e.is_active; });
data_vector.erase(e, data_vector.end());

每个元素被标记为活动或非活动的概率为 50% 的快速测试显示此运行ning 大约是复制活动元素速度的两倍。

copy_if 对比保存序列和使用复制

copy_if vs saving sequences and using copy

c++

vector

copy

stl-algorithm