บางครั้งการเพิ่มประสิทธิภาพก่อนเวลาอันควรก็สนุกดี (2025)

 (invlpg.com)
1 คะแนน โดย GN⁺ 4 일 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ระหว่างการลดขนาดสตรักต์สำหรับบันทึก ICMP Echo Request ของระบบติดตามการเชื่อมต่อ การใช้หน่วยความจำของริงบัฟเฟอร์ ลดลงจาก 12KiB เหลือ 4KiB
  • เมื่อตัดการเก็บทั้ง sent_ns และ received_ns พร้อมกัน แล้วใช้ยูเนียนให้หลังรับแพ็กเก็ตเก็บไว้เพียง ค่า latency ขนาดอาร์เรย์จึงลดลงเหลือ 8KiB
  • เปลี่ยนจากความละเอียดระดับนาโนวินาทีเป็นหน่วยละ 100 ไมโครวินาที และเปลี่ยน received เป็นบิตฟิลด์ แต่ไม่ช่วยลดเพิ่มเพราะ struct padding
  • แทนที่จะเก็บ source address ผู้เขียนนำความหมายบางส่วนของ ICMP identifier มาใช้เป็นตัวนับ 4 บิต ทำให้สตรักต์เหลือ 8 ไบต์ และอาร์เรย์ 512 ช่องมีขนาด 4KiB
  • แม้แอปพลิเคชันจะไม่ได้มีข้อจำกัดด้านหน่วยความจำ จึงไม่ได้มีความจำเป็นเชิงปฏิบัติจริง แต่ก็กลายเป็นการทดลองเพิ่มประสิทธิภาพที่พิจารณาไปถึงการจัดวางฟิลด์และต้นทุนการเข้าถึงบิต

การตั้งปัญหา: วิธีเก็บบันทึก ping

  • ระบบติดตามการเชื่อมต่อจะส่ง ICMP Echo Request ไปยังหลายเซิร์ฟเวอร์ และเฝ้าดูค่าเฉลี่ยของ latency กับ packet loss ในช่วง 1 นาที, 5 นาที และ 15 นาที
  • วิธีเก็บข้อมูลที่นึกถึงในตอนแรกคือริงบัฟเฟอร์ขนาด 512 เอนทรี โดยแต่ละเอนทรีเก็บเวลาส่ง เวลารับ source address หมายเลขลำดับ และสถานะว่ารับแล้วหรือไม่
  • อาร์เรย์สตรักต์เริ่มต้น pings_rb[512] วัดได้ว่ามีขนาด 12KiB
struct ping_timestamp {
    uint64_t sent_ns;
    uint64_t received_ns;
    in_addr_t source_addr;
    uint16_t seq_no;
    bool received;
};

การลดครั้งแรก: รวมเวลาส่งกับเวลาที่ผ่านไปด้วยยูเนียน

  • ค่าที่อยากเก็บจริง ๆ หลังรับแพ็กเก็ตคือค่า latency received - sent ดังนั้นจึงไม่จำเป็นต้องเก็บทั้งเวลาส่งและเวลาที่ผ่านไปพร้อมกัน
  • สตรักต์ที่รวม sent_ts และ elapsed_ts ไว้ในยูเนียน จะใช้สล็อตเดียวกันเป็นเวลาส่งก่อนรับ และเป็นเวลาที่ผ่านไปหลังรับ
  • หลังเปลี่ยนแบบนี้ ขนาดอาร์เรย์ 512 ช่องลดจาก 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;
};

ความพยายามครั้งที่สอง: ลดความละเอียดและใช้บิตฟิลด์

  • เวลาของ ping วัดกันในระดับหลายสิบ หลายร้อย หรือหลายพันมิลลิวินาที จึงไม่จำเป็นต้องเก็บความละเอียดระดับนาโนวินาทีทั้งหมด
  • ถ้าเปลี่ยนหน่วยเวลาเป็น 100 ไมโครวินาที หรือ 0.1ms ก็ใช้เพียง 43 บิตเพื่อติดตาม ping ได้นานสูงสุด 20 ปี
  • การใช้ 8 บิตเพื่อเก็บค่าจริง/เท็จของ received ถือว่าเกินความจำเป็น จึงนำบิตฟิลด์มาใช้
  • แต่ขนาดอาร์เรย์ของ ping_timestamp_3 ก็ยังคงอยู่ที่ 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

  • ping_timestamp_2 มี padding bytes ต่อท้ายเพื่อให้ตรงตามข้อกำหนดการจัดแนว
  • ping_timestamp_3 นำเวลา สถานะรับ และหมายเลขลำดับใส่ไว้ใน 8 ไบต์แรก แต่ด้านหลังก็ยังเหลือ source address และ padding
  • ถึงจะใช้บิตฟิลด์ ก็ยังมี padding อยู่ 36 บิต ทำให้ขนาดสตรักต์โดยรวมไม่ลดลง
  • การลดแค่ bool ให้เหลือหนึ่งบิตอย่างเดียว ไม่ได้แก้ปัญหาเรื่อง memory layout และ alignment

