แก้ปัญหาประสิทธิภาพของ Gleam ที่ค้างมานาน 3 ปีด้วย Rust arena

 (giacomocavalieri.me)
1 คะแนน โดย GN⁺ 6 시간 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • แก้ปัญหาการปรับปรุงประสิทธิภาพที่ค้างมานาน 3 ปี โดยเปลี่ยน การจัดสรรฮีปแยกรายครั้ง ที่เกิดซ้ำในโครงสร้าง Document แบบ recursive ของฟอร์แมตเตอร์ Gleam ให้เป็น reference แบบ arena
  • แทนที่ Box<Self> ด้วย &Self ที่เก็บอยู่ใน arena และใช้ การตรวจสอบ lifetime ของ Rust เพื่อรับประกันว่าข้อมูลภายในจะไม่ถูกอ้างอิงหลังจาก arena ถูกลบไปแล้ว
  • จัดสรร Document ที่เกิดซ้ำหลายร้อยรายการ เช่น คีย์เวิร์ดของภาษาและจุลภาค เพียงครั้งเดียวแล้วนำกลับมาใช้ซ้ำ ทำให้เวลารันของ pretty printer ลดจาก 13ms เหลือ 9.8ms เร็วขึ้น 24%
  • เวลารันโดยรวมของ gleam format ซึ่งรวมการอ่านและ parsing ซอร์สด้วย ก็ ลดลง 13% และการใช้หน่วยความจำสูงสุดลดจาก 8.4MB เหลือ 7.6MB หรือประมาณ 10%
  • แม้ต้องแก้ฟังก์ชันและจุดเรียกใช้งานเป็นวงกว้างเพื่อส่ง arena ต่อไป จนต้องทำงานด้วยมือขนาด +2963/-1032 แต่ก็สามารถปรับปรุงทั้งความเร็วและการใช้หน่วยความจำได้ด้วยวิธี ลดการจัดสรรแยกรายครั้งที่เกิดซ้ำ

ต้นทุนการจัดสรรที่เกิดจากโครงสร้าง Document แบบ recursive

  • pretty printer ของ Gleam ใช้ โครงสร้างข้อมูล Document แบบ recursive เพื่อแสดงว่าควรพิมพ์โค้ดอย่างไร และควรตัดบรรทัดตรงไหนเมื่อเกินขีดจำกัดความยาวบรรทัด
  • variant หลัก ๆ ประกอบด้วย String ที่เก็บสตริงที่จะพิมพ์, Break ที่กำหนดสตริงก่อนและหลังการขึ้นบรรทัดใหม่, Group ที่รวมเอกสารหลายชิ้นเข้าด้วยกัน, Nest ที่เพิ่มการเยื้องเมื่อขึ้นบรรทัดใหม่ เป็นต้น
  • แม้แต่ลิสต์ [1, 2] ก็แสดงได้ด้วยการประกอบ String, Break, Nest, Group เข้าด้วยกัน
    • ถ้าอยู่ในบรรทัดปัจจุบันได้ จะพิมพ์เป็นบรรทัดเดียวเหมือน [1, 2]
    • ถ้าเกินขีดจำกัดบรรทัด จะตัดเป็นหลายบรรทัดตาม Break ที่กำหนดไว้ พร้อมเยื้องและพิมพ์จุลภาคท้ายรายการด้วย
  • variant ที่เก็บ Document อื่นไว้ภายใน เช่น Nest เดิมใช้ Box<Self> จึงต้อง จัดสรรบนฮีปแยกรายครั้ง สำหรับเอกสารที่ซ้อนกันแต่ละชิ้น และงานนี้อาจกินเวลารันไปเป็นสัดส่วนมาก
  • อัลกอริทึมพื้นฐานของ pretty printer ของ Gleam ดูได้จากบทความ Strictly Pretty

