แนวทางเขียนโครงสร้างข้อมูลแบบ type-safe (Generic) ใน C

• บทความนี้อธิบายวิธีใหม่ในการสร้าง โครงสร้างข้อมูลแบบ type-safe (Generic) ในภาษา C
• ใช้เทคนิค เชื่อมข้อมูลชนิดเข้ากับโครงสร้างข้อมูลด้วย union โดยอธิบายผ่านตัวอย่างการทำ linked list
• เปรียบเทียบ จุดแตกต่างและข้อเสียของแต่ละแนวทาง กับแพตเทิร์น generic แบบเดิมใน C (macro, void pointer, Flexible Array Member)
• สามารถทำ type check ได้ตั้งแต่คอมไพล์ไทม์ เพื่อป้องกันการใช้ชนิดข้อมูลผิดตั้งแต่ต้น
• เทคนิคใหม่นี้ให้ อินเทอร์เฟซของฟังก์ชัน/โครงสร้างข้อมูลที่ชัดเจนและสม่ำเสมอ เช่น foo_list

---

บทนำ

• แนะนำวิธีสร้าง โครงสร้างข้อมูล generic ในภาษา C ให้มี type safety
• เทคนิคนี้ใช้ union เพื่อผูกข้อมูลชนิดเข้ากับโครงสร้างข้อมูลตั้งแต่คอมไพล์ไทม์
• สามารถประยุกต์ใช้ได้กับโครงสร้างข้อมูลทุกแบบ เช่น map, array, binary tree และอธิบายผ่านตัวอย่างการทำ linked list แบบพื้นฐาน
• เพราะนักพัฒนาจำนวนมากคิดว่า generic ใน C เป็นไปไม่ได้ ผู้เขียนจึง อธิบายแบบทีละขั้นให้เข้าใจง่าย

generic แบบดั้งเดิมที่อิง macro

• วิธีดั้งเดิมในการทำโครงสร้างข้อมูล generic ใน C คือใช้ macro เพื่อสร้างชื่อ struct, ฟังก์ชัน และชนิดข้อมูล
• ขยายการใช้งานโดย include header ของโครงสร้างข้อมูลซ้ำหลายครั้งสำหรับหลายชนิดข้อมูล

ตัวอย่าง:

• ใช้ macro (เช่น CONCAT, NODE_TYPE, PREPEND_FUNC) เพื่อสร้างชื่อ struct และฟังก์ชันให้ตรงกับชนิดข้อมูล
• จะมี ฟังก์ชันและ struct ถูกสร้างแยกกันตามแต่ละชนิด ทำให้ทั้ง int และ Foo มีนิยามโครงสร้างข้อมูลของตัวเองคนละชุด

ข้อเสีย:

• ติดตามได้ยากว่าชนิดข้อมูลและฟังก์ชันถูกนิยามไว้ที่ไหน (เพราะถูกสร้างผ่าน macro)
• ใช้ประโยชน์จากระบบ autocomplete ของโค้ดได้ยาก
• มีการสร้างฟังก์ชันชุดเดียวกันซ้ำหลายชุด ทำให้ขนาดไบนารีใหญ่ขึ้นและใช้เวลาบิลด์มากขึ้น
• ต้องมีคำนำหน้าชื่อฟังก์ชันตามชนิดข้อมูล (เช่น Foo_list_prepend)

generic ขั้นที่ 1: วิธี void pointer

• กำหนดชนิดข้อมูลของโครงสร้างข้อมูลเป็น void * เพื่อให้ไม่ผูกกับชนิดใดชนิดหนึ่ง
• ประกาศฟิลด์ data ของ linked list เป็น void *
• ไม่สามารถตรวจสอบชนิดข้อมูลได้ จึงอาจเกิด type error ตอนรันไทม์ และมีความปลอดภัยในระดับคอมไพล์ไทม์ต่ำ
• ไม่มีประสิทธิภาพด้านหน่วยความจำและแคช: node และข้อมูลถูกจัดสรรแยกกัน ทำให้เกิด overhead ที่ไม่จำเป็นและ cache miss มากขึ้น

generic ขั้นที่ 2: inline storage (Flexible Array Member)

