# Phân loại băm nhanh hơn bảng băm

Trong xử lý dữ liệu lớn, việc đếm các giá trị duy nhất trong một mảng lớn các số uint64 là một thách thức phổ biến. Có hai phương pháp tiếp cận tiêu chuẩn: chèn vào bảng băm và trả về số lượng mục, hoặc sắp xếp mảng rồi đếm các vị trí khác với phần tử tiền nhiệm. Mặc dù bảng băm chiến thắng trong các cuộc phỏng vấn thuật toán (O(n) so với O(n log n)), nhưng trong thực tế, phân loại đã được tinh chỉnh thường nhanh hơn đáng kể.

## Kết quả đánh giá hiệu suất

Trên M2 Pro, khi so sánh bảng băm và phương thức phân loại đã được tối ưu hóa tốt nhất của chúng tôi, chúng ta thấy rằng phân loại đã được tinh chỉnh vượt trội hơn bảng băm khoảng 1,5 lần đối với các kích thước không quá nhỏ, và nhanh gấp 4 lần so với các bảng băm “Swiss Table” xuất sắc được cung cấp cùng với thư viện chuẩn Rust.

| Kích thước dữ liệu | Bảng băm cơ sở | Phân loại cơ sở | Bảng băm đã tinh chỉnh | Phân loại đã tinh chỉnh |
|——————-|—————-|—————-|———————-|———————-|
| 8 KiB | 3.8 µs | 5.1 µs | 1.6 µs | 6.5 µs |
| 256 KiB | 219 µs | 264 µs | 193 µs | 92 µs |
| 8 MiB | 8.1 ms | 12.0 ms | 7.1 ms | 3.9 ms |
| 256 MiB | 875 ms | 464 ms | 269 ms | 185 ms |
| 2 GiB | 7.6 s | 4.3 s | 2.6 s | 1.9 s |

## Tại sao phân loại lại chiến thắng?

Lý do chính nằm ở băng thông bộ nhớ: mặc dù phân loại thực hiện nhiều lần duyệt qua bộ nhớ, mỗi lần sử dụng băng thông hiệu quả hơn nhiều so với bảng băm duyệt một lần.

Khi bộ dữ liệu lớn hơn bộ nhớ đệm CPU (thường khoảng ~1 MiB trên một lõi, phụ thuộc vào CPU), cả băm và sắp xếp đều bị giới hạn bởi băng thông truy xuất dòng bộ nhớ đệm vào bộ nhớ chính. Dòng bộ nhớ đệm thường có kích thước 64 byte, và CPU sẽ truy xuất toàn bộ dòng nếu bạn chỉ chạm vào một byte duy nhất.

Bảng băm lãng phí băng thông: mỗi lần truy cập khóa 8 byte kéo theo một dòng bộ nhớ đệm 64 byte đầy đủ. Do đó, bảng băm phải gây ra ít nhất 128 byte dữ liệu trên mỗi uint64 được xử lý: 64 byte đọc và 64 byte ghi.

Đối với phân loại, chúng tôi sử dụng sắp xếp cơ số (radix sort) chia thành 1024 xô mỗi lần duyệt, chỉ cần 3 lần duyệt đối với 2^30 phần tử. Mỗi lần duyệt đọc và ghi toàn bộ mảng một lần, và các truy cập có đủ tính cục bộ không gian để toàn bộ dòng bộ nhớ đệm được sử dụng hiệu quả, khác với bảng băm. Vì vậy, xử lý một uint64 chỉ tốn 48 byte lưu lượng bộ nhớ: 8 byte × 3 lần duyệt đọc, 8 byte × 3 lần duyệt ghi.

Phân tích này gợi ý một tốc độ tăng lên 2,7 lần so với bảng băm: 128 byte so với 48 byte lưu lượng bộ nhớ trên mỗi uint64. Tốc độ tăng lên thực tế chỉ khoảng 1,5 lần, chủ yếu (theo tôi có thể thấy) vì việc làm cho hệ thống bộ nhớ đệm CPU thực hiện chính xác những gì bạn muốn cho sắp xếp cơ số khó hơn đối với bảng băm.

## Làm cho sắp xếp cơ số trở nên mạnh mẽ

Mặc dù sắp xếp cơ số thường là thuật toán sắp xếp nhanh nhất trên dữ liệu ngẫu nhiên, hiệu suất của nó suy giảm trên dữ liệu không phân bố đều không gian khóa. Một lần duyệt sắp xếp một byte của khóa vào 256 xô; nếu chỉ một tập hợp nhỏ các xô trong 256 được sử dụng bởi khóa trong thực tế – ví dụ, nếu byte cao nhất của uint64 luôn là zero – thì một phần lớn công việc trên lần duyệt này của sắp xếp cơ số có thể bị lãng phí.

Để tránh những sự chậm trễ này, chúng tôi vay một ý tưởng từ bảng băm: phân loại theo hash(key) thay vì key. Đối với việc đếm các giá trị duy nhất, chúng tôi không quan tâm đến thứ tự cuối cùng, chỉ cần nhóm lại. Tất nhiên, điều này sẽ thay đổi thứ tự sắp xếp, nhưng vì chúng tôi chỉ quan tâm đến việc đếm các giá trị duy nhất chứ không phải thứ tự sắp xếp, nên điều này không quan trọng.

Ngay hơn nữa, hãy sử dụng một hàm băm khả đảo (song ánh) để biến đổi khóa tại chỗ. Điều này tránh việc lưu cả khóa và băm, hoặc tính toán lại băm mỗi lần duyệt. Nhiều hàm băm được sử dụng rộng rãi là khả đảo trên uint64; tôi đã sử dụng Murmur3 và một biến thể rẻ hơn, MulSwapMul.

