Chậm hơn quicksort 25%, tôi đổ tội cho malloc — đo ra thủ phạm là thứ khác

Khi một việc chạy chậm, tâm trí ta chộp ngay lấy nghi phạm quen mặt — như cảnh sát lười bắt đúng kẻ có tiền án dù chưa xem bằng chứng. Trong lập trình, kẻ có tiền án đó thường là malloc: "chắc tại cấp phát bộ nhớ". Bài này là câu chuyện tôi bắt nhầm đúng nghi phạm quen mặt ấy, và đồng hồ chỉ ra kẻ thật nằm chỗ khác. Quicksort bài trước nhanh nhưng có mặt tối: pivot dở gặp mảng đã sắp thì thành O(n²) và tràn ngăn xếp. Merge sort là câu trả lời "chắc chắn" cho nỗi lo đó — O(n log n) trên mọi đầu vào, không ca xấu. Câu hỏi tự nhiên: nếu cả hai đều O(n log n), merge sort có nhanh bằng quicksort không? Tôi đo, và câu trả lời — cùng cách tôi tìm ra vì sao — là một bài học về việc big-O giấu điều gì và trực giác nhầm thủ phạm ra sao.

Merge sort: chia, sắp, rồi trộn

Merge sort cũng chia để trị, nhưng theo hướng ngược với quicksort. Nó chia mảng làm đôi một cách máy móc (đúng giữa, không cần chọn pivot), đệ quy sắp hai nửa, rồi trộn (merge) hai nửa đã sắp thành một dãy sắp hoàn chỉnh. Bước trộn là trái tim: đặt hai con trỏ ở đầu hai nửa, mỗi lần chép phần tử nhỏ hơn ra một mảng đệm, cứ thế cho tới hết. Vì việc chia luôn cân đúng một nửa, cây đệ quy luôn sâu đúng log n tầng, và mỗi tầng làm O(n) việc trộn — nên tổng luôn là O(n log n), bất kể đầu vào. Không có mảng đã sắp nào, không có kẻ tấn công nào, làm nó chậm đi được.

Merge sort có hai phẩm chất mà quicksort không có. Nó ổn định (stable): hai phần tử có khóa bằng nhau giữ nguyên thứ tự gốc — cực kỳ quan trọng khi bạn sắp theo nhiều tiêu chí liên tiếp. Và nó không có ca xấu O(n²). Cái giá đổi lại: nó không sắp tại chỗ, cần O(n) bộ nhớ phụ để trộn. Câu hỏi tôi mang vào phép đo: cái giá bộ nhớ đó khiến merge sort chậm hơn quicksort bao nhiêu, và cái chậm ấy nằm ở đâu?

Cùng O(n log n), mà chậm hơn 1,25 lần

Tôi cài merge sort (dùng một mảng đệm tái sử dụng) và quicksort trung vị-của-ba (từ bài trước), sắp cùng hai triệu số ngẫu nhiên:

quicksort (sắp tại chỗ)          :  98 ms
merge sort (một đệm tái dùng)    : 121 ms   = 1,25 lần quicksort

Cùng một độ phức tạp O(n log n), mà chênh nhau 25%. Big-O nói hai thuật toán này "như nhau"; đồng hồ nói không. Đây chính là điều ký hiệu tiệm cận giấu đi: nó đếm số phép so sánh (cả hai đều ~n log n phép), nhưng không đếm những gì mỗi phép kéo theo. Và tôi tưởng mình biết ngay thủ phạm.

Tôi nhầm thủ phạm là malloc

Trực giác của tôi bật ra lập tức: merge sort chậm hơn vì nó cấp phát bộ nhớ — cái mảng đệm. Ai cũng biết malloc trong vòng lặp nóng là kẻ giết hiệu năng. Tôi đoán rằng nếu viết một phiên bản merge sort ngây thơ hơn — cấp phát một mảng đệm mới trong mỗi lần trộn thay vì dùng một đệm chung — thì nó sẽ chậm thảm hại, và đó sẽ là bằng chứng cho "malloc giết hiệu năng".

Tôi đo phiên bản malloc-mỗi-lần đó:

merge sort (một đệm tái dùng)      : 121 ms
merge sort (malloc mỗi lần trộn)   : 128 ms   = chỉ chậm hơn 6%

Chỉ 6%. Không hề là thảm họa tôi chờ đợi. Hóa ra bộ cấp phát của glibc có một đường nhanh cho những lần cấp phát nhỏ cùng cỡ lặp đi lặp lại (tcache), nên malloc trong merge rẻ hơn nhiều so với danh tiếng của nó. Trực giác của tôi đã chỉ nhầm thủ phạm. Vậy 23 mili giây chênh giữa quicksort và merge sort đến từ đâu, nếu không phải malloc?

Phân rã con số cho câu trả lời sạch sẽ. Phiên bản merge "một đệm tái dùng" không cấp phát trong vòng nóng, mà vẫn chậm hơn quicksort 23 mili giây. Phiên bản malloc-mỗi-lần chỉ cộng thêm 7 mili giây nữa. Nghĩa là: chi phí chép dữ liệu (23 ms) lớn hơn chi phí cấp phát (7 ms) gấp ba. Thủ phạm thật là việc merge sort, ở mỗi tầng trong log n tầng, phải chép cả n phần tử ra mảng đệm rồi chép ngược về — đó là n log n lượt di chuyển bộ nhớ mà quicksort hoàn toàn không phải trả, vì quicksort phân hoạch ngay tại chỗ trên mảng gốc, chẳng chép đi đâu cả. Điều rút ra: khi một thứ chậm hơn, đừng tin thủ phạm đầu tiên trực giác chỉ ra — đo để tách bạch, vì cái đắt thường không phải cái bạn nghĩ. Ở đây tôi suýt viết cả một đoạn đổ tội cho malloc, trong khi đồng hồ chỉ thẳng vào việc di chuyển dữ liệu.

