- หากไม่เก็บ AST เป็นกราฟของอ็อบเจ็กต์ที่เชื่อมกันด้วยพอยน์เตอร์ แต่แทนด้วย อาร์เรย์เดียวและดัชนี จะทำให้การจัดวางหน่วยความจำและการจัดการโครงสร้างข้อมูลแบบคอมไพเลอร์เรียบง่ายขึ้น
- ตัวอย่าง Rust แสดงการทำ AST แบบแบนราบด้วยการเปลี่ยน
Box<Expr> เป็น ExprRef และเพิ่ม add/get ให้กับ ExprPool ซึ่งเป็นการเปลี่ยนแปลงเพียงเล็กน้อย
- ในไมโครบेंช์มาร์กที่สร้าง โหนด AST ราว 100 ล้านโหนด แล้วตีความทันที เวอร์ชันปกติใช้เวลา 3.1 วินาที ส่วนเวอร์ชันแบบแบนราบใช้เวลา 1.3 วินาที จึง เร็วขึ้น 2.4×
- ความต่างด้านประสิทธิภาพมาจาก locality ที่ดีขึ้นจากการจัดหน่วยความจำแบบต่อเนื่อง, การใช้ดัชนี 32 บิตแทนพอยน์เตอร์ 64 บิตซึ่งทำให้รีเฟอเรนซ์เล็กลง, การจัดสรรที่ถูกกว่า และการคืนหน่วยความจำแบบยกทั้งพูล
- หากอาศัยคุณสมบัติที่ว่าในอาร์เรย์ โหนดลูกจะอยู่ก่อนโหนดพ่อเสมอ การเดินต้นไม้แบบรีเคอร์ซีฟจะเปลี่ยนเป็นการรันเชิงเส้นได้ และนำไปสู่รูปแบบที่ใกล้กับ bytecode interpreter
แนวคิดพื้นฐานของการทำให้แบนราบ
- Arena หรือ region เป็นเทคนิคที่ใช้กันแพร่หลายในระบบภาษาโปรแกรมสมัยใหม่ และวิธีที่กล่าวถึงที่นี่คือการใช้ arena ที่เก็บข้อมูลเพียงชนิดเดียวให้เหมือนอาร์เรย์ธรรมดา หรือก็คือ การทำโครงสร้างข้อมูลให้แบนราบ
- นี่คือเทคนิคที่เปลี่ยนพอยน์เตอร์ในโครงสร้างข้อมูลที่มีพอยน์เตอร์จำนวนมากให้กลายเป็นดัชนีของอาร์เรย์ โดยตัวอย่างหลักคือ AST แต่ยังใช้กับโครงสร้างข้อมูลอื่นในคอมไพเลอร์ได้เช่นกัน
- โค้ดตัวอย่างอยู่ใน คลัง flatcalc และดูความต่างระหว่างเวอร์ชันปกติกับเวอร์ชันแบบแบนราบได้จาก การเทียบสาขา
- แม้การเปลี่ยนโค้ดจะมีไม่มาก แต่ในไมโครบेंช์มาร์กกลับได้ ความเร็วเพิ่มขึ้น 2.4× และนอกจากเรื่องประสิทธิภาพแล้ว ยังมีข้อดีด้านการใช้งานของโค้ดอีกด้วย
การแทน AST แบบทั่วไป
- ภาษาตัวอย่างเป็นภาษานิพจน์เลขคณิตที่เรียบง่ายมาก รองรับเพียงลิเทอรัลจำนวนเต็มและตัวดำเนินการเลขคณิตแบบทวิภาคี 4 ชนิด
- ตัวอย่างโปรแกรมที่เป็นไปได้ เช่น
42, 0 + 14 * 3, (100 - 16) / 2
- การแทนใน Rust ประกอบด้วย enum
BinOp และ Expr
Expr::Binary(BinOp, Box<Expr>, Box<Expr>)Expr::Literal(i64)
Box<Expr> ใน Rust เทียบได้กับพอยน์เตอร์ที่ชี้ไปยัง Expr และมีบทบาทคล้าย Expr* ในภาษา C- parser, ตัวจัดรูปแบบการแสดงผล และ interpreter มีโครงสร้างแบบมาตรฐาน โดย interpreter เขียนเป็นเมธอดแบบรีเคอร์ซีฟบน
Expr
- ความหมายเชิงเลขคณิตถูกกำหนดให้ทุกนิพจน์ประเมินค่าออกมาเป็น
i64
- การบวก·ลบ·คูณ ใช้การคำนวณแบบ wrapping
- การหารด้วย 0 ใช้
checked_div แล้วให้คืนค่า 0
- มีตัวสร้างโปรแกรมสุ่มที่ใช้ PRNG seed คงที่ เพื่อวัด ประสิทธิภาพในการจัดการ AST โดยไม่รวมต้นทุนจาก parser และการพิมพ์ผล
การเปลี่ยน AST ให้เป็นอาร์เรย์และดัชนี
- การทำให้แบนราบประกอบด้วยการเปลี่ยนหลัก 2 อย่าง
- ไม่จัดสรร
Expr แต่ละตัวบนฮีปแยกกัน แต่เก็บไว้ในอาร์เรย์ต่อเนื่องเพียงชุดเดียว
- ให้โหนดลูกอ้างอิงกันด้วย ดัชนี ในอาร์เรย์แทนพอยน์เตอร์
- ในตัวอย่าง Rust มีการนิยาม
ExprPool เป็น newtype ของ Vec<Expr>
struct ExprPool(Vec<Expr>);
- ส่วนที่เคยทำหน้าที่เป็นพอยน์เตอร์ ถูกแทนด้วย
ExprRef ที่อิงจำนวนเต็ม 32 บิต
struct ExprRef(u32);
- การเปลี่ยนชนิดข้อมูลหลักคือเปลี่ยนฟิลด์ลูกของ
Binary จาก Box<Expr> เป็น ExprRef
enum Expr {
Binary(BinOp, ExprRef, ExprRef),
Literal(i64),
}
ExprPool จะมียูทิลิตี add สำหรับเพิ่ม Expr ใหม่ และ get สำหรับค้นหา Expr จาก ExprRef- parser จะไม่คืนค่า
Expr โดยตรงอีกต่อไป แต่จะเพิ่มโหนดลงใน ExprPool แล้วคืนค่า ExprRef แทน
- interpreter ก็เปลี่ยนจากการเป็นเมธอดของ
Expr ไปเป็นเมธอดของ ExprPool และก่อน pattern matching จะอ้างกลับด้วย self.get(expr)
- โดยรวมแล้ว การเปลี่ยนแปลงทั้งระบบมีเพียงการแทน
Box<Expr> ด้วย ExprRef และใส่ add กับ get ในจุดที่จำเป็น
ข้อดีด้านประสิทธิภาพ
- ข้อดีเด่นของ AST แบบแบนราบคือ memory locality
Expr แบบพอยน์เตอร์ทั่วไปมีความเสี่ยงต่อการกระจัดกระจายของหน่วยความจำExpr แบบแบนราบจะกระจุกอยู่ในพื้นที่หน่วยความจำต่อเนื่อง ทำให้ data cache และ prefetcher ทำงานได้ดีขึ้น- ตัวจัดสรรหน่วยความจำที่ฉลาดพออาจให้ผลคล้ายกันได้ แต่การใช้อาร์เรย์ที่หนาแน่นช่วยลดความไม่แน่นอนลง
- ขนาดของรีเฟอเรนซ์ก็เล็กลงด้วย
- พอยน์เตอร์ทั่วไปบนสถาปัตยกรรมสมัยใหม่มีขนาด 64 บิต
- หากต้องการโหนด AST ไม่เกิน 4,294,967,295 โหนด รีเฟอเรนซ์ 32 บิตก็เพียงพอ
- ประหยัดพื้นที่ได้ 50% ต่อหนึ่งรีเฟอเรนซ์ และใน AST ที่มีพอยน์เตอร์มาก ก็อาจลดการใช้หน่วยความจำโดยรวมได้
- หากเป็นโครงสร้างข้อมูลที่เล็กกว่า อาจใช้รีเฟอเรนซ์ 16 บิตหรือ 8 บิตได้ด้วย
- ต้นทุนการจัดสรรต่ำลง
- ไม่ต้องเรียก
malloc สำหรับทุกโหนด
- หากจองหน่วยความจำไว้ล่วงหน้าเพียงพอ ก็สามารถสร้างพื้นที่สำหรับ
Expr ใหม่ได้ด้วย bump allocation ที่เพียงแค่ขยับ tail pointer
- การคืนหน่วยความจำทำได้เป็นระดับพูล
- แนวทางนี้ตั้งอยู่บนสมมติฐานว่าไม่จำเป็นต้องคืน
Expr ทีละตัว
- ในระบบภาษาจำนวนมาก AST มักถูกสร้างพร้อมกันและหมดอายุพร้อมกัน
- AST แบบทั่วไปต้องไล่ตามพอยน์เตอร์ไปคืนหน่วยความจำทุกโหนด แต่ AST แบบแบนราบสามารถคืนทั้ง
ExprPool ได้ครั้งเดียว
- เวลาพูดถึง arena allocation มักเน้นว่าข้อดีหลักคือการคืนหน่วยความจำที่ถูก แต่ในบริบทของคอมไพเลอร์ AST อาจอยู่จนจบกระบวนการคอมไพล์ ทำให้เรื่องการคืนหน่วยความจำอาจเป็นเหตุผลที่สำคัญน้อยที่สุดก็ได้
ข้อดีด้านการใช้งานของโค้ด
- การทำให้แบนราบช่วยให้ การจัดการอายุการใช้งาน ง่ายขึ้น
- AST ที่มี n โหนดสามารถมองเป็นอายุการใช้งานเดียวของ AST แทน n อายุการใช้งานของแต่ละโหนด
- ใน Rust ความง่ายนี้ส่งผลโดยตรงต่อการเขียน lifetime ในโค้ด
- แทนที่จะต้องจัดการ lifetime ของ
&Expr ก็สามารถส่ง ExprRef ซึ่งเป็น u32 แล้วพึ่งอายุการใช้งานของ ExprPool ได้
- ความเรียบง่ายแบบเดียวกันนี้ยังใช้ได้กับภาษาอย่าง C++ ที่ต้องจัดการหน่วยความจำด้วยตนเอง
- อาร์เรย์แบบแบนราบยังทำให้ การตัดข้อมูลซ้ำ ทำได้สะดวก
- จะใช้
hash consing หรือวิธีที่ง่ายกว่านั้นเพื่อหลีกเลี่ยงการสร้างนิพจน์ซ้ำก็ได้
- ตัวอย่างเช่น สามารถจอง 128 ช่องแรกของ
ExprPool ไว้ให้ Literal ที่ใช้บ่อยตั้งแต่ 0 ถึง 127
- เมื่อต้องการลิเทอรัลจำนวนเต็ม
42 ก็ไม่ต้องสร้าง Expr ใหม่ แต่คืน ExprRef(42) ได้เลย
- การทำแบบคล้ายกันนี้ก็เป็นไปได้ในโครงสร้างที่ใช้พอยน์เตอร์เช่นกัน แต่มีแนวโน้มว่าจะต้องใช้องค์ประกอบข้อมูลเสริมเพิ่มเติม
ผลของไมโครบेंช์มาร์ก
- เบนช์มาร์กนี้สร้างโปรแกรมสุ่มที่มี โหนด AST ราว 100 ล้านโหนด แล้วป้อนให้ interpreter ทันที
- ไม่รวม parser และตัวจัดรูปแบบการแสดงผล
- เป็นการสร้างโปรแกรมหนึ่งชุดแล้วรันทันที จึงไม่ใช่เบนช์มาร์กที่สมจริงนัก
- เงื่อนไขการทดลองมีข้อจำกัดอยู่หลายอย่าง
- มีการจองพื้นที่ใน
Vec<Expr> ล่วงหน้าให้พอสำหรับเก็บทั้งโปรแกรม
- ในการใช้งานจริงอาจต้องประเมินขนาด arena เพิ่มเติม
- งานที่ทำมีแทบแค่การสร้างและการรัน ทำให้ข้อดีของการจัดสรรและคืนหน่วยความจำที่ถูกอาจถูกขยายให้เด่นเกินจริง
- โปรแกรมมีขนาดใหญ่มากจนสัดส่วนที่อยู่ใน CPU cache มีน้อย จึงอาจทำให้ผลของ locality ถูกประเมินต่ำเกินไป
- มีการใช้ Hyperfine เปรียบเทียบค่าเฉลี่ยจากการรัน 10 ครั้งบนโน้ตบุ๊ก
- สภาพแวดล้อมคือ M1 Max 10-core 3.2GHz, หน่วยความจำ 32GB, macOS 13.3.1, Rust 1.69.0
- เวอร์ชันปกติใช้เวลา 3.1 วินาที ส่วนเวอร์ชันแบบแบนราบใช้เวลา 1.3 วินาที จึงได้ ความเร็วเพิ่มขึ้น 2.4×
- เพื่อดูต้นทุนการคืนหน่วยความจำแยกต่างหาก จึงมีการทำเวอร์ชันที่ข้าม deallocation ทั้งสองฝั่ง
- ฝั่งแบบแบนราบ เวลาของเวอร์ชัน no-free กับเวอร์ชันมาตรฐานแทบไม่ต่างกัน แปลว่าต้นทุนการคืนหน่วยความจำไม่สูงนัก
- ฝั่งปกติ เวลาลดจาก 3.1 วินาทีเหลือ 1.9 วินาที หมายความว่ามีเวลาราว 38% ถูกใช้ไปกับการคืนหน่วยความจำ
- แม้เทียบกันเฉพาะเวอร์ชัน no-free แบบแบนราบก็ยัง เร็วกว่า 1.5×
interpreter ที่ใช้คุณสมบัติของรูปแบบแบนราบโดยตรง
- ตอนแรกการทำให้แบนราบถูกใช้เหมือนเป็นเพียงการเปลี่ยน implementation ภายในเพื่อแทนการจัดสรรทั่วไปและพอยน์เตอร์ แต่จริง ๆ แล้วเรายังใช้คุณสมบัติของการแทนแบบอาร์เรย์ได้โดยตรง
- หาก
Expr ไม่เปลี่ยนแปลง ก็ต้องสร้างโหนดลูกก่อน แล้วค่อยสร้างโหนดพ่อทีหลัง
- เมื่อต้องสร้าง
a * b ตัว a และ b จะอยู่ก่อน * ใน ExprPool
- ลูกศรของการอ้างอิงจึงชี้ย้อนจากท้ายอาร์เรย์ไปยังต้นอาร์เรย์เสมอ ขณะที่การไหลของข้อมูลเดินหน้าไปข้างหน้า
- ด้วยอินวาเรียนต์นี้ เราสามารถสร้าง interpreter ที่ไม่ต้องไล่ลงแบบรีเคอร์ซีฟจากราก แต่สแกน
ExprPool ตั้งแต่ต้นจนจบแทนได้
- การเดินจะเยี่ยมชมลูกก่อนพ่อเสมอ
- ผลลัพธ์ของแต่ละนิพจน์จะถูกเก็บไว้ในเวกเตอร์
state
- นิพจน์แบบทวิภาคีจะไปอ่านค่าจาก
state ด้วยดัชนี ExprRef ของลูก
- สุดท้ายจะคืนค่าผลลัพธ์ที่ตรงกับ
root ที่ร้องขอ
- interpreter แบบ “extra-flat” นี้ไม่มีภาระจากการจัดการสแตกของการเรียกรีเคอร์ซีฟ และสามารถเดิน
ExprPool แบบเชิงเส้นได้
- ในทางกลับกัน มันอาจเสียเปรียบด้าน locality เพราะต้องเข้าถึงเวกเตอร์
state ขนาดใหญ่แบบสุ่ม
- ผลคือ interpreter แบบ extra-flat ใช้เวลา 1.2 วินาที ส่วน interpreter แบบแบนราบที่ยังใช้รีเคอร์ชันใช้เวลา 1.3 วินาที จึง ดีขึ้น 8.2%
ความเชื่อมโยงกับ bytecode interpreter
- ความเห็นของ Bob Nystrom บน Reddit มองว่าวิธีนี้แท้จริงแล้วคือการค้นพบแนวคิดของ bytecode interpreter ขึ้นมาอีกครั้ง
- โครงสร้าง
Expr ทำงานคล้ายคำสั่ง bytecode และการอ้างอิงตัวแปรก็ถูกเข้ารหัสเป็นรีเฟอเรนซ์แบบ u32
- หากเปลี่ยนตาราง
state แบบง่าย ๆ ให้กลายเป็นโครงสร้างคล้ายสแตก ก็แทบไม่ต่างจาก bytecode interpreter ที่ถูกออกแบบมาตั้งแต่ต้น
- เพียงแค่เปลี่ยนโครงสร้างข้อมูลของ AST ก็ทำให้แนวทางการประมวลผลเลื่อนจากการเดินต้นไม้ไปสู่รูปแบบแบบ bytecode ได้อย่างเป็นธรรมชาติ
แหล่งข้อมูลที่เกี่ยวข้อง
- แหล่งข้อมูลเกี่ยวกับการทำให้แบนราบในบริบทของคอมไพเลอร์
- แนวคิดคล้ายกันนี้ยังปรากฏในงานสายประสิทธิภาพนอกเหนือจากระบบภาษาโปรแกรม
- บทความภาษา Rust สำหรับภาษาคำนวณของเล่น ของ Inanna Malick ก็ใช้เทคนิคเดียวกัน และยังผสานแนวคิด recursion scheme จากโลกของ Haskell ด้วย
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
Blender (ซอฟต์แวร์ทำโมเดล 3D) เป็นกรณีตัวอย่างที่น่าสนใจของแนวทางนี้ เพื่อให้การโหลด/บันทึกไฟล์รวดเร็วและไม่สูญเสียข้อมูล จึงใช้ รูปแบบบนดิสก์และรูปแบบในหน่วยความจำ ให้เหมือนกัน
กล่าวคือทุกอย่างอยู่ใน arena และการบันทึก/โหลดก็แทบจะเหมือน
memcpyทั้ง arena เลย เมื่อคิดถึงความซับซ้อนที่อาจเกิดขึ้นของโปรเจกต์ Blender และปัญหา serialization/deserialization แล้ว นี่ดูเป็นการออกแบบที่ยอดเยี่ยมข้อเสียคือเพราะต้องสามารถเปิดไฟล์จากเวอร์ชันเก่าได้ด้วย จึงทำให้ การออกแบบโครงสร้างข้อมูลมีแนวโน้มจะถูกตรึงตายตัว
ให้รันการแปลงแบบนี้เฉพาะตอนโหลดข้อมูลจากแอปเวอร์ชันเก่า และหลังจากนั้นก็บันทึกลงดิสก์เป็นเวอร์ชันที่อัปเดตแล้วทันที จะได้ไม่ต้องเสียต้นทุนเดิมซ้ำอีก
https://www.inkandswitch.com/cambria/ ที่สร้างขึ้นในบริบทของ CRDT เป็นตัวอย่างการนำแนวคิดนี้ไปใช้จริง และถึงจะนำมาใช้ตรง ๆ ไม่ได้ ก็ยังเป็นแรงบันดาลใจที่ดีได้
ไม่ว่าจะชอบหรือไม่ เฟรมเวิร์ก I/O ก็ serialize โครงสร้างแบบ dump struct ตรง ๆ อยู่ดี จึงต้องออกแบบโครงสร้างข้อมูลเผื่ออนาคตตลอดเวลาเพราะรู้ว่าจะต้องถูกผูกติดกับโครงสร้างนั้นไปตลอด มันเป็นยุคมืดจริง ๆ
เลยทำให้การเขียนตัวแปลงเป็นปัญหาใหญ่ และเท่าที่จำได้คือต้องถอดรหัสโครงสร้างข้อมูลภายในของ Word ที่ไม่เคยมีเอกสารอธิบายไว้
ถ้าใครแก้ไฟล์บนดิสก์ได้ ก็แปลว่าเขายึดเครื่องได้ไปแล้ว โหลดเลยเร็วแบบเหลือเชื่อ โดยอ่านทุกอย่างเข้าเมมโมรีก่อน แล้วค่อยแพตช์ตำแหน่ง pointer ให้ชี้ไปยัง address ที่โหลดจริง
ชอบ flattened abstract syntax tree มาก โดยเฉพาะวิธีที่ใช้กับการประมวลผล inline markup ของ pulldown-cmark มีคำอธิบายสั้น ๆ ที่ https://fullyfaithful.eu/pulldown-cmark/
อินพุตดิบจะถูกแยกเป็นลำดับของโหนด และสิ่งอย่าง
*อาจกลายเป็นการเน้นข้อความ หรือถ้าไม่มีคู่ก็อาจคงเป็นข้อความธรรมดา จึงถูกเก็บเป็นโหนดMaybeEmphasisในขั้นถัดไปจะใช้สแตกไล่ดูโหนดตามลำดับเพื่อหาคู่ที่เป็นไปได้ เมื่อเจอคู่แล้วก็เปลี่ยนโหนด
MaybeEmphasisให้เป็นโหนดเน้นข้อความที่เหมาะสม และตัดลำดับโหนดทั้งหมดระหว่างโหนดเปิดกับโหนดปิดออกมาเป็น subtree ของโหนดใหม่การแปลงต้นไม้แบบนี้ค่อนข้างแปลก ทำให้การอิมพลีเมนต์แบบตรงไปตรงมามีโอกาสกลายเป็น O(n) ได้ง่าย แต่ใน representation แบบ flattened AST จะทำได้ใน O(1) โดยไม่ขึ้นกับจำนวนโหนดหรือความลึกของสแตก
รายละเอียดของ representation ของต้นไม้อยู่ที่ https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6... ซึ่งโดยพื้นฐานแล้วเก็บดัชนี
child,nextไว้คู่กับตัวเนื้อหาโหนด ส่วนโค้ด tree surgery ตอนจับคู่ emphasis อยู่ที่ https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6...ประสิทธิภาพยอดเยี่ยมมาก pulldown-cmark อาจไม่ใช่ CommonMark parser ที่เร็วที่สุดเพียงตัวเดียว แต่ก็แข่งขันได้สบาย และเร็วกว่าแนวทางที่ต้อง allocate ต่อหนึ่งโหนดอย่างมาก
ทำให้นึกถึงงานพูดใน GDC ที่ชื่นชม Rust เนื้อหาคือ Rust ทำให้คุณแทบคลั่งเพราะ borrow checker ไม่ก็ทำให้ต้องจัดโครงสร้างโค้ดแบบ entity component system
สิ่งที่น่าสนใจคือ ในกรณีจริงที่มีปัญหาเรื่อง lifetime ซับซ้อน คุณค่าของ borrow checker กลับอยู่ที่การทำให้สุดท้ายคุณมองหาวิธีเอาทุกอย่างใส่ไว้ในอาร์เรย์แล้วอ้างอิงด้วยดัชนี เพื่อหลีกเลี่ยง borrow checker ให้มากที่สุด
พอวัตถุไม่อ้างอิงกันโดยตรง ประโยชน์ของ type system ก็ลดลงมาก และทำให้อนุมานโค้ดได้ยากมาก ฉันเชื่อว่ามันอาจมีประโยชน์กับระบบขนาดใหญ่มาก แต่กับโปรแกรมเล็ก ๆ ที่ฉันเขียนมันแทบจะเป็นอุปสรรคมากกว่า
ซึ่งรวมถึงเกม ฐานข้อมูล ระบบฝังตัว งานแบตช์แบบ high-performance computing และแม้แต่คอมไพเลอร์
แน่นอนว่ายังมีข้อจำกัดเรื่อง aliasing อยู่ จึงไม่เกิด data race แต่บั๊กที่โดยแก่นแล้วเหมือนกับบั๊กจาก raw pointer ก็ยังเกิดขึ้นได้อยู่ดี
ในกระบวนการนี้ ฝั่งที่ยืมจะต้องมีอายุสั้นกว่าเจ้าของเสมอ และเข้าถึงได้เฉพาะหน่วยความจำที่ถูกจัดสรรไว้ระหว่างการเป็นเจ้าของเท่านั้น เมื่อเจ้าของตายก็จะถูกคืนหน่วยความจำ และหลังจากนั้นไม่มีใครใช้งานหรือคืนซ้ำได้ จึงหลีกเลี่ยง use-after-free, การ free ซ้ำ และการเข้าถึงหน่วยความจำที่ไม่ได้จัดสรรได้
ยังมีข้ออ้างแปลก ๆ ด้วยว่า arena ใน C ช่วยแก้ปัญหา memory safety ทั้งที่สำหรับบางโปรแกรมมันก็มีโอกาสทำให้เกิด dangling pointer หรือ use-after-free ได้พอ ๆ กัน
ปัญหาเดียวกันนี้ปรากฏทั้งใน C/C++ และ Rust เพียงแต่ในรูปแบบที่ต่างกันเล็กน้อย
คอมเมนต์ที่ฉันเคยฝากไว้กับบทความนี้เมื่อสองเดือนก่อน: https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
สรุปคือ ข้อดีมีความเป็นจริงมาก แต่ก็ควรพูดถึงข้อเสียด้วย arena ทำให้ความปลอดภัยของหน่วยความจำถูกเลื่อนออกไป เรื่อง ownership อาจยุ่งยากขึ้น การแก้ไขและการเพิ่มรายการ/เวกเตอร์ก็ซับซ้อนขึ้น และการแทนแบบ pointer ก็เป็นมิตรกับดีบักเกอร์มากกว่า
ด้านล่างบทความนี้มีลิงก์ไปยังหน้า wiki ของฉัน ซึ่งมีทั้งโค้ดจริงและค่าที่วัดได้ เลยอ่านด้วยความขอบคุณ: https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
Prolog term ก็ถูกแทนบน heap แบบนี้ใน Warren Abstract Machine (WAM) เช่นกัน ถ้าเขียน Prolog term อย่าง
+(*(a,b), c)ในรูปแบบตัวดำเนินการเหมือนในตัวอย่างของบทความ ก็จะได้แบบนี้expr(E) :- E = a*b + c.จากนั้นจะมีการสร้าง representation แบบ flattened บน global stack ของ virtual machine ใน Scryer Prolog สามารถดูคำสั่ง WAM ได้ด้วย
?- wam_instructions(expr/1, Is), maplist(portray_clause, Is).ผลลัพธ์จะออกมาประมาณ
put_structure(*,2,x(3)).,set_constant(a).,set_constant(b).,put_structure(+,2,x(2)).,set_value(x(3)).,set_constant(c).,execute(=,2).โดยทั้งสอง compound term จะถูกทำให้เป็นเชิงเส้น และถูกวางบน heap ในรูปแบบที่ตามหลัง functor จะเป็นอาร์กิวเมนต์ต่อเนื่องกัน แต่ละตัวกินพื้นที่ หนึ่ง memory cell ของ WAM พอดี และอาร์กิวเมนต์สามารถชี้ไปยัง memory cell อื่นได้
heap คืออาร์เรย์ของ cell เหล่านี้ และทุก cell มี concrete type แบบเดียวกัน ตัวอย่างเช่น Scryer Prolog ใช้ 8 ไบต์ต่อ cell ทำให้การเข้าถึงและแก้ไข cell มีประสิทธิภาพมากบนสถาปัตยกรรม 64 บิต
การ "แทนที่จะจอง
Exprobject กระจายเต็ม heap ก็เอามาใส่ในอาร์เรย์ต่อเนื่องก้อนเดียว แล้วให้ลูกอ้างถึงกันด้วยดัชนีแทน pointer" นั้นใกล้เคียงกับการเปลี่ยนรูปแบบการแทน heap มากกว่าจะเป็น flattening จริง ๆ เพราะรูปร่างของ AST เองไม่ได้เปลี่ยนไปหลายภาษาก็ทำแบบนี้กันมานานแล้ว เช่นในตระกูล Lisp ที่เอา cons cell และ object อื่น ๆ ไว้ในอาร์เรย์ แล้วใช้ bump allocation กับ index pointer
เมื่อ object อยู่ในอาร์เรย์ ตัว garbage collector ก็จะเดินในช่วง sweep ได้ง่ายหลังจบขั้น mark โดยขั้น mark คือการเดินกราฟเพื่อหา object ที่ยังเข้าถึงได้ ส่วนขั้น sweep คือการไล่ผ่านอาร์เรย์แบบแบนเพื่อล้าง GC bit และทำเครื่องหมาย object ที่เข้าถึงไม่ได้ให้พร้อมนำกลับมาใช้ใหม่
คงหา implementation ของ Lisp ที่จริงจังพอสมควรได้ยากมากที่จะเรียก
mallocแยกสำหรับ cons cell ทุกตัว เพราะถ้าทำแบบนั้นก็ต้องใส่ไว้ใน linked list ระดับ global เพื่อให้ GC ทำขั้น sweep ได้ หรือไม่ก็ต้องมีอาร์เรย์ระดับ global ที่เก็บแต่ pointerฉันเคยเห็นโปรเจกต์ Lisp เล่น ๆ ที่ทำสุดสัปดาห์อย่างน้อยสองครั้ง ซึ่ง
malloccons cell แล้วปล่อยรั่วไว้ โดยทิ้ง GC เป็น TODO ก้อนโตถึง cell จะมาจาก heap แบบอาร์เรย์อัดแน่น สุดท้ายก็อาจยังมีอาร์เรย์ global เพิ่มอยู่ดี เช่นเวลาทำ generational garbage collection บน allocator ที่ไม่คัดลอก object อาจเพิ่ม object อายุน้อยลงในอาร์เรย์เสริมเพื่อรวบรวมไว้ให้ sweep ได้ในรอบ GC เร็ว ๆ และอาร์เรย์นั้นก็คือ nursery
เป็นบทความที่ดี แต่มีข้อควรระวังอยู่สองอย่าง
tagged union ก็ทำได้เช่นกัน แต่ต้องจัดการการใช้หน่วยความจำอย่างชาญฉลาด
เทคนิค “virtual memory” ทำให้สามารถนำพื้นที่หน่วยความจำกายภาพที่กระจัดกระจายมาต่อให้เป็นพื้นที่หน่วยความจำเสมือนที่ต่อเนื่องกันได้ ถ้าพื้นที่แอดเดรสเสมือนถูกแบ่งเป็นเซกเมนต์ตั้งแต่แรก มันก็คงไม่เกิดการแตกกระจาย และพื้นที่หน่วยความจำใด ๆ ก็น่าจะขยายตัวอยู่ที่เดิมได้เสมอโดยไม่ชนกับพื้นที่อื่น
ถ้าเป็นอย่างนั้น การทำ
realloc()ก็คงตัดเส้นทางmemcpy()ออกได้ น่าเสียดายภายในอาจไม่ปลอดภัย แต่ดูเหมือนจะทำอินเทอร์เฟซแบบปลอดภัยที่อ่านอย่างเดียวได้ การคืนหน่วยความจำอาจเป็น O(n) แต่ถึงอย่างนั้นก็น่าจะเร็วกว่า tree มาก
ผมแปลกใจที่ยังมีพอยน์เตอร์ (“การอ้างอิง”) สองตัวเหลืออยู่ในโหนด ทั้งที่ตอนนี้เรารู้แล้วว่าพอยน์เตอร์ตัวแรกชี้ไปยังโหนดถัดไปที่ถูกต้องเสมอ
ผมเคยเห็น https://github.com/rswier/c4 ใช้วิธีแบบนั้น แน่นอนว่าโค้ดอ่านยากกว่า แต่เล็กกว่าและเร็วกว่า
ในเรื่องการจัดการหน่วยความจำ คำว่า arena ทำให้นึกถึง arena allocator มากกว่าคำว่า “flattening”
เวลาต้องจัดสรรรายการจำนวนมากที่มีอายุการใช้งานเท่ากัน ก็จะจัดสรรจากก้อนหน่วยความจำใหญ่หนึ่งก้อนหรือหลายก้อนให้มีประสิทธิภาพมากขึ้น แล้วเมื่ออายุการใช้งานร่วมกันนั้นจบลง ก็คืนก้อนใหญ่แทนการคืนทีละรายการ
เพราะแค่ใช้พื้นที่ของก้อนแม่ไปตามลำดับ จึงไม่ต้องมี free list แบบ heap allocator ทั่วไป ทำให้การจัดสรรมีประสิทธิภาพมากขึ้นได้ด้วย
ในบริบทนี้ “flattening” ที่ใช้อินเด็กซ์แทนพอยน์เตอร์ก็อาจมองได้ว่าเป็นการใช้พอยน์เตอร์สัมพัทธ์กับก้อนแม่ หรือก็คือ offset
ตอนทำ V7(https://github.com/cesanta/v7) ซึ่งเป็น JavaScript parser และ interpreter สำหรับสภาพแวดล้อม embedded ที่หน่วยความจำจำกัดมาก ผมก็ใช้ โครงสร้าง AST แบบกะทัดรัด แบบนี้
ภายหลังเปลี่ยนไปเป็นขั้นตอนคอมไพล์จาก AST เป็น bytecode แต่ช่วงหนึ่งก็เคยตีความโดยไล่เดิน implicit AST โดยตรงระหว่างการรัน
ผมก็ทำอะไรคล้าย ๆ กันในคอมไพเลอร์ Yaml to Sql ของผมที่ https://yaml2sql.netlify.app
กระบวนการ flattening อาจจะแปลกไปหน่อย แต่สนุก และสุดท้ายก็คุ้มค่ากับความพยายามที่ลงไป
ตัวอย่างเช่น การ flattening นิพจน์บูลีนเป็นแบบฝึกหัดที่ดีสำหรับคนที่อยากลอง: https://github.com/revskill10/yaml2sql/blob/main/app/query.r...