4 tỷ câu lệnh if

 (andreasjhkarlsson.github.io)
3 điểm bởi GN⁺ 2023-12-29 | 1 bình luận | Chia sẻ qua WhatsApp
  • Một ý tưởng nghịch ngợm nhằm xác định chẵn/lẻ chỉ bằng cách liệt kê các câu lệnh so sánh, không dùng %, được mở rộng từ 8-bit lên 32-bit và làm lộ ra các giới hạn của trình biên dịch cũng như định dạng tệp thực thi
  • Khi dùng trình sinh mã Python để tự động tạo if (number == n), phạm vi 8-bit và 16-bit hoạt động được, nhưng ở 32-bit, số đối tượng cần so sánh tăng vọt lên khoảng 4,2 tỷ
  • Phiên bản C 32-bit sau 48 giờ đã tạo ra một tệp C khoảng 330GB, và MSVC thất bại khi biên dịch do giới hạn số dòng và thiếu không gian heap
  • Để tránh ràng buộc 4GB của tệp thực thi PE, tác giả trực tiếp tạo lệnh x86-64 thành binary 40GB isEven.bin, rồi gọi nó như mã thực thi bằng cơ chế ánh xạ bộ nhớ của Windows
  • Chương trình cuối cùng sau khi đổi atoi sang strtoul đã xác định đúng cả các giá trị 32-bit lớn; với input lớn, chương trình trả kết quả trong khoảng 10 giây trên môi trường Core i5 12600K, RAM 32GB, SSD M.2

Xác định chẵn/lẻ chỉ bằng câu lệnh so sánh

  • Điểm khởi đầu là một ảnh chụp màn hình mã nguồn thấy trên mạng xã hội, với cách giải bài toán kinh điển xác định chẵn/lẻ mà không dùng phép toán modulus
  • Cấu trúc là đặt if (number == n) cho từng con số và dùng printf để in ra số đó là chẵn hay lẻ
  • Ví dụ C đầu tiên dùng uint8_t number = atoi(argv[1]); và viết thủ công các câu lệnh so sánh từ 0 đến 10
  • Biên dịch với /Od để tắt tối ưu hóa, nhằm ngăn trình biên dịch thay đổi thuật toán
    • 0, 4 là even
    • 3, 7 là odd
    • 50, 11, 99 không có output nào
  • Nguyên nhân là sau câu if cuối cùng không còn câu so sánh nào để xử lý, nên cần thêm nhiều câu lệnh if hơn

Sinh câu lệnh if bằng Python

  • Thay vì viết tay toàn bộ câu lệnh so sánh, tác giả dùng cách siêu lập trình bằng Python để in ra mã C
  • Script Python tạo các câu lệnh so sánh từ 0 đến 255 bằng for i in range(2**8)
    • Nếu i % 2 == 0 thì printf("even\n");
    • Nếu không thì printf("odd\n");
  • Chương trình C được tạo ra hoạt động trên toàn bộ phạm vi 8-bit
    • 99 là odd
    • 50 là even
    • 240 là even
    • 241 là odd

Đến 16-bit vẫn biên dịch C thành công

  • Cùng cách này được mở rộng sang uint16_t và range(2**16)
  • Tệp C được tạo ra có quy mô khoảng 130 nghìn dòng
  • Sau khi biên dịch bằng MSVC, chương trình hoạt động bình thường với nhiều giá trị
    • 21000 là even
    • 3475 là odd
    • 3 là odd
    • 65001 là odd
    • 65532 là even
  • Kích thước tệp thực thi khoảng 2MB, và không gây vấn đề trên PC có 31,8GB bộ nhớ

Tệp C 32-bit và giới hạn của trình biên dịch

  • Mục tiêu tiếp theo là xử lý toàn bộ phạm vi 32-bit bằng các câu lệnh so sánh với uint32_t và range(2**32)
  • 32-bit có số lượng con số nhiều hơn 16-bit 65.536 lần
  • Sau khi chạy trình sinh Python trong 48 giờ, một tệp C khoảng 330GB được tạo ra
  • Việc biên dịch bằng MSVC nhanh chóng chạm giới hạn
    • warning C4049: đạt giới hạn số dòng của trình biên dịch nên ngừng phát sinh line number emission
    • Giới hạn số dòng là 16777215
    • fatal error C1060: compiler is out of heap space
  • Định dạng Portable Executable (.exe) của Windows cũng có ràng buộc khó vượt quá 4GB, nên con đường biên dịch C để nhét hơn 4 tỷ phép so sánh vào tệp thực thi bị chặn
  • Một ràng buộc liên quan được nhắc đến là kích thước tối đa của tệp PE

