C - 为什么固定大小的数组比动态分配的数组执行得慢得多？

Question

我有一个包含超过 400 万行的 csv，我正在将其加载到数组中。

csv：欧元兑美元，20010102,230100,0.9507,0.9507,0.9507,0.9507,4

此操作大约需要 3.5 分钟。

...

typedef struct Rates_t
{
  char open[7];
  char high[7];
  char low[7];
  char close[7];
} Rates_t;

void Substr(char *src, char **dst, int start, int length)
{
  char *ptr1 = *dst;
  char *ptr2 = src+start;

  int i;
  for (i = 0; i < length; i++)
  {
    *(ptr1 + i) = *(ptr2 + i);
  }
  (*dst)[length] = '[=10=]';
}

void FillRates(char *tmp, char *price)
{
  Substr(tmp, &price, 0, 6);
}

bool BacktestServer()
{  
  ...

  Rates_t r = { {0}, {0}, {0}, {0} };
  Rates_t *rates = &r;
  rates = (Rates_t *) malloc(sizeof(Rates_t));

  FILE *f;
  if (!(f = fopen("EURUSD.txt", "r"))) {
    fprintf(stderr, "Unable to open 'EURUSD.txt' for reading.\n");
    exit(1);
  }

  ...

  while (fgets(line, 72, f))
  {
    tmp = line;

    for (skip = 0; skip < 3; skip++)
    {
      tmp = strchr(tmp, ',');
      tmp++;
    }

    sz += sizeof(Rates_t);
    rates = (Rates_t *) realloc(rates, sz);

    FillRates(tmp, rates[i].open);
    tmp = strchr(tmp, ',');
    tmp++;

    FillRates(tmp, rates[i].high);
    tmp = strchr(tmp, ',');
    tmp++;

    FillRates(tmp, rates[i].low);
    tmp = strchr(tmp, ',');
    tmp++;

    FillRates(tmp, rates[i].close);

    i++;

    free(line);
    line = NULL;
    line = (char *) malloc(72 * sizeof(char));
  }

  ...

}

这大约需要 1 分钟。

...

typedef struct Rates_t
{
  char *open;
  char *high;
  char *low;
  char *close;
} Rates_t;

void Substr(char *src, char **dst, int start, int length)
{
  char *ptr1 = *dst;
  char *ptr2 = src+start;

  int i;
  for (i = 0; i < length; i++)
  {
    *(ptr1 + i) = *(ptr2 + i);
  }
  (*dst)[length] = '[=11=]';
}

void FillRates(char *tmp, char *price)
{
  Substr(tmp, &price, 0, 6);
}

bool BacktestServer()
{  
  ...    

  Rates_t r = { NULL, NULL, NULL, NULL };
  Rates_t *rates = &r;
  rates = (Rates_t *) malloc(sizeof(Rates_t));

  FILE *f;
  if (!(f = fopen("EURUSD.txt", "r"))) {
    fprintf(stderr, "Unable to open 'EURUSD.txt' for reading.\n");
    exit(1);
  }

  ...

  while (fgets(line, 72, f))
  {
    tmp = line;

    for (skip = 0; skip < 3; skip++)
    {
      tmp = strchr(tmp, ',');
      tmp++;
    }

    sz += sizeof(Rates_t);
    rates = (Rates_t *) realloc(rates, sz);

    rates[i].open = (char *) malloc(7 * sizeof(char));
    FillRates(tmp, rates[i].open);

    tmp = strchr(tmp, ',');
    tmp++;

    rates[i].high = (char *) malloc(7 * sizeof(char));
    FillRates(tmp, rates[i].high);

    tmp = strchr(tmp, ',');
    tmp++;

    rates[i].low = (char *) malloc(7 * sizeof(char));
    FillRates(tmp, rates[i].low);

    tmp = strchr(tmp, ',');
    tmp++;

    rates[i].close = (char *) malloc(7 * sizeof(char));
    FillRates(tmp, rates[i].close);

    i++;

    free(line);
    line = NULL;
    line = (char *) malloc(72 * sizeof(char));
  }

  ...

}

使用 memcpy 或 snprintf，程序会多几秒钟。

void Substr(char *src, char **dst, int start, int length)
{
  memcpy(*dst, src+start, length);
  (*dst)[length] = '[=12=]';
}
void Substr(char *src, char **dst, int start, int length)
{
  snprintf(*dst, length + 1, "%s", src+start);
  (*dst)[length] = '[=12=]';
}

从网上的共识来看，静态数组应该比动态数组快。如果有人需要更多信息，我将编辑 post 以实现该效果。

更新：

我没有按照建议将分配增加到 2，而是增加到 4096，我仍然得到与动态数组版本相同的结果，大约一分钟或更短时间。静态数组版本已减少到约 2.75 分钟。

初始分配：

int sz = 256 * sizeof(Rates_t);
rates = (Rates_t *) malloc(sz);

重新分配：

if (realloc_count == 256)
{
  sz += 256 * sizeof(Rates_t);
  rates = (Rates_t *) realloc(rates, sz);
  realloc_count = 0;
}
realloc_count++;

我在 64 位 Windows 机器上，但我通过 cygwin gcc 编译 32 位程序。另一方面，在 VM 中的 64 位 Linux 上，速度明显要低得多，但速度是相反的。动态分配的版本比静态版本需要更长的时间。在 Linux，动态内存 = ~20-30 秒，静态 = ~15 秒。在 Linux @1、2、256、4096 或 524,288 上，速度几乎没有变化。当我在 cygwin 上将分配增加到 524,288 时，静态分配得到 ~6 秒，动态分配得到 ~8 秒。

Answer 1

我很惊讶它会产生如此大的不同，但由于您 realloc() 读取每行数据的 rates 数组，因此复制该数组的成本很可能往往是罪魁祸首。如果目标是 32 位机器，包含完整数组的 Rates_t 结构可能大约是仅包含指针的 Rates_t 结构大小的两倍。

正如 JS1 在评论中提到的那样，预先适当调整数组的大小（或者如果您不知道它需要多大，则重新分配更大的块）应该会使运行时差消失。

Answer 2

一个区别是在重新分配期间复制的数据量。在第一种情况下，代码 realloc 是一个大小为 28 的结构数组，而不是在 ram / 缓存友好边界上。在第二种情况下，代码 realloc 是一个大小为 16 的结构数组，它位于 ram / 缓存友好边界上，但随后它执行 4 个 malloc（这些不会被重新分配）。

我想知道您将第一种情况下的字符数组大小从 7 更改为 8 是否会有帮助。

我也想知道这是否是在 64 位模式（64 位指针）下完成的，差异是否相似。

C - 为什么固定大小的数组比动态分配的数组执行得慢得多？

C - Why is a fixed size array performing much slower than a dynamically allocated array?

c

arrays

malloc