如何以缓存友好方式实现LIFO栈？两种数组实现的性能对比

我之前对cache line的理解是错误的，这导致本问题失去相关性且具有误导性。我曾以为CPU获取特定索引的内存时，也会同时获取该索引之后的内存，但事实并非如此。可参考《How do cache lines work?》了解详情。

我打算实现一个基于连续可扩容内存块的数据容器，仅支持从一端进行push或pop操作——本质上是一个LIFO栈。我查阅了大量关于CPU cache和内存访问模式的资料，希望该容器尽可能具备缓存友好性。

我调研了网络上常见的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会读取包含垃圾数据的空闲区域内存，至少我是这样理解的。

那将空闲区域放在内存块开头、数据放在末尾的方式是否性能更优？这种方式下元素索引和栈底、栈顶的位置都会反转，此时cache line可以命中更多元素，结构如下：

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

我的理解是否正确？哪种方式性能更优、更缓存友好？

我的假设可能完全错误，正如我所说，我看到的大多数实现都采用第一种方式，这背后肯定有原因。

谢谢！

内容的提问来源于stack exchange，提问作者sleeptightAnsiC