Teknik eksplorasi otomatis fungsi hash bilangan bulat

 (github.com/skeeto)
3 poin oleh GN⁺ 2024-05-06 | 1 komentar | Bagikan ke WhatsApp
  • Hash Function Prospector adalah alat yang menghasilkan fungsi hash bilangan bulat acak dalam jumlah besar, mengompilasinya dengan JIT, mengevaluasi perilaku avalanche, lalu menampilkan fungsi terbaik saat ini dalam sintaks C
  • Evaluasi menggunakan avalanche score, yaitu jumlah rata-rata bit output yang tetap tidak berubah ketika satu bit input dibalik; makin rendah makin baik, dan nilai idealnya adalah 0
  • Target eksplorasi adalah fungsi hash bilangan bulat 32-bit dan 64-bit; karena kompiler JIT, alat ini sendiri hanya mendukung x86-64, tetapi fungsi yang ditemukan dapat dipakai di lingkungan lain
  • Fungsi-fungsi utama yang ditemukan memakai susunan xorshift-multiply-xorshift; lowbias32 2 ronde menunjukkan bias lebih rendah dengan selisih kecil dibanding finalizer MurmurHash3 32-bit, dan triple32 3 ronde mendekati batas bias teoretis
  • Pengukuran bias yang akurat dapat dilakukan untuk fungsi 32-bit dengan -E dan -e, hash 16-bit ditangani alat terpisah hp16, dan perlu berhati-hati terhadap aturan promosi integer di C

Peran Hash Function Prospector

  • Hash Function Prospector adalah alat penemuan fungsi hash bilangan bulat otomatis
  • Alat ini menghasilkan miliaran fungsi hash bilangan bulat secara acak, lalu mengompilasinya dengan JIT dan mengevaluasi perilaku avalanche-nya
  • Di antara fungsi yang dihasilkan, fungsi terbaik saat ini ditampilkan dalam sintaks C
  • Tautan terkait tersedia ke Prospecting for Hash Functions

Kriteria evaluasi dan cakupan dukungan

  • avalanche score adalah jumlah rata-rata bit output yang tetap tidak berubah ketika satu bit input dibalik
    • Semakin rendah nilainya, semakin baik
    • Secara ideal semua bit output akan terbalik dengan probabilitas 50%, sehingga score menjadi 0
  • Prospector dapat menghasilkan fungsi hash bilangan bulat 32-bit dan 64-bit
  • Opsi lengkap dapat dilihat melalui penggunaan -h
  • Karena kompiler JIT, alat ini sendiri hanya mendukung x86-64
    • Namun fungsi hash yang ditemukan dapat digunakan di mana saja

Operasi reversibel yang dipakai dalam eksplorasi

  • Generator menyusun fungsi secara acak dari 9 operasi reversibel yang dipilih
  • Daftar operasinya adalah sebagai berikut
    • 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)
  • Secara teknis x = ~x dapat direpresentasikan sebagai x ^= constant, tetapi kemungkinan generator memilih konstanta XOR tersebut secara kebetulan sangat kecil, sehingga diperlakukan sebagai operasi terpisah

