การย่อขนาด {fmt}: ลดขนาดไบนารีเหลือ 14k และตัด C++ runtime ออก

 (vitaut.net)
1 คะแนน โดย GN⁺ 2024-09-02 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • {fmt} เป็นไลบรารีฟอร์แมตสำหรับ C++ ที่ลดการพองตัวของเทมเพลตด้วย type erasure และในการทดลองครั้งนี้ลดขนาดไฟล์ปฏิบัติการ fmt::print แบบง่ายจาก 75kB เหลือ 14kB
  • โครงสร้างหลักคือให้ format ส่งงานต่อไปยัง vformat ที่ไม่ใช่เทมเพลต และซ่อนชนิดเอาต์พุตไว้หลัง buffer API จึงช่วยลดได้ทั้ง ขนาดไบนารี และเวลา build
  • บน aarch64 Ubuntu 22.04 และ GCC 11.4.0 ไฟล์ปฏิบัติการที่ strip แล้วของ {fmt} 11.0.2 มีขนาด 75kB และเมื่อตัด locale ออก ลดชนิด built-in และใช้แมโครปรับให้เหมาะกับขนาด ก็ลดลงเป็น 71kB → 31kB → 27kB → 23kB
  • การตัด C++ runtime ออกทำได้โดยให้ exception ถูกจัดการด้วย FMT_THROW เป็น abort, build ด้วย -fno-exceptions, -nodefaultlibs, -lc แล้วเปลี่ยน allocator เริ่มต้นของ basic_memory_buffer ให้ใช้ malloc/free
  • ไฟล์ปฏิบัติการสุดท้ายมีขนาด 14kB และเมื่อพิจารณาว่า C main เปล่าในระบบเดียวกันมีขนาด 6kB ขนาดที่ {fmt} เพิ่มเข้ามาจึงน้อยกว่า 10kB และใน ldd ก็ไม่เห็น dependency ต่อ C++ runtime

วิธีที่ {fmt} สร้างไบนารีขนาดเล็ก

  • {fmt} formatting library มักสร้างโค้ดต่อการเรียกฟังก์ชันน้อยกว่าทางเลือกอย่าง IOStreams, Boost Format, tinyformat หลายเท่า
  • แก่นหลักอยู่ที่โครงสร้างซึ่งใช้ type erasure ในหลายชั้น เพื่อลดการพองตัวของเทมเพลต
  • อาร์กิวเมนต์สำหรับฟอร์แมตถูกทำ type erasure ด้วย format_args
    • ฟังก์ชันเทมเพลต format ส่งงานจริงต่อไปยัง vformat ที่ไม่ใช่เทมเพลต
    • output iterator และชนิดเอาต์พุตอื่น ๆ ก็ถูกทำ type erasure ผ่าน buffer API แยกต่างหาก
  • การใช้เทมเพลตถูกจำกัดไว้ที่ชั้นบาง ๆ ด้านบนสุด และโครงสร้างนี้ช่วยให้ไบนารีเล็กลงและ เวลา compile C++ เร็วขึ้น

ขนาดโค้ดใกล้เคียง printf พร้อมความปลอดภัยที่แข็งแรงกว่า

  • โปรแกรมตัวอย่างเรียกเพียง fmt::print("The answer is {}.", 42);
  • ผลการ compile เล็กกว่า IOStreams มาก และอยู่ในระดับใกล้เคียงตัวอย่าง printf
    • ตัวอย่าง {fmt} บน Godbolt: godbolt
    • ตัวอย่าง printf บน Godbolt: godbolt
  • ต่างจาก printf ตรงที่ {fmt} ให้ ความปลอดภัยด้านชนิดใน runtime
    • ข้อผิดพลาดใน format string สามารถตรวจจับได้ตอน compile time
    • แม้ format string จะถูกกำหนดตอน runtime ก็จัดการข้อผิดพลาดด้วย exception เพื่อหลีกเลี่ยง undefined behavior, ความเสียหายของหน่วยความจำ และ crash ที่อาจเกิดขึ้น
  • เมื่อใช้ positional arguments ซึ่งไม่เข้ากับ variadic arguments ของ C เท่าไร การเรียก {fmt} โดยทั่วไปจะมีประสิทธิภาพกว่า

