JavaScript से 2 करोड़ particles का simulation

 (dgerrells.com)
4 पॉइंट द्वारा GN⁺ 2024-07-09 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • केवल CPU पर चलने वाले JavaScript particle simulation से शुरुआत कर, मोबाइल पर 10 लाख particles 60fps का लक्ष्य हासिल किया गया और अंतिम उदाहरण को 2 करोड़ particles तक बढ़ाया गया
  • performance की कुंजी object arrays से बचकर TypedArray और SharedArrayBuffer के साथ particle data को contiguous memory में रखना, और Web Worker के जरिए काम को CPU cores में बाँटना था
  • असली bottleneck particle position calculation से ज़्यादा rendering और memory access में दिखा, और pixel buffer पर random writes ने CPU cache miss पैदा किए
  • Worker-प्रति pixel buffer, postMessage synchronization, double buffering, per-pixel particle count grid, और GPU texture rendering के जरिए bottlenecks को चरणबद्ध तरीके से कम किया गया
  • अंतिम architecture में CPU simulation करता है और GPU screen resolution आकार की grid texture render करता है, जिससे M1 Mac पर 2 करोड़ particles लगभग 20fps पर चल पाए

लक्ष्य और बुनियादी approach

  • चुनौती यह थी कि WebAssembly के बिना pure JavaScript और केवल CPU से मोबाइल पर 10 लाख particles को 60fps पर simulate किया जाए
  • साधारण JavaScript object arrays को mobile single-core performance और memory layout, दोनों के लिहाज़ से सीमित मानकर, data को contiguous arrays में संभालने का तरीका चुना गया
  • बड़े पैमाने की calculation में ऐसी सघन contiguous memory arrays महत्वपूर्ण होती हैं जिनसे CPU cache में अधिकतम data रखा जा सके
  • सामान्य JavaScript arrays और objects के बारे में यह गारंटी देना कठिन है कि वे low-level language के arrays या struct की तरह tightly packed होंगे
  • TypedArray fixed-size contiguous byte arrays बनाने देता है, जिससे JavaScript में अपेक्षाकृत low-level memory management संभव होता है

पहला implementation: SharedArrayBuffer और Web Worker

  • particle data को SharedArrayBuffer पर Float32Array view चढ़ाकर store किया गया
    • एक particle को x, y, dx, dy इन चार 32-bit floating-point values से व्यक्त किया गया
    • stride = 4, byte_stride = stride * 4 के जरिए flat buffer को index किया गया
  • simulation की शुरुआत हर frame में x += dx, y += dy जैसी साधारण position update से हुई
  • multithreading को Web Worker और SharedArrayBuffer से बनाया गया
    • main thread, Worker-दर-Worker particle chunks बाँटकर भेजता था
    • हर Worker सिर्फ अपने assigned chunk को पढ़ता-लिखता था, ताकि एक ही memory location पर कई threads के लिखने की स्थिति न बने
  • browser में SharedArrayBuffer इस्तेमाल करने के लिए ये headers चाहिए थे
    • Cross-Origin-Embedder-Policy: require-corp
    • Cross-Origin-Opener-Policy: same-origin
  • शुरुआती synchronization एक अलग signal SharedArrayBuffer से किया गया
    • main thread, Worker को run signal लिखता था
    • Worker setInterval(..., 1) से signal जाँचता था, और काम पूरा होने पर ready state लिखता था
  • rendering को ImageData के साथ CPU-based rasterizer की तरह संभाला गया
    • हर particle को screen के एक pixel के रूप में draw किया गया
    • screen के बाहर के particles को skip किया गया ताकि array bounds के बाहर access न हो
    • putImageData से result को Canvas पर draw किया गया
  • शुरुआती profiling में Worker का काम कुछ ms का था, जबकि अधिकतर समय main thread rendering में जा रहा था
  • memory को startup पर एक बार allocate किया गया और simulation loop में नए objects नहीं बनाए गए, इसलिए garbage generation लगभग नहीं थी

