FizzBuzz 55 GiB/s (2021)

 (codegolf.stackexchange.com)
5 điểm bởi GN⁺ 2023-07-04 | 1 bình luận | Chia sẻ qua WhatsApp
  • High throughput Fizz Buzz trên Code Golf Stack Exchange là một thử nghiệm hiệu năng xem ai có thể tạo đầu ra FizzBuzz nhanh đến mức nào và đẩy nó qua pipe, chấm điểm theo thông lượng của <program> | pv > /dev/null
  • Đầu ra hợp lệ phải là ASCII thuần, xuống dòng bằng \n, Fizz/Buzz/FizzBuzz chính xác, kéo dài ít nhất đến 2^58 hoặc thực tế là vô hạn, và mẹo byte null chỉ bị pv bắt được là bị cấm
  • Các bản cài đặt hàng đầu đã bỏ % 3, % 5, vòng lặp printf, thay bằng unroll mẫu 15 dòng, xử lý số độ rộng cố định, bộ đệm lớn, song song hóa, và xuất không sao chép (zero-copy) để giảm nút thắt cổ chai
  • Câu trả lời assembly x86-64+AVX2 được nêu ra giả định Linux và AVX2, kết hợp vmsplice, L2 cache, huge page, và trình thông dịch bytecode FizzBuzz để đạt khoảng 61GiB/s
  • Kết quả dao động mạnh theo CPU, pipe buffer, phiên bản pv, CPU affinity, và thiết lập mitigation; trên máy của người đặt câu hỏi, điểm cao nhất được tổng hợp là bản C++ của David Frank khoảng 1.7Tb/s

Giới hạn thông lượng bị ép tới cùng với FizzBuzz

  • Trọng tâm không phải bài toán FizzBuzz, mà là kiểm tra trong việc tạo văn bản cực kỳ đơn giản thì tính toán CPU, sao chép bộ nhớ, pipe I/O, hay ranh giới kernel sẽ trở thành nút thắt trước
  • Bản cài đặt C ngây thơ làm mốc dùng % 3, % 5, và printf, cho khoảng 170MiB/s trên máy trung bình
  • Người đặt câu hỏi cho biết đã từng thấy các bản cài đặt vượt 3GiB/s trên cùng máy và muốn cộng đồng khám phá giới hạn thông lượng cao hơn
  • Điểm số được đo trên máy desktop của người đặt câu hỏi
    • AMD 5950x, 16C/32T
    • 64GB RAM 3200MHz
    • Tắt CPU mitigations
  • Bảng theo ngôn ngữ gồm asm 60.8GiB/s, C 20.9GiB/s, Julia 15.5GiB/s, Go 6.8GiB/s, Java 5.8GiB/s, Rust 3.4GiB/s, Ruby 1.7GiB/s, Python 0.5GiB/s, v.v.
  • Câu trả lời assembly x86-64+AVX2 của ais523 nhắm tới hiệu năng đơn luồng tối đa, đạt khoảng 31GiB/s trên máy tác giả và khoảng 61GiB/s trong bảng tổng hợp của người hỏi
  • Bản C++ của David Frank hiện là điểm cao nhất theo phần thân câu hỏi, đạt khoảng 1.7 Terrabit/s; tác giả cũng nói một bản C++20 riêng đạt 283GB/s trên AMD Ryzen 9 7700X

Quy tắc đầu ra và điều kiện benchmark

  • Điều kiện đầu ra hợp lệ khá khắt khe
    • Đầu ra phải là FizzBuzz chính xác
    • Mỗi ký tự ASCII phải chiếm 1 byte
    • Chỉ cho phép xuống dòng \n
    • Không chấp nhận \r\n
    • Đầu ra phải tiếp tục đến ít nhất 2^58, tức là một phạm vi cực lớn
  • Bản thân cách benchmark cũng ảnh hưởng tới thông lượng
    • Có thảo luận rằng pv và Linux pipe buffer mặc định dùng bộ đệm 64K
    • Tùy cách bố trí các sibling core CPU mà đường đi L2 cache giữa chương trình sinh dữ liệu và chương trình tiêu thụ có thể thay đổi
    • Có thể ép bố trí CPU bằng taskset để so sánh

