Spice: Zig में सब-नैनोसेकंड ओवरहेड के साथ बारीक parallel processing तकनीक

 (github.com/judofyr)
2 पॉइंट द्वारा GN⁺ 2024-08-14 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Spice एक research project है जिसका लक्ष्य Zig में heartbeat scheduling का उपयोग करके functions में parallel execution की संभावना जोड़ने पर भी overhead को 1ns से कम रखना है
  • इसका core design fork से ऐसा काम चिह्नित करना है जिसे कोई दूसरा thread संभाल सकता है, लेकिन अगर कोई thread उसे नहीं उठाता, तो join पर current thread खुद execute करता है — यानी fallback structure
  • 100 मिलियन nodes वाले binary tree summation benchmark में Rayon का 1-thread overhead लगभग 15ns था और 16 threads पर यह baseline की तुलना में लगभग 4.5x था, जबकि Spice ने 16 threads पर baseline के मुकाबले लगभग 11x speedup लगभग जस का तस हासिल किया
  • 1000 nodes जैसे बहुत कम execution time वाले tasks में Rayon के 32 threads पर कुल मिलाकर 60x धीमा होने के मामले थे, और Spice अगर तय करता है कि parallel processing की जरूरत नहीं है, तो extra threads को सुला देता है और multithreading शुरू नहीं करता
  • मौजूदा implementation में tests, documentation, array/slice support और additional benchmarks की कमी है, @panic का काफी उपयोग है, और author ने कहा है कि production use से पहले कई limitations समझना जरूरी है

Spice जिस समस्या को हल करना चाहता है

  • Spice Zig में बहुत बारीक parallel processing को low overhead के साथ implement करने वाला project है
  • लक्ष्य यह है कि parallelization जोड़ने पर program धीमा होगा या नहीं, users को लगातार इसकी चिंता न करनी पड़े
  • performance maximize करने के लिए sophisticated benchmarks की जरूरत होती है, लेकिन सामान्य तौर पर Spice इस तरह design किया गया है कि parallelism जोड़ने पर practically लगभग कोई overhead न हो
  • यह project मुख्य रूप से research project है, और production use पर विचार कर रहे हों तो पहले limitations देखनी चाहिए
  • September 2024 update में, इस idea के Rust port Chili को introduce किया गया

उपयोग का तरीका और core API

  • Spice के parallel functions *spice.Task को parameter के रूप में लेते हैं और उसे work coordination के लिए use करते हैं
  • recursive calls या parallelize किए जा सकने वाले function calls को सीधे call न करके t.call के जरिए call करना चाहिए
  • fork ऐसा काम set करता है जिसे कोई दूसरा thread execute कर सकता है
  • function को fork के बाद खुद भी meaningful work करना चाहिए
  • join इंतजार करता है कि दूसरे thread ने काम पूरा किया है या नहीं, लेकिन यह null return कर सकता है
    • null इस बात का signal है कि किसी दूसरे thread ने वह काम नहीं उठाया
    • इस स्थिति में current thread को वह काम खुद execute करना चाहिए

“सारा काम queue से नहीं आता” वाला design

  • Spice का core idea यह है कि सारा काम queue से शुरू नहीं होता
  • fork बताता है कि कोई काम है जिसे दूसरा thread execute कर सकता है, लेकिन अगर दूसरा thread busy है तो original sequential execution की तरह current thread ही उसे संभालता है
  • जब parallel execution की संभावना नहीं होती, तो hot path में Spice का काम queue में push/pop करने जितना ही होता है, और यह queue items को वास्तव में inspect नहीं करता
  • दूसरे threads के साथ वास्तविक coordination fixed heartbeat पर होता है
    • लगभग हर 100 microseconds पर thread current work queue check करता है
    • queue के top work को waiting दूसरे thread को देता है
    • heartbeat frequency कम होने के कारण, कुछ सौ ns खर्च होने पर भी overall overhead छोटा रहता है

