Thử thách 1 tỷ dòng

 (morling.dev)
2 điểm bởi GN⁺ 2024-01-05 | 2 bình luận | Chia sẻ qua WhatsApp
  • One Billion Row Challenge (1BRC), diễn ra trong tháng 1/2024, là một thử thách hiệu năng nhằm xử lý tệp văn bản 1 tỷ dòng và so tài xem Java có thể nhanh đến đâu
  • Dữ liệu đầu vào là văn bản đơn giản theo định dạng station;temperature, nhưng phải tính chính xác nhiệt độ thấp nhất, trung bình và cao nhất theo từng trạm quan trắc, rồi xuất theo thứ tự tên
  • Phần triển khai chỉ cho phép dùng Java; có thể dùng các bản phân phối từ SDKMan và các bản Early Access của openjdk.net, nhưng cấm phụ thuộc bên ngoài
  • Người tham gia nộp bài bằng pull request vào kho 1brc trên GitHub, và có thể dùng bản triển khai cơ sở được cung cấp để so sánh định dạng đáp án cũng như hiệu năng
  • Việc đánh giá được chạy 5 lần trong cùng môi trường Hetzner Cloud CCX33, sau đó loại bỏ kết quả nhanh nhất và chậm nhất, lấy trung bình 3 lần còn lại để xếp hạng trên leaderboard

Bài toán Java tổng hợp 1 tỷ dòng nhanh nhất

  • One Billion Row Challenge là thử thách hiệu năng Java diễn ra từ ngày 1/1 đến 31/1/2024
  • Người tham gia viết chương trình Java đọc các giá trị đo nhiệt độ từ tệp văn bản và tính nhiệt độ thấp nhất, trung bình và cao nhất cho từng trạm khí tượng
  • Điểm khó cốt lõi nằm ở việc tệp đầu vào có 1.000.000.000 dòng
  • Đầu vào có cấu trúc đơn giản, mỗi dòng chứa một giá trị đo
    • Ví dụ: Hamburg;12.0
    • Ví dụ: Bulawayo;8.9
    • Ví dụ: Palembang;38.8
  • Đầu ra phải sắp xếp tên trạm quan trắc theo thứ tự alphabet và hiển thị các giá trị min/mean/max của từng trạm
    • Ví dụ: {Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, ...}

Quy tắc nộp bài và môi trường chạy

  • Mục tiêu là tạo ra bản triển khai Java nhanh nhất thực hiện cùng một tác vụ
  • Có thể tận dụng luồng ảo, Vector API và SIMD, tối ưu GC, biên dịch AOT, v.v. để tối ưu
  • Các quy tắc cơ bản như sau
    • Bài nộp phải được viết bằng Java
    • Có thể sử dụng các bản phân phối Java do SDKMan cung cấp và các bản Early Access từ openjdk.net
    • Các bản EA của những dự án OpenJDK như Valhalla cũng được phép dùng
    • Không được sử dụng phụ thuộc bên ngoài
  • Người tham gia clone kho 1brc và nộp phần triển khai theo hướng dẫn trong README
  • Bản triển khai cơ sở được cung cấp để làm mốc so sánh và kiểm tra định dạng đáp án
  • Việc nộp bài được thực hiện bằng cách mở pull request lên kho upstream

Cách tính leaderboard và chia sẻ trong cộng đồng

  • Việc đánh giá được thực hiện trên instance Hetzner Cloud CCX33
    • Cấu hình là 8 dedicated vCPU, 32 GB RAM
    • Đo thời gian chạy end-to-end bằng chương trình time
    • Mỗi bài nộp được chạy liên tiếp 5 lần
    • Lần chạy chậm nhất và nhanh nhất sẽ bị loại
    • Trung bình thời gian của 3 lần chạy còn lại là kết quả của bài nộp đó
    • Kết quả được thêm vào leaderboard
  • Thảo luận về các kỹ thuật tối ưu tiếp tục diễn ra trong mục discussion của kho GitHub
  • Ngoài ra còn có mục Show & Tell để chia sẻ các bản triển khai bằng ngôn ngữ ngoài Java; các bản 1BRC bằng Rust, Go, C++... đã được chia sẻ tại đây

Bài viết liên quan

