Hết tiền và hết chỗ trong ví là hai chuyện khác nhau. Tiêu quá tay thì bạn chật vật, xoay xở, tháng sau thắt lưng buộc bụng — vẫn sống. Nhưng nếu cái ví chỉ nhét vừa mười tờ mà bạn cố nhồi tờ thứ mười một, nó rách. Thời gian chạy của thuật toán giống chuyện thứ nhất: chậm thì khó chịu nhưng vẫn ra kết quả. Bộ nhớ giống chuyện thứ hai: vượt trần là rách — hệ điều hành không cho bạn chạy chậm lại, nó giết thẳng tiến trình. Suốt sê-ri này tôi đo thời gian. Bài này đo cái trục thứ hai mà người ta hay quên: không gian — và tôi muốn cho bạn thấy tận mắt lúc nó biến từ "hơi tốn RAM" thành "chết".

Tôi đọc RAM thật bằng VmHWM (đỉnh bộ nhớ tiến trình, lấy từ /proc) của vài thuật toán quen, trong container gcc:13 trên host ARM. Không gian hóa ra không phải tài nguyên vô hạn để tiện tay cấp phát — nó là bức tường cứng, và nó đổi qua đổi lại với thời gian theo những cách chỉ đo mới thấy.

Không gian: cùng ký hiệu O, khác hẳn hậu quả

Độ phức tạp không gian đo lượng bộ nhớ phụ — ngoài phần lưu chính đầu vào — mà thuật toán cần khi n lớn dần. Nó mượn nguyên bộ ký hiệu O của thời gian: O(1) là bộ nhớ phụ không đổi dù n bao lớn (vài biến); O(n) là tỉ lệ với n (một mảng cỡ n); O(n²) là bình phương (một ma trận n×n). Ngăn xếp đệ quy cũng tính là không gian — đệ quy sâu n ăn O(n) ngăn xếp.

Nhưng chữ O ở đây có một cái đuôi mà chữ O của thời gian không có. Chậm là chuyện độ khó chịu, có thể chờ. Hết bộ nhớ là chuyện sống chết. Khi chương trình đòi nhiều RAM hơn máy có, hệ điều hành không giảm tốc — nó bấm nút OOM và giết tiến trình. Bức tường ấy, với một thuật toán O(n²) không gian, ở gần hơn nhiều so với lúc bạn lo hết thời gian.

Ma trận đụng tường, danh sách thì không

Ví dụ kinh điển nhất: lưu một đồ thị V đỉnh. Ma trận kề dùng một bảng V×V — O(V²) bộ nhớ. Danh sách kề chỉ lưu các cạnh có thật — O(V+E). Tôi cấp phát rồi chạm hết bộ nhớ mỗi cách (chạm để nó thực sự nằm trong RAM chứ không chỉ được hứa hẹn), rồi đọc đỉnh:

Bộ nhớ (VmHWM) theo số đỉnh V:
  V       | ma trận kề O(V²) | danh sách kề O(V+E), bậc 10
   5.000  |      24,9 MB     |     1,2 MB
  10.000  |      96,4 MB     |     1,4 MB
  20.000  |     382,5 MB     |     1,8 MB
  40.000  |   1.526,9 MB     |     2,6 MB

Cột ma trận kể đúng câu chuyện O(V²): V gấp đôi thì RAM gấp bốn (24,9 → 96,4 → 382,5 → 1527). Tới V = 40.000, ma trận đã nuốt 1,5 GB, danh sách vẫn 2,6 MB — chênh gần 600 lần. Và đây là chỗ bức tường lộ mặt: trên máy 8 GB này, ma trận sẽ chạm trần quanh V = 90.000 rồi bị OOM giết, còn danh sách vẫn lửng lơ ở vài megabyte và chạy tới hàng triệu đỉnh không mảy may. Không phải "chậm hơn khi V lớn" — mà là "thôi, không chạy nữa". Với đồ thị thưa (E ≪ V², tức gần như mọi đồ thị thực tế), chọn ma trận là tự tay xây một bức tường ngay trước mũi mình.

Rất nhiều RAM ta giữ mà chẳng dùng tới

Tôi bước vào loạt đo này với một định kiến gọn lỏn: "cứ tối ưu thời gian đi, bộ nhớ để đó tính sau". Hai phép đo bắt tôi nghĩ lại. Cái thứ nhất là bức tường OOM ở trên. Cái thứ hai tinh tế hơn nhiều, và tôi ngờ nó phổ biến hơn: rất thường xuyên, ta cấp O(n) trong khi chỉ cần O(1).

Lấy quy hoạch động: Fibonacci dp[i] = dp[i-1] + dp[i-2]. Sách giáo khoa dựng cả bảng dp[0..n] — O(n) không gian. Nhưng để ra được giá trị thứ n, bạn chỉ cần hai số gần nhất, tức một cặp biến "cuộn" O(1). Tôi đo cả hai ở n = 50 triệu:

DP Fibonacci (mod), n = 50 triệu:
  bảng đầy đủ O(n) : 382,5 MB | 133 ms
  cuộn 2 biến O(1) :   1,0 MB | 126 ms

