40 अरब if स्टेटमेंट्स

 (andreasjhkarlsson.github.io)
3 पॉइंट द्वारा GN⁺ 2023-12-29 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • % के बिना केवल comparison statements की सूची से even/odd तय करने का एक शरारती आइडिया 8-bit से 32-bit तक फैलते हुए compiler और executable file format की सीमाएँ उजागर करता है
  • Python code generator से if (number == n) अपने-आप बनाने पर 8-bit और 16-bit range तो चल गई, लेकिन 32-bit में comparison targets की संख्या लगभग 4.2 अरब तक फट गई
  • 32-bit C version ने 48 घंटे बाद लगभग 330GB C file बनाई, और MSVC line number limit तथा heap space की कमी के कारण compile नहीं कर पाया
  • PE executable की 4GB सीमा से बचने के लिए x86-64 instructions सीधे generate करके 40GB binary isEven.bin बनाई गई, और Windows memory mapping से उसे executable code की तरह call किया गया
  • अंतिम program ने atoi को strtoul से बदलने के बाद 32-bit के बड़े values भी सही पहचाने, और बड़े inputs पर Core i5 12600K·32GB memory·M.2 SSD environment में लगभग 10 सेकंड के भीतर result लौटाया

केवल comparison statements से even/odd पहचानना

  • शुरुआत social media पर देखे गए code screenshot से हुई, जिसमें classic even/odd problem को modulus operation के बिना हल करने की कोशिश थी
  • संरचना यह थी कि हर number के लिए if (number == n) रखा जाए, और वह number even है या odd, इसे printf से print किया जाए
  • पहले C example में uint8_t number = atoi(argv[1]); का उपयोग किया गया और 0 से 10 तक comparison statements हाथ से लिखे गए
  • /Od से optimization बंद रखी गई ताकि compiler algorithm न बदल दे
    • 0, 4 ने even प्रिंट किया
    • 3, 7 ने odd प्रिंट किया
    • 50, 11, 99 पर कुछ भी print नहीं हुआ
  • वजह यह थी कि आख़िरी if के बाद उन्हें संभालने के लिए कोई comparison statement नहीं था, इसलिए और ज़्यादा if statements की ज़रूरत पड़ी

Python से if statements generate करना

  • सारे comparison statements हाथ से लिखने के बजाय Python से C code output करने वाला meta programming तरीका अपनाया गया
  • Python script for i in range(2**8) से 0 से 255 तक comparison statements generate करती है
    • अगर i % 2 == 0 हो तो printf("even\n");
    • नहीं तो printf("odd\n");
  • generate किया गया C program पूरे 8-bit range में काम करता है
    • 99 है odd
    • 50 है even
    • 240 है even
    • 241 है odd

16-bit तक C compile से सफलता

  • इसी तरीके को uint16_t और range(2**16) तक बढ़ाया गया
  • generate हुई C file लगभग 1.3 लाख lines की थी
  • MSVC से compile करने के बाद यह कई values पर सही चली
    • 21000 है even
    • 3475 है odd
    • 3 है odd
    • 65001 है odd
    • 65532 है even
  • executable का size लगभग 2MB था, और 31.8GB memory वाले PC पर कोई समस्या नहीं हुई

32-bit C file और compiler की सीमाएँ

  • अगला लक्ष्य uint32_t और range(2**32) के साथ पूरे 32-bit range को comparison statements से संभालना था
  • 32-bit में 16-bit की तुलना में numbers की संख्या 65,536 गुना अधिक है
  • Python generator को 48 घंटे चलाने के बाद लगभग 330GB C file बनी
  • MSVC compile जल्दी ही सीमा पर पहुँच गया
    • warning C4049: compiler line number limit तक पहुँच गया और line number emission बंद कर दिया
    • line number limit थी 16777215
    • fatal error C1060: compiler is out of heap space
  • Windows के Portable Executable(.exe) format में 4GB से ऊपर जाना भी कठिन है, इसलिए 4 अरब से अधिक comparisons को executable में भरने वाला C compile path बंद हो गया
  • संबंधित सीमा के रूप में PE file maximum size का उल्लेख किया गया

