Thuật toán SIMD được thiết kế lại từ đầu

 (mcyoung.xyz)
2 điểm bởi GN⁺ 2023-11-29 | 1 bình luận | Chia sẻ qua WhatsApp
  • Codec base64 vb64 được tạo bằng std::simd của Rust cho thấy để có mã SIMD nhanh và có tính di động, cần thiết kế lại cách bố trí dữ liệu và luồng tính toán như một mạch điện, thay vì chỉ vector hóa nguyên xi vòng lặp thủ tục
  • Tối ưu hóa cốt lõi là giảm stall do nhánh và truy cập bộ nhớ, đồng thời tạo cấu trúc branchless thực hiện cùng một phép toán bất kể đầu vào bằng compare, mask, select và shuffle
  • Trong giải mã base64, để biến ký tự ASCII thành sextet, tác giả tạo một perfect hash bằng byte >> 4 và hiệu chỉnh /, rồi dùng lookup table nằm trong vector SIMD cùng shuffle để tìm offset
  • Khi đóng gói bốn sextet 6 bit thành ba byte, tác giả mở rộng lane lên u16 rồi shift, sau đó tách low/high byte và dùng rotate_lanes_left cùng OR để ghép các mảnh byte từ các lane kề nhau
  • Trong benchmark, sau khi kết hợp -Zbuild-std, -Ctarget-cpu=native, N = 32 và tối ưu tải phần remainder, hiệu năng đạt xấp xỉ gấp đôi so với triển khai base64 baseline trên crates.io ở gần như toàn bộ dải thử nghiệm

Bối cảnh vật lý khiến SIMD trở nên cần thiết

  • Việc cải thiện hiệu năng máy tính không chỉ liên quan đến khoa học máy tính lý thuyết mà còn gắn trực tiếp với các ràng buộc vật lý
  • Tính đến năm 2023, Moore’s law có vẻ vẫn còn đúng, nhưng trong khoảng 15 năm qua, hiệu ứng Dennard scaling đã sụp đổ, khiến transistor dày đặc hơn kéo theo mật độ tiêu thụ điện năng tăng lên
  • Sau khi việc tiếp tục tăng xung nhịp trở nên khó khăn, từ đầu những năm 2000, hướng chính để nâng hiệu năng đã chuyển sang sử dụng nhiều lõi hơn
  • Đa luồng đòi hỏi sự phối hợp giữa các lõi nên phát sinh chi phí đồng bộ hóa, còn các luồng điều khiển như jump, gọi hàm ảo hay đồng bộ hóa đều gây stall
  • Có hai nguyên nhân chính gây stall
    • Nhánh: luồng điều khiển như if, vòng lặp, gọi hàm, trả về từ hàm, hay switch trong C
    • Tác vụ bộ nhớ: load/store, đặc biệt là các truy cập không thân thiện với cache

Mã thủ tục và song song mức lệnh

  • Các lõi CPU hiện đại không thực thi mã từng dòng một, mà phát hành đồng thời các phép toán không phụ thuộc lẫn nhau
  • Những phép toán không phụ thuộc nhau như a = x + y và b = x ^ y có thể sử dụng đồng thời mạch add và xor
  • Cách này được gọi là song song mức lệnh, và các phụ thuộc cản trở nó được gọi là data hazard
  • CPU càng bão hòa tốt các functional unit thì càng xử lý được nhiều phép toán hơn trong mỗi đơn vị thời gian
  • Nhánh phải chờ tính điều kiện xong mới có thể nạp lệnh tiếp theo, còn tác vụ bộ nhớ phải chờ dữ liệu thực sự đến được CPU nên gây stall
  • GPU xử lý hình ảnh dưới dạng pixel vector và thường thực hiện nhiều phép toán có tính cục bộ cao, nên gần với một cỗ máy SIMD được thiết kế cho xử lý theo lô và luồng điều khiển hạn chế
  • SIMD là single instruction, multiple data, tức một lệnh thực hiện tính toán song song trên nhiều lane dữ liệu

