- Nút thắt cổ chai của 1BRC là phân tích cực nhanh 1 tỷ giá trị nhiệt độ trong CSV, và mã SWAR của merykitty từ Quân Anh Mai đã gây chú ý khi biến nhiệt độ thành số nguyên bằng các phép toán ALU cố định không cần
if
- Đoạn mã này dùng SWAR (SIMD Within A Register), xử lý đồng thời 8 byte chứa trong một
long, tức xử lý nhiều ký tự gần như song song ngay trong thanh ghi CPU thông thường
- Luồng xử lý lần lượt là phát hiện dấu âm, loại bỏ dấu, tìm vị trí dấu thập phân, căn chỉnh về dạng
XY.Z, chuyển ký tự ASCII thành chữ số, phép nhân ma thuật, rồi áp dụng dấu
- Định dạng đầu vào có 4 dạng
-XX.X, -X.X, X.X, XX.X; dựa trên vị trí dấu thập phân, các byte được dịch chuyển để đưa các chuỗi có độ dài khác nhau về cùng một bố cục bit
- Thay vì dùng nhánh và vòng lặp, mã tận dụng dày đặc đặc tính mã ASCII, bù hai, mặt nạ bit và tính chất dịch-cộng của phép nhân để đạt hiệu năng phân tích rất cao
Phân tích nhiệt độ, nút thắt cổ chai trong 1BRC
- Trong One Billion Row Challenge(1BRC), việc phân tích cực nhanh các giá trị nhiệt độ trong tệp CSV nổi lên như nút thắt cổ chai cốt lõi
- Chỉ riêng các tối ưu hóa trước đó cũng đã giúp mã Java song song kiểu thông dụng tăng tốc từ 71 giây xuống 1,7 giây
- Định dạng nhiệt độ thì đơn giản, nhưng khi phải phân tích 1 tỷ giá trị trong chưa tới 1 giây, ngay cả chi phí rất nhỏ cũng tích lũy thành đáng kể
- Các định dạng có thể có là
-XX.X, -X.X, X.X, XX.X
- Những người tham gia ban đầu dùng
Double.parseDouble(), nhưng về sau đã xuất hiện các bộ phân tích tùy biến không vòng lặp
- Một phần lời giải của Quân Anh Mai tại @merykitty xử lý bằng cách đọc một lượt một tệp mà không cần
if, và lan rộng như một thành phần gần như tiêu chuẩn trong các lời giải 1BRC hàng đầu
- Người chiến thắng Thomas Wuerthinger đã ghi nhận Quân Anh là một phần của nhóm đóng góp cho lời giải của mình
Mã của merykitty làm gì
- Mã nhận vào một
long chứa 8 byte đầu vào CSV và trả về giá trị nhiệt độ nguyên, bằng 10 lần nhiệt độ thực tế
- Đầu vào được đọc trực tiếp từ tệp CSV
mmap thông qua đọc bộ nhớ native; phần đó là một mối quan tâm riêng nên được tách ra
- Phép tính gồm 18 thao tác ALU theo thứ tự cố định
- dịch bit, AND, NOT, XOR
- cộng, trừ, nhân
Long.numberOfTrailingZeros()
numberOfTrailingZeros() dùng lệnh CPU đặc biệt thông qua intrinsic của trình biên dịch JDK- Vì nó không dùng các lệnh SIMD chuyên dụng mà xử lý nhiều byte bằng thanh ghi và lệnh CPU thông thường, nên đây là phương pháp SWAR
- Mã ví dụ đã được chỉnh nhẹ để dễ đọc hơn so với bản gốc; bản gốc nằm tại CalculateAverage_merykitty.java
Toàn bộ các bước xử lý
- Mã phân tích nhiệt độ theo thứ tự sau
- kiểm tra xem ký tự đầu tiên có phải
- hay không để phát hiện số âm
- nếu có ký tự dấu, biến byte đó thành 0
- tìm vị trí của dấu thập phân
.
- dịch các bit trong
long để các chữ số khớp với mẫu XY.Z
- chuyển ký tự ASCII thành giá trị số thực tế
- nhân từng chữ số với trọng số
1x, 10x, 100x rồi cộng lại
- cuối cùng áp dụng dấu
- Bề ngoài giống một bài toán phân tích ở mức cao, nhưng từng bước đều được thực hiện chỉ bằng các phép toán ALU
Bước 1: phát hiện dấu trừ
- Việc phát hiện dấu bắt đầu với đoạn mã sau
long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;
- Nếu đổi cách nhìn theo thứ tự mô tả thì có thể xem như
( ~(inputData << 59) ) >> 63
- Trong ASCII, dấu trừ
- có bit 4 bằng 0, còn các ký tự chữ số thì bit đó bằng 1; mã tận dụng tính chất này
- Khi dịch đầu vào sang trái 59 bit, bit phân biệt của ký tự đầu tiên được đưa lên bit cao nhất
- Sau khi đảo bit bằng NOT rồi thực hiện dịch phải số học 63 bit, bit cao nhất được lan ra toàn bộ
long
- Kết quả
broadcastSign sẽ có mọi bit bằng 1 nếu có dấu trừ, và mọi bit bằng 0 nếu không có
Bước 2: loại bỏ ký tự dấu
- Vì trạng thái âm/dương đã được lưu trong
broadcastSign, nên ký tự dấu được loại khỏi dữ liệu đầu vào
long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;
- Nếu
broadcastSign toàn 1, thì broadcastSign & 0xFF sẽ chỉ giữ 8 bit thấp nhất ở mức 1
- Đảo nó bằng NOT sẽ tạo ra một mặt nạ mà chỉ 8 bit thấp nhất là 0
- AND với
inputData sẽ xóa ký tự - ở byte thấp nhất
- Nếu không có dấu trừ,
broadcastSign bằng 0 nên mặt nạ sẽ là toàn 1 và các byte chữ số được giữ nguyên
Bước 3: tìm vị trí dấu thập phân
- Vị trí dấu thập phân được tính bằng đoạn mã sau
int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);
- Ký tự
. cũng giống dấu trừ ở chỗ bit 4 bằng 0
- Để chỉ kiểm tra bit 4 tại các vị trí có thể xuất hiện dấu thập phân, mã dùng mặt nạ
DOT_DETECTOR = 0x10101000
- Trong
negatedInput, tức đầu vào đã bị đảo bit, bit tương ứng với vị trí dấu thập phân sẽ thành 1
Long.numberOfTrailingZeros() trả về vị trí của bit 1 đó- Với ví dụ
-10.8, dấu thập phân nằm ở vị trí bit 28 nên dotPos = 28
Bước 4: căn chỉnh về mẫu cố định
- Dựa trên vị trí dấu thập phân, đầu vào được dịch sang trái để luôn khớp cùng một mẫu
long alignedToTemplate = withSignRemoved << (28 - dotPos);
0 0 0 Z . Y X 0
- Ở đây
X là hàng chục, Y là hàng đơn vị, Z là chữ số đầu tiên sau dấu thập phân
0 ở đây không phải ASCII "0" mà là byte có giá trị 0- Sau khi bỏ dấu, đầu vào có thể rơi vào một trong bốn bố cục sau
0 0 0 Z . Y X 00 0 0 0 Z . Y 00 0 0 0 Z . Y X0 0 0 0 0 Z . Y
- Với
-10.8, vì đã có dotPos = 28 nên độ dịch là 0
- Với
-7.7, dấu thập phân ở bit 20 nên đầu vào được dịch trái 8 bit, tức 1 byte, để đặt 0 vào vị trí của X
Bước 5: chuyển chữ số ASCII thành giá trị số
- Sau khi căn chỉnh, mã chỉ giữ lại phần giá trị số từ các ký tự ASCII
long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;
- Các chữ số ASCII từ
0 đến 9 có mã hexa từ 0x30 đến 0x39
- Chỉ cần giữ lại 4 bit thấp là mã ký tự sẽ trở thành giá trị số thực tế
- Một mặt nạ có
F tại đúng các vị trí chữ số trong mẫu sẽ được áp dụng
0 0 0 Z . Y X 0
000000F000F0F00
- Với ví dụ
-10.8, sau khi áp mặt nạ chỉ còn lại các giá trị thể hiện Z=8, Y=0, X=1
Bước 6: cộng gộp giá trị hàng bằng phép nhân ma thuật
- Giá trị tuyệt đối cuối cùng cần được tính là
100 * X + 10 * Y + Z
- Mã tận dụng tính chất phép nhân là tổ hợp của dịch và cộng để xử lý việc tính trọng số của nhiều chữ số chỉ bằng một phép nhân
- Trước hết, nếu chỉ nghĩ đến
X + Y + Z, ta có thể cộng các bản dịch của digits ở vị trí bit 0, 16 và 24 để gom tổng vào một vùng bit cụ thể
- Tổ hợp dịch-cộng này có thể được biểu diễn bằng phép nhân sau
0x1 + 0x10000 + 0x1000000
- Trong thực tế, trọng số của từng chữ số khác nhau nên
MAGIC_MULTIPLIER được tạo như sau
MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;
absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;
0x3FF là mặt nạ để tách riêng kết quả rộng 10 bit- Dù
100 * X có thể lớn tới mức 10 bit và chồng lấn với các bit lân cận, không gian bit cần thiết vẫn được đảm bảo nhờ tính chất hai bit bên phải của Y * 100 luôn bằng 0
- merykitty để lại chú thích
// That was close :) cho phần này
Bước 7: áp dụng dấu mà không cần nhánh
- Đến đây ta đã có giá trị tuyệt đối
absValue và thông tin dấu trong broadcastSign
broadcastSign hoạt động như 0 nếu số dương, và như -1 nếu số âm- Trong bù hai, số âm được biểu diễn bằng công thức sau
-n = NOT(n) + 1
- XOR có thể dùng như một phép NOT có điều kiện
n XOR -1 là NOT(n)n XOR 0 là n
- Phần
+1 tùy chọn được xử lý bằng -broadcastSign
temperature = (absValue ^ broadcastSign) - broadcastSign;
- Kết quả là không cần
if: số dương giữ nguyên, số âm được chuyển thành giá trị âm theo bù hai
Phần thưởng: tính vị trí bắt đầu của dòng CSV kế tiếp
- Trong toàn bộ lời giải 1BRC, còn cần phải tính rẻ vị trí bắt đầu của dòng CSV tiếp theo
- Vì sau dấu thập phân luôn có đúng một chữ số thập phân rồi tới ký tự xuống dòng, vị trí bắt đầu dòng kế tiếp được suy ra từ vị trí dấu thập phân
dotPos là vị trí theo bit, nên để chia cho 8 mã dùng dịch phải 3 bit
nextLineStart = (dotPos >>> 3) + 3;
+3 là để trỏ đến byte đầu tiên sau dấu thập phân, chữ số thập phân và ký tự xuống dòng
Kết luận
- Mã SWAR của merykitty phân tích thống nhất bốn định dạng chuỗi nhiệt độ chỉ bằng các phép toán bit cố định
- Cốt lõi nằm ở đặc tính bit của mã ASCII, việc căn chỉnh theo vị trí dấu thập phân, trích xuất chữ số bằng mặt nạ, cộng gộp giá trị hàng bằng phép nhân, và áp dụng dấu dựa trên bù hai
- Khi tách thành từng bước thì có thể lần theo cách nó hoạt động, nhưng việc ghép được tất cả những điều này chỉ trong vài ngày của một thử thách trực tuyến vẫn là điều đặc biệt ấn tượng
1 bình luận
Ý kiến trên Hacker News
Hơn 2 năm trước, tôi đã nhận ra rằng byte array view var handle khá phù hợp để tạo các routine SWAR hiệu quả trong Java/Scala
Ở đây cũng có nhiều ví dụ dùng SWAR như phân tích chuỗi Base16/64,
java.time.*, phân tích trực tiếp giá trị số từ mảng byte: https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...Giá trị lớn của một parser đã được rèn giũa trong thực tế nằm ở kiểm tra lỗi và phục hồi một cách hiệu quả
Và tôi cũng tò mò cần bao nhiêu công sức để phát hiện và trả về một giá trị lỗi sentinel nào đó như phong cách code hiện tại
Dù chưa thú vị đến mức tôi tự làm thử ;-)
MULđể dịch/cộng là một cách khá quen thuộcXem bài của Lemire: https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui...
Bài báo: https://arxiv.org/abs/1902.08318
Github: https://github.com/simdjson/simdjson
Hơn nữa, 1BRC chính thức đã ghi rõ rằng để loại hoàn toàn tốc độ I/O, kết quả được đánh giá trên RAM disk: https://github.com/gunnarmorling/1brc?tab=readme-ov-file#eva...
“Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant)”
Theo hiểu biết hạn chế của tôi, một file văn bản lớn được đưa tuần tự vào L1 và mỗi giá trị được đọc một lần. Trên đa số bộ xử lý, có thể thực hiện hai lần đọc như vậy mỗi chu kỳ. Phần chậm sẽ là đưa dữ liệu từ RAM vào L1, nhưng đọc tuần tự thì khá nhanh
Sau đó mỗi lần đọc được xử lý. Nhìn qua, trong phiên bản đã tối ưu, có vẻ mất khoảng 4 chu kỳ. Sau đó cần ghi kết quả vào đâu đó, và có lẽ trước đó còn cần một hoặc hai lần đọc ngẫu nhiên. Bạn xem phần này là nút thắt I/O à?
Tôi không nói việc bị giới hạn bởi CPU là hiển nhiên, nhưng điều ngược lại cũng có vẻ không hiển nhiên
Sửa: tôi đã không tính đến khả năng ý bạn là “I/O đĩa”. Như những người khác đã nói, ở đây về cơ bản nó không phải yếu tố đáng kể
Tức là toàn bộ dữ liệu nằm trong RAM, chính xác hơn là trong page cache
Nếu nhớ không nhầm thì xử lý overflow khá khó. Tôi rất thích bài này
Vẫn còn những người thực sự biết lập trình CPU và hiểu mình đang làm gì
Bí ẩn thật sự là phần lớn những người tự gọi mình là lập trình viên lại thiếu hiểu biết sâu, thậm chí dường như còn không biết rằng mình thiếu hụt nghiêm trọng
Việc nó thực sự hoạt động tốt có thể thấy ở lời giải C# có vẻ là nhanh nhất trong số các lời giải 1BRC đã công bố cho đến nay: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
Vấn đề là chi phí dựng vector ban đầu và trích xuất kết quả có quá lớn hay không
Tuy nhiên tôi nghi ngờ HotSpot có tự làm được không, và còn một chuyện riêng là phần lớn submission 1BRC được chạy bằng Graal để giảm overhead khởi động
SSE2 cơ bản không có phép nhân 32-bit hay 64-bit nên phép nhân 32×32→64-bit là vấn đề, nhưng SSE4.1 đã thêm đúng
pmuldqcần thiết. Tuy nhiên kết quả là 64-bit, nên để xử lý cả vector số nguyên 32-bit thì cần thực hiện thao tác này hai lầnNgoài ra trường nhiệt độ có độ dài biến thiên, nên ngay cả khi được lưu theo cột cũng có khả năng không có lợi
Tuy vậy, SSE đã được áp dụng thành công cho việc tìm dấu phân cách giữa tên và nhiệt độ