Vậy dùng merge sort để làm gì?

Nếu merge sort chậm hơn quicksort, sao còn dùng? Vì tốc độ thô không phải giá trị của nó. Tôi đo hai thứ khác. Thứ nhất, ổn định: tôi sắp một triệu bản ghi có khóa trùng nhau rất nhiều (nghìn giá trị khóa cho một triệu bản ghi) và đếm số cặp cùng khóa bị đảo thứ tự gốc. Merge sort: 0 cặp đảo — hoàn toàn ổn định. Quicksort: 488.887 cặp đảo — nó xáo tung thứ tự của các phần tử bằng nhau. Khi bạn sắp một bảng theo cột A rồi theo cột B và muốn giữ thứ tự A trong các nhóm B bằng nhau, tính ổn định này là bắt buộc, và quicksort không cho bạn. Thứ hai, không ca xấu: merge sort trên mảng đã sắp hai triệu phần tử chạy 27 mili giây — nhanh như (thực ra nhanh hơn) trên dữ liệu ngẫu nhiên, chứ không sụp thành O(n²) như quicksort pivot dở. Merge sort đổi 25% tốc độ để lấy hai bảo đảm: thứ tự ổn định và không bao giờ có ngày tồi tệ.

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

Điều đầu tiên: chọn thuật toán sắp xếp theo tính chất bạn cần, không theo một chữ "nhanh" trần trụi. Cần tốc độ thô trên dữ liệu trong bộ nhớ và không quan tâm thứ tự phần tử bằng nhau? Quicksort (có ngẫu nhiên hóa pivot). Cần thứ tự ổn định, hoặc bảo đảm không bao giờ O(n²), hoặc đang sắp một danh sách liên kết (nơi merge không cần bộ nhớ phụ và quicksort thì vụng), hoặc sắp dữ liệu lớn hơn RAM phải đọc theo dòng từ đĩa (external sort — merge là nền tảng của nó)? Merge sort.

Và đây là chỗ hiểu biết này trả cổ tức trên code thật, vì tính ổn định không phải chi tiết học thuật — nó là hợp đồng bạn dựa vào. Java tách bạch rõ: Arrays.sort(int[]) là quicksort không ổn định, còn Arrays.sort(Object[]) và Collections.sort/List.sort là Timsort (nền merge) có ổn định — nên "sắp theo ngày rồi sắp lại theo tên, giữ nguyên thứ tự ngày trong mỗi tên" chỉ đúng với cái sau. Python sorted/list.sort luôn ổn định (Timsort), đó là lý do mẫu "sort nhiều khóa bằng nhiều lần sort" hoạt động. Còn dữ liệu lớn hơn RAM thì merge là vua tuyệt đối: ORDER BY của cơ sở dữ liệu tràn ra đĩa dùng external merge sort, và MapReduce/Spark trộn kết quả cũng bằng merge — vì merge chỉ cần đọc tuần tự từng dòng, thứ mà đĩa và mạng làm tốt còn quicksort truy cập ngẫu nhiên thì không. Mẫu số chung: big-O giống nhau không có nghĩa hiệu năng giống nhau, và giá trị của một thuật toán không phải lúc nào cũng là tốc độ — đôi khi là những bảo đảm (ổn định, không ca xấu, đọc tuần tự) mà nó cho bạn.

Còn về đo lường thì bài này để lại một thói quen: khi tối ưu, tách bạch nguyên nhân bằng phép đo, đừng vá theo trực giác. Nếu tôi tin ngay "malloc là thủ phạm", tôi đã đi tối ưu cấp phát và chỉ vắt ra được 6%, trong khi vấn đề thật — di chuyển dữ liệu — lớn gấp ba và nằm chỗ khác. Cách đúng là dựng hai phiên bản chỉ khác nhau đúng một yếu tố (có/không malloc trong vòng nóng) rồi đo hiệu số, để mỗi con số quy về đúng một nguyên nhân.

Muốn tự kiểm thì lần tới khi gọi một hàm sắp xếp, hỏi một câu bạn có thể chưa từng hỏi: nó có ổn định không? Tài liệu thường ghi rõ, và nó quyết định hành vi thật — sắp một danh sách đã theo tên rồi sắp lại theo tuổi, một sort ổn định giữ người cùng tuổi theo thứ tự tên, một sort không ổn định thì không. Thử nhanh: tạo vài bản ghi có khóa trùng, sắp, xem thứ tự các bản ghi cùng khóa có giữ nguyên không. Và nếu bạn từng thấy một đoạn code sắp xếp chậm bất ngờ, đừng vội đoán "chắc tại cấp phát" — hãy đo hai phiên bản khác nhau đúng một yếu tố, để đồng hồ chỉ cho bạn thủ phạm thật, thứ mà trực giác rất hay bắt nhầm.