Tư duy theo đơn vị lane

  • SIMD và vector thường được dùng gần như cùng nghĩa, và đơn vị cơ bản của lệnh SIMD là vector: một mảng số có kích thước cố định
  • Mỗi thành phần của vector được gọi là một lane
  • Vector SIMD phải nằm trong thanh ghi nên thường khá nhỏ
    • Trong môi trường ví dụ, độ rộng vector tối đa là 256 bit
    • Tương ứng với 32 byte của u8x32 hoặc 4 số double của f64x8
  • Ngay cả vector nhỏ cũng có thể cải thiện độ trễ tương ứng nếu giúp giảm gánh nặng bão hòa pipeline đi 4 lần

Chia để trị qua ví dụ popcnt

  • Phép toán vector đơn giản nhất là bitwise and/or/xor
  • Nếu nhìn từ góc độ bitwise, số nguyên thông thường cũng có thể được xem là vector các lane 1 bit
    • Theo cách nhìn này, i32 tương đương i1x32
  • popcnt là phép đếm số bit 1 trong một số nguyên, và nếu xem i32 là i1x32 thì đây là một phép reduce
  • Cách cài đặt ngây thơ bằng cách tách 32 bit thành mảng rồi cộng lại có thể tạo ra mã kém chất lượng
  • Cách tốt hơn là cộng các cặp bit kề nhau, rồi cộng các cặp của các cặp, đồng thời tăng độ rộng lane khi cộng dồn
    • Dùng mặt nạ 0x55555555, 0xaaaaaaaa để tách bit chẵn/lẻ
    • Canh lane bằng shift rồi cộng
    • Sau đó lặp lại theo đơn vị 2 bit, 4 bit, 8 bit và 16 bit
  • Cách cài đặt này không được tối ưu thành lệnh popcnt, nhưng vẫn cho mã nhỏ và nhanh trên các hệ thống không có lệnh đó
  • Với u64, chỉ cần thêm một bước reduction nữa là áp dụng được, không cần phép cộng u64 toàn phần
  • Cách tiếp cận chia để trị này là một mẫu cốt lõi trong lập trình SIMD

Các công cụ chính trong tập lệnh SIMD

  • Vector SIMD thực tế mang ngữ nghĩa phức tạp hơn scalar, và những chức năng dùng để thay thế luồng điều khiển chậm đặc biệt quan trọng
  • Các lệnh khả dụng phụ thuộc rất nhiều vào kiến trúc
    • Nhiều lõi hiệu năng cao trên x86 triển khai AVX2
    • AVX2 cung cấp vector ymm 256 bit
    • Bản thân thanh ghi không có số lane; chính lệnh quyết định cách diễn giải lane
    • Ví dụ, vpaddb diễn giải ymm là i8x32
  • Các phép toán thường có sẵn gồm
    • Phép toán bitwise: độ rộng lane mặc định ngầm hiểu luôn là 1 bit
    • Số học theo lane: cộng, trừ, nhân, chia, shift số nguyên, min/max, v.v.
    • So sánh theo lane: tạo mask vector như m[i] = a[i] < b[i]
    • select: dùng mask để chọn giá trị theo từng lane từ hai vector
    • shuffle/swizzle: coi một vector như lookup table và sắp xếp lại lane bằng vector chỉ số
  • Giá trị true/false trong mask vector thường dùng mẫu bit all-ones hoặc all-zeros
  • Compare và select là các công cụ cốt lõi giúp mã SIMD duy trì trạng thái branchless
  • Mã branchless thực hiện cùng một phép toán bất kể đầu vào, rồi loại bỏ kết quả không cần bằng các tính chất như x * 0 = 0, a ^ b ^ a = b

Căn chỉnh vị trí dữ liệu bằng shuffle

  • Shuffle là công cụ cốt lõi trong SIMD để đưa dữ liệu về “đúng vị trí”
  • Broadcast hoặc splat tạo ra vector mà mọi lane đều mang cùng một scalar, và có thể biểu diễn bằng shuffle chỉ số [0, 0, ...]
  • Interleave hoặc zip/pack xen kẽ các lane của hai vector a, b
    • c = [a[0], b[0], a[1], b[1], ...]
    • Có thể cài đặt bằng shuffle2
  • Deinterleave hoặc unzip/unpack là thao tác ngược lại của interleave
  • Rotate xoay lane theo dạng b[i] = a[(i + j) % n], và đây cũng là một dạng shuffle
  • Trong lập trình SIMD, người ta thường xuyên diễn giải lại và sắp xếp lại các khối dữ liệu lớn hơn số nguyên thành các khối nhỏ với nhiều kích thước khác nhau

