使用依區塊大小排列的分離式串列的物件配置器在垃圾蒐集環境下的尋訪之減少

Abstract

使用依區塊大小排列的分離式串列之物件配置器是一種常見的物件配置器。使用依區塊大小排列的分離式串列的物件配置器，在作物件配置時，需要做尋訪以找出存放合適大小的區塊的串列。因為串列可能會變成空的，使得尋訪的串列增加，所以其效能仍然有改善的空間，這種情形在垃圾收集環境之下尤為顯著。 因此，我們在這份研究中提出了一個查表機制，以減少在配置物件時的尋訪動作。機制中的主要結構是一個要求區塊大小–最靠近的存放夠大區塊的非空串列的對映表。在配置物件之時，藉由查詢此對映表，只需要一次尋訪就能定位出存放有合適大小的區塊的串列，使得物件配置的速度大幅增快；我們並且以爪哇語言，一種使用自動垃圾回收機制的物件導向程式語言為例。結果顯示我們提出的機制能使管理堆積區的效能增加一倍。我們也研究了不同的區塊合併策略在自動垃圾回收環境之下，對堆積區管理的效能的影響；並且指出了在選擇區塊合併策略上的權衡，會在加入我們所提出的機制之後發生變化。原本會使得物件配置速度較慢而不傾向被使用的立即合併策略，在加入了我們的機制之後，成為較好的合併策略。這個結果也說明了在自動垃圾收集環境之下，只要物件配置速度夠快，空間破碎問題才是較重要的議題。

Size-ordered segregated list allocator is a widely-used object allocator. Upon object allocation, traversals are required to locate the free list holding large enough free chunks. Because some free lists might become empty, increasing the traversals upon object allocation, the performance of size-ordered segregated list allocator still has room for improvement. This is especially true in garbage collection environment. Therefore, we propose a table lookup mechanism to reduce the traversals. The main structure in this mechanism is a table which is a mapping from allocation request of each size to the closest non-empty free list holding large enough chunks. By looking up the table, only one traversal is required to locate the closest non-empty free list, hence speeding up object allocation. We take Java, a popular object-oriented programming language with automatic garbage collection, as example. The result shows that our proposed mechanism can improve the heap management performance by 100%. We also studied the impact of using different coalescing strategies on heap management performance in garbage collection environment, and showed that the trade-off to choosing a coalescing strategy will change, in the presence of our proposed mechanism. Immediate coalescing strategy, which is not used because it results in slower allocation speed, becomes a better one after our proposed mechanism is added. The result also indicates that fragmentation problem is a more serious issue in garbage collection environment than allocation performance if the allocation speed is fast enough.