Fragmentation定義
The Memory Fragmentation Problem Solved? 論文中,提出了四種Fragmentation的定義。

我們用百分比來表示記憶體碎片化的程度,也就是

(allocator_usagelive_data_usage)/live_data_usage(allocator\_usage - live\_data\_usage)/live\_data\_usage

live_data是目前程式所使用的記憶體用量,因此最好的情況下,live data剛好等於allocator所使用的記憶體,那麼Fragmentation Rate就是0%。如果allocator使用了相當於live data三倍的記憶體,那麼就會是
200%。

我們以下圖為例協助我們理解並定義何謂fragmentation,這是gcc使用segregated 2^N allocator的記憶體用量變化圖,上方的線是allocator當下的記憶體用量,下方的線是程式當下的記憶體用量。橫軸是類似進度條的概念,以總共程式所分配的記憶體量作為橫軸的最大值,紀錄每分配一定數量的記憶體,當下程式和allocator的記憶體用量。

基於這個原則,我們提出了四種定義的方式,以各種不同的觀點來代入allocator usage和live data usage。
  • average memory used by allocator / average memory requested by program
  • 平均的意思圖中平均上方和下方線條每個點的平均值
  • 在live data用量最大的當下的allocator usage和live data usage,分別是點1和點2。
  • 在allocator最大記憶體用量的情況下,allocator usage和live data usage,分別是點3和點4。
  • 在allocator用量最大的當下,取allocator usage,另外在live data最大用量的當下,取live data usage,這兩個未必是同一的點。這張圖的情況下是點3和點2。
  • 這種作法可能的問題在於如果程式在allocator用量最大的當下,只使用了少少的memory,實際上是有fragementation的問題,但我們會傾向於低估fragmentation rate。