工作應用/Java

Java 優化內存使用 結構篇

概要

首先，針對 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;
}
...

結語

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

Read More +
工作應用/Meme

File Extension

當我以為副檔名有著特殊含義和命名規則，把自動化辨識可存取的副檔名過濾器寫好，同事卻說他們都採用一些後綴習慣，都必須按照原本的行為運行。

然後，卻在又在　lock 檔案加在前綴，此時我的內心是崩潰的。你們到底想怎樣？

Read More +
工作應用/Meme

Job Build

Disconnected to server. Not enough quota is available.

通常我們會在 CI 過程中，保留每一次的 log 和運行結果的報表，也會週期性地去刪除過時資料。而不幸地，有人設計 CI 的專案，每執行一次就會永久耗掉 GB 級的硬碟空間。明明設置保留近期數量，和不把整個中間產物丟到保留項目就完善了。

而我們卻常常看到手動刪除的蠢事，事情卻一而三、再而三地發生。

Read More +
工作應用/Meme

Machine Learning for Newbie

最近面一些 python 為主要語言的 ML 高手，也許知道 stackoverflow，卻不知道 stack overflow，所以開始懷疑 CS 的專業已經有大幅度的概念調整，不了解底層的確可以做事，但也要有人替你打下手。

然後，得知這一年的台灣大學資訊工程學系，大一課程不學 C，直接 python，越來越接近西方的美式教育。

Read More +