การตัด source address ออกและใช้ตัวนับ 4 บิต

  • เดิมสตรักต์เก็บ source address ไว้เพราะผลิตภัณฑ์ทำงานบนเครือข่ายข้อมูลมือถือ ซึ่ง source address เปลี่ยนบ่อย
  • เมื่อ address เปลี่ยน หมายเลขลำดับก็จะถูกรีเซ็ตด้วย และในอดีตเคยมีกรณีที่มีการประมวลผลแพ็กเก็ตที่ใช้หมายเลขลำดับเดียวกันแต่ต่าง source address พร้อมกัน
  • ICMP Echo Request มีฟิลด์ identifier ขนาด 16 บิตที่แอปพลิเคชันใช้ระบุแพ็กเก็ตที่ตัวเองส่งได้
  • เนื่องจากไม่จำเป็นต้องใช้ครบทั้ง 16 บิต จึงนำ 4 บิตที่เหลือมาใช้เป็น rolling counter ที่เพิ่มขึ้นเมื่อ source address เปลี่ยน
  • ตัวนับนี้จะเพิ่มตามการเปลี่ยน source address ที่มีการเฝ้าตรวจจากตำแหน่งอื่นของแอปพลิเคชัน
struct ping_timestamp {
    uint64_t elapsed_or_sent_ts : 43;
    uint64_t received : 1;
    uint64_t counter: 4;
    uint64_t seq_no: 16;
};

ผลลัพธ์สุดท้ายและการจัดวางฟิลด์

  • สตรักต์สุดท้ายตัดฟิลด์ source address ออก และเก็บเวลา สถานะรับ ตัวนับ และหมายเลขลำดับไว้ภายใน 64 บิต
  • อาร์เรย์ริงบัฟเฟอร์ 512 ช่องจึงมีขนาด 4KiB ลดลงจนเหลือข้อมูลเพียงหนึ่งเพจ
  • เมื่อเทียบกับจุดเริ่มต้นที่ 12KiB จึงประหยัดได้รวม 8KiB
  • ลำดับของฟิลด์ถูกปรับให้ seq_no ตรงกับขอบเขต 16 บิต ทำให้อ่านตอนโหลดได้ด้วยคำสั่ง ldrh เดียวโดยไม่ต้อง shift
  • การอ่าน elapsed_or_sent_ts ต้องใช้เพียง mask เท่านั้น

การเพิ่มประสิทธิภาพเพิ่มเติม: ลดต้นทุนการเข้าถึงบิตสถานะรับ

  • เนื้อหาที่เพิ่มเมื่อ 2025-06-21 ระบุว่าถ้าสลับลำดับของ received กับ counter จะทำให้การเข้าถึงบิต received ใช้เพียง shift แทน shift กับ mask
  • การเปลี่ยนนี้ทำให้การเข้าถึง received ถูกลง แต่เพิ่มต้นทุนตอนอ่าน counter เพราะต้อง mask เพื่อตัดบิต received ออก
  • เนื้อหาที่เพิ่มเมื่อ 2025-06-22 ใช้เงื่อนไขที่ว่า counter จะถูกอ่านเฉพาะเมื่อ received เป็นจริงเท่านั้น
  • ถ้ากลับความหมายของ received เป็น not_received ก็จะสามารถตรวจว่า not_received เป็น 0 ได้ และภายในเงื่อนไขนั้น mask ของ counter ถูกคอมไพเลอร์ตัดออกได้ทั้งหมด
struct ping_timestamp {
    uint64_t elapsed_or_sent_ts : 43;
    uint64_t counter: 4;
    uint64_t not_received : 1;
    uint64_t seq_no: 16;
};

