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

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

  • 静态

    char data[65536];
    
  • 动态

    char *data;
    …
    data = (char*)malloc(65536);  /* or whatever size */
    
  • 问题是,哪种方法有更好的性能? 并通过多少?

    据了解,第一种方法应该更快。

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

  • 读取包含指向数组开头的指针的变量data
  • 计算特定元素的偏移量
  • 访问元素
  • 通过第一种方法,编译器将data变量的地址硬编码到代码中,第一步被跳过,所以我们有:

  • 根据编译时定义的固定地址计算特定元素的偏移量
  • 访问数组的元素
  • 每个内存访问相当于大约40个CPU时钟周期,因此,使用动态分配,特别是对于不频繁的读取,可以比静态分配具有显着的性能下降,因为可以通过更频繁访问的变量从缓存清除data变量。 相反,解引用静态分配的全局变量的代价是0,因为它的地址已经在代码中被硬编码了。

    它是否正确?


    一个人应该总是基准确定。 但是,暂时忽略缓存的效果,效率可能取决于您如何偶尔访问这两者。 这里,考虑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;
    }
    

    现在,如果我们考虑缓存, datasetpdatasets将是大致相同的[第一次访问后],因为取的data_p将从缓存[没有保证,但可能]满足,因此时间差得多。


    但是,在紧密循环访问数据时,它们大致相同,因为编译器[优化程序]将在循环开始时预取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从缓存中被逐出,那么性能差异并不重要,因为访问[任一]数组的data_p并不高。 因此,不是代码调优的目标。

    如果发生这种驱逐,实际数据阵列很可能也会被驱逐。

    一个更大的数组可能会有更多的效果(例如,如果不是65536 ,我们有100000000 ,那么仅仅遍历就会驱逐data_p并且在我们到达数组末尾时,最左边的条目已经被驱逐。

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

    因此,它有助于对特定用例/访问模式进行基准测试[或模型测试]。


    更新:

    根据一些进一步的实验[由Peter的评论触发],由于严格的混叠考虑因素, datasetallp函数没有针对特定条件的datasetallp_optimized进行优化。

    由于数组是char [或unsigned char ],编译器会在每次循环迭代中生成data_p提取。 请注意,如果数组不是char (例如int ),优化就会发生并且data_p被提取一次,因为char可以data_p其他任何内容,但int更加受限。

    如果我们将char *data_p更改为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,他们得到他们应得的[编译器应该允许获取优化]。


    对于我自己,我总是手工编码等同于datasetallp_optimized [sans register ],所以我通常不会看到多重取指“问题”[如果您会]太多。 我一直相信“给编译器一个有用的提示”,关于我的意图,所以我只是这样做的公理。 它告诉编译器和另一个程序员,意图是“仅获取data_p一次”。


    此外,使用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_sdata_p ]“硬连线”原始数组操作函数通常不如将数组地址作为参数传递那么有用。

    注意: clang会将data_s某些函数优化为memset调用,因此,在实验过程中,我稍微修改了示例代码以防止出现这种情况。

    void
    dataincallx(array_t *data,int val)
    {
        int idx;
    
        for (idx = 0;  idx < 65536;  ++idx)
            data[idx] = val + idx;
    }
    

    这不会受到多重取指问题的影响。 也就是说, dataincallx(data_s,17)dataincallx(data_p,37)工作原理与[最初的额外data_p提取]相同。 这更可能是一般人可能使用的[更好的代码重用等]。


    因此, data_sdata_p之间的区别变得更加data_p 。 加上谨慎使用restrict [或者使用char以外的类型], data_p读取开销可以被最小化,以至于它并不是真正那么重要。

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

    这与用例有关。

    如果我们有数量有限的数组函数,但有大量不同的数组,将数组地址传递给这些函数显然是赢家。

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


    计算抵消不是一个很大的性能问题。 你必须考虑如何在代码中实际使用数组。 你很可能会写一些像data[i] = x; 然后无论data存储在哪里,程序都必须加载一个基地址并计算偏移量。

    编译器可以在静态分配数组的情况下对地址进行硬编码的场景只发生在你编写类似data[55] = x; 这可能是一个不太可能的用例。

    无论如何,我们在这里和那里讨论几个CPU tick。 这不是你应该尝试手动优化追求的东西。

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

    什么!? 那是什么CPU? 一些1960年以前的古代电脑?

    关于高速缓存,这些担忧可能更有效。 有可能静态分配的内存更好地利用数据缓存,但这只是推测,你必须有一个非常具体的CPU来进行讨论。


    然而,静态和动态分配之间存在显着的性能差异,这就是分配本身。 对于每次对malloc的调用,都会调用OS API,然后运行搜索函数浏览堆并查找空闲段。 库还需要在内部跟踪该段的地址,以便在调用free()时知道要释放多少内存。 而且,你调用malloc / free的次数越多,堆的分割就越多。


    我认为数据局部性比计算阵列的基地址要重要得多。 (我可以想象,访问指针内容的情况非常快,因为它位于寄存器中,而堆栈指针或文本段的偏移量是编译时间常量;访问寄存器可能会更快。)

    但真正的问题将是数据局部性,这通常是在性能严格的紧密循环中小心动态内存的原因。 如果你有更多的动态分配数据恰好接近你的数组,那么内存将保留在高速缓存中。 如果你的数据分散在不同时间分配的RAM上,你可能会有许多缓存未命中访问它们。 在这种情况下,如果可能的话,将它们静态分配(或在堆栈中)会更好。

    链接地址: http://www.djcxy.com/p/13885.html

    上一篇: Is accessing statically or dynamically allocated memory faster?

    下一篇: when memory will be released?