Your Sort Is Slow Because of Your Comparator: The Schwartzian Transform in JavaScript, Python and Dart

Tuần này mình đọc một bài trên Dev.to. Tác giả nhắc lại Schwartzian Transform sau khi thấy một bài tối ưu performance Flutter bỏ sót nó. Mình nhận ra kỹ thuật cũ từ thời Perl những năm 90 này vẫn cứu được rất nhiều code production năm 2026. Trong các lần review code, mình gặp lỗi này nhiều lần: một hàm sort() trông vô hại lại chiếm 70% thời gian xử lý request, chỉ vì comparator gọi một hàm tốn kém hàng trăm nghìn lần. Bài này giải thích vấn đề nằm ở đâu, cách sửa trong JavaScript, Python và Dart, và khi nào không nên áp dụng.

Vấn đề: comparator bị gọi nhiều hơn bạn nghĩ

Thuật toán sort dựa trên so sánh (TimSort trong V8 từ Chrome 70/Node 11, TimSort trong CPython, Dual-Pivot Quicksort/Insertion sort trong Dart) cần khoảng n·log₂(n) lần so sánh. Mỗi lần so sánh, comparator xử lý cả hai phần tử.

Với n = 10.000 phần tử:

• Số lần so sánh ≈ 10.000 × 13,3 ≈ 133.000
• Nếu comparator gọi expensive(a) và expensive(b) thì sẽ có khoảng 266.000 lần gọi hàm tốn kém
• Trong khi thực tế chỉ cần 10.000 lần, mỗi phần tử một lần

Bạn đang lãng phí gấp khoảng 26 lần. Khi n tăng, con số này còn tăng theo log(n).

Ví dụ kinh điển mà dev Việt hay gặp: sort danh sách tên tiếng Việt có dấu.

// ❌ Cách hay gặp: normalize + bỏ dấu trong comparator
function removeTones(s) {
  return s
    .normalize('NFD')
    .replace(/[\u0300-\u036f]/g, '')
    .replace(/đ/g, 'd')
    .replace(/Đ/g, 'D')
    .toLowerCase();
}

users.sort((a, b) => removeTones(a.name).localeCompare(removeTones(b.name)));

Đoạn code này đúng, nhưng với 50.000 user, removeTones bị gọi gần 1,6 triệu lần. Mỗi lần gọi lại cấp phát vài string mới, nên GC phải làm việc liên tục.

Schwartzian Transform: decorate → sort → undecorate

Ý tưởng rất đơn giản: tính key đắt tiền một lần cho mỗi phần tử, gắn key vào phần tử, sort theo key, rồi bóc key ra.

flowchart LR
    A[Mảng gốc] -->|map: tính key 1 lần/phần tử| B[Mảng tuple: key, item]
    B -->|sort theo key rẻ| C[Tuple đã sắp xếp]
    C -->|map: lấy item| D[Mảng kết quả]

Phiên bản JavaScript:

// ✅ Schwartzian Transform
const collator = new Intl.Collator('vi', { sensitivity: 'base' });

function sortByName(users) {
  return users
    .map((u) => [removeTones(u.name), u])     // decorate
    .sort((x, y) => collator.compare(x[0], y[0])) // sort theo key có sẵn
    .map(([, u]) => u);                       // undecorate
}

// Benchmark nhanh với Node 22
const users = Array.from({ length: 50_000 }, (_, i) => ({
  name: ['Nguyễn Văn An', 'Trần Thị Bích', 'Đỗ Đức Đạt', 'Lê Hoàng'][i % 4] + ' ' + i,
}));

console.time('naive');
[...users].sort((a, b) => removeTones(a.name).localeCompare(removeTones(b.name)));
console.timeEnd('naive');

console.time('schwartzian');
sortByName(users);
console.timeEnd('schwartzian');

Trên MacBook M2 với Node 22.x, mình đo được khoảng 1.900ms cho cách naive và ~85ms cho cách dùng Schwartzian Transform. Có hai cải thiện cộng dồn ở đây:

1. removeTones chỉ chạy 50.000 lần thay vì khoảng 1,6 triệu lần.
2. Intl.Collator được tạo một lần. Mỗi lần gọi localeCompare với locale, engine có thể phải khởi tạo lại collator nội bộ, và chi phí này lớn hơn nhiều người nghĩ.

Mẹo phụ: nếu chỉ cần so sánh không phân biệt dấu, new Intl.Collator('vi', { sensitivity: 'base' }) đã tự bỏ qua dấu, nên có thể không cần removeTones nữa. Nhưng pattern decorate-sort-undecorate vẫn áp dụng cho mọi loại key đắt tiền khác.

Python: key= đã làm sẵn, đừng phá nó bằng cmp_to_key

Python có Schwartzian Transform tích hợp sẵn từ bản 2.4 qua tham số key=. CPython gọi hàm key đúng một lần cho mỗi phần tử, lưu kết quả, rồi sort trên đó. Python 3 còn bỏ hẳn tham số cmp.

Vấn đề là mình vẫn thấy code kiểu này trong các project migrate từ Python 2 hoặc do người quen viết Java:

import os
import time
from functools import cmp_to_key
from pathlib import Path

files = list(Path('/var/log').rglob('*'))  # vài nghìn file