Cùng thời gian (~130 ms), nhưng bản cuộn xài 1 MB thay cho 382 MB — tiết kiệm 382 lần bộ nhớ, gần như cho không (còn nhanh hơn tí vì khỏi cấp mảng lớn). Cái bảng O(n) mà cách ngây thơ ôm suốt là không gian thừa: nó cất 50 triệu giá trị trung gian không bao giờ được đọc lại lần nữa. Trước khi bạn cấp một mảng O(n), câu hỏi đáng giá là: mình có thật cần giữ cả không, hay chỉ cần vài phần tử cuối? Vô số bài DP một chiều tụt từ O(n) xuống O(1) không gian đúng theo kiểu ấy.

Không gian đổi được với thời gian — và trượt cả hai chiều

Vậy nếu O(1) không gian lúc nào cũng ngon, cứ chọn thuật toán tại chỗ là xong? Không đơn giản thế. Tôi so hai cách sắp 30 triệu số nguyên: heapsort (sắp tại chỗ, O(1) bộ nhớ phụ) và merge sort (cần bộ đệm O(n)):

Sắp 30 triệu int (đầu vào ~114 MB):
  heapsort (tại chỗ)      : 7.666 ms | VmHWM 115,5 MB
  merge sort (+đệm n)     : 2.061 ms | VmHWM 229,4 MB

Phần không gian đúng như đoán: merge sort tốn gấp đôi RAM (229 so với 115 MB) vì phải nuôi một bộ đệm bằng cả mảng. Nhưng phần thời gian thì làm tôi ngớ ra: merge sort nhanh hơn 3,7 lần dù cùng O(n log n). Thủ phạm là cache: heapsort tuy tại chỗ nhưng nhảy khắp đống (mỗi lần "sàng" phóng tới con hoặc cha ở tận đâu) — cực kỳ phản cache; merge sort quét tuần tự, chiều lòng cache. Thế là ta có một đánh đổi thời gian–không gian thật, chạy được cả hai chiều: heapsort mua RAM rẻ bằng thời gian đắt; merge sort mua tốc độ bằng RAM gấp đôi. Chẳng cái nào "đúng" tuyệt đối — kẹt RAM thì heapsort, cần tốc độ mà dư RAM thì merge. Con dao trượt giữa hai đầu, còn bạn chọn điểm theo ràng buộc của mình.

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

Điều đầu tiên, và thực dụng nhất: đo cả bộ nhớ, đừng chỉ đo thời gian — nhất là độ dốc theo n. Một thuật toán O(n²) không gian có thể chạy ngọt trên dữ liệu test bé rồi chết trên dữ liệu thật, mà triệu chứng không phải "chậm dần" — nó là "bị kill đột ngột", khó chẩn đoán hơn hẳn. Khi chọn cấu trúc, hỏi độ phức tạp không gian của nó ngang với hỏi thời gian: ma trận kề hay danh sách kề, bảng DP đầy hay cuộn, đọc cả file vào RAM hay xử lý theo luồng.

Điều thứ hai: không gian là một biến để tối ưu, và thường tối ưu được rất nhiều mà chẳng mất gì. Bản cuộn O(1) của DP là bằng chứng: 382 lần RAM tiết kiệm gần như miễn phí. Xử lý theo luồng thay vì nạp cả tập, dùng chỉ số gọn thay cho bản sao đầy đủ, bitset thay mảng bool — nhiều kỹ thuật cắt không gian mà giữ nguyên hoặc còn cải thiện thời gian nhờ cache. Đừng để câu "RAM rẻ mà" thành cái cớ cấp phát bừa; ở quy mô lớn, bộ nhớ mới là thứ chạm trần trước.

Và chuyện này vượt xa C. Trong Java, mỗi Integer trong một ArrayList<Integer> là một đối tượng có header, ngốn gấp mấy lần một int[] thô — cùng "n phần tử" mà dấu chân bộ nhớ lệch hẳn; muốn nhìn đỉnh heap thật thì bật -Xlog:gc hoặc soi jcmd <pid> GC.heap_info chứ đừng đoán. Go cho bạn runtime.ReadMemStats và pprof bộ nhớ để thấy cấp phát dồn ở đâu, và một make([]T, 0, n) đặt sẵn dung lượng sẽ tránh cả loạt lần copy khi slice lớn dần. Còn cơ sở dữ liệu thì sống chết với cùng cán cân này: một hash join đổi RAM lấy tốc độ, merge join cần đầu vào đã sắp, và khi bộ nhớ làm việc không đủ, Postgres tràn ra đĩa — EXPLAIN ANALYZE in thẳng dòng "Sort Method: external merge Disk: ..." cho bạn thấy đúng khoảnh khắc không gian đụng trần và thời gian trả giá. Mẫu số chung ở mọi tầng: thời gian và không gian là hai trục, tối ưu một trục là mới thấy nửa bức tranh.

Muốn tự thấy thì chạy một chương trình bất kỳ của bạn dưới /usr/bin/time -v ./chương-trình (Linux) và nhìn dòng Maximum resident set size — đó là đỉnh bộ nhớ thật, cùng thứ VmHWM bài này đọc. Cho nó đầu vào nhỏ, rồi đầu vào gấp đôi, so hai con số: RAM gấp đôi thì bạn đang ở O(n) không gian, gấp bốn thì O(n²) — bạn vừa đo được độ dốc không gian của chính mình. Rồi ngó bất kỳ vòng lặp nào tích vào một danh sách và hỏi: mình có thật cần giữ cả danh sách, hay chỉ cần tổng/max/phần tử cuối? Mỗi lần câu trả lời là "chỉ cần vài cái", bạn vừa tìm ra một chỗ cắt O(n) xuống O(1) — thứ mà, như bài này đo, thường không tốn lấy một mili giây.