[Advanced Java] ArrayList vs LinkedList vs Vector: So sánh các implementation của List

Phần 1 của khóa học nói về ngôn ngữ và cách thiết kế bằng ngôn ngữ đó. Phần 2 chuyển sang thư viện mà bạn thiết kế dựa trên nó: Collection Framework, ở mức sâu. Phần này mở đầu bằng ba implementation của List trong java.util, sau đó tới set và map, rồi queue, deque và iteration.

Bài này có tựa đề là một bài so sánh hiệu năng, và nó không công bố một con số millisecond nào. Đó là lựa chọn có chủ ý, được giải thích đầy đủ ở mục thứ hai: một microbenchmark Java tự viết tay thường sai, và một con số sai trong bài hướng dẫn còn tệ hơn là không có con số nào. Mọi thứ bên dưới được dựng từ cấu trúc: số byte đọc trực tiếp từ JVM đang chạy, số thao tác đếm được bằng code có gắn counter, và marker interface mà chính JDK rẽ nhánh theo.

Mọi con số, dòng output và đoạn disassembly bên dưới đều được tạo ra trên OpenJDK 21.0.6 cho arm64. Bài này giả định bạn đã biết API List hằng ngày; đây là lượt thứ hai, nói về cái giá của từng implementation.

Ba implementation của cùng một interface

Cả ba đều lưu một dãy có thứ tự và cả ba đều implement List. Bên dưới thì không giống nhau, và runtime sẽ nói thẳng ra điều đó:

import java.util.*;

public class Shape {
    static void show(Class<?> c) {
        StringBuilder sb = new StringBuilder(c.getSimpleName() + " -> ");
        for (Class<?> i : c.getInterfaces()) sb.append(i.getSimpleName()).append(" ");
        Class<?> sup = c.getSuperclass();
        if (sup != null) sb.append("| extends ").append(sup.getSimpleName());
        System.out.println(sb.toString().trim());
    }

    public static void main(String[] args) {
        show(ArrayList.class);
        show(LinkedList.class);
        show(Vector.class);
        show(Stack.class);
        show(java.util.concurrent.CopyOnWriteArrayList.class);
    }
}

ArrayList -> List RandomAccess Cloneable Serializable | extends AbstractList
LinkedList -> List Deque Cloneable Serializable | extends AbstractSequentialList
Vector -> List RandomAccess Cloneable Serializable | extends AbstractList
Stack -> | extends Vector
CopyOnWriteArrayList -> List RandomAccess Cloneable Serializable | extends Object

Năm dòng cho ra ba sự thật. Vector có cùng hình dạng với ArrayList - một List dựa trên array và có implement RandomAccess. LinkedList implement Deque chứ không implement RandomAccess, và đó chính là toàn bộ cuộc so sánh gói trong một dòng. Còn Stack thì extends Vector, nên Stack thừa hưởng mọi vấn đề nói trong bài này; nó là class legacy và bài 10 của khóa sẽ nói kỹ về nó cùng với Deque.

Mọi dòng trong bảng đó đều được kiểm chứng bằng cách chạy code ở các mục bên dưới.

Vì sao bài này không công bố con số millisecond nào

Có hai lý do, và lý do thứ hai mới là cái đáng để ý.

Lý do thứ nhất mang tính cục bộ: máy chạy các chương trình này đang làm song song nhiều việc khác, nên mọi khoảng thời gian đo được ở đây đều là nhiễu bị thổi phồng. Đó là lý do không nên tin những con số này.

Lý do thứ hai mang tính tổng quát, và nó là lý do không nên tin phần lớn con số Java được công bố. Một microbenchmark viết dưới dạng vòng for bọc quanh System.nanoTime() đo trạng thái biên dịch của JVM ít nhất là ngang với đo code của bạn. Có bốn cơ chế cùng chống lại nó:

Tiered compilation. Method của bạn khởi đầu ở chế độ interpret, rồi được C1 biên dịch, rồi tới C2, và các phiên bản cũ bị vứt đi ngay giữa lúc chạy. -XX:+PrintCompilation cho thấy đúng chuyện đó xảy ra với một vòng lặp theo index rất bình thường trên ArrayList:

12   14       3       java.util.ArrayList::get (15 bytes)
12   17       4       java.util.ArrayList::get (15 bytes)
12   14       3       java.util.ArrayList::get (15 bytes)   made not entrant
13   18 %     3       Warmup::sum @ 4 (38 bytes)
14   19       3       Warmup::sum (38 bytes)
14   20 %     4       Warmup::sum @ 4 (38 bytes)
15   18 %     3       Warmup::sum @ 4 (38 bytes)   made not entrant
15   21       4       Warmup::sum (38 bytes)
16   19       3       Warmup::sum (38 bytes)   made not entrant

Cột đầu tiên là mốc millisecond của sự kiện biên dịch, không phải kết quả đo bất cứ thứ gì list làm. Cột đáng nhìn là cột tier: 3 là C1, 4 là C2. ArrayList::get bị biên dịch hai lần và bản đầu bị loại; Warmup::sum bị biên dịch bốn lần. Một benchmark bấm đồng hồ trước khi mọi thứ ổn định thì đang đo cái interpreter.

On-stack replacement. Dấu % trên ba dòng đó đánh dấu một bản biên dịch OSR: JVM thay thế method ngay khi vòng lặp bên trong nó vẫn đang chạy, vì vòng lặp nóng lên trước khi method kịp được gọi đủ nhiều lần. Code OSR được biên dịch với giả định khác code thường, nên một benchmark dồn hết việc vào một vòng lặp dài có thể đang đo một phiên bản code không bao giờ chạy trong production.