intrinsics, target feature, portable SIMD

  • Các phép toán có thể dùng trong SIMD thay đổi tùy theo kiến trúc và instruction set extension
  • x86 có thể có những phép toán mà ARM không có, và ngay cả trong cùng một nhà cung cấp cũng có những phần mở rộng chỉ xuất hiện trên chip máy chủ cao cấp như Intel AVX-512
  • Toolchain khái quát hóa các phần mở rộng này thành target feature
    • lscpu trên Linux hiển thị các feature mà CPU nhận diện
    • LLVM chọn lệnh khác nhau tùy theo thiết lập feature
    • Phải có +avx2 thì LLVM mới có thể sinh mã dùng ymm
  • -march=native hoặc -Ctarget-cpu=native có thể tạo ra mã tốt phù hợp với máy dùng để build, nhưng tính di động sang bộ xử lý khác có thể giảm
  • Runtime feature detection là cách kiểm tra các tính năng CPU hỗ trợ để quyết định gọi phiên bản hàm nào, và được dùng trong các đoạn mã phân phối trên nhiều thiết bị như thư viện mã hóa
  • Mã SIMD trong C++ thường dùng intrinsics như _mm256_cvtps_epu32
    • Biểu diễn các phép toán mức thấp của một instruction set cụ thể
    • Không nhất thiết ánh xạ thành một lệnh đơn
    • Trình biên dịch có thể thực hiện tối ưu như hợp nhất, loại bỏ trùng lặp và chọn lệnh
  • Nếu phải lặp lại mã tương tự cho nhiều instruction set, lợi thế bảo trì so với assembly có thể không còn lớn
  • Thư viện portable SIMD là cách tiếp cận xử lý một phần việc chọn lệnh ở cấp thư viện, phần còn lại giao cho trình biên dịch
  • Cài đặt vb64 là một thử nghiệm để kiểm tra xem portable SIMD của Rust có sinh ra mã đủ cạnh tranh hay không

chuyển giải mã base64 sang SIMD

  • base64 là cách mã hóa dữ liệu nhị phân tùy ý thành ASCII
  • Xem dãy byte đầu vào như một vector bit rồi chia thành các sextet là những chunk 6 bit
  • Giá trị sextet được ánh xạ sang các ký tự sau
    • 0..25 → 'A'..'Z'
    • 26..51 → 'a'..'z'
    • 52..61 → '0'..'9'
    • 62 → +
    • 63 → /
  • base64 có nhiều biến thể, nhưng phần lớn độ phức tạp là giống nhau
  • Có hai điểm cần chú ý
    • base64 là định dạng mà các bit trong byte theo kiểu big endian
    • Độ dài đầu vào có thể không chia hết cho 4, và về nguyên tắc sẽ được đệm bằng = để thành bội số của 4, nhưng cũng có thể xử lý các thông điệp có phần đệm không đúng
  • decoded length được tính bằng input / 4 * 3, rồi cộng thêm phần độ dài dư theo input % 4

refactor cơ bản hướng tới branchless

  • Bộ giải mã base64 đơn giản có nhiều nhánh
    • Vòng lặp duyệt đầu vào theo chunk
    • Vòng lặp byte bên trong chunk
    • match theo từng ký tự ASCII
    • return Err khi có lỗi
    • match bên trong decoded_len
    • Vec::extend_from_slice và khả năng gọi allocator
  • Chỉ dẫn tối ưu là loại bỏ mọi nhánh
  • match trong decoded_len ánh xạ các giá trị input % 4 là 0, 1, 2, 3 thành 0, 1, 1, 2
  • Đổi nó thành mod4 - mod4 / 2 sẽ cho phiên bản branchless
  • LLVM vốn có thể gấp match này thành switch table, nhưng ở vùng này truy cập bộ nhớ không cần thiết sẽ làm giảm hiệu năng