Rayon benchmark से तुलना

  • binary tree के 100 million nodes का summation ऐसा case है जिसमें actual computation बहुत तेज है, इसलिए parallel framework का overhead बहुत साफ दिखता है
  • Rust का Rayon और Spice दोनों की तुलना ऐसे fork/join API form में की गई जिसे पढ़ना और reason करना आसान है
  • Rayon benchmark में overhead लगभग 15ns मापा गया
    • यह 7.48ns से बढ़कर 22.99ns हुआ
    • 4 threads पर यह sequential performance पर लौटने जैसा स्तर है, लेकिन CPU 4x use करता है
    • 16 threads पर Rayon के अपने आधार पर लगभग 14x speedup, और baseline के मुकाबले लगभग 4.5x speedup है
  • Spice 1 thread से 16 threads पर जाने पर लगभग 11x speedup दिखाता है
    • scaling Rayon से थोड़ी खराब है, लेकिन low overhead के कारण baseline के मुकाबले speedup भी लगभग वैसा ही बना रहता है
  • benchmark Google Cloud के c4-standard-16 instance, 16-core environment में run किए गए
  • Zig baseline, Rust baseline से लगभग 2x तेज क्यों है, यह स्पष्ट नहीं है
    • compiled assembly के अनुसार Rust stack पर 5 registers store करता है और Zig 3 registers store करता है

छोटे tasks में behavior

  • 1000-node binary tree summation बहुत छोटा task है, जिसकी total execution time कुछ microseconds के स्तर की है
  • Rayon में इस case में overhead लगभग 19ns और ज्यादा दिखा, और जितने ज्यादा threads जोड़े गए, performance उतनी खराब हुई
  • 16-core machine पर 32 threads use करने पर total execution time 60x धीमा हो गया
    • यह निश्चित रूप से नहीं कहा जा सकता कि 32-core machine पर भी वही slowdown दिखेगा
    • फिर भी, इस तरह के scaling behavior को worrying माना गया
  • traditional parallel processing judgment “केवल तब worth it है जब पर्याप्त काम हो” जैसा हो जाता है
    • “पर्याप्त काम” का criterion input-specific benchmarks से समझना पड़ सकता है
    • binary tree जैसे input में, जहां सिर्फ root देखकर कुल size पता नहीं चलता, यह तय करना मुश्किल है कि task छोटा है या नहीं
    • अगर workload का 90% छोटे inputs हैं, तो extreme slowdown समस्या बन सकता है
    • program evolve होने पर पर्याप्त काम का criterion भी बदलता है
  • Spice उसी 1000-node case में execution time बहुत कम मानकर multithreading शुरू नहीं करता
    • extra threads sleep state में रहते हैं
    • cores दूसरे programs चलाने के लिए use किए जा सकते हैं

work-stealing और Spice में फर्क

  • Spice fork/join model देता है, और यह model आमतौर पर work-stealing से implement होता है
  • typical work-stealing में हर thread के पास local work queue होती है, और queue खाली होने पर वह दूसरे thread की queue के end से work चुरा लेता है
  • work-stealing की inefficiency तीन तरह से summarize की जाती है
    • हर task generic “dynamic function call” form बन जाता है, जिससे dynamic dispatch cost आती है
    • local queue असल में ऐसी queue होती है जिससे सभी threads steal कर सकते हैं, इसलिए atomic operations की जरूरत होती है
    • queue contention के दौरान spinning होती है और कुछ conditions में 10–100x धीमा हो सकता है
  • Spice इन inefficiencies को सीधे कम करता है
    • work queue का dynamic dispatch केवल तब use होता है जब work दूसरे thread को भेजा जाता है
    • एक single thread के अंदर किए जाने वाले work में normal function calls use होते हैं
    • work queue push stack pointer, current stack frame और register save करके handle होता है, और दूसरे threads से synchronize नहीं करता
    • wait() call के बिना चलने वाला while loop नहीं है, इसलिए spinning नहीं होती