Dead-code elimination. Nếu một vòng lặp tính ra kết quả mà không ai đọc, C2 có quyền xóa luôn vòng lặp. Triệu chứng kinh điển là một benchmark báo ra thời gian nhỏ đến mức vô lý, và càng thêm việc vào thì càng nhanh hơn.

Cấp phát và garbage collector. LinkedList cấp phát một object cho mỗi element còn ArrayList cấp phát theo từng đợt, nên mọi so sánh giữa hai bên đều có phần là so sánh garbage collector, so sánh kích thước heap, và so sánh xem có lần thu gom nào rơi đúng vào khoảng đang đo hay không.

Đó chính là lý do JMH tồn tại. Nó là harness benchmark của chính OpenJDK, và toàn bộ thiết kế của nó là một danh sách những cái bẫy trên: @Warmup và @Measurement tách vòng khởi động khỏi vòng được đo, @Fork chạy mỗi benchmark trong một JVM mới để benchmark này không làm hỏng profile của benchmark kia, @State giữ dữ liệu đầu vào ra ngoài phần code được tính giờ, Blackhole tiêu thụ kết quả để chúng không bị tối ưu mất, và -prof gc báo tốc độ cấp phát bên cạnh thời gian để bạn thấy khi nào mình đang đo garbage collector.

Một phép so sánh đúng đắn cho ba class này phải kiểm soát hết tất cả: chạy nóng tới trạng thái ổn định, mỗi trường hợp một JVM riêng, dữ liệu đầu vào dựng bên ngoài vùng đo, kết quả được tiêu thụ, heap và collector cố định, nhiều fork để lộ ra độ dao động giữa các lần chạy, và báo cả sai số chứ không phải một con số duy nhất. Đó là một khối lượng công việc nghiêm túc, mà kết quả vẫn chỉ đúng cho một máy và một bản JDK.

Vì vậy bài này dùng loại bằng chứng không đổi khi máy đang bận:

• số đếm - một lời gọi thực hiện bao nhiêu lần copy element, bao nhiêu bước nhảy pointer, bao nhiêu lần cấp phát, đo bằng code có counter tái hiện đúng thuật toán của JDK;
• số byte - chi phí bộ nhớ thật cho mỗi element, đọc từ JVM đang chạy qua field offset và được xác nhận lại bằng một phép đo heap;
• cấu trúc - JDK trong chính source của nó làm khác đi những gì cho implementation này mà không làm cho implementation kia.

Chỗ nào cấu trúc quyết định được câu trả lời, bài sẽ nói rõ. Chỗ nào chỉ benchmark mới quyết được, bài cũng nói rõ như vậy.

Một element tốn bao nhiêu bộ nhớ

Phát biểu đáng tin nhất về ba class này là phát biểu về bộ nhớ, và nó suy ra được chính xác chứ không phải ước lượng. Unsafe cho biết những field offset mà JVM thực sự chọn:

import java.lang.reflect.Field;

public class Layout {
    public static void main(String[] args) throws Exception {
        Field theUnsafe = sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
        theUnsafe.setAccessible(true);
        sun.misc.Unsafe u = (sun.misc.Unsafe) theUnsafe.get(null);

        Class<?> node = Class.forName("java.util.LinkedList$Node");
        for (Field f : node.getDeclaredFields())
            System.out.printf("  %-6s %-8s offset %d%n",
                    f.getName(), f.getType().getSimpleName(), u.objectFieldOffset(f));

        System.out.println("arrayBaseOffset(Object[]) = " + u.arrayBaseOffset(Object[].class));
        System.out.println("arrayIndexScale(Object[]) = " + u.arrayIndexScale(Object[].class));
    }
}

  item   Object   offset 12
  next   Node     offset 16
  prev   Node     offset 20
arrayBaseOffset(Object[]) = 16
arrayIndexScale(Object[]) = 4

Toàn bộ phép suy ra nằm ở đó. Field đầu tiên của một Node nằm ở offset 12, nên header của object là 12 byte. Mỗi reference trong ba cái chiếm 4 byte, vì JVM này bật UseCompressedOops - đã xác nhận bằng java -XX:+PrintFlagsFinal -version. Byte cuối cùng được dùng là byte 23, và ObjectAlignmentInBytes bằng 8, nên một Node đúng bằng 24 byte. Một Object[] có header 16 byte và 4 byte cho mỗi slot, nên một element trong ArrayList tốn 4 byte cộng thêm phần chia sẻ của header array.

Một phép đo heap khớp tới từng byte. Cả hai list đều được đổ đầy từ cùng một array Integer, nên chỉ phần cấu trúc của list được tính:

import java.util.*;

public class Footprint {
    static Object keepAlive;
    static long used() {
        Runtime r = Runtime.getRuntime();
        for (int i = 0; i < 8; i++) { System.gc(); try { Thread.sleep(80); } catch (Exception e) {} }
        return r.totalMemory() - r.freeMemory();
    }