tách vòng lặp nóng nhất

  • Điểm mạnh của SIMD là xử lý nhiều dữ liệu cùng lúc để unroll vòng lặp mạnh và đưa nó đến gần branchless
  • Mục tiêu của hot loop là đọc tối đa 4 byte, tạo tối đa 3 byte kết quả giải mã, đồng thời cho biết có lỗi cú pháp hay không
  • Có ba sự thật có thể tận dụng
    • Độ dài đầu ra có thể tính bằng decoded_len() dạng branchless
    • Có thể xem base64 không hợp lệ là đường đi rất hiếm, và nếu cần vị trí lỗi thì có thể quét lại sau đó
    • Trong base64, A là 0 nên có thể đệm chunk bị cắt cụt bằng A mà không làm thay đổi giá trị
  • decode_hot() được tách ra thành dạng xử lý bốn byte đầu vào rồi trả về kết quả giải mã và một giá trị bool cho biết thành công hay không
  • Trả về bool riêng thay vì Option<[u8; 3]> giúp dễ loại bỏ nhánh if !ok về sau
  • Trong phiên bản SIMD, đầu vào là Simd<u8, 4>, và đầu ra cũng để là Simd<u8, 4> cho phù hợp với số lane là lũy thừa của hai
    • Đầu ra thực sự cần chỉ là 3 byte
    • Lane cuối cùng không được dùng

cách chuyển ASCII thành sextet

  • Phần lớn match chuyển ký tự ASCII thành sextet có thể biểu diễn dưới dạng byte - C
    • 'A'..'Z' → byte - 'A'
    • 'a'..'z' → byte - 'a' + 26
    • '0'..'9' → byte - '0' + 52
    • '+' → byte - '+' + 62
    • '/' → byte - '/' + 63
  • Chỉ cần tạo vector offset theo từng lane rồi thực hiện ascii - offsets
  • Cách tiếp cận đầu tiên là compare-and-select
    • Tạo mask cho A-Z, a-z, 0-9, +, /
    • Lane nào không được mask nào chọn thì bị coi là invalid
    • Splat offset tương ứng với từng mask rồi ghép lại bằng OR
  • Cách này gọn đẹp và có thể tạo ra mã cạnh tranh, nhưng cần tổng cộng 8 phép so sánh và có thể tạo register pressure vì có nhiều giá trị còn sống

bảng băm SIMD và perfect hash

  • Các dải byte của A-Z, a-z, 0-9 lần lượt là 0x41..0x5b, 0x61..0x7b, 0x30..0x3a, và chúng có high nibble khác nhau
  • + và / là 0x2b, 0x2f, nên chỉ với byte >> 4 đã có thể phân biệt được phần lớn trường hợp
  • Với trường hợp /, trừ đi 1 sẽ tạo thành một perfect hash theo các dải này
  • Ánh xạ của (byte >> 4) - (byte == '/') như sau
    • A-Z → 4 hoặc 5
    • a-z → 6 hoặc 7
    • 0-9 → 3
    • + → 2
    • / → 1
  • Giá trị này đủ nhỏ để đặt bảng tra offset vào trong một vector SIMD và lookup bằng shuffle
  • Ý tưởng perfect hash này do một người dùng ẩn danh trong GitHub issue đưa ra
  • Simd::swizzle_dyn() có ràng buộc là mảng chỉ số và độ dài bảng tra phải bằng nhau
  • Trong cách perfect hash, quá trình tính sextet không đồng thời cho ra validation như một tác dụng phụ, nên dùng exact bloom filter từ cùng GitHub issue đó để kiểm tra tính hợp lệ của byte
  • Ví dụ cài đặt có trong simd.rs của vb64

đóng gói bốn sextet thành ba byte

  • Bước gộp bốn sextet 6 bit thành ba byte phức tạp hơn
  • Nếu đặt một sextet đầu vào cụ thể thành all-ones rồi kiểm tra các bit dịch chuyển đến đâu trong đầu ra, có thể lần theo quan hệ sắp xếp
  • Chỉ dùng shuffle theo đơn vị byte là không đủ
    • Đích cần dịch chuyển là các mảnh của byte
    • Chỉ shift cũng không đủ
    • Các bit bị overshift phải chuyển sang lane lân cận
  • Cách giải là làm cho lane lớn hơn
  • Cast sextets sang vector u16, rồi shift từng lane
    • input[0] dịch 2 bit
    • input[1] dịch 4 bit
    • input[2] dịch 6 bit
    • input[3] điều chỉnh bằng dịch 8 bit
  • Tách vector low byte và high byte từ kết quả shift
  • Dùng hi.rotate_lanes_left::<1>() để đưa các mảnh phía high byte sang đúng lane lân cận, rồi gộp bằng lo | hi_rotated
  • Cách này tận dụng mạnh các hardware primitive nên mã ngắn gọn và hiệu quả

