Otomatikleştirilmiş Tamsayı Hash Fonksiyonu Keşif Tekniği

• Hash Function Prospector, tamsayı hash fonksiyonlarını rastgele ve büyük ölçekte üreten, bunları JIT derleyen ve avalanche davranışını değerlendirdikten sonra o anki en iyi fonksiyonu C sözdizimiyle çıktılayan bir araçtır
• Değerlendirmede, tek bir giriş biti ters çevrildiğinde ortalamada sabit kalan çıkış biti sayısı olan avalanche score kullanılır; ne kadar düşükse o kadar iyidir ve ideal değer 0’dır
• Keşif hedefi 32 bit ve 64 bit tamsayı hash fonksiyonlarıdır; JIT derleyici nedeniyle aracın çalışması yalnızca x86-64 üzerinde desteklenir, ancak bulunan fonksiyonlar başka ortamlarda da kullanılabilir
• Bulunan başlıca fonksiyonlar xorshift-multiply-xorshift yapısını kullanır; 2 turlu lowbias32, MurmurHash3 32-bit finalizer’a göre küçük bir farkla daha düşük bias gösterir, 3 turlu triple32 ise teorik bias sınırına yakındır
• Kesin bias ölçümü 32 bit fonksiyonlar için -E ve -e ile yapılabilir; 16 bit hash’ler için ayrı hp16 aracı kullanılır ve C tamsayı yükseltme kurallarına dikkat edilmelidir

---

Hash Function Prospector’ın rolü

• Hash Function Prospector, otomatikleştirilmiş bir tamsayı hash fonksiyonu keşif aracıdır
• Rastgele milyarlarca tamsayı hash fonksiyonu üretir, bunları JIT derler ve avalanche davranışını değerlendirir
• Üretilen fonksiyonlar arasındaki o anki en iyi fonksiyon C sözdizimiyle çıktı olarak verilir
• İlgili yazı olarak Prospecting for Hash Functions bağlantısı verilmiştir

Değerlendirme ölçütü ve destek kapsamı

• avalanche score, giriş bitlerinden biri ters çevrildiğinde ortalamada sabit kalan çıkış biti sayısıdır
  • Skor ne kadar düşükse o kadar iyidir
  • İdeal olarak tüm çıkış bitleri %50 olasılıkla ters çevrilir ve skor 0 olur
• Prospector, 32 bit ve 64 bit tamsayı hash fonksiyonları üretebilir
• Tüm seçenekler -h kullanım çıktısından görülebilir
• JIT derleyici nedeniyle aracın kendisi yalnızca x86-64 destekler
  • Ancak bulunan hash fonksiyonları her yerde kullanılabilir

Keşifte kullanılan tersinir işlemler

• Üretici, seçili 9 tersinir işlemden rastgele fonksiyonlar oluşturur
• İşlem listesi şöyledir
  • 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)
• Teknik olarak x = ~x, x ^= constant ile ifade edilebilir; ancak üreticinin ilgili XOR sabitini tesadüfen seçme olasılığı düşük olduğundan ayrı bir işlem olarak ele alınır

Bulunan 32 bit hash fonksiyonları