    public static void main(String[] args) {
        int n = 2_000_000;
        Integer[] shared = new Integer[n];
        for (int i = 0; i < n; i++) shared[i] = Integer.valueOf(i);
        keepAlive = shared;

        long b1 = used();
        List<Integer> al = new ArrayList<>(n);
        for (int i = 0; i < n; i++) al.add(shared[i]);
        keepAlive = new Object[]{shared, al};
        long a1 = used();

        long b2 = used();
        List<Integer> ll = new LinkedList<>();
        for (int i = 0; i < n; i++) ll.add(shared[i]);
        keepAlive = new Object[]{shared, al, ll};
        long a2 = used();

        System.out.printf("  ArrayList  structure = %,d bytes = %.2f bytes per element%n",
                a1 - b1, (a1 - b1) / (double) n);
        System.out.printf("  LinkedList structure = %,d bytes = %.2f bytes per element%n",
                a2 - b2, (a2 - b2) / (double) n);
    }
}

  ArrayList  structure = 8,000,176 bytes = 4.00 bytes per element
  LinkedList structure = 48,000,544 bytes = 24.00 bytes per element

Gấp sáu lần bộ nhớ, và giống hệt nhau qua nhiều lần chạy lại. Field keepAlive không phải để trang trí: thiếu nó, JVM được phép thu gom shared ngay trong lúc đo lần cuối, và con số của LinkedList sẽ thấp đi 4 byte trên mỗi element.

Hai điểm cần nói cho sòng phẳng. ArrayList ở đây được khởi tạo đúng bằng size cuối cùng nên không dư slot nào; một list lớn dần bằng add liên tiếp thì có dư. Dựng 100.000 element mà không gợi ý size sẽ để lại capacity 106.710, tức dư 6,7%, đưa con số thật lên khoảng 4,27 byte mỗi element. Và cả hai con số đều không tính bản thân các element, vì chúng dùng chung và giống nhau ở cả hai bên.

Lập luận về cache locality bắt nguồn từ đây, và nó là lập luận cấu trúc chứ không phải kết quả bấm giờ. Một cache line trên CPU hiện đại là 64 byte. Mười sáu reference liền nhau của ArrayList nằm gọn trong một cache line, nên đi dọc list là chạm vào vùng bộ nhớ mà prefetcher đoán trước được. Đi dọc một LinkedList là lần theo next từ object 24 byte này sang object 24 byte khác ở bất cứ chỗ nào allocator đặt nó, và mỗi bước là một dependent load: chưa lấy được node hiện tại thì chưa biết địa chỉ node kế tiếp. Đó mới là lý do thật khiến ArrayList thường thắng trong thực tế, và nó là lập luận về layout chứ không phải một con số trên đồng hồ.

Đếm khối lượng công việc: copy, bước nhảy và cấp phát

Số thao tác đếm được thì tái lập lại được trên mọi máy, dưới mọi mức tải. Các con số dưới đây đến từ một chương trình tái hiện chính code của JDK và gắn thêm counter - System.arraycopy dịch size - index reference cho ArrayList.add(int, E), dịch size - 1 - index cho remove(int), còn LinkedList thì dùng đúng vòng node(int) xuất phát từ đầu nào gần hơn:

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Bản tái hiện được đối chiếu với class thật trước khi đếm bất cứ thứ gì: cùng một chuỗi lời gọi add, add(int, E) và remove(int) được áp lên cả hai, rồi so nội dung kết quả.

replay matches ArrayList : true
replay matches LinkedList: true

Trên một list 100.000 element, một lời gọi tốn chừng này:

Hãy đọc kỹ mấy dòng ở giữa, vì đó là chỗ lời khuyên phổ biến nói sai. Xóa ở giữa khiến LinkedList tốn đúng bằng ArrayList: 49.999 cả hai bên. LinkedList tiêu số đó vào việc đi bộ thay vì copy, mà đi bộ mới là loại việc đắt hơn - System.arraycopy là một lần chuyển khối trên vùng nhớ liền nhau, còn 49.999 bước nhảy pointer là 49.999 dependent load rải khắp các object được cấp phát rời nhau. Bằng nhau trên máy đếm, không hề bằng nhau trên phần cứng.

Chỗ LinkedList thắng thẳng là ở đầu list. add(0, e) và remove(0) không tốn gì cả, trong khi ArrayList phải dịch cả array. Chỗ nó không thắng được gì là ở cuối, vì thêm vào cuối một ArrayList vốn đã gần như miễn phí.

Đọc theo index là nửa còn lại của bức tranh. LinkedList.get(i) xuất phát từ đầu gần hơn, nên trường hợp xấu nhất giảm một nửa nhưng bản chất không đổi:

LinkedList.get(i) pointer hops, size 100000
  get(0     ) = 0 hops
  get(1     ) = 1 hops
  get(25000 ) = 25000 hops
  get(49999 ) = 49999 hops
  get(50000 ) = 49999 hops
  get(75000 ) = 24999 hops
  get(99998 ) = 1 hops
  get(99999 ) = 0 hops

⚠️ Đọc hết một list bằng for (int i = 0; i < list.size(); i++) list.get(i) tốn của ArrayList 100.000 lần đọc array và tốn của LinkedList 2.499.950.000 bước nhảy pointer. Vòng lặp theo index là tuyến tính với bên này và bậc hai với bên kia. Enhanced for loop tuyến tính với cả hai, vì iterator giữ nguyên vị trí thay vì đi lại từ đầu.

Cấp phát là trục cuối cùng, và đó là chỗ tính cách hai class khác nhau nhiều nhất:

building 100000 elements with add(e)
  ArrayList : 24 array allocations, 320123 slots allocated in total, 213413 references copied
  LinkedList: 100000 Node allocations, 0 references copied

