6

我正在编写一个 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;
}

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

我很遗憾地去分配了具有固定大小数组的所有东西。

现在令人震惊的是。

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

（当切片长度为 200 时，原始代码过去常常等待几分钟，在超过 300 时可能需要一个小时......现在它在切片长度为 70、80 时这样做......并且已经花费了几个小时说 120。仍然不是 200。）

唯一的问题是，现在切片被赋予与完整策略相同的内存（MAXBUFLEN 为 10000），但整体似乎根本没有耗尽内存。'top' 表明消耗的总内存非常适中，和以前一样，只有几十兆字节的范围。（当然，当我存储长度时，我并没有遍历整个内容，只是具有真实规则的部分。）

谁能帮忙解释一下为什么它突然变得这么慢？

4

1 回答 1

3

似乎当您将结构的大小固定为更大的大小（例如 10000 条规则）时，您的缓存位置可能会比原来的位置更差。您可以使用分析器（Valgrind 中的 oprofile 或 cachegrind）来查看缓存是否有问题。

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

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

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

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

于 2013-05-29T08:31:46.897 回答