Với một hàm băm đủ nhanh, chi phí băm là rẻ và nó khắc phục được các phân phối xấu. Sử dụng MulSwapMul, hiệu suất trông như thế này bất kể phân phối dữ liệu:

| Kích thước dữ liệu | Sắp xếp cơ số đã băm |
|——————-|———————|
| 8 KiB | 6.5 µs |
| 256 KiB | 92 µs |
| 8 MiB | 3.9 ms |
| 256 MiB | 185 ms |
| 2 GiB | 1.9 s |

Đây là “thuật toán tốt nhất” được hiển thị ở đầu bài viết: băm với MulSwapMul, sau đó sắp xếp cơ số sử dụng sắp xếp cơ số LSD chuyển hướng. Tôi hợp nhất việc băm với lần duyệt đầu tiên của sắp xếp cơ số, và việc đếm với lần duyệt cuối cùng, để có một tốc độ tăng thêm nhỏ.

## Khi nào tôi nên chọn bảng băm so với sắp xếp cơ số đã băm?

Một số việc sử dụng bảng băm không thể được diễn giải lại dưới dạng sắp xếp cơ số đã băm; sau này hạn chế hơn. Việc chuyển đổi tra cứu/chèn bảng băm thành sắp xếp cơ số đã băm cơ bản yêu cầu xử lý theo lô: bạn phải phát ra nhiều truy vấn mà không cần kết quả cho đến sau này. Đôi khi bạn có thể biến đổi một thuật toán một lần duyệt (duyệt qua một cấu trúc dữ liệu và tra cứu khi đi) thành hai lần duyệt cấu trúc dữ liệu: trước tiên thu thập khóa từ cấu trúc dữ liệu; thực hiện sắp xếp cơ số; sau đó duyệt cấu trúc dữ liệu một lần nữa để ghi kết quả lại. Trong một số tình huống, chẳng hạn như băm đồng nhất, loại bỏ biểu thức con chung, hoặc bảng tra cứu trình phân tích, yêu cầu xử lý theo lô là một yếu tố quyết định: sắp xếp không khả thi.

Ở đâu việc xử lý theo lô là khả thi, sắp xếp cơ số đã băm thường là khả thi:

– Bất kỳ kiểu khóa nào có thể sử dụng với bảng băm đều hoạt động với sắp xếp cơ số đã băm: áp dụng cùng một băm.
– Nếu bạn đang xây dựng một bảng băm, tương đương là xây dựng một mảng đã sắp xếp bằng sắp xếp cơ số. Nếu bạn đang truy vấn một bảng hiện có, tương đương là: sắp xếp các truy vấn, sau đó thực hiện hợp tuyến tính thời gian với mảng khóa đã sắp xếp hiện có.
– Sắp xếp cơ số song song ít nhất tốt như bảng băm, nếu không thì tốt hơn.

Nếu sắp xếp cơ số đã băm khả thi cho vấn đề của bạn, liệu chúng sẽ nhanh hơn không? Yếu tố quyết định chính dường như là số lần truy cập lặp lại trên mỗi khóa duy nhất. Nếu bạn thực hiện nhiều chèn/tra cứu hơn nhiều so với số lượng khóa duy nhất, bảng băm có xu hướng thắng; nếu các truy cập có cùng số lượng với các khóa – hầu hết các khóa chỉ được chạm vào vài lần – sắp xếp cơ số có xu hướng thắng. Điều này là vì bảng băm sử dụng O(khóa duy nhất) bộ nhớ, trong khi sắp xếp cơ số sử dụng O(truy cập); phù hợp vào một dấu chân nhỏ hơn thường mang lại hiệu suất hệ thống bộ nhớ tốt hơn.

## Tại sao điều này quan trọng?

Nhiều hệ thống hiệu suất cao có một vòng lặp bên trong tương đương với điều này; tôi đã cá nhân làm việc trên hai hệ thống như vậy.

Thứ nhất, nhân ma trận thưa thớt cực độ với mật độ thưa thớt như một trong một tỷ và một vô hướng mỗi phần tử không zero. Điều này áp dụng cho Sibyl của Google, vào năm 2015 là một trong những khối lượng công việc lớn nhất của Google và tiêu thụ vài phần trăm CPU trên toàn bộ đội máy chủ. Tôi và nhiều người khác đã dành nhiều năm để tối ưu hóa các vòng lặp bên trong này.

Thứ hai, bộ kiểm tra BigCrush cho bộ tạo số ngẫu nhiên đếm các trùng lặp giữa n-gram của các số được tạo để tìm bất thường.

Theo kinh nghiệm của tôi, mặc định cho các vấn đề như vậy là bảng băm. Điều bất ngờ đối với tôi, sau khi chạy các đánh giá này, là sắp xếp cơ số có thể đánh bại chúng với biên độ đáng kể.

## Kết luận

Mặc dù về mặt lý thuyết, bảng băm có vẻ hiệu quả hơn với độ phức tạp O(n) so với sắp xếp cơ số có độ phức tạp O(n log n), thực tế cho thấy rằng sắp xếp cơ số đã được tinh chỉnh tốt có thể nhanh hơn đáng kể, đặc biệt đối với các bộ dữ liệu lớn. Điều này chủ yếu là do việc sử dụng băng thông bộ nhớ hiệu quả hơn của sắp xếp cơ số. Tuy nhiên, lựa chọn giữa bảng băm và sắp xếp cơ số phụ thuộc vào các yếu tố cụ thể của ứng dụng, bao gồm tần suất truy cập các khóa và khả năng xử lý theo lô của thuật toán.