8 triệu bản sao của 1000 chuỗi: interning cắt 732 MB xuống 30

Hãy tưởng tượng một thư viện mà mỗi lần ai đó nhắc tới một cuốn sách, họ lại photo nguyên cuốn để cầm về. Mười nghìn người đọc cùng một cuốn là mười nghìn bản photo nằm rải khắp thành phố. Thay vào đó, thư viện chỉ giữ một bản gốc trên kệ và phát cho mỗi người một phiếu mượn nhỏ ghi số hiệu — ai cũng biết đang nói về cuốn nào, mà chẳng ai phải ôm nguyên cuốn. Đó gần như đúng ý tưởng của interning trong lập trình.

Trong dữ liệu thật, cùng một giá trị xuất hiện đi xuất hiện lại: cùng một tên người dùng trong hàng triệu bản ghi log, cùng một tên trường trong hàng triệu đối tượng JSON, cùng một đường dẫn, cùng một nhãn, cùng một mã. Cách ngây thơ là mỗi nơi giữ một bản sao riêng của chuỗi đó. Nghe vô hại — "một chuỗi thì tốn bao nhiêu?". Nhưng khi cùng một giá trị lặp lại hàng triệu lần, những bản sao đó cộng dồn thành hàng trăm megabyte. Interning xóa hết chi phí đó: lưu một bản duy nhất mỗi giá trị trong một bảng, rồi mọi nơi dùng chung một chỉ số tới nó. Tôi đo interning so với giữ bản sao trong container gcc:13, và con số cho thấy nó không chỉ tiết kiệm bộ nhớ mà còn tăng tốc cả so sánh.

Một bản duy nhất, mọi nơi dùng chung chỉ số

Ý tưởng của interning rất gọn: giữ một intern pool — một bảng băm unordered_map<chuỗi, id> ánh xạ mỗi giá trị duy nhất tới một số nguyên nhỏ (id). Khi bạn muốn "lưu" một chuỗi:

• intern(s): tra bảng. Nếu s đã có, trả về id cũ. Nếu chưa có, thêm s vào một mảng store và cấp một id mới.
• Sau đó, mọi tham chiếu tới giá trị đó chỉ giữ một id 4 byte (hoặc một con trỏ tới bản duy nhất), thay vì một bản sao đầy đủ của chuỗi.

Đúng như cái tên "gộp giá trị trùng", điều này cho hai lợi ích:

1. Bộ nhớ: nếu bạn có N tham chiếu nhưng chỉ U giá trị duy nhất (U ≪ N), bạn chỉ trả U bản chuỗi + N chỉ số nhỏ, thay vì N buffer chuỗi đầy đủ. Càng nhiều trùng lặp, càng lời.
2. So sánh bằng: hai giá trị đã interned bằng nhau khi và chỉ khi chúng có cùng id. So sánh trở thành so một số nguyên — O(1) — thay vì so từng ký tự — O(n). Với chuỗi dài, khác biệt lớn.

Cái giá phải trả: mỗi lần intern là một lần tra bảng băm cộng có thể một lần chèn — nhưng bạn trả nó một lần lúc nạp dữ liệu, rồi hưởng lợi mãi về sau. Và bạn cần giữ intern pool sống suốt đời để các bản duy nhất còn đó.

Đo: bộ nhớ ít hơn 24 lần, so sánh nhanh 6,4 lần

Tôi dựng một tập 8 triệu tham chiếu, nhưng chỉ tới 1000 giá trị duy nhất (mỗi giá trị là một chuỗi 40 ký tự kiểu đường dẫn) — mô phỏng dữ liệu thật nhiều trùng lặp. So hai cách lưu, đọc RSS thật từ /proc/self/statm, và bấm giờ so sánh:

8tr tham chiếu, 1000 giá trị duy nhất, chuỗi 40 ký tự, g++ -O2:

A. BỘ NHỚ:
   COPY (mỗi nơi một std::string riêng) : RSS +732,5 MB
   INTERN (1000 bản duy nhất + 8tr chỉ số 4B) : RSS +30,8 MB
   -> intern ít hơn ~24 lần

