Case Study: ArrayList.grow() — Vì sao 1.5x là magic number

TL;DR: ArrayList.grow() trong OpenJDK 21 tính capacity mới bằng oldCapacity + (oldCapacity >> 1) — tăng 1.5x mỗi lần đầy, khác hẳn 2x của C++ std::vector. Big-O không phân biệt hai hệ số (đều amortized O(1)); khác biệt nằm ở bộ nhớ: 1.5x lãng phí trung bình 17% RAM so với 25% của 2x, và vì 1.5 nhỏ hơn golden ratio φ ≈ 1.618, tổng các block đã giải phóng đủ lớn để allocator tái sử dụng cho block mới — 2x thì không bao giờ. Pre-size new ArrayList<>(n) loại bỏ toàn bộ grow event, nhanh hơn ~33% khi insert 1 triệu phần tử.

Bài này mổ cách Java thật sự viết ArrayList bên trong JDK. Lý thuyết nền — mảng động và vì sao nhân đôi dung lượng cho chi phí trung bình O(1) mỗi lần thêm — đã giải thích kỹ ở khoá Thuật toán: Amortized analysis. Nếu còn mơ hồ, đọc trước rồi quay lại sẽ dễ theo hơn.

Trên Stack Overflow có một câu hỏi được vote cao: "Java ArrayList grow factor là 1.5x, không phải 2x như C++ std::vector. Tại sao Oracle không dùng 2x?"

Nếu bạn vừa học xong bài amortized analysis, bạn biết rằng với bất kỳ grow factor nào lớn hơn 1, add() vẫn là amortized O(1). Vậy khác biệt giữa 1.5x và 2x nằm ở đâu? Không phải Big-O — mà là bộ nhớ và allocator behavior. Bài này đọc thẳng OpenJDK 21 source, đo benchmark, và trả lời vì sao một con số cụ thể được chọn.

1. Vấn đề ArrayList giải — và tại sao grow là cần thiết

ArrayList giải quyết vấn đề: collection có kích thước động nhưng vẫn cho phép random access O(1).

LinkedList cũng là dynamic-size collection, nhưng random access tốn O(n) vì phải traverse từ đầu. Thêm vào đó, mỗi node LinkedList là một object heap riêng biệt — pointer chasing phá vỡ CPU prefetcher, khiến traverse 10 triệu phần tử chậm hơn int[] khoảng 25 lần dù cùng O(n).

ArrayList chọn backing store là array liên tiếp trong bộ nhớ — random access O(1) và cache-friendly. Vấn đề: array có kích thước cố định khi khởi tạo. Khi đầy, phải cấp phát array mới lớn hơn và copy toàn bộ phần tử — O(n) per resize.

Hình dung một xưởng thuê kho chứa hàng: kho đầy thì thuê kho mới lớn hơn theo một hệ số cố định, chuyển toàn bộ hàng sang, rồi trả kho cũ cho chủ bãi. Chủ bãi (memory allocator) luôn muốn cho khách sau thuê lại các kho vừa trả. Thuê "gấp rưỡi" hay "gấp đôi" mỗi lần chính là câu hỏi 1.5x vs 2x của bài này.

Khoá Thuật toán — Amortized analysis đã chứng minh amortized O(1) cho add(): nếu grow factor là r, tổng chi phí copy sau n lần add() là chuỗi hình học hội tụ về O(n), nên trung bình mỗi add() vẫn là O(1). Vậy câu hỏi không phải grow factor có ảnh hưởng amortized không — mọi factor lớn hơn 1 đều đảm bảo — mà là grow factor cụ thể nào tối ưu nhất cho JVM environment.

2. Đọc source OpenJDK 21

Source file: java.base/share/classes/java/util/ArrayList.java — dòng 245–270.

// OpenJDK 21 -- ArrayList.java, around line 245
// License: GPL v2 with Classpath Exception
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

Giải thích từng phần:

oldCapacity >> 1 — bit shift phải 1 bit, tức oldCapacity / 2 bằng 1 CPU instruction. Preferred growth = một nửa capacity cũ → newCapacity = 1.5 * oldCapacity. Đây là nơi 1.5x được quyết định.

ArraysSupport.newLength(oldCapacity, minGrowth, prefGrowth) — cộng vào oldCapacity giá trị lớn hơn giữa minGrowth và prefGrowth, kèm xử lý overflow khi capacity tiến gần Integer.MAX_VALUE.

Empty array case — ArrayList vừa khởi tạo trỏ tới sentinel DEFAULTCAPACITY_EMPTY_ELEMENTDATA; lần add() đầu tiên mới cấp phát DEFAULT_CAPACITY = 10 (lazy initialization — không tốn bộ nhớ cho list tạo ra mà chưa dùng).