सीधे machine code generate करके चलाना

  • compiler और executable file format की सीमाओं से बचने के लिए x86-64 instructions को सीधे binary में output करने वाले तरीके पर स्विच किया गया
  • target function IsEven रूप में थी, जो argument को ECX में लेती है और return value EAX में देती है
    • XOR EAX, EAX से default return value odd के लिए 0 रखी गई
    • हर number के लिए CMP ECX, i
    • even होने पर INC EAX के बाद RET
    • odd होने पर सीधे RET
  • x86-64 assembly और opcode का उपयोग हुआ, और हर instruction का opcode ChatGPT से पूछा गया
  • Python script ने isEven.bin को binary mode में खोलकर 0 से 2**32 - 1 तक हर number के लिए comparison instructions लिखीं
  • बनी हुई isEven.bin लगभग 40GB की थी और इसमें पूरे 32-bit number space के लिए लगभग 4.2 अरब comparisons शामिल थे

Windows memory mapping से 40GB code call करना

  • host C program ने isEven.bin खोली और पूरी file पढ़ने के बजाय Windows API से उसे memory map किया
  • execution flow इस प्रकार था
    • CreateFileA से isEven.bin को GENERIC_READ | GENERIC_EXECUTE permissions के साथ खोलना
    • GetFileSizeEx से 64-bit file size जाँचना
    • CreateFileMapping में PAGE_EXECUTE_READ देना
    • MapViewOfFile से executable और readable mapping बनाना
    • mapped pointer को int (*isEven)(int) function pointer में cast करके call करना
  • इस तरीके में 40GB file को ऐसे treat किया गया जैसे वह पूरी की पूरी memory में मौजूद हो, जबकि actual placement operating system की virtual memory पर छोड़ी गई
  • पहले test में ज़्यादातर values सही चलीं, लेकिन 4200000000 पर odd आया और नतीजा गलत निकला
  • वजह यह थी कि atoi unsigned बड़े values को सही तरह handle नहीं कर पाया; strtoul(argv[1], NULL, 10) पर बदलने के बाद 4200000000 ने even और 4200000001 ने odd प्रिंट किया

performance पर नज़र

  • छोटे numbers पर result तुरंत आया, और 2^32 सीमा के क़रीब बड़े numbers पर भी लगभग 10 सेकंड में result मिला
  • test environment था Core i5 12600K, 32GB memory, M.2 SSD
  • calculation के दौरान SSD की अधिकतम read speed लगभग 800MB/s देखी गई
  • 40GB data को disk से पढ़कर physical memory में map करने और CPU को cache का लगभग कोई फ़ायदा न मिलने जैसी स्थिति में भी इतनी speed मिलना एक चौंकाने वाला नतीजा रहा

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