ArrayList cấp phát 24 lần trong lúc lớn dần tới 100.000, copy khoảng 2,13 reference mỗi element tính trên toàn bộ quá trình - đó chính là ý nghĩa thực tế của "amortised constant time". LinkedList không copy gì và không bao giờ cấp phát lại, đổi lại là 100.000 lần cấp phát object riêng lẻ, mỗi cái 24 byte heap sống mà collector phải duyệt qua.

RandomAccess: marker mà JDK thật sự rẽ nhánh theo

RandomAccess không có method nào. Toàn bộ nội dung của nó là phần javadoc, trong đó phát biểu quy tắc rất rõ: một List nên implement nó nếu, với các instance điển hình, vòng lặp theo index chạy nhanh hơn vòng lặp bằng iterator. ArrayList và Vector có implement, LinkedList thì không:

ArrayList            instanceof RandomAccess : true
Vector               instanceof RandomAccess : true
LinkedList           instanceof RandomAccess : false
List.of(1, 2)        instanceof RandomAccess : true
Arrays.asList(1, 2)  instanceof RandomAccess : true

Đây không phải chuyện tài liệu. java.util.Collections nhắc tới RandomAccess mười sáu lần: mười lần trong đó chọn giữa thuật toán theo index và thuật toán chạy bằng iterator, sáu lần còn lại chọn trả về class wrapper nào. Khác biệt đó quan sát được. Phép thử dưới đây bọc cùng 10.000 element vào hai list ủy quyền có thân class giống hệt nhau - khác biệt duy nhất là một bên implement marker - rồi đếm xem JDK chạm tới element bằng cách nào:

static class Counting extends AbstractList<Integer> {
    final List<Integer> delegate;
    int getCalls, setCalls, iteratorCalls, toArrayCalls;
    Counting(List<Integer> d) { delegate = d; }
    public Integer get(int i) { getCalls++; return delegate.get(i); }
    public Integer set(int i, Integer v) { setCalls++; return delegate.set(i, v); }
    public int size() { return delegate.size(); }
    public ListIterator<Integer> listIterator() { iteratorCalls++; return delegate.listIterator(); }
    public ListIterator<Integer> listIterator(int i) { iteratorCalls++; return delegate.listIterator(i); }
    public Object[] toArray() { toArrayCalls++; return delegate.toArray(); }
}

/** Thân class giống hệt. Khác biệt duy nhất là marker interface. */
static class CountingRA extends Counting implements RandomAccess {
    CountingRA(List<Integer> d) { super(d); }
}

Collections.binarySearch
  plain List   get(i)=0      set(i,e)=0      listIterator()=1  toArray()=0
  RandomAccess get(i)=13     set(i,e)=0      listIterator()=0  toArray()=0
Collections.shuffle
  plain List   get(i)=0      set(i,e)=0      listIterator()=1  toArray()=1
  RandomAccess get(i)=9999   set(i,e)=19998  listIterator()=0  toArray()=0
Collections.fill
  plain List   get(i)=0      set(i,e)=0      listIterator()=1  toArray()=0
  RandomAccess get(i)=0      set(i,e)=10000  listIterator()=0  toArray()=0

Hai thuật toán hoàn toàn khác nhau, chọn bằng một phép instanceof. List có marker nhận được binary search nhảy tới 13 index; list không có marker nhận được phiên bản chạy bằng ListIterator. List có marker nhận được shuffle Fisher-Yates tại chỗ theo index; list không có marker thì bị copy ra array, xáo ở đó, rồi ghi ngược lại qua iterator - đúng là JDK đang bảo vệ một linked list khỏi 10.000 lần đi bộ.

Trong source, đó chỉ là một dòng rẽ nhánh, lặp lại với các ngưỡng khác nhau:

public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

Hệ quả thực tế nằm ở code bạn viết. Nếu bạn nhận vào một parameter kiểu List rồi truy cập element theo index trong vòng lặp, bạn vừa viết một thuật toán bậc hai với một nửa số implementation có thể được truyền vào. Cách JDK xử lý là hoặc kiểm tra instanceof RandomAccess rồi đi đường khác, hoặc dùng iterator để tuyến tính ở mọi trường hợp.

Khi nào LinkedList thắng thật sự

Có hai trường hợp, và cả hai đều hẹp hơn lời đồn nhiều.

Khi bạn đã cầm sẵn vị trí. Việc chèn rẻ của LinkedList cần một cursor, không phải một index. Nếu code viết list.add(i, x) thì vòng đi bộ quay lại ngay, vì đi bộ chính là cách tìm ra cursor. Nếu code viết it.add(x) trên một ListIterator bạn đang cầm, thì không có bước đi bộ nào cả. Chèn một dấu phân cách trước mỗi element của list 20.000 phần tử, ba cách:

ArrayList,  by index          :     400,052,697 element copies
LinkedList, by index          :     133,320,000 pointer hops
LinkedList, at a held cursor  :               0 pointer hops
all three produced 40000 / 40000 / 40000 elements

Bằng không. Không phải "ít hơn" - bằng không. Hai cách còn lại làm hàng trăm triệu đơn vị công việc để ra cùng một kết quả. Đó chính là trường hợp LinkedList được thiết kế cho, và nó hoàn toàn vô hình với code truy cập element theo index:

LinkedList<String> real = new LinkedList<>(List.of("a", "b", "c"));
for (ListIterator<String> it = real.listIterator(); it.hasNext(); ) {
    it.next();
    it.add("-");
}
System.out.println(real);