Fungsi hash 32-bit yang ditemukan

  • Fungsi 2 ronde

    • Salah satu keluarga fungsi yang berguna yang ditemukan adalah susunan xorshift-multiply-xorshift 2 ronde
    • TheIronBorn menemukan parameter optimal yang diketahui untuk susunan ini dengan menggunakan optimisasi kombinatorial, dan hasilnya adalah [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501
    • lowbias32 adalah permutasi 32-bit 2 ronde dengan bias rendah, dan menunjukkan bias yang sedikit lebih rendah daripada finalizer MurmurHash3 32-bit
    • Exact bias dari lowbias32 adalah 0.17353355999581582
    • Susunannya ditemukan oleh Prospector, dan parameternya disetel dengan hill climbing serta algoritme genetika
    • Fungsi invers lowbias32_r juga disediakan
    • prospector32 adalah fungsi yang ditemukan hanya dengan menggunakan Prospector
    • Exact bias-nya adalah 0.34968228323361017
    • Bias ini lebih besar daripada lowbias32 sebelumnya
    • Untuk mengeksplorasi konstanta perkalian alternatif secara acak, pola dapat ditentukan seperti berikut
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • Fungsi 3 ronde

    • Jika satu ronde multiply-xorshift lagi ditambahkan ke susunan yang sama, parameter yang dipilih dengan cermat dapat mencapai batas bias teoretis
    • triple32 memiliki exact bias sebesar 0.020888578919738908
    • README menjelaskan bahwa fungsi ini tak dapat dibedakan dari PRF sempurna seperti permutasi acak atas semua integer 32-bit
    • Fungsi invers triple32_r juga disediakan
    • Daftar konstanta 3 ronde mencakup hasil bias rendah dari 0.020888578919738908 hingga sekitar 0.022984943828687553
    • triple32inc, yaitu triple32 yang didahului operasi increment, memecahkan masalah hash(0) = 0 dan juga sedikit menurunkan bias
    • Exact bias-nya adalah 0.020829410544597495
    • Fungsi invers triple32inc_r menjalankan x-- di bagian akhir

Pengukuran exact bias

  • Mode -E mengevaluasi bias dari fungsi hash yang diberikan
  • Secara default Prospector menggunakan estimasi untuk mengevaluasi bias dengan cepat
    • Estimasi ini tidak deterministik dan hasilnya sangat berisik
  • Untuk mengukur exact bias dengan pencarian menyeluruh, gunakan opsi -e
  • Fungsi yang akan diperiksa dapat didefinisikan dengan dua cara
    • Didefinisikan dengan -p dan pola
    • Didefinisikan dengan -l dan shared library yang berisi fungsi hash()
  • Metode shared library memungkinkan pengujian fungsi hash yang tidak dapat direpresentasikan dengan ekspresi fungsi Prospector yang terbatas
  • Input default diperlakukan sebagai fungsi hash 32-bit
  • Switch -8 menguji fungsi 64-bit dengan metode estimasi
    • Fungsi hash 64-bit memerlukan waktu terlalu lama sehingga tidak ada exact exhaustive test

hp16 untuk hash 16-bit

  • Hash 16-bit memiliki kendala yang berbeda, sehingga disediakan alat terpisah hp16
  • Tidak seperti Prospector 32-bit dan 64-bit, hp16 sepenuhnya portabel dan dapat dijalankan di hampir semua sistem
  • hp16 juga dapat membuat dan mengevaluasi s-box 128KiB
  • Karena hash 16-bit mungkin dibutuhkan pada mesin tanpa instruksi perkalian cepat, tersedia juga opsi untuk menghilangkan operasi tertentu saat eksplorasi
    • -m
    • -r

Hasil 16-bit dan perhatian pada implementasi C

  • Contoh hasil 16-bit saat ini adalah sebagai berikut
    • 2 ronde xorshift-multiply hash16_xm2: bias 0.0085905051336723701
    • 3 ronde xorshift-multiply hash16_xm3: bias 0.0045976709018820602
    • Tanpa perkalian hash16_s6: bias 0.023840118344741465
  • hash16_s6 tanpa perkalian disebut setara dengan bentuk xorshift-multiply tertentu
  • Hash xorshift 3 ronde yang baik dari eksplorasi singkat dengan hp16 -Xn3 merupakan pendekatan yang dekat dengan s-box baik dari hp16 -S
  • Saat menulis operasi 16-bit dalam C, perlu berhati-hati terhadap aturan promosi integer
    • Misalnya, pada implementasi 32-bit, operan unsigned 16-bit dapat dipromosikan menjadi integer 32-bit signed
    • Dalam kasus ini, hasil yang salah dapat muncul pada situasi tertentu
    • Kode C yang dikeluarkan program ini berhati-hati untuk mempromosikan operasi 16-bit menjadi unsigned int di tempat yang diperlukan

Bacaan terkait

1 komentar

 
GN⁺ 2024-05-06
Komentar Hacker News

  • Saya tidak mengenalnya secara pribadi, tetapi saya suka kodenya
    Terutama library JSON https://github.com/skeeto/pdjson, library parsing opsi https://github.com/skeeto/optparse dan https://github.com/skeeto/getopt, decoder UTF-8 tanpa percabangan https://github.com/skeeto/branchless-utf8, stack bebas-lock https://github.com/skeeto/lstack, serta library trie https://github.com/skeeto/trie
    Saya juga suka preferensi lisensinya: semua proyek di atas didistribusikan dengan The Unlicense

    • Skeeto itu sudah sekelas legenda. Menurut saya ia satu level dengan Fabrice Bellard
      Saya sudah mengikutinya di GitHub selama bertahun-tahun, dan ia selalu merilis tool kecil dan unik untuk ceruk yang aneh. Misalnya Branchless UTF-8 yang terkenal
    • Ia juga penulis elfeed https://github.com/skeeto/elfeed, “klien web feeds untuk Emacs”, dan saya mendapat banyak inspirasi dari implementasinya yang minimalis

  • Halo, saya pembuat MurmurHash. Ini pekerjaan yang menarik, dan lucu juga melihat pendekatan multiply-shift-XOR bertahan begitu baik selama ini

    • XOR-shift mengimbangi dua kelemahan perkalian. Bit tinggi tidak punya bit di atasnya yang dapat memengaruhi, dan bit rendah tidak punya bit di bawahnya yang dapat dipengaruhi
    • Seperti MurmurHash, ini juga tampaknya dimaksudkan sebagai hash non-kriptografis
      Namun ide avalanche + bias tampaknya masih cukup banyak kekurangannya. Misalnya fungsi triple32 yang dicantumkan di bagian akhir memiliki bias persis 0.020888578919738908, dan jika FabriceNeyret2 mengimplementasikannya di ShaderToy, hasilnya menjadi gambar seperti ini: https://www.shadertoy.com/view/WttXWX atau https://i.imgur.com/qU2P5rx.png
      Tetapi jika melakukan diferensiasi kemiringan normal map sederhana, terlihat cukup banyak garis “kristal” yang mencolok. Mungkin ada istilah teknis untuk bentuk ridge seperti ini: https://i.imgur.com/IHWT1GM.png
      Sebagai tambahan, saya rasa keseluruhan ide ini sudah sekitar 5 tahun lamanya: https://nullprogram.com/blog/2018/07/31/

  • Karena pengalaman mengembangkan fungsi hash yang bagus, saya sering memikirkan ide pencarian hash otomatis
    Senang melihat pekerjaan seperti ini. Akan bagus jika dihubungkan dengan SMHasher3, varian yang jauh lebih baik dan lebih cepat dari rangkaian pengujian hash lama buatan Frank J. T. Wojcik, lalu hasil keluarannya dievaluasi secara otomatis. Demi kecepatan, sebagian pengujian saja bisa digunakan dan dibuat cepat gagal
    Memperluasnya ke hash 64-bit dan 128-bit juga bagus, tetapi tentu ruang pencariannya menjadi lebih besar. Terkait itu, saya pernah membuat kode NodeJS yang mengukur avalanche pada perkalian bilangan prima 64-bit untuk memilih nilai yang akan dipakai di Rain
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • Akan menarik jika ini digeneralisasi ke operasi yang tersedia di ekstensi manipulasi bit RISC-V. Mungkin suatu saat akan ditemukan fungsi-fungsi kuat yang bisa dipakai ketika instruksi-instruksi itu makin tersebar luas
    Perkalian tanpa carry juga dapat memperluas himpunan operasi yang dapat dibalik, dan cepat pada sebagian hardware yang sudah ada. CRC juga agak terkait, tetapi tersedia pada kumpulan hardware yang lebih luas, dan semestinya merupakan subset ketat dari apa yang bisa ditemukan CLMUL
    Banyak penggunaan hash hanya peduli pada bit paling rendah atau bit paling tinggi dari nilai hash, jadi menarik juga untuk mengevaluasi bias pada rentang bit tertinggi/terendah atau sisa pembagian oleh berbagai bilangan. Fungsi yang tampak tidak bias jika dilihat dari keseluruhan output bisa menjadi lebih baik atau lebih buruk pada metrik yang tidak melihat keseluruhan output, atau pada input yang tidak seragam seperti teks ASCII

  • Bisa jelaskan kenapa ini keren dan dipakai untuk apa?

    • Sepertinya ini alat untuk menghasilkan urutan instruksi guna membuat fungsi hash, lalu mengevaluasi seberapa bagus fungsi hash itu
      Metrik tujuannya tampaknya adalah apakah saat satu bit input berubah, sebanyak mungkin bit output berubah seacak mungkin. Alat ini mengeluarkan kode C untuk fungsi hash terbaik dari yang dihasilkannya
      Jadi ini berguna ketika kita membutuhkan fungsi hash tetapi merasa fungsi yang ada belum cukup bagus, atau saat meneliti fungsi hash dan membutuhkan ide struktur baru. Pembuatan kodenya sendiri sudah keren, dan melakukannya secara acak adalah langkah pertama menuju genetic programming yang lebih keren lagi. Selain itu, manusia tampaknya sejak sekitar 15 tahun lalu suka membuat komputer membakar siklus CPU untuk menghitung hash yang kemungkinan besar tidak akan pernah dipakai
    • Fungsi seperti ini sangat penting untuk hash table. Nama terkaitnya juga ada hash map dan hash set
      Hash table adalah struktur data hebat yang memungkinkan banyak algoritma diimplementasikan secara sederhana dan efisien. Efisiensi ini bergantung pada apakah kita bisa membuat hash yang kecil untuk data, misalnya 32-bit atau 64-bit, dan hampir unik
      Misalnya, saat melakukan hash pada nama pengguna, jika hanya memakai kode ASCII huruf pertama dari nama, banyak nama pengguna akan dipetakan ke angka yang sama sehingga tidak bekerja dengan baik. Ini disebut collision, dan jika collision banyak, hash table menjadi sangat tidak efisien
      Cara yang lebih baik adalah mengambil bit dari seluruh nama pengguna lalu mencampurnya dengan suatu cara agar throwaway_1237 dan throwaway_12373 menjadi angka yang berbeda. Fungsi hash melakukan pemetaan ini, dan sifat avalanche menjelaskan seberapa baik ia menghindari collision
      Biasanya ada kompromi antara seberapa cepat fungsi hash nyata dan seberapa baik ia menghindari collision. Fungsi hash kelas dunia terlihat cukup aneh, seperti mengalikan dengan konstanta ganjil, melakukan XOR, dan shift; sangat sulit bagi manusia menebak performanya hanya dengan melihat fungsi yang sulit dipahami seperti ini
      Kode ini mencoba berbagai fungsi hash secara acak dan membuatnya saling bersaing. Kalau berhasil, ini keren karena bisa meningkatkan performa nyata struktur data inti yang dipakai di berbagai bahasa dan library
    • Karena ini fungsi hash untuk integer, bisa dipakai saat membutuhkan hash integer cepat dalam set atau map. Jika fungsi-fungsinya bercabang cukup berbeda, ini juga menyediakan hash cepat untuk Bloom filter

  • Beberapa minggu lalu saya mengimplementasikan 1brc di Go https://github.com/infogulch/1brc-go, dan setelah melihat repositori ini saya terinspirasi untuk mencari fungsi perfect hash kustom agar setiap stasiun pengamatan masuk ke bucket-nya sendiri tanpa collision
    Namun saya membatalkan ide itu setelah melihat aturan bahwa fungsi hash tidak boleh dikustomisasi berdasarkan data sebelum program dimulai
    Saya membuat perangkat uji yang memeriksa konstanta acak, nilai awal, konstanta perkalian, jumlah shift/rotasi, dan sebagainya, lalu mencetak konstanta terbaik sejauh ini berdasarkan jumlah bucket yang collision dan jumlah collision. Seingat saya, pada load factor sekitar 40%, saya berhasil menurunkannya hingga hanya dua nilai yang collision di satu bucket saja. Menariknya, konstanta dengan performa terbaik, terlepas dari konstanta lain, mengandung jumlah posisi shift yang mirip, jadi pada akhirnya nilai-nilai itu saya hard-code

  • Akan sangat menarik kalau kita bisa memasukkan generator data input sendiri. Dalam praktiknya, data sering kali bukan data biner acak, melainkan data yang terstruktur dengan suatu cara, dan struktur itu mungkin memungkinkan kita memperoleh fungsi hash yang sangat bagus

  • Membatasi ke operasi reversibel punya kelebihan matematis, tetapi pada saat yang sama mengecualikan banyak hal
    Saat saya melakukan sesuatu yang mirip, saya sedang memikirkan perfect hashing di mana kumpulan input sudah diketahui sebelumnya. Pendekatan umum memakai array konstanta, tetapi saya ingin melihat apakah bisa dibuat lebih ringkas, terutama jika inputnya sudah berupa integer kecil. Tentu saja bisa dilakukan dengan sesuatu seperti hash -= hash >> gap_index
    Jadi saya mencoba daftar sekitar 100 operasi primitif. Sebagiannya saling tumpang tindih, tetapi berguna jika dipikirkan secara terpisah. Lalu saya bosan dan tidak menjadikannya proyek apa pun

    • Apa yang dimaksud dengan “membatasi ke operasi reversibel punya kelebihan matematis”, dan mengapa operasi reversibel diinginkan dalam konteks ini?

  • Saya tidak begitu paham apa tepatnya yang dilakukan. Apakah ini mencari yang terbaik sepanjang masa? Kalau bukan, saya penasaran kenapa nilai terbaik berubah setiap kali dijalankan
    Saya juga penasaran apakah ada yang tahu mekanisme untuk menemukan fungsi hash yang bagus ketika kita tahu nilai integer hanya muncul dalam rentang tertentu, misalnya antara 10.000 dan 200.000, agar nilai itu masuk ke jumlah bucket hash yang optimal

    • Pendekatannya adalah mencoba nilai secara acak untuk menemukan yang terbaik di antara nilai-nilai yang dicoba dalam eksekusi itu
      Menyapu seluruh ruang pencarian dalam satu kali eksekusi untuk menemukan nilai optimal absolut tidak realistis, dan karena urutan percobaannya juga acak, nilainya bisa berbeda tiap kali dijalankan
      Jika yang dibutuhkan hanya hash yang “bagus”, hampir selalu pilihan terbaik adalah memakai fungsi hash umum. Jika angkanya sangat besar dan rentangnya sangat kecil, kita bisa menerapkan offset agar nilai minimum kembali menjadi 0, lalu memakai hash yang lebih kecil dan cepat. Jika ingin menemukan “pilihan sempurna” untuk rentang yang tepat, pendekatan acak seperti ini tampaknya yang paling mendekati, dan pengujiannya tinggal diubah agar dilakukan pada rentang tersebut

  • Saya penasaran apakah memakai konstanta yang sama untuk dua perkalian bisa mengurangi ukuran kode sehingga perhitungannya juga mungkin sedikit lebih cepat
    Saya juga memperbarui jawaban StackOverflow: https://stackoverflow.com/questions/664014/what-integer-hash...