2 bình luận

 
GN⁺ 2024-01-05
Ý kiến trên Hacker News

  • Lời giải hiện có vẻ nhanh nhất [0] dường như không tính đến va chạm băm, nên nếu trong bộ dữ liệu có đủ nhiều thành phố khác nhau thì có thể sẽ cho kết quả sai
    Không biết có phải tôi đang bỏ sót điều gì không
    [0] https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...

    • Đúng vậy. Hôm qua vấn đề này đã được nêu ra, và thực sự có hai lời giải dựa vào hàm băm được tinh chỉnh cho một bộ dữ liệu cụ thể, nên đã vi phạm quy tắc rằng phải hoạt động với mọi tên trạm quan trắc, nhưng đã bị bỏ sót trong lúc đánh giá
      Tạm thời các mục đó đã bị gỡ khỏi bảng xếp hạng, và hai tác giả đang sửa bài nộp nên sau đó sẽ được thêm lại
      [0] https://twitter.com/mtopolnik/status/1742652716919251052

  • Tôi nghĩ với cách tiếp cận sau thì có thể xử lý toàn bộ trong 0,3 giây
    Nhiệt độ chỉ có một chữ số thập phân nên trong thực tế chỉ cần khoảng 400 giá trị, và địa danh cũng hữu hạn ở khoảng 400 cái, vậy có thể tạo một bảng tra khoảng 160 nghìn tổ hợp nhiệt độ × địa danh
    Có thể tự động sinh một máy trạng thái ánh xạ 160 nghìn giá trị này vào các bucket duy nhất của bảng băm, bất kể chúng nằm ở vị trí xoay nào trong thanh ghi 4 byte, rồi trên thanh ghi trạng thái 32 bit thực hiện mỗi chu kỳ một lần tra bảng chuyển trạng thái và XOR với 4 byte tiếp theo
    Chỉ cần quét toàn bộ dữ liệu ở tốc độ bộ nhớ và tăng bộ đếm theo từng trạng thái; vì chỉ có 65K trạng thái nên các bộ đếm sẽ nằm gọn trong cache
    Với AVX512, có thể chạy song song 512 máy trạng thái 32 bit như vậy trên mỗi lõi, nên tính toán có lẽ sẽ không phải nút thắt cổ chai
    Các nhiệt độ quá cao/thấp hoặc địa danh không xác định không ánh xạ vào bucket hợp lệ thì chuyển sang mã chậm, và việc xử lý giá trị nhỏ nhất/lớn nhất cũng có thể làm qua kiểu escape này nên chỉ xảy ra vài nghìn lần
    Tôi nghĩ cách này có thể chạy ở tốc độ bộ nhớ chỉ với một lõi AVX512, nên không có nhiều lợi ích khi chia ra nhiều lõi

    • Không cần bảng tra. Yêu cầu chỉ là giá trị nhỏ nhất/trung bình/lớn nhất, nên có thể tính hết trong một lần duyệt mà không cần lưu dữ liệu
      Chỉ cần một bảng băm 400 mục, ba giá trị dấu phẩy động cho min/avg/max đang chạy, và một số nguyên đếm để cập nhật giá trị trung bình
      Kể cả nếu dùng 16 byte cho tên thì toàn bộ vẫn nằm trong 16KB
      Thời gian chạy sẽ chủ yếu bị chi phối bởi I/O, rồi đến phân tích JSON
    • Một lõi đơn không thể bão hòa băng thông bộ nhớ. Lõi bị giới hạn bởi mức song song của truy cập bộ nhớ và độ trễ
      Hầu hết chip máy chủ x86 hiện đại có thể retire 2 SIMD load mỗi chu kỳ, nên với AVX2 ở 1GHz có thể đạt khoảng 32GB/s; vì vậy không nhất thiết phải có AVX-512 để tối đa hóa băng thông trên mỗi lõi
      Nhưng nếu đọc từ DRAM thì sẽ chạm trần sớm hơn nhiều, thường là quanh mức 10–16GB/s trên máy chủ thông thường
      Miễn là phần lớn dữ liệu vẫn tràn ra RAM, thông lượng trên một lõi sẽ giảm mạnh, và với các tác vụ streaming lớn thì gần như lúc nào song song đa lõi cũng có lợi
      Có thể dễ dàng kiểm chứng bằng cách cấp phát một khối nhớ lớn hơn nhiều so với cache L3, tạo page fault trước, rồi chạy vector load đã được unroll trong một vòng lặp chặt (AVX2/AVX-512)
    • Trạng thái kế tiếp luôn phụ thuộc vào trạng thái trước đó, nên tôi không rõ có thể chạy song song máy trạng thái này như thế nào
      Tôi cũng thắc mắc sẽ diễn giải thanh ghi trạng thái ra sao. Khi XOR với 4 byte đầu vào thì với các địa danh không mong đợi, trên thực tế nó có thể trở thành bất kỳ giá trị nào trong khoảng 4,7 tỷ khả năng
      Ngay cả với các địa danh đã dự kiến, nếu dài hơn 4 byte thì chẳng phải sẽ cần nhiều trạng thái cho từng tên để phân biệt với các tên khác có cùng tiền tố sao?
    • Có lẽ cần xác nhận cách diễn giải quy tắc. Chưa rõ liệu mã được tối ưu cho 400 địa danh đã biết nhưng vẫn hỗ trợ tên bổ sung qua đường chậm có hợp lệ hay không
      Quy tắc nói rằng dù trình tạo dữ liệu có dùng một tập tên trạm cố định, mọi lời giải vẫn phải hoạt động với các tên trạm UTF-8 tùy ý
    • Muốn tìm địa danh thì rốt cuộc vẫn phải đọc và phân tích toàn bộ tệp

  • Thay vì bỏ lần chạy chậm nhất và nhanh nhất rồi lấy trung bình của ba lần còn lại, tôi nghĩ nên bỏ hai lần chậm nhất hoặc đơn giản là chấp nhận giá trị nhanh nhất
    Tôi không thấy có lý do chính đáng nào để loại bỏ kết quả chạy tốt

    • Đây là một cách đo khá tiêu chuẩn gọi là trung bình cắt ngọn (Trimmed Mean): https://statisticsbyjim.com/basics/trimmed-mean/
    • Có lý do để bỏ lần chạy tốt nhất. Nếu cho rằng hệ thống hoạt động có thể dự đoán được và chỉ thỉnh thoảng chậm đi vì tác vụ nền thì dùng lần chạy tốt nhất có thể hợp lý
      Nhưng nếu trong bản thân chương trình có dù chỉ một chút nguồn gây không xác định, điều này thực ra khá phổ biến, thì thời gian tốt nhất có thể không mang tính đại diện
      Bài viết này liên quan khá hay: https://tratt.net/laurie/blog/2019/minimum_times_tend_to_mis...
    • Nếu việc bỏ lần chạy nhanh nhất là không thể chấp nhận được, thì tôi thắc mắc vì sao lại đồng ý bỏ lần chạy chậm nhất

  • Theo cách nhìn quá bám luật, ở lần chạy đầu tiên người ta sẽ muốn bật một daemon chạy nền, nạp toàn bộ tệp vào bộ nhớ rồi giữ cố định, sau đó còn kéo sẵn cả cache để các lần chạy tiếp theo về cơ bản chỉ còn quét tuyến tính
    Việc tính trước kết quả ngay từ lần chạy đầu cũng có vẻ khả thi, tùy việc diễn giải luật theo hướng nới rộng đến đâu; thậm chí có thể parse số trước sang định dạng dày đặc hơn rồi ở các lần chạy sau đọc thẳng để cộng dồn
    Điều này hoàn toàn không đúng với tinh thần cuộc thi, nhưng theo phần luật nhìn thấy thì có vẻ cũng không bị cấm
    Nếu không thích tính toán trước, vẫn có thể dùng các tiểu xảo như sắp xếp đầu vào trước, parse trước, hoặc nén·sắp xếp·bố trí bộ nhớ đã sắp xếp
    Cực đoan hơn nữa, còn có thể vá script calculate_time để nó trả về 0 giây cho mình và trả về 9999 cho đối thủ

    • Nếu cung cấp cho người tham gia đúng tệp sẽ dùng thật trong cuộc thi thì sẽ phát sinh vấn đề thực sự
      Từ việc không thèm đọc đầu vào mà hardcode đáp án thành một dòng, cho tới việc xử lý dưới giả định không biết nội dung tệp, đều tồn tại vùng xám của tiền tính toán dài cỡ 1 tỷ nấc
      Cuộc thi có thể biến thành chuyện phân xử cái gì là tiền tính toán công bằng và cái gì thì không
      Vì thế các cuộc thi machine learning không cho người tham gia xem dữ liệu cuối cùng
    • Có vẻ việc này sẽ vi phạm quy tắc
      Phép tính phải diễn ra tại thời điểm ứng dụng chạy, và không được xử lý tệp đo ở thời điểm build rồi nhúng kết quả vào binary
    • Theo luật thì nên quy định rõ mỗi lần chạy đều diễn ra trên tmpfs riêng, và giữa các lần chạy phải xóa mọi tiến trình lẫn page cache

  • Có vẻ đây chẳng phải chỉ là bài toán bị khóa bởi tốc độ đĩa sao. Tôi nghi ngờ các tối ưu như SIMD hay multithreading có thực sự có ý nghĩa không
    Dù còn tùy số lượng trạm khác nhau và cách tra cứu hash, tôi vẫn hoài nghi liệu chúng có đủ lớn để đo ra được so với chi phí I/O hay không

    • Truy cập đĩa có thể song song hóa và NVMe rất nhanh, nên nút thắt có thể nằm ở CPU hơn là đĩa
      Các hệ thống được thiết kế với giả định phần cứng hiện đại đều tận dụng điểm này, và redpanda.com nơi tôi làm việc cũng là một ví dụ
      Parse chiếm phần lớn thời gian tính toán, và các kỹ thuật SIMD kiểu SWAR để tìm dấu phân cách có thể hữu ích
      Nếu muốn xem một triển khai gọn gàng của các thuật toán như vậy thì Stringzilla rất đáng xem: https://github.com/ashvardanian/StringZilla
      Về điểm tệp sẽ được cache hoàn toàn trong bộ nhớ sau lần chạy đầu, tôi đã trả lời ở đây: https://news.ycombinator.com/item?id=38864034
    • Cái này hoàn toàn phụ thuộc vào tải công việc và phần cứng. Ngay cả SSD tiêu dùng phổ thông cũng có thể dễ dàng duy trì 7GB/s (56Gbps) nếu chỉ dùng 700GB trong tổng 2TB
      Máy chủ thông thường có đủ lane PCIe để cắm 15 SSD như vậy, nên băng thông I/O của server gần ngang với băng thông bộ nhớ
      Máy chủ đắt tiền hơn còn có lane nhanh hơn như PCIe 5.0 và nhiều lane hơn
      Tệp này có 1 tỷ dòng nên khi nén chỉ khoảng 1GB, và sau lần chạy bỏ đi đầu tiên thì nó đã nằm trong bộ nhớ, nên trong kịch bản này băng thông I/O không quan trọng
      Kho GitHub ghi là 12GB chưa nén, nhưng điều đó vẫn chỉ xác nhận rằng băng thông I/O không quan trọng
    • Bài nói chuyện này của Daniel Lemire khá thú vị: https://www.youtube.com/watch?v=wlvKAT7SZIQ
      Ý chính là hiếm khi đĩa mới là nút thắt
    • Còn tùy hệ điều hành và hệ thống tệp. Tệp đầu vào khoảng 12GB và được chạy 5 lần trên máy có 32GB RAM, nên sau lần chạy đầu toàn bộ tệp có thể đã được cache trong bộ nhớ
      Ví dụ trên Linux dùng ext2 thì sau lần chạy đầu rất có thể toàn bộ tệp sẽ được cache, nhưng với ZFS thì có thể không
    • Muốn parse nhanh nhất thì có vẻ rõ ràng là nên đưa toàn bộ lên RAM rồi xử lý ngược từ cuối về đầu
      Khi đó chữ số sẽ xuất hiện theo thứ tự từ hàng thấp lên hàng cao, sau đó là dấu phân cách và chuỗi, rồi cứ thế cho đến khi gặp EOF hoặc ký tự xuống dòng

  • Theo luật, bài nộp phải hoạt động đúng với mọi đầu vào, nhưng đồng thời dường như cũng có nghĩa là có thể, và có lẽ nên, tinh chỉnh cho đầu vào cụ thể được tạo bởi create_measurements.sh
    Ví dụ, hoàn toàn có thể tưởng tượng ra một bài nộp dùng hàm băm hoàn hảo được tối ưu cho đúng tập trạm đã cho

    • Nếu có yêu cầu này thì khôn ngoan nhất là làm cho dữ liệu kiểm thử khác với dữ liệu ví dụ
      Như vậy mới tránh được các tối ưu kiểu overfitting
    • Vì UTF-8 mà việc này khó hơn nhiều. Nhưng nếu chỉ bám câu chữ của luật chứ không theo tinh thần của nó, thì cứ phát hiện byte nào lớn hơn 127 là lập tức chuyển sang triển khai chậm hơn
      Byte lớn hơn 127 có nghĩa là ký tự UTF-8 đa byte

  • Cho vui nên tôi thử so tốc độ awk với Java
    Đây là script dùng awk -F';' để cộng dồn tổng, số lượng, giá trị nhỏ nhất, lớn nhất theo từng trạm, rồi đến END thì tính trung bình và in ra

    • Tôi muốn xem so sánh tốc độ với file foreign data wrapper của PostgreSQL: https://www.postgresql.org/docs/current/file-fdw.html
      Cách làm là dùng file_fdw tạo bảng ngoài từ tệp CSV rồi GROUP BY station_name để tính MIN, AVG, MAX
    • Chạy bằng ClickHouse local thì ra khoảng 15.2 giây
      Trong clickhouse local, nó đọc file('measurements.txt', 'CSV', 'station String, t Float32'), nhóm theo từng trạm để tính min, max, avg, và chạy với max_threads = 8
      Phần lớn thời gian được dùng cho việc parse tệp
    • Biến sum có thể khá lớn nên dùng trung bình luồng sẽ tốt hơn
      Ví dụ như new_mean = ((n*old_mean)+temp)/(n+1)

  • Một thử thách thú vị, nhưng khá tiếc vì chỉ dành cho Java. Hóng đến lúc mọi người bắt đầu tự viết bytecode JVM bằng tay

    • Xem phần thảo luận thì có vẻ có bài nộp bằng nhiều ngôn ngữ khác nhau. Có Go, Rust, Python, C++ v.v.
      [0] https://github.com/gunnarmorling/1brc/discussions
    • Hoặc cũng có thể hiểu “phải viết bằng Java” là “phải dùng JVM để bắt đầu chạy”, và rõ ràng Java có thể gọi ra tiến trình khác

  • Khá vui. Cảm giác như phần hậu tiệc của Advent of Code
    Nếu muốn so sánh công bằng giữa các ngôn ngữ thì nên tính cả make và thời gian build. Tôi đã không dùng Java/Maven vài năm rồi, nhưng thấy ./mvnw clean verify tải xuống suốt 2 phút thì lại nhớ ra lý do

    • Thời gian build Java thực ra rất nhanh. Thứ đang được đo lúc này là tốc độ Internet
      Và trong các công cụ build biên dịch tăng dần thì Gradle nhanh hơn
    • Nếu tính cả thời gian build thì cũng nên tính cả thời gian lập trình, rồi chia cả hai cho số lần đoạn mã sẽ được chạy trong suốt vòng đời của nó
      Cũng nên cộng thêm một tỷ lệ phù hợp của thời gian bỏ ra để học lập trình
      Trong kiểu thử thách này, rất có thể một phiên bản cực kỳ ngây thơ sẽ thắng, điều đó không thực tế và theo tôi cũng đi ngược lại mục đích của thử thách
    • Tôi không hiểu tại sao lại clean
      Khác nào vứt cache đi rồi than là chậm
    • Không cần Maven
      Vì có ghi là không được dùng phụ thuộc bên ngoài

  • Trong môn C ở Đại học Kỹ thuật Séc từng có một bài tập rất giống thế này
    Tất cả bài nộp của sinh viên liên tục được chấm trên bảng xếp hạng, và để kiếm thêm điểm cho thành tích tốt hơn, thực chất là điểm địa vị, rất nhiều sinh viên đã dành hàng chục giờ để tối ưu hóa
 
dlehals2 2024-01-10

Hạng nhất là 6 giây nhỉ.. thật đáng kinh ngạc