อาร์เรย์ enum ที่ใช้หน่วยความจำอย่างมีประสิทธิภาพใน Zig

 (alic.dev)
3 คะแนน โดย GN⁺ 2023-09-19 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เมื่อเก็บ enum/tagged union ที่มี variant ขนาดต่างกันจำนวนมาก จะต้องจองพื้นที่ตาม variant ที่ใหญ่ที่สุด ทำให้ต้นทุนจาก padding และ fragmentation ใน Vec·HashMap สูงขึ้น
  • Zig สามารถตรวจดูขนาดฟิลด์·alignment·discriminant ผ่าน comptime และการสะท้อนชนิดข้อมูล แล้วแปลงคอนเทนเนอร์ enum แบบ generic ตาม memory layout ได้
  • Vec<Enum> แบบธรรมดาทำให้ทุกองค์ประกอบใช้พื้นที่เท่ากับ variant ที่ใหญ่ที่สุด ส่วน SoA ช่วยลด padding ของ tag ได้ แต่ยังเหลือ variant fragmentation ในพื้นที่เก็บค่า
  • dense AoVA ที่จัดกลุ่ม variant ขนาดเท่ากันเข้าด้วยกัน สามารถลดจาก 15 เวกเตอร์ใน enum ตัวอย่างให้เหลือ 3 คลัสเตอร์ขนาด 2·4·8 ไบต์ แต่ถ้ามีหลาย variant ปะปนอยู่ใน allocation เดียวกัน การวนลูปแบบ type-safe จะทำได้ยาก
  • Rust proc macro เข้าถึงข้อมูลขนาด·alignment ของชนิดข้อมูลได้ยาก และยังมีข้อจำกัดในการคำนวณความยาวอาร์เรย์แบบ generic จึงทำให้ staged แบบรับรู้ชนิดข้อมูลของ Zig แสดงให้เห็นการประกอบรวมด้านประสิทธิภาพหน่วยความจำของโค้ดระบบได้ชัดกว่า

อาร์เรย์ enum ของ Rust เปลืองพื้นที่อย่างไร

  • enum/tagged union ที่มี variant ขนาดต่างกัน ต้องจองหน่วยความจำให้พอสำหรับเก็บ variant ที่ใหญ่ที่สุด
  • enum ตัวอย่าง Foo มี variant แบบ u8, u16, u32, u64 และเพราะ tag กับ alignment ทำให้ขนาดของชนิดข้อมูลนี้กลายเป็น 16 ไบต์
  • เมื่อนำ enum แบบนี้ไปใส่ใน Vec หรือ HashMap จำนวนมาก แต่ละองค์ประกอบจะกินพื้นที่ตาม variant ที่ใหญ่ที่สุด ทำให้ padding และ fragmentation สูงขึ้น
  • การแปลงเป็น struct of arrays(SoA) ที่แยก tag ไปไว้อีก allocation หนึ่ง ช่วยลด padding บางส่วนได้ แต่ไม่ได้กำจัด fragmentation ในส่วนข้อมูลค่าที่เกิดจากความต่างของขนาด variant
  • แม้ใน Rust จะสร้างโครงสร้างข้อมูลเฉพาะสำหรับ enum บางตัวได้เอง แต่การสร้างโครงสร้างข้อมูลแบบ generic ที่ใช้หน่วยความจำได้คุ้มที่สุดสำหรับ enum ใดก็ได้ ยังทำได้ยากมากหรือแทบเป็นไปไม่ได้
    • proc macro ติด #[derive] ให้กับชนิดข้อมูลของบุคคลที่สามหรือ type alias ได้ยาก และมี composability ต่ำ
    • มันไม่มีการรับรู้ชนิดข้อมูล และวิธีอ้อมด้วย generic_const_expr ก็ทำให้ where clause ยืดยาวและแพร่ไปทั่ว call graph อีกทั้งยังไม่เข้ากับ generic type parameter มากนัก

