Trong dữ liệu thật, cùng một giá trị thường 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. Có một kỹ thuật đơn giản để xóa hết chi phí đó: interning — 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 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ếusđã có, trả về id cũ. Nếu chưa có, thêmsvào một mảngstorevà 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.
Điều này cho hai lợi ích, đúng như tên gọi "gộp giá trị trùng":
- 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.
- 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 — con số bộ nhớ: 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.
Nhìn B — con số so sánh, chỗ phá vỡ niềm tin "interning chỉ tiết kiệm bộ nhớ": 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 trung thực: 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ột lần tôi đo hớ: "giữ bản sao chuỗi trùng chẳng tốn bao nhiêu" và "interning chỉ tiết kiệm bộ nhớ"
Tôi vào đo với một sự vô tư quen thuộc: "cứ giữ mỗi bản ghi một std::string riêng, chuỗi thì nhẹ, trùng lặp có sao đâu". Đo phá tan: 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 32 byte cộng phí cấp phát.
Còn một niềm tin ngược 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ỉ là chuyện RAM. Bỏ qua nó là bỏ lỡ một nửa lợi ích của interning.
Bài học đo lường: interning — lưu MỘT bản duy nhất mỗi giá trị trong một bảng băm rồi mọi nơi dùng chung một id nhỏ: (1) BỘ NHỚ — 8tr tham chiếu tới 1000 giá trị duy nhất tốn 732 MB nếu giữ bản riêng, chỉ 30,8 MB nếu intern (1 bản + chỉ số 4B) = ~24x ít hơn, càng nhiều trùng càng lời; (2) SO SÁNH BẰNG — so id O(1) (5,9 ns) thay vì so ký tự O(n) (37,9 ns) = ~6,4x nhanh. Giá: tra băm 15,8 ns/lần trả MỘT lần lúc nạp + bảng sống suốt đời. Nếu tôi tin "bản sao chẳng tốn gì" tôi phí hàng trăm MB cho dữ liệu trùng; nếu tôi tin "chỉ tiết kiệm bộ nhớ" tôi bỏ lỡ một tăng tốc so sánh 6,4 lần.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi cùng một giá trị lặp lại nhiều lần trong dữ liệu, 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 vài dòng code cho tiết kiệm hàng chục lần.
Hệ quả 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 là lý do trình biên dịch intern ký hiệu (so sánh tên biến bằng con trỏ), và nhiều ngôn ngữ (Java String.intern(), Python với chuỗi ngắn/định danh, Lua) intern chuỗi sẵn — không chỉ để tiết kiệm mà để so sánh danh tính nhanh.
Hệ quả thứ ba là tinh thần đo lường: "trùng lặp" là một chi phí có cấu trúc — gộp nó lại vừa nhỏ bộ nhớ vừa nhanh thao tác. Con số mang theo: interning gộp N bản trùng thành U bản duy nhất + N chỉ số nhỏ (đo: 732 MB → 30,8 MB, ~24x khi 8tr tham chiếu / 1000 giá trị), và biến so sánh bằng từ O(n) ký tự (37,9 ns) thành O(1) id (5,9 ns, ~6,4x). Giá: một lần tra băm lúc intern (15,8 ns) + một bảng sống suốt đời. Lời khi tỷ lệ trùng cao và có so sánh/làm khóa nhiều. Đo tỷ lệ trùng của dữ liệu trước — trùng nhiều thì interning gần như luôn thắng.
Thử ba mươi giây
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 (ví dụ 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 (một lần tra băm) và nhận ra bạn chỉ trả nó một lần lúc nạp. Ba mươi giây đó cho bạn 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.