दूसरा implementation: input और gravity-जैसी interaction

  • input data को मौजूदा simulation state वाले SharedArrayBuffer में जोड़ा गया
    • delta time, mouse x/y, touch state, screen width/height store किए गए
    • touch state boolean-जैसी value थी, लेकिन 4 bytes इस्तेमाल किए गए
  • screen दबाने पर particles touch point की ओर खिंचने वाला effect जोड़ा गया
    • असली gravity formula के 1 / r² रूप से प्रेरणा ली गई, लेकिन सटीक physics simulation के बजाय मज़ेदार interaction के लिए इसे बदला गया
    • friction-जैसी damping जोड़ी गई ताकि particles अनंत तक accelerate होकर screen के बाहर न उड़ जाएँ
  • rendering color को particle position के आधार पर बदलने के लिए संशोधित किया गया
    • x / width, y / height values से RGB channel values adjust की गईं
    • अगर हर particle के लिए color अलग store किया जाता तो particle size बढ़ता, इसलिए data size घटाने के लिए position-based color अपनाया गया
  • 20 लाख particles तक experiment किया जा सका, और URL के count query parameter से particle count बदलना संभव बनाया गया
  • 1 करोड़ particles पर framerate गिरने लगी, और profiling में Worker से अधिक ImageData pixel writes धीमे हिस्से के रूप में सामने आए
  • पूरे RGB लिखने के बजाय सिर्फ blue और alpha channels लिखने पर कुछ environments में render time लगभग 80~90ms से घटकर 16~18ms हो गया
    • यह अंतर CPU के अनुसार बदलता था, और M1 MacBook Air की तुलना में desktop Ryzen पर अधिक बड़ा दिखा

तीसरा implementation: Worker में pixel buffer लिखना

  • अधिक CPU cores का उपयोग करने के लिए Worker से simulation के साथ-साथ pixel drawing भी कराया गया
  • कई Workers एक ही pixel buffer में एक साथ न लिखें, इसलिए Worker-प्रति pixel buffer रखा गया
    • CPU_CORES * window.innerWidth * window.innerHeight * 3 आकार का SharedArrayBuffer इस्तेमाल हुआ
    • हर Worker के पास पूरी screen के लिए एक RGB buffer था
  • main thread सभी Worker pixel buffers को जोड़ने के बाद ImageData में लिखता था
  • इस version में screen flickering हुई
    • Worker अपने pixel buffer को fill(0) से साफ कर रहा था, उसी दौरान main thread वही buffer पढ़ रहा था
    • पहले भी rendering पुराने data पढ़ सकती थी, लेकिन frame-to-frame अंतर कम दिखता था; इस बार Worker की clearing screen के हिस्सों में flicker के रूप में दिखी
  • संभावित समाधान Atomics आधारित synchronization, postMessage से Worker completion का इंतज़ार, और double buffering थे

चौथा implementation: postMessage आधारित synchronization

  • flickering हटाने के लिए signal array छोड़ी गई और Worker completion बताने हेतु postMessage अपनाया गया
  • main thread activeWorkers value manage करता था
    • हर Worker खत्म होने पर message भेजता और activeWorkers घटाया जाता
    • सभी Workers के खत्म होने पर render किया जाता और अगला requestAnimationFrame माँगा जाता
  • इस तरीके से flickering खत्म हो गई
  • frame time में बड़ा सुधार नहीं हुआ, बल्कि यह और खराब हो सकता था
    • वजह यह थी कि main thread, Worker completion का इंतज़ार करते समय कुछ नहीं कर रहा था
    • 20 लाख particles के मामले में, अगर Worker को main thread rendering का इंतज़ार न करना पड़े तो लगभग 7ms बच सकते थे
  • इस bottleneck को घटाने के लिए graphics drivers में आम double buffering लागू की गई