Cách tối ưu của bản assembly

  • Trọng tâm của bản assembly là giảm chi phí sao chép đầu ra hơn là chi phí tính toán
    • Dùng write sẽ tốn chi phí sao chép từ không gian người dùng sang không gian kernel
    • Tác giả viết rằng nếu đổi sang dựa trên write, hiệu năng giảm còn 1/5
    • vmsplice cho phép pipe tham chiếu trực tiếp tới bộ đệm của chương trình để giảm sao chép
  • Việc tính FizzBuzz được chia thành 3 giai đoạn
    • Giai đoạn đầu hard-code các chuỗi ban đầu
    • Giai đoạn hai xử lý các số có 2–5 chữ số bằng một routine AVX2 khá trực tiếp
    • Giai đoạn ba xử lý vùng 6–18 chữ số bằng trình thông dịch bytecode FizzBuzz
  • Vòng lặp chính của giai đoạn ba nhắm tới 64 byte đầu ra mỗi 4 chu kỳ clock
    • 1 byte bytecode tạo ra 1 byte đầu ra
    • Nạp 32 byte bytecode rồi dùng vpshufb, vpsubb, v.v. để tạo 32 byte đầu ra
    • Số dòng được xử lý bằng giá trị gần đúng và hiệu chỉnh bằng bytecode, nên không cần chuyển đổi số thông thường cho mỗi dòng
  • Bản cài đặt này phụ thuộc nền tảng rất mạnh
    • Cần Linux không quá cũ
    • Cần CPU x86-64 hỗ trợ AVX2
    • Nếu đầu ra chuẩn không phải pipe thì sẽ báo lỗi khi khởi động
    • Tác giả nói rằng trong cấu hình pipe có splice chen vào, đôi khi có thể tạo ra đầu ra sai

Chiến lược chung mà các bản cài đặt ngôn ngữ khác sử dụng

  • Các bản C, Go, Java, Rust, Python, Julia, Ruby, C# cũng lặp lại các hướng tối ưu tương tự
    • Unroll mẫu FizzBuzz 15 dòng
    • Giảm số lần chuyển đổi số sang chuỗi
    • Ghi dồn vào bộ đệm lớn
    • Song song hóa việc sinh dữ liệu bằng thread hoặc goroutine
    • Dùng barrier, channel, queue, mutex để giữ đúng thứ tự đầu ra
  • Kết quả này khó xem như một phép so sánh đơn giản về “hiệu năng ngôn ngữ”
    • Phiên bản pv, kích thước pipe, khả năng dùng vmsplice, CPU affinity, huge page, tối ưu hóa compiler, và việc memcpy có được inline hay không đều ảnh hưởng mạnh tới thông lượng
    • Có bình luận cho biết một số câu trả lời rất nhanh trên máy cụ thể nhưng không tái hiện được cùng con số trong môi trường khác