ทำไมปัญหานี้เด่นชัดใน AST ของคอมไพเลอร์

  • หนึ่งในแรงจูงใจใหญ่ของอาร์เรย์ enum ที่มีประสิทธิภาพ คือการใช้หน่วยความจำของ AST ของคอมไพเลอร์
  • AST ขนาดใหญ่ทำให้เกิด memory latency และ cache eviction ระหว่างคอมไพล์ ซึ่งมีต้นทุนสูงต่อประสิทธิภาพฝั่ง frontend
  • ในวิดีโอเกี่ยวกับ Carbon compiler ของ Chandler Carruth มีการบอกว่า AST ของ clang ที่ parse แล้ว มักใช้หน่วยความจำมากกว่าซอร์สโค้ดต้นฉบับถึง 50 เท่า
  • ตัวอย่างการแทนโหนด expression ใน Rust ใช้ enum Expr
    • Unit
    • Number
    • Binary(Operation, ExprId, ExprId)
    • Ident(Symbol)
    • Eval(ExprId, ExprSlice)
    • BlockExpression(ExprId, StatementSlice)
  • OCaml สามารถแทนชนิดข้อมูลแบบ recursive ได้โดยไม่ต้องมี indirection แบบชัดเจน เพราะระบบรันไทม์และ GC จัดการหน่วยความจำให้
  • ใน Rust, Vec<Expr> ทำให้ทุกองค์ประกอบใช้พื้นที่เท่ากับ sizeof(Enum) ซึ่งรวมทั้งขนาดของ variant ที่ใหญ่ที่สุด, tag และ padding

ลด fragmentation ด้วย SoA และ AoVA

  • หาก enum แบบง่ายมี 3 variant ที่มีสมาชิกขนาด 8, 16 และ 32 บิต Vec ปกติจะต้องจองพื้นที่มากให้ทุกองค์ประกอบเพื่อรองรับ variant 32 บิตและเงื่อนไข alignment
  • วิธีปรับปรุงที่พบได้บ่อยคือใช้ tagged index เป็นต้น เพื่อ ทำให้ตัว enum variant เองมีขนาดเล็กลง
    • tagged_index crate ของ Rust compiler
    • กรณีของ small-string optimization
    • เป็น optimization ที่ใช้บ่อยในโค้ดประสิทธิภาพสูง เช่น language runtime, GC, compiler, game engine และ OS kernel
  • อีกทางหนึ่งคือเปลี่ยนคอนเทนเนอร์เป็นแบบ SoA ที่เก็บ discriminant และค่าไว้คนละ allocation
    • self-hosted Zig compiler ใช้วิธีนี้
    • มันช่วยลด padding ที่เกิดจาก tag แต่ใน collection ของค่า union ก็ยังมี variant fragmentation อยู่
  • staged compilation ของ Zig ทำให้สามารถสร้างคอนเทนเนอร์แบบ generic ที่แปลงเป็น SoA สำหรับชนิดข้อมูลใดก็ได้
  • ฝั่ง Rust ต้องพึ่ง proc macro อย่าง soa_derive และติดข้อจำกัดว่าต้องแก้ซอร์สของชนิดข้อมูลจากภายนอกไม่ได้เพื่อใส่ #[derive]

