是保持釋放的塊列表中動態內存分配時，最好使用LIFO順序或先進先出的順序？

我想實現的malloc（）用C類的，我不能決定一個塊是否應該被添加到空閒列表的末尾或空閒鏈表的頭。哪個更好，爲什麼？我使用的列表是一個雙向鏈表，並且（現在）是無序的。是保持釋放的塊列表中動態內存分配時，最好使用LIFO順序或先進先出的順序？

2011-10-16 David

都去嘗試一下，並運行一些性能/使用測試？（這應該回答至少兩個問題......） – 2011-10-16 04:06:49

@pst：他應該運行什麼樣的測試？ – Gabe

兩者之間的差異不應該很明顯（如果存在的話）：塊的分配和釋放順序取決於用戶（使用malloc的程序員），因此您可以將其視爲隨機。

製造至少一種有序列表的大小。

看看一些其他技術，如果你真的想要的東西快，例如，實現buddy system。

2011-10-16 04:19:47 Simon

感謝您的幫助。另外，我的教科書提到，在分配器使用第一個擬合算法時，按地址順序維護列表的內存利用率優於LIFO順序中的列表，但這並不能解釋原因。它是否更容易合併塊，或者是否有其他原因？ – David

沒有運行的基準測試中，最可能的選擇產生最佳性能FIFO，自由表頭即放釋放的塊。

這是因爲FIFO最有可能提供temporal locality of reference，因爲剛釋放的塊更可能駐留在CPU緩存中，而不是先前釋放的塊並且不會在較長時間段內使用。

2011-10-16 04:32:55

回答