4 tỷ câu lệnh if

4 tỷ câu lệnh if

• Gần đây khi đang lướt mạng xã hội, tôi bắt gặp ảnh chụp màn hình này trên tàu.
• Đoạn mã này là một ví dụ hoàn hảo về đánh đổi thời gian-bộ nhớ.
• Tôi muốn triển khai nó bằng ngôn ngữ C để tăng hiệu năng.

Cấu trúc mã

• Viết mã C để xác định số chẵn và số lẻ.
• Biên dịch với tối ưu hóa bị tắt.
• Chạy đúng với các số từ 0 đến 10, nhưng phát sinh vấn đề với các số lớn hơn.

Meta programming

• Dùng Python để meta programming các câu lệnh if.
• Tạo một chương trình xác định số chẵn và số lẻ cho số nguyên 8 bit.

Mở rộng lên 16 bit

• Mở rộng chương trình theo cùng cách cho số nguyên 16 bit.
• Tạo và biên dịch một tệp C khoảng 130k dòng.

Thử thách 32 bit

• Cố gắng mở rộng chương trình cho số nguyên 32 bit.
• Tạo một tệp C dung lượng 330GB, nhưng trình biên dịch thất bại do thiếu không gian heap.
• Do giới hạn của định dạng Portable Executable, không thể xử lý các tệp lớn hơn 4GB.

Tự viết mã máy

• Tự viết trực tiếp hàm IsEven bằng hợp ngữ x86-64.
• Dùng Python để biên dịch thủ công mã máy.

Tạo tệp thực thi

• Tạo một tệp dung lượng 40GB để xác định số chẵn và số lẻ cho mọi số nguyên 32 bit.
• Ánh xạ tệp vào bộ nhớ và dùng con trỏ hàm để thực thi mã.

Sửa lỗi cuối cùng

• Thay bằng hàm strtoul để giải quyết vấn đề phân tích số nguyên không dấu.
• Chương trình rất nhanh và trả về kết quả trong vòng 10 giây ngay cả với các số lớn.

Ý kiến của GN⁺

• Tầm quan trọng: Bài viết này giúp hiểu rõ khái niệm cơ bản của lập trình là đánh đổi thời gian-bộ nhớ. Đồng thời, đây cũng là một ví dụ tốt cho thấy mã không được tối ưu hóa ảnh hưởng thế nào đến hiệu năng thực tế.
• Điểm thú vị: Quá trình khám phá bằng thực nghiệm sự khác biệt hiệu năng giữa các ngôn ngữ lập trình và giới hạn của trình biên dịch khá thú vị. Đặc biệt, nỗ lực so sánh Python và C để cải thiện hiệu năng rất đáng xem.
• Bài học rút ra: Bài viết cho thấy rằng để giải quyết một vấn đề phức tạp, đôi khi những cách tiếp cận trông có vẻ kém hiệu quả lại có thể thực sự hữu ích. Đồng thời, nó cũng nhấn mạnh tầm quan trọng của việc tìm kiếm các giải pháp sáng tạo trong khoa học máy tính.

[GN⁺]

Ý kiến Hacker News

• Tóm tắt bình luận thứ nhất:

  • Ký ức về chương trình đầu tiên tự viết vào năm 1996, khi 16 tuổi.
  • Sau khi xem phần phụ lục đồ họa máy tính trong một cuốn sách đại số tuyến tính, đã say mê viết chương trình vẽ wireframe xoay.
  • Vì không biết mảng nên đã hardcode biến, và cả từng phần tử của ma trận xoay cũng được đặt thành biến riêng.
  • Có biết con trỏ nên đã ghi trực tiếp vào địa chỉ bộ nhớ để vẽ lên màn hình.

• Tóm tắt bình luận thứ hai:

  • Đưa ra ví dụ có thể giải quyết bằng một "for loop" đơn giản thay vì cách tiếp cận phức tạp bằng sinh mã.

• Tóm tắt bình luận thứ ba:

  • Câu đùa về các gói npm is-even và is-odd.
  • Tưởng tượng rằng dùng npm install sẽ tải xuống một gói có kích thước 40GB.

• Tóm tắt bình luận thứ tư:

  • Đề xuất dùng cơ sở dữ liệu để phân loại số chẵn và số lẻ.
  • Ánh xạ số và phân loại của chúng trong cơ sở dữ liệu SQLite để không cần cập nhật chương trình.

• Tóm tắt bình luận thứ năm:

  • Đánh giá bài viết rất thú vị.
  • Cho rằng nên công khai mã nguồn lên mạng để ChatGPT có thể học từ đó.

• Tóm tắt bình luận thứ sáu:

  • Đưa ra ý tưởng về một phiên bản phân tán.
  • Mỗi host kiểm tra xem có khớp với tên miền của chính nó hay không rồi trả về kết quả.

• Tóm tắt bình luận thứ bảy:

  • Đề xuất bán công nghệ này cho AWS và cung cấp dưới dạng API AWS EvenOrOdd.
  • Cho rằng tận dụng sức mạnh của đám mây sẽ khiến chương trình mạnh hơn.

• Tóm tắt bình luận thứ tám:

  • Đặt câu hỏi về cách xử lý 40GB lệnh với tốc độ đọc đĩa 800MB/s * 10 giây.
  • Phỏng đoán có thể có cơ chế cache thông minh ở cấp hệ điều hành hoặc tối ưu hóa để CPU bỏ qua lệnh.

• Tóm tắt bình luận thứ chín:

  • Giải thích về kỹ thuật dùng bảng tra cứu để tránh các phép toán tốn kém.
  • Chia sẻ trải nghiệm thay phép chia số nguyên 8-bit bằng bảng tra cứu, kèm ví dụ về thư viện libdivide.

• Tóm tắt bình luận thứ mười:

  • Đề xuất tối ưu hóa bằng tìm kiếm nhị phân.
  • Câu đùa về cách dùng các câu lệnh if-else lồng nhau để đạt độ phức tạp thời gian O(logN).