[a, -, b, -, c, -]

Cùng vòng lặp đó trên ArrayList cho ra cùng một list và không tiết kiệm được gì, vì ListIterator.add của ArrayList vẫn phải dịch phần đuôi của array. Cầm cursor giúp ích cho implementation lưu vị trí bằng object; nó không giúp gì cho implementation lưu vị trí bằng offset.

Khi bạn làm việc ở cả hai đầu. LinkedList implement Deque, nên addFirst, addLast, removeFirst và removeLast đều chỉ là vài phép gán pointer, không dịch chuyển và không bao giờ cấp phát lại. Bài 10 của khóa này nói kỹ về Deque và các implementation của nó, bao gồm lựa chọn dựa trên array thường là tốt hơn khi bạn không cần nó đồng thời là List.

Mọi công trạng khác gán cho LinkedList đều không sống sót qua phép đếm. Nó không tiết kiệm bộ nhớ - nó tốn gấp sáu lần mỗi element. Nó không làm việc xóa rẻ đi nói chung - chỉ rẻ ở vị trí bạn đang cầm sẵn. Và nó không làm contains hay indexOf nhanh hơn; cả hai đều là quét tuyến tính ở cả hai class.

ensureCapacity và trimToSize

ArrayList mở ra hai method chạm thẳng vào backing array, và reflection cho thấy tác dụng của chúng:

new ArrayList<>()            size=0 capacity=0
  ensureCapacity(8)          size=0 capacity=0
  ensureCapacity(11)         size=0 capacity=11
new + ensureCapacity(1000)   size=0 capacity=1000
  after 1000 adds            size=1000 capacity=1000
  add #1001                  size=1001 capacity=1500
1000 adds, no hint           size=1000 capacity=1234
  trimToSize()               size=1000 capacity=1000
  clear()                    size=0 capacity=1000
  trimToSize()               size=0 capacity=0
  add after trim             size=1 capacity=1

Bốn điều trong vết chạy đó đáng nhớ.

ensureCapacity(8) không làm gì cả. Trên một list vẫn đang giữ array mặc định dùng chung, JDK bỏ qua mọi yêu cầu tới 10, vì lần add đầu tiên dù sao cũng cấp phát 10:

public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

ensureCapacity(1000) cấp phát đúng 1000 slot, và lần add thứ 1001 nâng lên 1500 - quy tắc 1.5x thông thường tiếp quản ngay khi đã có array thật. Gợi ý size chặn được chuỗi tăng capacity; nó không đổi chính sách về sau.

clear() không trả bộ nhớ lại. Capacity vẫn là 1000 với size 0, và đó là mặc định đúng - list bạn vừa dọn sạch thường là list bạn sắp đổ đầy lại - nhưng nó có nghĩa là một ArrayList sống lâu từng chứa một triệu element thì vẫn đang giữ một triệu slot.

trimToSize() trên list rỗng trả array lại hoàn toàn, và lần add kế tiếp cấp phát một slot chứ không phải mười. Đó không phải bug; trimToSize gắn vào EMPTY_ELEMENTDATA, một sentinel khác với DEFAULTCAPACITY_EMPTY_ELEMENTDATA mà list mới toanh mang theo, và chỉ cái sau mới kích hoạt mặc định 10.

Vector cũng có cả hai method đó, cộng thêm một capacity() public mà ArrayList cố tình không mở ra. Cần đọc capacity của một list gần như luôn là dấu hiệu abstraction đã rò rỉ.

Vector: khóa mọi lời gọi, và điều đó không mua được gì

Vector có trước Collection Framework - nó xuất hiện trong Java 1.0 và được gắn vào List ở bản 1.2. Javadoc của chính nó nói rõ nên làm gì với chuyện đó:

As of the Java 2 platform v1.2, this class was retrofitted to implement the List
interface, making it a member of the Java Collections Framework. Unlike the new
collection implementations, Vector is synchronized. If a thread-safe
implementation is not needed, it is recommended to use ArrayList in place of
Vector.

Phần synchronized là thật và làm rất kỹ. Đếm modifier bằng reflection:

Vector                 public instance methods = 49  synchronized = 38
ArrayList              public instance methods = 38  synchronized = 0
CopyOnWriteArrayList   public instance methods = 43  synchronized = 0

Mười một cái không mang modifier đó không phải là lỗ hổng. javap cho thấy quy luật, đã lược bớt để giữ những dòng đáng chú ý:

  public synchronized int size();
  public synchronized boolean isEmpty();
  public boolean contains(java.lang.Object);
  public int indexOf(java.lang.Object);
  public synchronized E get(int);
  public synchronized E set(int, E);
  public synchronized boolean add(E);
  public boolean remove(java.lang.Object);
  public void add(int, E);
  public synchronized E remove(int);
  public void clear();

Mỗi cái không đánh dấu đều ủy quyền cho một cái có đánh dấu - contains(o) là indexOf(o, 0) >= 0, add(int, E) là insertElementAt, clear() là removeAllElements() - hoặc tự lấy monitor bằng khối synchronized (this) tường minh, như addAll(Collection) làm. Mọi thao tác public trên một Vector đều được canh giữ.

Đảm bảo đó thật ra là gì

Một lời gọi trên Vector là atomic so với các lời gọi khác trên cùng Vector đó, và nó công bố các thay đổi của mình cho ai gọi tiếp theo. Điều đó thật sự hữu ích, và cũng thật sự là tất cả những gì bạn nhận được. Nó không mở rộng ra hai lời gọi, mà gần như mọi việc bạn muốn làm đều không gói trong một lời gọi.

