工作應用/Java

Java 優化內存使用 組合篇

contents

  1. 1. 整數映射 (Integer Mapping)
  2. 2. 陣列替代 (Array Substitute)
  3. 3. 欄位轉移 (Field Translation)
  4. 4. 卸載策略 (Offloading Strategy)

整數映射 (Integer Mapping)

算法經常會使用整數映射到物件，而整數範圍就會影響到內存。為了技術性能 (capability)，直接宣告 

1
2
Map<Long, Object> a;
TLongObjectMap<Object> b;

以應付未來變化。考慮到鍵值欄位，實作上建立 $\mathcal{O}(n)$ long[]。在初始狀態下，大多情境只使用 int[] 的情況。為此，我們考慮分流使用

1
2
3
4
class MMap<T> {
    TLongObjectMap<T> longMap;
    TIntObjectMap<T> intMap;
}

使用這樣子的概念，通用狀態可以降低 $50\%$ 內存，均勻分布情況則可以降低 $25\%$。

陣列替代 (Array Substitute)

前一篇，我們提到了將 ArrayList 換成最原生的 T[]。更進一步，以前寫 C 的時候，壓根不在意 T[].length 這一個需求，因為題目已經寫死在某個全區變數裡。可在 Java 裡頭，我們宣告不出純粹的陣列，只能硬生生多出 $4 \; \text{bytes}$。

1
2
3
4
class Scheme {
    K[] keys; // as known, keys.length = 10
    V[] vals; // as known, vals.length = 10
}

換個方向思考，那朝著減少試試。進行陣列雙向合併

1
2
3
class Scheme {
    Object[] keyval; // [key0, key1, ..., val1, val0]
}

在 Scheme 物件中，我們減少了 $8 \; \text{bytes}$ 的額外資訊。但在使用時， casting 是個開銷。

欄位轉移 (Field Translation)

1
2
3
Map<T, String> map;
map.put(a, "MARKED");
map.put(b, "UNMARKED");

當我們還沒有仔細規劃結構時，直接用 has-A 的精神去寫第一步。回過頭來，就會造成不少零散的映射出現。如果映射使用雜湊實作，而不是樹的話，整體的記憶體效率會低個 $33\%$，因為無法塞滿所有的 hash table 中的桶子。

1
2
3
4
class T {
    ...
    Object userData;
}

那為了提升記憶體效率，先檢查是不是所有的項目，幾乎都在這個映射裡面。如果是的話，將這個欄位轉移到目標類別上。看起來很不美觀，但進一步的資料佈局是很可觀的，甚至可以比雜湊 $\mathcal{O}(1)$ 更快的存取。

卸載策略 (Offloading Strategy)

在平行處理中，我們可以劃分成不同數量級的策略。在小規模下，嘗試先以 CPU 計算，若發現更大規模，將資料卸載給其他異質計算單元來完成。同樣的道理，對於資料結構也能更近一步地劃分。

如集合實作：

1
2
3
class MSet {
    Object mRaw; // size < 8: LinkedList; otherwise, HashSet
}

由於 Java 中的 HashSet<T> 並不是單一欄位的實作，實值為 HashMap<T, T>，相較於 C/C++ 的狀態，空間多了兩、三成。我們可以簡單使用 LinkedList 取代 HashSet，並且避免小規模數據中未能填滿 hash table 的狀態。在元素個數為一時，串列的記憶體效率 $100 \%$，但雜湊集合只有 $12.5 \%$。換句話說，有時候數據分布很極端，內存用量就差了十倍。