पाँचवाँ implementation: double buffering और cache bottleneck

  • double buffering में दो pixel buffers बनाए जाते हैं और हर frame active buffer बदल दिया जाता है
    • जब main thread एक buffer draw कर रहा होता है, तब Worker दूसरे buffer में अगला frame तैयार करते हैं
  • इसे लागू करने के बाद Workers को main thread rendering का इंतज़ार नहीं करना पड़ा, और पहले 50ms से ऊपर जाने वाले कुछ frames 16ms के अधिक करीब आ गए
  • जो code लगातार धीमा रहा, वह pixel buffer के RGB channels में values जोड़ने वाली तीन lines थीं
  • कारण यह था कि data भले contiguous store हो, access order contiguous नहीं था
    • particle के x, y से निकला pixelIndex, particle array order के साथ aligned नहीं था
    • loop की हर iteration में pixel buffer की random location पर jump होता था, जिससे pattern random access के करीब हो जाता था
  • यह access pattern तब cache miss पैदा करता था जब particle data और pixel data दोनों cache में फिट नहीं होते थे
  • iPhone के लिए उदाहरणीय calculation यह थी
    • formula: screen width * screen height * bytes per pixel + bytes per particle * total particles / number of workers
    • 2532 * 1170 * 3 + 16 * 2,000,000 / 5
    • परिणाम 15MB से अधिक था, जो L1 cache में रखने के लिए बहुत बड़ा है
  • इस version में M1 chip पर 20 लाख particle simulation लगभग 4ms, pixel data access लगभग 3.5ms, और pixel buffer writes लगभग 7ms लेते थे
  • मोबाइल पर 10 लाख particles 60fps पर बनाए रखे जा सकते थे, लेकिन 20 से अधिक threads वाले desktop पर main thread को 20+ pixel buffers हर frame जोड़ने में 30ms लगते थे

छठा implementation: शुरुआती position पर लौटाने वाला बल

  • नया effect यह था कि particle जितना अपनी शुरुआती position से दूर जाए, उतनी ताकत से वापस खिंचे
  • इसके लिए particle में शुरुआती position sx, sy की दो values जोड़ी गईं
    • एक particle में x, y, dx, dy, sx, sy ये छह floats हो गए
    • particleStride = 6 तक बढ़ा
  • Worker code में force calculation function जोड़ा गया, और garbage generation से बचने के लिए cache object इस्तेमाल हुआ
  • परिणाम ने jelly या fluid-जैसा visual effect दिया, और particles मुड़े हुए कागज़ या कपड़े जैसी swirl patterns दिखाने लगे
  • इसी दौरान यह विचार आया कि Worker-प्रति pixel buffer रखने के बजाय प्रति pixel particle count वाली grid रखी जाए

सातवाँ implementation: प्रति-pixel particle count grid

  • RGB values store करने के बजाय हर pixel position पर सिर्फ particle count store करने से memory 1/3 तक घट सकती थी
  • color particle-प्रति data से नहीं, बल्कि x, y position से calculate होता था, इसलिए rendering सिर्फ per-pixel count से संभव थी
  • सभी Workers को एक साझा particle count grid पर काम करने दिया गया
    • main thread का Worker buffers को जोड़ने वाला काम खत्म हो गया
    • Workers की संख्या बढ़ने पर render merge cost बढ़ने की समस्या हल हो गई
  • नई cache calculation यह थी
    • screen width * screen height + bytes per particle * total particles / number of workers
    • iPhone के आधार पर 2532 * 1170 + 16 * 2,000,000 / 5
    • यह लगभग 9.3MB था, जो पहले से लगभग 30% कम था, लेकिन फिर भी L1 cache के लिए बड़ा था
  • rendering में पूरे pixels पर iterate किया गया, उस pixel के particle count को पढ़ा गया, RGB values निकाली गईं, और grid को fill(0) से reset किया गया
  • Worker simulation के बाद screen के भीतर आने वाले particle का pCountIndex निकालते और activeGrid[pCountIndex]++ चलाते थे
  • यह बदलाव खासकर तब उपयोगी रहा जब Workers की संख्या अधिक थी, और desktop पर सभी 24 threads का उपयोग संभव हुआ
  • फिर भी कुछ स्थितियों में M1 MacBook Air, Ryzen 9 3900X desktop से तेज़ निकला
    • Ryzen 9 3900X में L3 cache 64MB है, लेकिन L1 सिर्फ 64KB है
    • पहली पीढ़ी के M1 में L1 cache 320KB है, जिसमें 128KB data और 192KB instruction के लिए है
    • माना गया कि बड़ा L1 data cache memory wait time घटाने में फायदेमंद रहा

