ऑटोमेटेड integer hash function खोज तकनीक

 (github.com/skeeto)
3 पॉइंट द्वारा GN⁺ 2024-05-06 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Hash Function Prospector एक ऐसा टूल है जो integer hash functions को बड़ी संख्या में random तरीके से generate करता है, उन्हें JIT compile करता है, avalanche behavior का मूल्यांकन करता है, और फिर मौजूदा best function को C syntax में output करता है
  • मूल्यांकन के लिए avalanche score का उपयोग होता है, जो किसी एक input bit को flip करने पर औसतन fixed रहने वाले output bits की संख्या है; जितना कम हो उतना बेहतर, और ideal value 0 है
  • खोज का लक्ष्य 32-bit और 64-bit integer hash functions हैं; JIT compiler की वजह से टूल चलाना सिर्फ x86-64 पर supported है, लेकिन खोजे गए functions दूसरे environments में भी इस्तेमाल किए जा सकते हैं
  • खोजे गए प्रमुख functions xorshift-multiply-xorshift structure का उपयोग करते हैं; 2-round lowbias32, MurmurHash3 32-bit finalizer की तुलना में बहुत छोटे अंतर से lower bias दिखाता है, और 3-round triple32 theoretical bias limit के करीब है
  • 32-bit functions के लिए accurate bias measurement -E और -e से किया जा सकता है; 16-bit hashes के लिए अलग टूल hp16 है, और C integer promotion rules पर ध्यान देना जरूरी है

Hash Function Prospector की भूमिका

  • Hash Function Prospector एक automated integer hash function discovery टूल है
  • यह अरबों integer hash functions को random तरीके से generate करता है, उन्हें JIT compile करता है, और फिर avalanche behavior का मूल्यांकन करता है
  • generated functions में से मौजूदा best function C syntax में output होता है
  • संबंधित लेख के रूप में Prospecting for Hash Functions लिंक किया गया है

मूल्यांकन मानदंड और support scope

  • avalanche score वह average number of output bits है जो input का एक bit flip करने पर fixed रहते हैं
    • score जितना कम हो, उतना बेहतर
    • आदर्श रूप से सभी output bits 50% probability से flip होते हैं और score 0 हो जाता है
  • Prospector 32-bit और 64-bit integer hash functions generate कर सकता है
  • पूरे options -h usage में देखे जा सकते हैं
  • JIT compiler की वजह से टूल खुद सिर्फ x86-64 support करता है
    • हालांकि खोजे गए hash functions कहीं भी इस्तेमाल किए जा सकते हैं

खोज में इस्तेमाल होने वाले reversible operations

  • generator चुने गए 9 reversible operations से random तरीके से functions compose करता है
  • operations की सूची इस प्रकार है
    • 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)
  • तकनीकी रूप से x = ~x को x ^= constant से express किया जा सकता है, लेकिन generator के उस XOR constant को संयोग से चुनने की संभावना कम होने के कारण इसे अलग operation माना जाता है

