HeapAlloc的计算复杂度

Question

C++实现vector依赖于在超出当前容量时对其进行两次扩展。显然，push_back操作在Windows上使用HeapAlloc，并且根据C++标准，应该以某种方式使用使用摊销恒定时间。Windows到HeapAlloc需要多长时间，如果事先不知道特定程序中的指令集，那么如何计算push_back使用摊销常量时间？

Answer 1

我认为假设HeapAlloc (或任何操作系统中的动态分配)是摊还常数是非常安全的。

首先，当您要求堆交付给定的内存量时，它必须找到可以分配给您的大量空闲内存。如何找到内存块的内部逻辑是特定于实现的(但是是有一些很好的线索要找)，并且可能会因碎片和效率之类的事情而有很大的不同。但是，如果堆的实现不能在摊销的恒定时间内交付这一点，那么这个实现是非常糟糕的。它通常被称为“堆”，因为这种“查找好块”机制的基本实现是使用一种优先级队列或第一可用块列表，它可以立即交付(接近)最好的块。更复杂的版本不会比平均水平更糟(在摊销的意义上)，但可能会涉及额外的“簿记”工作，这取决于它如何跟踪空闲块，以及它试图减少碎片的程度，从一个起点来看，看看经典的伙伴分配器。所以，这是为了“找到一个好的块”部分。当然，还有许多其他有趣的问题，比如争用，但总的来说，它仍然是摊销的常数时间(在这里更重要的是常数因素)。

堆所做的另一部分是面对OS内核(或其他与操作系统相关的层)，以便在耗尽时获得额外的内存。基本上，堆是一个内存管理器，它从操作系统(或后端)获取大量内存块，然后微管理这些大内存块，以分配程序(或前端)请求的所有较小块(通过new、malloc、HeapAlloc等)。偶尔，您将向堆请求更多的内存，堆会发现它已经没有内存可供使用了，因此，它必须转向操作系统，并请求另一大块内存。正如您所看到的，堆本身现在的行为必须非常类似于std::vector，因为它必须按指数增长才能将请求的成本摊销到操作系统以获得更多的内存。

当OS内核将内存交付给堆时，成本同样是常数(很可能)，因为它的实现方式可能与堆在程序中分配内存的方式非常相似。当然，区别在于，如果操作系统内存不足，它就不能向任何人请求更多的内存，因此只能失败。从操作系统内核请求内存最昂贵的是用户模式/ 核模式、进程间争用和扩展虚拟地址空间之间的切换。

如果事先不知道一个特定程序中的指令集，那么一个人怎么能计算出push_back在此基础上使用了摊销的恒定时间呢？

基本上，C++标准要求在不包括堆分配成本的摊销固定时间内实现push_back on std::vector，因为它们具体地将内存分配时间从分析中排除在外，这是他们无法真正支配或预测的。但是，如果你愿意的话，你可以用经验来测试它，我过去也有过，我可以肯定地说(至少在Linux下)，push_back on std::vector确实是摊销常数时间。

Answer 2

“摊销”这个术语的固定时间意味着“如果你执行一个长的操作序列，每个操作平均需要一个恒定的时间。”vector的工作方式是表加倍。当您的向量耗尽空间时，它不是为单个项创建更多的空间，而是将当前向量的大小加倍。这将花费与向量大小相等的时间(对于算法人员来说，O(N))，但是您只需要在表的大小加倍时才能这样做。因此，如果以大小为n的向量开始并添加n个多个项，则第一个项将花费O(n)时间(使表的大小加倍并复制旧值)，但下一个n-1项将花费O(1)时间。这给出了n个插入的O(n) + (n-1)O(1)时间，或者给出了O(2n) = O(n)时间的总和。平均每个操作的O(1)时间。

Answer 3

请记住，STL将使用new (或自定义分配器)，因此不需要在Windows平台上调用HeapAlloc。

尽管如此，STL文档不能保证与低级API调用的任何运行时一致性，它只是定义了它自己的墙内实现了什么。

还请记住，HeapAlloc的实现可能会在OS甚至Service版本之间发生变化，因此这里的任何答案都很容易被未来的版本淘汰。

就我个人而言，我更关心堆中锁的数量和长度(由于通过多个线程同时访问而需要确保数据结构的一致性)。

进一步阅读：MSDN -堆:快乐与痛苦