如何以缓存友好的方式将项目存储在 LIFO 堆栈中？

Question

我打算编写一个数据容器来存储连续且可调整大小的内存块，其中的项目只能通过压入或弹出从一侧访问 - 基本上是一个 LIFO 堆栈。我已经阅读了很多有关 CPU 缓存和内存访问模式的内容，并希望所述容器尽可能对缓存友好。

---

所以我研究了互联网上 LIFO 堆栈的常见实现。他们中的大多数建议使用动态数组作为基础，并通过在数组末尾添加或删除项目来访问数据。在这种情况下，空容量间隙按以下方式存储在数据之后：

 stack bottom            stack top
 array begin             V  array end
 V                       V  V
|V          data         V |V     gap     |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|8 |7 |6 |5 |4 |3 |2 |1 |0 |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                        |       cache line       |

但是，这对我来说似乎不太适合缓存。每当人们查找堆栈顶部的项目时，CPU 就会从包含垃圾的间隙中获取内存，或者至少我是这么理解的。

间隙作为内存块的乞求和最后的数据出现的方法会不会性能更好？在这种情况下，项目的索引将被反转，与底部和顶部相同。在这种情况下，缓存行可能会命中更多项目，如下所示：

                stack top               stack bottom
                V                       V
|      gap     |V          data         V |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |0 |1 |2 |3 |4 |5 |6 |7 |8 |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
               |       cache line      |

我的理解正确吗？哪种方法性能更高且缓存友好？

我的假设可能完全错误。正如我所说，我看到的大多数实现都使用第一种方法，所以一定有它的道理。

干杯！

Answer 1

使用末尾有间隙的动态数组实现堆栈的标准方法是常用的，但由于从间隙区域获取不必要的数据，可能会导致访问堆栈顶部时 CPU 缓存使用效率低下。

您提出的替代方案，即数据位于分配的内存块的开头，间隙位于末尾，可以通过将最近的堆栈访问与缓存行对齐来潜在地提高缓存性能，从而提高缓存命中率。

要确定适合您的特定用例的最佳方法，请考虑尝试这两种方法并测量缓存命中率和执行时间等性能指标。这种经验方法将帮助您决定哪种设计可以有效优化性能。