खोजे गए 32-bit hash functions

  • 2-round functions

    • उपयोगी discovered function families में से एक 2-round xorshift-multiply-xorshift structure है
    • TheIronBorn ने combinatorial optimization का उपयोग करके इस structure के known optimal parameters खोजे, और result [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501 है
    • lowbias32 एक 32-bit 2-round permutation है, जिसका bias कम है और यह MurmurHash3 32-bit finalizer की तुलना में बेहद छोटे अंतर से lower bias दिखाता है
    • lowbias32 का exact bias 0.17353355999581582 है
    • structure Prospector ने खोजा था, और parameters hill climbing तथा genetic algorithm से adjust किए गए
    • inverse function lowbias32_r भी दिया गया है
    • prospector32 सिर्फ Prospector का उपयोग करके खोजा गया function है
    • exact bias 0.34968228323361017 है
    • इसका bias ऊपर वाले lowbias32 से ज्यादा है
    • alternate multiplication constants की random search करने के लिए pattern को इस तरह specify किया जाता है
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • 3-round functions

    • इसी structure में एक और multiply-xorshift round जोड़ने पर सावधानी से चुने गए parameters के साथ theoretical bias limit तक पहुंचा जा सकता है
    • triple32 का exact bias 0.020888578919738908 है
    • README इसे सभी 32-bit integers के random permutation जैसे perfect PRF से indistinguishable बताता है
    • inverse function triple32_r भी दिया गया है
    • 3-round constants की सूची में 0.020888578919738908 से लेकर लगभग 0.022984943828687553 तक के low-bias results शामिल हैं
    • triple32inc, जो triple32 के आगे increment operation जोड़ता है, hash(0) = 0 problem को तोड़ता है और bias को थोड़ा और कम करता है
    • exact bias 0.020829410544597495 है
    • inverse function triple32inc_r अंत में x-- perform करता है

exact bias measurement

  • -E mode दिए गए hash function के bias का evaluation करता है
  • default रूप से Prospector bias को तेजी से evaluate करने के लिए estimates का उपयोग करता है
    • यह estimate non-deterministic होता है और results में काफी noise होती है
  • exhaustive search से exact bias measure करने के लिए -e option का उपयोग किया जाता है
  • test किए जाने वाले function को दो तरीकों से define किया जा सकता है
    • -p और pattern से define करना
    • -l और hash() function वाली shared library से define करना
  • shared library वाला तरीका उन hash functions को भी test करने देता है जिन्हें Prospector के limited function representation से express नहीं किया जा सकता
  • default input को 32-bit hash function माना जाता है
  • -8 switch 64-bit function को estimate method से test करता है
    • 64-bit hash functions में बहुत ज्यादा समय लगता है, इसलिए exact exhaustive test नहीं है

16-bit hashes के लिए hp16

  • 16-bit hashes की constraints अलग हैं, इसलिए अलग टूल hp16 दिया गया है
  • 32-bit और 64-bit Prospector के विपरीत, hp16 पूरी तरह portable है और लगभग हर system पर चल सकता है
  • hp16 128KiB s-box generation और evaluation भी कर सकता है
  • क्योंकि 16-bit hash उन machines पर जरूरी हो सकता है जिनमें fast multiplication instruction नहीं है, search के दौरान कुछ operations को omit करने के options भी हैं
    • -m
    • -r

16-bit results और C implementation में सावधानियां

  • अब तक के 16-bit results के examples इस प्रकार हैं
    • 2-round xorshift-multiply hash16_xm2: bias 0.0085905051336723701
    • 3-round xorshift-multiply hash16_xm3: bias 0.0045976709018820602
    • multiplication-free hash16_s6: bias 0.023840118344741465
  • multiplication-free hash16_s6 को एक खास xorshift-multiply form के equivalent बताया गया है
  • hp16 -Xn3 से short search में मिला अच्छा 3-round xorshift hash, hp16 -S के अच्छे s-box का करीबी approximation है
  • 16-bit operations को C में लिखते समय integer promotion rules पर ध्यान देना चाहिए
    • उदाहरण के लिए 32-bit implementation में unsigned 16-bit operands signed 32-bit integer में promote हो सकते हैं
    • ऐसे में कुछ स्थितियों में गलत result आ सकता है
    • यह program जो C code output करता है, उसमें जहां जरूरत हो वहां 16-bit operations को unsigned int में promote करने का ध्यान रखा गया है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-05-06
Hacker News टिप्पणियाँ

  • मुझे व्यक्तिगत रूप से नहीं पता, लेकिन उसका कोड मुझे पसंद है
    खासकर JSON लाइब्रेरी https://github.com/skeeto/pdjson, option parsing लाइब्रेरी https://github.com/skeeto/optparse और https://github.com/skeeto/getopt, branchless UTF-8 decoder https://github.com/skeeto/branchless-utf8, lock-free stack https://github.com/skeeto/lstack और trie लाइब्रेरी https://github.com/skeeto/trie अच्छी हैं
    यह भी पसंद है कि ऊपर के सभी प्रोजेक्ट The Unlicense के तहत वितरित होते हैं

    • Skeeto तो लेजेंड-स्तर का है। मेरे हिसाब से वह Fabrice Bellard के बराबर है
      मैं उसे GitHub पर कई सालों से फ़ॉलो कर रहा हूँ, और वह हमेशा दिलचस्प छोटे और अजीब niche tools निकालता रहता है। उदाहरण के लिए Branchless UTF-8 काफ़ी मशहूर है
    • वह elfeed https://github.com/skeeto/elfeed का लेखक भी है। यह “An Emacs web feeds client” है, और उसकी उस मिनिमल implementation से मुझे बहुत प्रेरणा मिली है

  • नमस्ते, मैं वही व्यक्ति हूँ जिसने MurmurHash बनाया था। यह दिलचस्प काम है, और यह मज़ेदार है कि multiplication-shift-XOR तरीका इतने लंबे समय तक अच्छी तरह टिका रहा

    • XOR-shift, multiplication की दो कमज़ोरियों की भरपाई करता है। ऊँचे बिट्स को उनके ऊपर से प्रभावित करने वाला कोई बिट नहीं होता, और निचले बिट्स को उनके नीचे से प्रभावित करने वाला कोई बिट नहीं होता
    • MurmurHash की तरह, यह भी non-cryptographic hash के लिए ही बनाया गया लगता है
      लेकिन avalanche + bias वाला विचार काफ़ी हद तक गायब दिखता है। उदाहरण के लिए अंत में दी गई triple32 function का सही bias 0.020888578919738908 है, और जब FabriceNeyret2 इसे ShaderToy में implement करता है, तो ऐसी images मिलती हैं: https://www.shadertoy.com/view/WttXWX या https://i.imgur.com/qU2P5rx.png
      लेकिन अगर simple normal map gradient differential किया जाए, तो काफ़ी साफ़ “crystal” lines दिखाई देती हैं। ऐसी ridge जैसी आकृतियों के लिए शायद कोई technical term होगा: https://i.imgur.com/IHWT1GM.png
      और जोड़ूँ तो, मुझे लगता है यह पूरा विचार पहले से ही लगभग 5 साल पुराना है: https://nullprogram.com/blog/2018/07/31/

  • अच्छे hash functions विकसित करने के अनुभव की वजह से मैं अक्सर automatic hash search के विचार के बारे में सोचता रहा हूँ
    ऐसा काम देखकर अच्छा लगा। अगर output को अपने-आप evaluate करने के लिए इसे Frank J. T. Wojcik के पुराने hash test suite के बहुत बेहतर और तेज़ variant SMHasher3 से जोड़ा जाए, तो और अच्छा होगा। speed के लिए कुछ tests ही लेकर जल्दी fail भी कराया जा सकता है
    इसे 64-bit और 128-bit hash तक बढ़ाना भी अच्छा होगा, लेकिन जाहिर है search space और बड़ा हो जाएगा। इसी संदर्भ में, Rain में इस्तेमाल के लिए values चुनने हेतु मैंने 64-bit prime multiplications में avalanche मापने वाला NodeJS कोड भी बनाया था
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • इसे RISC-V bit manipulation extension में उपलब्ध operations तक generalize किया जाए तो दिलचस्प हो सकता है। बाद में जब वे instructions ज़्यादा व्यापक हो जाएँ, तब इस्तेमाल के लिए शायद कुछ मज़बूत functions मिलें
    carry-less multiplication भी reversible operations के सेट को बढ़ा सकता है, और कुछ मौजूदा hardware पर तेज़ है। CRC भी कुछ हद तक संबंधित है, लेकिन यह ज़्यादा व्यापक hardware set पर संभव है, और CLMUL से जो मिल सकता है उसका एक सख्त subset होना चाहिए
    hash के कई उपयोगों में hash value के सिर्फ सबसे निचले या सबसे ऊँचे बिट्स ही मायने रखते हैं, इसलिए सबसे ऊँचे/सबसे निचले बिट रेंज के bias या कई संख्याओं से भाग देने पर शेषफल का मूल्यांकन करना भी दिलचस्प होगा। कोई function पूरे output को देखने पर निष्पक्ष लग सकता है, लेकिन जो metrics पूरा output नहीं देखते, या ASCII text जैसे non-uniform inputs पर, वह बेहतर भी हो सकता है या बदतर भी

  • क्या कोई समझा सकता है कि यह क्यों शानदार है और इसका उपयोग कहाँ होता है?

    • यह हैश फ़ंक्शन बनाने के लिए command sequence जनरेट करने और यह आकलन करने वाला टूल लगता है कि वह हैश फ़ंक्शन कितना अच्छा है।
      लगता है कि लक्ष्य metric यह है कि जब input bit का एक हिस्सा बदलता है, तो जितने संभव हो उतने output bits यथासंभव random तरीके से बदलें। यह जनरेट किए गए फ़ंक्शनों में से सबसे अच्छे हैश फ़ंक्शन का C code आउटपुट करता है।
      इसलिए, जब आपको हैश फ़ंक्शन चाहिए लेकिन लगता है कि मौजूदा फ़ंक्शन पर्याप्त अच्छे नहीं हैं, या हैश फ़ंक्शन पर शोध करते समय किसी नई संरचना के आइडिया चाहिए हों, तब यह उपयोगी है। Code generation अपने-आप में भी शानदार है, और random तरीके से करना उससे भी शानदार genetic programming की पहली सीढ़ी है। और लगता है कि इंसान लगभग 15 साल से कंप्यूटर को CPU cycles जलाकर ऐसे hash निकालने में लगाना पसंद करते हैं जिनका ज़्यादातर कभी उपयोग नहीं होगा
    • ऐसे फ़ंक्शन hash table के लिए अनिवार्य हैं। संबंधित नामों में hash map और hash set भी आते हैं।
      Hash table एक बेहतरीन data structure है जो कई algorithms को सरल और efficient तरीके से implement करने देता है। यह दक्षता इस बात पर निर्भर करती है कि क्या आप data के लिए छोटा, जैसे 32-bit या 64-bit, और लगभग unique hash बना सकते हैं।
      उदाहरण के लिए, अगर आप usernames को hash कर रहे हैं और नाम के सिर्फ पहले अक्षर का ASCII code इस्तेमाल करते हैं, तो बहुत से usernames एक ही संख्या पर map हो जाएंगे और चीज़ें ठीक से काम नहीं करेंगी। इसे collision कहते हैं, और collisions ज़्यादा हों तो hash table बहुत inefficient हो जाती है।
      इससे बेहतर तरीका है कि पूरे username से bits लेकर उन्हें किसी तरह mix किया जाए ताकि throwaway_1237 और throwaway_12373 अलग-अलग संख्याएँ बनें। Hash function यही mapping करता है, और avalanche property बताती है कि वह collisions से बचने में कितना अच्छा है।
      आम तौर पर वास्तविक hash function की speed और collision avoidance के बीच trade-off होता है। विश्व-स्तरीय hash functions अक्सर अजीब constants से multiply, XOR और shift जैसी काफ़ी विचित्र चीज़ें करते दिखते हैं, और किसी इंसान के लिए ऐसे कठिन फ़ंक्शन को देखकर इसकी performance का अनुमान लगाना बहुत मुश्किल होता है।
      यह code random तरीके से कई hash functions आज़माता है और उन्हें एक-दूसरे से मुकाबला कराता है। अगर यह सफल हो, तो यह कई भाषाओं और libraries में इस्तेमाल होने वाले एक core data structure की वास्तविक performance सुधार सकता है, इसलिए यह शानदार है
    • यह integer के लिए hash function है, इसलिए जहाँ set या map में fast integer hash चाहिए वहाँ इसका उपयोग हो सकता है। अगर फ़ंक्शन पर्याप्त अलग-अलग दिशा में फैलते हों, तो यह Bloom filter के लिए fast hash भी दे सकता है

  • कुछ हफ़्ते पहले मैंने Go में 1brc implement किया था, https://github.com/infogulch/1brc-go, और इस repository को देखकर मुझे ऐसा custom perfect hash function ढूँढने की प्रेरणा मिली जो हर station को बिना collision उसके अपने bucket में डाल दे।
    फिर मैंने वह rule देखा कि program शुरू होने से पहले data के हिसाब से hash function को customize नहीं किया जा सकता, तो मैंने यह आइडिया छोड़ दिया।
    मैंने random constants, seed values, multiplication constants, shift/rotation amounts आदि जाँचने और collision buckets की संख्या तथा collisions की संख्या के आधार पर अब तक मिले सबसे अच्छे constants को प्रिंट करने के लिए एक test harness बनाया। लगता है कि लगभग 40% load factor पर मैं इसे इतना घटा पाया था कि सिर्फ एक bucket में दो values टकरा रही थीं। दिलचस्प बात यह थी कि सबसे performant constants में, दूसरे constants से स्वतंत्र रूप से, मिलती-जुलती shift positions की संख्या थी, इसलिए अंत में मैंने उन values को hardcode कर दिया

    • जानकारी के लिए, minimal perfect hash function ढूँढने की बेहतर techniques मौजूद हैं। इसे implement करना काफ़ी आसान है: https://cmph.sourceforge.net/chd.html

  • अगर इसमें अपना input data generator डालना संभव हो, तो यह सच में बहुत दिलचस्प होगा। व्यवहार में, data अक्सर random binary data नहीं होता बल्कि किसी न किसी तरह से structured होता है, और उसी संरचना की वजह से शायद बहुत अच्छा hash function मिल सके

  • इसे reversible operations तक सीमित करने से गणितीय रूप से कुछ अच्छे पहलू मिलते हैं, लेकिन साथ ही बहुत कुछ बाहर भी हो जाता है।
    जब मैंने कुछ ऐसा ही किया था, तब मैं input set को पहले से जानने वाली perfect hashing के बारे में सोच रहा था। सामान्य तरीका constants की array का उपयोग करता है, लेकिन खासकर अगर input पहले से छोटे integers हों, तो मैं देखना चाहता था कि क्या इसे और compress किया जा सकता है। स्वाभाविक रूप से, hash -= hash >> gap_index जैसी चीज़ें संभव हैं।
    इसलिए मैंने शायद लगभग 100 primitive operations की सूची आज़माई थी। उनमें से कुछ एक-दूसरे से overlap करती थीं, लेकिन अलग-अलग सोचने पर उपयोगी थीं। फिर मैं बोर हो गया और इस project के साथ कुछ नहीं किया

    • “इसे reversible operations तक सीमित करने से गणितीय रूप से अच्छे पहलू मिलते हैं” से क्या मतलब है, और इस संदर्भ में reversible operations क्यों वांछनीय हैं?

  • मुझे ठीक-ठीक समझ नहीं आ रहा कि यह क्या कर रहा है। क्या यह अब तक का सर्वश्रेष्ठ ढूँढ रहा है? अगर नहीं, तो हर run पर सर्वोत्तम मान क्यों बदल जाता है, यह जानना दिलचस्प होगा।
    और मैं यह भी जानना चाहूँगा कि अगर आपको पता हो कि integers सिर्फ किसी निश्चित range में आएँगे, जैसे 10,000 से 200,000 के बीच, तो क्या कोई ऐसा mechanism जानता है जो उन values को hash buckets की इष्टतम संख्या में डालने के लिए अच्छा hash function खोज सके

    • यह उस run में आज़माई गई values में से सर्वश्रेष्ठ ढूँढने के लिए values को random तरीके से आज़माने का तरीका है।
      एक ही run में पूरे search space को खंगालकर absolute optimum ढूँढना व्यवहारिक रूप से असंभव है, और क्योंकि आज़माने का क्रम भी random है, इसलिए हर run पर मान बदल सकता है।
      अगर आपको बस “अच्छा” hash चाहिए, तो लगभग हमेशा सामान्य-purpose hash function का उपयोग करना सबसे अच्छा होता है। अगर संख्याएँ बहुत बड़ी हों लेकिन range बहुत छोटी हो, तो minimum को फिर से 0 बनाने के लिए offset लगाकर छोटा और तेज़ hash इस्तेमाल किया जा सकता है। अगर आप किसी सटीक range के लिए “perfect choice” ढूँढना चाहते हैं, तो शायद यह random approach उसके सबसे क़रीब है, और आप tests को उसी interval पर चलाने के लिए बदल सकते हैं

  • मुझे जिज्ञासा है कि अगर दो multiplications में एक ही constant इस्तेमाल किया जाए, तो क्या code size कम होने से computation भी थोड़ा तेज़ हो सकता है
    मैंने StackOverflow answer भी update किया है: https://stackoverflow.com/questions/664014/what-integer-hash...