• 2 turlu fonksiyon

  • Yararlı bulunan fonksiyon ailelerinden biri 2 turlu xorshift-multiply-xorshift yapısıdır
  • TheIronBorn, kombinasyon optimizasyonu kullanarak bu yapının bilinen en iyi parametrelerini buldu; sonuç [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501 şeklindedir
  • lowbias32, düşük bias’a sahip 32 bit 2 turlu bir permütasyondur ve MurmurHash3 32-bit finalizer’dan çok küçük bir farkla daha düşük bias gösterir
  • lowbias32 için exact bias 0.17353355999581582’dir
  • Yapı Prospector tarafından bulunmuş, parametreler hill climbing ve genetik algoritmalarla ayarlanmıştır
  • Ters fonksiyon lowbias32_r de sağlanır
  • prospector32, yalnızca Prospector kullanılarak bulunmuş bir fonksiyondur
  • exact bias değeri 0.34968228323361017’dir
  • Önceki lowbias32’den daha yüksek bias’a sahiptir
  • Alternatif çarpma sabitlerini rastgele aramak için desen şu şekilde belirtilir
  • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

• 3 turlu fonksiyon

  • Aynı yapıya bir multiply-xorshift turu daha eklendiğinde, dikkatle seçilmiş parametrelerle teorik bias sınırına ulaşılabilir
  • triple32 için exact bias 0.020888578919738908’dir
  • README, bunun tüm 32 bit tamsayıların rastgele permütasyonu gibi eksiksiz bir PRF’den ayırt edilemediğini açıklar
  • Ters fonksiyon triple32_r de sağlanır
  • 3 turlu sabit listesinde 0.020888578919738908 ile yaklaşık 0.022984943828687553 arasında düşük bias sonuçları yer alır
  • triple32’nin başına artırma işlemi ekleyen triple32inc, hash(0) = 0 sorununu bozar ve bias’ı da biraz daha düşürür
  • exact bias değeri 0.020829410544597495’tir
  • Ters fonksiyon triple32inc_r, en sonda x-- gerçekleştirir

exact bias ölçümü

• -E modu, verilen hash fonksiyonunun bias değerini değerlendirir
• Varsayılan olarak Prospector, bias’ı hızlı değerlendirmek için tahmin kullanır
  • Bu tahmin deterministik değildir ve sonuçlarda çok gürültü vardır
• Tam arama ile exact bias ölçmek için -e seçeneği kullanılır
• Denetlenecek fonksiyon iki şekilde tanımlanabilir
  • -p ve bir desen ile tanımlama
  • -l ve hash() fonksiyonunu içeren bir paylaşımlı kütüphane ile tanımlama
• Paylaşımlı kütüphane yöntemi, Prospector’ın sınırlı fonksiyon gösterimiyle ifade edilemeyen hash fonksiyonlarının da test edilmesini sağlar
• Varsayılan giriş 32 bit hash fonksiyonu olarak ele alınır
• -8 anahtarı, 64 bit fonksiyonları tahmin yöntemiyle test eder
  • 64 bit hash fonksiyonları çok uzun sürdüğünden exact exhaustive test yoktur

16 bit hash’ler için hp16

• 16 bit hash’lerde kısıtlar farklı olduğundan ayrı bir hp16 aracı sağlanır
• hp16, 32 bit ve 64 bit Prospector’dan farklı olarak tamamen taşınabilirdir ve neredeyse her sistemde çalışabilir
• hp16, 128KiB s-box üretimi ve değerlendirmesi de yapabilir
• 16 bit hash’ler hızlı çarpma komutu bulunmayan makinelerde gerekebileceğinden, keşif sırasında belirli işlemleri atlama seçenekleri de vardır
  • -m
  • -r

16 bit sonuçlar ve C uygulamasında dikkat edilecekler

• Bugüne kadarki 16 bit sonuç örnekleri şöyledir
  • 2 turlu xorshift-multiply hash16_xm2: bias 0.0085905051336723701
  • 3 turlu xorshift-multiply hash16_xm3: bias 0.0045976709018820602
  • Çarpmasız hash16_s6: bias 0.023840118344741465
• Çarpmasız hash16_s6’nın belirli bir xorshift-multiply biçimiyle aynı olduğu belirtilir
• hp16 -Xn3 ile kısa süreli aramada bulunan iyi 3 turlu xorshift hash, hp16 -S’nin iyi bir s-box’ına yakın bir yaklaşımdır
• 16 bit işlemleri C ile yazarken tamsayı yükseltme kurallarına dikkat edilmelidir
  • Örneğin 32 bit bir uygulamada unsigned 16 bit operandlar signed 32 bit tamsayıya yükseltilebilir
  • Bu durumda belirli koşullarda hatalı sonuçlar çıkabilir
  • Bu programın çıktı verdiği C kodu, gerekli yerlerde 16 bit işlemleri unsigned int’e yükseltmeye dikkat eder

[GN⁺]

Hacker News yorumları

• Kişisel olarak bilmiyorum ama onun kodunu beğeniyorum
  Özellikle JSON kütüphanesi https://github.com/skeeto/pdjson, seçenek ayrıştırma kütüphaneleri https://github.com/skeeto/optparse ve https://github.com/skeeto/getopt, dalsız UTF-8 çözücüsü https://github.com/skeeto/branchless-utf8, kilitsiz yığın https://github.com/skeeto/lstack ve trie kütüphanesi https://github.com/skeeto/trie hoşuma gidiyor
  Yukarıdaki projelerin hepsinin The Unlicense ile dağıtılması da lisans tercihleri açısından hoşuma gidiyor

  • Skeeto efsane seviyesinde. Bana göre Fabrice Bellard ile aynı ligde
    Onu GitHub'da yıllardır takip ediyorum; sürekli ilginç küçük ve tuhaf niş araçlar çıkarıyor. Örneğin Branchless UTF-8 epey bilinir
  • Ayrıca elfeed https://github.com/skeeto/elfeed'in de yazarı. “An Emacs web feeds client” ve onun minimal uygulamasından çok ilham aldım

• Merhaba, MurmurHash'i yapan kişi benim. İlginç bir çalışma ve çarpma-kaydırma-XOR yaklaşımının bu kadar uzun süre dayanması eğlenceli

  • XOR-kaydırma, çarpmanın iki zayıf noktasını telafi ediyor. Yüksek bitlerin üstlerinden etkilenebilecek bit yok, düşük bitlerin de altlarından etkilenebilecek bit yok
  • MurmurHash gibi bunlar da görünüşe göre kriptografik olmayan hash amaçlı
    Ama avalanche + bias fikrinde epey eksik kalan nokta var gibi. Örneğin sonda listelenen triple32 fonksiyonunun tam bias değeri 0.020888578919738908; FabriceNeyret2 bunu ShaderToy'da uygulayınca şu görseller çıkıyor: https://www.shadertoy.com/view/WttXWX veya https://i.imgur.com/qU2P5rx.png
    Ancak basit bir normal map eğim türevi alınca göze çarpan epey fazla “kristal” çizgisi görülüyor. Bu sırt biçimi için muhtemelen teknik bir terim vardır: https://i.imgur.com/IHWT1GM.png
    Ayrıca bu fikrin tamamı zaten yaklaşık 5 yıllık değil mi diye düşünüyorum: https://nullprogram.com/blog/2018/07/31/

• İyi hash fonksiyonları geliştirme deneyimim olduğu için otomatik hash arama fikrini sık sık düşündüm
  Böyle bir çalışmayı görmek harika. Frank J. T. Wojcik'in eski hash test paketinin çok geliştirilmiş ve hızlı bir türevi olan SMHasher3 ile bağlayıp çıktıların otomatik değerlendirilmesi güzel olurdu. Hız için testlerin sadece bir kısmı kullanılabilir ve hızlı başarısızlık uygulanabilir
  Bunu 64 bit ve 128 bit hash'lere genişletmek de güzel olurdu ama doğal olarak arama uzayı daha da büyür. Bununla bağlantılı olarak, Rain'de kullanılacak değerleri seçmek için 64 bit asal çarpımında avalanche ölçen bir NodeJS kodu da yazmıştım
  [Rain]: https://github.com/dosyago/rain
  [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

• Bunu RISC-V bit manipulation extension içinde kullanılabilen işlemlerle genelleştirmek ilginç olabilir. İleride bu komutlar daha yaygınlaştığında kullanılabilecek güçlü fonksiyonlar bulunabilir
  Elde taşma olmadan çarpma da tersinir işlem kümesini genişletebilir ve bazı mevcut donanımlarda hızlıdır. CRC de bir ölçüde bununla ilişkili, ama daha geniş bir donanım kümesinde mümkündür ve CLMUL'ün bulabildiklerinin katı bir alt kümesi olmalıdır
  Hash'in birçok kullanımında sadece en düşük veya en yüksek bitler önemsendiği için, en yüksek/en düşük bit aralıklarındaki bias ya da çeşitli sayılara göre kalanların değerlendirilmesi de ilginç olur. Tam çıktıya göre bias göstermeyen fonksiyonlar bile, tüm çıktıya bakmayan ölçütlerde veya ASCII metin gibi eşit dağılmayan girdilerde daha iyi ya da daha kötü olabilir

• Bunun neden harika olduğunu ve nerede kullanıldığını açıklayabilir misiniz?

  • Hash fonksiyonu oluşturmak için komut dizileri üreten ve bu hash fonksiyonunun ne kadar iyi olduğunu değerlendiren bir araç gibi görünüyor.
    Hedef ölçüt muhtemelen, girişteki tek bir bit değiştiğinde mümkün olduğunca çok çıkış bitinin olabildiğince rastgele değişip değişmediği. Üretilenler arasından en iyi hash fonksiyonunun C kodunu veriyor.
    Bu yüzden, hash fonksiyonuna ihtiyaç duyuyor ama mevcut fonksiyonların yeterince iyi olmadığını düşünüyorsanız ya da hash fonksiyonlarını araştırırken yeni yapı fikirlerine ihtiyaç duyuyorsanız faydalı. Kod üretiminin kendisi de havalı; bunu rastgele yapmak ise daha da havalı olan genetik programlamaya giden ilk adım. Ayrıca insanlar yaklaşık 15 yıldır bilgisayarların CPU döngülerini yakıp büyük olasılıkla çoğu hiç kullanılmayacak hash’leri hesaplatmasından hoşlanıyor gibi görünüyor
  • Bu tür fonksiyonlar hash table için vazgeçilmezdir. İlgili adlar arasında hash map ve hash set de var.
    Hash table, birçok algoritmanın basit ve verimli biçimde uygulanmasını sağlayan harika bir veri yapısıdır. Bu verimlilik, veriden küçük, örneğin 32 bit ya da 64 bit, neredeyse benzersiz bir hash üretip üretemediğinize bağlıdır.
    Örneğin kullanıcı adlarını hash’lerken yalnızca adın ilk harfinin ASCII kodunu kullanırsanız birçok kullanıcı adı aynı sayıya eşlenir ve bu iyi çalışmaz. Buna çakışma denir; çakışma çoksa hash table çok verimsiz hale gelir.
    Daha iyi yöntem, kullanıcı adının tamamından bitler alıp bunları bir şekilde karıştırarak throwaway_1237 ile throwaway_12373 için farklı sayılar üretmektir. Bu eşlemeyi yapan şey hash fonksiyonudur ve avalanche özelliği bunun çakışmaları önlemede ne kadar iyi olduğunu açıklar.
    Genelde gerçek bir hash fonksiyonunun ne kadar hızlı olduğu ile çakışmaları önlemede ne kadar başarılı olduğu arasında bir ödünleşim vardır. Dünya çapında iyi hash fonksiyonları tuhaf sabitlerle çarpma, XOR, kaydırma gibi işlemler yüzünden epey garip görünür ve bir insanın böyle anlaşılmaz bir fonksiyona bakıp performansını tahmin etmesi çok zordur.
    Bu kod birçok hash fonksiyonunu rastgele dener ve birbirleriyle yarıştırır. Başarılı olursa, birçok dil ve kütüphanede kullanılan temel bir veri yapısının gerçek performansını iyileştirebileceği için harika
  • Tamsayılar için bir hash fonksiyonu olduğu için, küme ya da map içinde hızlı tamsayı hash’i gerektiğinde kullanılabilir. Fonksiyonlar yeterince farklı dallanıyorsa Bloom filtreleri için de hızlı hash sağlayabilir

• Birkaç hafta önce Go ile 1brc uyguladım: https://github.com/infogulch/1brc-go ve bu depoyu görünce her istasyonun çakışma olmadan kendi bucket’ına girmesini sağlayacak özel bir perfect hash fonksiyonu bulmayı denemek için ilham aldım.
  Sonra program başlamadan önce veriye göre hash fonksiyonunu özelleştirmenin yasak olduğunu söyleyen kuralı görüp bu fikirden vazgeçtim.
  Rastgele sabitleri, başlangıç değerlerini, çarpma sabitlerini, kaydırma/döndürme miktarlarını deneyen ve çakışan bucket sayısı ile çakışma sayısına göre o ana kadar bulunan en iyi sabitleri yazdıran bir test düzeni kurdum. Yaklaşık %40 doluluk oranında, yalnızca tek bir bucket içinde iki değerin çakıştığı noktaya kadar düşürmeyi başardığımı sanıyorum. İlginç olan, en iyi performans veren sabitlerin diğer sabitlerden bağımsız olarak benzer kaydırma konum sayılarını içermesiydi; sonunda bu değerleri hardcode ettim

  • Bilginize, minimal perfect hash function bulmak için daha iyi teknikler var. Bunu uygulamak görece kolay: https://cmph.sourceforge.net/chd.html

• Doğrudan bir girdi veri üretici ekleyebilseydiniz gerçekten ilginç olurdu. Gerçekte çoğu veri rastgele ikili veri değil, bir şekilde yapılandırılmış veridir ve belki de bu yapı sayesinde gerçekten çok iyi bir hash fonksiyonu elde edilebilir

• Tersinir işlemlerle sınırlamak matematiksel olarak güzel özellikler sağlasa da aynı zamanda birçok şeyi dışarıda bırakıyor.
  Benzer bir şey yaptığımda, girdi kümesini önceden bildiğiniz perfect hashing üzerine düşünüyordum. Genel yaklaşım bir sabitler dizisi kullanır ama özellikle girdiler zaten küçük tamsayılarsa daha da sıkıştırmanın mümkün olup olmadığına bakmak istiyordum. Elbette hash -= hash >> gap_index gibi bir şeyle bu yapılabilir.
  Bu yüzden muhtemelen yaklaşık 100 kadar ilkel işlemden oluşan bir liste denedim. Bazıları birbirinin tekrarıydı ama ayrı ayrı düşününce faydalıydı. Sonra sıkıldım ve bunu bir proje haline getirmedim

  • “Tersinir işlemlerle sınırlamak matematiksel olarak güzel özellikler sağlar” derken kastedilen nedir ve bu bağlamda tersinir işlemler neden arzu edilir?

• Tam olarak ne yaptığını pek anlayamadım. Tüm zamanların en iyisini mi arıyor? Değilse her çalıştırmada en iyi değerin neden değiştiğini merak ediyorum.
  Ayrıca belirli bir aralıktaki tamsayı değerlerinin, örneğin yalnızca 10.000 ile 200.000 arasının geleceğini biliyorsak, bu değerleri optimal sayıda hash bucket’a yerleştirecek iyi bir hash fonksiyonu bulma mekanizmasını bilen biri var mı diye de merak ediyorum

  • O çalıştırmada denenen değerler arasından en iyisini bulmak için değerleri rastgele deneme yöntemi kullanılıyor.
    Tek bir çalıştırmada tüm arama uzayını gezip mutlak optimumu bulmak pratikte mümkün değil ve deneme sırası da rastgele olduğu için sonuç her çalıştırmada değişebilir.
    Sadece “iyi” bir hash gerekiyorsa neredeyse her zaman genel amaçlı bir hash fonksiyonu kullanmak en iyisidir. Sayılar aşırı büyük ama aralık çok küçükse, minimum değerin yeniden 0 olması için bir ofset uygulayıp daha küçük ve daha hızlı bir hash kullanılabilir. Belirli bir aralık için “mükemmel seçim”i gerçekten bulmak istiyorsanız, buna en yakın yaklaşım muhtemelen bu rastgele yöntemdir; testleri o aralık üzerinde çalışacak şekilde değiştirmeniz yeterlidir

• İki çarpmada aynı sabitin kullanılmasının kod boyutunu küçültüp hesabı biraz hızlandırıp hızlandıramayacağını merak ediyorum.
  StackOverflow yanıtını da güncelledim: https://stackoverflow.com/questions/664014/what-integer-hash...