Tưởng tượng bạn viết một lá thư dài, và mỗi lần muốn thêm một chữ, bạn lại chép toàn bộ lá thư đang có sang một tờ giấy mới rồi mới viết thêm chữ đó vào cuối. Lá thư càng dài, mỗi lần thêm một chữ càng lâu — vì bạn phải chép lại tất cả những gì đã viết. So với việc chỉ đặt bút xuống cuối trang và viết tiếp chữ mới, cách chép-lại-toàn-bộ nghe điên rồ. Nhưng đó chính xác là điều xảy ra khi bạn nối chuỗi bằng s = s + phần với một chuỗi bất biến, và cú pháp gọn gàng đã giấu nó đi.

Bạn xây một chuỗi lớn bằng cách nối dần trong vòng lặp, lặp N lần. Nhìn thì vô hại — mỗi lần chỉ thêm một mẩu nhỏ. Nhưng có một chi tiết mà cú pháp giấu đi: chuỗi của bạn biến đổi tại chỗ hay tạo mới mỗi lần? Câu trả lời quyết định vòng lặp đó là O(N) hay O(N²) — và với chuỗi bất biến như trong Java hay Python, câu trả lời là O(N²), một cái bẫy có thể biến vài giây thành hàng chục phút. Tôi đo cả hai cách trong container gcc:13, và con số cho thấy "chỉ là nối chuỗi" có thể là một quả bom bậc hai.

Copy cả chuỗi mỗi lần, hay chỉ thêm vào cuối

Điểm mấu chốt là bất biến (immutable) hay không:

  • Chuỗi bất biến — String trong Java, str trong Python. Chúng không thể sửa. Khi bạn viết s = s + c, ngôn ngữ không thêm c vào s — nó tạo một chuỗi hoàn toàn mới, copy toàn bộ s (i byte) rồi thêm c. Đúng cái cảnh chép lại cả lá thư. Lần lặp thứ i copy i byte. Tổng qua N lần: 1 + 2 + ... + N = N²/2 byte phải copy — O(N²). Đây đúng là bài học grow-by-1 của phần 2 và chèn đầu mảng của phần 3: mỗi thao tác copy lại tất cả những gì đã có.

  • Buffer động — std::string +=, StringBuilder (Java), hoặc gom vào list rồi ''.join (Python). Chúng ghi vào cuối vùng bộ nhớ đã cấp; khi đầy thì nhân đôi capacity — nên trung bình mỗi ký tự chỉ O(1) amortize, tổng O(N). Không copy lại chuỗi cũ mỗi lần; chỉ đặt bút viết tiếp.

Cùng kết quả — một chuỗi N ký tự — nhưng hai con đường khác nhau cả một bậc độ phức tạp.

Đo: 2151 ns/ký tự so với 2,18 ns/ký tự

Tôi xây chuỗi bằng ba cách. Với cách bất biến (mô phỏng bằng cách tạo std::string mới mỗi lần), tôi phải giảm N vì O(N²):

g++ -O2:

A. IMMUTABLE (s = s + c, tạo chuỗi MỚI mỗi lần):
   N = 200.000 ký tự : 0,43 s | tổng byte copy = 20 tỷ (~N²/2) | 2.151 ns/ký tự  (O(N²))

B. std::string += (append tại chỗ, amortize):
   N = 20.000.000 ký tự : 0,044 s | 2,18 ns/ký tự  (O(N))

C. reserve(N) trước rồi += :
   N = 20.000.000 ký tự : 0,042 s | 2,10 ns/ký tự  (nhanh nhất, 0 mọc lại)

Nhìn khác biệt: cách bất biến chỉ xây được 200 nghìn ký tự mà đã mất 0,43 giây, và tổng số byte phải copy lên tới 20 tỷ — cho một chuỗi chỉ 200 nghìn ký tự! Mỗi ký tự tốn 2.151 ns. Trong khi cách += xây 20 triệu ký tự (nhiều gấp 100 lần) chỉ trong 0,044 giây, mỗi ký tự 2,18 ns. Tức là per-ký-tự, cách bất biến chậm hơn ~1.000 lần. Nếu bạn xây 20 triệu ký tự bằng cách bất biến, nó sẽ mất (20tr/200k)² × 0,43s = 100² × 0,43 ≈ 4.300 giây ≈ 72 phút — so với 0,044 giây của +=. Đó là sự khác biệt giữa "tức thời" và "đi ăn trưa rồi quay lại vẫn chưa xong". Cách reserve còn nhanh hơn chút (2,10 ns) vì không mọc lại lần nào.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, mỗi số lấy MIN sau warmup. Con số tuyệt đối đổi theo máy; cái cần nhìn là dáng O(N²) (N gấp đôi thì thời gian gấp bốn) so với O(N), và con số 72 phút là suy ra từ tỉ lệ N², không phải chạy thật.)

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