Mở rộng số lượng lane và loại bỏ garbage lane

  • Simd<u8, 4> còn nhỏ hơn cả thanh ghi vector 128-bit tối thiểu của x86, nên decode_hot() được viết generic theo số lane N
  • Ràng buộc LaneCount<N>: SupportedLaneCount đảm bảo số lane là lũy thừa của hai ở kích thước nhỏ
  • Bảng tra cứu và bảng shift dùng helper tiled() để tạo vector mẫu lặp lại
  • Với N = 4, chỉ cần bỏ qua giá trị rác ở lane cuối, nhưng khi N lớn hơn thì garbage sẽ lẫn vào ở mọi lane thứ tư
  • Để loại bỏ chúng, dùng shuffle
    • Quan hệ mong muốn là shuffled[i] = output[i + i / 3]
    • Bỏ qua ở mỗi chỉ số thứ tư để xóa garbage lane
    • Phần bị tràn nằm ở 1/4 trên của vector đầu ra cuối cùng nên có thể bỏ qua
  • Làm như vậy thì có thể giải mã song song 32 byte base64 bằng decode_hot::<32>()

Tối ưu outer loop

  • decode() cũng được chuyển thành generic theo số lane nội bộ N
  • Chi phí còn lại gồm những phần sau
    • Nhánh so sánh độ dài trong for chunks in ...
    • memcpy có độ dài biến thiên của [T]::copy_from_slice
    • Nhánh ok ở mỗi vòng lặp
    • Khả năng gọi allocator của Vec::extend_from_slice và thêm một memcpy nữa
  • Vì đã biết độ dài đầu ra, nên cấp trước dung lượng bằng out.reserve(final_len + N / 4)
  • Thêm vào đó chừa vùng slop để thực hiện full SIMD store thay vì memcpy có độ dài biến thiên
  • Mỗi iteration ghi toàn bộ vector SIMD, và lần ghi tiếp theo dịch đi 3/4 * N để ghi đè các byte garbage trước đó
  • Các byte garbage cuối cùng không được tính vào Vec::set_len() cuối cùng, nên được xem như đã bị xóa
  • Dù có early return vì if !ok, do chưa commit bằng set_len() nên out vẫn giữ nguyên trạng thái chưa bị sửa đổi

Dời xử lý lỗi ra ngoài hot loop

  • Thay vì return bằng if !ok ở mỗi iteration, lỗi được tích lũy bằng error |= !ok
  • Chỉ kiểm tra có lỗi hay không một lần ngay trước set_len() cuối cùng
  • Với giả định rằng phần lớn blob base64 là hợp lệ, đường đi xử lý lỗi được đẩy ra ngoài hot loop
  • Ngay cả khi có lỗi cú pháp, các phép toán SIMD phía sau cũng không tự ý hoạt động sai, nên các lần ghi garbage sẽ không được commit và sẽ biến mất
  • Sau đó các lời gọi như Vec::push() có thể ghi đè lại cùng vùng bộ đệm đó

Unroll and jam và xử lý remainder

  • Để giảm memcpy có độ dài biến thiên của copy_from_slice, áp dụng unroll and jam
  • Chia vòng lặp thành hai phần
    • hot vectorized loop: luôn chỉ xử lý đầu vào độ dài N
    • cold remainder part: xử lý đầu vào i < N nhiều nhất một lần
  • Dùng Iterator::chunks_exact() của Rust để triển khai unroll-and-jam viết tay
  • Trong hot loop, gọi Simd::from_slice() để thực hiện một lần nạp dữ liệu có kích thước đúng bằng một vector
  • Bounds check trở thành dạng mà trình biên dịch dễ loại bỏ hơn

