是否更快地访问静态或动态分配的内存？

Question

在C中有两种分配全局数组的方法:

1. 静态

   char data[65536];
   

2. 动态

   char *data;
   …
   data = (char*)malloc(65536);  /* or whatever size */
   

问题是,哪种方法有更好的表现？多少钱？

理解它,第一种方法应该更快.

因为使用第二种方法,要访问数组,每次访问时都必须取消引用元素的地址,如下所示:

1. 读取data包含指向数组开头的指针的变量
2. 计算特定元素的偏移量
3. 访问元素

使用第一种方法,编译器将data变量的地址硬编码到代码中,跳过第一步,因此我们有:

1. 从编译时定义的固定地址计算特定元素的偏移量
2. 访问数组的元素

每次存储器访问相当于大约40个CPU时钟周期,因此,使用动态分配,特别是对于不频繁的读取,与静态分配相比可以显着降低性能,因为data可以通过一些更频繁访问的变量从缓存中清除变量.相反,解除引用静态分配的全局变量的成本是0,因为它的地址已经在代码中进行了硬编码.

它是否正确？

Answer 1

人们应该始终确定基准.但是,暂时忽略缓存的影响,效率可能取决于你偶尔如何访问缓存.在这里,考虑char data_s[65536]和char *data_p = malloc(65536)

如果访问是零星的,静态/全局将稍微加快:

// slower because we must fetch data_p and then store
void
datasetp(int idx,char val)
{

    data_p[idx] = val;
}

// faster because we can store directly
void
datasets(int idx,char val)
{

    data_s[idx] = val;
}

现在,如果我们考虑缓存,datasetp并且datasets[在第一次访问之后]将大致相同,因为提取data_p将从缓存中实现[无法保证,但很可能],因此时间差异要小得多.

但是,当在紧密循环中访问数据时,它们将大致相同,因为编译器[optimizer]将data_p在循环开始时预取并将其放入寄存器:

void
datasetalls(char val)
{
    int idx;

    for (idx = 0;  idx < 65536;  ++idx)
        data_s[idx] = val;
}

void
datasetallp(char val)
{
    int idx;

    for (idx = 0;  idx < 65536;  ++idx)
        data_p[idx] = val;
}

void
datasetallp_optimized(char val)
{
    int idx;
    register char *reg;

    // the optimizer will generate the equivalent code to this
    reg = data_p;

    for (idx = 0;  idx < 65536;  ++idx)
        reg[idx] = val;
}

如果访问是如此零散以至于data_p从缓存中逐出,则性能差异并不重要,因为对[或者]数组的访问很少.因此,不是代码调整的目标.

如果发生这样的驱逐,实际数据阵列也很可能被驱逐.

一个更大的数组可能会产生更多的影响(例如,如果不是65536,我们有100000000,那么仅仅遍历将逐出data_p,当我们到达数组的末尾时,最左边的条目将被逐出.

但是,在这种情况下,额外提取data_p将是0.000001%的开销.

因此,它有助于对特定用例/访问模式进行基准测试(或建模).

更新:

基于一些进一步的实验[通过由Peter评论触发]时,datasetallp函数并没有优化到相当于datasetallp_optimized对某些条件下,由于严格别名的考虑.

因为数组是char[或unsigned char],所以编译器会data_p在每次循环迭代时生成一个fetch .请注意,如果数组不是 char(例如int),则优化确实发生并且data_p仅被提取一次,因为char可以别名,但int更有限.

如果我们改变char *data_p,char *restrict data_p我们得到优化的行为.添加restrict告诉编译器data_p将不会别名任何东西[甚至本身],因此它是安全的优化提取.

个人说明:虽然我明白这一点,对我来说,这似乎愚蠢的认为没有 restrict,编译器必须假定,data_p可以别名回到本身.虽然我确定还有其他[同样做作]的例子,但我能想到的唯一一个例子是data_p指向自身或者data_p是结构的一部分:

// simplest
char *data_p = malloc(65536);
data_p = (void *) &data_p;

// closer to real world
struct mystruct {
    ...
    char *data_p;
    ...
};
struct mystruct mystruct;
mystruct.data_p = (void *) &mystruct;

这些将是获取优化错误的情况.但是,IMO,这些与我们一直在处理的简单案例有所区别.至少,结构版本.并且,如果程序员应该做第一个,IMO,他们得到他们应得的[并且编译器应该允许获取优化].

对于我自己来说,我总是手工编写相当于datasetallp_optimized[sans register]的代码,所以我通常不会看到多重"问题"[如果你愿意]太多.我总是相信"给编译器一个有用的提示",因此我只是公理化地做这件事.它告诉编译器和另一个程序员意图是" data_p只获取一次".

此外,使用输入时不会出现多重捕获问题data_p[因为我们没有修改任何东西,别名不是考虑因素]:

// does fetch of data_p once at loop start
int
datasumallp(void)
{
    int idx;
    int sum;

    sum = 0;
    for (idx = 0;  idx < 65536;  ++idx)
        sum += data_p[idx];

    return sum;
}

但是,尽管它可以是相当普遍的,"硬接线"具有显式阵列基本数组运算函数[ 要么 data_s或data_p]通常比传递数组地址作为参数不太有用.

附注: clang将优化的一些使用功能data_s到memset调用,因此,在实验过程中,我修改了代码示例略有防止这种情况.

void
dataincallx(array_t *data,int val)
{
    int idx;

    for (idx = 0;  idx < 65536;  ++idx)
        data[idx] = val + idx;
}

这并没有从multifetch问题的困扰.也就是说,dataincallx(data_s,17)并dataincallx(data_p,37)使用相同的[初始额外data_p提取].这更可能是人们通常可以使用的[更好的代码重用等].

所以,区别data_s和data_p变得更加有点没有实际意义.与明智地使用restrict[或使用除了char] 以外的类型相结合,data_p可以将获取开销最小化到不太考虑的程度.

现在,它更多地涉及选择固定大小阵列或动态分配阵列的架构/设计选择.其他人指出了权衡.

这是用例依赖的.

如果我们有数量有限的数组函数,但是有大量不同的数组,那么将数组地址传递给函数是一个明显的赢家.

但是,如果我们有大量的数组操作函数并且[比较]一个数组(例如[2D]数组是游戏板或网格),那么每个函数可能更好地直接引用全局[ data_s或者data_p].

Answer 2

计算偏移量不是一个很大的性能问题.您必须考虑如何在代码中实际使用该数组.您最有可能编写类似的东西data[i] = x;,然后无论data存储在何处,程序都必须加载基址并计算偏移量.

编译器可以在静态分配数组的情况下对地址进行硬编码的情况仅在您编写类似data[55] = x;可能不太可能的用例时发生.

无论如何,我们在这里和那里谈论几个CPU滴答声.这不是你应该通过尝试手动优化来追逐的东西.

每次存储器访问相当于大约40个CPU时钟周期

什么!？这是什么CPU？一些1960年以前的古代计算机？

关于高速缓冲存储器,这些问题可能更有效.静态分配的内存有可能更好地利用数据缓存,但这只是猜测,你必须考虑到一个非常具体的CPU才能进行讨论.

然而,静态和动态分配之间存在显着的性能差异,即分配本身.对于每次调用都会调用mallocOS API,而OS API又会运行搜索功能并通过堆查找空闲段.库还需要在内部跟踪该段的地址,以便在调用free()它时知道要释放多少内存.此外,您调用malloc/free越多,堆就越分割.