Thử thách xử lý 1 tỷ dòng bằng Go: rút ngắn từ 1 phút 45 giây xuống 4 giây với 9 phương pháp

 (benhoyt.com)
35 điểm bởi GN⁺ 2024-03-04 | 6 bình luận | Chia sẻ qua WhatsApp
  • 1BRC: một thử thách viết mã để đọc các giá trị đo nhiệt độ từ một tệp văn bản có 1 tỷ dòng và tính nhiệt độ tối thiểu/trung bình/tối đa theo từng trạm quan trắc
  • Diễn ra từ ngày 1/1/2024 đến 31/1/2024, với mục tiêu tận dụng tối đa Java mới nhất
  • Từ đó, nhiều người bắt đầu quan tâm và thử sức bằng nhiều ngôn ngữ khác nhau (Rust, Go, C++, SQL)
  • Giới thiệu chi tiết 9 lời giải viết bằng Go (theo thứ tự từ chậm nhất đến nhanh nhất)

Mốc đo cơ bản

  • Dùng lệnh cat để đọc dữ liệu văn bản 1 tỷ dòng (13GB) mất 1.052 giây.
  • Lệnh wc thực sự xử lý tệp mất gần 1 phút (55.710 giây).
  • Dùng lời giải AWK để giải bài toán mất 7 phút 35 giây.

Lời giải 1: Go đơn giản và đúng phong cách

  • Lời giải đầu tiên dùng thư viện chuẩn Go mất 1 phút 45 giây.
  • Đọc từng dòng bằng bufio.Scanner và tách theo dấu ';' bằng strings.Cut.
  • Phân tích nhiệt độ bằng strconv.ParseFloat và dùng map của Go để cộng dồn kết quả.

Lời giải 2: Map với giá trị con trỏ

  • Dùng map[string]*stats để tránh phải băm hai lần trong map.
  • Sử dụng giá trị con trỏ giúp rút thời gian từ 1 phút 45 giây xuống 1 phút 31 giây.

Lời giải 3: Tránh strconv.ParseFloat

  • Dùng mã tự viết để phân tích nhiệt độ thay cho strconv.ParseFloat.
  • Rút thời gian từ 1 phút 31 giây xuống 55.8 giây.

Lời giải 4: Dùng số nguyên fixed-point

  • Biểu diễn nhiệt độ bằng số nguyên để tránh phép toán dấu phẩy động.
  • Rút thời gian từ 55.8 giây xuống 51.0 giây.

Lời giải 5: Tránh bytes.Cut

  • Thay vì quét toàn bộ tên trạm để tìm ';', thực hiện phân tích từ cuối chuỗi.
  • Rút thời gian từ 51.0 giây xuống 46.0 giây.

Lời giải 6: Tránh bufio.Scanner

  • Loại bỏ bufio.Scanner và đọc tệp theo các khối lớn.
  • Rút thời gian từ 46.0 giây xuống 41.3 giây.

Lời giải 7: Bảng băm tự cài đặt

  • Tự triển khai bảng băm thay vì dùng map của Go.
  • Rút thời gian từ 41.3 giây xuống 25.8 giây.

Lời giải 8: Xử lý song song theo khối

  • Song song hóa đoạn mã đơn giản, đúng phong cách để rút thời gian từ 1 phút 45 giây xuống 24.3 giây.

Lời giải 9: Kết hợp mọi tối ưu hóa và xử lý song song

  • Kết hợp mọi tối ưu hóa với xử lý song song để rút thời gian từ 24.3 giây xuống 3.99 giây.

Bảng kết quả

  • Có bảng so sánh tất cả lời giải Go cùng với các lời giải Go và Java nhanh nhất.
  • Bản Go nhanh nhất xử lý trong 2.90 giây, còn bản Java là 0.953 giây.
  • Bản Java mất chưa tới 1 giây là của Thomas Wuerthinger (người tạo ra GraalVM), có lẽ chỉ khả thi vì ông là chuyên gia trong lĩnh vực này.

Bình luận cuối

  • Trong công việc lập trình hằng ngày, mã đơn giản và đúng phong cách là điểm khởi đầu tốt.
  • Nếu xây dựng pipeline xử lý dữ liệu, việc làm cho mã nhanh hơn 4 lần hoặc 26 lần có thể tăng mức độ hài lòng của người dùng và tiết kiệm chi phí tính toán.
  • Nếu đang xây dựng runtime hoặc interpreter, cải thiện hiệu năng là rất quan trọng.

Ý kiến của GN⁺

  • Bài viết này cung cấp một nghiên cứu tình huống thú vị về tối ưu hiệu năng bằng cách khám phá nhiều cách tối ưu xử lý dữ liệu quy mô lớn với ngôn ngữ Go.
  • Bài viết cho thấy trong quá trình tối ưu, việc vượt ra ngoài thư viện chuẩn Go để tự cài đặt các cấu trúc dữ liệu như bảng băm đóng vai trò quan trọng.
  • Bài viết nhấn mạnh hiệu quả của xử lý song song, và việc kết hợp tối ưu hóa đơn lõi với song song hóa đã mang lại mức cải thiện hiệu năng đáng kinh ngạc.
  • Bài viết mang đến những góc nhìn hữu ích cho các kỹ sư phần mềm phát triển ứng dụng nhạy cảm với hiệu năng.
  • Mức độ hữu ích của các tối ưu hóa này trong môi trường production thực tế có thể khác nhau tùy theo từng trường hợp sử dụng. Không phải ứng dụng nào cũng cần mức tối ưu hóa như vậy.