# ❌ cmp_to_key + syscall trong comparator: os.stat bị gọi O(n log n) lần
def compare(a, b):
    return os.stat(a).st_mtime - os.stat(b).st_mtime

t = time.perf_counter()
sorted(files, key=cmp_to_key(compare))
print(f'cmp_to_key: {time.perf_counter() - t:.3f}s')

# ✅ key=: os.stat chỉ gọi n lần
t = time.perf_counter()
sorted(files, key=lambda p: p.stat().st_mtime)
print(f'key=:       {time.perf_counter() - t:.3f}s')

# ✅ Multi-key: tuple so sánh theo thứ tự, vẫn chỉ tính 1 lần/phần tử
sorted(files, key=lambda p: (p.suffix, -p.stat().st_size, p.name))

Ở đây hàm key là một syscall, nên chênh lệch rất rõ: với khoảng 5.000 file, bản cmp_to_key chậm hơn cỡ 10–15 lần. Nếu file nằm trên NFS hoặc network mount, con số này còn tệ hơn nhiều.

Quy tắc của mình: chỉ dùng cmp_to_key khi logic so sánh thật sự không biểu diễn được bằng key, ví dụ phép so sánh không bắc cầu hoặc phụ thuộc vào cặp phần tử. Trường hợp này rất hiếm.

Dart/Flutter: chỗ hay bị bỏ quên nhất

Trong Flutter, sort thường chạy trên UI isolate. Sort chậm 50ms nghĩa là rớt khoảng 3 frame ở 60fps. List.sort của Dart chỉ nhận comparator và không có key= như Python, nên bạn phải tự làm transform. Dart 3 có records nên code khá gọn:

// ❌ DateTime.parse bị gọi O(n log n) lần
messages.sort((a, b) =>
    DateTime.parse(b.createdAt).compareTo(DateTime.parse(a.createdAt)));

// ✅ Schwartzian Transform với Dart 3 records
List<Message> sortByDateDesc(List<Message> messages) {
  final decorated = [
    for (final m in messages) (DateTime.parse(m.createdAt).microsecondsSinceEpoch, m)
  ];
  decorated.sort((x, y) => y.$1.compareTo(x.$1));
  return [for (final (_, m) in decorated) m];
}

Nếu danh sách lớn (hơn 10.000 item), hãy kết hợp thêm Isolate.run() (Dart 2.19+) hoặc compute() để đẩy việc sort khỏi UI thread.

flowchart TD
    S[Cần sort danh sách] --> Q1{Key có đắt không?<br/>parse, regex, IO, normalize}
    Q1 -->|Không, chỉ đọc field| N[Sort trực tiếp, không cần transform]
    Q1 -->|Có| Q2{Ngôn ngữ có key= built-in?}
    Q2 -->|Python sorted/list.sort| P[Dùng key=, tránh cmp_to_key]
    Q2 -->|JS / Dart / Go| T[Decorate - Sort - Undecorate]
    T --> Q3{n lớn và chạy trên UI thread?}
    Q3 -->|Có| W[Đẩy sang Worker / Isolate]

Khi nào KHÔNG nên dùng

Đừng áp dụng một cách máy móc. Schwartzian Transform có chi phí riêng:

• Bộ nhớ: tạo thêm một mảng tuple có n phần tử. Với vài triệu object trên mobile, điều này có thể gây áp lực lên bộ nhớ.
• Key rẻ thì không đáng: a.age - b.age hay a.id.localeCompare(b.id) không cần transform. Thêm map hai lần còn làm code chậm hơn một chút.
• Mảng nhỏ: dưới vài trăm phần tử thì chênh lệch tính bằng micro giây. Hãy ưu tiên code dễ đọc.

Cách nhanh nhất để biết có cần tối ưu hay không là đo. Trong Node, đếm số lần comparator được gọi:

node -e "let c=0; const a=Array.from({length:1e4},()=>Math.random()); a.sort((x,y)=>(c++,x-y)); console.log('comparisons:', c)"
# comparisons: ~120000

Nếu con số đó nhân với chi phí hàm key của bạn ra một giá trị đáng kể, đó là lúc nên dùng transform.

Kết luận

Schwartzian Transform đã hơn 30 tuổi nhưng vẫn là một trong những tối ưu có tỉ lệ "công sức / hiệu quả" tốt nhất mà mình biết. Những việc bạn có thể làm ngay:

1. Grep codebase tìm .sort( có gọi parse, normalize, replace, toLowerCase, new Date, stat hoặc regex bên trong comparator. Đó là những ứng viên cần sửa.
2. Python: luôn dùng key=, xem mọi chỗ dùng cmp_to_key là code smell cần review. Dùng tuple cho multi-key.
3. JS/TS: tạo Intl.Collator một lần rồi tái sử dụng, đừng gọi localeCompare(x, 'vi') trong vòng lặp. Với key đắt tiền, dùng pattern map → sort → map.
4. Dart/Flutter: dùng records (key, item) để làm transform, và đẩy sang Isolate.run() khi danh sách lớn.
5. Đo trước khi tối ưu: đếm số lần comparator chạy, dùng console.time hoặc time.perf_counter. Đừng tối ưu một mảng chỉ có 20 phần tử.

Lần tới khi profiler chỉ ra sort() là hotspot, đừng vội đổi thuật toán hay thêm cache phức tạp. Thường bạn chỉ cần tính key một lần cho mỗi phần tử.