1 टिप्पणियां

 
GN⁺ 2023-12-29
Hacker News की रायें

  • काश मेरे पास अपने शुरुआती दिनों में लिखे प्रोग्राम्स में से एक अब भी होता। 1996 में, जब मैं 16 साल का था, linear algebra की किताब के appendix में computer graphics वाला हिस्सा देखकर, पिछले semester में सीखी programming से कुछ shapes के rotating wireframe बनाने वाले program में पूरी तरह लग गया था
    इसी वजह से मैं class में लगभग fail होने वाला था, और उस समय मुझे arrays भी नहीं पता थे, इसलिए सभी vertices और rotation matrix elements अलग-अलग hardcoded variables थे, और matrix multiplication भी loops के बिना लंबी calculation expressions की list थी जिसे हर vertex के लिए copy-paste करके बदलना पड़ता था
    Screen पर draw करने के लिए किसी खास address से memory में लिखना पड़ता था, इसलिए pointers के बारे में जानता था, और vertices के बीच lines को rasterize करने वाला loop भी था। यानी आखिरकार arrays और indexing की concept मेरे पास पहले से थी, बस उन्हें खुद बनाना नहीं आता था

    • मेरे साथ भी कुछ ऐसा ही था। करीब 12 साल की उम्र में BASIC में Pac-Man game बनाने की कोशिश करते हुए मुझे लगा कि 4 ghosts की logic अलग-अलग (x1,y1) से (x4,y4) तक लिखनी पड़ेगी, और मैं अटक गया
      मैंने पिता से कहा कि मैं for loop के अंदर xn, yn जैसा लिखना चाहता हूं, जहां n बताए कि कौन-सा ghost है; उन्होंने BASIC की किताब निकाली और दिखाया कि x(n) सच में काम करता है
      शिक्षा की बात करते समय मुझे यह घटना याद आती है। Abstract concepts छात्र तब सबसे अच्छी तरह समझते हैं जब उन्हें सच में उनकी जरूरत होती है; जिस बात को पूरे दिन समझाने पर भी वे blank रहते हैं, वही जब उनकी अपनी problem solve करती है तो कुछ seconds या minutes में फिट बैठ जाती है
    • जाहिर समाधान यह है कि screen के निचले हिस्से को working memory की तरह इस्तेमाल करते हुए ऊपर का हिस्सा draw किया जाए। जब तक नीचे तक पहुंचेंगे, तब तक calculations लगभग बची नहीं होंगी, और तेज GPU memory इस्तेमाल होगी, इसलिए यह CUDA जैसा और बहुत AI जैसा है
    • शुरुआती freelancing के दिन याद आ गए। मेरे पास सिर्फ एक छोटा VPS था जिस पर PHP चलती थी, और 2002/2003 के हिसाब से काफी बड़ी 5,000–10,000 rows वाली spreadsheets process करनी थीं
      Computer science major नहीं था, इसलिए file को सबसे बेवकूफी वाले तरीके से read किया, और nested loops की वजह से memory usage और space shortage errors लगातार आते रहे। इसलिए जहां भी संभव था, मैंने $variable = null डाल दिया, और सच में वह चल गया
    • Middle school में बनाया गया मेरा hit project, TI-83 के लिए Snake, भी ऐसा ही था। Snake के हर segment के x, y coordinates को अलग-अलग variables में रखा था, और TI-83 BASIC में usable variables की संख्या limited थी, इसलिए snake की length भी उससे ज्यादा नहीं बढ़ सकती थी
    • Documentation देखकर print, input, if, goto खुद सीखने के बाद, दूसरों से मदद मांगकर मैंने पहली GWBasic feature जो सीखी वह chain थी

  • लगता है इसे जरूरत से ज्यादा over-engineer किया गया है। समझ नहीं आता code generation तक क्यों करना है; इसे एक simple for loop से solve किया जा सकता है
    isOdd में 0 से n तक odd = !odd repeat करके फिर return कर दें
    Playground link: https://go.dev/play/p/8TIfzGrdWDF
    अभी profiling नहीं की है, लेकिन intuition और industry experience के हिसाब से यह fast है

    • अगर सच में production-quality implementation चाहिए, तो हमेशा recursion इस्तेमाल करनी चाहिए। अगर n == 0 है तो false, positive हो तो !isOdd(n-1), और negative हो तो !isOdd(n+1) return करें
    • इस approach का Rust version fast है, यह verify किया जा सकता है
      Assembly testq %rdi, %rdi, setg %al, andb %dil, %al, retq जैसी निकलती है
      Build के बगल में ... दबाने पर assembly देख सकते हैं: https://play.rust-lang.org/?version=stable&mode=release&edit...
      अफसोस, लगता है Go Playground assembly output support नहीं करता
    • Even function को भी भूलना नहीं चाहिए। isEven(n int64) bool { return !isOdd(n) }
    • अगर n = infinity हो, तो यह infinite repeat करेगा
    • इसे tail recursion से improve किया जा सकता है

  • यह तरीका is-even npm package[1] के लिए बिल्कुल फिट है, जिसके साप्ताहिक downloads 196,023 हैं, या is-odd npm package[2] के लिए, जिसके 285,501 हैं। npm install टाइप करते ही अगर 40GB वाला is-even और 40GB वाला is-odd डाउनलोड होना शुरू हो जाए, तो मज़ा आ जाएगा
    [1] https://www.npmjs.com/package/is-even
    [2] https://www.npmjs.com/package/is-odd

    • यह हमेशा बताने लायक बात है कि ये packages एक समर्पित npm spammer[1] की कोशिश का नतीजा हैं, जो जितनी ज़्यादा node_modules directories में घुसना चाहता था
      ansi-colors में भी रंगों का एक पूरा package ही नहीं, बल्कि हर रंग के लिए अलग package है, और इसके अलावा भी न जाने क्या-क्या है। ऐसी चीज़ें CLI tools या दिखने में भरोसेमंद packages में शामिल हो जाती हैं और एक-दूसरे को reference करती हैं, इसलिए किसी असली project में भी सिर्फ़ एक innocuous dependency से jonschlinkert के दर्जनों packages खिंचकर आ सकते हैं
      [1] https://www.npmjs.com/~jonschlinkert
    • हैरानी की बात है कि “खुद को repeat मत करो” को सबसे शुद्ध रूप में मानने का नतीजा यह है कि is-even, is-odd पर निर्भर करता है
      var isOdd = require('is-odd'); के बाद बस module.exports = function isEven(i) { return !isOdd(i); }; ही सब कुछ है
    • इस व्यक्ति को पता नहीं था, लेकिन हमारे 2 frontend apps के source trees देखने पर पता चला कि is-odd जिस is-number package पर निर्भर करता है, उसे कई दूसरे packages भी खींच रहे थे
      JS में कोई value number type है या नहीं, यह पता लगाना अगर सच में इतना झंझट वाला है, तो शायद यह package मायने रखता हो, लेकिन लगता है कि दूसरे built-in types भी संभालने वाला कोई ज्यादा general package होना चाहिए
      हालांकि isNumber उन strings को भी number मानता है जिन्हें number में बदला जा सकता है, जिससे अजीब नतीजे आ सकते हैं। जैसे const a = '1'; isNumber(a); // true, लेकिन const b = a + a; string '11' बन जाता है
      बेशक 2*a का नतीजा 2 होता है और 1+'1' तथा '1'+1 दोनों standard JS वाली मूर्खता के तहत '11' बनते हैं, लेकिन इसी वजह से '1' को number कहना शायद सही जवाब न हो। फिर भी यह package पिछले हफ्ते 4.6 करोड़ बार डाउनलोड हुआ, और Christmas के कारण यह कम था; उससे पिछले हफ्तों में औसत करीब 7 करोड़ था। हमारे project की तरह, ज़्यादातर downloads dependencies के रूप में ही होंगे
    • मैंने कभी nullll package[1] बनाया था, जो बस एक null export करता है लेकिन 400MB memory इस्तेमाल करता है; किसी वजह से HN पर उसे flag कर दिया गया[2]
      GitHub पर 41 stars और 100% test coverage[3] के साथ, वह निश्चित रूप से production-ready था
      [1]: https://github.com/mickael-kerjean/nulll
      [2]: https://news.ycombinator.com/item?id=17072675
      [3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
    • असल में JavaScript numbers u32 नहीं, बल्कि f64 होते हैं, इसलिए इतना काफी नहीं है। सिर्फ़ safe integer range support करने पर भी यह 2⁵⁴ है, जो 2³² से 40 लाख गुना से भी ज्यादा बड़ा है
      machine code का size हर branch पर 4 bytes, यानी करीब 40% ही बढ़ेगा, इसलिए यह लगभग 224 exbibytes तक पहुंच जाएगा। वह भी तब, जब आखिरी 10 bits को आलस में छोड़ दिया जाए
      सही तरीके से करना हो तो शायद उसे 1,000 से और multiply करना पड़े, और मैंने NaN patterns पर गहराई से नहीं सोचा है, इसलिए यह थोड़ा छोटा भी हो सकता है। bigint तक support कर दिया तो शायद बस अनंत ही हो जाए

  • समझ नहीं आता कि इसे जानबूझकर इस तरह क्यों करना है। database का आविष्कार ठीक इसी काम के लिए हुआ था। SQLite database में numbers और even/odd classification की mapping store कर दो
    इस तरीके का एक फायदा यह भी है कि जब भी किसी number की classification odd से even में बदलती है, तो program update करने की जरूरत नहीं पड़ती

    • databases को भी maintenance और updates चाहिए होते हैं। इसके बजाय एक Ethereum contract बना देना बेहतर है, ताकि दूसरे लोग oracle की तरह काम करें और हमेशा सही जवाब लौटाने के लिए उन्हें आर्थिक incentives मिलें
    • यह उस तरह का data लगता है जिसे Wikidata में होना चाहिए। तब local database रखने की जरूरत नहीं होगी, बस एक तेज़ HTTPS request करनी होगी
      एकमात्र समस्या तब हो सकती है जब TLS खुद even/odd function पर निर्भर हो, लेकिन शायद ऐसा नहीं होगा
    • table का नाम even_or_odd रखो और columns is_odd, is_even, is_zero, is_one, is_two, is_three वगैरह रख दो। 1 को is_odd,is_one और 2 को is_even,is_two के रूप में डाल दो
    • सही है, लेकिन जाहिर है XML database इस्तेमाल करना चाहिए
      इससे data portability में भी मदद मिलेगी, और जब हाथ से verify करना पड़े तो इसे human-readable format में रखा जा सकेगा
    • AWS का Elastic Cloud Parity पहले से यह देता है, और वह कहीं ज्यादा scalable है

  • यहां पढ़ी गई posts में से यह सबसे मजेदार posts में से एक है। source code online डालना चाहिए ताकि ChatGPT इसे “train” कर सके

    • तब तो वह उसकी strict license का पक्का उल्लंघन होगा
      /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/
      इतना elegant code हो तो भला कोई दोष कैसे दे सकता है?

  • मज़ाक बिल्कुल समझ नहीं आया। जिसने इसे बनाया, वह तो ठीक है, लेकिन अभी के 1198 upvotes समझ नहीं आ रहे
    गणना-योग्य values के लिए lookup table न तो नया है और न ही मज़ाक। यह time/memory trade-off का वास्तविक समाधान है, और लेखक भी यह जानता है
    समस्या अपने-आप में बेतुकी है, लेकिन इतनी primitive है कि इसके संभव होने पर कोई शक नहीं था; और अपने कंप्यूटर पर करीब 10 सेकंड तक 40GB program को process करने के observation के अलावा कोई वास्तविक measurement भी नहीं था
    तो हमने क्या सीखा? कि exe file 4GB से बड़ी नहीं हो सकती? कि if अगर 2^32 हों तो program करीब 300GB का होता है? समझ नहीं आता कि 1198 लोगों को यह दिलचस्प क्यों लगा
    “Hexing the technical interview” या SIGBOVIK लेखों के उलट, यह पागलपन नहीं, बस निरर्थक लगता है

    • मज़ाक यह है कि उसने इसे सचमुच कर दिया। दशकों से लोग ऐसे मज़ाक करते आए हैं, और इस पागल इंसान ने इसे वाकई कर दिखाया
      यह इतना extreme था कि कोई compiler इसे handle नहीं कर पाया, और ज्ञात assembler भी नहीं। इसलिए इसे चलाने के लिए उसे सीधे machine-code binary generate करनी पड़ी, और यह सच में चला। पागलपन है
    • यह कहना सही है कि गणना-योग्य value की lookup table नई चीज़ नहीं है, लेकिन optimization बंद हो तो 4 अरब if statements lookup table में compile नहीं होंगे
      हर if को input से match होने के लिए क्रम से evaluate किया जाएगा, और original program के output में छोटे numbers पर बहुत जल्दी खत्म होना भी इसे support करता है। क्योंकि छोटे numbers code के शुरुआती हिस्से में हैं
      इसके उलट, 4 अरब case वाला switch statement हो तो मैं उम्मीद करूंगा कि वह किसी lookup table में compile होगा। हालांकि data type unsigned integer होने पर बिना optimization compile किया code कैसा दिखेगा, यह नहीं जानता
    • कभी-कभी लोग हंसाने के लिए कुछ करते हैं
    • मैंने इसे उन blog posts की parody के रूप में समझा जो conventional wisdom के खिलाफ प्रतिक्रिया कितनी निरर्थक हो सकती है, इस पर satire करती हैं। काफी dry joke है

  • कमाल की technology है। इसे AWS को बेच देना चाहिए ताकि वे इसे Enterprise-ready AWS EvenOrOdd API के रूप में उन सबको उपलब्ध करा सकें जिन्हें 40GB executable को सही से host करना नहीं आता
    cloud की ताकत हो तो इस program को रोका नहीं जा सकेगा

    • यह तो बिल्कुल Lambda function बनने का इंतज़ार करता दिख रहा है

  • हैरानी है कि किसी ने बीच में यह नहीं टोका कि program ने सिर्फ 800 MB/s * 10 सेकंड के disk reads से 40GB instructions को “process” कर लिया
    मेरा अनुमान है कि OS level पर कोई smart caching रही होगी, लेकिन फिर इसका मतलब है कि n के 2^32 के करीब वाले benchmark ठीक से run नहीं हुए
    या फिर CPU इतना smart हो सकता है कि वह लाखों instructions आगे jump कर जाए

    • “31.8GB memory वाली powerful gaming machine” हो तो, अगर file system caching repeated/sequential scan में कुछ हद तक मजबूत हो, तो दोबारा चलाने पर सिर्फ करीब 8GB पढ़ना पड़ेगा
      पहले मुझे लगा math गलत होगा, लेकिन मोटा-मोटी हिसाब लगाने पर यह काफी plausible लगता है। numbers भी सभी vague rounded values थे, और input value भी absolute maximum नहीं बल्कि बस high value थी, इसलिए और भी
    • शायद compression था या data RAM में बचा हुआ था। CPU यहां smart नहीं बन सकता, क्योंकि उसे भविष्य के if क्या हैं, यह पता नहीं होता
      उसे यह भी नहीं पता कि वे code blocks क्रम में हैं या unique हैं, या valid instructions भी हैं या नहीं। theory में program चलने के दौरान किसी if को infinite loop में बदला भी जा सकता है। हालांकि OS इसकी अनुमति नहीं देगा
    • predictive paging भी होती है। OS अंदाज़ा लगा सकता है कि अगला कौन-सा page request होगा
    • CPU की वजह से नहीं हो सकता। असल में यह memory-mapped code है, और branch predictor page fault trigger करके अगला code page load नहीं करा सकता होगा
      सच में curiosity है। linear access pattern मदद तो करेगा, लेकिन 800 MiB/s?
    • program को mmap किया जाता है, इसलिए unused pages सिर्फ page table entries लेते हैं और load नहीं होते। असल में load केवल वही page होता है जिस पर सीधे jump किया गया हो। neat trick है

  • दूरदर्शी genius Ross van der Gussom अब मेरा पसंदीदा mythical creature है

    • Python को C को script करने के तरीके के रूप में देखिए और compilation का अधिकतर या पूरा हिस्सा skip कर दीजिए। अगर Python धीमा है, तो शायद आप उसे गलत तरह से इस्तेमाल कर रहे हैं
      यह लेख recommend करता हूं: https://cerfacs.fr/coop/fortran-vs-python
    • मैंने web search किया कि “Ross van der Gussom” कोई inside joke है या नहीं, लेकिन top 2 search results original post और यह parent comment ही थे

  • पूरा लेख LLM development की allegory जैसा लगा। अगर कोई आलोचक लिखता, तो कहता कि बहुत भारी resources और “training data” लगाकर solution को “memorize” करना है
    सोच रहा हूं कि क्या लेखक का यही intent था

    • सिर्फ title देखकर लगा था कि यह किसी नए 4B model की announcement post होगी, तो शायद हां
    • title पढ़कर मुझे पूरा यकीन था कि यह LLM पर लेख होगा
    • सही। यह for loop करने वाले 40B LLM model जैसा दिखता है। यह allegory ही लेख की असली motivation लगती है, और यह engineering story नहीं बल्कि आने वाली absurdity पर लिखा हुआ लगता है