Phần trước kết thúc bằng một câu hỏi treo: immutable an toàn khi chia sẻ, nhưng "sửa" bằng cách copy cả đối tượng thì đắt — làm sao vừa immutable vừa sửa nhanh?

Nghĩ tới cách Git lưu lịch sử. Mỗi commit không chép lại toàn bộ dự án; nó chỉ ghi những file thay đổi, còn mọi file không đổi thì trỏ chung về commit trước. Nhờ vậy bạn giữ được cả nghìn commit — cả lịch sử — mà kho không phình lên nghìn lần kích thước dự án. Cấu trúc bền vững (persistent data structure) làm đúng điều đó cho một cấu trúc dữ liệu trong bộ nhớ: khi "sửa", nó tạo một phiên bản mới nhưng chia sẻ phần lớn cấu trúc cũ (structural sharing), giữ được cả bản cũ lẫn bản mới. Không copy cả thứ — chỉ tạo lại đúng phần đổi. Đây là nền của các collection immutable trong Clojure, Scala, Immutable.js. Tôi tự cài một persistent vector kiểu trie nhánh 32 và đo nó trong container gcc:13, và con số cho thấy structural sharing biến O(n) thành O(log n) — với cái giá đọc nhỏ hơn nhiều so với tôi tưởng.

Copy cả mảng so với copy đúng đường dẫn

Cách làm kinh điển là một persistent vector kiểu bit-partitioned trie (nhánh 32, như Clojure/Scala):

  • Dữ liệu thật nằm ở lá, mỗi lá chứa 32 phần tử liền nhau. Các tầng node trong dẫn đường: mỗi tầng dùng 5 bit của chỉ số (2⁵ = 32) để chọn một trong 32 con. Với N cỡ một triệu, cây chỉ 4 tầng (32⁴ ≈ 1,05 triệu) — vì log₃₂ rất nông.
  • Update một phần tử: đi từ gốc xuống lá theo chỉ số, copy các node trên đường đi (gốc → lá, khoảng 4 node), đổi phần tử ở lá mới. Mọi node không nằm trên đường đi được chia sẻ nguyên vẹn với phiên bản cũ — đúng như file không đổi trỏ chung về commit trước. Kết quả: một phiên bản mới hoàn chỉnh, nhưng chỉ tốn ~4 node mới — O(log n) thay vì copy cả N.

So với naive immutable (copy cả mảng mỗi lần đổi — như phần 38), persistent trie chỉ đụng một đường dẫn mảnh. Cái giá: dữ liệu nằm rải trong các node (con trỏ gián tiếp), nên đọc phải đi qua nhiều tầng — về lý thuyết chậm hơn mảng phẳng.

Đo: update nhanh 319 lần, bộ nhớ ít 2345 lần, đọc chỉ chậm 1,1 lần

Tôi dựng một persistent vector 1.048.576 phần tử (trie 4 tầng), đo update, bộ nhớ mỗi phiên bản, và đọc:

Persistent vector = trie nhánh 32, N=1.048.576, g++ -O2:

A. UPDATE một phần tử:
   naive immutable (copy cả mảng) : 65.070 ns/lần   (O(n))
   persistent trie (copy đường dẫn ~4 node) : 203,7 ns/lần   (O(log n))
   -> persistent nhanh hơn ~319 lần

B. BỘ NHỚ mỗi phiên bản mới:
   naive (copy cả mảng)   : 4.137 KB/phiên bản
   persistent (chia node) : 1,76 KB/phiên bản
   -> persistent ít hơn ~2345 lần

C. ĐỌC NGẪU NHIÊN một phần tử (20 triệu lần):
   mảng phẳng : 1,41 ns
   trie       : 1,57 ns   (đi 4 tầng node) -> chỉ chậm ~1,1 lần
   (duyệt tuần tự toàn bộ trie: 0,224 ns/phần tử ~ tie với mảng, vì lá 32 int liền)

Nhìn A — update: copy cả mảng 1 triệu int mỗi lần đổi mất 65.070 ns (một memcpy 4 MB), còn persistent chỉ copy đường dẫn ~4 node, mất 203,7 ns — nhanh hơn ~319 lần. Đây là điều làm immutable trở nên thực dụng: bạn giữ được lịch sử/phiên bản mà không trả giá O(n) mỗi lần đổi.

Nhìn B — bộ nhớ: đây là chỗ ấn tượng nhất. Giữ một phiên bản mới bằng cách copy cả mảng tốn 4.137 KB (cả mảng); còn persistent chỉ tốn 1,76 KB (~4 node mới) — ít hơn ~2345 lần. Vì các phiên bản chia sẻ mọi node không đổi. Bạn có thể giữ hàng chục nghìn phiên bản (undo/history, snapshot) mà tổng bộ nhớ vẫn nhỏ — điều bất khả thi nếu copy cả mảng mỗi lần, đúng như Git giữ nghìn commit không phình kho.

