- แชร์กลยุทธ์การออกแบบและพัฒนา Lexer ความเร็วสูงมาก สำหรับภาษา purple-garden พร้อมข้อมูลประสิทธิภาพจากการวัดจริง
- นำ เทคนิคการปรับแต่งประสิทธิภาพ หลายแบบมาใช้ เช่น Threaded Lexing (อิง jump table), 0-copy และ window string, interning, bump allocator
- เพิ่มความเร็วในการพาร์สสูงสุดด้วย token hashing และ การเปรียบเทียบคีย์เวิร์ดด้วยค่าแฮชที่เตรียมไว้ล่วงหน้า โดย jump table ให้ประสิทธิภาพด้าน CPU cache ดีกว่า
switch แบบง่าย
- ใช้ mmap กับไฟล์ทั้งก้อน และ ลด dynamic allocation ให้น้อยที่สุด เพื่อลดต้นทุนด้าน IO และการจัดการหน่วยความจำสำหรับอินพุตขนาดใหญ่ได้มาก
- พิสูจน์แล้วว่าเร็วกว่า lexer ชื่อดังเดิม ๆ (เช่น flex, handcoded) ได้ มากกว่า 10 เท่า พร้อมตัวเลข micro-benchmark แยกตามแต่ละขั้นของ parsing/runtime
ภาพรวมของ Lexing และคอมไพล์ไปป์ไลน์
- Lexer (tokenizer) แปลงสตริงอินพุตให้เป็น รายการของ token ที่มีความหมาย แล้ว parser จะรับไปสร้าง AST (abstract syntax tree) ต่อ
- การออกแบบ token ในภาษา purple-garden คงโครงสร้างให้ เล็กที่สุด โดยใช้ enum TokenType และเก็บเพียงข้อมูลสตริงกับชนิดเท่านั้น
การออกแบบ Lexer แบบมินิมอลและตัวอย่างโค้ด
- โครงสร้าง Lexer เก็บเพียง สตริงอินพุต และ ตำแหน่งปัจจุบัน
- สร้าง token ตามอักขระแต่ละตัวด้วยคำสั่ง switch
- เพื่อ การดีบัก มีการใช้ array สำหรับแมปชนิดกับสตริง และการกำหนดค่าเริ่มต้นแยกตามชนิด
Threaded Lexing (อิง jump table)
- แทนการแยก token ด้วย switch ด้วย jump table (computed goto)
- ใช้ array ขนาด 256 ไบต์ โดยใช้อักขระเป็นดัชนีเพื่อแมปไปยัง label สำหรับจัดการแต่ละแบบ
- ในการแตกแขนงของโค้ดจริง ใช้แมโคร JUMP_TARGET เพื่อกระโดดไปทำงานได้ทันที
- ข้อดี:
- ทำงานได้เร็วขึ้นจาก cache miss ที่ลดลง และ การปรับแต่ง branch prediction
- ข้อเสีย:
- ไม่รองรับ MSVC (ใช้ได้เฉพาะ Clang, GCC) และดีบักได้ยาก
การจัดการหน่วยความจำและการทำ allocator abstraction
- นิยามอินเทอร์เฟซสำหรับกลยุทธ์การจัดสรรหน่วยความจำหลายแบบ เช่น bump allocator (โครงสร้าง Allocator)
- ใช้แมโคร CALL เพื่อลดความซับซ้อนของ verbose log และการส่ง context
- แสดงตัวอย่างโครงสร้างและโค้ดสำหรับการจัดสรร, การคืนหน่วยความจำ และการเก็บสถิติจริง
การจัดการสตริงแบบ 0-copy และอิง window
- เพื่อให้ประมวลผลได้มีประสิทธิภาพใน C มีการนำโครงสร้าง Str (pointer, length, hash) มาใช้
- มีการเขียนเองสำหรับ slice, concat, eq, hashing, การแปลงตัวเลข ฯลฯ
- string slice สร้างได้ทันทีด้วยการเลื่อน pointer โดยไม่ต้องจัดสรรหน่วยความจำ
- แม้แต่การแปลงตัวเลขก็ยังใช้อัลกอริทึมแปลงอักขระเป็นจำนวนเต็มที่เขียนเอง
Token hashing และการเทียบคีย์เวิร์ดด้วยแฮชที่เตรียมไว้ล่วงหน้า
- คำนวณ แฮชของ token (FNV-1a) ตั้งแต่ตอนสร้าง เพื่อเพิ่มประสิทธิภาพการเทียบซ้ำและ interning
- สำหรับ คีย์เวิร์ดค่าคงที่ เช่น true/false จะใช้การเทียบด้วยค่าแฮชโดยตรงเพื่อแตกแขนงทันที (ช่วยเพิ่มประสิทธิภาพ)
is_alphanum (ตรวจว่าเป็นตัวอักษร/ตัวเลข/อักขระพิเศษ) ก็มีการปรับแต่งด้วย bit operation และวิธีแบบ lookup เช่นกัน
การทำให้การพาร์สตัวเลขมีประสิทธิภาพขึ้นและย้ายไปไว้ขั้นคอมไพล์
- ใน Lexer จะเก็บเพียง window และ hash ของ token ตัวเลข ส่วนการแปลงเป็นจำนวนเต็ม/ทศนิยมจริงจะทำเพียงครั้งเดียวใน ขั้นคอมไพล์ โดยไม่ซ้ำซ้อน
- เมื่อต้องพาร์สค่าตัวเลขซ้ำ พบว่าความเร็วรวมดีขึ้นมากกว่า 64%
การเร่งความเร็ว IO ของไฟล์ขนาดใหญ่
- แทนที่วิธี
fread เดิมด้วย mmap เพื่อ แมปไฟล์ทั้งก้อนเข้าหน่วยความจำโดยตรง
- ฟังก์ชัน IO_read_file_to_string จะ mmap อินพุตทั้งหมด และพบว่าประสิทธิภาพดีขึ้น 6–35 เท่าสำหรับข้อมูลขนาดใหญ่
เบนช์มาร์กใช้งานจริงและการเปรียบเทียบประสิทธิภาพ
- บน Laptop: อินพุต 25MB มากกว่า 1,000,000 บรรทัด ใช้เวลา 44ms (เฉพาะการ tokenize)
- บน Desktop: อินพุตเดียวกันทำได้ 30ms (สูงสุด 848MB/s)
- เมื่อเทียบกับ lexer อื่น เร็วกว่าได้ มากกว่า 10 เท่า (0.3 วินาที เทียบกับ 2–13 วินาที)
- ใน micro-benchmark มีการวัดผลของแต่ละ optimization อย่างเป็นตัวเลข (เช่น ใช้ bump allocator เร็วขึ้น 1.58 เท่า, สตริงแบบ 0 alloc เร็วขึ้น 1.4–1.5 เท่า, ย้ายการพาร์สตัวเลขไปขั้นคอมไพล์เร็วขึ้น 2.8 เท่า ฯลฯ)
สรุปกลยุทธ์การพัฒนา
- แตกแขนงตรงด้วย jump table (threaded lexing)
- โครงสร้าง token แบบ window 0-copy
- interning สำหรับ token ค่าคงที่
- การจัดการหน่วยความจำบนพื้นฐาน bump allocator
- token hashing และการเทียบด้วยแฮชที่เตรียมไว้ล่วงหน้า
- พาร์สแบบหน่วงเวลาและ interning สำหรับ token ตัวเลข/สตริง
- ประมวลผลไฟล์ขนาดใหญ่ด้วย mmap
- เสนอแนวทางต่อยอดในอนาคต เช่น การใช้ SIMD, อัลกอริทึมแฮชที่เร็วกว่า, memory alignment และ prefetch, การปรับ jump table ให้เหมาะกับอินพุตแต่ละแบบ
ยังไม่มีความคิดเห็น