So Sánh Giải Thuật GCD và Bitmask Trong Việc Tìm Overlapping Days
Phần 1: Mở Đầu — Ticket Đến Vào Một Buổi Sáng Không Có Gì Đặc Biệt
Hôm đó là một buổi sáng thứ Tư bình thường. Tôi vừa rót xong cốc cà phê, vừa ngồi xuống, vừa mở Jira thì đọc thấy một cái ticket với title ngắn gọn đến mức đáng ngờ:
“Validate: không cho phép tạo hai policy detail trùng ngày."
Oke. Nghe đơn giản. Hai khoảng thời gian không được trùng nhau — ai cũng học cái này hồi năm nhất đại học rồi, có gì đâu.
Nhưng mà đời không đơn giản vậy. Vì ở đây, hai policy không chỉ có fromDate và toDate. Chúng còn có thêm weekdays — kiểu như “policy này chỉ áp dụng vào thứ 2, thứ 4, thứ 6”, còn cái kia “áp dụng vào thứ 3, thứ 5”.
Vậy câu hỏi là: hai khoảng sau có “trùng” không?
Policy A: từ 01/01 đến 31/01, áp dụng thứ 2+4+6
Policy B: từ 15/01 đến 28/02, áp dụng thứ 3+5
Ngày thì chồng lên nhau (15/01 đến 31/01), nhưng weekday thì hoàn toàn khác nhau. Nên câu trả lời là: không trùng. Business logic đúng, nhưng implementation thì… tùy cách bạn viết.
Và đó là lý do tại sao tôi hôm nay kể câu chuyện về hai cách giải bài toán y hệt nhau, một cái dùng số học số nguyên tố + GCD, một cái dùng bitmask dịch bit. Cả hai đều đúng. Nhưng rất khác nhau về cả elegance lẫn performance thực đo.
Phần 2: Vấn Đề Và Bối Cảnh
Bài toán gốc
Hệ thống cần validate rằng khi tạo hoặc cập nhật một “policy detail” (có thể hiểu là một quy tắc áp dụng trong một khoảng thời gian), không được có hai detail nào trùng ngày cùng nhau.
“Trùng ngày” ở đây có nghĩa là:
- Khoảng thời gian
[from, to]chồng lên nhau (date range overlap) - VÀ trong phần chồng nhau đó, hai bên đều có ít nhất một ngày trong tuần chung
Ví dụ cho dễ hiểu:
Khoảng A: 01/01 - 31/01 | weekdays: [2, 4, 6] (thứ 2, 4, 6)
Khoảng B: 15/01 - 28/02 | weekdays: [3, 5, 7] (thứ 3, 5, 7)
→ Ngày trùng: 15/01-31/01
→ Weekday trùng: không có (tập rỗng)
→ KẾT LUẬN: KHÔNG OVERLAP
Khoảng A: 01/01 - 31/01 | weekdays: [2, 3, 4] (thứ 2, 3, 4)
Khoảng B: 15/01 - 28/02 | weekdays: [4, 5, 6] (thứ 4, 5, 6)
→ Ngày trùng: 15/01-31/01
→ Weekday trùng: [4] (thứ 4 có mặt ở cả hai)
→ KẾT LUẬN: CÓ OVERLAP
Bây giờ, làm sao detect điều đó một cách hiệu quả?
Quy ước ngày trong tuần dùng xuyên suốt bài:
1=Chủ Nhật, 2=Thứ Hai, 3=Thứ Ba, 4=Thứ Tư, 5=Thứ Năm, 6=Thứ Sáu, 7=Thứ Bảy. Đây là quy ước legacy — khác vớiDate.getDay()của JavaScript (vốn trả về 0=Sunday). Tất cả code snippet đều theo quy ước này.
Phần 3: Giải Pháp Cũ — Toán Học Với Số Nguyên Tố Và GCD
Cách hoạt động
Phiên bản gốc của hệ thống (viết bằng JavaScript, Express + Sequelize) giải quyết bài toán weekday overlap bằng một trick toán học khá thú vị.
Bước 1: Gán số nguyên tố cho từng ngày trong tuần
// Mỗi ngày trong tuần được gán một số nguyên tố riêng
const CHECKSUM_DAYS_VALUES = [3, 5, 7, 11, 13, 17, 19];
// index: 0 1 2 3 4 5 6
// tương ứng: Sun Mon Tue Wed Thu Fri Sat
// (weekday 1=Sun → index 0 → prime 3)
// (weekday 7=Sat → index 6 → prime 19)
Bước 2: Tính checksum = tích của các số nguyên tố
function calcChecksumForDaysArr(dayArr = []) {
return dayArr.reduce(
(result, current) => result * CHECKSUM_DAYS_VALUES[current - 1],
1
);
}
// Ví dụ:
// weekdays = [2, 4, 6] → checksum = 5 * 11 * 17 = 935
// weekdays = [4, 5, 6] → checksum = 11 * 13 * 17 = 2431
// weekdays = [3, 5] → checksum = 7 * 13 = 91
Tại sao phải là số nguyên tố, không phải 1, 2, 3…7 hay powers of 2?
Đây là câu hỏi quan trọng nhất. Ba lý do:
- Nếu dùng 1,2,…7 với phép cộng:
checksum([2,4]) = 2+4 = 6vàchecksum([1,2,3]) = 1+2+3 = 6— hai tập hoàn toàn khác nhau cho ra cùng checksum. Collision không thể dùng được. - Nếu dùng powers of 2 (1,2,4,8,…) với phép nhân: kết quả là bitmask! Approach này đúng nhưng khi đó không cần GCD nữa —
checkA & checkB != 0là đủ. Cách này chính là bitmask approach ở phần sau của bài. - Dùng số nguyên tố phân biệt với phép nhân: theo Định lý phân tích nhân tử (mọi số nguyên > 1 có duy nhất một cách viết dưới dạng tích các số nguyên tố), mỗi tập weekdays cho ra một tích duy nhất. Hai tích có GCD > 1 khi và chỉ khi chúng chia sẻ ít nhất một thừa số nguyên tố chung — tức là chia sẻ ít nhất một ngày trong tuần.
Vì vậy mảng là [3, 5, 7, 11, 13, 17, 19] — 7 số nguyên tố nhỏ nhất lớn hơn 2. (Bỏ 2 vì mọi tích số nguyên tố chẵn đều có GCD = 2 với nhau, gây false positive.)
Bước 3: Khi query, dùng hàm GCD trong MySQL
SELECT * FROM PolicyDetail
WHERE parentId = :parentId
AND fn_gcd(:checkSum, weekdaysChecksum) > 1
AND (
(from BETWEEN :from AND :to)
OR (to BETWEEN :from AND :to)
OR (from < :from AND to > :to)
)
Tại sao fn_gcd > 1 lại phát hiện được weekday chung? Vì Định lý phân tích nhân tử nguyên tố (Fundamental Theorem of Arithmetic) đảm bảo rằng: hai tích của các số nguyên tố phân biệt có GCD > 1 khi và chỉ khi chúng chia sẻ ít nhất một thừa số nguyên tố chung — tức là chia sẻ ít nhất một ngày trong tuần.
checkSum A = 5 * 11 * 17 = 935 (thứ 2, 4, 6)
checkSum B = 11 * 13 * 17 = 2431 (thứ 4, 5, 6)
GCD(935, 2431) = 11 * 17 = 187 > 1 → CÓ ngày chung (thứ 4 và thứ 6)
checkSum A = 5 * 11 * 17 = 935 (thứ 2, 4, 6)
checkSum C = 7 * 13 * 19 = 1729 (thứ 3, 5, 7)
GCD(935, 1729) = 1 → KHÔNG có ngày chung
Elegant không? Toán học số học ứng dụng thực tế luôn.
Tóm lại, approach GCD dùng hai cơ chế khác nhau cho hai layer khác nhau:
- DB-side (Sub-approach 1): lưu
weekdaysChecksumvào cột DB, query bằngfn_gcd()ngay trong SQL. MySQL lo hết, app không cần fetch data về. - In-memory (Sub-approach 2): khi cần validate trong service layer trước khi lưu, code dùng
getDateListFromTo()để sinh danh sách ngày → đếm bằng plain{}object. Chậm hơn nhiều và là cái mà benchmark phần sau đo.
Dưới đây là Sub-approach 2 in-memory:
function checkHasOverlap(arrDateConfig = []) {
let objCheck = {};
for (let i = 0; i < arrDateConfig.length; i++) {
// Sinh ra toàn bộ danh sách ngày trong khoảng + filter weekday
let dates = getDateListFromTo(
arrDateConfig[i].fromDate,
arrDateConfig[i].toDate,
arrDateConfig[i].weekdays
);
// Đếm vào hashmap
for (const aDate of dates) {
objCheck[aDate] = (objCheck[aDate] || 0) + 1;
}
// Nếu có ngày nào count > 1 → overlap
for (const key in objCheck) {
if (objCheck[key] > 1)
return [{ message: `Has overlap on ${key}`, item: arrDateConfig[i] }];
}
}
return false;
}
Mỗi lần gọi, hàm getDateListFromTo duyệt từng ngày từ fromDate đến toDate, filter theo weekday, rồi push string "YYYY-MM-DD" vào array. Với một khoảng 90 ngày × 300 records, đó là 27.000 Date object + 27.000 string allocation mỗi lần gọi.
Ưu điểm của approach GCD
1. Overlap detection trên database — không cần load data lên app
Cách hay nhất: query thẳng vào DB với fn_gcd(), tránh phải fetch hết data về app để compare. Với các bảng lớn, đây là sự khác biệt lớn về performance.
2. Trick toán học elegant, compact
Thay vì lưu cả array weekdays rồi compare, chỉ cần lưu một con số integer (weekdaysChecksum). Tra cứu nhanh, index được.
3. Phù hợp với moment.js ecosystem đã có sẵn
Phần date range dùng moment, phần weekday dùng checksum — hai lớp logic hoàn toàn tách biệt, dễ maintain.
Nhược điểm của approach GCD
1. Phụ thuộc vào MySQL custom function fn_gcd()
Đây là điểm nguy hiểm nhất. fn_gcd không phải built-in của MySQL — phải define bằng CREATE FUNCTION. Nếu deployment mới, DB migration không chạy function đó, hoặc team không biết nó tồn tại → query chắc chắn bị lỗi hoặc cho kết quả sai mà không có error rõ ràng.
2. Checksum có thể lớn bất ngờ
weekdays = [1,2,3,4,5,6,7] → checksum = 3*5*7*11*13*17*19 = 9,699,690
Vẫn nằm trong INT range của MySQL, nhưng với logic chưa rõ ràng thì con số này trong DB nhìn rất… kỳ lạ.
3. Khó debug
Bạn nhìn vào DB thấy weekdaysChecksum = 935, bạn phải tự tính ngược lại là “à, cái này là tích của 5 * 11 * 17, ứng với thứ 2, 4, 6”. Không ai làm việc đó một cách tự nhiên.
4. In-memory fallback (getDateListFromTo) là O(n × d)
Khi không query DB (ví dụ validate trong service trước khi lưu), code sinh toàn bộ danh sách ngày — khoảng 365 ngày × số config → chạy chậm nếu nhiều khoảng. Đây chính là điểm mà benchmark sau sẽ cho thấy rõ nhất.
Phần 4: Đo Lường Thực Tế — Tại Sao Phải Test Performance?
“Premature optimization is the root of all evil” — Knuth “Nhưng nếu không đo, bạn không biết mình đang tối ưu cái gì.” — Tôi, sau 3 lần tối ưu sai chỗ
Hai algorithm đều đúng về mặt logic. Nhưng “đúng” và “nhanh” là hai chuyện khác nhau. Với một pricing engine chạy validation cho hàng trăm config mỗi request, sự khác biệt về performance có thể là chênh lệch giữa response 10ms và response 10 giây.
Vì vậy, thay vì chỉ nhìn code rồi suy đoán, chúng tôi viết một benchmark in-memory — extract cả hai algorithm ra file riêng, chạy trên cùng một bộ test data, đo bằng các metric khách quan.
Test cases — Tại sao chọn như vậy?
Benchmark được thiết kế theo nguyên tắc: đo ở nhiều điểm trên đường cong tăng trưởng, không chỉ đo một scenario rồi kết luận.
const SCENARIOS = [
// Nhỏ: kiểm tra overhead cơ bản, loại bỏ JIT warm-up noise
{ label: 'tiny-nofilter', n: 10, span: 7, weekdays: ALL_DAYS, iters: 2000 },
{ label: 'tiny-overlap', n: 10, span: 7, weekdays: ALL_DAYS, iters: 2000 },
// Trung bình: gần với production load thực tế (50-100 config/property)
{ label: 'small-nofilter', n: 50, span: 31, weekdays: ALL_DAYS, iters: 1000 },
{ label: 'medium-nofilter', n: 100, span: 31, weekdays: ALL_DAYS, iters: 500 },
// Có filter weekday: kiểm tra xem filter có giúp skip bớt ngày không
{ label: 'medium-filtered', n: 100, span: 31, weekdays: [2,4,6], iters: 500 },
// Lớn: stress test, thấy rõ O(n×d) của GCD
{ label: 'large-nofilter', n: 300, span: 90, weekdays: ALL_DAYS, iters: 50 },
// Tệ nhất có thể: 200 khoảng × 90 ngày, không có overlap → GCD phải quét hết
{ label: 'worst-case', n: 200, span: 90, weekdays: ALL_DAYS, iters: 20 },
];
Lý do chọn từng thông số:
n(số ranges): từ 10 đến 300, phản ánh thực tế từ property nhỏ (vài config) đến property lớn (hàng trăm config theo mùa).span(độ dài mỗi range): 7 ngày (1 tuần), 31 ngày (1 tháng), 90 ngày (1 quý) — GCD in-memory phải sinh ran × spandate string, nên span là biến khuếch đại quan trọng.weekdays: ALL_DAYSvs[2,4,6]: test xem filter weekday có giảm được số ngày cần xét không — bitmask AND loại bỏ ngay trước khi enumerate, GCD phải filter tronggetDateListFromTo.overlap: false(no-overlap): trường hợp tệ nhất cho cả hai — phải quét hết toàn bộ data mà không được early-return.overlap: true: trường hợp tốt nhất — cả hai có thể exit sớm khi tìm thấy.- Iterations cao ở scenario nhỏ: 2000 iterations cho tiny để loại bỏ JIT noise (V8 cần vài chục lần chạy mới JIT-compile đúng cách). Scenario lớn giảm iterations vì GCD quá chậm — không thể chạy 1000 lần mỗi scenario mà đợi được.
Trước khi đo, benchmark chạy một correctness check — đảm bảo cả hai algorithm cho cùng kết quả (có overlap / không có overlap) trên cùng input. Nếu lệch nhau thì exit ngay:
function verifyAgreement(label, gcdRanges, bitmaskRanges) {
const gcdResult = gcd.checkHasOverlap(gcdRanges);
const bitmaskResult = bitmask.checkHasOverlap(bitmaskRanges);
if (!!gcdResult !== (bitmaskResult !== null)) {
console.error(`[CORRECTNESS FAIL] ${label}`);
process.exit(1);
}
}
Các thông số đo lường — Giải thích chi tiết
Benchmark dùng 4 metric thuần Node.js, không cần thư viện ngoài:
const cpuBefore = process.cpuUsage();
const memBefore = process.memoryUsage();
const t0 = performance.now();
fn(); // ← algorithm đang test
const elapsed = performance.now() - t0;
const cpuDelta = process.cpuUsage(cpuBefore); // { user, system } tính bằng µs
const memAfter = process.memoryUsage();
1. Wall time (ms) — performance.now()
Thời gian thực tế từ lúc gọi đến lúc trả về, tính bằng millisecond với độ chính xác microsecond. Đây là metric “người dùng cảm nhận” — latency thực tế của một API call.
Chúng ta collect min / avg / p95 / p99 / max để thấy được:
avg: hiệu suất trung bìnhp95 / p99: trường hợp xấu xảy ra bao nhiêu lần trong 100 (tail latency)max: trường hợp tệ nhất — thường do GC hoặc OS scheduling
2. CPU user time (µs) — process.cpuUsage().user
Số microsecond CPU thực sự dành cho tính toán của process (không kể thời gian bị OS preempt hoặc đợi I/O). Đây là metric “CPU cost thuần túy” — phản ánh độ phức tạp thuật toán chính xác hơn wall time vì không bị ảnh hưởng bởi context switching.
Nếu cpu-user thấp mà wall time cao → process đang đợi gì đó (GC, I/O). Nếu cả hai đều cao → thuật toán thực sự tốn CPU.
3. CPU sys time (µs) — process.cpuUsage().system
Số microsecond kernel dành cho process — thường là memory allocation syscall, buffer management. Với in-memory algorithm lý tưởng, con số này phải gần 0. Nếu cao → code đang tạo quá nhiều object khiến allocator phải gọi kernel liên tục.
4. Heap delta (KB) — process.memoryUsage().heapUsed
Lượng V8 heap được allocate mỗi call, tính bằng KB. Đây là metric quan trọng nhất để so sánh hai algorithm về memory pressure:
- GCD in-memory: mỗi call tạo một
string[]cho toàn bộ danh sách ngày + một{}object làm hashmap - Bitmask: tạo một
number[]cho epoch days + mộtMap<number, number>— compact hơn nhiều
Giá trị âm xảy ra khi GC chạy trong lúc measure — bình thường, average qua nhiều iterations sẽ cho con số ổn định.
5. RSS delta (KB) — process.memoryUsage().rss
Resident Set Size — tổng memory của process bao gồm cả code, stack, và native buffers. Phản ánh memory pressure thực sự lên OS, bao gồm cả overhead ngoài V8 heap.
GC isolation với --expose-gc
node --expose-gc compare/bench.js
Giữa mỗi scenario, benchmark gọi global.gc() để flush hết accumulated allocations:
function gcIfAvailable() {
if (typeof global.gc === 'function') global.gc();
}
// Trước mỗi scenario:
gcIfAvailable();
const gcdRaw = measureFn(() => gcd.checkHasOverlap(gcdFmt), s.iters);
Không làm vậy, GC pause của scenario trước sẽ “bleeding” vào timing của scenario sau — cho ra số liệu không đáng tin.
Phần 4b: Script Test — Cách Chạy Và Cấu Trúc
Toàn bộ benchmark được đặt trong thư mục compare/ của project:
compare/
├── bench.js ← script benchmark chính (542 dòng)
├── algos/
│ ├── gcd-memory.js ← faithful copy của production code (97 dòng)
│ └── bitmask.js ← port sang JS thuần của TS code mới (161 dòng)
├── results/
│ ├── latest.json ← raw data JSON của lần chạy gần nhất
│ └── latest.log ← full output text
└── README.md
Chạy benchmark
# Cơ bản — không có GC isolation
node compare/bench.js
# Khuyến nghị — bật GC isolation để kết quả clean hơn
node --expose-gc compare/bench.js
Kết quả tự động lưu vào compare/results/latest.json và compare/results/latest.log.
gcd-memory.js — Copy trung thành của production code
File này không sửa gì so với code gốc — copy nguyên si từ:
services/util.js→CHECKSUM_DAYS_VALUES,calcChecksumForDaysArr,getDateListFromTobusiness/rate-season/RateSeasonManager.js→checkHasOverlap
// File: compare/algos/gcd-memory.js
// Primes cho 7 ngày trong tuần (1=Sun, 7=Sat)
const CHECKSUM_DAYS_VALUES = [3, 5, 7, 11, 13, 17, 19];
function calcChecksumForDaysArr(dayArr = []) {
return dayArr.reduce(
(result, current) => result * CHECKSUM_DAYS_VALUES[current - 1], 1
);
}
function getDateListFromTo(from, to, weekdays = [1,2,3,4,5,6,7]) {
// ... iterate từng ngày, push vào string array nếu weekday match
}
function checkHasOverlap(arrDateConfig = []) {
let objCheck = {};
for (let i = 0; i < arrDateConfig.length; i++) {
let dates = getDateListFromTo(
arrDateConfig[i].fromDate,
arrDateConfig[i].toDate,
arrDateConfig[i].weekdays
);
for (const aDate of dates) {
objCheck[aDate] = (objCheck[aDate] || 0) + 1;
}
for (const key in objCheck) {
if (objCheck[key] > 1)
return [{ message: `Has overlap on ${key}`, item: arrDateConfig[i] }];
}
}
return false;
}
bitmask.js — Port JavaScript của TypeScript mới
File này là JS port của src/common/helpers/overlap.helper.ts từ NestJS project — giữ nguyên logic, chỉ bỏ TypeScript type annotations để chạy trong Node.js không cần compile:
// File: compare/algos/bitmask.js
function weekdaysToBitmask(weekdays) {
if (!weekdays || weekdays.length === 0) return 0b1111111;
return weekdays.reduce((mask, day) => mask | (1 << (day - 1)), 0);
}
function toEpochDay(dateStr) {
// Howard Hinnant's proleptic Gregorian algorithm — thuần integer, không new Date()
const [y, m, d] = dateStr.split('-').map(Number);
const era = Math.floor((m <= 2 ? y - 1 : y) / 400);
// ...
}
function checkHasOverlap(ranges) {
const dateCount = new Map();
for (const range of ranges) {
const mask = weekdaysToBitmask(range.weekdays);
for (let d = startEpoch; d <= endEpoch; d++) {
if (mask & (1 << epochDayToDow(d))) {
const count = (dateCount.get(d) ?? 0) + 1;
if (count > 1) return fromEpochDay(d); // early return
dateCount.set(d, count);
}
}
}
return null;
}
function checkTwoRangesOverlap(a, b) {
// Quick reject: date range không chồng
if (toEpochDay(a.endDate) < toEpochDay(b.startDate)) return null;
if (toEpochDay(b.endDate) < toEpochDay(a.startDate)) return null;
// Bitmask AND: weekday không chung
const combinedMask = weekdaysToBitmask(a.weekdays) & weekdaysToBitmask(b.weekdays);
if (combinedMask === 0) return null;
// Enumerate chỉ vùng giao
// ...
}
Correctness check trong bench.js
Trước khi đo bất kỳ metric nào, bench.js chạy một vòng correctness check — đảm bảo tất cả algorithms cho kết quả nhất quán nhau:
// bench.js — correctness verification
function runCorrectnessChecks() {
console.log('Running correctness checks...');
for (const s of SCENARIOS) {
const gcdRanges = buildGcdRanges(s);
const bitmaskRanges = buildBitmaskRanges(s);
const gcdResult = gcd.checkHasOverlap(gcdRanges);
const bitmaskResult = bitmask.checkHasOverlap(bitmaskRanges);
const twoResult = bitmask.checkTwoRangesOverlap(
bitmaskRanges[0], bitmaskRanges[1]
);
// Tất cả phải đồng ý: có overlap hay không
const hasOverlapGcd = !!gcdResult;
const hasOverlapBitmask = bitmaskResult !== null;
if (hasOverlapGcd !== hasOverlapBitmask) {
console.error(`[CORRECTNESS FAIL] ${s.label}: gcd=${hasOverlapGcd}, bitmask=${hasOverlapBitmask}`);
process.exit(1);
}
}
console.log('All correctness checks passed.\n');
}
Kết quả lần chạy cuối cùng: All correctness checks passed. — tất cả 11 scenarios × 4 algorithms đồng ý với nhau 100%.
Phần 5: Kết Quả — Số Biết Nói
Giải thích các label trong bảng:
gcd-memory: Sub-approach 2 của GCD — in-memory date enumeration với plain{}hashmap (code ở Phần 3 trên).bitmask-multi: hàmcheckHasOverlap(ranges[])của bitmask — nhận nhiều ranges, dùngMap<epochDay, count>để detect (chi tiết Phần 6).bitmask-two: hàmcheckTwoRangesOverlap(a, b)của bitmask — check đúng 2 ranges, có quick-reject O(1) bằngmaskA & maskB === 0(chi tiết Phần 6).uint8-prealloc: cải tiến của bitmask-multi, thay Map bằng Uint8Array pre-allocated (chi tiết Phần 7).
Bảng 1: Wall Time (ms per call) — tất cả 11 scenarios
Dữ liệu từ benchmark chạy với
--expose-gc(GC isolation). Tất cả correctness checks đã pass trước khi đo.
scenario algo iters min(ms) avg(ms) p95(ms) p99(ms)
─────────────────────────────────────────────────────────────────────────────────────────────
tiny-nofilter gcd-memory 2000 0.0531 0.0687 0.1016 0.2258
tiny-nofilter bitmask-multi 2000 0.0059 0.0077 0.0083 0.0248
tiny-nofilter bitmask-two 2000 0.0006 0.0010 0.0017 0.0027
tiny-nofilter uint8-prealloc 2000 0.0080 0.0102 0.0105 0.0157
tiny-overlap gcd-memory 2000 0.0504 0.0630 0.0802 0.2070
tiny-overlap bitmask-multi 2000 0.0058 0.0074 0.0076 0.0129
tiny-overlap bitmask-two 2000 0.0005 0.0007 0.0007 0.0021
tiny-overlap uint8-prealloc 2000 0.0084 0.0114 0.0151 0.0439
small-nofilter gcd-memory 1000 4.3744 5.3316 6.6942 7.5352
small-nofilter bitmask-multi 1000 0.0609 0.0804 0.1255 0.2717
small-nofilter bitmask-two 1000 0.0005 0.0007 0.0007 0.0009
small-nofilter uint8-prealloc 1000 0.0431 0.0535 0.0582 0.1425
small-overlap gcd-memory 1000 4.3846 5.2116 6.3432 7.2243
small-overlap bitmask-multi 1000 0.0644 0.0816 0.1171 0.3144
small-overlap bitmask-two 1000 0.0005 0.0008 0.0016 0.0038
small-overlap uint8-prealloc 1000 0.0430 0.0549 0.0703 0.1222
medium-nofilter gcd-memory 500 18.2387 20.4912 23.1606 25.2895
medium-nofilter bitmask-multi 500 0.1393 0.1837 0.2904 0.5048
medium-nofilter bitmask-two 500 0.0005 0.0006 0.0007 0.0008
medium-nofilter uint8-prealloc 500 0.0820 0.1087 0.1327 0.1863
medium-overlap gcd-memory 500 18.1113 20.6619 23.0462 24.7042
medium-overlap bitmask-multi 500 0.1395 0.1790 0.2911 0.5104
medium-overlap bitmask-two 500 0.0005 0.0006 0.0007 0.0007
medium-overlap uint8-prealloc 500 0.0832 0.1099 0.1500 0.2845
medium-filtered gcd-memory 500 7.2455 8.8718 10.5517 11.5796
medium-filtered bitmask-multi 500 0.0815 0.1047 0.1413 0.3068
medium-filtered bitmask-two 500 0.0005 0.0008 0.0007 0.0013
medium-filtered uint8-prealloc 500 0.0818 0.1085 0.1390 0.1823
large-nofilter gcd-memory 50 614.0863 640.6498 673.0568 694.9075
large-nofilter bitmask-multi 50 1.6479 2.1292 3.6472 4.0812
large-nofilter bitmask-two 50 0.0005 0.0008 0.0009 0.0133
large-nofilter uint8-prealloc 50 0.3335 0.4246 0.5418 0.8206
large-filtered gcd-memory 50 233.9158 248.8635 263.1342 285.5654
large-filtered bitmask-multi 50 0.7739 1.0038 1.5350 3.2730
large-filtered bitmask-two 50 0.0006 0.0008 0.0007 0.0114
large-filtered uint8-prealloc 50 0.2819 0.3566 0.4328 0.4564
worst-case gcd-memory 20 261.9527 271.7717 288.2922 291.3957
worst-case bitmask-multi 20 1.4704 1.7779 3.8166 4.0018
worst-case bitmask-two 20 0.0005 0.0014 0.0016 0.0148
worst-case uint8-prealloc 20 0.2213 0.2623 0.3470 0.3487
worst-overlap gcd-memory 20 257.6225 270.5480 282.1005 283.3465
worst-overlap bitmask-multi 20 1.3632 1.7532 2.6039 3.8955
worst-overlap bitmask-two 20 0.0006 0.0016 0.0010 0.0208
worst-overlap uint8-prealloc 20 0.1939 0.3012 0.3995 0.4774
─────────────────────────────────────────────────────────────────────────────────────────────
Biểu đồ 1: Speedup — bitmask-multi và uint8-prealloc so với gcd-memory
Speedup (gcd-memory wall-avg / algo wall-avg)
bitmask-multi uint8-prealloc
tiny-nofilter 8.9x 6.7x
tiny-overlap 8.5x 5.5x
small-nofilter 66.3x 99.7x
small-overlap 63.9x 94.9x
medium-nofilter 111.6x 188.5x
medium-overlap 115.4x 187.9x
medium-filtered 84.7x 81.8x
large-nofilter 300.9x 1508.9x ← uint8 wins big here
large-filtered 247.9x 697.9x
worst-case 152.9x 1035.6x
worst-overlap 154.3x 898.1x
Ghi chú: bitmask-two không so ở đây vì nó check 2 ranges, không phải N ranges.
Bảng 2: CPU Usage (avg µs per call) — tất cả 11 scenarios
scenario algo cpu-user(µs) cpu-sys(µs)
───────────────────────────────────────────────────────────────────────
tiny-nofilter gcd-memory 64 7
tiny-nofilter bitmask-multi 9 2
tiny-nofilter bitmask-two 3 2
tiny-nofilter uint8-prealloc 11 3
tiny-overlap gcd-memory 56 9
tiny-overlap bitmask-multi 8 3
tiny-overlap bitmask-two 4 1
tiny-overlap uint8-prealloc 12 3
small-nofilter gcd-memory 5,070 38
small-nofilter bitmask-multi 79 3
small-nofilter bitmask-two 3 1
small-nofilter uint8-prealloc 49 7
small-overlap gcd-memory 4,944 46
small-overlap bitmask-multi 83 0
small-overlap bitmask-two 3 2
small-overlap uint8-prealloc 54 3
medium-nofilter gcd-memory 19,429 207
medium-nofilter bitmask-multi 170 14
medium-nofilter bitmask-two 3 2
medium-nofilter uint8-prealloc 101 7
medium-overlap gcd-memory 19,637 167
medium-overlap bitmask-multi 175 0
medium-overlap bitmask-two 4 0
medium-overlap uint8-prealloc 104 7
medium-filtered gcd-memory 8,447 45
medium-filtered bitmask-multi 91 15
medium-filtered bitmask-two 5 0
medium-filtered uint8-prealloc 103 7
large-nofilter gcd-memory 589,761 26,896
large-nofilter bitmask-multi 1,364 749 ← sys còn cao
large-nofilter bitmask-two 4 0
large-nofilter uint8-prealloc 423 1 ← sys ≈ 0
large-filtered gcd-memory 237,163 1,066
large-filtered bitmask-multi 620 381
large-filtered bitmask-two 4 0
large-filtered uint8-prealloc 359 0 ← sys = 0
worst-case gcd-memory 257,455 4,039
worst-case bitmask-multi 866 909
worst-case bitmask-two 88 2
worst-case uint8-prealloc 293 0 ← sys = 0
worst-overlap gcd-memory 256,076 4,167
worst-overlap bitmask-multi 1,021 760
worst-overlap bitmask-two 6 0
worst-overlap uint8-prealloc 324 4
───────────────────────────────────────────────────────────────────────
cpu-sys là kernel calls — số này lên cao khi allocator phải xin thêm memory từ OS hoặc GC phải trả memory về. uint8-prealloc về 0 ở mọi large scenario vì một lần alloc duy nhất, không resize.
Bảng 3: Memory Pressure (avg KB delta per call) — tất cả 11 scenarios
scenario algo heap-avg(KB) rss-avg(KB)
──────────────────────────────────────────────────────────────────────
tiny-nofilter gcd-memory 0.8 0.0
tiny-nofilter bitmask-multi -0.3 0.0 ← GC ran
tiny-nofilter bitmask-two 0.4 0.0
tiny-nofilter uint8-prealloc 0.6 0.1
tiny-overlap gcd-memory 0.2 0.0
tiny-overlap bitmask-multi 0.2 0.1
tiny-overlap bitmask-two 0.4 0.0
tiny-overlap uint8-prealloc 0.7 0.0
small-nofilter gcd-memory 4.1 8.2
small-nofilter bitmask-multi 6.6 0.0
small-nofilter bitmask-two 0.4 0.0
small-nofilter uint8-prealloc 5.8 0.0
small-overlap gcd-memory 15.4 15.9
small-overlap bitmask-multi 6.7 0.0
small-overlap bitmask-two 0.4 0.0
small-overlap uint8-prealloc 5.8 0.5
medium-nofilter gcd-memory 19.2 14.9
medium-nofilter bitmask-multi 20.9 -0.8 ← GC ran
medium-nofilter bitmask-two 0.4 0.0
medium-nofilter uint8-prealloc 11.0 0.0
medium-overlap gcd-memory 19.2 14.6
medium-overlap bitmask-multi 20.9 0.0
medium-overlap bitmask-two 0.4 0.0
medium-overlap uint8-prealloc 11.1 0.0
medium-filtered gcd-memory 20.0 0.0
medium-filtered bitmask-multi 6.6 0.0
medium-filtered bitmask-two 0.4 0.3
medium-filtered uint8-prealloc 11.2 0.0
large-nofilter gcd-memory 450.1 443.5
large-nofilter bitmask-multi 605.2 411.7
large-nofilter bitmask-two 5.4 0.0
large-nofilter uint8-prealloc 134.1 5.1 ← 4.5x nhẹ hơn
large-filtered gcd-memory 345.5 271.1
large-filtered bitmask-multi 80.9 32.3
large-filtered bitmask-two 1.4 0.0
large-filtered uint8-prealloc 130.1 0.0
worst-case gcd-memory 1,312.7 1,263.8
worst-case bitmask-multi 1,139.7 -448.4 ← GC ran
worst-case bitmask-two 0.8 -45.2
worst-case uint8-prealloc 86.6 0.0 ← 13.2x nhẹ hơn
worst-overlap gcd-memory 1,319.3 1,242.8
worst-overlap bitmask-multi 1,139.4 700.0
worst-overlap bitmask-two 0.5 0.0
worst-overlap uint8-prealloc 86.4 0.0 ← 13.2x nhẹ hơn
──────────────────────────────────────────────────────────────────────
Nhận xét quan trọng về memory:
- Scale nhỏ (tiny/small): tất cả đều nhẹ, khác biệt không đáng kể.
- Scale trung bình:
uint8-prealloc(11 KB) bắt đầu nhẹ hơnbitmask-multi(20 KB) — do không dùng Map. - Scale lớn (
large-nofilter): bitmask-multi (605 KB) nặng hơn cả gcd-memory (450 KB). Đây là điều bất ngờ: Map overhead lớn hơn cả plain JS object{}của GCD. uint8-preallocluôn nhẹ nhất ở large/worst-case (134 KB và 86 KB).bitmask-twovô địch về memory mọi scenario (0.4-5.4 KB) — vì khimaskA & maskB === 0nó return ngay không allocate gì.
Nhưng Tên bitmask-multi Có Phần Gây Hiểu Lầm
Nhìn kỹ lại code của bitmask-multi, có một điều đáng chú ý:
function checkHasOverlap(ranges) {
const dateCount = new Map(); // ← đây là Map, không phải bitmask
for (const range of ranges) {
const mask = weekdaysToBitmask(range.weekdays); // ← bitmask dùng ở đây
for (let d = startEpoch; d <= endEpoch; d++) {
if (mask & (1 << epochDayToDow(d))) { // ← filter ngày bằng bitmask
const count = (dateCount.get(d) ?? 0) + 1;
if (count > 1) return fromEpochDay(d);
dateCount.set(d, count); // ← nhưng detect overlap bằng Map
}
}
}
return null;
}
Bitmask ở đây chỉ làm nhiệm vụ filter ngày trong khi enumerate — quyết định ngày nào cần đếm. Việc detect overlap thực sự vẫn do Map<epochDay, count> đảm nhận. Tên chính xác hơn phải là epoch-hashmap — dùng epoch day integer thay vì date string làm key, giúp hash nhanh hơn, nhưng bản chất vẫn là hashmap.
Điều này cũng giải thích tại sao bitmask-multi có memory tương đương hoặc cao hơn GCD ở scale lớn (605 KB vs 449 KB tại large-nofilter) — không phải lỗi của bitmask, mà là chi phí của Map.
V8 Map đắt hơn vẻ ngoài:
| Entry count | V8 làm gì |
|---|---|
| 1-8 | Allocate bucket 8 slot đầu tiên |
| 9 | Resize → 16 slot, copy toàn bộ + rehash |
| 17 | Resize → 32 slot, lại copy + rehash |
| … | Cứ x2 khi đầy 75% capacity |
| ~27.000 entries (300×90 ngày) | Đã qua khoảng 12 lần resize |
Mỗi lần resize: allocate array mới, copy toàn bộ, free array cũ → GC phải dọn. Thêm nữa, Map dùng pointer-based hash table nên access không tuần tự trên memory → cache miss nhiều. Đây là lý do cpu-sys của bitmask-multi không về 0 ở scale lớn, và là lý do phân tích ở Phần 7 tiếp theo.
Phần 6: Giải Pháp Mới — Bitmask 7-bit Đơn Giản Mà Hiệu Quả
Phiên bản mới của hệ thống (viết lại bằng TypeScript, NestJS) giải quyết bài toán weekday overlap bằng bitmask — đơn giản hơn nhiều, và không phụ thuộc gì vào DB custom function.
Ý tưởng cơ bản
Mỗi ngày trong tuần = 1 bit trong một số nguyên 7-bit:
bit6 bit5 bit4 bit3 bit2 bit1 bit0
Sat Fri Thu Wed Tue Mon Sun
7 6 5 4 3 2 1 ← weekday (legacy: 1=Sun)
Nên:
[Mon, Wed, Fri]=0b0101010= 42[Tue, Thu, Sat]=0b1001010= 74[Mon, Tue]=0b0000110= 6
Code — Chuyển weekdays thành bitmask
function weekdaysToBitmask(weekdays: number[] | null | undefined): number {
if (!weekdays || weekdays.length === 0) return 0b1111111; // tất cả ngày = 127
// weekday 1=Sun → bit0, weekday 7=Sat → bit6
// day=1 → (1-1)=0 → 1<<0 = 0b0000001 (bit vị trí 0)
// day=7 → (7-1)=6 → 1<<6 = 0b1000000 (bit vị trí 6)
return weekdays.reduce((mask, day) => mask | (1 << (day - 1)), 0);
}
// Layout 7 bit (bit6=Sat, bit5=Fri, ..., bit0=Sun):
// bit6 bit5 bit4 bit3 bit2 bit1 bit0
// Sat Fri Thu Wed Tue Mon Sun
//
// weekdaysToBitmask([1, 7]) = bit0 | bit6 = 0b1000001 = 65 (Sun + Sat)
// weekdaysToBitmask([2,3,4]) = bit1|bit2|bit3 = 0b0001110 = 14 (Mon-Wed)
// weekdaysToBitmask([1, 7]) → 0b1000001 = 65 (Sun + Sat)
// weekdaysToBitmask(null) → 0b1111111 = 127 (mọi ngày)
Code — Date arithmetic không dùng moment
Trước khi xem code, cần hiểu khái niệm epoch day — xuyên suốt toàn bộ implementation bitmask:
Epoch day = số nguyên đếm số ngày kể từ 1970-01-01 (UTC). Ví dụ:
2024-01-01 = 19723,2024-01-02 = 19724. Thay vì làm việc với string"2024-01-15", chúng ta convert một lần sang integer rồi làm toán thuần integer:
- “Ngày kế tiếp” =
d + 1(không cần parse)- “Cách nhau bao ngày” =
e - s(phép trừ đơn giản)- Dùng làm key của Map/array: integer hash nhanh hơn string hash nhiều lần
Thay vì dùng moment (floating point, timezone mess), dùng Howard Hinnant’s proleptic Gregorian algorithm — thuần integer:
function toEpochDay(dateStr: string): number {
const [y, m, d] = dateStr.split('-').map(Number);
// Howard Hinnant civil_from_days algorithm
const era = Math.floor((m <= 2 ? y - 1 : y) / 400);
const yoe = (m <= 2 ? y - 1 : y) - era * 400;
const doy = Math.floor((153 * (m > 2 ? m - 3 : m + 9) + 2) / 5) + d - 1;
const doe = yoe * 365 + Math.floor(yoe / 4) - Math.floor(yoe / 100) + doy;
return era * 146097 + doe - 719468;
}
function epochDayToDow(epochDay: number): number {
// 1970-01-01 là Thursday = 4
return ((epochDay % 7) + 7 + 4) % 7; // 0=Sun, 1=Mon, ..., 6=Sat
}
Không có new Date(), không có moment(), không có float — chỉ là integer arithmetic.
Code — Check overlap chính
function checkTwoRangesOverlap(a: DateRange, b: DateRange): string | null {
// Bước 1: Quick reject — date range không chồng nhau
if (toEpochDay(a.endDate) < toEpochDay(b.startDate)) return null;
if (toEpochDay(b.endDate) < toEpochDay(a.startDate)) return null;
// Bước 2: Kiểm tra weekday có chung không (bitwise AND — O(1))
const maskA = weekdaysToBitmask(a.weekdays);
const maskB = weekdaysToBitmask(b.weekdays);
const combinedMask = maskA & maskB;
if (combinedMask === 0) return null; // không có ngày chung
// Bước 3: Tìm ngày đầu tiên trong vùng giao nhau
const overlapStart = Math.max(toEpochDay(a.startDate), toEpochDay(b.startDate));
const overlapEnd = Math.min(toEpochDay(a.endDate), toEpochDay(b.endDate));
// Chỉ enumerate trong vùng giao — không enumerate toàn bộ range
for (let d = overlapStart; d <= overlapEnd; d++) {
const dow = epochDayToDow(d); // 0=Sun ... 6=Sat
if (combinedMask & (1 << dow)) return fromEpochDay(d);
}
return null;
}
Với logic maskA & maskB:
weekdays A = [2, 4, 6] → maskA = 0b0101010 = 42
weekdays B = [4, 5, 6] → maskB = 0b1011000 = 88
maskA & maskB = 0b0001000 = 8 ← bit3 = thứ 4
→ có ngày chung, enumerate để tìm ngày đầu tiên
weekdays A = [2, 4, 6] → maskA = 0b0101010 = 42
weekdays C = [3, 5, 7] → maskC = 0b1010100 = 84
maskA & maskC = 0b0000000 = 0
→ không có ngày chung → return null ngay, không enumerate gì cả
Ưu điểm của approach Bitmask
1. Đơn giản và đọc được ngay
maskA & maskB === 0 → “hai tập weekday này không có phần tử chung” — ai cũng hiểu, kể cả người mới.
2. Không phụ thuộc custom DB function
Không cần fn_gcd(), không cần lo DB migration có define hay không. Toàn bộ logic nằm trong application code, kiểm soát được 100%.
3. Bounded integer nhỏ
Bitmask weekday tối đa là 0b1111111 = 127. Luôn nằm trong 1 byte. Dễ lưu, dễ index, dễ debug.
4. Dễ test — unit test thuần túy, không cần DB
expect(weekdaysToBitmask([1, 7])).toBe(0b1000001); // Sun + Sat = 65
expect(weekdaysToBitmask(null)).toBe(127); // tất cả ngày
expect(checkTwoRangesOverlap(
{ startDate: '2024-01-01', endDate: '2024-01-31', weekdays: [2,3,4] },
{ startDate: '2024-01-01', endDate: '2024-01-31', weekdays: [5,6,7] }
)).toBeNull(); // không ngày chung
5. checkTwoRangesOverlap cực kỳ nhẹ với quick-reject
Như bảng memory cho thấy: chỉ 5-9 KB/call ngay cả ở worst-case, vì khi combinedMask === 0 nó return ngay mà không allocate array gì cả.
Nhược điểm của approach Bitmask
1. Vẫn phải duyệt từng ngày trong vùng giao nhau
Sau khi bitmask AND xác định có weekday chung, vẫn phải enumerate để tìm ngày cụ thể. Với khoảng dài 5 năm, đây là O(n) theo số ngày. Về mặt algorithmic, không khác gì cách cũ.
2. Không push logic xuống DB
GCD approach cho phép MySQL làm hết việc overlap check trong query. Bitmask approach hiện tại check trên app, có nghĩa là phải fetch data về trước rồi mới validate — với dataset lớn có thể là bottle-neck.
3. bitmask-multi vs GCD ở scale lớn — heap gần tương đương
Bảng memory cho thấy ở large-nofilter, bitmask-multi thậm chí còn tốn heap nhiều hơn GCD (605 vs 449 KB) vì Map<number, number> có overhead lớn hơn plain {}. Winner thực sự về memory là bitmask-two — nhưng nó chỉ check 2 ranges tại một thời điểm.
Phần 7: Giải Pháp Thứ Ba — Uint8Array Pre-allocated
Sau khi phân tích ở trên, vấn đề rõ ràng: cả GCD in-memory lẫn bitmask-multi đều có một kẻ thù giống nhau ở scale lớn — chi phí của dynamic hashmap. GCD dùng plain {} object, bitmask-multi dùng Map, nhưng cả hai đều phải grow dynamically theo số lượng entry.
Câu hỏi đặt ra: chúng ta có thể biết trước kích thước cần thiết không?
Câu trả lời là: có. Vì tất cả ranges đã được biết trước (đây là batch validation, không phải streaming), chúng ta có thể quét qua một lần để tìm minEpoch và maxEpoch, rồi allocate một array có kích thước chính xác trước khi bắt đầu đếm.
Ý Tưởng Cốt Lõi
Thay vì Map<epochDay, count> — phải hash, phải resize, cache miss tùy tiện — dùng Uint8Array được index bởi (epochDay - minEpoch):
epochDay → index = epochDay - minEpoch
counter[index]++ thay vì dateCount.set(d, count)
Truy cập mảng trực tiếp: base_addr + offset * 1 byte — một phép cộng nguyên. Không hash, không probe, không resize.
Thuật Toán Hai Lần Duyệt
function checkHasOverlapPrealloc(ranges) {
if (ranges.length === 0) return null;
// Pass 1: tìm epoch day bounds — chỉ so sánh integer, không alloc gì
let minEpoch = Infinity, maxEpoch = -Infinity;
for (const r of ranges) {
const s = toEpochDay(r.startDate);
const e = toEpochDay(r.endDate);
if (s < minEpoch) minEpoch = s;
if (e > maxEpoch) maxEpoch = e;
}
// Một lần allocate duy nhất — kích thước chính xác, zero-initialized theo spec
// Uint8Array: 1 byte/entry, không có object header, không có hash bucket
const counter = new Uint8Array(maxEpoch - minEpoch + 1);
// Pass 2: y hệt bitmask-multi, nhưng direct index thay vì Map.get/set
for (const range of ranges) {
const s = toEpochDay(range.startDate);
const e = toEpochDay(range.endDate);
const mask = weekdaysToBitmask(range.weekdays);
for (let d = s; d <= e; d++) {
if (mask & (1 << epochDayToDow(d))) {
if (++counter[d - minEpoch] > 1) return fromEpochDay(d); // early exit
}
}
}
return null;
}
Chi phí Pass 1 rất nhỏ: chỉ duyệt qua ranges.length lần (không phải ngày), không alloc gì. Chi phí phụ thêm so với bitmask-multi: chỉ là một lần duyệt O(n ranges) và một new Uint8Array(span).
Benchmark Đầy Đủ — 4 Thuật Toán
Dữ liệu dưới đây là từ cùng một lần chạy benchmark với Phần 5 —
--expose-gc, tất cả correctness checks pass. Phần 5 hiển thị đầy đủ 11 scenarios; bảng dưới đây tập trung vào 5 scenarios đại diện nhất để so sánh dễ nhìn hơn.
Dưới đây là kết quả từ lần chạy benchmark (với GC isolation --expose-gc):
Wall Time (ms per call):
scenario algo iters min(ms) avg(ms) p95(ms) p99(ms)
────────────────────────────────────────────────────────────────────────────────────────────
tiny-nofilter gcd-memory 2000 0.0531 0.0687 0.1016 0.2258
tiny-nofilter bitmask-multi 2000 0.0059 0.0077 0.0083 0.0248
tiny-nofilter uint8-prealloc 2000 0.0080 0.0102 0.0105 0.0157
tiny-nofilter bitmask-two 2000 0.0006 0.0010 0.0017 0.0027
small-nofilter gcd-memory 1000 4.3744 5.3316 6.6942 7.5352
small-nofilter bitmask-multi 1000 0.0609 0.0804 0.1255 0.2717
small-nofilter uint8-prealloc 1000 0.0431 0.0535 0.0582 0.1425
small-nofilter bitmask-two 1000 0.0005 0.0007 0.0007 0.0009
medium-nofilter gcd-memory 500 18.2387 20.4912 23.1606 25.2895
medium-nofilter bitmask-multi 500 0.1393 0.1837 0.2904 0.5048
medium-nofilter uint8-prealloc 500 0.0820 0.1087 0.1327 0.1863
medium-nofilter bitmask-two 500 0.0005 0.0006 0.0007 0.0008
large-nofilter gcd-memory 50 614.0863 640.6498 673.0568 694.9075
large-nofilter bitmask-multi 50 1.6479 2.1292 3.6472 4.0812
large-nofilter uint8-prealloc 50 0.3335 0.4246 0.5418 0.8206
large-nofilter bitmask-two 50 0.0005 0.0008 0.0009 0.0133
worst-case gcd-memory 20 261.9527 271.7717 288.2922 291.3957
worst-case bitmask-multi 20 1.4704 1.7779 3.8166 4.0018
worst-case uint8-prealloc 20 0.2213 0.2623 0.3470 0.3487
worst-case bitmask-two 20 0.0005 0.0014 0.0016 0.0148
────────────────────────────────────────────────────────────────────────────────────────────
CPU User Time (avg µs per call):
scenario algo cpu-user(µs) cpu-sys(µs)
────────────────────────────────────────────────────────────────────
tiny-nofilter gcd-memory 64 7
tiny-nofilter bitmask-multi 9 2
tiny-nofilter uint8-prealloc 11 3
small-nofilter gcd-memory 5,070 38
small-nofilter bitmask-multi 79 3
small-nofilter uint8-prealloc 49 7 ← cpu-sys ≈ 0
medium-nofilter gcd-memory 19,429 207
medium-nofilter bitmask-multi 170 14
medium-nofilter uint8-prealloc 101 7
large-nofilter gcd-memory 589,761 26,896
large-nofilter bitmask-multi 1,364 749 ← sys còn cao
large-nofilter uint8-prealloc 423 1 ← sys ≈ 0
worst-case gcd-memory 257,455 4,039
worst-case bitmask-multi 866 909
worst-case uint8-prealloc 293 0 ← sys = 0
────────────────────────────────────────────────────────────────────
Dấu hiệu rõ ràng nhất: cpu-sys của uint8-prealloc về 0 ở mọi scenario lớn. Không còn syscall nào từ allocator — vì không còn lần resize nào nữa.
Memory (avg heap delta per call):
scenario algo heap-avg(KB) rss-avg(KB)
────────────────────────────────────────────────────────────────────
medium-nofilter gcd-memory 19.2 14.9
medium-nofilter bitmask-multi 20.9 -0.8 ← GC ran
medium-nofilter uint8-prealloc 11.0 0.0 ← 1.9x nhẹ hơn
large-nofilter gcd-memory 450.1 443.5
large-nofilter bitmask-multi 605.2 411.7 ← nặng hơn GCD!
large-nofilter uint8-prealloc 134.1 5.1 ← 4.5x nhẹ hơn
worst-case gcd-memory 1,312.7 1,263.8
worst-case bitmask-multi 1,139.7 -448.4 ← GC ran
worst-case uint8-prealloc 86.6 0.0 ← 13.2x nhẹ hơn
────────────────────────────────────────────────────────────────────
Tại worst-case (200 ranges × 90 ngày): uint8-prealloc dùng 86 KB heap trong khi bitmask-multi dùng 1139 KB — 13 lần ít hơn.
Lý do rất cụ thể:
Map (bitmask-multi): 200 ranges × 90 ngày × 7/7 weekdays = khoảng 18.000 epoch-day entries trong Map. Mỗi entry của V8 Map tốn khoảng 60-70 bytes (8 bytes key SmallInt + 8 bytes value + hash bucket pointer + metadata). Tổng: ~18.000 × 65 bytes ≈ 1.17 MB — khớp với con số 1139 KB đo được.
Uint8Array (uint8-prealloc): Kích thước array = maxEpochDay - minEpochDay + 1 — tức là span từ ngày sớm nhất đến ngày muộn nhất trong toàn bộ 200 ranges. Worst-case benchmark tạo ranges ngẫu nhiên trong vài tháng, span điển hình là 100-400 ngày. Uint8Array 400 ngày = 400 bytes. Cộng với overhead của array ranges input và các small allocations = ~86 KB tổng. Không có resize chain nào.
Điểm mấu chốt: Uint8Array cost là O(span) — chỉ phụ thuộc vào khoảng thời gian bao phủ, không phụ thuộc vào số ranges hay số ngày được đếm. Map cost là O(n × d) — mỗi ngày được visit là một entry mới.
Speedup Summary
Speedup của uint8-prealloc so với bitmask-multi (wall-avg):
tiny-nofilter : 0.76x ← chậm hơn (Pass 1 overhead > saving ở dataset nhỏ)
tiny-overlap : 0.65x ← tương tự
small-nofilter : 1.50x ██
small-overlap : 1.49x ██
medium-nofilter : 1.69x ███
medium-overlap : 1.63x ███
medium-filtered : 0.97x ← gần bằng (weekday filter làm cả hai nhanh hơn)
large-nofilter : 5.01x █████
large-filtered : 2.81x ███
worst-case : 6.78x ███████
worst-overlap : 5.82x ██████
Nhỏ (tiny): uint8 chậm hơn một chút vì Pass 1 + allocate array có overhead cố định, trong khi dataset quá nhỏ để bù lại. Đây là điểm trade-off rõ ràng: prealloc phù hợp với medium-to-large input, không phải cho 10 records.
Lớn (large, worst): uint8 nhanh hơn 6x — hoàn toàn là lợi ích từ việc loại bỏ hashmap overhead.
Ưu Điểm
1. Loại bỏ toàn bộ chi phí của Map — không hash, không resize, không cache miss từ pointer chasing.
2. Memory thấp hơn đáng kể — 1 byte/entry thay vì ~50-60 bytes/entry của Map (header + hash bucket + key + value). Ở worst-case: 86 KB vs 1139 KB.
3. CPU-sys về 0 — không còn syscall từ allocator, không còn GC pressure từ resize.
4. Locality tốt — Uint8Array là một vùng nhớ liên tục, CPU prefetcher load trước được. Map là pointer-based, access tùy tiện trên heap.
Nhược Điểm
1. Cần biết trước toàn bộ ranges — phải có batch input. Không áp dụng được cho streaming (thêm range từng cái một) vì không có min/maxEpoch để pre-allocate.
2. Chậm hơn bitmask-multi ở input rất nhỏ — khi n × span nhỏ hơn khoảng 200 entries, overhead của Pass 1 lớn hơn lợi ích. Threshold thực tế: khoảng 30-50 ranges × 7-31 ngày trở lên thì mới có lợi.
3. Vẫn O(n × d) về time complexity — không khác về asymptotic, chỉ constant factor nhỏ hơn rất nhiều.
Phần 8: Kiến Thức Đại Học Ứng Dụng — Hồi Đó Tôi Tưởng Chỉ Để Thi Rớt Cho Vui
Môn Toán Rời Rạc / Lý Thuyết Số
Cách cũ dùng Định lý phân tích nhân tử nguyên tố (Fundamental Theorem of Arithmetic): mọi số nguyên dương có duy nhất một phân tích nhân tử nguyên tố. Vì vậy, tích của các số nguyên tố phân biệt sẽ chia sẻ ước chung > 1 khi và chỉ khi chúng có chung ít nhất một thừa số nguyên tố.
Đây chính xác là thứ thấy ở môn Toán rời rạc / Cơ sở Toán tin học năm 2 đại học. Hồi đó học xong thì thấy “có biến này để làm gì?”. Bây giờ biết rồi — để check weekday overlap trong pricing engine của khách sạn.
Môn Lập Trình Hệ Thống / Kiến Trúc Máy Tính
Bitmask là kỹ thuật cơ bản nhất của lập trình hệ thống. Bit shift (<<), bitwise AND (&), bitwise OR (|) — tất cả những thứ này học từ năm 1 trong môn Nhập môn lập trình hoặc Kiến trúc máy tính.
Ý tưởng dùng 7 bit để biểu diễn 7 ngày trong tuần là một ví dụ textbook của bit flags / bitmask pattern. Học xong rồi quên, đến khi gặp bài toán “check xem hai tập hợp nhỏ có phần tử chung không” thì mở não trắng… trong khi a & b != 0 là xong.
Môn Phân Tích Và Đánh Giá Giải Thuật
Benchmark này áp dụng đúng quy trình đánh giá giải thuật được dạy trong môn Algorithms:
- Chọn input đại diện: từ nhỏ đến lớn, có overlap và không có overlap
- Đo trường hợp tệ nhất (no-overlap = phải quét hết):
worst-case - Phân biệt wall time và CPU time: loại bỏ OS scheduling noise
- Đo memory: space complexity không kém time complexity
- Dùng p95/p99 thay vì chỉ avg: tail latency quan trọng hơn average với production systems
Môn Kiến Trúc Máy Tính — TypedArray và Locality of Reference
Uint8Array là một TypedArray trong JavaScript — một vùng nhớ liên tục (contiguous block), không phải object heap phân tán. Đây là khái niệm xuất hiện ngay trong môn Kiến trúc máy tính khi học về cache hierarchy:
- Spatial locality: nếu bạn access
counter[i], CPU sẽ prefetchcounter[i+1],counter[i+2]… vào L1 cache. Lần enumerate kế tiếp đã có sẵn trong cache. - No pointer chasing: Map là linked-node structure — mỗi get/set phải đi theo pointer từ bucket → node → value, nhảy tùy tiện trên heap. Uint8Array thì không có pointer, chỉ có
base + offset.
Hồi học Kiến trúc máy tính, bài giảng về cache line, cache miss luôn nghe rất abstract. Đến khi thấy cpu-sys của bitmask-multi là 838 µs/call còn uint8-prealloc là 0 ở cùng scenario, thì mới hiểu tại sao thầy nói “memory access pattern là thứ quyết định performance thực tế.”
Phần 9: Bài Học Rút Ra
- Không có cách nào “sai” khi nó hoạt động đúng. GCD và bitmask đều giải quyết bài toán, chỉ khác nhau ở chỗ: một cái elegant về toán học, một cái rõ ràng về engineering.
- Câu chuyện phụ thuộc là quan trọng nhất. Bitmask thắng vì nó không cần custom MySQL function — một thứ này có thể gây ra bug im lặng rất khó debug nếu deployment thiếu bước setup.
- Đo trước khi kết luận. Wall time thôi là chưa đủ. CPU time cho thấy cost thuần tính toán. Heap delta cho thấy memory pressure. RSS cho thấy tác động thực lên OS. Mỗi metric kể một câu chuyện khác nhau.
bitmask-twomới là winner thực sự về memory. Nhờ quick-reject O(1) với bitmask AND, nó gần như không allocate gì khi không có overlap — thay vì 1.3 MB/call của GCD ở worst-case.- Đặt tên hàm phản ánh đúng cơ chế.
bitmask-multithực ra làepoch-hashmap— bitmask chỉ dùng để filter, còn Map mới là nơi detect overlap. Khi tên không khớp với implementation, người đọc code sẽ hiểu sai cơ chế, và quan trọng hơn, sẽ không biết chỗ nào để tối ưu. - Biết trước kích thước thì pre-allocate. Khi input là batch (không phải streaming), Pass 1 để tính bounds rồi allocate chính xác một lần là pattern rất mạnh. Uint8Array pre-allocated loại bỏ toàn bộ chi phí resize chain của Map — 6x nhanh hơn và 13x ít heap hơn ở worst-case. Kỹ thuật này có trong sách giáo khoa, nhưng bạn chỉ nghĩ đến nó khi đã hiểu tại sao hashmap lại chậm.
- Kỹ thuật cơ bản từ đại học không “vô dụng”. Chúng chỉ nằm yên đó, chờ đến khi bạn gặp đúng bài toán. Vấn đề là phần lớn chúng ta quên mất chúng trước khi có dịp dùng.