บทสรุป

  • ผลของการเพิ่มประสิทธิภาพทำให้การใช้หน่วยความจำลดจาก 12KiB เหลือ 4KiB แต่ตัวแอปพลิเคชันเองไม่ได้ติดข้อจำกัดด้านหน่วยความจำ
  • ไม่ว่าความจำเป็นจริงจะมีหรือไม่ สิ่งนี้ก็กลายเป็นการทดลองที่พิจารณาทั้ง layout ของสตรักต์, padding, บิตฟิลด์ และต้นทุนการเข้าถึงในระดับคำสั่ง
  • ในหมายเหตุท้ายบทความ ผู้เขียนยังบอกด้วยว่าคำว่า “ปัญหา” ก็ใช้แบบหลวม ๆ และไม่ได้ทำ benchmark แม้แต่ครั้งเดียว

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 4 일 전
ความเห็นจาก Lobste.rs

  • ผมมองว่าวันที่การคิดเรื่องปัญหาแบบนี้ไม่สนุกอีกต่อไป ก็คือวันที่ควรเลิกเขียนโปรแกรมแล้ว

  • การ optimize ก่อนเวลาอันควร สนุกเสมอ
    แต่การต้องตามเก็บผลลัพธ์ที่เกิดขึ้นหลังจากรู้ว่าทำไมมันถึงเป็นการ optimize ที่เร็วเกินไป มักไม่ค่อยสนุก

    • เห็นด้วย รู้ทั้งรู้ว่าต้องห้ามใจตัวเองเพราะมันอาจย้อนมาทำร้ายทีหลัง แต่ก็ยังทำเพราะมันสนุก

  • ตรงที่บอกว่าใช้ 43 บิตกับ timestamp ค่อนข้างทำให้งง น่าจะใช้แค่ 24 บิตก็พอ
    จากที่พูดถึง ring buffer ขนาด 512 ดูเหมือนว่าจะส่ง ping ใหม่ทุก 2 วินาที และติดตาม ping ย้อนหลัง 17 นาที 4 วินาทีล่าสุด
    ขั้นแรกใช้ delta encoding เทียบกับ timer/sequence ในอุดมคติก็ได้ เพิ่มเวลาส่งล่าสุดทีละ 2 วินาทีแล้วดู index ของ ring buffer ก็รู้ได้ง่าย ๆ ว่าแพ็กเก็ตควรถูกส่งเมื่อไร ดังนั้นแค่บันทึกว่าถูกส่งตรงเวลาเป๊ะ ช้า 0.1ms หรือช้า 2.3ms เป็นต้น
    เวลาที่ผ่านไปก็ดูไม่จำเป็นต้องเกิน 17 นาที 4 วินาที เพราะหลังจากนั้น ping ก็คงหมดอายุแล้ว 512 × 2s = 10,240,000 × 100μs ดังนั้นที่ความละเอียดนั้นใช้ประมาณ 23.3 บิตก็พอ และถ้าต้องการก็ปัดขึ้นเป็น 24 บิตได้ เหลือรูปแบบบิตที่ใช้ไม่ได้อยู่อีกราว 6,536,216 แบบ ซึ่งอาจนำไปใช้ประโยชน์อย่างอื่นได้
    แถมถ้าใช้ 24 บิตก็ยังเพิ่มความละเอียดของสถานะ “ส่งแล้ว” ได้มากขึ้น ลด quantization error ได้อีก ที่ระดับความละเอียดไมโครวินาที ping ยังส่งช้าได้มากสุด 16 วินาที ก็ดูเหลือเฟือแล้ว
    ไม่แน่ใจว่าการลดขนาด sample จาก 64 บิตเหลือ 48 บิตจะช่วยหรือกลับเป็นโทษต่อประสิทธิภาพ ผลจะต่างกันไปในสภาพแวดล้อม 32 บิต/64 บิตของ x86 และ ARM ก็คงไม่แปลก

    • AArch64, AArch32 (น่าจะตั้งแต่ ARMv5), และ x86-64 รุ่นใหม่ต่างก็มีคำสั่งดึง/แทรกบิตฟิลด์ และถึงไม่มี ต้นทุนก็ยังต่ำ
      แต่ขนาดเดิมก็ดูเล็กพอจะลงใน data cache ของโปรเซสเซอร์ที่ค่อนข้างเก่าได้สบายอยู่แล้ว ดังนั้นการประหยัดหน่วยความจำน่าจะไม่ใช่สิ่งที่สร้างความแตกต่าง

  • ผมมั่นใจว่าเหตุผลที่เราทำ optimize ก่อนเวลาอันควรก็เพราะอย่างนี้แหละ มันคือกีฬาที่ทำเพื่อความสนุก

  • เวลาออกแบบระบบหรือทำงานกับภาษาเชิงระบบระดับล่าง การ optimize ก่อนเวลาอันควร เป็นหนึ่งในสิ่งที่ผมชอบที่สุดจริง ๆ
    อย่างน้อยก็มีความหวังว่ามันจะช่วยประหยัดเวลาและหน่วยความจำในภายหลัง ผลลัพธ์ระดับกลาง ๆ คืออย่างมากก็ปวดหัวเพิ่มนิดหน่อยตอนพยายามหาคำตอบว่า “ทำไมถึงสร้างมันแบบนี้นะ?” ส่วนกรณีแย่ที่สุด และบางทีกลับดีกว่า ก็คืองาน optimize ระหว่างออกแบบมันบานปลายจนสุดท้ายทำโปรเจกต์ต่อไม่ได้เลย แล้วก็ปิดโปรแกรมไปพร้อมคิดว่า “อา มันพันกันยุ่งเกินไปแล้ว จะทำสิ่งนี้ไปทำไม?”