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

Question

我观看了Bjarne Stroustrup的视频, 他解释了为什么要避免使用链表。

基本上，当使用指针动态分配内存时，会出现更多的缓存未命中，从而降低性能。

但是，如果同样的方法应用于非线性数据结构，例如树和图形，是否仍然适用？

因为在树中，每个节点也有两个指针，指针的随机移动会导致缓存未命中。

但是，已经证明了树比线性数据结构执行得更好。当然，也可以使用数组实现树，但会消耗大量内存。

我的问题是：动态内存分配好还是不好？

- xxx

---

动态内存分配好还是不好？这其实不是一个好问题。动态内存分配有时是必要的。但问题标题确实更有趣，尽管你应该期望一个好的答案至少包含一次“这取决于” 。 - JBL

你的问题是：动态内存分配好还是不好？我的答案是：是的。 - Jonathan Wakely

是的，它可能相对较慢。这就是为什么人们使用内存池来消除大量小的分配。动态内存分配是不好的吗？哈哈...它是用于你无法以其他方式完成的东西，因此它远非不好，事实上它非常非常好，因为它使您能够做更多的事情，自然地，如果您在不必要时使用它，那就是不好的，就像其他任何东西一样。 - dtech

“已经证明树形数据结构的表现比线性数据结构更好” - 不一定。在数组上进行迭代可能比在树上进行迭代更快（因为您所指的缓存局部性）;并且在排序的数组中进行二分查找可能比树更快，除非树是完美平衡的。 - Mike Seymour

@xxx：是的，也不完全是...每当你将一个数组传递给函数时，你都有间接引用（它会衰减为指针），每当你将变量的内存地址传递给函数时，你也有间接引用。间接引用并不局限于数据结构。你可以以各种方式搜索树，不一定从根节点开始（维基树遍历）。这完全取决于你需要什么，何时需要以及在哪里需要。你也可以传递单个叶节点的指针，这无关紧要：间接引用就是游戏的名字。 - Elias Van Ootegem

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结构体分配到堆栈中是有意义的，而不是在堆上分配。这不仅是动态分配本身的开销，而且是分配器返回的地址很可能还没有在缓存中。

- Blagovest Buyukliev

Answer 2

数据结构是一个抽象的概念，它们与语言无关，更不用说实现它们的库（在这种情况下是 std）。

树比数组更适合查找，不是因为内存是静态分配还是动态分配（对于这两种数据结构，都可能是静态或动态分配），而是因为用于搜索的算法。

然而，通常情况下，当遍历所有节点时，数组比树表现更好（这既是因为使用简单的算法又是实现细节-由于线性分配，缓存速度更快）。

最好使用符合计划执行操作的数据结构。您始终可以提供处理分配的自定义分配器。但是，再次强调，分配是正交的。有算法效率和低级效率。这里存在权衡。如果您将设计解耦到足够程度，则应能轻松地在数据结构之间进行切换，并在性能受到足够影响时执行此操作。

- Luchian Grigore

Answer 3

你想要动态分配内存还是在堆栈上分配内存完全取决于你的实现。一般来说，如果变量或对象仅在函数内部存在，则使用堆栈；如果变量或对象必须在整个程序中存在并由多个函数操作，则使用堆。

- Lawrence Aiello

---

根据您的看法，全局堆栈变量属于哪个类别？ - Elias Van Ootegem

是的...应该更多地考虑一下。它们确实在全局层面上被放置在堆栈中。 - Lawrence Aiello