केवल CPU optimization की सीमाएँ

  • कई optimizations के बाद, शुरुआती multithreaded version की तुलना में लगभग 2x speedup मिला
  • JavaScript मात्र से मोबाइल पर CPU-based 10 लाख particles को 60fps पर चलाने का लक्ष्य पूरा हुआ
  • कुल परिणाम कोई असाधारण रूप से प्रभावशाली स्तर का नहीं था, और compiled language में इसे 10x तेज़ होने की उम्मीद जताई गई
  • अगर tight loop में SIMD instructions इस्तेमाल किए जा सकें तो और speedup की गुंजाइश है
  • अगले चरण में simulation को CPU पर रखते हुए सिर्फ rendering को पारंपरिक GPU pipeline पर ले जाकर तुलना की गई

2 करोड़ particles और GPU rendering

  • पहली GPU rendering comparison, threejs की GPU instancing के साथ प्रति particle plane/quad draw करने वाली थी
  • इस तरीके की performance उम्मीद से कम रही
    • threejs instancing में हर particle position के लिए matrix update करनी पड़ती है, और यह काम CPU single thread पर होता है
    • particle transform data हर frame GPU पर upload करनी पड़ती है, और यह transfer धीमा है
  • M1 chip पर 40 लाख particles simulate करते समय frame time का 80% GPU को data भेजने में जा रहा था
  • desktop पर data transfer का हिस्सा 30% था, लेकिन फिर भी यही सबसे बड़ा bottleneck रहा
  • विकल्प यह था कि पहले बनाई गई particle count grid को texture की तरह इस्तेमाल किया जाए और full-screen quad render किया जाए
    • इससे GPU को भेजा जाने वाला data particle count पर नहीं, बल्कि screen resolution पर fixed हो गया
    • बड़े simulations में transfer कम हुआ, लेकिन छोटे simulations में यह ज़्यादा data भेजने वाला trade-off रहा
  • threejs और custom pixel shader के साथ जल्दी तैयार किए गए implementation में main thread rendering, simulation size से स्वतंत्र होकर कुछ ms तक सीमित रही
  • इस structure में Workers जितना तेज़ चल सकते थे उतना चले, और simulation बड़े तथा छोटे दोनों scale पर सीधे CPU core count से बँध गया
  • हर Worker अपना लगभग 50% समय numeric calculation में और लगभग 50% particle grid count update में खर्च कर रहा था
  • अंतिम version की performance इस प्रकार रही
    • battery mode में M1 Mac पर 2 करोड़ particles लगभग 20fps पर चले
    • desktop ने लगभग समान fps पर लगभग 3 करोड़ particles संभाले
    • 32-core CPU वाले एक मित्र के test में लगभग 4 करोड़ particles तक पहुँचा गया
  • संबंधित demos:

निष्कर्ष

  • CPU और GPU दोनों numeric calculation बहुत तेज़ी से कर सकते हैं
  • धीमा हिस्सा data को इधर-उधर ले जाना है, और खासकर random memory access
  • तेज़ code लिखने के लिए यह समझना ज़रूरी है कि hardware data को कैसे cache और move करता है
  • SharedArrayBuffer और Web Worker, JavaScript में multiple cores के उपयोग के प्रयोगों के लिए उपयोगी रहे
  • WebGPU अधिक व्यापक रूप से अपनाए जाने पर compute shader आज़माने की योजना है

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