Benchmark và tối ưu nạp dữ liệu thủ công

  • Benchmark giải mã các thông điệp có độ dài từ 0 đến khoảng 200 hoặc 500 byte, rồi so sánh với triển khai base64 baseline trên crates.io
  • Tùy chọn biên dịch dùng -Zbuild-std và -Ctarget-cpu=native
  • Sau khi tinh chỉnh, N = 32 cho kết quả tốt nhất, và mỗi iteration của hot loop dùng một thanh ghi YMM
  • Ban đầu đã vượt baseline, nhưng xuất hiện dao động hiệu năng dạng heartbeat tương quan mạnh với data.len() % 32
  • Sau khi kiểm tra assembly, tác giả cho rằng copy_from_slice đã bị inline/unroll thành một vòng lặp load theo từng byte
  • Cũng thử Simd::gather_or(), nhưng vì tạo ra assembly tệ hơn nên không dùng
  • Thay vào đó, viết một hàm nạp dữ liệu thủ công cho dữ liệu có độ dài biến thiên
    • Phần hot thực hiện các scalar load lớn nhất có thể là load u128 trong vòng lặp
    • LLVM hạ các chunk 16 byte này thành load XMM
    • Phần remainder dùng các load u64, u32, u8 chồng lấn lên nhau
  • Khi đọc 15 byte, đọc u64 tại p và u64 tại p + 7 để chồng lấn 1 byte, rồi ghép bằng OR
  • Với 4~7 byte, dùng các load u32 chồng lấn
  • Với 1~3 byte, đọc tại p, p + len/2, p + len - 1; có thể load trùng một số byte nhưng giảm được số nhánh
  • Sau khi áp dụng mã nạp dữ liệu mới, độ biến thiên giảm đi rất nhiều và gần như toàn bộ dải đều cho hiệu năng gấp 2 lần so với baseline

Encoding và base64 web-safe

  • Hàm encoding chỉ cần triển khai encode_hot(), thực hiện ngược lại các phép toán của decode_hot()
  • Perfect hash dùng trong giải mã không phù hợp cho encoding, nên cần một hash mới
  • Mã loading/storing xung quanh encoder cũng hơi khác decoder
  • vb64 cũng triển khai một routine encoding hiệu quả
  • Base64 web-safe là biến thể thay + và / bằng - và _
  • Việc xây dựng perfect hash cho base64 web-safe phức tạp hơn; ví dụ có thể cần cách như (byte >> 4) - (byte == '_' ? '_' : 0)
  • vb64 hiện vẫn chưa hỗ trợ base64 web-safe

