c++ - copy_if 与保存序列和使用复制

Question

为什么 copy_if 比 copy 慢

我目前正在研究我的 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;

为 vector 中的 1,000,000 个元素保留空间。用所有真值填充 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 仍然比其他两种方法运行得慢得多。 但是如果我在它之前添加一个简单的缓存预热循环:

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

就其值(value)而言，这是我运行时的代码:

#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% 的概率将每个元素标记为事件或非事件的快速测试表明，这种运行速度大约是复制事件元素速度的两倍。