1 टिप्पणियां

 
GN⁺ 2024-07-09
Hacker News की राय

  • ब्लॉग के अंदर ही simulation को सीधे embed कर दिया जाए तो अच्छा होगा
    असली simulation का link खोजने के लिए मुझे काफी देर तक ऊपर-नीचे scroll करना पड़ा
    पुराने phones पर भी ठीक-ठाक चलने वाली values चुनी जा सकती हैं, या frame rate के हिसाब से adjust कराया जा सकता है, या फिर लेख के ऊपर ही कुछ links रखे जा सकते हैं
    https://ciechanow.ski/ यह दिखाने वाला world-class example है कि लेख के अंदर simulation डालना कितना शानदार हो सकता है
    पहले हर website ऐसे शानदार interactive elements embed करती थी
    और मुझे लगता है कि WebGPU के बिना भी GPU पर particle simulation चलाया जा सकता है
    उदाहरण: https://news.ycombinator.com/item?id=19963640

    • अब तक देखे गए explanatory blogs में यह सबसे बेहतरीन examples में से एक है
      काश information sharing का standard ऐसा ही हो। अगर कोई चीज़ share करने लायक है, तो उसे समझने में आसान बनाने लायक भी है
    • वह fluid simulation सचमुच कमाल का है
    • embed अच्छा है, इस पर सहमत हूँ
      मैंने सोचा था कि हर version को embed करूँ, लेकिन चिंता थी कि बहुत सारे workers एक साथ चलने लगेंगे
      लेख के अंत में final version embed करने के लिए update करूँगा
      उस blog में हर example की polish जबरदस्त है और वह सच में बहुत अच्छा है
      संपादन: embed version जोड़ने की कोशिश की, लेकिन जरूरी headers दूसरे embeds के साथ ठीक से compatible नहीं थे, और पुराने versions अभी भी codesandbox से बंधे हुए हैं
    • बस यह सूचना दे दें कि “final app के साथ खेलने के लिए अंत पर जाएँ”

  • mobile demo [0] को खुद try करके देखा, काफी हैरान करने वाला है
    [0] https://dgerrells.com/sabby

    • यह कई fingers के साथ भी काम करता है
      pure JavaScript में इस स्तर का होना चौंकाने वाला है, और fingers बढ़ने पर latency बढ़ती दिखती है, जिससे लगता है कि threads के बीच आने-जाने वाला data ज्यादा हो रहा है
    • अजीब तरह से organic दिखता है, जैसे primordial soup में lipid structures हों
    • मेरे phone पर Firefox, Chrome से बेहतर चला, यह देखकर अच्छा लगा

  • सिर्फ curiosity है: हर particle को x, y, dx, dy चार 32-bit floating-point numbers से represent करने के बजाय क्या इस data को एक JS number में encode किया जा सकता है?
    JS की safe integer range 2^53 - 1 = 9,007,199,254,740,991 है, और लेख में इस्तेमाल Float32Array की range -3.4e38 से 3.4e38 तक है
    उदाहरण के लिए, अगर screen position 1000x1000 canvas है, तो उसे 0~1,000,000 numbers से represent किया जा सकता है, और इसमें subpixel के 10 steps जोड़ने पर भी 100,000,000 numbers होंगे, जो JS range के भीतर आराम से आते हैं
    speed dx, dy भी (Math.random()*2-1)*10 से -10 और +10 के बीच random decimal के रूप में calculate होती है, लेकिन अगर एक decimal place तक सीमित करना काफी हो, तो उसे -100~+100 integer range में बदला जा सकता है, और possible values 10,000 ही चाहिए होंगी
    दोनों को मिलाने पर 10,000 * 100,000,000 = 1,000,000,000,000, यानी 1 trillion numbers से particle represent किया जा सकता है, जो JS के MAX_SAFE_INTEGER के अंदर है
    इसलिए लगता है कि single particle data को एक MAX_SAFE_INTEGER या Float32Array के एक element में रखा जा सकता है, जिससे stride की जरूरत नहीं होगी और data consistency भी ज्यादा पक्की हो सकती है
    हालांकि encoding/decoding की cost memory savings से ज्यादा हो सकती है, इसलिए performance के लिहाज से शायद बिल्कुल भी worth न हो

  • वाकई शानदार है, लेकिन इस हिस्से को लेकर जिज्ञासा है
    Javascript does support an Atomics API but it uses promises which are gross. Eww sick.
    waitAsync[1] को छोड़ दें तो Atomics API promises का उपयोग करता हुआ नहीं दिखता
    पहले Atomics इस्तेमाल किया था, लेकिन async/promise code से निपटने की ज़रूरत नहीं पड़ी थी
    जिज्ञासा है कि क्या यह अंदरूनी तौर पर promises इस्तेमाल करता है, या मैंने कुछ मिस कर दिया है
    [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

  • लगभग 2 करोड़ particles संभालने वाला simulation भी है
    इसे चला और program किया जा सकता है: https://tinlizzie.org/~ohshima/shadama2/
    https://tinlizzie.org/~ohshima/shadama2/live2017/
    https://www.youtube.com/watch?v=tqBO_5GMfWw

  • वीडियो शानदार है, लेकिन try it out here वाले codesandbox links MacOS Chrome desktop पर काम नहीं करते
    Uncaught ReferenceError: SharedArrayBuffer is not defined और ERR_BLOCKED_BY_RESPONSE.NotSameOriginAfterDefaultedToSameOriginByCoep जैसी CORS errors आती हैं

    • क्योंकि codesandbox का inline editor header settings को रोकता है, इसलिए preview को dedicated tab में खोलना होगा
      privacy-focused browser इस्तेमाल करने पर यह block भी हो सकता है
      आगे से embedded examples शामिल करने की कोशिश करूँगा
      final version यहाँ try कर सकते हैं: https://dgerrells.com/sabby

  • बेहतरीन
    code समझने और उससे खेलने में एक घंटा लगाया, और यहाँ live implementation बना दिया है: https://particules.kapochamo.com/index.html

    • पहली बार खोलने पर चौंक गया
      सच में बहुत सुंदर है, और भरोसा करना मुश्किल है कि JS में इतने सारे particles simulate हो रहे हैं
    • शानदार
      आपने code में इतनी गहराई तक dive किया, यह impressive है

  • यह देखना worthwhile होगा कि chrome://tracing और ज़्यादा insight देता है या नहीं
    यहाँ से पता चला: https://youtu.be/easvMCCBFkQ?t=114

  • इसे slow React apps बनाने वाली UI team को तुरंत भेजना चाहता हूँ
    JS सच में fast है, खासकर अच्छी तरह लिखा जाए तो बहुत fast

    • समस्या यह है कि idiomatic JS और fast JS असल में लगभग एक-दूसरे के उलट हैं
      fast JS किसी खराब C dialect जैसा दिखता है, और garbage collection object allocation नहीं करनी चाहिए, लेकिन language में allocation-free अच्छे alternatives की कमी है
      complex JS app में सारी memory allocation को एक बड़े ArrayBuffer के अंदर pointers की तरह handle करने वाले लोग बहुत कम होंगे, और ऐसा करने से तो WebAssembly पर जाना ज़्यादा आसान है
    • JavaScript शायद वह language है जिसमें अलग-अलग engine optimizations पर सबसे ज़्यादा human hours लगे हैं
      अफ़सोस की बात यह है कि केवल JS पर भरोसा करके नहीं चला जा सकता और DOM manipulation काफ़ी मिलानी पड़ती है; हमारे बनाए UI में आमतौर पर slow हिस्सा वही DOM manipulation होता है