据我所知,堆栈内存在虚拟内存地址中是连续的,但堆栈内存在物理上也是连续的?这与堆栈大小限制有关吗?
不,堆栈内存在物理地址空间中不一定是连续的。它与堆栈大小限制无关。这与操作系统如何管理内存有关。操作系统仅在第一次访问相应的虚拟页面(或自从它被分页到磁盘后第一次访问)时才分配一个物理页面。这称为需求分页,它有助于节省内存使用量。
为什么我们认为栈内存总是比堆内存快?如果它在物理上不是连续的,堆栈如何更好地利用缓存?
它与缓存无关。从堆栈分配和释放内存比堆更快。这是因为从堆栈分配和释放只需要一条指令(递增或递减堆栈指针)。另一方面,从堆中分配和/或解除分配内存涉及更多工作。有关更多信息,请参阅本文。
现在,一旦分配了内存(从堆或堆栈),访问该分配的内存区域所花费的时间并不取决于它是堆栈内存还是堆内存。这取决于内存访问行为以及它是否对缓存和内存架构友好。
如果我们要对大量的数字进行排序,使用数组存储数字比使用列表更好,因为每个列表节点都可能由malloc构造,所以它可能没有很好地利用缓存,这就是为什么我说堆栈内存比堆内存快。
使用数组更快不是因为数组是从堆栈中分配的。可以从任何内存(堆栈、堆或任何地方)分配数组。它更快,因为数组通常一次连续访问一个元素。当第一个元素被访问时,包含该元素和其他元素的整个高速缓存行从内存中提取到 L1 高速缓存。因此访问该缓存行中的其他元素可以非常有效地完成,但访问缓存行中的第一个元素仍然很慢(除非缓存行是预取的)。这是关键部分:由于缓存行是 64 字节对齐的,并且虚拟页面和物理页面也是 64 字节对齐的,因此可以保证任何缓存行完全驻留在单个虚拟页面和单个物理页面中. 这使得获取缓存行变得高效。同样,所有这些都与数组是从堆栈还是堆中分配无关。无论哪种方式,它都是正确的。
另一方面,由于链表的元素通常不连续(甚至在虚拟地址空间中也不连续),因此包含一个元素的高速缓存行可能不包含任何其他元素。因此,获取每个元素可能会更昂贵。