Tự tạo mã máy để thực thi

  • Để tránh giới hạn của trình biên dịch và định dạng tệp thực thi, tác giả chuyển sang cách trực tiếp xuất các lệnh x86-64 thành binary
  • Hàm mục tiêu có dạng IsEven, nhận tham số qua ECX và trả giá trị qua EAX
    • Dùng XOR EAX, EAX để đặt giá trị trả về mặc định là 0 cho số lẻ
    • Với mỗi số, thực hiện CMP ECX, i
    • Nếu là số chẵn thì INC EAX rồi RET
    • Nếu là số lẻ thì RET luôn
  • x86-64 assembly và opcode được sử dụng, còn opcode của từng lệnh được hỏi ChatGPT
  • Script Python mở isEven.bin ở dạng binary và ghi các lệnh so sánh cho mọi số từ 0 đến 2**32 - 1
  • isEven.bin được tạo ra có dung lượng khoảng 40GB, chứa khoảng 4,2 tỷ phép so sánh cần thiết cho toàn bộ số 32-bit

Gọi đoạn mã 40GB bằng ánh xạ bộ nhớ Windows

  • Chương trình C host mở isEven.bin và thay vì đọc toàn bộ tệp, dùng Windows API để ánh xạ bộ nhớ
  • Luồng thực thi như sau
    • Mở isEven.bin bằng CreateFileA với quyền GENERIC_READ | GENERIC_EXECUTE
    • Kiểm tra kích thước tệp 64-bit bằng GetFileSizeEx
    • Chỉ định PAGE_EXECUTE_READ cho CreateFileMapping
    • Tạo ánh xạ có thể thực thi và đọc bằng MapViewOfFile
    • Ép con trỏ đã ánh xạ thành con trỏ hàm int (*isEven)(int) rồi gọi
  • Cách này xử lý tệp 40GB như thể toàn bộ tệp đã nằm trong bộ nhớ, còn việc bố trí thực tế được giao cho bộ nhớ ảo của hệ điều hành
  • Trong thử nghiệm đầu tiên, hầu hết đều hoạt động bình thường, nhưng 4200000000 lại trả ra odd, gây kết quả sai
  • Nguyên nhân là atoi không xử lý đúng các giá trị unsigned lớn; sau khi đổi sang strtoul(argv[1], NULL, 10), 4200000000 được in là even, còn 4200000001 là odd