Nhìn C — chỗ tôi đo hớ theo chiều ngược: tôi tưởng đọc một persistent trie sẽ chậm hơn nhiều mảng phẳng vì phải đi qua 4 tầng con trỏ. Đo cho thấy chỉ chậm ~1,1 lần (1,57 vs 1,41 ns) cho đọc ngẫu nhiên, và duyệt tuần tự thì gần như tie (0,224 vs 0,227 ns/phần tử). Lý do: nhánh rộng (32) giữ cây rất nông (chỉ 4 tầng), các node trong chỉ vài nghìn và nằm gọn trong cache, còn lá là 32 int liền nhau nên đọc bulk vẫn cache-tốt. Cái "gián tiếp con trỏ" mà tôi lo hầu như biến mất nhờ branching rộng — khác hẳn một cây nhị phân (log₂ ~20 tầng) sẽ chậm hơn nhiều.

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với niềm tin: "muốn giữ nhiều phiên bản của một cấu trúc (undo, snapshot, lịch sử) thì phải copy cả nó mỗi lần đổi — O(n) thời gian và O(n) bộ nhớ mỗi phiên bản, quá đắt cho dữ liệu lớn". Con số bác ngay: persistent trie chia sẻ các node không đổi, nên update chỉ O(log n) (203,7 ns, nhanh hơn copy-cả-mảng 319 lần) và mỗi phiên bản mới chỉ tốn ~1,76 KB thay vì 4 MB (ít hơn 2345 lần). "Giữ lịch sử phải copy cả cấu trúc" là sai — structural sharing khiến nó rẻ đến mức bất ngờ, và đó là lý do các ngôn ngữ functional dùng immutable làm mặc định mà không sập hiệu năng.

Nhưng tôi cũng mang theo một niềm tin ngược cần sửa: "persistent trie thì đọc/duyệt chắc chậm hơn nhiều so với mảng phẳng vì phải nhảy qua các tầng node". Đo cho thấy điều đó sai về mức độ: đọc ngẫu nhiên chỉ chậm ~1,1 lần, duyệt tuần tự gần tie — vì nhánh 32 giữ cây nông (4 tầng) và node trong nằm trong cache. Persistent trie không trả một cái giá đọc lớn. Cái giá thật của nó nằm ở chỗ khác: mỗi update cấp ~4 node mới (áp lực cấp phát và đếm tham chiếu), và một phiên bản đơn lẻ tốn nhiều bộ nhớ hơn một mảng phẳng cùng cỡ một chút (do overhead node). Nếu bạn chỉ cần một phiên bản và đổi ít, một mảng phẳng vẫn đơn giản hơn và không có overhead đó — persistent không phải "tốt mọi mặt".

Về đến code hằng ngày

Việc đầu tiên: cần lịch sử, undo/redo, snapshot, hoặc chia sẻ nhiều phiên bản an toàn — dùng cấu trúc persistent. Trình soạn thảo (undo), quản lý trạng thái UI (Redux/Immutable.js giữ snapshot mỗi hành động), cơ sở dữ liệu MVCC, hệ thống versioning — tất cả đều cần giữ bản cũ khi tạo bản mới. Persistent structure cho điều đó với chi phí O(log n)/update và bộ nhớ chia sẻ, thay vì copy cả cấu trúc mỗi bước. Đừng tự tay copy cả mảng để "giữ lịch sử" — đó là O(n) không cần thiết.

Việc thứ hai: branching rộng là chìa khóa để persistent không đắt khi đọc. Một cây nhị phân persistent (log₂ n ~ 20 tầng) sẽ chậm và tốn node; một trie nhánh 32 (log₃₂ n ~ 4 tầng) giữ cây nông, node trong nằm cache, lá liền mạch — nên đọc gần bằng mảng phẳng. Đây là lý do các persistent vector thực tế đều dùng nhánh 32 (hoặc 64), không phải nhị phân. Nếu bạn tự thiết kế, chọn nhánh rộng.

Điều đáng nói là bạn đã dùng structural sharing hằng ngày mà có thể không để ý, ở tận tầng cao. Toàn bộ hệ sinh thái React/Redux dựa vào immutable + chia sẻ cấu trúc: mỗi lần cập nhật state tạo một object mới chia sẻ phần không đổi, và React so sánh tham chiếu (===, rẻ) thay vì so sâu để biết nhánh nào cần vẽ lại — persistent structure làm cái so-sánh-rẻ đó đúng đắn. Trong Java, String bất biến và các collection List.of()/Guava ImmutableList cùng triết lý an-toàn-khi-chia-sẻ; Clojure/Scala thì dùng thẳng persistent vector này làm collection mặc định. Và MVCC của PostgreSQL — mỗi transaction thấy một "phiên bản" nhất quán của dữ liệu trong khi người khác vẫn ghi — chính là structural sharing ở quy mô database: giữ nhiều phiên bản mà không copy cả bảng. Nguyên tắc chung: chia sẻ phần không đổi biến "immutable đắt" thành "immutable thực dụng", và cái giá còn lại nhỏ hơn trực giác nhiều.

Muốn tự hình dung thì nghĩ về một mảng một triệu phần tử và bạn cần giữ 1000 phiên bản (mỗi phiên bản khác phiên bản trước một phần tử). Cách naive: copy cả mảng mỗi lần → 1000 × 4 MB = 4 GB, và mỗi update là một memcpy 4 MB. Giờ nghĩ về một trie nhánh 32: cây chỉ 4 tầng, mỗi lá 32 phần tử. Để đổi một phần tử, bạn chỉ copy 4 node trên đường từ gốc tới lá (đổi phần tử ở lá mới), và chia sẻ mọi node còn lại với phiên bản cũ — mỗi phiên bản mới tốn ~2 KB thay vì 4 MB, và update là ~4 lần cấp node nhỏ thay vì memcpy khổng lồ. Cuối cùng, đọc một phần tử: mảng phẳng là một phép truy cập; trie là đi xuống 4 tầng — nhưng vì chỉ 4 tầng và các node trong nằm trong cache, nó chỉ chậm hơn chút xíu. Hình dung đó cho thấy điều mà "giữ lịch sử phải copy cả cấu trúc" giấu đi: bằng cách chia sẻ phần không đổi, một persistent structure cho bạn hàng nghìn phiên bản với chi phí của vài node mỗi lần — và branching rộng khiến cái giá đọc gần như biến mất.