使用malloc和realloc進行動態存儲的最佳方式

Question

我想弄清楚使用malloc和realloc從用戶接收未知數量的字符，存儲它們以及僅在最後打印它們的最佳方式。

我想到調用realloc太多次都不會那麼聰明。 因此，我每次分配一定數量的空間，可以說 sizeof char * 100 並且在文件末尾，我使用realloc來精確地匹配整個事物的大小。

你覺得呢？這是一個好方法嗎？ 你會走在另一條路上嗎？

請注意，我沒有打算使用鏈表，getchar（），putchar（）。使用malloc和realloc的 是必須的。

Answer 1

如果您重新分配以適合所需的確切數據量，那麼您正在優化內存消耗。這可能會導致代碼變慢，因爲1）您會得到額外的realloc調用，以及2）您可能不會分配與CPU對齊和數據緩存非常匹配的數量。可能這也會導致堆分割問題，因爲重複的reallocs，在這種情況下，它實際上可能會浪費內存。

很難回答什麼是「最好」的一般，但下面的方法是相當普遍的，因爲它降低了執行速度realloc的調用和降低內存使用之間的良好折衷：

您分配一個段，然後跟蹤這部分是用戶數據的多少。這是分配size_t mempool_size = n * _Alignof(int);字節一個好主意，這大概也是明智的8

使用n這是整除每次在該段運行的可用內存的時候，你的realloc到mempool_size*2字節。這樣你每次都會使可用內存翻一番。

Answer 2

我想到調用realloc太多次不會那麼聰明。

你是怎麼想出來的？因爲唯一真正知道的方法是衡量表現。

根據用戶如何閱讀數據，您的策略可能需要不同。如果您使用的是getchar()，則每次讀取字符時，您可能不希望使用realloc()將緩衝區大小增加一個字符。但是，即使在這種情況下，好的realloc()的效率也會比您想象的低得多。我認爲，glibc實際給你的最小塊大小爲malloc()，這是16字節。因此，從0到16個字符並重新分配每次不涉及任何複製。類似地，對於較大的重新分配，可能不需要分配新塊，可以使現有塊更大。不要忘記，即使速度最慢，realloc()也會比人們輸入的速度快。

大多數人不會選擇這種策略。可以輸入什麼類型的內容，因此人們輸入非常快的參數不一定有效。通常，您會介紹容量的概念。您分配具有一定容量的緩衝區，當它滿了時，通過添加一定大小的新區塊來增加容量（使用realloc()）。初始大小和重新分配大小可以通過各種方式進行調整。如果您正在閱讀用戶輸入內容，則可能需要較小的值，例如256字節，如果您正在從磁盤或整個網絡讀取文件，則可能需要更大的值，例如4Kb或更大。

增量大小甚至不需要保持不變，您可以選擇將每個所需重新分配的大小加倍。這是一些編程庫使用的策略。例如，哈希表的Java實現使用它我相信，所以可能做一個數組的可可實現。

事先不可能知道在任何特定情況下最好的策略是什麼。我會選擇一些感覺不錯的東西，然後，如果應用程序有性能問題，我會做測試來調整它。您的代碼不一定是最快的，但速度不夠快。

但是我絕對不會做的一件事是覆蓋家庭滾動內存算法覆蓋內置分配器的頂部。如果你發現自己保留了一個你沒有使用的塊列表，而不是釋放它們，那麼你做錯了。這是OpenSSL陷入困境的原因。