Ví dụ kinh điển là check-then-act:

static void addIfAbsent(Vector<String> v, String s) {
    if (!v.contains(s)) {
        v.add(s);
    }
}

contains lấy lock, trả lời, rồi nhả ra. add lấy lock, thêm vào, rồi nhả ra. Giữa hai cái là một khoảnh khắc không ai giữ gì cả. Compiler nói ra điều đó hoàn toàn tường minh:

static void addIfAbsent(java.util.Vector<java.lang.String>, java.lang.String);
    Code:
       0: aload_0
       1: aload_1
       2: invokevirtual #7    // Method java/util/Vector.contains:(Ljava/lang/Object;)Z
       5: ifne          14
       8: aload_0
       9: aload_1
      10: invokevirtual #13   // Method java/util/Vector.add:(Ljava/lang/Object;)Z
      13: pop
      14: return

Trong method đó không có monitorenter và cũng không có monitorexit. Toàn bộ việc khóa diễn ra bên trong các method được gọi, và đó chính là vấn đề: chuỗi thao tác không được canh giữ. Tự lấy lock sẽ đổi bytecode:

static void addIfAbsent(Vector<String> v, String s) {
    synchronized (v) {
        if (!v.contains(s)) {
            v.add(s);
        }
    }
}

       0: aload_0
       1: dup
       2: astore_2
       3: monitorenter
       4: aload_0
       5: aload_1
       6: invokevirtual #7    // Method java/util/Vector.contains:(Ljava/lang/Object;)Z
       9: ifne          18
      12: aload_0
      13: aload_1
      14: invokevirtual #13   // Method java/util/Vector.add:(Ljava/lang/Object;)Z
      17: pop
      18: aload_2
      19: monitorexit
      20: goto          28
      23: astore_3
      24: aload_2
      25: monitorexit
      26: aload_3
      27: athrow
      28: return

monitorenter ở 3, monitorexit ở 19 trên đường bình thường và ở 25 trên đường có exception. Giờ cả cặp mới là một thao tác. Hãy để ý điều này có nghĩa gì: ngay khi bạn cần một thao tác ghép, bạn viết đúng cái khối synchronized mà bạn cũng sẽ viết quanh một ArrayList, và phần khóa sẵn của Vector trở thành công việc thừa thực hiện bên trong một lock bạn vốn đang giữ.

Đó là chỗ tạo cảm giác an toàn giả. Vector trong một dòng khai báo trông như một quyết định về tính đúng đắn, mà thật ra nó quyết ít hơn vẻ ngoài rất nhiều.

Và cái giá phải trả

Khóa thì không miễn phí. Mỗi lời gọi đều phải trả tiền cho một lần lấy và nhả monitor kể cả trong chương trình chỉ có một thread, và một synchronized method là mục tiêu khó nhằn hơn cho JIT so với một method thường. Nó tốn bao nhiêu trong một chương trình cụ thể chính là loại câu hỏi mà bài này từ chối trả lời bằng con số bịa - nó phụ thuộc vào inlining, vào lock elision, vào JVM, và cần một benchmark JMH đàng hoàng mới trả lời trung thực được. Điều nói được mà không cần đo là: cái giá đó trả trên mọi lời gọi, và trong chương trình một thread nó không mua được gì cả.

Chính sách tăng capacity của Vector so với ArrayList

Cả hai class đều tăng qua cùng một hàm phụ trợ, và truyền vào một mong muốn khác nhau. ArrayList:

int oldCapacity = elementData.length;
int newCapacity = ArraysSupport.newLength(oldCapacity,
        minCapacity - oldCapacity, /* minimum growth */
        oldCapacity >> 1           /* preferred growth */);

Vector:

int oldCapacity = elementData.length;
int newCapacity = ArraysSupport.newLength(oldCapacity,
        minCapacity - oldCapacity, /* minimum growth */
        capacityIncrement > 0 ? capacityIncrement : oldCapacity
                                   /* preferred growth */);

oldCapacity >> 1 là một nửa, nên ArrayList tăng theo hệ số 1.5x. oldCapacity là toàn bộ, nên Vector tăng gấp đôi - trừ khi bạn truyền capacityIncrement vào constructor, lúc đó nó tăng thêm đúng bấy nhiêu slot mỗi lần. Đọc elementData của cả hai sau mỗi lần add cho thấy đủ ba chính sách:

ArrayList capacity        : 0, 10, 15, 22, 33, 49, 73, 109, 163, 244, 366
Vector capacity           : 10, 20, 40, 80, 160, 320
Vector(10, 25) capacity   : 10, 35, 60, 85, 110, 135, 160, 185, 210, 235, 260, 285, 310
Vector(1) capacity        : 1, 2, 4, 8, 16, 32, 64
ArrayList(1) capacity     : 1, 2, 3, 4, 6, 9, 13, 19, 28, 42

Hai dòng đầu còn cho thấy một khác biệt ngay ở vị trí đầu tiên. Một ArrayList mới bắt đầu ở capacity 0 - nó dùng chung một array rỗng static và không cấp phát gì cho tới lần add đầu tiên. Một Vector mới cấp phát mười slot ngay trong constructor, dùng hay không dùng cũng vậy.

Gấp đôi so với một nửa là một sự đánh đổi thật, và nó đi cả hai chiều:

