工作應用/Java

Java 優化內存使用 結構篇

contents

  1. 1. 概要
  2. 2. 打包物件 (packed object)
  3. 3. 原始型別 (Primitive Type)
    1. 3.1. 繼承與泛型影響
    2. 3.2. 多形使用
  4. 4. 資料結構 (Data Structure)
    1. 4.1. 雜湊表 (Hash Table)
      1. 4.1.1. 開放定址法 (Open Addressing)
      2. 4.1.2. 串鏈法 (Chaining)
    2. 4.2. 固定長度陣列 (Fixed-length Array)
  5. 5. 結語

概要

首先，針對 JVM 這一類的語言設計，所有事物皆為物件，那麼就表示每一個物件都必須額外紀錄 object header，也就是說一個物件在 64 位元的作業系統環境下，通常會額外帶有 12 bytes 資料 (mark word:4 bytes 和 klass word:8 bytes)，但 64 位元計算機架構需對齊 8 bytes 的規範，使得每一個物件都大上許多。

例如，一個 struct Point 在 C 語言裡面，

1
2
3
4
struct Point {
    long x; // 8 byte
    long y; // 8 byte
}

我們輕易地就明白單一物件大小為 16 bytes，而在 Java 撰寫時，卻會變成 $32 \; \text{bytes} \;(\text{header:}12 + \text{x:}8 + \text{y:}8 + \text{padding:}4)$。

1
2
3
4
5
class Point { // object header 12 byte
    long x; // 8 byte
    long y; // 8 byte
    // padding 4 byte
}

這樣看起來並不妙。相同的演算法、配上相同的數據，Java 處理時的內容硬是比 C 還多出整整兩倍。物件導向有其優點，必然存在一些缺點，可以很彈性地開發、豐富的權限管理、方便追蹤剖析，卻容易在非常基礎的大量計算中暴露記憶體方面的問題。

打包物件 (packed object)

對於基礎物件，就只能倚靠撰寫 JNI 或者修改 JVM 的參數，來降低每一個單一物件的大小。對於底層不夠熟悉的開發者而言，還是可以透過一些實作方法來完成。但必須犧牲一點物件導向的方法論，喪失維護性，面對真實問題。

例如，我們儲存一個矩形，需要一個左上角和右下角的點。

1
2
3
4
class Rectangle {
    Point a; // pointer: 8 bytes
    Point b; // pointer: 8 bytes
}

資深工程師總會很直覺地 重複使用，這個原則並沒有錯，但對於大量的基礎物件而言，宣告一個矩形實際上會占用 $32 + 2 \times 32 = 96 \; \text{bytes}$。接著，老是有人跟我唱反調說「效能分析工具 (Profiler) 只給出 $32 \; \text{bytes}$，你肯定算錯了！」別忘了，你寫的不是 C/C++，是一切皆為指標的 Java。

那我們要怎麼打包物件呢？或者說 攤平，目標要減少 Point 多出來的 object header。

1
2
3
4
5
6
class Rectangle {
    long lx;
    long ly;
    long rx;
    long ry;
}

返璞歸真，直接將欄位往上提取，破壞一點基礎建設，在一些 API 上犧牲一點效能。這樣就變成了 $48 \; \text{bytes} = 12 + 8 \times 4 + 4 \; \text{bytes}$ 的物件。如此一來，減少了一半的內存用量。

原始型別 (Primitive Type)

在很多不經意的操作下，很容易將原始型別 (primitive type) 儲存成物件型別 (object type)，也就是物件導向最容易造成的問題，從整體用法來分析，並不影響程式正確性，但會造成記憶體用量飆高。如 long 原本為 8-byte 物件，轉換成 Long 會變成 24-byte 物件。

繼承與泛型影響

1
class Version extends Pair<Long, Long> {}

當想重複使用類別，透過繼承的泛型很容易自動轉換成物件型別。這個問題在 C# 內並不存在，CIL 能允許宣告 Pair<long, long>，並且不透過型別抹除，分別建立相應的代碼，能解決此問題。在 Java 上要解決這個問題，只能更樸素一點。

1
2
3
4
class Version {
    long major;
    long minor;
}

代碼多了一點，取而代之的是記憶體量減少，物件轉換次數的降低。

多形使用

1
2
3
4
List<Object> list;
list.add(1);
Map<Object, Object> map;
map.put(2, 3);

多形操作下，將好幾種不同類別的物件一起使用，隱式轉換問題就會發生，一般要追到底層才知道最後發生什麼事情。由於 Java 官方的庫並沒有預設大量的原生型別的資料結構，我們只能透過像 trove4j、eclipse collections 等插件來補足，必要時自己刻一個。

1
2
3
TLongObjectMap<T> a;
TLongArrayList b;
...

資料結構 (Data Structure)

雜湊表 (Hash Table)

在大多數的實作下，雜湊表佔據線性空間 $\mathcal{O}(n)$，存取時間 $\mathcal{O}(1)$，理論分析上也近乎完美。在處理碰撞的技巧上，影響常數級別的空間用量。通常分成以下兩種

開放定址法 (Open Addressing)

trove4j 和 eclipse collections 採用此方法。

  • 使用記憶體空間最小
    僅有兩個陣列 key[] 和 value[]，沒有多餘的 object header。
  • 存取常數大，調整時間較長
    通常會有兩個以上的 probing 操作，中間穿插刪除操作時，容易造成退化。

串鏈法 (Chaining)

jdk 預設採用此方法。

  • 使用記憶體空間最大
    HashNode {val, next, prev} 佔據了大部分的記憶體，且大量的 object header 出現。
  • 存取常數較小

從穩定性分析上，串鏈法在某種程度上可以複合許多結構，如 unrolled linked list (bucket) 或者是 binary tree 來降低最慘複雜度。而開放定址法，雖然有記憶體用量小，快取能力更高，但數據量一大，很容易在 rehash 的階段花太久的時間，而且不容易做到刪除操作。

固定長度陣列 (Fixed-length Array)

Java 開發久了，連宣告陣列都很吃技術。有時候，並沒仔細探討固定長度與不固定長度的差異。劈頭就寫一個

1
2
3
class Scheme {
    ArrayList<Field> fields;
}

這樣的設計擴充性佳，具有彈性。在底層設計時，卻會發現 ArrayList 至少包含了 size 和 val[] 兩個欄位，而 val[] 包含了真正的 array pointer 和 length 兩個欄位。如果已知固定長度且不再變更，或者變更的使用量極低，且能保證 size == val.length，那不如直接宣告

1
2
3
class Scheme {
    Field[] fields;
}

如此一來，一個 Scheme 物件便能減少 $16 \; \text{bytes}$。更進一步，我們可以利用封裝 (Encapsulation) 和多型技術，再降低 $8 \; \text{bytes}$。

1
2
3
4
5
6
7
8
class Scheme1 {
    Field f1;
}
class Scheme2 {
    Field f1;
    Field f2;
}
...

結語

根據實際應用的數據分布，對最常用的物件進行優化。醜了點，但能解決問題。雖然並不是黑魔法，更能了解實作。