多個realloc比一個巨大的malloc更貴嗎？

Question

我正在使用動態數組來表示最小堆。有一個循環可以刪除最小值，並在最小堆中添加隨機元素，直到發生某種情況。雖然我不知道堆的長度在運行時如何變化（有很多隨機性），但我知道上限是1000萬。我有兩種選擇：

1）使用malloc聲明一個小數組，然後在堆中的元素數量超過該長度時調用realloc。

2）聲明瞭1000萬條目陣列使用malloc。這避免了調用realloc。

問題

是選項2比方案1更有效？

我與我的代碼使用2。這是因爲在代碼中隨機性的估計測試這一點，似乎有顯著（20％），運行時間減少。使用malloc預先聲明一個大型的10-50萬個入口數組有沒有什麼缺點？

Answer 1

如果您能抽出內存，使大量的前期配置，它提供了有價值的性能提升，然後通過各種手段做到這一點。

如果你堅持使用realloc，那麼你可能會發現每次增加一倍而不是增加一個固定的數量可以在性能和有效的內存使用之間進行良好的折衷。

Answer 2

缺點是，如果你沒有使用所有的空間，那麼你需要佔用大量的內存空間。如果您確切知道需要多少字節，由於系統調用開銷，將立即分配效率更高，然後逐個分配。通常你可能有一個上限但不知道確切的數字。花時間來處理上限可能需要1秒。但是，如果這種特殊情況只有上限的一半，可能需要0.75秒的時間分配。所以這取決於你認爲你會得到多少接近上限。

Answer 3

這不是說，當你使用的realloc，內存將被來自同一place.It擴大也可能發生內存會在另一個區域移位。
因此，使用realloc可能會導致您複製之前的內存查找。
還要考慮系統調用可能需要一些開銷，所以你最好調用一次malloc。