แทนที่ Box ด้วย reference ของ arena

  • เปลี่ยน Nest(Box<Self>) เดิมเป็น Nest(&'doc Self) เพื่อเปลี่ยนโครงสร้างให้ อ้างอิง Document อื่นที่เก็บอยู่ใน arena
  • เพิ่ม lifetime ของข้อมูลเอกสาร 'doc เข้าไปใน Document แยกจาก lifetime ของสตริง 'string เพื่อให้เก็บ reference ได้
  • ใช้ crate typed_arena ในการ implement
    • เมื่อเก็บค่าลง arena ด้วย alloc จะคืน reference ของค่านั้นกลับมา
    • ข้อมูลที่ถูกจัดสรรสามารถใช้งานได้ตราบใดที่ arena ยังมีชีวิตอยู่
    • เมื่อ arena หลุดออกจาก scope ข้อมูลภายในก็จะถูกลบไปพร้อมกัน
  • reference ที่ alloc(&self, value: T) -> &mut T คืนกลับมาไม่สามารถมีชีวิตอยู่นานกว่า arena ได้ และ borrow checker ของ Rust จะป้องกัน reference ที่ผิดพลาดหลังจาก arena ถูกลบ

จัดสรรเอกสารที่ซ้ำกันเพียงครั้งเดียวแล้วนำกลับมาใช้ซ้ำ

  • arena ไม่ได้ถูกใช้แค่อ้างอิงเอกสารอื่นเท่านั้น แต่ยังใช้ cache Document ที่เกิดซ้ำทั่วทั้งโค้ดด้วย
  • ไม่จำเป็นต้องสร้างเอกสารใหม่ทุกครั้งสำหรับคีย์เวิร์ดของภาษา เช่น String("fn"), String("pub"), String("type")
  • เอกสารอย่าง Break { unbroken: ", ", broken: "," } ที่ใช้คั่นรายการในลิสต์ ก็จัดสรรครั้งเดียวแล้วนำกลับมาใช้ซ้ำได้
  • ทำให้สามารถจัดสรร เอกสารขนาดเล็กหลายร้อยรายการ ที่เดิมต้องใส่ลง Box อยู่เรื่อย ๆ ได้เพียงรายการละหนึ่งครั้ง

API ที่เรียบง่ายกับการแก้ไขจุดเรียกใช้งานเป็นวงกว้าง

  • ตัว API ของ arena เองเรียบง่าย แต่กระบวนการย้ายโค้ดเดิมส่วนใหญ่ต้องอาศัยการแก้ไขซ้ำ ๆ
  • ฟังก์ชันที่ก่อนหน้านี้แค่เรียก Box::new ตอนนี้ต้องรับ argument arena เพิ่มเพื่อใช้จัดสรรข้อมูล
  • ฟังก์ชันอย่าง format_list ถูกปรับให้ส่ง arena เดียวกันต่อไปยังฟังก์ชันย่อยที่ฟอร์แมตรายการในลิสต์ และสร้างเอกสารซ้อนกันด้วย arena.alloc แทน Box::new
  • หลังค้นหาและแทนที่อย่างระมัดระวังเป็นเวลาหลายวัน งานก็เสร็จในรูปของ pull request ขนาด +2963/-1032
  • เป็นงานที่ซ้ำ ๆ และต้องทำด้วยมือ โดยไม่ได้ใช้ LLM ในกระบวนการนี้

ปรับปรุงความเร็วและการใช้หน่วยความจำสูงสุด

  • เมื่อฟอร์แมตโปรเจกต์ Gleam จริงอย่าง squirrel เวลารันของ pretty printer ลดจาก 13ms เหลือ 9.8ms
    • หากเทียบเฉพาะ pretty printer ถือว่า ประสิทธิภาพดีขึ้น 24%
  • gleam format นอกจากการฟอร์แมตแล้วยังต้องอ่านและ parse ซอร์สโค้ดของโปรเจกต์ด้วย ดังนั้น pretty printer จึงเป็นเพียงส่วนหนึ่งของงานทั้งหมด แต่เวลารันโดยรวมก็ยัง ลดลง 13%
  • การใช้หน่วยความจำสูงสุดลดจาก 8.4MB เหลือ 7.6MB หรือประมาณ 10%
  • ผลจากการลดจำนวนการจัดสรรฮีปแยกรายครั้งด้วย arena ทำให้ฟอร์แมตเตอร์รันเร็วขึ้นและใช้หน่วยความจำน้อยลงไปพร้อมกัน

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

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

 
GN⁺ 6 시간 전
ความคิดเห็นบน Lobste.rs

  • หากต้องการลดการใช้หน่วยความจำสูงสุดลงอีก 10% ก็ควรพิจารณา arena แบบอื่นที่คืนค่าเป็น opaque handle แทน reference ได้เช่นกัน เพราะสามารถทำให้ handle มีขนาด 16 บิตหรือ 32 บิตแทน 64 บิตได้ จึงมีผลมากเมื่อมีการจัดสรรขนาดเล็กจำนวนมาก
    ตาม https://donsz.nl/blog/arenas/ crate ที่รองรับสิ่งนี้มีเพียง compact_arena เท่านั้น แต่ถ้าไม่ตรงกับความต้องการ การทำขึ้นเองก็ไม่ใช่เรื่องยาก

    • การใช้ opaque handle ยังช่วยให้จัดเก็บข้อมูลได้แน่นหนา/กระชับขึ้นด้วย โปรเจกต์ส่วนตัวอย่าง columnar จัดเก็บรายการ Option<T> โดยแยกเป็นข้อมูลการมีอยู่ที่ใช้ราว ๆ 1 บิตต่อรายการ กับค่า T ของรายการที่มีอยู่จริง
      แต่จะคืนค่าในรูปแบบ reference เป็น Option<&T> ไม่ใช่ &Option<T> และโดยทั่วไปคือเป็นวิธีที่ทำ recursion เชิงโครงสร้างตาม reference แทนที่จะวาง reference ไว้ภายใน structural recursion
    • บทความนั้นอ้างอิงจาก การสำรวจเมื่อ 2 ปีก่อน และไม่ได้ครอบคลุม crate ทั้งหมดอย่างสมบูรณ์ หากพบข้อผิดพลาดหรือไลบรารีใหม่ที่ตกหล่น ก็สามารถส่ง PR ไปได้
      arena สมควรถูกใช้งานอย่างแพร่หลายกว่านี้ และหากคืนค่าเป็น reference แทน handle หรือ smart pointer การทำ pattern matching กับ recursive enum ใน Rust จะสะดวกมาก ปกติแม้จะอยากเขียนแบบ if let MyAst::Add(MyAst::Multiply(a, b), c) = expr {} ก็มักทำไม่ได้เพราะมีกล่องหรือ pointer คั่นอยู่ตรงกลาง แต่ reference สามารถ pattern match ได้อย่างโปร่งใสโดยไม่ต้องใช้ฟีเจอร์ nightly หาก reference ทั้งหมดชี้ไปยัง arena เดียวกัน lifetime ที่เชื่อมทั้ง tree ไว้ด้วยกันก็จะคงความสอดคล้องได้
    • ผลลัพธ์ออกมาดี จึงกำลังพิจารณา เปลี่ยนส่วนอื่น ๆ ของ compiler ไปใช้แนวทาง arena ด้วย และจะติดตามแนวทางนี้ต่อไป

  • วิธีนี้ค่อนข้างคล้ายกับแนวทางที่ pretty ซึ่งเป็นไลบรารี pretty-printing อีกตัวตาม แนวทางของ Wadler รองรับอยู่เช่นกัน อย่างไรก็ตาม เนื่องจากรองรับ วิธีจัดสรรหน่วยความจำ หลายแบบ API จึงอาจรู้สึกค่อนข้างหนักไปหน่อย

  • น่าประหลาดใจที่ผู้เขียน 论文 ที่อ้างถึงในบทความ ทำงานอยู่ที่บริษัท IT ธรรมดาแห่งหนึ่งใน Brunswick

    • นี่แหละคือเสน่ห์ของ โอเพนซอร์ส ความเชี่ยวชาญกับงานที่ทำหาเลี้ยงชีพมักไม่ได้สัมพันธ์กันมากนัก