C++堆内存性能提升

Question

我正在编写一个需要大量堆内存的函数。是否可以告诉编译器这些数据将在特定的 for 循环中被频繁访问，从而提高性能（通过编译选项或类似选项）？

我无法使用堆栈的原因是我需要存储的元素数量很大，如果我尝试这样做，就会出现分段错误。

现在代码正在运行，但我认为它可以更快。

更新： 我正在做这样的事情

vector< set<uint> > vec(node_vec.size());
for(uint i = 0; i < node_vec.size(); i++)
  for(uint j = i+1; j < node_vec.size(); j++)
    // some computation, basic math, store the result in variable x
      if( x > threshold ) {
         vec[i].insert(j);
         vec[j].insert(i);
      }

一些细节：
- 我使用了 hash_set，几乎没有什么改进，除了 hash_set 并不在我用于模拟目的的所有机器上可用的事实
- 我尝试使用数组在堆栈上分配 vec，但是，正如我所说，如果元素数量太大，我可能会出现分段错误 如果

node_vec.size() 等于 k，其中 k 的顺序几千个中，我预计 vec 比 node_vec 大 4 或 5 倍。考虑到我必须多次运行代码，在这个数量级下，代码看起来很慢。当然，我使用多线程来并行化这些调用，但我无法让函数本身运行得比我现在看到的更快。

例如，是否可以在高速缓存中分配 vec 以进行快速数据检索或类似的操作？

Answer 1

我正在编写一个需要大量堆内存的函数...将在特定的 for 循环中频繁访问

这不是您可以在编译器级别真正优化的东西。我认为您担心的是您有很多内存可能“陈旧”（调出），但在特定时间点您将需要迭代所有内存，可能需要迭代几次，并且您不想要这些内存要调出到磁盘的页面。

您需要研究特定于平台的策略来提高性能。将页面保留在内存中可以通过 mlockall 或 VirtualLock 但您确实不需要这样做。不过，请确保您了解将应用程序的内存页锁定到 RAM 中的含义。您正在占用其他进程的内存。

您可能还想研究低碎片堆 （但是它可能与这个问题根本不相关）和 此页面描述了与for循环相关的缓存行。

后一页介绍了 CPU 在内存访问方面的工作原理（通常不必关心的细节）。

示例 1：内存访问和性能
与循环 1 相比，您预计循环 2 的运行速度要快多少？

int[] arr = new int[64 * 1024 * 1024];

// 循环1
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;

// 循环2
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

第一个循环将数组中的每个值乘以 3，第二个循环仅每 16 个值相乘。 第二个循环只完成第一个循环大约 6% 的工作，但在现代机器上，两个 for 循环花费的时间大约相同：80 毫秒和 78 毫秒分别在我的机器上。

Answer 2

更新

vector< set<uint> > vec(node_vec.size());
for(uint i = 0; i < node_vec.size(); i++)
  for(uint j = i+1; j < node_vec.size(); j++)
    // some computation, basic math, store the result in variable x
      if( x > threshold ) {
         vec[i].insert(j);
         vec[j].insert(i);
      }

这仍然没有显示出太多信息，因为我们无法知道条件 x > 出现的频率。阈值将为真。如果x > Threshold 通常为 true，那么 std::set 可能是瓶颈，因为它必须为您插入的每个 uint 进行动态内存分配。

而且我们不知道“某些计算”实际上意味着/做什么/是什么。如果它做得太多，或者做得不对，那可能会成为瓶颈。

我们不知道您需要如何访问结果。

不管怎样，凭直觉：

    vector<pair<int, int> > vec1;
    vector<pair<int, int> > vec2;

    for (uint i = 0; i < node_vec.size(); i++)
    {
        for (uint j = i+1; j < node_vec.size(); j++)
        {
            // some computation, basic math, store the result in variable x
            if (x > threshold)
            {
                vec1.push_back(make_pair(i, j));
                vec2.push_back(make_pair(j, i));
            }
        }
    }

如果你能以这种形式使用结果，那么你就完成了。否则你可以做一些后处理。只是不要再次将其复制到 std::set 中（显然）。尝试坚持使用 std::vector。例如，您可以像这样在向量中构建索引：

    // ...
    vector<int> index1 = build_index(node_vec.size(), vec1);
    vector<int> index2 = build_index(node_vec.size(), vec2);
    // ...
}    

vector<int> build_index(size_t count, vector<pair<int, int> > const& vec)
{
    vector<int> index(count, -1);

    size_t i = vec.size();
    do
    {
        i--;
        assert(vec[i].first >= 0);
        assert(vec[i].first < count);
        index[vec[i].first] = i;
    }
    while (i != 0);

    return index;
}

ps.: 我几乎确定您的循环不受内存限制。但不能确定......如果你没有向我们展示的“节点”真的很大，它可能仍然很大。

---

原始答案：

没有简单的 I_will_access_this_frequently_so_make_it_fast(void* ptr, size_t len) 类型的解决方案。

不过你可以做一些事情。

1. 确保编译器可以“看到”关键循环内调用的每个函数的实现。编译器能够“看到”实现所需的条件取决于编译器。不过，有一种方法可以确保：在循环之前的同一翻译单元中定义所有相关函数，并将它们声明为内联函数。

   这也意味着您不应该以任何方式在这些关键循环中调用“外部”函数。我所说的“外部”函数是指系统调用、运行时库内容或在 DLL/SO 中实现的内容。也不要调用虚函数，也不要使用函数指针。或者当然不要分配或释放内存（在关键循环内）。

2. 确保您使用最佳算法。如果算法的复杂度高于必要的程度，线性优化就没有意义。

3. 使用尽可能小的类型。例如，如果 signed char 可以完成这项工作，则不要使用 int。我通常不会推荐这样做，但是当处理大块内存时，它可以大大提高性能。特别是在非常紧密的循环中。

4. 如果您只是复制或填充内存，请使用 memcpy 或 memset。如果块大于大约 50 到 100 字节，则禁用这两个函数的固有版本。

5. 确保以缓存友好的方式访问数据。最佳方式是“流式传输”——即以升序或降序地址访问存储器。您可以一次“跳转”一些字节，但不要跳得太远。最糟糕的是随机访问一大块内存。例如，如果您必须处理二维矩阵（如位图图像），其中 p[0] 到 p[1] 是“向右”的一步（x + 1），请确保内部循环递增 x 并且外部增量 y。如果您以相反的方式进行操作，性能将会大大变差。

6. 如果你的指针是无别名的，你可以告诉编译器（如何完成取决于编译器）。如果您不知道无别名意味着什么，我建议您搜索网络和编译器的文档，因为解释超出了范围。

7. 如果合适，请使用内部 SIMD 指令。

8. 如果您知道不久的将来将需要哪些内存位置，请使用显式预取指令。

Answer 3

您不能使用编译器选项来做到这一点。根据您的使用情况（插入、随机访问、删除、排序等），您可能会获得更适合的容器。

Answer 4

编译器已经可以看到数据在循环内被频繁访问。

Answer 5

假设您在执行循环之前只从堆中分配一次数据，请注意，正如@lvella，内存就是内存，如果经常访问它，则应该在执行期间有效地缓存它。