कभी-कभी समय से पहले किया गया optimization भी मजेदार होता है (2025)

 (invlpg.com)
1 पॉइंट द्वारा GN⁺ 5 시간 전 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • connectivity monitoring system के ICMP Echo Request record struct को छोटा करने की प्रक्रिया में ring buffer memory usage 12KiB से घटकर 4KiB हो गया
  • sent_ns और received_ns दोनों को store करने के बजाय receive होने के बाद केवल latency बची रहे, इसके लिए union इस्तेमाल करने पर array size 8KiB तक घट गया
  • nanosecond precision की जगह 100 microsecond unit इस्तेमाल की गई और received को bitfield में बदला गया, लेकिन struct padding की वजह से अतिरिक्त बचत नहीं हुई
  • source address की जगह ICMP identifier के कुछ अर्थ को 4-bit counter से बदलने पर struct 8 byte का रह गया और 512-element array 4KiB बन गया
  • application पर memory constraint नहीं था, इसलिए व्यावहारिक जरूरत कम थी, लेकिन यह field layout और bit access cost तक परखने वाला optimization experiment बन गया

समस्या की रूपरेखा: ping records को store करने का तरीका

  • connectivity monitoring system कई servers को ICMP Echo Request भेजता है और 1 मिनट, 5 मिनट, 15 मिनट के intervals में latency और packet loss के average को देखता है
  • शुरुआत में सोचा गया storage तरीका 512 entries वाला ring buffer था, और हर entry में send time, receive time, source address, sequence number, और receive हुआ या नहीं, यह रखा जाता था
  • शुरुआती struct array pings_rb[512] का size 12KiB मापा गया
struct ping_timestamp {
    uint64_t sent_ns;
    uint64_t received_ns;
    in_addr_t source_addr;
    uint16_t seq_no;
    bool received;
};

पहली बचत: send time और elapsed time को union में मिलाना

  • वास्तव में जो value रखनी थी, वह receive होने के बाद की received - sent latency थी, इसलिए send time और elapsed time को एक साथ store करने की जरूरत नहीं थी
  • sent_ts और elapsed_ts को union में बांधने वाला struct, उसी slot को send से पहले send time के रूप में और receive के बाद elapsed time के रूप में इस्तेमाल करता है
  • इस बदलाव के बाद 512-element array का size 12KiB से घटकर 8KiB हो गया
struct ping_timestamp_2 {
    union {
        uint64_t sent_ts;
        uint64_t elapsed_ts;
    };
    in_addr_t source_addr;
    uint16_t seq_no;
    bool received;
};

दूसरा प्रयास: precision कम करना और bitfield

  • ping time को आम तौर पर दर्जनों, सैकड़ों, या हजारों milliseconds में मापा जाता है, इसलिए nanosecond precision पूरी की पूरी store करना जरूरी नहीं था
  • time unit को 100 microseconds यानी 0.1ms करने पर 43 bits में अधिकतम 20 साल तक का ping tracking संभव हो जाता है
  • received के true/false मान के लिए 8 bits खर्च करना ज्यादा था, इसलिए bitfield लागू किया गया
  • लेकिन ping_timestamp_3 array का size भी 8KiB ही रहा, इसलिए अतिरिक्त बचत नहीं मिली
struct ping_timestamp_3 {
    uint64_t sent_or_elapsed_ts: 43;
    uint64_t received: 1;
    uint64_t seq_no: 16;
    in_addr_t source_addr;
};

struct padding की वजह से size कम नहीं हुआ

  • ping_timestamp_2 के अंत में alignment requirement पूरी करने के लिए padding bytes जुड़ते हैं
  • ping_timestamp_3 पहले 8 bytes में time, receive status, और sequence number रखता है, लेकिन उसके बाद source address और padding बचते हैं
  • bitfield लगाने के बाद भी 36 bits की padding बची रहती है, इसलिए struct का कुल size नहीं घटता
  • सिर्फ bool को bit में छोटा कर देना memory layout और alignment की समस्या हल नहीं करता

source address हटाना और 4-bit counter

  • product mobile data network पर चलते समय source address अक्सर बदलता था, इसलिए पुराना struct source address को store करता था
  • address बदलने पर sequence number भी reset हो जाता था, और पहले ऐसा हुआ था कि अलग source address लेकिन same sequence number वाले packets एक साथ process हुए थे
  • ICMP Echo Request में 16-bit identifier field होती है, जिससे application अपने भेजे हुए packet को पहचान सकती है
  • पूरे 16 bits की जरूरत नहीं थी, इसलिए बचे हुए 4 bits को source address बदलने पर बढ़ने वाले rolling counter के रूप में इस्तेमाल किया गया
  • यह counter application के दूसरे हिस्से में monitor किए जाने वाले source address change के साथ बढ़ता है
struct ping_timestamp {
    uint64_t elapsed_or_sent_ts : 43;
    uint64_t received : 1;
    uint64_t counter: 4;
    uint64_t seq_no: 16;
};

