Kỹ thuật khám phá hàm băm số nguyên tự động

 (github.com/skeeto)
3 điểm bởi GN⁺ 2024-05-06 | 1 bình luận | Chia sẻ qua WhatsApp
  • Hash Function Prospector là công cụ tạo ngẫu nhiên hàng loạt hàm băm số nguyên, biên dịch JIT chúng để đánh giá hành vi avalanche, rồi xuất ra hàm tối ưu hiện tại dưới cú pháp C
  • Việc đánh giá dùng avalanche score, tức số bit đầu ra trung bình vẫn giữ nguyên khi lật một bit đầu vào; càng thấp càng tốt và giá trị lý tưởng là 0
  • Đối tượng tìm kiếm là các hàm băm số nguyên 32-bit và 64-bit; do phụ thuộc vào trình biên dịch JIT nên công cụ chỉ chạy trên x86-64, nhưng các hàm được tìm ra vẫn có thể dùng ở môi trường khác
  • Các hàm nổi bật được tìm thấy chủ yếu dùng cấu trúc xorshift-multiply-xorshift; bản lowbias32 2 vòng cho bias thấp hơn MurmurHash3 32-bit finalizer với chênh lệch nhỏ, còn triple32 3 vòng tiến sát giới hạn bias lý thuyết
  • Có thể đo bias chính xác cho hàm 32-bit bằng -E và -e, hàm băm 16-bit do công cụ riêng hp16 đảm nhiệm, và cần chú ý đến quy tắc integer promotion trong C

Vai trò của Hash Function Prospector

  • Hash Function Prospector là công cụ phát hiện hàm băm số nguyên tự động
  • Công cụ tạo ngẫu nhiên hàng chục tỷ hàm băm số nguyên, biên dịch JIT chúng rồi đánh giá hành vi avalanche
  • Trong số các hàm được tạo ra, hàm tốt nhất hiện tại sẽ được xuất ra dưới cú pháp C
  • Bài viết liên quan là Prospecting for Hash Functions

Tiêu chí đánh giá và phạm vi hỗ trợ

  • avalanche score là số bit đầu ra trung bình vẫn giữ nguyên khi lật một bit đầu vào
    • Điểm càng thấp càng tốt
    • Lý tưởng là mọi bit đầu ra đều lật với xác suất 50%, khiến score bằng 0
  • Prospector có thể tạo các hàm băm số nguyên 32-bit và 64-bit
  • Có thể xem toàn bộ tùy chọn trong hướng dẫn dùng -h
  • Do trình biên dịch JIT, bản thân công cụ chỉ hỗ trợ x86-64
    • Tuy nhiên, các hàm băm được tìm ra có thể dùng ở bất kỳ đâu

Các phép toán khả nghịch dùng trong quá trình tìm kiếm

  • Bộ sinh sẽ tạo ngẫu nhiên hàm từ 9 phép toán khả nghịch đã chọn
  • Danh sách phép toán như sau
    • x = ~x
    • x ^= constant
    • x *= constant | 1
    • x += constant
    • x ^= x >> constant
    • x ^= x << constant
    • x += x << constant
    • x -= x << constant
    • x <<<= constant
    • x = bswap(x)
  • Về mặt kỹ thuật, x = ~x có thể biểu diễn thành x ^= constant, nhưng xác suất bộ sinh vô tình chọn đúng hằng số XOR đó là thấp nên nó được xem là phép toán riêng