ขนาดตั้งต้นและการตัด locale ออก

  • ในบทความปี 2020 เรื่อง การปรับขนาดไลบรารีให้เล็กลง เคยลด {fmt} ให้ต่ำกว่า 100kB และเหลือราว 57kB เมื่อใช้ -Os -flto
  • หลังจากนั้น {fmt} เริ่มใช้ algorithm Dragonbox ที่ Junekey Jeon มีส่วนร่วมพัฒนา สำหรับการฟอร์แมต floating-point
  • การวัดครั้งนี้อิงจากขนาดไฟล์ปฏิบัติการที่ผู้ใช้ปลายทางรับรู้ และทำบน aarch64 Ubuntu 22.04 กับ GCC 11.4.0
  • build ตั้งต้นของ {fmt} 11.0.2 มีขนาด 75kB หลังใช้ -Os -flto -DNDEBUG และ strip
    • แม้ตลอด 4 ปีที่ผ่านมาจะมีการเปลี่ยนแปลงหลายอย่าง แต่ขนาดไม่ได้ถดถอยมากนัก
  • เมื่อตัดการรองรับ locale ด้วย FMT_STATIC_THOUSANDS_SEPARATOR ขนาดไบนารีลดลงเป็น 71kB
    • การฟอร์แมตของ {fmt} โดยพื้นฐานไม่ขึ้นกับ locale
    • locale สามารถเลือกใช้ได้ผ่าน format specifier L

การลดชนิด built-in และโมเดล “ไม่ใช้ก็ไม่ต้องจ่ายต้นทุน”

  • การวิเคราะห์ด้วย Bloaty พบว่าการฟอร์แมตตัวเลข โดยเฉพาะ การฟอร์แมต floating-point กินสัดส่วนใหญ่ของขนาดไบนารี
    • การฟอร์แมต floating-point ใช้ตารางด้วย และตารางดังกล่าวไม่ปรากฏใน output ของ Bloaty
  • ภาระพื้นฐานเกิดจากฟังก์ชันฟอร์แมตต้องรู้จักทุกชนิดที่ฟอร์แมตได้
    • วิธีนี้เหมาะกับ printf ในมาตรฐาน C แต่ไม่ใช่เงื่อนไขจำเป็นสำหรับ {fmt}
    • {fmt} รองรับ API ส่วนขยายที่สามารถฟอร์แมตชนิดใด ๆ ได้โดยไม่ต้องรู้ชุดชนิดทั้งหมดล่วงหน้า
  • ใน implementation ทดลอง มีการตั้งค่า FMT_BUILTIN_TYPES=0 เพื่อจัดการพิเศษเฉพาะ int และส่งชนิดที่เหลือไปยัง API ส่วนขยายทั่วไป
    • int จำเป็นสำหรับการจัดการความกว้างและความแม่นยำแบบ dynamic
    • ตัวอย่าง: fmt::print("{:{}}\n", "hello", 10); จะพิมพ์ "hello "
  • วิธีนี้ให้ โมเดลที่ไม่ต้องจ่ายต้นทุนสำหรับชนิดที่ไม่ได้ใช้ แต่ขนาดไบนารีต่อการเรียกจะเพิ่มขึ้นเล็กน้อย
    • หากฟอร์แมต floating-point หรือชนิดอื่นจริง โค้ดที่เกี่ยวข้องก็ยังจะถูกใส่เข้ามาใน build
  • หลังใช้ FMT_BUILTIN_TYPES=0 ไบนารีตัวอย่างลดลงเหลือ 31kB
  • จากนั้นจึงลบร่องรอยที่เกี่ยวกับ locale ที่ยังเหลืออยู่ใน e582d37 และ b3ccc2d พร้อมทำให้ปิดได้ชัดเจนขึ้นด้วยแมโคร FMT_USE_LOCALE ทำให้ขนาดเหลือ 27kB