B. SO SÁNH BẰNG (50 triệu lần, chuỗi 40 ký tự, prefix chung 36):
   so chuỗi (O(n) ký tự) : 37,87 ns/lần
   so chỉ số (O(1))      :  5,91 ns/lần
   -> intern nhanh hơn ~6,4 lần

C. Chi phí intern (tra băm + chèn) : 15,8 ns/lần (trả MỘT lần lúc nạp)

Nhìn A trước — con số bộ nhớ làm tôi hơi giật mình dù đã đoán trước hướng: giữ 8 triệu std::string riêng (mỗi cái một buffer trên heap, vì chuỗi 40 ký tự vượt ngưỡng SSO) tốn 732,5 MB. Interning cùng dữ liệu đó chỉ tốn 30,8 MB — 1000 bản chuỗi duy nhất (khoảng 100 KB) cộng 8 triệu chỉ số 4 byte (32 MB). Ít hơn ~24 lần. Và tỷ lệ này tăng theo mức trùng lặp: nếu 8 triệu tham chiếu tới chỉ 100 giá trị duy nhất, khác biệt còn lớn hơn nữa. Toàn bộ 700 MB kia là những bản sao y hệt nhau của cùng 1000 chuỗi — đúng cái đống photo thừa ở đầu bài.

Nhìn B — con số so sánh, và đây mới là chỗ interning làm nhiều hơn tôi tưởng: so hai chuỗi 40 ký tự (chia sẻ tiền tố dài 36 ký tự, kiểu đường dẫn) mất 37,87 ns vì phải quét qua từng ký tự tới chỗ khác nhau; so hai id chỉ mất 5,91 ns vì chỉ so một số nguyên. Interning nhanh hơn ~6,4 lần. Cần nói thẳng cho công bằng: một phần của khác biệt này còn đến từ cache — mảng chỉ số 4 byte đặc và nhỏ (32 MB), còn các đối tượng chuỗi thì lớn và rải rác (nên chạm chúng tốn thêm cache miss). Cả hai yếu tố — so số nguyên thay vì ký tự, và dữ liệu đặc hơn — đều là lý do thật khiến interning tăng tốc so sánh.

C cho thấy cái giá: mỗi lần intern một chuỗi tốn 15,8 ns (tra bảng băm, có thể chèn). Nhưng đây là chi phí một lần lúc nạp — sau khi mọi thứ đã interned, bạn chỉ còn làm việc với id 4 byte, và mọi so sánh về sau đều nhanh. Trả trước một lần, hưởng mãi.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, RSS đọc từ /proc/self/statm, thời gian so sánh lấy MIN sau warmup chia số lần. Con số tuyệt đối đổi theo máy và độ dài chuỗi; cái cần nhìn là tỉ lệ 24x bộ nhớ và 6,4x so sánh khi tỉ lệ trùng cao.)

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

Tôi vào đo với một sự vô tư rất quen: "cứ giữ mỗi bản ghi một std::string riêng, chuỗi thì nhẹ, trùng lặp có sao đâu". Con số bác thẳng: 8 triệu tham chiếu tới chỉ 1000 giá trị duy nhất mà giữ bản riêng tốn 732 MB — trong khi bản chất chỉ có 1000 chuỗi khác nhau. Interning (một bản duy nhất + chỉ số) chỉ tốn 30,8 MB, ít hơn 24 lần. "Bản sao chuỗi chẳng tốn bao nhiêu" đúng cho một chuỗi, nhưng sai thảm hại khi cùng giá trị lặp lại hàng triệu lần — mỗi lần một buffer heap 40+ byte cộng header cộng phí cấp phát.