implementation details

  • static dispatch optimization

    • Spice मानता है कि fork किए गए tasks में से ज्यादातर दूसरे threads द्वारा नहीं उठाए जाते, इसलिए function के अंदर संबंधित code execution path को duplicate रखता है
    • अगर task दूसरे thread द्वारा execute नहीं होता, तो program कुछ predictable branches जुड़ी हुई sequential version की तरह behave करता है
    • यह structure inlining जैसी code optimizations और CPU execution के लिए favorable है

  • low-overhead heartbeat signal

    • heartbeat scheduling local level पर low frequency में scheduling करता है
    • लगभग हर 100 microseconds में thread local work queue देखता है और दूसरे thread को work भेजता है
    • हर 100 microseconds में 100ns खर्च होने पर total overhead करीब 0.1% होता है
    • operating system signals की जगह cooperative तरीके से tick() call किया जाता है
      • t.call helper use करते समय tick() automatic call होता है
      • अलग heartbeat thread हर thread के atomic heartbeat value को periodically false से true में बदलता है
      • tick() इस value को पढ़ता है और true होने पर heartbeat code execute करता है
    • heartbeat function को cold के रूप में mark किया जाना चाहिए, वरना overhead बहुत बढ़ जाता है

  • contention-free global mutex

    • Spice के thread pool में एक single mutex है जिसे कई जगह lock किया जाता है
    • global mutex तब problem बनता है जब thread वास्तव में block होता है
    • Spice में heartbeat के कारण आमतौर पर सिर्फ एक thread heartbeat execute करता है
    • lock पकड़े रहते हुए user code execute नहीं होता, और केवल constant-time में खत्म होने वाले simple memory reads/writes protected होते हैं

  • branchless doubly linked list

    • Spice work queue tracking के लिए doubly linked list use करता है
    • fork() end में append करता है, join() अगर अभी भी बचा हो तो end से pop करता है, और background worker को भेजते समय front से pop करता है
    • सामान्य append में खाली list है या नहीं यह check करने के लिए conditional statement चाहिए
    • Spice हमेशा मौजूद sentinel head node रखकर list को कभी empty नहीं होने देता, और push/pop branch के बिना करता है

  • stack use कम करना

    • Future की queued या executing state होती है
    • heartbeat queued future को executing में बदलता है
    • executing state के लिए जरूरी extra state को अलग pool-allocated struct में रखा जाता है, जिससे queued future का stack use कम होता है
    • prev_or_null first field null है या नहीं, इससे queued/executing state को अलग करने वाला manual tagged union form use किया जाता है

  • registers से values pass करना

    • Task में owning worker pointer और work queue tail pointer होते हैं
    • LLVM अक्सर struct passing को stack के जरिए handle करता है, इसलिए Spice worker और job_tail को अलग function parameters के रूप में लेने वाला callWithContext define करता है
    • इस function को हमेशा inline होने के लिए call किया जाता है, ताकि pointer parameters registers से pass हों

research base और related work

  • Spice heartbeat scheduling research पर आधारित है
  • “The best multicore-parallelization refactoring you've never heard of” heartbeat scheduling concept को संक्षेप में introduce करने वाला paper है, जो single use case पर focus करता है लेकिन generalizable तरीके से समझाता है
    • इस paper का solution code को continuation-passing style में बदलकर sequential execution और parallel execution के बीच switch करता है
    • Spice इसी approach के experiment से शुरू हुआ था, लेकिन overhead 10ns से ज्यादा निकला
  • “Heartbeat scheduling: provable efficiency for nested parallelism” heartbeat scheduling को पहली बार introduce करने वाला paper है
    • इसमें concept की जानकारी काफी है, लेकिन implementation interpreter integration आधारित है और theoretical guarantees पर ज्यादा focus है
  • “Task parallel assembly language for uncompromising parallelism” custom assembly language और OS signaling से heartbeat performance improve करने वाला follow-up research है
    • इसे existing languages में integrate करना मुश्किल माना गया