Bài viết liên quan

6 bình luận

 
cosine20 2024-03-07

Mình khá tò mò ở bước 7 cụ thể đã thực hiện những công việc gì. Đây là đoạn hiệu năng được cải thiện cực kỳ nhiều luôn haha
 
sddsdd94 2024-03-06

Việc phân tách theo từng bước để thể hiện mức thời gian cải thiện hiệu năng khá thú vị nhỉ ha
 
galadbran 2024-03-05

Chỉ dùng wc thôi cũng mất 1 phút.... đúng là đỉnh cao vẫn là không cần viết code... haha
 
jhbaek 2024-03-05

Cảm ơn bạn đã chia sẻ bài viết hay. Nó làm tôi nhớ lại thời có lúc mình từng ám ảnh với việc tối ưu hóa hệ thống, haha.
Khi kinh nghiệm phát triển dày dạn hơn, tôi đã nhiều lần trải qua việc những đoạn mã được tối ưu đến mức tối đa lại rất khó bảo trì, nên trong môi trường tổ chức rất khó vận hành, vì thế dần dần tôi cũng rời xa con đường tối ưu hóa. (đột nhiên thành một đoạn hồi tưởng cá nhân)
 
misolab 2024-03-05

Đoạn mã được tối ưu hóa cho tổ chức!!
 
GN⁺ 2024-03-04
Ý kiến trên Hacker News
  • Người dùng đầu tiên cho biết vì họ không có kinh nghiệm tối ưu hóa mã cho việc xử lý dữ liệu, nên phần đầu tiên dùng cat, wc v.v. để lấy số đo cơ bản đặc biệt thú vị. Họ cho rằng đây là cách dễ dàng để có được một phạm vi “hợp lý”.
  • Người dùng thứ hai nhắc đến việc thời gian xử lý khi dùng thư viện Polars là 33 giây, đồng thời bày tỏ sự quan tâm đến giải pháp đơn giản nhất nhưng vẫn tiệm cận được lời giải tối ưu thủ công nhanh nhất.
  • Người dùng thứ ba nói rằng báo cáo phân tích hiệu năng của Go khá khó hiểu, và giải thích rằng khi thời gian thực thi của một dòng mã cụ thể không trực quan, có thể là do dữ liệu khó dự đoán và bộ dự đoán nhánh đã dự đoán sai.
  • Người dùng thứ tư chia sẻ kết quả thực hiện 1BRC (1 Billion Row Challenge) bằng Go và cho biết họ đã học được các kỹ thuật tối ưu hóa đặc trưng của Go. Ví dụ như đọc bộ nhớ không kiểm tra biên bằng unsafe.Pointer, các hàm trong các gói bytes và bits của thư viện chuẩn được viết bằng assembly, thiết lập để tắt garbage collector, và cách ghim goroutine vào thread.
  • Người dùng thứ năm cho rằng một lập trình viên shell script hẳn đã xử lý xong bộ dữ liệu 1 tỷ dòng cụ thể đó từ lâu trong lúc các lập trình viên ngôn ngữ khác còn đang chuẩn bị.
  • Người dùng thứ sáu lập luận rằng cơ sở dữ liệu nhanh hơn mã ứng dụng, ít phức tạp hơn và vững vàng hơn trước các cập nhật dữ liệu, đồng thời nhấn mạnh rằng nên thực hiện nhiều công việc hơn trong cơ sở dữ liệu.
  • Người dùng thứ bảy chia sẻ rằng vào năm 2010 họ đã phát triển một ứng dụng web dùng PostgreSQL để truy vấn 270 triệu dòng dữ liệu khí hậu của Environment Canada, và phần mềm này đã giành giải thưởng. Ứng dụng được tối ưu để có thể tạo báo cáo trong vòng chưa đầy 1 phút.
  • Người dùng thứ tám nhận xét rằng thật tuyệt khi mã song song trong Go vẫn giữ được phong cách mã mang tính thành ngữ của Go.
  • Người dùng thứ chín nói rằng khi xử lý các tệp văn bản lớn trên CLI, nếu bỏ qua việc phân tích Unicode thì awk, grep v.v. sẽ nhanh hơn hẳn, và cho rằng chỉ cần thêm LC_ALL=C vào lời giải awk là có thể rút thời gian xử lý xuống dưới 1 phút.
  • Người dùng cuối cùng nhận xét rằng thật thú vị khi phiên bản Java nhanh nhất còn nhanh hơn phiên bản Go nhanh nhất, và đánh giá hiệu năng của Java Virtual Machine (JVM) là rất tốt.