// ArraysSupport.newLength -- central grow logic shared by ArrayList, Vector, StringBuilder
// MAX_ARRAY_LENGTH cap to avoid JVM header overflow
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // prefGrowth is preferred, minGrowth is the floor
    int prefLength = oldLength + Math.max(minGrowth, prefGrowth);
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        return prefLength;
    } else {
        // Overflow-conscious code
        return hugeLength(oldLength, minGrowth);
    }
}
// SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8

ArraysSupport.newLength() là trung tâm grow logic dùng chung cho ArrayList, Vector, và StringBuilder/StringBuffer (qua AbstractStringBuilder) — không phải logic riêng của ArrayList.

3. Capacity growth trace

Trace capacity qua các lần add() — bảng lấy mẫu vài mốc trong ~30 lần resize (cột đầu là số thứ tự lần resize), không liệt kê đủ:

Công thức mỗi hàng: mới = cũ + (cũ >> 1) — ví dụ 15 + (15 >> 1) = 15 + 7 = 22 (shift truncate như phép chia nguyên). Để capacity vượt 1 triệu cần ~29 lần realloc (30 nếu tính cả lần cấp phát đầu như bảng trên); với 2x chỉ cần ~17 lần. 1.5x resize nhiều hơn ~1.7 lần nhưng tiết kiệm RAM — phân tích ngay phần tiếp theo.

4. Vì sao 1.5x mà không phải 2x?

4.1 Memory utilization

Ngay sau resize với grow factor r, phần trống của mảng là (r - 1) / r; phần trống giảm dần về 0% khi mảng đầy lại. Trung bình giữa hai lần resize:

• 2x: waste dao động từ 50% xuống 0%, trung bình 25%
• 1.5x: waste dao động từ 33% xuống 0%, trung bình 17%

Chênh 8% RAM — có ý nghĩa thực tế trong môi trường container Java (limit 512 MB, nhiều ArrayList nhỏ).

4.2 Block reuse và golden ratio

Đây là lập luận allocator được trích dẫn nhiều nhất khi so 1.5x với 2x. (JDK source không ghi chính thức vì sao chọn 1.5x — hãy coi đây là giả thuyết kỹ thuật mạnh và phổ biến, không phải tuyên bố của Oracle.) Khi ArrayList resize, block cũ được giải phóng; memory allocator giữ track các block đã free và cố tái sử dụng chúng cho allocation mới.

Đếm cho đúng: lúc cấp phát block thứ k (kích thước r^k), block ngay trước nó (r^(k-1)) vẫn đang dùng — dữ liệu phải copy từ nó sang block mới, nên chưa được tính là free. Các block thực sự đã giải phóng chỉ là r^0, r^1, ..., r^(k-2), tổng dung lượng (r^(k-1) - 1) / (r - 1).

Để block mới nằm vừa vùng nhớ các block cũ để lại:

tong_block_da_free >= block_moi
(r^(k-1) - 1) / (r - 1) >= r^k

Với k đủ lớn, bỏ hằng số nhỏ: r^(k-1) / (r - 1) >= r^k, chia hai vế cho r^(k-1) được 1 / (r - 1) >= r, tức r^2 - r - 1 <= 0 — nghiệm dương là r không vượt golden ratio φ = (1 + √5) / 2 ≈ 1.618.

• r = 2.0: 2 > φ → tổng block cũ luôn thiếu, mỗi resize phải xin vùng nhớ mới; fragmentation tích lũy.
• r = 1.5: 1.5 < φ → sau vài lần resize, tổng block cũ đủ cho block mới. Memory pressure giảm.
• r = 1.618 (chính xác φ): biên giới lý thuyết, không dùng vì số vô tỷ và thêm overhead.

Cùng phép cộng đó trên hai chuỗi capacity thật, hai kết luận ngược nhau:

1.5 là giá trị rational (tính bằng integer arithmetic với >> 1) nhỏ hơn φ — lý tưởng cho cả correctness và performance.

4.3 Resize count và peak RAM

(Cùng thước đo: capacity thực tế khi vừa chứa nổi 1M.) Chênh lệch capacity cuối không lớn — khác biệt RAM thật nằm ở waste trung bình 17% vs 25% (§4.1) và khả năng tái sử dụng block (§4.2).

5. Benchmark thực tế

Đo bằng JMH trên Java 21, warmup 5 iteration, 10 iteration đo:

// JMH @BenchmarkMode(AverageTime), insert 1M Integer, warmup 5 + 10 measured
// Each benchmark: for (int i = 0; i < 1_000_000; i++) list.add(i);