Phạm vi không được đề cập

  • Ghi chú đầu vào cho biết một số đoạn nguồn đã bị lược bỏ do giới hạn độ dài và chi phí, nên không bao quát đầy đủ toàn bộ 46 câu trả lời cùng mọi mã nguồn và bình luận
  • Phần bị lược bỏ có thể gồm một số bài nộp theo ngôn ngữ, phần thân mã dài, nhật ký tinh chỉnh chi tiết, và các thảo luận trong bình luận

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-07-04
Ý kiến trên Hacker News

  • Điều gây ấn tượng nhất là Linux có thể giữ dữ liệu được pipe từ chương trình này sang chương trình khác chỉ nằm trong cache L2 mà không cần đụng tới bộ nhớ chính
    Việc nhiều phần khác nhau của một kernel Linux bình thường phối hợp với nhau để tạo ra đường đi nhanh như vậy cho thấy một thiết kế kiến trúc hệ thống thật đáng kinh ngạc
    Tò mò không biết điều này có thể xảy ra với Mach port trên Mac OSX hay Named Pipes trên Windows hay không

    • Nếu cache CPU dùng thẻ địa chỉ vật lý, và bảng trang của hai tiến trình cùng chia sẻ một trang vật lý, thì trừ khi hệ điều hành chủ động xóa hoặc vô hiệu hóa cache khi chuyển ngữ cảnh, CPU sẽ cho phép tiến trình nào cũng dùng nội dung đang có trong cache
    • Đây là một trong nhiều lý do khiến cả ngành giao dịch tần suất cao chạy trên Linux

  • Đúng với tên người dùng “ais523 - high effort answers”, người này đã để lại một bình luận rất công phu ngay cả với người không chạy được chương trình, và kết luận là thế này
    “Có lẽ chương trình đã vô tình được biên dịch khi ASLR đang bật. Trong trường hợp đó, dynamic linker không tôn trọng căn chỉnh 4MiB của BSS segment nên .align của tôi về cơ bản bị bỏ qua, và đó dường như là nguyên nhân gây ra lỗi”

    • Chỉ biết là nếu người này ứng tuyển cùng vị trí với tôi thì tôi không có cửa thắng. Đúng kiểu leet coder tối thượng

  • Mỗi lần bài này được đào lại, tôi lại bật cười khi đọc bình luận này
    “@chx: Tôi đã có sẵn một luận văn thạc sĩ rồi. Cái này còn khó hơn. – ais523 - high effort answers Oct 29, 2021 at 1:17”

  • Đã thử cài đặt đơn giản bằng Rust, Python3 và C mà không tối ưu hóa. Chỉ dùng if/else/while đơn thuần và xuất ra standard output
    Rust -> 23.2MiB/s
    Python3 -> 28.6MiB/s
    C -> 238MiB/s
    Có ai biết vì sao hiệu năng Rust lại ở cùng tầm với Python3 không. Tôi đã nghĩ nó sẽ gần với C hơn

    • Hàm print của Rust mặc định sẽ lấy khóa. Đó là vì lý do an toàn, còn C thì không. Xem chi tiết trong tài liệu Rust: https://doc.rust-lang.org/std/macro.print.html
      Muốn có hiệu năng gần như C thì rất có thể bạn sẽ phải tự xử lý phần khóa này
      let mut lock = stdout().lock();
      write!(lock, "hello world").unwrap();
      Và cũng cần chỉnh kích thước bộ đệm của standard output cho khớp với C
    • Đây là một bài viết cũ tôi từng đăng, có thể sẽ hữu ích
      https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
    • C và Python dùng buffering thích ứng cho standard output. Nếu đầu ra là terminal thì sẽ flush ở mỗi dòng mới, còn nếu không thì chỉ flush khi bộ đệm nội bộ đầy
      Với một chương trình C đếm số có độ trễ 1ms, cột thứ hai là thời gian đã trôi qua kể từ read() trước đó
      $ ./out | rtss
      4.7ms 4.7ms | 1
      4.7ms | 2
      4.7ms | 3
      4.7ms | 4
      4.8ms exit status: 0
      Có thể thấy tất cả được ghi ra cùng một lúc. Nếu cấp phát terminal thì nó sẽ hiện theo từng dòng
      $ rtss --pty ./out
      0.8ms 0.8ms | 1
      1.9ms 1.1ms | 2
      3.0ms 1.1ms | 3
      4.1ms 1.1ms | 4
      4.3ms exit status: 0
      Rust không có kiểu hành vi thích ứng này cho đầu ra, nên bất kể có phải terminal hay không thì nó luôn hoạt động như kết quả thứ hai
      Về mặt kỹ thuật, standard output luôn được bọc bằng LineWriter(https://doc.rust-lang.org/std/io/struct.LineWriter.html), và khi gặp thao tác ghi có chứa ký tự xuống dòng thì nó sẽ luôn flush. Muốn tối đa hóa thông lượng thì cần bọc bằng BufWriter để gộp nhiều dòng lại rồi ghi
    • Rust nên biên dịch với --release, còn C với -O3
    • Gần như chắc chắn là đang bị giới hạn bởi output. Nhiều khả năng là vấn đề buffering hoặc khóa

  • Khiến tôi tự hỏi nếu mọi thứ đều được viết bằng assembly thì nó sẽ nhanh đến mức nào
    Trong phát triển audio, việc viết mã DSP bằng assembly là chuyện rất phổ biến

    • Lý do nó nhanh không đơn giản chỉ vì là assembly. Điều đó là cần thiết cho cách tiếp cận này, nhưng tuyệt đối không phải điều kiện đủ
      Cần có sự kết hợp của nghiên cứu thuật toán ở mức cực đoan, kiến thức sâu về Linux system call và tối ưu hóa theo từng nền tảng thì điều này mới khả thi. Mượn lời chính tác giả Alex Smith:
      “@chx: Tôi đã có một luận văn thạc sĩ rồi. Cái này còn khó hơn.”
      Đây hoàn toàn là một đẳng cấp khác với kiểu chỉ cần nói “cứ làm bằng assembly là được”
    • Dù có được viết hoàn toàn bằng Java đi nữa, có lẽ vẫn sẽ tốt hơn cách làm hiện nay là nhét Chrome vào trong một instance Python rồi chạy web server JavaScript để render tài liệu
    • Rốt cuộc nó sẽ thành ra giống câu chuyện Geoworks của Steve Yegge
      “Được thôi. Tôi học ở University of Washington rồi đi làm cho một công ty tên là Geoworks và đã lập trình assembly language suốt 5 năm. Chúng tôi ở Geoworks viết toàn bộ hệ điều hành, thư viện, driver, ứng dụng, tức là cả desktop operating system, hoàn toàn bằng assembly. Là assembly 8086 đấy! Thậm chí còn không phải loại assembly hay ho gì! Chỉ có bốn thanh ghi thôi! Nếu tính đến 386 thì còn có cả thanh ghi si nữa. Thật kinh khủng.
      Thực ra chúng tôi lại khá thích nó. Vì đó là assembly hướng đối tượng. Thật đáng kinh ngạc khi con người có thể tự thuyết phục mình thích một thứ gì đó, và đó mới là mỉa mai thực sự của tất cả chuyện này. Với chúng tôi, C++ là đỉnh cao của sự suy đồi kiểu La Mã. Giống như đi nôn ra để còn ăn thêm. Họ có IF! Còn chúng tôi có jump CX zero! Họ có ‘object’. Chúng tôi cũng có, nhưng họ có cả cú pháp dành cho nó. Trông thật yếu đuối. Và hồi đó, chúng tôi biết mình có thể tạo ra mã nhanh hơn bất kỳ compiler nào, và thực tế đúng là như vậy!
      Vậy chuyện gì đã xảy ra? Công ty phá sản. Tại sao ư? Có lẽ tôi sẽ khác quan điểm với mọi Geoworker khác. Thực ra tôi cũng biết mình có thể là người duy nhất tin điều này. Nhưng lý do là vì chúng tôi đã viết 15 triệu dòng assembly language 8086. Chúng tôi có công cụ rất tốt, đẳng cấp thế giới, cứ tin tôi đi. Phải có những thứ như vậy mới làm được. Nhưng rồi sẽ đến một lúc…
      Vấn đề là, hãy tưởng tượng một con kiến đang cố đi theo đường thẳng qua sàn nhà để xe. Nó không thể đi thẳng được. Chúng ta biết điều đó vì tầm nhìn của chúng ta rộng hơn. Ta thấy con kiến cứ vòng vèo và tối ưu cục bộ theo hòn đá này, rồi lại theo hướng bên kia.
      Đó chính là điều xảy ra khi chúng tôi viết một hệ thống assembly language khổng lồ. Cuối cùng Microsoft tung ra một nền tảng thiết bị di động nhanh hơn của chúng tôi rất nhiều. Tôi cầm debugger chui vào xem, kiểu như, ‘Cái gì vậy? Sao lại thế này? Render chậm khủng khiếp, giật lag quá’. Chui vào rồi mới thấy rằng mỗi lần refresh màn hình, có một title bar nào đó bị render đến 140 lần. Mà không chỉ title bar đâu. Mọi thứ đều bị gọi đi gọi lại nhiều lần.
      Vì chúng tôi không còn nhìn thấy hệ thống hoạt động như thế nào nữa!
      Một hệ thống nhỏ không chỉ dễ tối ưu hơn, mà còn tối ưu được. Ý tôi là tối ưu hóa toàn cục là khả thi.”
      http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
    • Assembly quá xa so với mã nguồn gốc được viết ngày nay, đến mức ngay cả việc nghĩ theo hướng đó cũng không còn thực tế. Nhưng vẫn đáng để tưởng tượng mọi thứ có thể nhanh hơn đến mức nào nếu các công ty làm phần mềm thực sự quan tâm đến hiệu năng
      Có cảm giác khoảng 99% website và phần mềm ngày nay chỉ cần chú ý một chút đến hiệu năng ứng dụng thì với vài thay đổi cơ bản cũng có thể đạt được ít nhất 50% cải thiện tốc độ. Ví dụ như caching đúng cách, tối ưu asset, thay các thư viện bên thứ ba cồng kềnh bằng các lời gọi native có sẵn làm cùng một việc, và cấu hình server cùng database cho phù hợp
      Cũng có thể trong vài năm nữa AI sẽ cung cấp tối ưu hóa một cú nhấp cho kho mã, tự áp dụng best practice hoặc viết lại mã gốc thành assembly nhanh hơn
    • Một chi tiết thường bị bỏ qua trong câu chuyện rằng ngôn ngữ càng nguyên thủy thì chương trình càng nhanh là: nếu chỉ để tiến lên được một chút khi viết code cũng đã đau đớn, thì bạn sẽ rất cố gắng chỉ triển khai ít nhất có thể
      Ràng buộc tài nguyên có thể mang lại sự rõ ràng về trọng tâm

  • Thí nghiệm này tuy thú vị và hữu ích nhưng có vẻ hơi khiếm khuyết. Nó chủ yếu kiểm tra một vấn đề ngoại vi là hiệu quả của việc lấy dữ liệu từ bộ nhớ trong một tiến trình rồi chuyển sang tiến trình khác, hơn là đánh giá một bài toán phức tạp được giải nhanh đến mức nào
    Vì vậy trông như tiến trình thứ hai liên tục ghi ra console hoặc file, nhưng về mặt kỹ thuật thì không phải vậy. Chạy pv >/dev/null về bản chất gần như không làm gì cả, và lời gọi hệ thống write gần như trả về ngay lập tức
    vmsplice về cơ bản là chức năng tương đương bộ nhớ dùng chung, cho phép một tiến trình khác truy cập vào buffer/bộ nhớ của một tiến trình. Có vẻ không rõ liệu điều này có hợp lệ theo luật chơi hay không, rất có thể vì yêu cầu ban đầu của cuộc thi khá mơ hồ

    • Có thể cuộn lên trên xem câu hỏi gốc để kiểm tra liệu yêu cầu ban đầu có mơ hồ hay không, và lịch sử chỉnh sửa cũng cho thấy nó không hề thay đổi sau khi thử thách bắt đầu
      “Hãy viết một chương trình FizzBuzz. Chạy nó. Pipe đầu ra qua | pv > /dev/null. Thông lượng càng cao thì bạn làm càng tốt.”
      “Đầu ra của chương trình phải là fizzbuzz hợp lệ chính xác. Không được gian lận kiểu chèn byte null vào giữa các đầu ra hợp lệ. Ý là những byte null không hiện trên console nhưng vẫn bị tính vào thông lượng của pv.”
      Và vmsplice(2) thực sự tạo ra một luồng byte trên pipe đầu ra chuẩn, rồi pv(1) có thể splice nó sang /dev/null hoặc cat(1) có thể sao chép nó ra terminal
      Không chỉ riêng bài nộp này dùng vmsplice(2). Những người tham gia khác cũng đã phát hiện ra rằng đây hoàn toàn không phải là lời giải thần kỳ. Ngay cả sau khi vượt qua rào cản I/O, vẫn còn rất nhiều việc để tạo ra các trang đầu ra nhanh nhất có thể
    • Tôi nghĩ “hiệu quả của việc lấy dữ liệu từ bộ nhớ trong một tiến trình rồi chuyển sang tiến trình khác” gần như lúc nào cũng chính là toàn bộ vấn đề
      Hầu hết mã nguồn đều bị nghẽn ở bộ nhớ và I/O. Ngay cả các bài toán phức tạp cũng thường bị giới hạn bởi tốc độ di chuyển dữ liệu từ nơi này sang nơi khác, chứ hiếm khi bị giới hạn bởi tính toán dữ liệu; từ góc độ của người dành cả ngày tối ưu hóa hợp ngữ GPU thì ngay cả những trường hợp hiếm hoi bị nghẽn do tính toán, sau khi tối ưu xong thì bộ nhớ lại trở thành nút thắt
    • Tôi không đồng ý. Trước tiên phải có mức tối ưu hóa rất đặc thù cho FizzBuzz thì nút thắt mới chạm đến “hiệu quả của việc lấy dữ liệu từ bộ nhớ trong một tiến trình rồi chuyển sang tiến trình khác”
      Ví dụ, có một cách biểu diễn bit thông minh để việc nhớ sang chữ số thập phân diễn ra tự nhiên
      Yêu cầu ban đầu của cuộc thi cũng không hề mơ hồ ở điểm này. Nó nói rõ phải đo thông lượng bằng | pv > /dev/null, và còn nói thêm:
      “Tối ưu hóa theo kiến trúc / hợp ngữ đều được chấp nhận. Đây không phải một cuộc thi nghiêm túc. Tôi chỉ muốn xem mọi người đẩy fizz buzz đến giới hạn, kể cả khi nó chỉ chạy trên một môi trường/nền tảng đặc thù.”
    • I/O theo nghĩa đen là việc mọi chương trình đều phải làm. Trên phần cứng hiện đại, 99% mã chạy cũng có thể bị nghẽn ở đây. Di chuyển byte từ nơi này sang nơi khác là bắt buộc và tương đối chậm
      Hiểu cách xử lý I/O bộ nhớ và I/O tệp hiệu quả là kỹ năng liên quan đến mọi chương trình và mọi lập trình viên

  • Họ bảo lưu dưới tên fizzbuzz.S, nên tôi thắc mắc sự khác nhau giữa phần mở rộng .S và .s là gì

    • Chữ S viết hoa sẽ chạy trình tiền xử lý trước
      Theo trang hướng dẫn:
      file.s
      Mã assembler
      file.S
      file.sx
      Mã assembler cần tiền xử lý
    • Nếu tôi nhớ không nhầm thì theo truyền thống, khác biệt là đầu vào có đi qua trình tiền xử lý (.S) hay không (.s)
      Tôi không rõ trong toolchain hiện đại còn có khác biệt nào nữa không
    • Theo quy ước tôi quen dùng, .S là file hợp ngữ do con người viết, thường được theo dõi trong git, còn .s là hợp ngữ do máy sinh ra và có thể ghi đè nếu cần
    • GCC và các công cụ tương tự sẽ không ghi đè .S, nhưng nếu bạn yêu cầu nó sinh mã hợp ngữ (ví dụ gcc -S xyz.c) thì nó sẽ ghi đè .s

  • Bài trước:
    https://news.ycombinator.com/item?id=29031488
    https://news.ycombinator.com/item?id=29413656

  • Lúc đầu tôi đọc thành FritzBox 55 GiB/s. FritzBox là dòng router phổ biến ở khu vực nói tiếng Đức tại châu Âu
    ISP của tôi tuần trước cũng tweet rằng sắp cung cấp hộp OPNSense hỗ trợ 60 GiB/s[1]
    [1] https://twitter.com/init7/status/1674920410889043973

    • Tôi đang dùng DEC750 với bộ nhớ nâng lên 16GB. Một router hỗ trợ 10GbE, WireGuard đạt 2.3GbE, chạy êm và điện năng nhàn rỗi chỉ khoảng 8W tương đương modem cáp, nên đây là thiết bị tuyệt vời và tôi không định thay nó trước giai đoạn 2030–2035
      Tôi còn cắm thêm adapter USB WiFi để nếu đường cáp bị đứt thì một số VLAN nhất định sẽ tự động failover, dùng điện thoại để duy trì kết nối thiết yếu cho công việc
      Nó không rẻ, nhưng nếu bạn muốn hỗ trợ tài chính cho dự án OPNSense đồng thời mua phần cứng tử tế thì rất khó chê thiết bị của Deciso. Chúng tiết kiệm điện, dùng linh kiện thiên về độ bền, và đơn giản là hoạt động tốt
      Thật vui khi thấy dòng sản phẩm thương mại ngày càng mạnh hơn