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
- Nếu comparator gọi
-
- 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.
```mermaid
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:
```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:
```python
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:
```dart
// ❌ 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.
```mermaid
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:
```bash
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ử.All rights reserved