อาร์เรย์แยกตาม variant และการจัดกลุ่มตามขนาด

  • หากต้องการลด fragmentation ในพื้นที่เก็บค่าให้มากขึ้น สามารถมี หนึ่งเวกเตอร์ต่อหนึ่ง variant ได้
  • ตอนแทรกข้อมูล จะคืนค่าเป็น tagged index ที่เก็บทั้ง tag ของ enum และ index ภายในอาร์เรย์ของ variant นั้น
  • แพตเทิร์นนี้เรียกว่า array of variant arrays(AoVA)
  • AoVA สามารถทำได้ด้วย proc macro ใน Rust และด้วย comptime ใน Zig
  • ถ้ามี variant จำนวนมาก และหลาย variant มีขนาดเท่ากัน จำนวนเวกเตอร์แบบแยกตาม variant จะเพิ่มมากเกินไป
    • enum ตัวอย่าง Foo มี 15 variant
    • วิธีแยกเวกเตอร์ตาม variant ต้องเพิ่มเวกเตอร์ 15 ตัว
    • อาจทำให้เกิดการ reallocation และ system call มากขึ้น และอาจต้องใช้หน่วยความจำเพื่อ amortization มากกว่า Vec แบบ naive
    • เวกเตอร์อาจกระจายอยู่ในหน่วยความจำแบบสุ่ม ทำให้โอกาสเกิด cache conflict สูงขึ้น
    • คอนเทนเนอร์ AoVA เองก็ใช้หน่วยความจำมาก และอาจทำให้ struct ที่บรรจุมันอยู่มีขนาดบวมขึ้น
  • หากจัดกลุ่มตามขนาด enum ตัวอย่างจะถูกแบ่งเป็น 3 คลัสเตอร์คือ 2 ไบต์, 4 ไบต์, 8 ไบต์
    • c_2: Vec<[u8; 2]> เก็บ A ถึง D
    • c_4: Vec<[u8; 4]> เก็บ E ถึง I
    • c_8: Vec<[u8; 8]> เก็บ J ถึง O
  • วิธี dense AoVA ช่วยลดจำนวนเวกเตอร์ทั้งหมดได้ 80%
  • แต่เมื่อเก็บ variant ต่างชนิดไว้ใน allocation เดียวกัน ก็จะวนลูปกับเวกเตอร์แบบ type-safe ได้ยาก
    • การเข้าถึงทำได้ผ่าน tagged pointer ที่สร้างตอนแทรกข้อมูลเท่านั้น
    • ถ้าเป็นโครงสร้างต้นไม้ที่อิง flattened index และไม่ต้องทำ blind iteration ก็นับเป็น trade-off ที่ยอมรับได้
  • ถ้าจำเป็นต้องมีการวนลูปแบบ type-safe ก็สามารถยอมรับต้นทุน padding แล้วใส่ tag กลับเข้าไปได้
  • หาก padding ใหญ่เกินไป ก็อาจใช้การแปลง SoA กับอาร์เรย์ของแต่ละ variant ได้ แต่กรณีนี้จำนวนเวกเตอร์จะเพิ่มเป็นสองเท่า