• ใช้ Flexible Array Member เพื่อเก็บข้อมูลจริงไว้ใน node โดยตรงแทนการเก็บ pointer
• ต้องจัดสรรหน่วยความจำเพียงครั้งเดียวต่อหนึ่ง node และข้อมูลกับ pointer next จะอยู่ใกล้กันในแคช
• วิธีนี้ต้อง ส่งข้อมูลขนาดเพื่อใช้กับ memcpy เป็นต้น แต่ให้ประสิทธิภาพดีขึ้นจากการจัดวางหน่วยความจำที่สม่ำเสมอ
• หากใช้ฟังก์ชัน list_alloc_front ก็สามารถกำหนดค่า struct ได้โดยตรงโดยไม่ต้องใช้ memcpy

generic ขั้นที่ 3: ทำ type check

• ประกาศ pointer ของชนิดข้อมูลที่พารามิเตอร์ไว้ในสมาชิก payload ของ union เพื่อเพิ่มข้อมูลชนิดให้กับโครงสร้างข้อมูลตั้งแต่คอมไพล์ไทม์
• ตัวอย่าง) #define List(type) union { ListNode *head; type *payload; }
• ด้วยวิธีนี้สามารถดึงชนิดข้อมูลของลิสต์นั้นได้ด้วย __typeof__(foo_list.payload)
• ใน macro (list_prepend) สามารถ cast ชนิดของฟังก์ชันเพื่อให้คอมไพล์ได้เฉพาะเมื่อใช้ชนิดข้อมูลถูกต้องเท่านั้น
• หากใช้ชนิดข้อมูลผิด จะเกิด error ตั้งแต่คอมไพล์ไทม์

ตัวอย่าง error:

• หากเพิ่ม int ลงใน foo_list จะได้ข้อความคอมไพล์เออร์ว่า 'incompatible integer to pointer conversion'

การรองรับคอมไพเลอร์ที่ไม่รองรับ typeof

• ก่อน C23 นั้น __typeof__ ยังไม่ใช่มาตรฐาน จึงอาจใช้ไม่ได้ในคอมไพเลอร์บางตัว (เช่น MSVC รุ่นเก่า)
• สามารถใช้วิธีอ้อม เช่นอาศัยสมาชิก payload ภายใน struct เพื่อให้ได้ผลใกล้เคียงกัน

การส่งพารามิเตอร์และ typedef

• แม้จะเป็น List(Foo) รูปแบบเดียวกัน แต่ คอมไพเลอร์ยังมองว่าเป็นคนละชนิดข้อมูลกัน
• หากใช้ typedef จะช่วยให้ การส่งเป็นอาร์กิวเมนต์และการกำหนดค่า ทำได้ราบรื่นขึ้น

ตัวอย่าง:

• typedef List(Foo) ListFoo;
• สามารถประกาศตัวแปร ListFoo และใช้เป็นพารามิเตอร์ของฟังก์ชันได้

ปิดท้ายและการขยายไปยังโครงสร้างข้อมูลแบบต่าง ๆ

• เทคนิคนี้สามารถนำไปใช้กับโครงสร้างข้อมูลที่ต้องมี type parameter หลายตัวได้ด้วย (เช่น hash map)
• สามารถใช้ union เพื่อรับประกัน type safety ของทั้ง key และ value ได้
• หากต้องการดูตัวอย่างเชิงปฏิบัติและ implementation ของ macro เพิ่มเติม ดูได้ที่ ลิงก์ gist ของโค้ดที่เกี่ยวข้อง

สรุป

• แนวทางใหม่นี้ช่วยแก้ข้อเสียของวิธีเดิม (ความอ่านง่าย ประสิทธิภาพการบิลด์ และการดูแลรักษา) พร้อมทั้งให้ ระบบการตั้งชื่อฟังก์ชันที่สม่ำเสมอและ type safety
• รองรับโครงสร้างข้อมูลหลายแบบและ type parameter หลายตัวได้ง่าย
• ด้วยการทำ type check ตั้งแต่คอมไพล์ไทม์ จึงได้ทั้ง ความปลอดภัยและประสิทธิภาพ ในการใช้งานโครงสร้างข้อมูล generic

คำขอบคุณ

• บทความนี้สำเร็จขึ้นได้จากฟีดแบ็กและกำลังใจของ Martin Fouilleul

[click]

หรือพูดง่าย ๆ ว่า แค่ใช้ Zig ก็พอแล้วไม่ใช่เหรอ? ก็มีความสงสัยแบบนั้นขึ้นมาเหมือนกัน