การเลือกระหว่างความเร็วกับขนาด และการตัด C++ runtime ออก

  • ภายในไลบรารีมีหลายจุดที่แลกขนาดเพื่อความเร็ว
  • do_count_digits ซึ่งคำนวณจำนวนหลักในเลขฐานสิบใช้ตาราง 256 ไบต์
    • หากเปลี่ยน implementation นี้แบบบังคับทั้งหมด อาจส่งผลเสียต่อ use case อื่น ๆ
    • มี fallback implementation อยู่แล้วสำหรับกรณีอย่าง constexpr ที่ใช้ __builtin_clz ไม่ได้
  • เพิ่มแมโคร FMT_OPTIMIZE_SIZE เพื่อให้ผู้ใช้ควบคุมว่าจะใช้ fallback implementation หรือไม่
    • การปรับนี้และการเปลี่ยนแปลงคล้ายกันอีกบางส่วนทำให้ขนาดไบนารีลดลงเป็น 23kB
  • เพื่อตัด dependency ต่อ C++ standard library สามารถปิด exception ด้วย FMT_THROW ได้
    • ตัวอย่างใช้ FMT_THROW(s)=abort() และ -fno-exceptions
    • โดยทั่วไปไม่แนะนำ แต่สำหรับบาง use case ที่ข้อผิดพลาดส่วนใหญ่ถูกจับได้ตอน compile time ก็อาจยอมรับได้
  • เมื่อ build ด้วย -nodefaultlibs -lc dependency ต่อ C++ runtime ที่ยังเหลือมาจาก fmt::basic_memory_buffer
    • buffer นี้เป็น buffer ขนาดเล็กที่ allocate บน stack และจะขยายด้วยหน่วยความจำแบบ dynamic เมื่อจำเป็น
    • โดยทั่วไป fmt::print สามารถเขียนลง buffer ของ FILE ได้โดยตรง จึงไม่จำเป็นต้อง allocate แบบ dynamic
  • วิธีแก้ที่ทั่วไปกว่าคือเปลี่ยน allocator เริ่มต้นจาก new/delete เป็นแบบใช้ malloc/free
    • หลังการเปลี่ยนแปลงนี้ ขนาดไบนารีสุดท้ายเป็น 14kB
    • โปรแกรม C main เปล่าในระบบเดียวกันมีขนาด 6kB ดังนั้นขนาดที่ {fmt} เพิ่มเข้ามาจึงน้อยกว่า 10kB
  • ผลลัพธ์ของ ldd a.out แสดงเฉพาะ libc.so.6 กับ loader และไม่พบ dependency ต่อ C++ runtime
  • ผลลัพธ์สุดท้ายแสดงให้เห็นว่าสามารถใช้ {fmt} ให้เล็กลงได้ใน embedded และสภาพแวดล้อมที่มีข้อจำกัดด้านหน่วยความจำ

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

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

 
GN⁺ 2024-09-02
ความคิดเห็นบน Hacker News

  • จริง ๆ แล้วเรื่องนี้ออกจะเป็นปัญหาแนว รสนิยมของคณะกรรมการ มากกว่า จึงไม่ได้คาดหวังว่า fmt ซึ่งเป็นไลบรารีจากบุคคลที่สามจะต้องมีค่าเริ่มต้นที่ผิดพลาดเสียเอง
    น่าแปลกที่เมื่อฟีเจอร์นี้ถูกทำให้เป็นมาตรฐานใน std::format ของ C++20 คณะกรรมการไม่ได้ใส่ความผิดพลาดนี้กลับเข้าไปเหมือนในหลายส่วนอื่น ๆ ของมาตรฐาน
    ดังนั้นสำหรับผู้เสนอที่พยายามร้องขอว่าอย่าทำให้ C++ แย่ลงโดยไม่จำเป็นเพียงเพื่อให้มัน “สอดคล้องกัน” ก็ยังมีความหวังอยู่บ้าง

  • ถ้าดูปริมาณโค้ดที่จำเป็นสำหรับ การฟอร์แมตเลขทศนิยมลอยตัว แล้วค่อนข้างน่าตกใจ
    โปรเจกต์ Dragonbox [1] ที่ลิงก์ไว้ก็น่าอ่าน และแม้แต่แขนงที่แทบไม่ถูกใช้งานก็ยังถูกปรับแต่งค่อนข้างมาก
    [1] https://github.com/jk-jeon/dragonbox

    • ช่วงหลังจากทำงานกับ Zig จึงได้รู้ว่าการฟอร์แมตเลขทศนิยมลอยตัวต้องใช้โค้ดมากแค่ไหน
      โดยปกติคอมไพเลอร์ Zig บน Windows ไม่พึ่งพา C runtime จึงสร้างไบนารีที่เล็กกว่า MSVC ได้ แต่ครั้งนี้ไบนารีกลับใหญ่ผิดปกติเมื่อเทียบกับสิ่งที่เครื่องมือนั้นทำ
      พอเปิดดูด้วย Binary Ninja ก็พบว่าโค้ดส่วนใหญ่เป็นส่วนรองรับการฟอร์แมตเลขทศนิยมลอยตัว และเมื่อแคสต์เลขทศนิยมลอยตัวเป็นจำนวนเต็มก่อนพิมพ์ ขนาดก็ลดลงมาเท่าที่คาดไว้
    • https://github.com/jk-jeon/dragonbox/discussions/57#discussioncomment-9340182
      กำลังทดลองปรับขนาดให้เล็กลงอยู่ และตอนนี้บน AVR 8 บิต สามารถลดลงได้ถึงประมาณ 3k
      โดยมีเฉพาะอิมพลีเมนต์และตารางสำหรับ binary32 ความแม่นยำเดี่ยว ส่วนความแม่นยำคู่ต้องใช้อีกมากกว่าเดิม แต่ในขณะเดียวกันส่วนที่บวมขึ้นจำนวนมากก็เป็นเพราะข้อจำกัดของ AVR
      บนแพลตฟอร์มอย่าง x64 อาจเล็กลงได้มากกว่านี้ แต่ก็ยังพูดได้ว่า 3k ก็ยังใหญ่พอสมควร
    • ถ้าอยากให้เร็ว ก็ต้องใช้โค้ดเยอะ
      อิมพลีเมนต์อ้างอิงก็สุดท้ายแล้วเป็นการทำ เลขคณิตความแม่นยำตามอำเภอใจ อยู่ดี แต่ก็ไม่ได้แย่ขนาดนั้น
      [1] https://research.swtch.com/ftoa
      [2] https://go.dev/src/strconv/ftoa.go
    • ใน {fmt} มีอิมพลีเมนต์เสริมของ อัลกอริทึม Dragon4 แบบเก่า ซึ่งขนาดโค้ดเล็กกว่าแต่ช้ากว่า
    • กรณีใช้งานส่วนใหญ่คงจำกัดจำนวนตำแหน่งทศนิยมที่จะพิมพ์
      เลยสงสัยว่าวิธีคูณตามจำนวนตำแหน่งทศนิยมแล้วแปลงเป็นจำนวนเต็ม ผ่าน itoa() จากนั้นค่อยแทรกจุดทศนิยมในตำแหน่งที่เหมาะสม จะมีประสิทธิภาพกว่าหรือไม่

  • ในมุมของมือใหม่ C++ ขอถามหน่อยว่า allocator เริ่มต้นของ libc++ หรือก็คืออิมพลีเมนต์ new/delete เริ่มต้น ทำอะไรที่ต่างจากการเรียก malloc/free ของ libc ภายในจริง ๆ ไหม? ถ้าต่าง ทำไมถึงเป็นเช่นนั้น?

    • ผมไม่ได้เชี่ยว C++ มากนัก แต่ new[] จะเรียกตัวดำเนินการ new เพื่อขอหน่วยความจำ แล้วพยายามรันคอนสตรัคเตอร์ของแต่ละองค์ประกอบ
      delete[] จะพยายามรันดีสตรัคเตอร์ของแต่ละองค์ประกอบก่อนคืนหน่วยความจำ
      เพื่อให้ delete[] ทำงานได้ C++ ต้องติดตามขนาดที่จัดสรรไว้ที่ไหนสักแห่ง และข้อมูลนี้อาจวางใกล้บริเวณที่จัดสรร หรือเก็บในโครงสร้างแยกก็ได้
      ถ้าใช้โครงสร้างแยก โอกาสที่ข้อมูลจะถูกเขียนทับจากการเขียนหน่วยความจำผิดพลาดหลังอ็อบเจ็กต์จะลดลง แต่ต้องมีต้นทุนการค้นหาและโค้ดเพิ่มเติม
      ไลบรารี C++ ที่ทำอย่างถูกต้องคงทำงานมากกว่านี้ แต่ก็พอเห็นภาพได้ว่า new/delete ไม่เหมือน malloc/free
    • ISO C++ ไม่ได้กำหนดว่าอิมพลีเมนต์เริ่มต้นของ new/delete ต้องเรียก malloc()/free()
      ที่หลายอิมพลีเมนต์ทำแบบนั้นก็เพราะมันมีอยู่แล้วและใช้งานง่ายเท่านั้น
    • หากไม่นับโอเวอร์โหลดของ aligned allocation โดยพื้นฐานแล้วก็ไม่ได้ต่างกัน
      อย่างไรก็ตาม แอปพลิเคชันสามารถแทนที่ operator new เริ่มต้นของไลบรารีมาตรฐานด้วยอิมพลีเมนต์ของตัวเองได้ แม้บนแพลตฟอร์มที่ไม่มีความสามารถเทียบเท่า ELF symbol interposition
    • เหตุผลหลักที่เปลี่ยนไปใช้ malloc คือ new จะโยน std::bad_alloc ทำให้ถ้าใช้มันก็ต้องลิงก์กับ C++ runtime

  • ถ้าเป็นไลบรารีฟอร์แมตที่ออกแบบมาให้เล็กและพิมพ์สตริงกับจำนวนเต็มได้ ผมคาดหวังว่าควรอยู่ราว ๆ 50 ไบต์
    สำหรับสตริงก็แค่ตรวจอักขระสิ้นสุดแบบ null, พิมพ์อักขระ, กระโดดย้อนกลับสองขั้น ประมาณ 4 คำสั่งก็พอ
    สำหรับจำนวนเต็มก็ตรวจค่าลบแล้วพิมพ์ '-' และกลับเครื่องหมาย, ใส่ 1000000000 ใน R1 แล้วหารและเก็บเศษ, บวก ASCII '0', พิมพ์อักขระ, หาร R1 ด้วย 10, ใส่เศษกลับเป็นอินพุต, ทำซ้ำจน R1=0 ประมาณ 20 คำสั่งก็พอ
    เลขทศนิยมลอยตัวไม่ได้ใช้ในหลายโปรแกรม จึงควรถูกคอมไพล์เข้ามาเฉพาะเมื่อจำเป็น และเลขฐานสิบหก·พอยน์เตอร์·การเติม 0 ด้านหน้าก็เช่นกัน
    ตอนเขียนโค้ดสำหรับไมโครคอนโทรลเลอร์ที่มีพื้นที่โค้ด 2KB คงไม่ใส่ไลบรารีฟอร์แมตสตริงขนาด 14KB เข้าไป

    • นี่ไม่ใช่ไลบรารีพิมพ์จำนวนเต็ม·สตริงแบบช้า ๆ ที่ไม่มีตัวปรับแต่ง แต่เป็น ไลบรารีฟอร์แมตที่มีฟีเจอร์เยอะ
      คุณไม่สามารถสร้างไลบรารีที่ฟีเจอร์เยอะ เร็ว และเล็กได้พร้อมกันทั้งหมด
    • การออกแบบไลบรารีสำหรับไมโครคอนโทรลเลอร์กับการออกแบบไลบรารีที่ “เทียบเท่า” สำหรับแอปพลิเคชันผู้ใช้ทั่วไป แตกต่างกันแทบทุกจุดสำคัญ
      ไม่ค่อยเข้าใจว่านี่ต่างจากการบ่นทั่วไปในที่สาธารณะอย่างไร หรือเป็นเรื่องเฉพาะกับ fmt ตรงไหน
      แค่โค้ดอัลกอริทึมอย่าง Dragonbox หรือ Dragon4 ก็เกินงบขนาดแล้ว ดังนั้นฟีเจอร์ “เสริม” จึงไม่ใช่สาระสำคัญนัก
      และนั่นก็เป็นเพียงหนึ่งในราว 20 ฟีเจอร์ที่ผู้คนต้องการ
    • ถ้าอย่างนั้นก็น่าจะเผยแพร่ไลบรารีที่ใช้อยู่จริง และทำเอกสารว่า รองรับ ฟีเจอร์การฟอร์แมต อะไรบ้าง
      แล้วคนอื่นอาจหาวิธีใส่ฟีเจอร์ได้มากขึ้นอย่างฉลาดกว่าเดิม
      ไม่อย่างนั้นก็ไม่ค่อยเห็นประเด็น
    • ผมคิดว่าความต้องการของสายเฉพาะทางบางแขนงในการเขียนโปรแกรมไม่ควรมีอิทธิพลต่อภาษาในลักษณะนั้น
      ความต้องการนั้นสมเหตุสมผล แต่เป็นสิ่งที่ คอมไพเลอร์ไมโครคอนโทรลเลอร์สเปกต่ำสุด ควรจัดการ ไม่ใช่ข้อกำหนดของภาษา
    • ไลบรารีนี้ไม่ได้มีเป้าหมายหลักเพื่อทำให้เล็ก แต่คือการทำ ไลบรารีฟอร์แมตสตริงที่ครบถ้วน โดยให้ขนาดเป็นเป้าหมายรองที่สำคัญ
      ถ้าต้องเล็กสุดขีดแลกกับการไม่รองรับแม้แต่ฟีเจอร์พื้นฐาน ก็ย่อมมีตัวเลือกที่ดีกว่าแน่นอน
      ถ้ามีพื้นที่โค้ดแค่ 2KB ก็ไม่ควรใช้ตัวนี้
      โชคดีที่ไมโครคอนโทรลเลอร์สมัยใหม่ส่วนใหญ่ใหญ่กว่านั้นมาก เช่น esp32 เริ่มที่ 1MB ดังนั้นการใช้ไลบรารีฟอร์แมตขนาด 14KB ก็สมเหตุสมผลพอสมควร

  • ขอโปรโมตนิดหนึ่ง แม้รวม libc ที่มีการบัฟเฟอร์เอาต์พุต ก็สามารถทำ printf(Hello, World!\n"); เป็น ไฟล์ปฏิบัติการ 1008 ไบต์ ได้: https://github.com/pts/minilibc686
    แน่นอนว่าถ้าเทียบกันตรง ๆ ก็เหมือนเอาแอปเปิลไปเทียบกับส้ม

    • นั่นเป็นเพราะคอมไพเลอร์แปลงมันเป็น fputs

  • ส่วนที่ว่า “ถ้าโปรแกรม C ที่มีฟังก์ชัน main ว่าง ๆ บนระบบนี้มีขนาด 6kB ตอนนี้ {fmt} ก็เพิ่มเข้าไปในไบนารีไม่ถึง 10kB” น่าสนใจดี
    ไม่เคยลองทดสอบแบบนี้มาก่อน

    • ขึ้นอยู่มากกับว่าลิงก์ C library แบบไดนามิกหรือสแตติก และแอปพลิเคชันกับ C library ถูก build อย่างไร
      ใช้ C library ตัวไหนก็สำคัญ และใช้ ELF หรือคอนเทนเนอร์อื่นก็มีผลอยู่บ้าง

  • ปัญหาเป็น fmt เสมอ
    ตลกมากที่พอไปแตะตัวเลขจำนวนมากพอ โดยเฉพาะ การฟอร์แมต/พาร์สเลขทศนิยมลอยตัวและ decimal ลิงเกอร์ก็จะดึงโค้ดเกี่ยวกับทศนิยมลอยตัวและ BigInt เข้ามาเยอะจนทำให้ขนาดไบนารีใหญ่ขึ้น และตอนนี้เรื่องเดียวกันก็เกิดใน .NET แล้ว

    • ใน Native AOT ก็ยังคาดหวังประสบการณ์แบบ Delphi อยู่ และโชคดีที่มันดีขึ้นเรื่อย ๆ

  • น่าสนุกมาก
    ชอบ การปรับแต่งแบบพลิกมุมคิด แบบนี้

  • ไม่รู้ว่าผมช้าเองหรือเปล่า แต่ใช้เวลาสักพักกว่าจะนึกได้ว่า “14k” ในชื่อเรื่องหมายถึง 14kB

    • แล้วมันจะหมายถึงอะไรได้อีกล่ะ
      อย่างน้อยในเชิงประวัติศาสตร์ k ก็เป็นตัวย่อที่ใช้กันทั่วไปของ kB