Quan sát hiệu năng

  • Các số nhỏ cho kết quả ngay lập tức, còn các số lớn gần giới hạn 2^32 cũng trả kết quả sau khoảng 10 giây
  • Môi trường thử nghiệm là Core i5 12600K, RAM 32GB, SSD M.2
  • Tốc độ đọc SSD tối đa quan sát được trong khi tính toán là khoảng 800MB/s
  • Việc đạt được tốc độ như vậy dù phải đọc 40GB dữ liệu từ đĩa, ánh xạ vào bộ nhớ vật lý, và CPU gần như khó hưởng lợi từ cache, vẫn là một kết quả đáng ngạc nhiên

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-12-29
Các ý kiến trên Hacker News

  • Ước gì tôi vẫn còn giữ một trong những chương trình đầu tiên mình từng viết. Năm 1996, khi 16 tuổi, sau khi đọc mục đồ họa máy tính trong phụ lục của một cuốn sách đại số tuyến tính, tôi bị cuốn vào việc dùng kiến thức lập trình vừa học ở học kỳ trước để viết một chương trình vẽ wireframe xoay của vài khối hình
    Vì chuyện đó mà tôi suýt rớt môn; hồi ấy tôi còn chưa biết mảng, nên mọi đỉnh và mọi phần tử của ma trận xoay đều là các biến hard-code riêng lẻ, còn phép nhân ma trận thì cũng không có vòng lặp, chỉ là một danh sách dài các biểu thức tính toán phải copy-paste rồi sửa cho từng đỉnh
    Để vẽ lên màn hình thì phải ghi vào bộ nhớ bắt đầu từ một địa chỉ nhất định, nên tôi có biết con trỏ, và cũng có vòng lặp để raster hóa các đường nối giữa các đỉnh. Rốt cuộc, có thể nói tôi đã có khái niệm về mảng và indexing, nhưng chưa biết tự tạo ra chúng

    • Tôi cũng từng tương tự. Khoảng 12 tuổi, khi cố làm một game Pac-Man bằng BASIC, tôi thấy nản vì nghĩ rằng phải viết riêng logic cho 4 con ma từ (x1,y1) đến (x4,y4)
      Tôi nói với bố rằng mình muốn dùng kiểu xn, yn trong vòng lặp for, trong đó n biểu thị con ma nào, thì ông lấy sách BASIC ra và cho tôi thấy x(n) thật sự làm được như vậy
      Khi nói về giáo dục, tôi thường nhớ tới chuyện này. Khái niệm trừu tượng được học sinh hiểu tốt nhất khi các em thật sự có nhu cầu; thứ giảng giải cả ngày vẫn khiến các em mơ hồ có thể khớp ngay trong vài giây hoặc vài phút nếu nó giải quyết đúng vấn đề của chính các em
    • Cách giải hiển nhiên là dùng phần dưới của màn hình làm bộ nhớ làm việc trong khi vẽ phần trên. Đến lúc vẽ xuống gần đáy thì hầu như không còn phép tính nào nữa, lại dùng bộ nhớ GPU tốc độ cao, nên rất kiểu CUDA và rất kiểu AI
    • Chuyện này làm tôi nhớ thời mới làm freelance. Tôi chỉ có một VPS nhỏ chạy được PHP, và phải xử lý các bảng tính 5.000–10.000 dòng, vốn là khá lớn theo chuẩn năm 2002/2003
      Tôi không học chuyên ngành khoa học máy tính nên đọc file theo cách ngu ngốc nhất, và vì các vòng lặp lồng nhau nên liên tục gặp lỗi dùng quá nhiều bộ nhớ và hết dung lượng. Thế là tôi nhét $variable = null vào mọi nơi có thể, và nó thật sự chạy được
    • Snake cho TI-83, bản hit tôi làm hồi trung học cơ sở, cũng tương tự. Tôi lưu tọa độ x, y của từng đốt rắn vào các biến riêng biệt, mà số lượng biến có thể dùng trong TI-83 BASIC lại bị giới hạn, nên chiều dài con rắn cũng không thể vượt quá mức đó
    • Sau khi tự học print, input, if, goto từ tài liệu, tính năng GWBasic đầu tiên tôi học được nhờ nhờ người khác giúp là chain

  • Có vẻ thiết kế quá tay rồi. Không hiểu sao lại cần sinh mã, chuyện này có thể giải bằng một vòng lặp for đơn giản
    Trong isOdd, cứ lặp odd = !odd từ 0 đến n rồi trả về là được
    Link Playground: https://go.dev/play/p/8TIfzGrdWDF
    Tôi chưa profile thử, nhưng theo trực giác và kinh nghiệm trong ngành thì cái này nhanh

    • Nếu là triển khai chất lượng production thật sự thì luôn phải dùng đệ quy. Nếu n == 0 thì trả về false, nếu dương thì trả về !isOdd(n-1), nếu âm thì trả về !isOdd(n+1)
    • Có thể xác nhận phiên bản Rust của cách này là nhanh
      Assembly cho ra kiểu testq %rdi, %rdi, setg %al, andb %dil, %al, retq
      Nhấn ... cạnh phần build để xem assembly: https://play.rust-lang.org/?version=stable&mode=release&edit...
      Tiếc là Go Playground có vẻ không hỗ trợ xuất assembly
    • Cũng không được quên hàm chẵn. isEven(n int64) bool { return !isOdd(n) }
    • Nếu n = vô cực thì sẽ lặp vô hạn
    • Có thể cải thiện bằng đệ quy đuôi

  • Cách tiếp cận này hoàn toàn hợp với gói npm is-even[1] có 196.023 lượt tải hằng tuần, hay gói npm is-odd[2] có 285.501 lượt tải hằng tuần. Sẽ rất tuyệt nếu gõ npm install rồi nó bắt đầu tải về một is-even 40GB và một is-odd 40GB
    [1] https://www.npmjs.com/package/is-even
    [2] https://www.npmjs.com/package/is-odd

    • Luôn đáng nhắc rằng các gói này là kết quả của một spammer npm tận tụy[1] cố chen vào càng nhiều thư mục node_modules càng tốt
      ansi-colors cũng không phải một gói tổng hợp cho toàn bộ màu sắc, mà có các gói theo từng màu, và còn đủ thứ linh tinh khác. Những thứ này được nhét vào các công cụ CLI hoặc các gói trông có vẻ hợp lý rồi tham chiếu lẫn nhau, nên ngay cả một dự án thật cũng có thể kéo theo hàng chục gói của jonschlinkert chỉ vì một phụ thuộc trông vô hại
      [1] https://www.npmjs.com/~jonschlinkert
    • Đáng kinh ngạc là, do tuân theo “đừng lặp lại chính mình” theo cách thuần khiết nhất, is-even phụ thuộc vào is-odd
      Sau var isOdd = require('is-odd'); thì toàn bộ chỉ là module.exports = function isEven(i) { return !isOdd(i); };
    • Người này thì không biết, nhưng khi tôi kiểm tra cây mã nguồn của 2 ứng dụng frontend của chúng tôi, gói is-number mà is-odd phụ thuộc vào đang được khá nhiều gói khác kéo vào
      Nếu việc xác định một giá trị có phải kiểu số trong JS thật sự phiền phức thì gói này có thể có ý nghĩa, nhưng chắc hẳn phải có một gói tổng quát hơn xử lý cả các kiểu tích hợp sẵn khác
      Tuy nhiên isNumber cũng coi chuỗi có thể chuyển thành số là số, nên có thể cho ra kết quả kỳ lạ. Ví dụ const a = '1'; isNumber(a); // true, nhưng const b = a + a; lại trở thành chuỗi '11'
      Tất nhiên 2*a thành 2, còn 1+'1' và '1'+1 đều thành '11', đúng kiểu ngớ ngẩn chuẩn của JS; vì vậy câu trả lời rằng '1' là số có thể không đúng. Thế mà gói này tuần trước được tải 46 triệu lần, và chỉ thấp vì là Giáng sinh; các tuần trước trung bình khoảng 70 triệu. Giống dự án của chúng tôi, phần lớn hẳn là do phụ thuộc kéo vào
    • Tôi từng tạo gói nullll[1] chỉ xuất ra một null nhưng dùng 400MB bộ nhớ, vậy mà không hiểu sao lại bị gắn cờ trên HN[2]
      Với 41 sao GitHub và độ bao phủ kiểm thử 100%[3] thì rõ ràng nó đã sẵn sàng cho production
      [1]: https://github.com/mickael-kerjean/nulll
      [2]: https://news.ycombinator.com/item?id=17072675
      [3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
    • Thật ra số trong JavaScript không phải u32 mà là f64, nên từng đó vẫn chưa đủ. Chỉ cần hỗ trợ phạm vi số nguyên an toàn thôi đã là 2⁵⁴, lớn hơn 2³² hơn 4 triệu lần
      Kích thước mã máy có lẽ chỉ tăng khoảng 4 byte cho mỗi nhánh, tức khoảng 40%, nên sẽ lên xấp xỉ 224 exbibyte. Đó là còn trong trường hợp lười biếng bỏ qua 10 bit cuối
      Nếu làm cho đúng thì có khi phải nhân thêm 1.000 lần nữa, và tôi chưa suy nghĩ kỹ về các mẫu NaN nên cũng có thể nhỏ hơn một chút. Nếu hỗ trợ cả bigint thì có lẽ đơn giản là vô hạn

  • Không hiểu sao phải làm như vậy. Cơ sở dữ liệu được phát minh chính là để làm những việc kiểu này. Chỉ cần lưu ánh xạ giữa số và phân loại even/odd trong cơ sở dữ liệu SQLite là được
    Cách này còn có ưu điểm là không phải cập nhật chương trình mỗi khi phân loại của một số nào đó đổi từ lẻ sang chẵn

    • Cơ sở dữ liệu cũng cần bảo trì và cập nhật. Chi bằng dựng một hợp đồng Ethereum, để người khác đóng vai trò oracle và có động lực kinh tế trả về đáp án đúng bất cứ lúc nào
    • Đây trông giống loại dữ liệu nên có trên Wikidata. Như vậy không cần cơ sở dữ liệu cục bộ, chỉ cần một yêu cầu HTTPS nhanh là xong
      Vấn đề duy nhất có thể là khi bản thân TLS phụ thuộc vào hàm chẵn/lẻ, nhưng chắc là không đâu
    • Tạo bảng tên even_or_odd và thêm các cột như is_odd, is_even, is_zero, is_one, is_two, is_three. 1 thì điền is_odd,is_one, 2 thì điền is_even,is_two
    • Đúng, nhưng tất nhiên là phải dùng cơ sở dữ liệu XML
      Nó cũng giúp tính di động của dữ liệu, và khi cần kiểm tra thủ công thì vẫn giữ được định dạng dễ đọc cho con người
    • AWS đã có Elastic Cloud Parity cung cấp rồi, và khả năng mở rộng tốt hơn nhiều

  • Đây là một trong những bài thú vị nhất tôi từng đọc ở đây. Nên đưa mã nguồn lên mạng để ChatGPT có thể “học” được

    • Như vậy chắc chắn sẽ vi phạm giấy phép nghiêm ngặt của anh ta
      /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/
      Với đoạn mã tao nhã như vậy thì ai trách được chứ?

  • Tôi hoàn toàn không hiểu trò đùa này. Người tạo ra nó thì cứ cho là vậy đi, nhưng 1198 lượt đề xuất hiện tại làm tôi bối rối
    Bảng tra cứu cho các giá trị có thể tính toán được chẳng mới mẻ gì, cũng chẳng phải trò đùa. Đó là một giải pháp thực tế để đánh đổi thời gian/bộ nhớ, và tác giả cũng biết điều đó
    Bản thân bài toán thì lố bịch nhưng rất sơ khai, nên không có gì để nghi ngờ rằng nó khả thi; ngoài quan sát rằng họ đã xử lý một chương trình 40GB trên máy tính của mình trong khoảng 10 giây, cũng không có phép đo thực tế nào
    Vậy ta học được gì? Rằng file exe không thể vượt quá 4GB? Rằng nếu có 2^32 câu if thì chương trình sẽ khoảng 300GB? Tôi không hiểu vì sao 1198 người lại thấy thứ này thú vị
    Khác với “Hexing the technical interview” hay các bài SIGBOVIK, cái này không điên rồ mà chỉ có vẻ vô nghĩa

    • Trò đùa nằm ở chỗ họ thực sự đã làm nó. Suốt nhiều thập kỷ, người ta đã đùa kiểu này, và kẻ điên này đã thực sự làm được
      Nó cực đoan đến mức không compiler nào xử lý nổi, ngay cả các assembler đã biết cũng không. Vì vậy, để nó chạy được, họ phải tự tạo binary mã máy, và nó thực sự chạy. Điên thật
    • Nói rằng bảng tra cứu cho các giá trị có thể tính toán được không mới thì đúng, nhưng nếu tắt tối ưu hóa thì 4 tỷ câu lệnh if sẽ không được biên dịch thành bảng tra cứu
      Từng câu if sẽ được đánh giá tuần tự xem có khớp với input không, và output cho thấy chương trình gốc kết thúc nhanh hơn nhiều với các số nhỏ cũng ủng hộ điều này. Vì các số nhỏ nằm ở phần đầu code
      Ngược lại, nếu là một câu lệnh switch với 4 tỷ case, tôi sẽ kỳ vọng nó được biên dịch thành một dạng bảng tra cứu nào đó. Nhưng tôi không biết code được biên dịch không tối ưu hóa sẽ trông ra sao khi kiểu dữ liệu là số nguyên không dấu
    • Đôi khi người ta làm gì đó chỉ để gây cười
    • Tôi hiểu đây là một bản nhại các bài blog châm biếm việc phản kháng lại trí khôn thông thường vô nghĩa đến mức nào. Một trò đùa khá khô khan

  • Công nghệ đáng kinh ngạc. Nên bán cho AWS để họ cung cấp nó dưới dạng Enterprise-ready AWS EvenOrOdd API cho tất cả những ai không biết cách host đúng một file thực thi 40GB
    Với sức mạnh của cloud, chương trình này sẽ không thể bị ngăn cản

    • Trông đúng kiểu đang chờ để trở thành một hàm Lambda

  • Tôi ngạc nhiên là không ai chen vào chuyện chương trình đã “xử lý” 40GB lệnh chỉ với tốc độ đọc đĩa khoảng 800 MB/s * 10 giây
    Tôi đoán là có caching thông minh ở cấp hệ điều hành, nhưng như vậy nghĩa là benchmark với n gần 2^32 đã không thực sự chạy đúng
    Hoặc có thể CPU đủ thông minh để nhảy trước qua hàng triệu lệnh

    • Nếu là “một dàn máy gaming mạnh mẽ với 31.8GB bộ nhớ”, thì nếu caching của hệ thống file đủ mạnh với các lần quét lặp/tuần tự, khi chạy lại chỉ cần đọc khoảng 8GB là đủ
      Ban đầu tôi nghĩ phép tính hẳn là sai, nhưng tính nhẩm thì thấy khá hợp lý. Các con số đều là giá trị được làm tròn một cách mơ hồ, và input cũng không phải giá trị tối đa tuyệt đối mà chỉ là một giá trị cao, nên càng hợp lý hơn
    • Có lẽ là do nén hoặc dữ liệu còn nằm trong RAM. CPU không thể tỏ ra thông minh ở đây vì nó không biết các câu if trong tương lai là gì
      Nó không biết những đoạn code đó có theo thứ tự không, có duy nhất không, hay thậm chí có phải lệnh hợp lệ không. Về lý thuyết, trong lúc chương trình chạy, một câu if nào đó cũng có thể bị đổi thành vòng lặp vô hạn. Dù hệ điều hành sẽ không cho phép
    • Cũng có paging dự đoán. Hệ điều hành có thể đoán trang nào sẽ được yêu cầu tiếp theo
    • Không thể là do CPU. Thực tế đây là code được memory-map, và branch predictor hẳn không thể gây page fault để nạp trang code tiếp theo
      Tôi thật sự tò mò. Mẫu truy cập tuyến tính thì có giúp, nhưng 800 MiB/s ư?
    • Vì chương trình được mmap, các trang không dùng đến chỉ chiếm các mục trong page table chứ không được load. Thứ thực sự được load chỉ là trang mà nó nhảy trực tiếp tới. Một mẹo gọn gàng

  • Thiên tài có tầm nhìn xa Ross van der Gussom giờ là sinh vật thần thoại yêu thích nhất của tôi

    • Hãy xem Python như một cách scripting C và bỏ qua phần lớn hoặc toàn bộ việc biên dịch. Nếu Python chậm thì có lẽ bạn đang dùng sai cách
      Tôi đề xuất bài này: https://cerfacs.fr/coop/fortran-vs-python
    • Tôi đã tìm web để xem “Ross van der Gussom” có phải là một câu đùa nội bộ không, và 2 kết quả tìm kiếm hàng đầu là bài gốc và bình luận cha này

  • Toàn bộ bài viết có cảm giác như một ngụ ngôn về phát triển LLM. Nếu do một người phê bình viết, họ có thể nói đó là việc bỏ ra tài nguyên khổng lồ và “dữ liệu huấn luyện” để “ghi nhớ” lời giải
    Tôi tự hỏi liệu đó có phải ý định của tác giả không

    • Chỉ nhìn tiêu đề tôi đã tưởng đây là bài công bố một mô hình 4B mới, nên có lẽ đúng vậy
    • Đọc tiêu đề xong tôi đã hoàn toàn đoán đây sẽ là một bài về LLM
    • Đúng. Nó trông giống như một mô hình LLM 40B thực hiện vòng lặp for. Ẩn dụ này có vẻ như động cơ thực sự của bài viết, và nó giống một bài về sự phi lý sắp ập tới hơn là một câu chuyện kỹ thuật