Kết luận

  • Tác giả nói rõ vb64 không phải là thư viện nhằm giải quyết một nút thắt cổ chai quan trọng, và cũng không biết nơi nào thực sự bị nghẽn bởi base64 decoding
  • Mã branchless thường hơi quá tay, nhưng giúp hiểu được những gì trình biên dịch có thể và không thể làm
  • std::simd của Rust nhìn chung khá tốt và sinh ra mã rất chất lượng
  • Dù vẫn có một vài rough edge mà tác giả muốn được cải thiện để mã SIMD đơn giản hơn, họ đánh giá hài lòng với kết quả hiện tại
  • SIMD và tối ưu hiệu năng là chủ đề phức tạp, đòi hỏi nhiều mẹo và kiến thức phần cứng, trong đó phần lớn còn chưa được tài liệu hóa

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-11-29
Ý kiến trên Hacker News

  • Thấy việc dùng portable SIMD trong thực tế khá thú vị; tôi thử tái hiện benchmark trên hệ thống Zen 3 thì cũng thu được mức tăng tốc tương tự
    Trên M1 MacBook Pro, với độ dài đầu vào 110 byte, mức cải thiện hiệu năng bắt đầu từ 1,4 lần rồi tăng dần lên 2 lần; thấp hơn x86_64 nhưng có vẻ đã đạt mục tiêu
    Tuy nhiên nhìn vào code thì nó xác nhận trải nghiệm của tôi rằng Rust có ergonomics khá tệ trong các thao tác liên quan đến SIMD và con trỏ, rộng hơn là trong performance engineering

    • Ở góc nhìn kỹ sư Rust thì tôi đồng ý ở một mức độ nào đó, nhưng thao tác với con trỏ và bộ nhớ thô bị hạn chế có chủ ý vì lý do an toàn, và có mặt là ngôn ngữ buộc bạn thật sự phải nghĩ về điều mình đang làm
      Dù vậy, portable SIMD của Rust vẫn chưa phải là câu chuyện hay so với C++; nếu muốn đi xuống vùng byte thô, con trỏ và thao tác buffer thì phải quen với Pin, MaybeUninit, v.v.
      portable_simd và allocator_api đã ở trạng thái unstable nhiều năm, rào cản gia nhập cũng cao và còn gượng gạo hơn, nhưng phần lớn là thiết kế có chủ ý
      Tuy nhiên không có gì ngăn bạn tự tạo abstraction dễ dùng hơn trong chương trình của mình, hoặc dùng crate bên thứ ba
    • Tôi không đồng ý rằng ergonomics tệ
      SSE intrinsic trong C++ còn tệ hơn nhiều: dấu gạch dưới trông xấu và tên cũng khó nhớ

  • Tôi đã cố hết sức triển khai bằng C++ cổ điển, rồi thỉnh thoảng thật sự bất ngờ khi ai đó mang đến phiên bản SIMD nhanh hơn hơn 10 lần
    Đổi lại, code đó kém portable hơn
    Tôi mong auto-vectorization của compiler tốt hơn nữa, và cũng mong có hỗ trợ kiểu annotation ở cấp ngôn ngữ để cho phép cục bộ việc sắp xếp lại một số phép toán

    • Code SIMD tốt phải cân nhắc rất kỹ dữ liệu được bố trí trong bộ nhớ như thế nào
      Compiler không thể thay bạn sửa dữ liệu ngoài một ngữ cảnh rất cục bộ, nên auto-vectorization trở nên thật sự khó
    • Ngay cả khi compiler có thể tối ưu hoàn hảo, vẫn có nhiều bảo đảm tuần tự không thể tránh
      Ví dụ trong for(double v: vec) sum+=v, phép cộng số thực dấu phẩy động không có tính kết hợp, nên cộng các giá trị theo thứ tự không giống với cách SIMD cộng theo từng nhóm cách nhau 8 phần tử rồi cộng phần còn lại
      Từ góc nhìn compiler, đó có vẻ là tối ưu hóa hiển nhiên, nhưng nếu bạn không nói cho nó biết được phép nới lỏng các bảo đảm cụ thể, nó sẽ ưu tiên bảo đảm ngữ nghĩa tuần tự hơn tối ưu hóa
      Vì vậy mọi thứ trở nên lộn xộn, và như janwas nói, với hot path thì tôi nghĩ tốt hơn là dùng thư viện, đặc biệt là Google Highway hoặc Intel ISPC
    • Đó là một trong những điểm chính của ngôn ngữ lập trình hệ thống như C++
      Nó cố gắng hiệu quả theo cách portable nhất có thể, đồng thời giúp lập trình chuyên biệt theo mục tiêu dễ hơn khi cần
      Auto-vectorization thì compiler FORTRAN làm tốt hơn hẳn, vì không cho phép aliasing
      C++ bị kéo chân vì phải đi theo mô hình bộ nhớ của C
    • Cũng có thể đơn giản dùng CUDA
      CUDA là C++ được thiết kế cho GPU, cỗ máy SIMD tối thượng ngày nay, còn ROCm thực chất gần như là CUDA cho AMD
      Cá nhân tôi thích C++AMP của Microsoft; tôi nghĩ nó là thứ dễ nhập môn nhất
      Chỉ tiếc là cuối cùng nó không trụ lại được
    • Theo kinh nghiệm của tôi, chuyện này xảy ra thường xuyên
      Ngoài ra, nếu dùng thư viện wrapper SIMD thì thực tế có thể làm khá portable

  • Ghi chú nhỏ: compiler không tối ưu được triển khai popcount đó thành một lệnh đơn, nhưng với triển khai khác thì có thể
    Tất nhiên cũng khá khó: https://godbolt.org/z/T69KxWWW8

  • Bài nói _mm256_cvtps_epu32 biểu thị thao tác cấp thấp của một tập lệnh cụ thể và giải thích đó là phép cast float-to-int của AVX2, nhưng lệnh đó thuộc AVX-512
    AVX2 không có phép cast float-to-int, còn trong AVX1 thì kết quả số nguyên là signed và lệnh là _mm256_cvtps_epi32

  • Không biết so với fastbase64[0] thì thế nào
    Bài viết rất hay và thật vui khi thấy nội dung như vậy trên mạng, nhưng khó chia sẻ sự lạc quan của tác giả về thư viện portable SIMD
    [0]: https://github.com/lemire/fastbase64

  • Tôi nghĩ ISPC đơn giản là tốt hơn việc gắn SIMD vào C++ hay Rust
    Nó cũng hỗ trợ dynamic dispatch, một tính năng rất đau đầu nếu tự triển khai

    • Công cụ giúp mọi người dùng SIMD nhiều hơn nói chung là điều tốt, nhưng cá nhân tôi thích SIMD được tích hợp trong cùng toolchain hơn
      Như vậy có thể gọi inline ngược lại vào C++, dùng template và class trong code SIMD, và cũng có thể inline nhiều vùng code SIMD với nhau
      Tôi đồng ý rằng triển khai dynamic dispatch là khó, nhưng Highway xử lý phần đó
    • Tôi tự hỏi với một subroutine nhỏ như trong bài thì C++ hay Rust gọi ISPC có dễ không

  • Bài viết xuất sắc, và để lại cảm giác rất mạnh rằng “mình sẽ không bao giờ thông minh được như thế này”

    • Chỉ là đó không phải lĩnh vực công việc của bạn thôi
      Cũng giống như người bình thường không phải kỹ sư phần mềm hay nhà vật lý
      Nếu tập trung học vài tháng thì có thể làm được ở mức tương tự
    • Nếu có cơ hội gặp nhà tuyển dụng hoặc dự án cần những thứ như vậy, có lẽ bạn có thể “thông minh đến mức này”
      Rốt cuộc là vấn đề hứng thú và nhu cầu
      Tôi cũng thử qua lại giữa tối ưu hiệu năng và kỹ thuật bare-metal gần hệ thống hơn trong các dự án cá nhân, nhưng ước gì công việc cần đến nó nhiều hơn
      Tuy nhiên phần lớn công việc trong ngành không đòi hỏi hướng đó
    • Nên thử làm AoC '23 bằng APL/j/k, BQN, Python/numpy, CUDA và các thứ tương tự
      Tức là không dùng Python theo kiểu thông thường, mà giải mọi thứ bằng numpy
      Rất vui, học được kiểu thông minh này, và nhiều phần trong bài sẽ cảm thấy rất tự nhiên theo lối tư duy giải bài toán của các ngôn ngữ đó
      Theo thời gian bạn sẽ bắt đầu nhìn vấn đề dưới dạng như vậy
    • https://fgiesen.wordpress.com/2016/02/05/smart/

  • Bài viết thú vị
    Ở ví dụ đầu tiên phần đầu, tác giả nói rằng phần triển khai popcnt không được vector hóa tạo ra “đoạn mã tệ đến mức nói thật là buồn cười”, nhưng nếu dùng chế độ release với CPU đích native thì hàm đó có vẻ được vector hóa khá ổn
    https://godbolt.org/z/WE1Eq65jY

    • Đoạn mã dưới đây phải tạo ra đầu ra tương đương
      pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
      Nó được biên dịch thành popcnt eax, edi; ret
      Với các vector bit lớn, triển khai AVX2 có thể nhanh hơn POPCNT
      Tham khảo “Faster Population Counts Using AVX2 Instructions”: https://academic.oup.com/comjnl/article/61/1/111/3852071
      32 bit thì chưa đủ lớn, và mã mà Rust tạo ra thực sự tệ đến mức buồn cười
    • Lý tưởng thì có vẻ phần này nên được hạ xuống thành lệnh popcnt
    • Tự động vector hóa có lúc được, có lúc không
      Gần đây tôi viết đoạn mã cần đếm số bit trong mask kết quả của phép toán vector, và phần này được chuyển thành popcnt rất tốt
      https://godbolt.org/z/zT9Whcnco

  • Vì có những đoạn kiểu “Câu này giống câu hỏi bẫy nhỉ… chẳng phải chỉ là add thôi sao?”, thường người ta sẽ muốn nhắm tới biểu diễn vector trung gian và để trình biên dịch quyết định các chi tiết
    Ví dụ, chip Haswell có nhiều đơn vị thực thi dấu phẩy động trên mỗi lõi, và CPU có thể chạy đồng thời nhiều hơn một phép toán dấu phẩy động được pipeline hóa, nhưng trong số đó chỉ thực hiện được một lệnh add
    Nếu có nhiều phép cộng không phụ thuộc vào kết quả trước đó để có thể tránh độ trễ, thì cũng có thể gửi kèm một lệnh fused multiply-add với hạng tử nhân là 1 để tăng gấp đôi thông lượng phép cộng
    Lệnh đó có thể chạy đồng thời với phép cộng dấu phẩy động vector thông thường