building 100000 elements with add(e)
  ArrayList  grows=24  references copied=213413  copies/element=2.13  final capacity=106710  slack=6710
  Vector     grows=14  references copied=163830  copies/element=1.64  final capacity=163840  slack=63840
  new ArrayList<>(100000)  grows=0  references copied=0

Vector cấp phát lại ít hơn mười lần và copy ít hơn 50.000 reference - đổi lại nó ôm 63.840 slot không dùng, so với 6.710 của ArrayList. Gấp đôi mua được ít lần copy hơn bằng bộ nhớ lãng phí; 1.5x mua được bộ nhớ chặt hơn bằng nhiều lần copy hơn. Không bên nào sai, và lựa chọn của ArrayList là mặc định tốt hơn vì phần copy là một lần chuyển khối bộ nhớ còn phần lãng phí thì nằm lại vĩnh viễn.

capacityIncrement là tùy chọn nên tránh. Một mức tăng cố định biến tăng trưởng hình học thành tăng trưởng tuyến tính, và tổng khối lượng copy trở thành bậc hai:

Vector(10, 0    ) grows=14     references copied=        163,830 final capacity=163840
Vector(10, 100  ) grows=1000   references copied=     49,960,000 final capacity=100010
Vector(10, 1000 ) grows=100    references copied=      4,951,000 final capacity=100010

Copy gấp ba trăm lần để tiết kiệm 63.830 slot. Con số capacity cuối cùng gọn gàng trông rất hấp dẫn cho tới khi bạn thấy giá của nó; nếu muốn một array chặt, hãy khai báo đúng size lúc khởi tạo hoặc gọi trimToSize() ở cuối.

Nên dùng gì thay cho Vector

Không có gì ở Vector là không sửa được - chỉ là mọi lý do để chọn nó bây giờ đều có câu trả lời tốt hơn.

Collections.synchronizedList chính là cơ chế khóa của Vector áp lên list bạn tự chọn, và nó giữ lại marker interface khi có thể:

synchronizedList class       : java.util.Collections$SynchronizedRandomAccessList
synchronizedList(LinkedList) : java.util.Collections$SynchronizedList
synchronizedList RandomAccess: true
its iterator class           : java.util.ArrayList$Itr

Hãy nhìn dòng cuối. iterator() của wrapper trả về iterator của chính list bên dưới, và cái đó hoàn toàn không synchronized - javadoc của nó nói thẳng ra như vậy:

It is imperative that the user manually synchronize on the returned list when
traversing it via Iterator, Spliterator or Stream:

 List list = Collections.synchronizedList(new ArrayList());
     ...
 synchronized (list) {
     Iterator i = list.iterator(); // Must be in synchronized block
     while (i.hasNext())
         foo(i.next());
 }

Và đó vẫn là kết luận cũ: khóa theo từng lời gọi không bao giờ phủ được một chuỗi thao tác, dù nó đến từ Vector hay từ một wrapper.

CopyOnWriteArrayList đi theo hướng ngược lại, và cái giá của nó rất dễ chứng minh. Field array private của nó bị thay mới sau mỗi lần ghi:

  add(0) -> array length 1, same array object as before: false
  add(1) -> array length 2, same array object as before: false
  ...
  add(9) -> array length 10, same array object as before: false
array replaced 10 times in 10 adds

Mười lần add, mười array mới, không bao giờ có slot dư. Javadoc của nó nói rất thẳng về khi nào chấp nhận được điều đó - "ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations". Một registry listener được đọc ở mọi event và chỉ ghi hai lần lúc khởi động là đúng hình dạng đó; một list bạn append trong vòng lặp thì không.

Iterator của Vector là fail-fast giống như của ArrayList, và bài 11 của khóa này nói kỹ về chuyện đó. Nhắc ở đây chỉ vì "synchronized" và "an toàn khi duyệt trong lúc thread khác sửa" là hai tuyên bố khác nhau, còn Vector chỉ đưa ra tuyên bố thứ nhất.

Chọn giữa ba class

Quy tắc rất ngắn, và không chỗ nào cần tới đồng hồ bấm giờ.

• Dùng ArrayList. Đây là mặc định đúng cho gần như mọi code làm việc với list: 4 byte mỗi element, lưu liền khối, truy cập theo index miễn phí, thêm vào cuối gần như miễn phí, và không có khóa nào bạn không yêu cầu.
• Chỉ dùng LinkedList khi bạn cầm cursor hoặc làm việc ở hai đầu. Một ListIterator đậu sẵn ở chỗ cần sửa, hoặc một hàng đợi lấy ra ở đầu và thêm vào ở cuối. Nếu code có list.get(i) hay list.add(i, x) thì bạn không cầm cursor và trường hợp này không áp dụng.
• Đừng dùng Vector trong code mới. Mọi lý do chọn nó đều được phục vụ tốt hơn bởi ArrayList với khối synchronized do bạn kiểm soát, Collections.synchronizedList, hoặc CopyOnWriteArrayList - và cái đầu tiên chính là thứ bạn rốt cuộc vẫn phải viết ngay khi cần hai thao tác xảy ra cùng nhau.
• Khai báo size khi bạn biết size. new ArrayList<>(n) xóa sạch chuỗi tăng capacity với cái giá là một số nguyên.
• Nếu bạn thật sự cần một con số thời gian, hãy đo bằng JMH, trên một máy rảnh, trên đúng bản JDK bạn deploy, với đúng dữ liệu bạn có. Đừng tin bảng millisecond trong bài viết - kể cả cái bảng bạn có thể đã tưởng sẽ tìm thấy trong bài này.