मौजूदा limitations

  • Spice गलत इस्तेमाल होने पर rough behavior दिखा सकता है
    • खासकर fork और join के use pattern को लेकर sensitive है
    • compile-time checks, debug-mode assertions और API changes से इसे improve करना होगा
  • concurrency code बहुत है, लेकिन test coverage 0 है
  • बारीक parallel processing के common use case, यानी array/slice के हर element को process करने के लिए native support नहीं है
  • usage समझाने वाली अच्छी documentation की कमी है
  • फिलहाल केवल एक छोटे benchmark के आसपास testing हुई है
    • माना जाता है कि यह benchmark representative होना चाहिए, लेकिन results verify करने के लिए additional benchmarks चाहिए
  • error handling में @panic का काफी उपयोग है
    • proper Zig library मानने के लिए error cases handling पर और ज्यादा विचार करना होगा
  • Zig के ReleaseSafe में यह कितना अच्छा काम करता है, इसके लिए additional benchmarks और tests चाहिए
  • पूरा codebase लगभग 500 lines का है, और current author के पास समय की कमी के कारण Spice improve करने के लिए active development plan नहीं है
  • fork या दूसरी languages में reimplementation के जरिए improvements encouraged हैं

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

1 टिप्पणियां

 
GN⁺ 2024-08-14
Hacker News की राय

  • यह implementation हालिया research trend heartbeat scheduling पर आधारित है, जो parallelism बनाने की cost को amortize करके एक तरह का dynamic automatic task granularity control हासिल करती है
    संबंधित papers:
    (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
    (2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
    (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
    (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf

    • यह वाकई दिलचस्प है, और Spice लिखते समय मुझे सिर्फ पहले दो papers के बारे में पता था
      पीछे के दोनों papers भी ज़रूर देखने का इरादा है

  • मैंने code को विस्तार से नहीं पढ़ा, लेकिन 1 nanosecond से कम overhead वाला phrase भ्रामक marketing copy जैसा लगता है
    पहली नज़र में यह ऐसी स्थिति में निकाला गया कोई पेचीदा “time per task” measurement लगता है, जहां threads की संख्या “tasks” की संख्या से बहुत कम है

    • मैं author हूं
      मुझे पता था कि कुछ लोग इस phrase पर negative reaction देंगे, लेकिन मकसद यह था कि Spice और Rayon को ठीक कब और कैसे इस्तेमाल करना है, यह बेहतर समझ में आए
      benchmark document पढ़ने की सलाह दूंगा: https://github.com/judofyr/spice/blob/main/bench/README.md
      आम तौर पर parallel code की तुलना करते समय लोग सिर्फ sequential/baseline implementation और सभी threads (16) इस्तेमाल करने वाली parallel implementation की तुलना करते हैं। 100M case में Rayon के numbers sequential version 7.48ns और Rayon 1.64ns थे, और तब “Rayon इस problem में 4.5 गुना तेज था, लेकिन उसने 16 threads इस्तेमाल किए, इसलिए यह अच्छी fit नहीं है” कहकर बात खत्म करना आसान है। यह बात सही है, लेकिन यह सीखना मुश्किल है कि इसे दूसरे तरह की problems पर कैसे apply किया जाए
      वही benchmark अलग-अलग thread counts के साथ चलाने पर ज्यादा interesting चीज़ें दिखती हैं। Rayon का scheduler अलग thread में काम बांटने में काफी अच्छा है, लेकिन पूरे task execution mechanism में करीब 15ns overhead है। भले ही यह program पूरी तरह बेकार example हो, फिर भी आगे apply की जा सकने वाली बात सीखते हैं: Rayon इस्तेमाल करने के लिए सबसे छोटी task unit के लगभग 7ns से बड़ी होने की संभावना ज्यादा है। हालांकि अगर total throughput कुर्बान करके भी overall latency घटाना ज्यादा जरूरी हो, तो exception है
      Rayon documentation numbers नहीं देती, बस कहती है कि “conceptually join() call दो threads बनाकर हर एक में एक closure चलाने जैसी है, लेकिन implementation काफी अलग है और बहुत low overhead रखती है”: https://docs.rs/rayon/latest/rayon/fn.join.html
      अगर मैं misleading होना चाहता, तो कहता “Spice में 10x speedup है और Rayon में 4.5x, इसलिए Spice Rayon से दोगुना तेज है”
    • “1 nanosecond से कम overhead” को भ्रामक marketing copy बनने के लिए 1-thread Spice - non-parallel baseline implementation का 1ns से बड़ा होना जरूरी है
      test results दावे को support करते हैं: https://github.com/judofyr/spice/tree/main/bench
    • मुझे लगता है यह भी quote की गई Rayon की ecological niche जैसा ही है
      जब हजारों से लेकर लाखों tasks process करने हों, कुछ दर्जन cores के भीतर जितना हो सके parallelize करना हो, और scheduling overhead से खा नहीं जाना हो, तो structure ऐसा ही होता है जिसमें per-task overhead देखा जाता है
    • कल जब यह Reddit पर आया था, मैंने benchmarks को लेकर concern जताया था
      benchmark हर call पर 0.36ns overhead का दावा करता है, लेकिन इसमें सिर्फ computation function शामिल है। scheduling करने वाला एक second thread है, जो overhead number में शामिल नहीं है। लगता है इसे hyperthreading वाले 8-core, यानी 16-thread machine पर चलाया गया है, और 3GHz मानें तो यह सचमुच one-cycle overhead है
      हर extra thread के साथ lock contention की वजह से overhead बढ़ता है। 16 threads पर यह 3.6ns हो जाता है, यानी 10 गुना बढ़ोतरी। अनुमान है, लेकिन अगर ऐसा है तो इसका मतलब 0.36ns overhead में uncontended lock शामिल है, जो असंभव है। benchmark data में और भी अजीब बातें हैं। या तो मैं समझ नहीं पा रहा कि असल में क्या measure हो रहा है, या benchmark code में bug हो सकता है
      सभी values को multiply करके देखें तो लगता है time milliseconds में measure हो रहा है। runtime calculate होकर milliseconds में convert होते समय integer में गिरता है। आम तौर पर benchmarkers इससे बेहतर precision इस्तेमाल नहीं करते क्या? हो सकता है सिर्फ time prog इस्तेमाल किया गया हो, इसलिए data बहुत messy है, या इस purpose के लिए पूरी तरह बेकार metric चुना गया हो
    • README पढ़ने पर मुझे लगता है कि title का claim exactly क्या मतलब रखता है, यह बहुत precise तरीके से समझाया गया है
      ऐसा कोई title नहीं होता जिसमें ambiguity बिल्कुल न हो, और यह title ठीक है। मैंने इसे इतना ही समझा कि किसी metric पर यह बेहद low latency वाली library है, और README में जाकर वह metric confirm किया जा सकता था। काफी clear है

  • मैं इस क्षेत्र से बहुत ज़्यादा परिचित नहीं हूँ, लेकिन यहाँ पेश किया गया concurrency model मुझे पसंद आया
    README भी बहुत अच्छी तरह लिखा गया है, और उसे पढ़ने भर से समझ आ जाता है कि क्या हो रहा है। हालांकि कुछ जगहों पर थोड़ा संदेह हुआ। अच्छी बात यह है कि code काफ़ी पढ़ने लायक है

    • Debug mode में zig build से build करने पर Baseline,3.92809172, Spice 1 thread,19.1012624 मिला
      ReleaseSafe mode में zig build --release=safe से build करने पर Baseline,3.264224280000001, Spice 1 thread,3.78043278 मिला
      इसलिए अगर Spice release build में नहीं है, तो performance में गिरावट काफ़ी बड़ी है। reference implementation Zig के Debug build mode में उसी हद तक धीमा नहीं होता
      इस्तेमाल किया गया version zig 0.13.0 है

  • यह एक दिलचस्प research work है, और सिर्फ़ code ही नहीं, बल्कि निर्णयों के आधार भी अच्छे हैं और documentation भी अच्छी तरह लिखी गई है
    2018 का heartbeat scheduling paper भी पढ़ने लायक है: https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf

  • project की limitations की सूची: https://github.com/judofyr/spice?tab=readme-ov-file#limitati...

    • यह project शानदार है, और लेखक ने इसे चलाने लायक बनाने तथा HN community के साथ साझा करने में जो समय लगाया है, उसके लिए उनकी बहुत सराहना होनी चाहिए
      HN आम तौर पर कुछ ज़्यादा ही आलोचनात्मक या निराशावादी प्रतिक्रियाओं के लिए भी जाना जाता है
      अच्छा है कि लेखक ने अपने project की सीमाओं को स्वीकार किया है, और इससे आम किस्म की cynicism को पहले ही काफी हद तक रोक दिया गया है
      “tests की कमी: Spice में बहुत सारा tricky concurrency code है, लेकिन test coverage 0 है। Spice को ज़िम्मेदारी से critical कामों में इस्तेमाल करने के लिए इसमें सुधार होना चाहिए” — इस हिस्से पर, critical कामों के execution की correctness को test करना अलग बात है, लेकिन tricky concurrency code implement करने वाली library में कम से कम regression tests तो होने ही चाहिए, ऐसा मुझे लगता है
      end user के नज़रिये से, मैं जानना चाहूँगा कि आज जो feature काम कर रहा है, वह कल किसी subtle और खतरनाक regression से नहीं टूटेगा, इसकी क्या गारंटी है
      SQLite में plain C source code की तुलना में test code और test scripts 590 गुना ज़्यादा हैं https://www.sqlite.org/testing.html। stability और portability के अलावा, यह भी उन कई कारणों में से एक है जिनकी वजह से SQLite दुनिया भर का de facto standard embedded database बन गया
      यह apples और oranges की ज़बरदस्ती तुलना करने वाला उदाहरण है, लेकिन सामान्य बात फिर भी लागू होती है। regression tests project की stability और trust पैदा करते हैं
      जहाँ मैं काम करता हूँ, अगर basic regression tests को टालना ही पड़े, तो आम तौर पर उसी epic में follow-up ticket बनाया जाता है, ताकि feature/epic release से पहले कम से कम वे लिखे जा सकें

  • description के मुताबिक nanosecond-level latency पाने के लिए workers में busy waiting का इस्तेमाल किया गया है
    बड़े applications में, जहाँ दसियों हज़ार tasks होते हैं, busy waiting कितनी practical है, यह सोचने वाली बात है। अगर tasks thread-based न होकर async हैं, तो executor thread pool size N जितने ही waiters होंगे, इसलिए शायद यह संभव हो। किसी भी हालत में, ऐसी structure में energy consumption ज़्यादा होगा
    इसी से जुड़ा, मैं लंबे समय से सोचता रहा हूँ कि क्या task producer बिना busy waiting के consumer को और तेज़ी से जगा सकता है। उदाहरण के लिए, क्या producer के time slice के भीतर consumer को चलाने का तरीका संभव होगा
    इससे भी जुड़ा, यह भी सोचने की बात है कि user-space FUTEX_WAKE operation संभव हो जाए तो consumer को जगाने की cost सामान्य की आधी, यानी सिर्फ़ consumer-side cost तक घट सकती है या नहीं

  • साफ़-सुथरे और अच्छे papers भी link किए गए हैं
    हालांकि तुलना का target OpenMP tasks होता तो अच्छा होता। मैंने सुना है कि Rayon की reputation थोड़ी धीमी होने की है

  • cooperative scheduling कई ऐसे patterns की बुनियाद है जो बेहतरीन metrics देते हैं

    • लेकिन यह उस अर्थ में cooperative scheduling नहीं है जहाँ tasks एक-दूसरे को yield करते हैं
      यह मुख्य रूप से कुछ tasks को दूसरे threads को सौंपने में cooperation करने का तरीका है, और वह भी हमेशा नहीं, बल्कि हर heartbeat पर केवल एक बार होता है। scheduling कम बार होती है, इसलिए amortized cost कम रहती है

  • bench के नीचे वाला README भी देखने लायक है: https://github.com/judofyr/spice/blob/main/bench/README.md