[GN⁺]

ความคิดเห็นจาก Hacker News

• มีคนชี้ว่าในโค้ดขั้นที่ 2 การใช้ uint64_t data[]; ไม่เหมาะกับชนิดข้อมูลที่มีข้อกำหนดการจัดแนวหน่วยความจำสูงกว่า uint64_t และในทางกลับกันก็สิ้นเปลืองโดยไม่จำเป็นสำหรับชนิดที่เล็กกว่า โดยเฉพาะจะยิ่งเป็นปัญหาใน ABI แบบ ilp32 บนสถาปัตยกรรม 64 บิต ในโค้ดขั้นที่ 3 ควรเขียนเป็น int main() { List(Foo) foo_list = {NULL}; แบบนี้ อีกความเห็นคือถ้าไม่มี typeof ก็จะคืนค่ากลับไม่ได้ และในโค้ดทางเลือกอาจเกิดข้อผิดพลาดเกี่ยวกับ const ได้ ซึ่งปัญหานี้เด่นชัดขึ้นเพราะความสมมาตรของตัวดำเนินการ == ถ้าเอา payload ออกก็จะไม่มีข้อมูลขนาด ทำให้ไม่ปลอดภัย เช่น อาจดูเหมือนว่าเพิ่ม int32_t ลงใน List(int64_t) ได้ แต่จริง ๆ แล้วไม่สามารถรู้ขนาดของ int32_t ได้ จึงเห็นว่ายังต้องเสริมอีกหากจะให้ปลอดภัยขึ้น มองว่าการใช้ generic ใน C มีข้อจำกัดใหญ่สองอย่าง อย่างแรกคือวิธี delegate ผ่าน vtable ทำให้ความสามารถถูกจำกัดเพราะ struct ใส่แมโครไม่ได้ อย่างที่สองคือถ้า delegate ไปยัง vtable ภายนอก ก็ต้องประกาศชนิดทั้งหมดที่จะใช้ไว้ล่วงหน้า วิธีที่ดีที่สุดคือประกาศเฉพาะฟังก์ชันแบบ static ในเฮดเดอร์ที่มี typedef อยู่ด้วย พร้อมเสริมว่า GCC และ Clang เตือนเรื่อง undefined static คนละจังหวะกัน ปิดท้ายด้วยการยกตัวอย่างการออกแบบฟังก์ชันที่รับบัฟเฟอร์ struct คนละแบบ เพื่อเน้นว่าต้องดูแลให้ครบแม้แต่เวอร์ชัน const

  • เกี่ยวกับปัญหา delegate ไปยัง vtable ภายนอก มีคนเล่าว่าในโปรเจกต์เก่าเคยแก้เรื่องนี้ถึงขั้นสร้างคอมไพเลอร์เอง เริ่มจากโปรเจกต์ Apache Clownfish ที่ตอนแรกพยายาม parse ไฟล์ .h ก่อนจะลงเอยด้วยการสร้างฟอร์แมตของตัวเองคือ Clownfish header (.cfh) มีการยกตัวอย่างโค้ดที่เรียกเมธอด "Clone" ของ obj จริง ๆ และเล่าประสบการณ์ว่าต้องสร้างโค้ดลักษณะฝืน ๆ แบบนี้จำนวนมากเพื่อทำ language binding สำหรับภาษาแบบ dynamic ที่ต้องการความสามารถเชิงวัตถุ จุดประสงค์ของ Clownfish คือการให้ object model ที่เป็นตัวหารร่วมต่ำสุด และชนิดของภาษา binding ก็สร้างจาก .cfh เช่นกัน พร้อมเสริมว่าความซับซ้อนแบบนี้ทำให้คนส่วนใหญ่ยอมทิ้ง type safety แล้วไปใช้การ cast void* แทน https://github.com/apache/lucy-clownfish

  • เรื่อง int main() มีคนเน้นว่าใน C นั้น int main() หมายถึงจำนวนอาร์กิวเมนต์ไม่แน่นอน ต้องประกาศเป็น int main(void) จึงจะหมายถึงไม่มีอาร์กิวเมนต์จริง ๆ และบอกว่านี่เป็นเรื่องที่คนเขียน C++ จำนวนมากมักลืม

  • มีความเห็นว่าอยากให้ union สามารถ union กันได้จริง ๆ กล่าวคืออยากให้ชนิดหนึ่งประกาศตัวเองเป็นส่วนหนึ่งของ union ของอีกชนิดได้

  • มีคนทักว่าตอน malloc อาจมีปัญหาเรื่อง padding ภายใน ทำให้ขนาดที่คำนวณได้เล็กกว่าความเป็นจริง เช่นกรณี malloc(sizeof(*node) + data_size); จึงมีความเสี่ยง

• มีคนโต้แย้งเนื้อหาในทริก #0 โดยบอกว่าตอนสร้าง dialect ของ C ทั้งชุดตัวเองใช้ทริกนี้อยู่ ยกตัวอย่างโค้ด implementation ของ generic binary heap https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h แม้ไวยากรณ์จะค่อนข้างหนัก แต่สุดท้ายจะกลายเป็น C struct ปกติ ซึ่งได้ประโยชน์มากในด้านการ optimize และความคาดเดาได้ ส่วน implementation อื่น ๆ มองว่าหลีกเลี่ยง void*, การกำหนดขนาดหน่วยความจำตอนรันไทม์ และการนิยามแมโครไม่ได้

  • ในฐานะผู้เขียน บอกว่า binary heap กับ linked list มีจุดประสงค์ต่างกัน Binary heap ต้องอ่านข้อมูลตอนจัดเก็บ จึงมีรูปแบบการเข้าถึงต่างออกไป และในการเขียน generic binary heap ก็อาจต้องเลือกทางออกไม่เหมือนกัน พร้อมเสริมว่าได้กล่าวไว้ในเชิงอรรถของบทความแล้ว

  • มีคนให้เหตุผลหลายข้อว่าทำไมชอบ implementation แบบ header เวลา debug จะตามโค้ดและใช้ข้อมูลชนิดได้ง่ายกว่าฟังก์ชันแมโคร คอมไพเลอร์สามารถทำ optimization แบบ monomorphized แยกแต่ละ instance ได้ จึงไม่มีต้นทุนรันไทม์หรือภาระจากขนาดแปรผัน สามารถวาง generic struct ไว้บนสแต็กได้ ปัญหาสองข้อที่ผู้เขียนยกมาสามารถเลี่ยงได้ โดยใช้แมโครชื่อฟังก์ชันเพื่อเปลี่ยนชื่อได้ง่าย และใช้ weak symbol เพื่อให้ตัวลิงเกอร์รวมการนิยามซ้ำอัตโนมัติได้ แม้ generic container สำหรับชนิดพอยน์เตอร์จะมีปัญหาอีกแบบ แต่ก็แก้ได้ด้วย typedef เป็นต้น พร้อมปิดท้ายว่าต่อให้ intrusive data structure ใน C ยังสะดวกอยู่ แต่ debug ยากจริง

  • มีคนขำมากกับสำนวนที่ว่า "คอมไพเลอร์กินมันเหมือนกินโดนัท"

• มีข้อสังเกตว่าเวลาแปลงชนิดฟังก์ชัน เช่นสมมติว่า Foo* กับ void* มี representation ภายในเหมือนกันนั้น มาตรฐาน C ไม่ได้รับประกัน และเมื่อไม่มีความเข้ากันได้ของชนิด ("compatible") การ cast แบบนี้อาจนำไปสู่พฤติกรรมที่ไม่กำหนดแน่ชัด รวมถึงอาจกระทบการวิเคราะห์ alias ของคอมไพเลอร์ด้วย (แนบลิงก์อ้างอิง) https://news.ycombinator.com/item?id=44421185

  • ผู้เขียนตอบว่าได้พูดถึงไว้ในเชิงอรรถแล้ว และยืนยันว่าการ cast ไม่ใช่แกนหลักของ type safety ในที่นี้ พร้อมชวนให้อ่านบทความทั้งหมด

• มีคนถามว่า "ถ้าจะใช้ generics ใน C ทำไมต้องฝืนขนาดนี้ ทำไมไม่ใช้ C++ ไปเลย"

  • มีคนแชร์ประสบการณ์ว่าด้วยเกณฑ์ด้านความปลอดภัยและข้อกำหนดอื่น ๆ โปรเจกต์เก่าจำนวนมากยังย้ายไป C++ ไม่ได้ในทันที โปรเจกต์ใหม่อาจกำหนดมาตรฐานแล้วนำ C++ มาใช้ได้ แต่โปรเจกต์เดิมคงต้องอยู่กับ C ไปอีกพักหนึ่ง และมองว่าทัศนคติแบบ "ก็ใช้ C++ สิ" ควรมีความเข้าใจบริบทมากกว่านี้

  • อีกความเห็นบอกว่าในภาคสนามที่ใช้ C จริง การย้ายไป C++ อาจซับซ้อนกว่าและก่อปัญหาได้มากกว่า

  • ในทางกลับกันก็มีคนเห็นว่า ถ้าออกแรงเพิ่มอีกนิดใน C ก็ได้ผลลัพธ์เดียวกันอยู่แล้ว จึงไม่จำเป็นต้องไปถึง C++

• มีคนแนะนำรูปแบบที่ลินุกซ์เคอร์เนลใช้จริง คือฝัง struct list_head ที่เก็บข้อมูลลิสต์ไว้ภายใน struct ของแต่ละชนิด พร้อมแนบลิงก์อ้างอิง https://kernelnewbies.org/FAQ/LinkedLists

  • มีคนรู้สึกว่าชื่อแมโคร LIST_HEAD_INIT, INIT_LIST_HEAD ของลินุกซ์เคอร์เนลไม่ค่อยสื่อความหมายเท่าไร

• มีคนชี้ว่าในโค้ดส่วน "typeof on old compilers" บรรทัด (list)->payload = (item); จริง ๆ ไม่ใช่ no-op แต่เป็นการเขียนทับ list head ด้วย item ถ้าต้องการพฤติกรรมตามที่คาดไว้ควรครอบด้วย if(0)

  • อีกความเห็นบอกว่าในตัวอย่างมีการเปลี่ยน union เป็น struct ซึ่งก็ดูสิ้นเปลืองเช่นกัน และน่าจะดีกว่าหากจัดการภายใน if(0)

• มีคนยกตัวอย่างว่าในภาษา D โครงสร้าง generic list แบบนี้ง่ายกว่ามาก และเปรียบว่า preprocessor ของ C ให้ความรู้สึกเหมือนใช้ค้อนทุบเล็บมือ ขณะที่งานตอกตะปูนั้น nail gun ทั้งเร็วและเรียบร้อยกว่า เพื่อเน้นย้ำความไม่สะดวกของแมโคร C

  • มีคนตอบว่าโพสต์นี้พูดถึง C และในบางโปรเจกต์ก็จำเป็นต้องใช้ C จริง ๆ

• มีคนมองว่าแนวคิดการใช้ union และ typeof() น่าสนใจ ส่วนตัวรู้สึกว่าสำหรับ intrusive data structure สุดท้ายก็ยังต้องมี wrapper ที่ครอบด้วยแมโครขนาดใหญ่ และตั้งคำถามว่า union กับ typeof จะทำ implementation แบบนี้ได้หรือไม่ พร้อมยกตัวอย่างโค้ด wrapper ของ hash table และลิงก์เอกสาร https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

• มีคนแชร์ว่าตัวเองก็ใช้เทคนิคนี้อยู่แล้วในไลบรารีเชิงทดลอง https://github.com/uecker/noplate/blob/main/src/list.h

  • และถามหาไอเดียสำหรับ struct แบบ intrusive กล่าวคือการใส่ node structure ไว้ในข้อมูล เพื่อให้วัตถุเดียวอยู่ในหลายคอนเทนเนอร์พร้อมกันได้

• มีคนมองว่าแก่นสำคัญคือการใช้ชนิดของ function pointer เพื่อให้ได้ type safety โดยทำแบบนี้แทนการใช้ handle type ที่พบได้บ่อย ทั้งยังแชร์ว่ามาตรฐาน C23 ปรับปรุงปัญหาเรื่องความเข้ากันได้ของชนิดแล้ว พร้อมแนบเอกสารมาตรฐานและสถานะการรองรับของ GCC/Clang รุ่นใหม่ https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

  • ผู้เขียนตอบว่าแนวคิดหลักจริง ๆ คือการใช้ union เพื่อผูกข้อมูลชนิดเข้ากับชนิดข้อมูล generic ไม่ได้มีแค่การ cast ฟังก์ชันเป็นวิธีเดียว และได้พูดถึงทางเลือกอื่น ๆ ไว้แล้ว รวมทั้งใน footnote และส่วน "typeof on old compilers" ด้วย