FAQ

LinkedList có thật sự nhanh hơn khi thêm và xóa không?

Chỉ ở vị trí bạn đã cầm sẵn. Đếm trên list 100.000 element, xóa ở giữa tốn của LinkedList 49.999 bước nhảy pointer và tốn của ArrayList 49.999 lần copy element - cùng một con số, nhưng phía LinkedList tiêu vào loại việc đắt hơn, vì một chuỗi dependent load rải khắp heap chậm hơn một lần arraycopy khối trên vùng nhớ liền nhau. LinkedList chỉ thắng thẳng ở đầu list, và thắng áp đảo khi vị trí đến từ một ListIterator thay vì một index: 0 bước nhảy so với 133.320.000 cho cùng một việc.

LinkedList tốn thêm bao nhiêu bộ nhớ?

Gấp sáu lần cho phần cấu trúc list, đo bằng hai cách độc lập trên OpenJDK 21 với compressed oops. Mỗi LinkedList$Node là 24 byte - header object 12 byte cộng item, next và prev mỗi cái 4 byte - so với 4 byte cho một slot của Object[]. Phép đo heap trên 2.000.000 element khớp chính xác: 48.000.544 byte so với 8.000.176.

Vector có thread-safe không?

Từng lời gọi riêng lẻ thì có, và đó là toàn bộ đảm bảo. Một chuỗi lời gọi thì không, nên if (!v.contains(x)) v.add(x) không an toàn dù hai method kia có synchronized đến đâu - bytecode không có lệnh monitor nào nằm giữa chúng. Mọi thao tác ghép đều cần một khối synchronized của riêng bạn, và một khi đã viết khối đó thì phần khóa sẵn của Vector là thừa.

Có nên dùng Vector cho việc gì trong code mới không?

Không. Javadoc của chính nó khuyên dùng ArrayList khi không cần thread safety, còn khi cần thì Collections.synchronizedList cho đúng cùng một đảm bảo theo từng lời gọi trên bất kỳ list nào, và CopyOnWriteArrayList cho đảm bảo mạnh hơn trong các tình huống thiên về đọc. Vector còn tăng capacity gấp đôi trong khi ArrayList tăng một nửa, nên sau 100.000 lần append nó ôm 63.840 slot dư so với 6.710 của ArrayList. Code cũ đang dùng nó thì vẫn ổn; code mới có lựa chọn tốt hơn.

ensureCapacity có tạo ra khác biệt thật không?

Nó xóa bỏ chuỗi tăng capacity, điều đó là thật nhưng có giới hạn. Dựng 100.000 element không có gợi ý tốn 24 lần cấp phát array và 213.413 reference được copy, khoảng 2,13 mỗi element; new ArrayList<>(100000) tốn 0 cả hai. Đáng làm khi bạn biết size, không đáng làm khi phải đoán. Lưu ý rằng ensureCapacity(n) với mọi n tới 10 trên một list mới thì không làm gì cả, và đó là chủ ý.

Vì sao ArrayList vẫn giữ bộ nhớ sau khi clear()?

Vì clear() chỉ gán null cho các slot và đặt lại size; bản thân array vẫn nằm đó. Một list từng chứa một triệu element thì sau đó vẫn sở hữu một array một triệu slot. trimToSize() là thứ duy nhất trả nó lại, và trên một list rỗng nó nhả hẳn array - sau đó lần add kế tiếp cấp phát đúng một slot chứ không phải mười như thường lệ, vì array sentinel mà nó gắn vào không phải cái kích hoạt capacity mặc định.

Kết luận

Ba implementation phân chia rất rõ ràng khi bạn thôi hỏi cái nào nhanh nhất và bắt đầu hỏi mỗi cái lưu gì. ArrayList giữ một reference cho mỗi element trong một array dùng chung: 4 byte mỗi cái, liền khối, truy cập theo index miễn phí, thêm vào cuối được phân bổ đều qua 24 lần cấp phát lại cho mỗi 100.000 element. LinkedList giữ một Node 24 byte cho mỗi element: không dịch chuyển và không bao giờ cấp phát lại, đổi lại là gấp sáu lần bộ nhớ, một lần cấp phát cho mỗi element, và một vòng đi bộ cho mọi vị trí không nằm ở hai đầu. Vector là ArrayList của năm 1996 với một monitor quanh mọi lời gọi và chính sách tăng gấp đôi, mà cái monitor đó chỉ canh giữ được một lời gọi mỗi lần - vốn không bao giờ là mức chi tiết mà một chương trình thật cần.

Không chỗ nào trong đó cần đồng hồ bấm giờ, và đó chính là điểm mấu chốt. Field offset, số thao tác đếm được, một phép instanceof bên trong Collections, và sự có mặt hay vắng mặt của monitorenter trong bytecode đều tái lập lại được trên mọi máy, dưới mọi mức tải, trên mọi bản build. Một microbenchmark thì không, và đó là lý do JMH tồn tại cũng như lý do phiên bản trung thực của phép so sánh này công bố số đếm thay vì millisecond.

Bài 8 rời bỏ vị trí có thứ tự để chuyển sang chuyện thành viên: Set và ba implementation của nó - HashSet, LinkedHashSet và TreeSet - mỗi cái xử lý thứ tự ra sao, và hỏi xem một giá trị đã có ở đó chưa thì tốn bao nhiêu.