Các hàm băm 32-bit được phát hiện

  • Hàm 2 vòng

    • Một trong những họ hàm được phát hiện hữu ích là cấu trúc 2 vòng xorshift-multiply-xorshift
    • TheIronBorn đã dùng tối ưu hóa tổ hợp để tìm bộ tham số tối ưu đã biết cho cấu trúc này, với kết quả [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501
    • lowbias32 là hoán vị 2 vòng 32-bit, có bias thấp và cho bias thấp hơn MurmurHash3 32-bit finalizer với chênh lệch rất nhỏ
    • exact bias của lowbias32 là 0.17353355999581582
    • Cấu trúc này do Prospector tìm ra, còn các tham số được tinh chỉnh bằng hill climbing và thuật toán di truyền
    • Hàm nghịch đảo lowbias32_r cũng được cung cấp
    • prospector32 là hàm được tìm ra chỉ bằng Prospector
    • exact bias là 0.34968228323361017
    • Bias của nó lớn hơn lowbias32 ở trên
    • Để tìm ngẫu nhiên các hằng số nhân thay thế, có thể chỉ định mẫu như sau
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • Hàm 3 vòng

    • Nếu thêm một vòng multiply-xorshift nữa vào cùng cấu trúc, với tham số được chọn cẩn thận, có thể đạt tới giới hạn bias lý thuyết
    • triple32 có exact bias là 0.020888578919738908
    • README mô tả rằng nó không thể phân biệt được với một PRF hoàn hảo giống như hoán vị ngẫu nhiên của mọi số nguyên 32-bit
    • Hàm nghịch đảo triple32_r cũng được cung cấp
    • Danh sách hằng số 3 vòng gồm các kết quả bias thấp từ 0.020888578919738908 đến khoảng 0.022984943828687553
    • triple32inc, tức triple32 có thêm phép tăng ở đầu, phá vỡ vấn đề hash(0) = 0 và còn giảm bias thêm một chút
    • exact bias là 0.020829410544597495
    • Hàm nghịch đảo triple32inc_r thực hiện x-- ở cuối

Đo exact bias

  • Chế độ -E dùng để đánh giá bias của hàm băm đã cho
  • Mặc định, Prospector dùng giá trị ước lượng để đánh giá bias nhanh
    • Ước lượng này là không xác định và có nhiều nhiễu trong kết quả
  • Để đo exact bias bằng vét cạn hoàn toàn, dùng tùy chọn -e
  • Hàm cần kiểm tra có thể được định nghĩa theo hai cách
    • Định nghĩa bằng -p và pattern
    • Định nghĩa bằng -l và thư viện dùng chung có chứa hàm hash()
  • Cách dùng thư viện dùng chung cho phép kiểm thử cả các hàm băm không thể biểu diễn bằng dạng hàm giới hạn của Prospector
  • Đầu vào mặc định được xem là hàm băm 32-bit
  • Công tắc -8 dùng để kiểm thử hàm 64-bit theo phương pháp ước lượng
    • Hàm băm 64-bit mất quá nhiều thời gian nên không có bài kiểm thử vét cạn exact

hp16 cho hàm băm 16-bit

  • Hàm băm 16-bit có các ràng buộc khác nên có công cụ riêng là hp16
  • Khác với Prospector 32-bit và 64-bit, hp16 hoàn toàn portable và có thể chạy trên gần như mọi hệ thống
  • hp16 cũng có thể tạo và đánh giá s-box 128KiB
  • Vì hàm băm 16-bit có thể cần trên các máy không có lệnh nhân nhanh, nên cũng có tùy chọn bỏ qua một số phép toán trong lúc tìm kiếm
    • -m
    • -r

Kết quả 16-bit và lưu ý khi triển khai bằng C

  • Một số kết quả 16-bit hiện tại như sau
    • xorshift-multiply 2 vòng hash16_xm2: bias 0.0085905051336723701
    • xorshift-multiply 3 vòng hash16_xm3: bias 0.0045976709018820602
    • không dùng phép nhân hash16_s6: bias 0.023840118344741465
  • hash16_s6 không dùng phép nhân được cho là tương đương với một dạng xorshift-multiply cụ thể
  • Hàm băm xorshift 3 vòng tốt được tìm nhanh bằng hp16 -Xn3 là một xấp xỉ gần với s-box tốt của hp16 -S
  • Khi viết phép toán 16-bit bằng C, cần chú ý đến quy tắc integer promotion
    • Ví dụ, trong triển khai 32-bit, toán hạng unsigned 16-bit có thể được nâng kiểu thành số nguyên signed 32-bit
    • Trong trường hợp đó, kết quả có thể sai trong một số tình huống cụ thể
    • Mã C do chương trình này xuất ra sẽ cẩn thận nâng các phép toán 16-bit lên unsigned int ở nơi cần thiết

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-05-06
Các ý kiến trên Hacker News

  • Cá nhân tôi không quen ông ấy, nhưng tôi thích mã của ông ấy
    Đặc biệt là thư viện JSON https://github.com/skeeto/pdjson, các thư viện phân tích tùy chọn https://github.com/skeeto/optparse và https://github.com/skeeto/getopt, bộ giải mã UTF-8 không rẽ nhánh https://github.com/skeeto/branchless-utf8, ngăn xếp không khóa https://github.com/skeeto/lstack, và thư viện trie https://github.com/skeeto/trie
    Tôi cũng thích gu giấy phép của ông ấy: tất cả các dự án trên đều được phát hành theo The Unlicense

    • Skeeto ở tầm huyền thoại. Với tôi, ông ấy cùng đẳng cấp với Fabrice Bellard
      Tôi đã theo dõi ông ấy trên GitHub nhiều năm rồi; ông ấy luôn thỉnh thoảng tung ra những công cụ nhỏ, kỳ lạ và rất ngách thú vị. Ví dụ nổi tiếng là Branchless UTF-8
    • Ông ấy cũng là tác giả của elfeed https://github.com/skeeto/elfeed, “một client web feed cho Emacs”, và tôi đã lấy được nhiều cảm hứng từ cách triển khai tối giản của nó

  • Xin chào, tôi là người tạo ra MurmurHash. Đây là một công trình thú vị, và thật hay khi thấy cách nhân-dịch-XOR vẫn trụ vững lâu đến vậy

    • XOR-dịch bù trừ hai điểm yếu của phép nhân: các bit cao không có bit nào phía trên để gây ảnh hưởng, còn các bit thấp không có bit nào phía dưới để bị ảnh hưởng
    • Giống MurmurHash, những thứ này có vẻ được nhắm tới như hàm băm phi mật mã
      Tuy nhiên ý tưởng avalanche + bias có vẻ còn bỏ sót khá nhiều. Chẳng hạn hàm triple32 được liệt kê ở cuối có bias chính xác là 0.020888578919738908; nếu FabriceNeyret2 triển khai nó trên ShaderToy thì sẽ ra hình như thế này: https://www.shadertoy.com/view/WttXWX hoặc https://i.imgur.com/qU2P5rx.png
      Nhưng nếu thử lấy đạo hàm độ dốc normal map đơn giản, sẽ thấy khá nhiều đường “tinh thể” nổi bật. Chắc hẳn có một thuật ngữ kỹ thuật nào đó để gọi dạng gờ như thế này: https://i.imgur.com/IHWT1GM.png
      Nói thêm, tôi nghĩ toàn bộ ý tưởng này đã có từ khoảng 5 năm trước rồi: https://nullprogram.com/blog/2018/07/31/

  • Vì từng có kinh nghiệm phát triển hàm băm tốt, tôi thường nghĩ đến ý tưởng tự động tìm kiếm hàm băm
    Thấy công việc kiểu này thật tuyệt. Sẽ hay nếu kết nối với SMHasher3 — một biến thể nhanh hơn và được cải tiến nhiều của bộ kiểm thử hash cũ do Frank J. T. Wojcik tạo ra — để tự động đánh giá kết quả đầu ra. Vì tốc độ, cũng có thể chỉ dùng một phần các bài test và cho thất bại sớm
    Mở rộng sang hash 64-bit và 128-bit cũng sẽ tốt, nhưng tất nhiên không gian tìm kiếm sẽ lớn hơn. Liên quan đến việc chọn giá trị dùng cho Rain, tôi từng viết cả mã NodeJS để đo avalanche trong phép nhân các số nguyên tố 64-bit
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • Sẽ rất thú vị nếu khái quát hóa việc này cho các phép toán có thể dùng trong phần mở rộng thao tác bit của RISC-V. Biết đâu ta sẽ tìm ra các hàm mạnh có thể dùng khi những lệnh đó phổ biến hơn trong tương lai
    Phép nhân không nhớ cũng có thể mở rộng tập các phép toán khả nghịch, và trên một số phần cứng hiện có thì nó nhanh. CRC cũng liên quan ở mức nào đó, nhưng khả dụng trên tập phần cứng rộng hơn và hẳn là một tập con nghiêm ngặt của những gì CLMUL có thể tìm ra
    Nhiều mục đích sử dụng hash chỉ quan tâm đến các bit thấp nhất hoặc cao nhất của giá trị hash, nên việc đánh giá bias ở các đoạn bit cao nhất/thấp nhất hoặc phần dư khi chia cho nhiều số khác nhau cũng rất thú vị. Một hàm trông có vẻ không thiên lệch khi xét toàn bộ đầu ra có thể tốt hơn hoặc tệ hơn theo các thước đo không nhìn toàn bộ đầu ra, hoặc với đầu vào không đồng đều như văn bản ASCII

  • Có thể giải thích vì sao thứ này hay ho và dùng ở đâu không?

    • Trông giống một công cụ tạo ra chuỗi lệnh để xây dựng hàm băm, rồi đánh giá hàm băm đó tốt đến mức nào
      Có vẻ chỉ số mục tiêu là khi một bit đầu vào thay đổi, càng nhiều bit đầu ra càng tốt sẽ thay đổi theo cách ngẫu nhiên nhất có thể. Nó xuất mã C của hàm băm tốt nhất trong số các hàm đã tạo
      Vì vậy nó hữu ích khi cần một hàm băm nhưng bạn cho rằng các hàm hiện có chưa đủ tốt, hoặc khi nghiên cứu hàm băm và cần ý tưởng cấu trúc mới. Việc tự sinh mã đã hay rồi, còn làm ngẫu nhiên thì là bước đầu tiên để tiến tới lập trình di truyền còn hay hơn. Và có vẻ con người từ khoảng 15 năm trước đã thích bắt máy tính đốt chu kỳ CPU để tính những hàm băm mà phần lớn sẽ chẳng được dùng đến
    • Những hàm như thế này là thiết yếu cho bảng băm. Các tên liên quan còn có hash map, hash set
      Bảng băm là một cấu trúc dữ liệu tuyệt vời, giúp triển khai nhiều thuật toán một cách đơn giản và hiệu quả. Hiệu quả này phụ thuộc vào việc có thể tạo ra một giá trị băm nhỏ so với dữ liệu, chẳng hạn 32 bit hoặc 64 bit, và gần như duy nhất hay không
      Ví dụ khi băm tên người dùng, nếu chỉ dùng mã ASCII của chữ cái đầu tiên trong tên thì nhiều tên người dùng sẽ được ánh xạ vào cùng một số, nên hoạt động không tốt. Đây gọi là va chạm, và nếu có nhiều va chạm thì bảng băm sẽ trở nên rất kém hiệu quả
      Cách tốt hơn là lấy các bit từ toàn bộ tên người dùng rồi trộn chúng bằng cách nào đó để throwaway_1237 và throwaway_12373 trở thành hai số khác nhau. Hàm băm thực hiện phép ánh xạ này, còn tính chất avalanche mô tả mức độ nó tránh va chạm tốt đến đâu
      Thông thường có sự đánh đổi giữa tốc độ của hàm băm thực tế và khả năng tránh va chạm. Các hàm băm đẳng cấp thế giới trông khá kỳ quặc, như nhân với các hằng số lạ, XOR, dịch bit, v.v.; con người rất khó nhìn vào những hàm khó hiểu như vậy để đoán hiệu năng
      Đoạn mã này thử ngẫu nhiên nhiều hàm băm và cho chúng cạnh tranh với nhau. Nếu thành công, nó hay ở chỗ có thể cải thiện hiệu năng thực tế của một cấu trúc dữ liệu cốt lõi được dùng rộng rãi trong nhiều ngôn ngữ và thư viện
    • Vì đây là hàm băm cho số nguyên, có thể dùng khi cần băm số nguyên nhanh trong set hoặc map. Nếu các hàm tách ra đủ khác nhau, nó cũng cung cấp hàm băm nhanh cho Bloom filter

  • Vài tuần trước tôi đã triển khai 1brc bằng Go https://github.com/infogulch/1brc-go, và kho này đã gợi ý cho tôi thử tìm một hàm băm hoàn hảo tùy chỉnh để mỗi trạm quan sát rơi vào bucket riêng mà không va chạm
    Nhưng rồi tôi thấy quy tắc nói rằng không được tùy biến hàm băm theo dữ liệu trước khi chương trình khởi động, nên bỏ ý tưởng đó
    Tôi đã tạo một bộ thử nghiệm kiểm tra các hằng số tùy ý, giá trị khởi đầu, hằng số nhân, lượng dịch/xoay bit, v.v., rồi in ra các hằng số tốt nhất tìm được cho đến lúc đó theo số bucket va chạm và số lần va chạm. Tôi nhớ là đã giảm được xuống mức chỉ có hai giá trị va chạm trong một bucket duy nhất, với hệ số lấp đầy khoảng 40%. Điều thú vị là các hằng số có hiệu năng tốt nhất đều chứa số vị trí dịch bit tương tự nhau, bất kể các hằng số khác, nên cuối cùng tôi hard-code các giá trị đó

    • Nhân tiện, có những kỹ thuật tốt hơn để tìm hàm băm hoàn hảo tối thiểu. Cái này thuộc loại khá dễ triển khai: https://cmph.sourceforge.net/chd.html

  • Nếu có thể tự đưa vào bộ sinh dữ liệu đầu vào thì sẽ rất thú vị. Trên thực tế, nhiều dữ liệu không phải là dữ liệu nhị phân ngẫu nhiên mà được cấu trúc theo cách nào đó, và nhờ cấu trúc đó có thể thu được hàm băm rất tốt

  • Giới hạn vào các phép toán khả nghịch thì có lợi về mặt toán học, nhưng đồng thời cũng loại trừ rất nhiều thứ
    Khi làm một thứ tương tự, tôi đã nghĩ tới băm hoàn hảo với tập đầu vào đã biết trước. Cách tiếp cận thông thường là dùng một mảng hằng số, nhưng tôi muốn xem có thể nén hơn nữa không, nhất là khi đầu vào vốn đã là các số nguyên nhỏ. Dĩ nhiên có thể làm kiểu như hash -= hash >> gap_index
    Vì vậy tôi đã thử dùng một danh sách khoảng 100 phép toán nguyên thủy. Một số phép trùng lặp với nhau, nhưng nếu xét riêng thì vẫn hữu ích. Rồi tôi chán và không làm ra dự án nào cả

    • “Giới hạn vào các phép toán khả nghịch thì có lợi về mặt toán học” nghĩa là gì, và trong ngữ cảnh này vì sao phép toán khả nghịch lại đáng mong muốn?

  • Tôi không rõ chính xác nó đang làm gì. Nó có đang tìm mức tốt nhất mọi thời không? Nếu không thì tôi tò mò vì sao giá trị tốt nhất lại thay đổi mỗi lần chạy
    Ngoài ra, nếu biết trước rằng chỉ xuất hiện các giá trị số nguyên trong một khoảng nhất định, chẳng hạn từ 10.000 đến 200.000, tôi cũng muốn biết có ai biết cơ chế nào để tìm một hàm băm tốt đưa các giá trị đó vào số bucket băm tối ưu không

    • Đây là cách thử ngẫu nhiên các giá trị để tìm giá trị tốt nhất trong số những giá trị đã thử ở lần chạy đó
      Việc quét toàn bộ không gian tìm kiếm trong một lần chạy để tìm tối ưu tuyệt đối là không thực tế, và thứ tự thử cũng ngẫu nhiên nên giá trị có thể khác nhau giữa các lần chạy
      Nếu chỉ cần một hàm băm “tốt”, gần như lúc nào dùng hàm băm tổng quát cũng là lựa chọn tốt nhất. Nếu các số cực kỳ lớn còn phạm vi thì rất nhỏ, có thể áp dụng offset để giá trị nhỏ nhất trở lại 0 rồi dùng hàm băm nhỏ hơn và nhanh hơn. Nếu muốn tìm “lựa chọn hoàn hảo” cho đúng phạm vi đó, cách tiếp cận ngẫu nhiên như thế này có lẽ là gần nhất, và chỉ cần sửa để phép thử chạy trên đoạn đó

  • Tôi tự hỏi liệu dùng cùng một hằng số cho hai phép nhân có thể giảm kích thước mã, nhờ đó tính toán cũng nhanh hơn một chút không
    Tôi cũng đã cập nhật câu trả lời trên StackOverflow: https://stackoverflow.com/questions/664014/what-integer-hash...