Tôi vào đo với niềm tin: "nối chuỗi trong vòng lặp là chuyện thường, chuỗi nào cũng vậy". Con số bác thẳng: nối kiểu bất biến (tạo chuỗi mới mỗi lần) copy toàn bộ chuỗi mỗi bước, tổng N²/2 byte, O(N²) — 200 nghìn ký tự đã copy 20 tỷ byte, và nếu 20 triệu thì mất 72 phút.

Nhưng niềm tin phổ biến hơn, tôi từng có khi mới viết Java, là: "String s = s + x cũng nhanh như StringBuilder, trình biên dịch tối ưu giùm mà". Sai — trong một vòng lặp, String + tạo một chuỗi mới mỗi lần lặp (trình biên dịch chỉ tối ưu được nối trên một biểu thức đơn, không xuyên vòng lặp), nên nó là O(N²). Đây là một trong những lỗi hiệu năng phổ biến nhất mà cả người mới lẫn người cũ đều mắc: xây một chuỗi/báo cáo/JSON lớn bằng += trên String, chạy nhanh với dữ liệu test nhỏ, rồi treo cứng với dữ liệu thật.

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

Điều đầu tiên: xây chuỗi trong vòng lặp thì dùng buffer, không dùng + trên chuỗi bất biến. Java: StringBuilder. Python: gom vào list rồi ''.join(list) (hoặc io.StringIO). C#: StringBuilder. C++: std::string += (đã là buffer động). Quy tắc để nhớ: nếu bạn thấy s = s + ... hay s += ... với s là chuỗi bất biến bên trong một vòng lặp, đó là O(N²) — đổi sang buffer ngay. Đây là một trong những tối ưu "một dòng đổi cả bậc" dễ nhất.

Điều thứ hai: biết trước độ dài thì reserve. Giống reserve của vector phần 2, nếu bạn ước lượng được kích thước chuỗi cuối, s.reserve(n) (C++) hay new StringBuilder(capacity) (Java) loại bỏ cả các lần mọc lại — nhanh nhất và tránh phân mảnh. Với vòng lặp xây chuỗi rất lớn, đây là tối ưu rẻ thêm vào.

Chỗ này đáng nói là các ngôn ngữ đã học từ chính cái bẫy này và cố cứu bạn theo những cách khác nhau. Java cũ đến mức javac tự biến a + b + c trên một biểu thức thành StringBuilder ngầm — nhưng đúng như đo ở trên, nó bó tay khi phép nối nằm rải qua các vòng lặp, nên StringBuilder thủ công vẫn cần. Go giải quyết bằng strings.Builder (và bytes.Buffer), còn Rust thì String vốn mutable nên push_str đã là O(N) amortize sẵn — họ chọn không làm chuỗi bất biến một phần vì cái bẫy này. Thú vị hơn, tính bất biến của chuỗi có lý do chính đáng của nó (an toàn luồng, dùng làm khóa hash, chia sẻ không lo bị sửa) — nên bài học không phải "bất biến là xấu", mà là "bất biến khiến build tăng dần đắt, nên tách riêng bước build bằng một buffer mutable rồi mới đóng băng thành chuỗi cuối". Đó chính xác là vai trò của StringBuilder.

Muốn tự thấy thì viết một vòng lặp xây chuỗi vài chục nghìn ký tự bằng s = s + 'x' (trong Java, Python, hay C++ với std::string t = s + 'x'; s = t; để buộc tạo mới), và bấm giờ. Rồi tăng số ký tự lên gấp đôi — thời gian gấp bốn, dấu hiệu rõ của O(N²). Giờ đổi sang StringBuilder (Java), list + join (Python), hay s += 'x' (C++ std::string) và xây gấp một trăm lần số ký tự — nó vẫn nhanh hơn. Bạn sẽ thấy khoảng cách không phải vài phần trăm mà hàng trăm tới hàng nghìn lần. Vài phút đó cho bạn thấy điều mà "chỉ là nối chuỗi" giấu đi: khi chuỗi bất biến, mỗi lần + copy lại tất cả, biến một vòng lặp trông tuyến tính thành bậc hai — và một buffer append-tại-chỗ là toàn bộ khác biệt giữa xong-trong-tích-tắc và chờ-cả-tiếng.