comptime ของ Zig กับ composability ของ memory layout

  • โปรโตไทป์ของ Zig ถูกนำไปทำไว้ใน osmium
  • หัวใจสำคัญคือ compile-time reflection ที่ใช้ built-in ของคอมไพเลอร์เพื่อตรวจดูชนิดข้อมูลฟิลด์, ขนาดเป็นไบต์, ขนาดเป็นบิต และ discriminant
  • โค้ดตัวอย่างใช้ @typeInfo(inner) เพื่อตรวจชนิดข้อมูล และประมวลผลเฉพาะกรณีที่เป็น union
    • วนลูปผ่าน field ของ union
    • คำนวณพื้นที่ที่ต้องใช้ด้วย @max(field.alignment, @sizeOf(field.type))
    • เก็บข้อมูลขนาดไว้ในเวกเตอร์ที่จัดสรรบนสแตก
    • สร้าง mapping จาก union field ไปยัง cluster index
    • หากไม่ใช่ union จะทำให้เกิด compile error
  • ดูโค้ดส่วนที่ตรงกันได้ที่ ซอร์สนี้
  • การทำตัวอย่างเดียวกันด้วย Rust proc macro นั้นแทบเป็นไปไม่ได้โดยพื้นฐาน
    • proc macro เข้าถึงข้อมูล size หรือ alignment ของชนิดข้อมูลไม่ได้
    • แม้จะสร้าง const fn สำหรับคำนวณคลัสเตอร์ของ enum เฉพาะตัวได้ ก็ไม่สามารถนำไปใช้กำหนดความยาวอาร์เรย์ของชนิดข้อมูล generic ได้
  • การทำ generic container ใน Rust ก็ยากที่จะเปลี่ยนพฤติกรรมแบบมีเงื่อนไขตามว่าชนิดข้อมูลที่รับมาเป็น enum หรือ struct
  • ใน Zig สามารถนึกภาพเป็นการเลือก EfficientEnumArray<T> หรือ EfficientStructArray<T> ตาม T.isEnum() ได้
  • การทำ AoVA ก็สามารถเลือกใช้ตามคุณสมบัติของ enum ได้เช่นกัน
    • ตัวอย่างเช่น อาจทำ specialization โดยตัดสินว่าการวาง variant ต่างชนิดรวมกันจะมีความหมายก็ต่อเมื่อลดจำนวนเวกเตอร์ได้เกิน 90% เท่านั้น
  • ถ้าทราบ capacity สูงสุดตั้งแต่คอมไพล์ ฟังก์ชันสร้างชนิดข้อมูลก็สามารถกำหนด bitwidth ที่จำเป็นสำหรับ tagged index ได้
  • หาก tagged index นี้ถูกบรรจุอยู่ในโครงสร้างข้อมูลอื่น เช่น enum อีกชั้นหนึ่ง ก็สามารถนำบิตที่เหลือไปใช้กับ discriminant ได้
  • Zig ระบุจำนวนบิตที่ต้องใช้ได้อย่างเจาะจง ทำให้ส่วนอื่นของโค้ดนำข้อมูลนี้ไปใช้ต่อได้อย่างเป็นธรรมชาติ เกิดเป็น ประสิทธิภาพด้านหน่วยความจำแบบ composable
  • ด้วย implicit widening integer coercion การใช้งาน API ที่มี bitwidth ต่างกันก็ยังสะดวก
  • หากเป็นภาษาสำหรับ system programming ที่ให้ความสำคัญกับประสิทธิภาพและ zero-cost abstraction ก็ควรกลับมาพิจารณา staged programming โดยเฉพาะ comptime ของ Zig อีกครั้ง

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

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

 
GN⁺ 2023-09-19
ความคิดเห็นจาก Hacker News

  • ยังมีกลยุทธ์อื่นที่มีประสิทธิภาพด้านการจัดเก็บดีและยังคงการวนผ่านองค์ประกอบไว้ได้ เวกเตอร์แรกเป็นรายการแท็ก เวกเตอร์ที่สองเป็น byte offset ของแต่ละองค์ประกอบ ส่วนตัวที่สามไม่เชิงเป็นเวกเตอร์ แต่เป็น ข้อมูล variant ที่ถูกแพ็ก ซึ่งเวกเตอร์ที่สองชี้ไปหา
    วิธีนี้ทำให้จำนวนเวกเตอร์เหลือครึ่งหนึ่งเมื่อเทียบกับทางออกสุดท้ายของผู้เขียน (6 ตัว vs 3 ตัว) ไม่เปลืองไบต์ padding เว้นแต่ในกรณีที่จำเป็นเพราะการจัดแนว และข้อมูลจะวางเรียงตามลำดับในหน่วยความจำโดยไม่ขึ้นกับชนิด ทำให้วนผ่านได้แบบเป็นมิตรต่อแคช นอกจากนี้ยังเข้าถึงองค์ประกอบด้วยดัชนีได้แบบ O(1) โดยรวมแล้วมีลักษณะด้านประสิทธิภาพคล้าย Vec สำหรับข้อมูลต่างชนิดกัน

    • การ เก็บ byte offset แบบ inline เป็นไอเดียที่ดี อย่างไรก็ดี เมื่อ offset ถูกเก็บในหน่วยความจำ กระบวนการวนผ่านจะเกิด data dependency ซึ่งแม้จะเป็นมิตรต่อแคช ก็อาจทำให้เกิดการติดขัดของหน่วยความจำอย่างรุนแรงใน pipeline ของโปรเซสเซอร์ได้
    • ถ้าต้องแก้ไข collection แบบนี้ ท้ายที่สุดก็มักมีแนวโน้มว่าจะต้องใช้ memory allocator เอง เพื่อจัดการการลบ การเปลี่ยนเป็น variant ที่ใหญ่กว่า และ fragmentation
    • หากไม่ปรับขนาดของ offset ให้เหมาะสม มันอาจกินพื้นที่ค่อนข้างมากเมื่อเทียบกับ T ขนาดเล็ก เช่น กรณีใช้ size_t 64 บิตคู่กับ uint8_t T และถ้าระวังแค่เรื่อง ขนาด offset ก็ดูเป็นแนวทางที่สมเหตุสมผล

  • สงสัยว่าโครงสร้างข้อมูล AoVA นี้ทำงานจริง ๆ อย่างไร จากมุมมองของอาร์เรย์ การคำนวณเลขคณิตของดัชนีอาจไม่มีความหมายอีกต่อไป แบบนี้ไม่ได้สูญเสีย การเข้าถึงแบบอิงดัชนี ไปหรือ? การวนผ่านก็ดูเหมือนไม่น่าจะรักษาลำดับการแทรกไว้ด้วย
    ในบริบทนี้ ผมคิดว่า TLV(tag-length-value) ซึ่งมีคุณสมบัติด้านแคชดีกว่า ถูกใช้กันบ่อยกว่า ความยาวอาจอนุมานได้จากแท็ก หรืออย่างน้อยก็ให้การวนไปข้างหน้าที่มีความหมาย ดู getdents, inotify, การส่งข้อความของ Netlink ได้

    • ถ้าดูคำบรรยายภาพของรูปที่ 4 ควรมองว่าแพตเทิร์น AoVA ไม่เหมาะนักในกรณีที่ต้องรักษาลำดับรวมทั้งหมดขององค์ประกอบที่แทรก
      เมื่อเทียบกับเลย์เอาต์ SoA ก่อนหน้า มันจะเกิดลำดับบางส่วน ไม่ใช่ลำดับรวม ตอนแทรกจะได้ดัชนีติดแท็กที่มีทั้ง enum tag และดัชนีภายในอาร์เรย์ของ variant นั้นกลับมา ดังนั้นการเข้าถึงแบบเรียงลำดับดูเหมือนจะอยู่นอกขอบเขตตรงนี้ ถ้าเก็บดัชนี global ไว้ในแต่ละองค์ประกอบ ก็อาจกู้การวนผ่านแบบเรียงลำดับกลับมาได้ แต่ก็ยังไม่ช่วยเรื่องการเข้าถึงแบบสุ่มที่เรียงลำดับอยู่ดี และโค้ดก็น่าจะมี branch ค่อนข้างมาก
    • “enum tag และดัชนีภายในอาร์เรย์ของ variant นั้น” ที่ได้กลับมาตอนแทรก โดยสาระแล้วก็คือ pointer ถ้าอยากวนผ่าน ก็เก็บ pointer ไว้ในอาร์เรย์ตามลำดับการใช้งานที่ต้องการได้เลย เหมือนกับสิ่งที่โปรแกรมที่จัดสรรหน่วยความจำบน heap ทำ
      วิธีจัดเก็บของตามขนาดยังถูกใช้ใน garbage collector และ allocator อเนกประสงค์ด้วย การที่รู้ขนาด object ที่เป็นไปได้ทั้งหมดอาจทำให้ได้ประสิทธิภาพ และยังอาจได้ประสิทธิภาพจากวิธีคืนหน่วยความจำที่เรียบง่ายกว่าแบบ arena ด้วย
    • การที่ AoVA ไม่มีลำดับรวมของตัวเองสำหรับดัชนี อาจเป็นปัญหาในบางกรณีใช้งาน แต่สำหรับ AST node ที่เสนอไว้ตรงนี้ ไม่จำเป็นต้องเป็นปัญหา
      ในกรณีแบบนี้ อาร์เรย์เหล่านี้อาจมองได้ว่าเป็นองค์ประกอบหนึ่งของโครงสร้างคล้าย heap หรือก็คือเหมือน arena ต้นทุนคือดัชนีต้องเป็น 2 มิติ เช่น (tag_idx, va_for_tag_idx) แต่จำนวนแท็กเป็นที่รู้ตอน compile time จึงสามารถ optimize การจัดเก็บได้โดยแพ็ก tag_idx ไว้ใน 4~5 บิตบน และให้ va_for_tag_idx ใช้บิตที่เหลือ อ้างอิง: https://www.cs.cornell.edu/~asampson/blog/flattening.html
    • การเขียนอาร์เรย์ที่เปลี่ยนชนิดของดัชนีน่าจะมีค่าใช้จ่ายสูงมหาศาล

  • ค่อนข้างเสียดายที่ pattern matching ของ Rust ไม่สามารถแสดงออกได้มากกว่านี้ในรูปแบบ trait ของ type system ที่ struct ใด ๆ ก็ทำตามได้ แทนที่จะเป็นชนิด object แบบ hard-code ระดับ first-class ที่ชัดเจนและมีโครงสร้างจัดเก็บของตัวเอง
    ช่วงหลังผมได้ implement AST คล้ายบทความนี้ และยังทำ interpreter สำหรับ opcode/bytecode ด้วย แต่รู้สึกว่า enum ของ Rust ไม่ได้เหมาะสมอย่างสมบูรณ์กับทั้งสองกรณี สำหรับ AST ผมอยากใส่แอตทริบิวต์เลขบรรทัด/คอลัมน์ให้กับ statement node ทุกตัว แต่ถ้าใส่บรรทัด/คอลัมน์ในทุกกรณีของ enum Stmt boilerplate ก็จะรก และถ้าห่อ enum ด้วย struct Stmt ใหม่ที่เก็บ enum เดิมพร้อมแอตทริบิวต์บรรทัด/คอลัมน์ ก็ต้อง refactor เยอะและไม่ค่อยสง่างาม ฝั่ง opcode เอง enum ของ Rust ที่ใช้ pattern matching ได้ก็ไม่ใช่ encoding ที่เหมาะที่สุดในแง่ประสิทธิภาพของ VM opcode interpreter แต่ภาษากลับชี้นำไปทางนี้ และความสามารถของรูปแบบ destructuring ก็น่าดึงดูดมาก ดูเหมือนยังมีพื้นที่ให้ปรับปรุง type system เพื่อให้ใช้ implementation ระดับต่ำตามที่ต้องการได้ พร้อมยังได้ความสามารถ pattern matching

    • ถ้ามีตัวอย่างที่เป็นรูปธรรมกว่านี้ก็คงดี สิ่งแรกที่นึกถึงคือ structural type system แบบหนึ่ง แต่ไม่แน่ใจว่าเข้าใจตรงกันแบบนั้นหรือไม่
      https://en.wikipedia.org/wiki/Structural_type_system
    • เทคนิคเก่าแก่ของ bytecode interpreter คือใช้ indirect jump เมื่อต้องไปยัง implementation ของ opcode ถัดไป ใน gcc เคยมี extension computed goto สำหรับเรื่องนี้ และถ้าเป็น Rust ก็น่าจะต้องมีอะไรสักอย่างที่บังคับใช้ function pointer และ tail-call optimization ได้
      ถ้าวาง indirect jump แบบนี้ไว้ตอนต้นของ implementation ของแต่ละ opcode ตัวทำนาย indirect jump ที่ CPU มีเพราะ OOP จะมีโมเดลแยกกันสำหรับส่วนท้ายของ opcode ต่าง ๆ ทำให้อัตราทำนายถูกสูงขึ้น ถึงแม้คำสั่งถัดไปเองจะทำนายยาก แต่เช่น หลัง test มีโอกาสตามด้วย branch สูงกว่ามาก อย่างไรก็ดี เทคนิคอื่น ๆ เช่นการเก็บยอดบนสุดของ stack ไว้ใน register ใน stack machine น่าจะสำคัญกว่า และก็ไม่แน่ใจว่าเทคนิคข้างต้นยังมีความหมายอยู่ในปัจจุบันหรือไม่
    • หลายภาษามีฟีเจอร์ที่คล้ายกับสิ่งที่ต้องการอยู่แล้ว ลองดู extractor ของ Scala หรือ active view ของ F#

  • ประโยคที่ว่า “clang AST ที่ parse แล้วกินหน่วยความจำเป็นประจำมากกว่าซอร์สโค้ดต้นฉบับ 50 เท่า” ดูเป็นเรื่องใหญ่ทีเดียว แต่บริบทที่ขาดไปคือ มันจะดีขึ้นได้มากแค่ไหน ถ้าต้องเก็บตำแหน่งในซอร์สของแต่ละโทเคน และต้องเข้ารหัสข้อมูลให้เพียงพอจนกู้คืนจาก AST ได้อย่างถูกต้อง อยากรู้ว่าอัตราการเพิ่มขึ้นในอุดมคติเมื่อเทียบกับต้นฉบับคือ 1.5 เท่า หรือ 15 เท่ากันแน่

    • ตัวอย่างเช่น ถ้าสามารถ ลดหน่วยความจำได้ 30% ก็ถือว่าเป็นข่าวค่อนข้างใหญ่ แต่ถ้าทำให้คอมไพเลอร์ดูแลรักษาต่อไปได้ยากขึ้นเพียงเพื่อลดได้แค่ 30% ก็อาจไม่คุ้มค่าเท่าไร ในทางกลับกัน ถ้ายอมทำให้คอมไพเลอร์หยาบขึ้นสักหน่อยแล้ว ลดได้ 80% ก็น่าลองทำ
      เป็นเรื่องยากที่จะบอกว่าอัตราการขยายจากซอร์ส→AST ในอุดมคติสำหรับภาษาที่เป็นมิตรทั้งกับผู้ใช้และนักพัฒนาคอมไพเลอร์ควรเป็นเท่าไร แต่ 50 เท่าก็ยังใช้งานได้อยู่ ในบทความต้นฉบับใช้การขยาย 50 เท่าเป็นแรงจูงใจในการทำให้การปรับแต่งเฉพาะอย่างหนึ่งเป็นอัตโนมัติ ถ้าเวกเตอร์ enum ของ Rust สามารถแยกค่า enum ออกเป็นแท็กกับค่าทึบแสงโดยอัตโนมัติ แล้วเก็บในรูปแบบ struct of arrays เหมือนที่บทความต้นฉบับทำใน Zig ได้ ก็น่าจะน่าสนใจ และดูเหมือนจะไม่มีที่ให้ซ่อนการใช้ unsafe มากนักด้วย
    • สำหรับตัวเปรียบเทียบ simdjson tape มีขนาดใหญ่กว่าเอกสารต้นฉบับประมาณ 3 เท่าเท่านั้น ส่วนสำคัญจำนวนมากของค่านี้อาจลดได้ หากใส่ตัวเลขไว้ใน tape slot เพียงช่องเดียว หรืออ้างอิงตำแหน่งในเอกสารต้นฉบับสำหรับสตริงที่ไม่มี escape sequence โดยไม่ต้องคัดลอก
      ในเอกสารที่ส่วนใหญ่เป็นอักขระ [] หรืออักขระ 0, ดูเหมือน overhead สูงสุดจะอยู่ราว 8 เท่า
    • ซอร์สโค้ดมีความหนาแน่นอย่างน่าประหลาดใจ ข้อมูลหนึ่งที่บอกได้ว่ามันจะดีขึ้นได้ถึงไหน คือผลที่ parser ของ Zig เอง parse parser ของ Zig เอง
      ไบต์ของซอร์ส: 139 KiB, โทเคน: 24646 รายการ (120 KiB), โหนด AST: 10998 รายการ (140 KiB) โทเคนแต่ละตัวถูกทำให้เล็กมากที่ 5 ไบต์ (แท็ก 1 ไบต์ + file offset 4 ไบต์) และโหนด AST ก็ถูกเข้ารหัสอย่างหนาแน่นและไม่สม่ำเสมอ โดยในกรณีนี้อยู่ที่ประมาณ 13 ไบต์ต่อโหนด แม้จะเป็นการเข้ารหัสขั้นต่ำแบบนี้ parse tree ก็ยังมีขนาดเกือบ 2 เท่าของไฟล์ซอร์ส แต่ถึงอย่างนั้น 2 เท่าก็ดีกว่า 50 เท่ามาก ที่มา: zig ast-check -t lib/std/zig/Parse.zig | head -n7
    • แนะนำให้ดูงานนำเสนอที่ลิงก์ไว้เลยดีกว่า เป็นงานนำเสนอที่ยอดเยี่ยม เท่าที่จำได้เหมือนจะไม่ได้ให้ตัวเลขที่แน่นอน และอาจยังเป็นช่วงที่เร็วเกินไปจะมั่นใจได้ อาจมีข้อมูลที่ยังไม่รู้ว่าจำเป็นต้องมีตกหล่นอยู่ ทำให้ตัวเลขออกมาต่ำก็ได้

  • พื้นที่ปัญหานี้ให้ความรู้สึกเหมือนเป็นรูปแบบหนึ่งของ packing problem
    คงจะดีถ้าสามารถเริ่มจากโครงสร้างสุดท้ายที่มนุษย์จัดการได้ง่าย แล้วสร้างคำแนะนำโครงสร้างข้อมูลที่ลดการสิ้นเปลืองหน่วยความจำ เคารพกฎการจัดแนว และเพิ่ม locality ของพื้นที่ได้ https://en.wikipedia.org/wiki/Packing_problems

  • อยากให้ proc macro พัฒนาไปจนสอบถามข้อมูลจากคอมไพเลอร์ได้ ถึงจะต้องออกแบบอย่างระมัดระวังเกี่ยวกับการเพิ่มขั้นตอนคอมไพล์ก็ตาม แต่สิ่งอย่าง “struct นี้ implement trait นี้หรือไม่”, “ขอรายการ trait ทั้งหมดที่ implement แบบเป็นรูปธรรม” มักมีประโยชน์มากใน proc macro

    • ถ้าจำไม่ผิด คอมไพเลอร์รันปลั๊กอินเป็นสองขั้นตอน ขั้นแรกได้รับ AST ก่อน type checking และสามารถแก้ไข AST ได้ โดย macro และ clippy lint บางส่วนรันตรงนี้ ขั้นที่สองอยู่ หลัง type checking จึงได้รับข้อมูลชนิด แต่แก้ไขไม่ได้ และ clippy lint อื่น ๆ รันตรงนี้

  • ผมเข้าใจบทความแค่บางส่วน แต่ในฐานะคนที่กำลังจะเขียน spreadsheet engine ด้วย Rust ดูเหมือนจะเกี่ยวข้องมาก ค่าในเซลล์ต้องมีรูปแบบแบบนี้
    pub enum Expr { Number(i32), String(String), Reference(Position), Binary(Box, char, Box), Function(String, Vec), }
    ตั้งใจว่าจะอ่านและศึกษาไปเรื่อย ๆ และยินดีรับเอกสารอ้างอิงถ้ามี

    • ปัญหาที่เน้นตรงนี้คือ variant มีขนาดต่างกันมาก และถ้ามีค่าพวกนี้จำนวนมากในอาร์เรย์ ประสิทธิภาพจะแย่ลงเพราะ พื้นที่ที่เสียไปกับ padding
      เทคนิคทั่วไปจากฝั่งเกมคือแยก array of structs (AoS) ออกเป็น struct of arrays (SoA) เช่นถ้าเขียนเป็น struct Humans { healths: Vec, ammo: Vec, … } ดัชนีที่ i ของแต่ละเวกเตอร์ก็จะเป็น Human ตัวที่ i ใน layout แบบ AoS เวกเตอร์ขนานแบบนี้เป็นเพียงตัวอย่าง ไม่ใช่ประสิทธิภาพที่ดีที่สุด เพราะเสียพื้นที่จากการทำบัญชีความยาวและความจุซ้ำในแต่ละฟิลด์ โดยพื้นฐานแล้วบทความนี้พยายามนำแนวคิดคล้ายกันมาใช้กับ enum แบบอัตโนมัติ และใน Rust ทำตรง ๆ ได้ยาก ปัญหานี้ใหญ่จริงแค่ไหนอาจถูกพูดเกินไปบ้าง สำหรับ spreadsheet ควรเก็บไว้ในใจเป็นการปรับแต่งที่อาจทำได้ก่อน และต้องตัดสินใจก่อนว่ากำลังทำเพื่อความเร็ว หรือเพื่อความเรียบง่ายและความเข้าใจง่าย
    • ดูเป็นโปรเจกต์ที่น่าสนุก ถ้ามุ่งเป้าไปที่ผู้ใช้ทั่วไป ควรคาดไว้เลยว่าผู้ใช้จะใส่เนื้อหาไว้ที่ มุมสุดโต่งทั้งสี่ของชีต แล้วดูว่าเอนจินจะล้มหรือไม่
      ถ้าอนุญาต 1 ล้าน × 1 ล้านเซลล์ แล้วเก็บ null ในทุกเซลล์ที่ยังไม่ถูกเติม หน่วยความจำจะหมด ดังนั้นอาจพิจารณาวิธีเก็บเนื้อหาเซลล์แบบ sparse วิธีหนึ่งคือใช้ implementation ของ hash map อย่าง hashbrown ประเด็นของบทความนี้เป็นรายละเอียดระดับต่ำ ถ้าเริ่มจาก hash map ตั้งแต่แรกเพื่อหลีกเลี่ยงข้อจำกัดหน่วยความจำช่วงต้น ก็ยังไม่จำเป็นต้องคิดลึกเรื่องนี้ในตอนนี้
    • จริง ๆ เคยทำ spreadsheet engine ด้วย Rust มาก่อน แม้จะไม่ใช่โอเพนซอร์ส แต่ให้คำแนะนำได้บางอย่าง คุณจะเจอปัญหาประสิทธิภาพอีกมากก่อนจะได้ประโยชน์จากวิธีในบทความนี้
      ปัญหาเดี่ยวที่ยากที่สุดคือ กลยุทธ์การประเมินผล

  • https://doc.rust-lang.org/reference/type-layout.html#the-alignment-modifiers เป็นอย่างไรบ้าง

  • ดูเหมือนว่าโค้ดตัวอย่างจะมีบั๊ก
    field_map[idx] = svec.len - 1;
    ถ้า svec มี size อยู่ในตำแหน่งที่ไม่ใช่ entry สุดท้ายอยู่แล้ว ก็น่าจะผิด