FUGC ของ Fil: garbage collector ที่น่าเหลือเชื่อ
(fil-c.org)- FUGC ของภาษา Fil-C เป็น garbage collector ขั้นสูงที่รองรับการทำงานแบบขนานและพร้อมกัน
- ใช้การทำงานแบบ on-the-fly (ทำงานได้ทันที) และ แนวทาง grey-stack ของ Dijkstra โดยไม่ต้องหยุดทั้งโปรแกรม
- ออกแบบให้มีทั้ง การติดตามหน่วยความจำอย่างแม่นยำ และ การทำงานโดยไม่ย้ายอ็อบเจ็กต์
- ใช้ safepoint เพื่อให้จัดการหน่วยความจำได้อย่างปลอดภัยและมีประสิทธิภาพแม้ในสภาพแวดล้อมแบบมัลติเธรด
- มีฟีเจอร์จัดการหน่วยความจำหลากหลายสไตล์แบบ C/Java/JavaScript เช่น การโยนข้อยกเว้นเมื่อเข้าถึงอ็อบเจ็กต์ที่ถูก free แล้วหรือ free ซ้ำ
ภาพรวมของ FUGC (Fil's Unbelievable Garbage Collector) ของ Fil
Fil-C ใช้ FUGC (Fil's Unbelievable Garbage Collector) ซึ่งเป็น garbage collector แบบ ขนาน พร้อมกัน on-the-fly grey-stack Dijkstra แม่นยำ และไม่ย้ายอ็อบเจ็กต์
ดูซอร์สโค้ดของ FUGC ได้ที่ fugc.c แต่จะไม่สามารถทำงานได้หากไม่มีตรรกะสนับสนุนจาก runtime และ compiler ส่วนอื่นๆ
คุณสมบัติหลักของ FUGC
- การประมวลผลแบบขนาน: ทำงาน marking และ sweeping พร้อมกันได้หลายเธรด ยิ่งมี CPU core มากก็ยิ่งเก็บกวาดได้เร็วขึ้น
- รองรับการทำงานพร้อมกัน: เธรดของ garbage collector ทำงานแยกจาก mutator (คือเธรดโปรแกรมผู้ใช้) ทำให้เธรดแอปพลิเคชันทำงานต่อได้โดยไม่ต้องหยุด
- on-the-fly (ทำงานได้ทันที): ไม่มี global stop-the-world โดยใช้ "soft handshake (=ragged safepoint)" ให้แต่ละเธรดทำงานบางอย่างแบบอะซิงโครนัส เช่น การสแกนสแตก
- แนวทาง grey-stack: ตรวจซ้ำสแตกของเธรดหลายรอบจนถึงจุดคงที่เพื่อทำ marking และหากพบอ็อบเจ็กต์เพิ่มระหว่างทางก็จะทำ marking ต่ออีก
- ใช้ store barrier แบบเรียบง่าย และไม่ต้องใช้ load barrier
- Dijkstra barrier: หากมีการเก็บพอยน์เตอร์ลงใน heap หรือตัวแปร global ระหว่าง marking ก็จะ mark อ็อบเจ็กต์ปลายทางไปพร้อมกัน
- การเก็บกวาดแบบแม่นยำ: runtime ติดตามตำแหน่งของพอยน์เตอร์ทั้งหมดได้อย่างถูกต้อง ทำให้ GC สำรวจเฉพาะอ็อบเจ็กต์จริงเท่านั้น
- การทำงานแบบไม่ย้ายอ็อบเจ็กต์: ตำแหน่งหน่วยความจำของอ็อบเจ็กต์ไม่เปลี่ยน ทำให้การเก็บกวาดพร้อมกันในระบบมัลติเธรดและการซิงก์ทำได้ง่าย
- การออกแบบแบบ advancing wavefront: mutator ไม่สามารถเพิ่มปริมาณงานให้ตัวเก็บกวาดได้ และอ็อบเจ็กต์ที่ถูก mark แล้วจะยังคงอยู่ตลอดรอบการเก็บกวาดนั้น
- incremental collection: อ็อบเจ็กต์บางตัวอาจยังมีชีวิตอยู่ตอนเริ่มรอบเก็บกวาด แต่ถูกปล่อยได้ระหว่างรอบนั้น
Safepoint และการจัดการเธรด
- Pollcheck: compiler จะแทรก pollcheck เป็นระยะ โดยใน fast path จะเป็นแค่การแตกแขนงธรรมดา ส่วน slow path จะเรียก callback ที่เกี่ยวข้องกับ GC
- Soft handshake: ส่งคำขอให้ทุกเธรดรัน pollcheck callback แล้วรอจนกว่าจะเสร็จ
- การจัดการสถานะ enter/exit: หากมีฟังก์ชันบล็อกนานๆ หรือ system call ที่ข้าม pollcheck ตัว collector จะเรียก callback นั้นเองโดยตรง
- รองรับมัลติเธรดพร้อม ป้องกัน race condition และรับประกันการเข้าถึงพอยน์เตอร์อย่างปลอดภัย
- รองรับงานพิเศษอย่างการดีบักหรือ
forkด้วยโหมด stop-the-world และทำ signal handling ได้อย่างเสถียร
ลูปการทำงานของตัวเก็บกวาด FUGC
- รอ trigger ของ GC
- เปิดใช้ store barrier แล้วทำ soft handshake (callback แบบ no-op)
- เปิดใช้ black allocation (mark ล่วงหน้าให้อ็อบเจ็กต์ใหม่) และรัน callback สำหรับรีเซ็ตแคช
- mark global root
- ทำ soft handshake (callback สำหรับสแกนสแตกและรีเซ็ตแคช) และถ้า mark stack ว่างให้ไปข้อ 7
- tracing (mark reference ของแต่ละอ็อบเจ็กต์ใน mark stack ทำซ้ำจน mark stack ว่าง แล้วกลับไปข้อ 5)
- ปิด store barrier, เตรียม sweep, แล้วทำ soft handshake เพื่อรีเซ็ตแคชอีกครั้ง
- sweep (หน้าที่ยังไม่ถูก sweep จะจัดสรรเป็น black ส่วนที่ sweep แล้วจะจัดสรรเป็น white)
- กลับเข้าสู่ลูปอีกครั้ง
ความแตกต่างจากงานวิจัยเดิมและการปรับแต่งประสิทธิภาพ
- FUGC คล้ายกับ DLG (Doligez-Leroy-Gonthier) collector แต่ใช้ Dijkstra barrier แบบง่าย และ grey stack ทำให้การทำ store barrier ตรงไปตรงมาและมีประสิทธิภาพสูง
- แนวทางจุดคงที่ช่วยให้ลู่เข้ารวดเร็วและมีต้นทุนต่ำ
- ใช้ การ sweep แบบ bitvector SIMD เพื่อปล่อยหน่วยความจำได้เร็วมาก โดยใช้เวลาไม่ถึง 5% ของเวลารวมของ GC
- มีการปรับแต่งประสิทธิภาพ เช่น การใช้ Verse heap config
ฟีเจอร์เสริม (ความยืดหยุ่นด้านการจัดการหน่วยความจำ)
การปล่อยอ็อบเจ็กต์
- เมื่อเรียก
freeแบบ C จะติดธงให้อ็อบเจ็กต์เป็น free ทันที และหากมีการเข้าถึงหลังจากนั้นจะเกิด trap - ป้องกัน GC ทำงานผิดพลาดจาก dangling pointer
- การอ้างอิงถึงอ็อบเจ็กต์ที่ถูกปล่อยแล้วจะถูกเปลี่ยนเส้นทางไปยัง free object แบบ singleton ทำให้ตรวจจับได้แน่นอนแม้มีการจัดสรรหน่วยความจำใหม่ภายหลัง
- ป้องกัน memory leak ที่ทำให้ GC ถูกยึดไว้โดยพอยน์เตอร์ที่ไม่ได้ใช้งาน
finalizer
- สามารถทำ finalizer queue แบบสไตล์ Java ได้อย่างยืดหยุ่นผ่านคิวที่ผู้ใช้กำหนดเองและการจัดการเธรด
weak reference
- ทำงานเหมือน
weak referenceของ Java ทุกประการ แต่ไม่มี reference queue แยกต่างหาก (ไม่รองรับ phantom และ soft reference)
weak map
- คล้ายกับ JavaScript WeakMap แต่สามารถวนดูทุกองค์ประกอบและตรวจจำนวนองค์ประกอบได้
บทสรุปและความหมาย
ผ่าน FUGC ทำให้ Fil-C มอบทั้ง ความปลอดภัยสูง และ การจัดการข้อยกเว้นที่เข้าใจง่าย สำหรับการใช้ free อย่างผิดวิธี
- ออกแบบให้เกิด trap เสมอเมื่อเข้าถึงอ็อบเจ็กต์ที่ถูกปล่อยแล้วหรือ free ซ้ำ
- หากไม่ปล่อยอ็อบเจ็กต์เอง GC ก็จะรับหน้าที่เก็บคืนให้อย่างเหมาะสม
- รองรับรูปแบบการจัดการหน่วยความจำที่หลากหลาย และมอบสภาพแวดล้อมที่คุ้นเคยแม้กับนักพัฒนา C/Java/JavaScript
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
อืม ดูเหมือนว่า Fil-C อาจมีความสำคัญมากจริง ๆ เพราะมีซอฟต์แวร์จำนวนมากที่มีอยู่ในรูปของโค้ด C เท่านั้น และน่าจะต้องมีแนวทางในการดูแลรักษามัน คอมไพเลอร์ C แบบเดิมยอมรับความเสี่ยงด้านความปลอดภัยขนาดใหญ่เพื่อรีดประสิทธิภาพ single-core ให้สูงสุด ซึ่ง trade-off แบบนี้ก็ดูเหมือนจะล้าสมัยไปแล้ว รายการซอฟต์แวร์ที่รองรับอย่าง CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash นั้นน่าทึ่งมาก ผมมองว่าแทบไม่มีตัวไหนในบรรดาซอฟต์แวร์เหล่านั้นที่จะถูกเขียนใหม่เป็น Rust อยากรู้ว่า Fil-C จะนำไปใช้กับการทำ multitasking ระหว่างโปรเซสที่ไม่ไว้ใจกันบนสภาพแวดล้อมที่ไม่มี MMU ได้ไหม ดูเหมือนว่าทิศทางอย่าง security แบบ capability-based และ non-blocking synchronization จะมาถูกทางแล้ว อยากรู้ว่ามีใครเคยใช้จริงบ้าง ในทางปฏิบัติมีรายงานว่าต่อให้แย่ที่สุดก็ช้าลงราว 4 เท่าเท่านั้น และชื่อนี่ก็ตลกดี ฟิลส์เวย์! ฟิลส์เวย์!
สำหรับคำถามที่ว่าสามารถใช้ Fil-C เพื่อทำ multitasking ระหว่างโปรเซสที่ไม่ไว้ใจกันบนคอมพิวเตอร์ที่ไม่มี MMU ได้หรือไม่ โดยพื้นฐานแล้ว FUGC อาศัยฟีเจอร์ของ OS ที่พึ่งพา MMU อยู่ก็จริง แต่คิดว่าน่าจะทำเวอร์ชันที่ตัดการพึ่งพานี้ออกได้ เรื่องประสิทธิภาพนั้น การช้าลง 4 เท่าเป็นกรณีเลวร้ายที่สุด และผมเป็นคนรายงานตัวเลขนั้นเอง ปกติผมจะพยายามวัดประสิทธิภาพตามความเป็นจริงเสมอ และไล่แก้ปัญหาด้านประสิทธิภาพอย่างไม่ลดละ ในความเป็นจริง แม้เป็นซอฟต์แวร์เวอร์ชัน Fil-C ก็ยังใช้โปรแกรมที่ผมชอบใช้เป็นประจำได้โดยไม่มีปัญหา
บอกว่ารายการซอฟต์แวร์ที่รองรับน่าประทับใจนั้น ผมเห็นด้วยในภาพรวม แต่มีมุมมองต่างออกไปเล็กน้อยกับตัวอย่างที่ยกมา CPython, Perl5 และอื่น ๆ เป็นรันไทม์ของภาษาที่ขึ้นชื่ออยู่แล้วว่า GC ช้า ดังนั้นการเอา GC ไปซ้อนอีกชั้นอาจไม่ใช่การออกแบบที่สวยนัก และอาจทำให้ช้าลงมากกว่าเดิม อีกทั้งก็มีความพยายามบางส่วนที่จะ reimplement หรือแทนที่มันด้วย Rust หรือ Go อยู่แล้ว เช่น SQLite ก็มี Turso และซอฟต์แวร์พวกนี้ก็เป็นโปรเจกต์หลักที่ได้รับการดูแลอย่างแข็งขันมากอยู่แล้ว จึงเป็นไปได้ว่าสักวันหนึ่งมันจะรีแฟกเตอร์เองหรือพอร์ตไป Rust ก็ได้ ตรงกันข้าม ผมคิดว่าจุดที่ Fil-C เหมาะกว่าคือโค้ดที่มีการดูแลน้อยกว่า ไม่ไวต่อประสิทธิภาพมากนัก แต่ยังถูกใช้งานต่อเนื่อง เหมือนโปรแกรม C อายุ 50 ปีที่ใครสักคนยังหยิบมาใช้เป็นครั้งคราว
จุดแข็งของ SQLite ที่เขียนด้วย C คือพกพาไปยัง OS ที่ไม่เป็นมาตรฐานได้ง่ายมาก ตัวอย่างเช่นผมเคยใช้มันโดยตรงบน μC/OS-II ซึ่งเป็น RTOS สำหรับระบบ embedded การออกแบบสภาพแวดล้อม embedded นั้นแตกต่างจาก PC/เซิร์ฟเวอร์พอสมควร จึงมักมีการระบุให้ reuse object/struct โดยไม่ free memory เลย เพื่อประสิทธิภาพและเพื่อลด memory fragmentation เป็นแนวคิดคล้าย custom heap allocation หรือ pooling เอกสาร VFS ของ SQLite, บทนำสู่ Micro-Controller OS
คุณบอกว่าซอฟต์แวร์ C ในรายการตัวอย่างคงจะไม่ถูกเขียนใหม่เป็น Rust แต่ผมสงสัยว่าอีกนานแค่ไหนก่อนที่เครื่องมือ static analysis ที่ขับเคลื่อนด้วย AI จะพัฒนาจนสามารถตรวจพบปัญหาในโค้ด C ได้อย่างแม่นยำ และให้ฟีดแบ็กว่า “ส่วนนี้จะเกิดข้อผิดพลาด แก้แบบนี้ได้” ถ้าเครื่องมือแบบนั้นออกมาจริง การใช้ C ต่อไปเรื่อย ๆ ก็คงพอไหว
ขอเสริมว่าตอนนี้ Fil-C ยังไม่รองรับระบบ 32 บิต (หรือเล็กกว่านั้น) เอกสารเกี่ยวกับ Invisicaps ใน Fil-C
โปรเจกต์แบบนี้ให้ความรู้สึกว่าเป็นกรณีหายากที่เดินทั้งสายวิจัยและสายใช้งานจริงพร้อมกัน ปกติเรื่องแบบนี้มักเกิดในบริษัท IT ใหญ่ ๆ ที่มีทีมทำและเลี้ยงด้วยรายได้โฆษณา เลยอยากรู้ว่า Fil-C เริ่มต้นมาจากพื้นหลังแบบไหน ถ้าไม่ใช่แค่โปรเจกต์แพสชันส่วนตัว ใครเป็นคนให้ทุน ใช้กำลังคนไปกี่ปี และเป้าหมายสุดท้ายคืออะไร
โดยส่วนตัวผมมองว่านี่น่าจะเป็นโปรเจกต์แพสชัน
สำหรับคำถามเรื่องเป้าหมายสุดท้าย มีการระบุว่า copyright ของโปรเจกต์เป็นของ Epic Games, Inc. ในปี 2024-2025
แค่การมีอยู่ของ Fil-C ก็น่ายินดีแล้ว แม้เทคโนโลยีแบบนี้จะใช้ได้ผลกับโปรแกรมจริง แต่ก็มักมีนักพัฒนาจำนวนมากเชื่อว่า “ของแบบนี้ทำไม่ได้” เพียงแค่การพิสูจน์ว่ามันสร้างขึ้นมาได้จริง ก็ช่วยตัดจบข้อถกเถียงมากมายได้ในทันที
อยากเห็นผล benchmark มาก ข้อกังวลใหญ่ที่สุดของแนวทางนี้คือมันอาจทำให้ประสิทธิภาพตกฮวบใน use case บางประเภทที่ C/C++ ยังได้รับความนิยมอยู่ ถ้าทั้ง throughput, latency, และการใช้หน่วยความจำออกมาใกล้กับภาษาอย่าง Go มากเกินไป สุดท้ายก็ดูเหมือนจะเหลือเหตุผลให้เลือกใช้น้อยลง
ในโลกของภาษาโปรแกรม การถกเถียงเรื่องประสิทธิภาพมีมาตั้งแต่ยุค assembly แล้ว เพียงแต่ผู้พัฒนาส่วนใหญ่ไม่ใช่คนที่มีวิสัยทัศน์โดดเด่นแบบ Ivan Suntherland, Alan Kay, Steve Jobs, Bret Victor แต่เป็นคนธรรมดาที่จะเชื่อเมื่อเห็นสิ่งนั้นทำงานต่อหน้าต่อตา ดังนั้นทุกวันนี้เราจึงยังเห็นสำเนาของ UNIX และ C อยู่เต็มไปหมด และหลายคนก็ยังใช้ชีวิตด้วยการทำซ้ำวิสัยทัศน์ในอดีตแทนที่จะสร้างสิ่งใหม่ขึ้นมาเอง แน่นอนว่าคนสองคนที่สร้าง UNIX และ C ในยุค 1970s ก็เป็นนักวิสัยทัศน์ที่ยอดเยี่ยมเช่นกัน
สงสัยว่าทำไมถึงไม่ใช้กลยุทธ์ retreating wavefront แทน advancing wavefront
ถ้าในโปรแกรม C เดิมมีการใส่
free(...)ไว้อย่างเหมาะสมอยู่แล้ว และยังมีการเก็บข้อมูลขอบเขตแยกสำหรับทุกพอยน์เตอร์อีกด้วย ทำไมถึงเลือกใช้ GC แบบเต็มระบบแทน ผมคิดว่าเทคนิค temporal checking แบบ lock-and-key (เอกสารอ้างอิง: ลิงก์งานวิจัย) อาจดีกว่าในแง่การคาดการณ์การใช้หน่วยความจำ ประสิทธิภาพ หรือการ scheduling ก็ได้ เดาว่าอาจเป็นเพราะพื้นที่เก็บ key ใหญ่เกินไป หรือเวลาในการตรวจสอบนานเกินไป หรือมีปัญหา race condition ในสภาพแวดล้อมแบบ multithreadingวิธี lock and key ไม่มีคุณสมบัติฉลาดเฉพาะตัวแบบที่ Fil-C มี จุดแข็งของ capability model ใน Fil-C คือมัน thread-safe อย่างสมบูรณ์ และในกรณีส่วนใหญ่ไม่ต้องใช้ atomics หรือ locking แบบพิเศษ
อีกจุดที่น่าสนใจคือมันอนุญาตให้ทำ pointer arithmetic ที่ออกนอกขอบเขตได้ ตราบใดที่ยังไม่มีการ dereference ซึ่งบางครั้งคอมไพเลอร์ก็ใช้ UB ตรงนี้เพื่อทำ optimization (คำถามที่เกี่ยวข้องใน Stack Overflow) เลยสงสัยว่าใน LLVM ภายในของ Fil-C มีการปิด optimization แบบนี้ไว้หรือไม่ หรือว่ามันจัดการพอยน์เตอร์ในรูป “base + offset” จึงตัดความเป็นไปได้นั้นไปเลย แล้วถ้าเป็นเช่นนั้น จะพลาด optimization บางอย่างที่ปกติใช้กับพอยน์เตอร์ทั่วไปหรือไม่
ดูเป็นโปรเจกต์ที่เจ๋งมาก ผมสะดุดกับตรงที่ fast path ของ pollcheck เป็นแค่ load-and-branch มีเทคนิคที่น่าสนใจอีกอย่างหนึ่งที่ใช้แทน branch แบบนี้ ซึ่งสรุปไว้ดีใน บทความ "implicit suspend check" ของบล็อกทางการ Android
C ที่รองรับ concurrency พร้อม GC แถมยังเป็น non-moving GC นี่น่าทึ่งจริง ๆ ถ้าสามารถเอาโปรเจกต์ C ขนาดกลางมาแลกกับประสิทธิภาพรันไทม์ที่ลดลง 2-3 เท่าเพื่อแลกกับการลด memory bug ได้ ผมก็ยินดีรับได้เลย อยากรู้ว่าการนำมาใช้แบบค่อยเป็นค่อยไปทำได้ง่ายแค่ไหน ทำได้แยกเป็นราย target หรือจำเป็นต้องเปลี่ยนทั้ง toolchain
ผมให้ความสำคัญกับ C, ประสิทธิภาพ และความปลอดภัยพอ ๆ กัน โครงสร้าง GC และ capability นี้น่าสนใจมาก ผมเคยคิดหลายครั้งว่า “C ที่ปลอดภัยขึ้น” จะมีหน้าตาอย่างไร และก็เคยพิจารณาแนวคิด capability อยู่หลายรอบ แต่ผมไม่เก่งโค้ดคอมไพเลอร์ เลยสงสัยว่าการรองรับ Windows นั้นยากไหม
สงสัยว่าใน GC มีการติดตาม root object อย่างไร มีขั้นตอนตอนคอมไพล์ที่มาร์กว่าอะไรคือ root ที่ต้องให้ GC สแกนหรือไม่ ถ้าใครรู้ช่วยอธิบายที
โปรเจกต์นี้น่าทึ่งจริง ๆ แปลกเหมือนกันที่ผมไม่เคยได้ยินชื่อมันมาก่อน อยากลองใช้ด้วยตัวเองมาก แม้อาจจะยากต่อการใช้ใน production เพราะข้อจำกัดด้านประสิทธิภาพ แต่ในฐานะวิธีตรวจสอบความปลอดภัยของบางโปรแกรมด้วยตัวเอง มันดูมีประโยชน์มาก ให้ความรู้สึกครอบคลุมกว่า sanitizer ที่ใช้อยู่เป็นประจำ