Nhưng có một niềm tin ngược lại cũng sai: "interning chỉ là một mẹo tiết kiệm bộ nhớ, không giúp gì về tốc độ". Đo cho thấy nó cũng biến so sánh bằng thành phép so một số nguyên O(1) (5,91 ns) thay vì so từng ký tự O(n) (37,87 ns) — nhanh 6,4 lần, và càng nhanh hơn với chuỗi dài hoặc chia sẻ tiền tố dài. Với những chỗ so sánh nóng (tra khóa, khớp nhãn, gom nhóm), đây là một tăng tốc thật, không chỉ chuyện RAM. Bỏ qua nó là bỏ lỡ đúng một nửa lợi ích của interning.

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

Điều đầu tiên: khi cùng một giá trị lặp lại nhiều lần trong dữ liệu, hãy intern nó. Log, sự kiện, đối tượng JSON/CSV, hàng trong bảng — chúng đầy những tên trường, nhãn, mã, đường dẫn lặp lại. Thay vì mỗi bản ghi giữ một bản sao chuỗi, giữ một intern pool và mỗi bản ghi giữ một id. Với dữ liệu lớn nhiều trùng, đây là một trong những cách cắt bộ nhớ dễ nhất — thường chỉ vài dòng code cho tiết kiệm hàng chục lần.

Điều thứ hai: interning biến so sánh và làm khóa thành O(1). Sau khi intern, hai giá trị bằng nhau khi và chỉ khi cùng id, nên bạn có thể dùng id làm khóa trong bảng băm/map (băm một số nguyên rẻ hơn nhiều băm chuỗi), so sánh bằng một phép so số nguyên, và gom nhóm cực nhanh. Đây chính là lý do trình biên dịch intern ký hiệu (so sánh tên biến bằng con trỏ) — không chỉ để tiết kiệm mà để so sánh danh tính nhanh. Trước khi quyết định, tôi hay đo tỷ lệ trùng của dữ liệu: trùng nhiều thì interning gần như luôn thắng; trùng ít thì cái intern pool lại thành gánh nặng vô ích.

Chỗ này người viết Java, Go hay dân làm database sẽ thấy cực quen, vì họ đã sống với interning mà đôi khi không gọi tên. Java có String.intern() gộp chuỗi về một bản trong pool, và mọi literal chuỗi được intern sẵn — đó là lý do "foo" == "foo" trả true dù == so tham chiếu. Python cũng tự intern các định danh và chuỗi ngắn, nên so sánh tên biến bên trong máy ảo nhanh như so con trỏ. Còn trong database và các engine phân tích thì kỹ thuật này có tên riêng: dictionary encoding — cột lưu một từ điển các giá trị duy nhất cộng một mảng mã nhỏ trỏ vào đó (Parquet, Arrow, ClickHouse đều làm), vừa nén mạnh vừa cho phép lọc và gom nhóm bằng cách so mã nguyên thay vì so chuỗi. Cùng một ý tưởng thư viện-giữ-bản-gốc-phát-phiếu-mượn, chỉ khác tên gọi ở mỗi tầng.

Muốn tự thấy thì không lâu. Tạo một tập vài triệu tham chiếu tới chỉ vài trăm chuỗi duy nhất (chọn ngẫu nhiên từ một danh sách nhỏ). Lưu hai cách: một vector<string> giữ bản sao đầy đủ, và một intern pool (unordered_map<string,int> + vector<int> chỉ số). Đọc RSS từ /proc/self/statm cho mỗi cách — bạn sẽ thấy bản interned nhỏ hơn nhiều lần, vì nó không nhân bản các chuỗi trùng. Rồi bấm giờ so sánh bằng: so hai chuỗi (quét ký tự) so với so hai id (một phép so số nguyên), id nhanh hơn vài lần và càng chênh nếu chuỗi dài. Cuối cùng đo chi phí intern một chuỗi và nhận ra bạn chỉ trả nó một lần lúc nạp. Vài phút đó cho thấy điều mà "giữ bản sao chuỗi chẳng tốn bao nhiêu" giấu đi: khi cùng một giá trị lặp lại hàng triệu lần, gộp chúng thành một bản duy nhất vừa cắt hàng trăm megabyte vừa biến mọi so sánh thành một phép so số nguyên.