堆解决方案优于堆栈

Question

我正在编写一个C模拟程序，在其中，给定要验证的规则序列，我们将其分解为"片段"并验证每个片段。(基本思想是顺序很重要，一条规则的实际意义受到它上面的一些规则的影响;我们可以用每条规则做一个"切片"，只有那些在它上面重叠的规则。然后我们验证这些切片，它们通常比整个序列小得多。)

我的问题如下。

我有一个结构体(策略)，它包含一个结构体(规则)数组和一个int(长度)。我最初的实现大量使用了malloc和realloc:

struct{
  struct rule *rules;
  int length;
}policy;
...
struct policy makePolicy(int length)
{
  struct policy newPolicy;
  newPolicy.rules = malloc(length * sizeof(struct rule));
  newPolicy.length = length;
  return newPolicy;
}
...
struct policy makeSlice(struct policy inPol, int rulePos)
{
  if(rulePos > inPol.length - 1){
    printf("Slice base outside policy n");
    exit(1);
   }
  struct slice = makePolicy(inPol.length);
  //create slice, loop counter gets stored in sliceLength
  slice.rules = realloc(slice.rules, sliceLength * sizeof(struct rule));
  slice.length = sliceLength;
  return slice;
}

由于这使用malloed内存，我假设它大量使用堆。现在我正在尝试移植到一个实验性的并行机器上，它没有malloc。

我遗憾地使用固定大小的数组来分配所有内容。

现在是令人震惊的。

新代码运行较慢。慢得多。

(原始代码在切片长度为200时连续等待几分钟，超过300时可能等待一个小时……当切片长度是70,80…花了几个小时，大概120分钟。)

唯一的问题是，现在给片提供了与完整策略相同的内存(MAXBUFLEN为10000)，但整个策略似乎根本没有耗尽内存。'top'表示所消耗的总内存相当适中，和以前一样只有几十兆字节。(当然，当我存储长度时，我不会循环遍历整个内容，只循环使用真正规则的部分。)

谁能帮我解释一下为什么它突然变慢了这么多?

Answer 1

似乎当您将结构体的大小固定为更大的大小(例如10000条规则)时，您的缓存局部性可能会比原始的要差得多。你可以使用分析器(oprofile或Valgrind中的cachegrind)来查看缓存是否存在问题。

在原始程序中，一条缓存线最多可以容纳8个struct policy(在具有64字节缓存线的32位机器上)。但在修改后的版本中，它只能保存一个，因为它现在比缓存行大小大得多。

在这种情况下，将length字段向上移动可以提高性能，因为现在length和前几个struct rule可以放入单个缓存行。

struct policy{
  int length;
  struct rule rules[10000];
};

要解决这个问题，您需要编写自己的自定义分配器来确保缓存局部性。如果您正在编写该程序的并行版本，还请记住将不同线程使用的内存隔离到不同的缓存行中，以避免缓存行争用。