Là một lập trình viên yêu công nghệ, thích viết blog để chia sẻ kiến thức, kinh nghiệm lập trình và những điều thú vị trong thế giới tech.
Một đoạn type-pun bằng ép con trỏ cho 1073741824 ở -O0 nhưng 1 ở -O2 — vì -O2 giả định int* và float* không trỏ cùng ô. Đó là hành vi không xác định. Cách đúng là memcpy, và gcc gấp nó thành một lệnh. Đo thật trong container.
O(1) < O(log n), nên hash luôn hơn cây? Tôi đo thử: tra cứu điểm hash nhanh hơn cây đỏ-đen 32 lần (16ns vs 518ns). Nhưng range query — tìm mọi phần tử >= x theo thứ tự — cây làm trong 7,8µs còn hash phải sort lại toàn bộ, 54,2ms. 'Cái nào nhanh hơn' là câu hỏi sai; chọn theo loại truy vấn.
Cây nhị phân và B-tree đều O(log n) — vậy sao mọi cơ sở dữ liệu dùng B-tree? Tôi đo thử: tra cứu 4 triệu khóa, cây nhị phân đi 22 tầng (887ns), B-tree fanout 64 chỉ 4 tầng (153ns) — nhanh 5,8 lần. Mỗi tầng là một lần chạm bộ nhớ (hay một lần đọc đĩa), nên ít tầng thắng. Cùng O(log n), khác cơ số log.
Tưởng chạy một lần trước/sau là đủ biết một tinh chỉnh có tác dụng? Tôi đo thử: cùng một getpid không đổi gì, một phép đo có thể ra 99,8 hoặc 197,9 ns (chênh 2 lần) tùy nhiễu; chỉ min-của-nhiều-lần mới tái lập, và phải cô lập đúng một biến. Đây là nền của mọi con số trong sê-ri.
Tưởng đọc cùng lượng byte thì nhiều file nhỏ hay một file lớn cũng như nhau? Tôi đo thử: 20000 file nhỏ chậm 4 lần một file lớn cùng byte; và 20000 file 4KB với 20000 file 512B (ít hơn 8 lần dữ liệu) tốn ngang nhau — chi phí là per-file, không per-byte.
Phần 4 cho thấy tải cao giết hash table. Nhưng tôi đo tiếp: ngay ở CÙNG tải 0,70, đổi hàm băm tốt sang xấu làm probe trung bình nhảy từ 2,17 lên 358,9 — tra cứu chậm 23 lần. Băm hằng số thì thoái hóa hoàn toàn về O(n). Tải thấp là điều kiện cần, không đủ.