अंतिम परिणाम और field layout

  • अंतिम struct में source address field हटा दी गई और 64-bit के भीतर time, receive status, counter, और sequence number रखे गए
  • 512-element ring buffer array का size 4KiB हो गया, यानी data एक page में सिमट गया
  • शुरुआती 12KiB की तुलना में कुल 8KiB की बचत हुई
  • field order को इस तरह सेट किया गया कि seq_no 16-bit boundary पर align रहे, ताकि load के समय बिना shift के एक single ldrh instruction से पढ़ा जा सके
  • elapsed_or_sent_ts पढ़ते समय केवल mask की जरूरत पड़ती है

अतिरिक्त optimization: receive bit access cost कम करना

struct ping_timestamp {
    uint64_t elapsed_or_sent_ts : 43;
    uint64_t counter: 4;
    uint64_t not_received : 1;
    uint64_t seq_no: 16;
};

निष्कर्ष

  • optimization का नतीजा memory usage को 12KiB से 4KiB तक लाना रहा, लेकिन application खुद memory-constrained नहीं थी
  • वास्तविक जरूरत से अलग, यह struct layout, padding, bitfield, और instruction-level access cost को परखने वाला एक प्रयोग बन गया
  • आखिरी टिप्पणी में यह भी कहा गया कि “समस्या” शब्द भी ढीले अर्थ में इस्तेमाल किया गया था, और benchmark तक नहीं किया गया था

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

1 टिप्पणियां

 
GN⁺ 5 시간 전
Lobste.rs की राय

  • जिस दिन इस तरह की समस्याओं के बारे में सोचना मज़ेदार नहीं लगेगा, उसी दिन मैं समझूँगा कि प्रोग्रामिंग छोड़ने का समय आ गया है

  • Premature optimization हमेशा मज़ेदार होती है
    लेकिन बाद में यह समझ आने के बाद कि वह optimization premature क्यों थी, उसके नतीजों से निपटना आम तौर पर मज़ेदार नहीं होता

    • सही। यह जानते हुए खुद को रोकना चाहिए कि आगे चलकर यह मुसीबत बन सकती है, फिर भी मज़ेदार लगने की वजह से कर ही बैठते हैं

  • timestamp के लिए 43 bits इस्तेमाल करने वाली बात थोड़ी उलझाऊ लगती है। 24 bits काफ़ी लगते हैं
    512-entry ring buffer की बात देखकर लगता है कि हर 2 सेकंड में नया ping भेजा जाता है, और पिछले 17 मिनट 4 सेकंड तक के ping ट्रैक किए जाते हैं
    पहले कदम के तौर पर ideal timer/sequence number के मुकाबले delta encoding इस्तेमाल की जा सकती है। आख़िरी send time को 2 सेकंड बढ़ाते हुए और ring buffer index देखकर आसानी से पता चल सकता है कि packet कब भेजा जाना था, इसलिए बस यह रिकॉर्ड करना होगा कि वह ठीक समय पर गया, 0.1ms देर से गया, 2.3ms देर से गया, वगैरह
    elapsed time को भी 17 मिनट 4 सेकंड से ज़्यादा रखने की ज़रूरत नहीं लगती, क्योंकि उसके बाद ping expire हो जाएगा। 512 × 2s = 10,240,000 × 100μs, इसलिए उस precision पर लगभग 23.3 bits काफ़ी हैं, और चाहें तो इसे 24 bits तक बढ़ाया जा सकता है। बचने वाले लगभग 6,536,216 invalid bit patterns शायद किसी और काम भी आ सकते हैं
    बोनस यह है कि 24 bits होने पर “sent” precision को काफ़ी बढ़ाकर quantization error कम किया जा सकता है। microsecond precision पर भी ping ज़्यादा से ज़्यादा 16 सेकंड देर से भेजा जा सकता है, इसलिए यह काफ़ी उदार सीमा लगती है
    sample को 64 bits से 48 bits करने से performance में मदद मिलेगी या नुकसान होगा, यह पक्का नहीं कह सकता। x86 और ARM के 32-bit/64-bit environments में नतीजे अलग हों तो हैरानी नहीं होगी

    • AArch64, AArch32 (शायद ARMv5 के बाद से), और modern x86-64 में सबमें bit-field extract/insert instructions हैं, और अगर वे न भी हों तो इसकी लागत कम है
      वैसे भी मूल आकार इतना छोटा है कि काफ़ी पुराने processor के data cache में भी बहुत आसानी से फिट हो जाएगा, इसलिए memory बचत से कोई खास फ़र्क पड़ेगा, ऐसा नहीं लगता

  • मुझे पूरा यक़ीन है कि हम premature optimization इसलिए करते हैं। यह मज़े के लिए खेला जाने वाला खेल है

  • सिस्टम डिज़ाइन करते समय या low-level system language में काम करते समय premature optimization ईमानदारी से कहूँ तो मेरे पसंदीदा कामों में से एक है
    कम से कम यह उम्मीद तो रहती है कि बाद में समय और memory बचेगी। बीच वाला नतीजा बस इतना होता है कि “मैंने इसे ऐसे क्यों बनाया?” समझने की कोशिश में सिरदर्द थोड़ा और बढ़ जाता है, और सबसे बुरा मामला — जो कभी-कभी उल्टा बेहतर भी होता है — यह है कि डिज़ाइन के दौरान optimization का काम इतना बढ़ जाता है कि पूरा project ही नहीं हो पाता। “अरे, यह तो बहुत उलझ गया, मैं यह कर ही क्यों रहा हूँ?” कहकर program बंद कर देते हैं