new ArrayList<>();            // ~30 grow events, amortized O(1)   -> ~12 ms
new ArrayList<>(1_000_000);   // 0 grow, pure insert throughput    -> ~8 ms
new LinkedList<>();           // 1M object alloc, no grow          -> ~95 ms (GC pressure)
new Vector<>();               // ~17 grow (2x), synchronized add   -> ~18 ms (sync overhead)

Ba kết luận: pre-size nhanh hơn 33% so với no-hint (chi phí ~30 lần resize là thật dù amortized — biết trước n thì new ArrayList<>(n) đáng giá); LinkedList chậm 8x (xác nhận pointer-chasing ở §1); Vector chậm hơn dù single-threaded (synchronization trên mỗi add() không miễn phí).

6. Production gotcha

6.1 Pre-size khi biết trước capacity

// Common anti-pattern: fetch N rows, collect into a default-capacity list
List<User> result = new ArrayList<>(); // start at 10, will resize
while (rs.next()) {
    result.add(mapRow(rs)); // unknown N -> unpredictable grow events
}

// Better: query COUNT first or use limit hint
int expectedSize = getTotalCount();
List<User> result = new ArrayList<>(expectedSize); // 0 grow events
while (rs.next()) {
    result.add(mapRow(rs));
}

// Modern: Stream.toList() for immutable result -- no grow concern at all
List<User> result = users.stream()
    .filter(User::isActive)
    .toList(); // immutable List, internally sized correctly

Stream.toList() (Java 16+) trả về immutable list được stream pipeline sizing sẵn — không grow event, không cần hint capacity thủ công.

6.2 MAX_ARRAY_LENGTH cap và OutOfMemoryError

SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8 — trừ 8 là defensive margin cho array header metadata trên một số JVM (không có spec cứng). Grow không bao giờ vượt cap này; cố cấp phát to hơn sẽ nhận OutOfMemoryError: Requested array size exceeds VM limit. Thực tế heap thường cạn (Java heap space) trước khi chạm cap — nó chỉ relevant với heap vài chục GB và ArrayList cực lớn.

7. Các collection class liên quan

Điểm đáng nhớ duy nhất ở đây là grow strategy khác nhau theo mục đích: Vector (legacy) giữ 2x từ Java 1.0; ArrayDeque từ Java 9 tăng ~1.5x khi array đã lớn (từ 64 phần tử trở lên) và gần gấp đôi khi còn nhỏ — không còn ràng buộc power-of-2 như bản cũ; CopyOnWriteArrayList không grow mà copy đúng kích thước mỗi lần write, đổi write O(n) lấy read lock-free.

HashMap dùng load factor 0.75 và double capacity khi size vượt 0.75 * capacity — chính là bài kế tiếp.

8. Deep Dive tài liệu gốc

Liên kết khoá học khác

• Khoá Thuật toán — Amortized analysis — formal proof O(1) amortized cho dynamic array; bài này là phần hiện thực JDK của proof đó.
• Bài kế tiếp — HashMap internals — cùng câu chuyện resize/amortized, khác chiến lược grow (double + load factor 0.75).
• Khóa Java — Generics & Collections — generics, type erasure trong context của ArrayList.
• Iterator và ConcurrentModificationException — cạm bẫy iteration (subList, modCount) đã tách khỏi phạm vi bài này.

9. Tóm tắt

• ArrayList.grow() trong OpenJDK 21 dùng oldCapacity + (oldCapacity >> 1) — bit shift cho preferred growth = 50%, kết quả là 1.5x capacity mỗi lần grow.
• Lazy initialization: capacity 0 khi khởi tạo, DEFAULT_CAPACITY = 10 chỉ được cấp phát khi add() đầu tiên — tiết kiệm RAM cho list được khởi tạo nhưng không dùng ngay.
• 1.5x không phải 2x vì ba lý do: (1) waste ít RAM hơn — trung bình 17% vs 25%; (2) nhỏ hơn golden ratio φ ≈ 1.618 nên block cũ tái sử dụng được (r = 2.0 vi phạm bound — C++ vector chấp nhận fragmentation đổi lấy ít lần resize); (3) tính bằng bit shift integer, không cần float.
• ArraysSupport.newLength() là grow logic dùng chung cho ArrayList, Vector, StringBuilder/StringBuffer — không phải code riêng từng class (ArrayDeque có grow logic riêng, ~1.5x từ Java 9).
• Pre-size khi biết trước: new ArrayList<>(n) loại bỏ hoàn toàn grow event — nhanh hơn 33% khi insert 1M phần tử. Stream.toList() tự sizing tối ưu.

10. Tự kiểm tra

Bài tiếp theo: HashMap internals — separate chaining + treeify