การค้นพบล่าสุดในฟังก์ชันการนำเข้าไฟล์ Universal Scene Description (USD) ของ Blender ได้จุดประเด็นการถกเถียงที่น่าสนใจเกี่ยวกับการเลือกใช้โครงสร้างข้อมูลและผลกระทบต่อประสิทธิภาพ ชุมชนนักพัฒนาได้ระบุและวิเคราะห์กรณีที่การเลือกวิธีการพัฒนาที่ดูเรียบง่ายกลับส่งผลให้เกิดความซับซ้อนในการประมวลผลแบบกำลังสอง
ปัญหาด้านประสิทธิภาพ
ปัญหาเกิดจากการที่ Blender ใช้รายการเชื่อมโยงสองทางแบบเรียงลำดับ (sorted doubly linked list) เพื่อจัดเก็บ ID ของวัตถุระหว่างการนำเข้าไฟล์ USD สิ่งที่ควรจะเป็นการทำงานแบบ O(N) กลับกลายเป็นประสิทธิภาพแบบ O(N²) เมื่อต้องจัดการกับไฟล์ที่มีการอ้างอิงถึงเอนทิตีเดียวกันหลายครั้ง การอภิปรายในชุมชนเผยให้เห็นว่านี่เป็นตัวอย่างคลาสสิกของพฤติกรรมแบบกำลังสองที่เกิดขึ้นโดยไม่ตั้งใจ ซึ่งการพัฒนาที่ดูสมเหตุสมผลกลับนำไปสู่การลดลงของประสิทธิภาพเมื่อข้อมูลมีขนาดใหญ่ขึ้น
ผมไม่เข้าใจจริงๆ ว่าทำไมคนไม่เคยคิดที่จะเปลี่ยนจาก linked lists แม้ว่าจะไม่มีกรณีแย่สุดของการแทรกข้อมูลแบบ O(n) มันก็มักจะทำงานได้แย่กว่า vectors, deques หรือ hives
ผลกระทบต่อประสิทธิภาพ:
- เวลาในการประมวลผลเดิมสำหรับ limits_48.usdc: 4 นาที 40 วินาที
- เวลาในการประมวลผลที่ปรับปรุงแล้ว: 27 วินาที
- การปรับปรุงประสิทธิภาพ: เร็วขึ้นประมาณ 10 เท่า
 |
|---|
| แผนภูมิเปลวไฟที่แสดงการวิเคราะห์ประสิทธิภาพที่เกี่ยวข้องกับฟังก์ชันการนำเข้าไฟล์ USD ของ Blender |
ทางเลือกในการแก้ปัญหา
ชุมชนได้เสนอแนวทางหลายวิธีเพื่อแก้ไขปัญหาประสิทธิภาพนี้ ข้อเสนอแนะรวมถึงการแทนที่ linked list ด้วยโครงสร้างข้อมูลที่มีประสิทธิภาพมากขึ้น เช่น red-black trees, hash tables หรือโครงสร้างแบบต้นไม้อื่นๆ นักพัฒนาบางคนสังเกตว่าในขณะที่โค้ดที่เขียนด้วยภาษา C มักจะใช้ linked lists เป็นค่าเริ่มต้น แต่การเขียนโปรแกรมสมัยใหม่มักจะเลือกใช้ประเภทคอนเทนเนอร์ที่เหมาะสมกว่าจากไลบรารีมาตรฐาน
หมายเหตุทางเทคนิค: O(N) หมายถึงความซับซ้อนของเวลาแบบเชิงเส้น โดยเวลาในการประมวลผลเพิ่มขึ้นตามสัดส่วนกับขนาดของข้อมูลนำเข้า ในขณะที่ O(N²) บ่งชี้การเติบโตแบบกำลังสอง ซึ่งเวลาในการประมวลผลเพิ่มขึ้นตามกำลังสองของขนาดข้อมูลนำเข้า
โครงสร้างข้อมูลทางเลือกที่แนะนำ:
- Red/black trees
- Hash tables
- Vectors
- Deques
- Hives
 |
|---|
| การแสดงผลการเรียกใช้ฟังก์ชันในแผนภูมิเฟลมแสดงให้เห็นถึงผลกระทบด้านประสิทธิภาพของโครงสร้างข้อมูลใน Blender |
เกินกว่าการแก้ไขอย่างง่าย
ในขณะที่บางคนแนะนำการแก้ไขแบบรวดเร็ว เช่น การเพิ่มการเติมเลขศูนย์ (เช่น เปลี่ยนจาก %s.%u เป็น %s.%010u) ชุมชนได้เน้นย้ำถึงความสำคัญของการแก้ไขที่สาเหตุของปัญหามากกว่าการใช้วิธีแก้ปัญหาชั่วคราว สิ่งนี้นำไปสู่การอภิปรายที่กว้างขึ้นเกี่ยวกับหนี้ทางเทคนิคและความสำคัญของการเลือกโครงสร้างข้อมูลที่เหมาะสมตั้งแต่เริ่มต้น
ข้อดีของโอเพนซอร์ส
กรณีนี้แสดงให้เห็นทั้งจุดแข็งและข้อจำกัดของการพัฒนาซอฟต์แวร์แบบโอเพนซอร์ส ในขณะที่ความโปร่งใสทำให้สามารถวิเคราะห์และหาทางแก้ไขปัญหาได้อย่างละเอียด สมาชิกบางคนในชุมชนสังเกตว่าการตรวจสอบนี้ส่งผลให้เกิดการเขียนรายละเอียดการวิเคราะห์มากกว่าการมีส่วนร่วมในการแก้ไขโค้ดจริงผ่าน pull request
การอภิปรายนี้เป็นเครื่องเตือนใจว่าการปรับปรุงประสิทธิภาพมักต้องการการพิจารณาอย่างรอบคอบในการเลือกโครงสร้างข้อมูล และสิ่งที่ทำงานได้ดีสำหรับการดำเนินการขนาดเล็กอาจกลายเป็นปัญหาเมื่อขนาดข้อมูลเพิ่มขึ้น
อ้างอิง: A curious case of O(N^2) behavior which should be O(N)