改進我的redblack樹實現

Question

我寫了一個rb-tree實現。節點使用malloc進行分配。在開始時分配一個大表並使用該空間分配節點並在每次表溢出時將其大小加倍，這是一個好主意。假設分配的時間很長，我不確定這會使插入操作更快一些。

Answer 1

分配一個大塊（並自行分配）與分配大量小項目是否更好的問題適用於許多情況。並沒有一個適合所有人的答案。但總的來說，可能是分配大塊的速度要快一點。但是加速（如果有的話）可能不會很大。根據我的經驗，在大量使用動態分配的高度併發系統中，執行單一大型分配通常值得付出努力和複雜性。如果您有單線程應用程序，我的猜測是每個節點的分配佔用插入操作的成本非常低。

一些一般想法/評論：

• 分配一個單一的大的塊（和它生長需要的話）通常將使用較少的內存整體。典型的通用分配器（例如C中的malloc/free）具有每個分配的開銷。因此，例如，一個100字節的小分配請求可能導致使用128個字節。
• 在有大量內存碎片的內存受限系統中，可能無法分配大塊內存並對其進行分塊，而多個小分配可能仍會成功。
• 儘管分配一個大塊減少了在分配器級別（例如，在malloc中）對同步的爭用，但仍然需要在從您自己的託管列表/塊中獲取節點時提供自己的同步（假設多線程系統）。但是隨後可能需要一些與插入節點本身相關的同步，所以它可以在相同的操作中處理。

最終，您需要測試它並測量差異。你可以做的一件簡單的事情就是寫一個簡單的「扔掉」測試，分配你希望處理的節點數量，以及分配時間需要多長時間（然後可能還有時間釋放它們）。這可能會給你一些分配成本的估計。