动态内存分配是否会降低性能？

Question

我浏览了Bjarne Stroustrup的视频,在那里他解释了为什么要避免链接列表.

基本上,当使用指针动态分配内存时,有更多的缓存未命中会降低性能.

但是,如果将相同的事情应用于非线性数据结构(如树和图形),那么同样的事情是否成立？

因为,在树中,我们每个节点都有两个指针,并且指针的随机移动也会导致缓存未命中.

但是,树已被证明比线性数据结构表现更好.当然,树也可以使用数组实现,但同样存在大量的内存消耗.

我的问题是:动态内存分配是否良好？

Answer 1

他试图说明小对象之间的大量间接会降低代码的缓存效率.您无法完全避免链接结构,但在某些情况下,您可以选择适合整个缓存行的"平面"布局.

树和链表都是依赖于动态内存分配的链接结构,但是列表被认为是"坏的",因为它们是O(n),并且几乎每次追逐next指针都会导致高速缓存未命中.一般来说,n失误比log(n)失误更糟糕.

例如,考虑以下两个结构:

struct point {
    int x, y;
};

struct rect {
    struct point origin;
    struct point size;
};

即使rect包含两个point结构,整个rect结构也完全"平坦",因为内部结构包含在内,而不是通过指针引用.这种平坦性是一件好事,因为rect现在可以放在缓存行上,origin.x例如,访问结构本身的初始版本之后不会导致缓存未命中.

此外,因为堆栈通常在高速缓存中"热",所以在rect那里分配整个结构是有意义的,而不是在堆上.它不仅是动态分配本身的开销,而且分配器返回的地址可能还没有在缓存中.