LibThai Thread-safety

อันเนื่องมาจากการที่ Pango 1.38.0 ที่ออกมาพร้อมกับ GNOME 3.18 ได้ตัดระบบ dynamic module ทิ้ง แล้วใช้วิธีรวมเข้าในซอร์สโค้ดเลย (GNOME #733882) ทำให้ผู้ดูแลหลัก คือ Behdad Esfahbod ได้มีโอกาสรื้อมอดูลภาษาต่าง ๆ รวมถึงภาษาไทย และพบประเด็นของ libthai ที่รองรับการตัดคำของมอดูลภาษาไทยอยู่ จึงได้ติดต่อมาที่ผมเพื่อให้แก้ไข โดยประเด็นสำคัญคือเรื่อง thread-safety

โค้ดใน libthai มีส่วนหนึ่งที่ทำให้ไม่ปลอดภัยเมื่อเรียกใช้ผ่าน thread หลาย thread พร้อมกัน ซึ่งเป็นส่วนที่ผมใช้ลดปริมาณการเรียก malloc() โดยยังไม่ free() โหนดทางเลือกต่าง ๆ ของการตัดคำที่เลิกใช้แล้วในทันที แต่เอาไปฝากไว้ใน free list เพื่อนำกลับมาใช้ใหม่ และไอ้เจ้า free list ที่เป็นเสมือนโกดังเก็บของเก่ารอ reuse นี่แหละ ที่ implement แบบ static โดยไม่มีการจองก่อนเข้าใช้ ทำให้เมื่อมีหลาย thread เข้าใช้พร้อมกันจะเกิด race condition ขึ้นได้

ประเด็นนี้ pango รุ่นนี้แก้ปัญหาเฉพาะหน้าด้วยการ ล็อคก่อนเรียก th_brk() เพื่อให้ thread ต่าง ๆ เข้าใช้ฟังก์ชันนี้ทีละ thread ซึ่งอาจกลายเป็นคอขวดของระบบหลาย thread ได้ ทางที่ดีคือทำให้ libthai threadsafe เสีย

ทางเลือกที่เป็นไปได้จึงมี 3 ทาง

1. ยกเลิก free list ไปเสีย (ซึ่ง Behdad สนับสนุน โดยให้เหตุผลว่า malloc() ใน libc รุ่นหลัง ๆ ทำงานเร็วขึ้นมากแล้ว และ CPU สมัยใหม่ก็ทำงานเร็วขึ้นมากแล้วด้วย จะไปนั่งออปติไมซ์ทำไมให้เมื่อยตุ้ม)
2. ใช้ free list 1 ชุดต่อ 1 thread แทนที่จะใช้ร่วมกันหมด (แต่ละ thread เก็บโหนดที่เลิกใช้ไว้ในกระเป๋า recycle ของใครของมัน ไม่ต้องใช้ร่วมกัน)
3. ใช้ free list กลางเหมือนเดิม แต่ให้มีระบบ lock (แต่ละ thread ต้องล็อคโกดังขณะเข้าใช้ thread อื่นต้องรอให้ thread ที่ใช้งานอยู่ใช้ให้เสร็จเสียก่อนจึงจะเข้าใช้ได้)

วิธียกเลิก free list อาจจะง่าย แต่ก่อนจะเชื่อก็ต้องวัดดูก่อน ซึ่งจากการทดลองของผมก็พบว่า th_brk() จะทำงานนานขึ้นถึง 18% ถ้าใช้ malloc() ตรง ๆ ทุกครั้ง หรือถ้าเทียบกลับ การใช้ free list สามารถประหยัดเวลาจากการใช้ malloc() ได้ถึง 15% ซึ่งผมถือว่ามีนัยสำคัญ ฉะนั้นจึงไม่เลือกวิธีนี้

จากนั้นจึงมาทดลองวิธีใช้ free list 1 ชุดต่อ 1 thread ซึ่งวิธีการก็ไม่ได้มีอะไรมาก เพียงแค่เปลี่ยนจากการใช้ตัวแปร static มาเป็นการสร้าง free list ใหม่ในการเรียก th_brk() แต่ละครั้งเท่านั้นเอง เนื่องจากตัว libthai เองไม่ได้สร้าง thread ใหม่อยู่แล้ว การสร้าง thread เกิดจากโค้ดผู้เรียกอย่าง pango หรือผู้ที่เรียก pango อีกทีทั้งสิ้น การสร้าง free list ต่อ 1 call ก็เท่ากับการสร้างต่อ 1 thread นั่นเอง

ผลการทดลองคือ free list แบบต่อ thread ก็ยังสามารถประหยัดเวลาได้ถึง 13% (2% ที่หายไปพบภายหลังว่าเกิดจากการสร้าง free list ผิดจากจุดเดิมในโค้ด ทำให้เกิดการสร้างและทำลาย free list เพิ่มขึ้น เมื่อแก้ให้ตรงกับจุดเดิมก็ปรากฏว่าประหยัดเวลาได้เท่าๆ ของเดิม) ซึ่งถือว่าน่าพอใจ

วิธีสุดท้ายที่ใช้ระบบล็อคนั้น จะทำให้ libthai ต้องมีการแทรกโค้ดการเรียก pthread เข้ามา ซึ่งทำให้โค้ดส่วนนี้ดูแปลกแยกไม่สวยงาม และในเมื่อวิธีที่ใช้ free list ต่อ thread ได้ผลเป็นที่น่าพอใจอยู่แล้ว ผมจึงไม่พิจารณาวิธีนี้อีก

จึงได้เป็น rev 577 (และแก้ไขเพิ่มเติมใน rev 583 หลังจากพบสาเหตุที่ทำให้การประหยัดเวลาลดลง 2%)

นอกจากนั้น ก็เป็นความพยายาม optimize การตัดคำของ libthai ต่อ ดังรายการต่อไปนี้:

• optimize libdatrie ในส่วน AlphaMap (การแม็ปอักขระให้เป็นดัชนีสำหรับ trie transition ซึ่งจะเกิด ทุกครั้ง ที่มี transition) จากการคำนวณหาลำดับของอักขระจากช่วงต่าง ๆ ที่กำหนด มาเป็นการเปิดตารางที่สร้างไว้ล่วงหน้า ฟังดูอาจจะนึกว่ามันคงเร็วขึ้นอย่างมโหฬาร แต่สำหรับ libthai แล้วไม่ใช่ เนื่องจากเรากำหนดช่วงอักขระภาษาไทยเป็นช่วงต่อเนื่องเพียงช่วงเดียว การคำนวณลำดับอักขระจึงไม่ซับซ้อน เพียงแค่ลบด้วยอักขระแรกของช่วงแล้วบวกด้วย 1 ก็จบแล้ว การทำงานที่ประหยัดได้จากการเปิดตารางจึงเป็นเรื่องของโสหุ้ยของการวนลูปเล็ก ๆ น้อย ๆ เท่านั้น ซี่งปรากฏว่าทำให้ตัวฟังก์ชันใช้เวลาทำงานลดลง 14.6% และทำให้การตัดคำของ libthai ใช้เวลาลดลงโดยรวม 0.2% เท่านั้น (libdatrie rev 277) แต่สำหรับ use case ที่อักขระอินพุตมีหลายช่วงไม่ต่อเนื่อง การเปิดตารางนี้จะช่วยประหยัดเวลาได้มาก
• optimize libthai ในส่วนของการยุบรวมกรณีตัดคำที่ตกตำแหน่งเดียวกัน (การตัดคำของ libthai ใช้วิธีลองตัดคำแบบต่าง ๆ เทียบกับพจนานุกรม แล้วเลือกเอาวิธีที่ได้จำนวนคำน้อยที่สุด โดยใช้การค้นแบบ best-first search ซึ่งคล้ายกับ breadth-first search แต่มีการคำนวณ heuristic ของกรณีต่าง ๆ และยุบรวมกรณีที่คืบหน้าเท่ากันเป็นระยะ ๆ) ซึ่งปรากฏว่าฟังก์ชัน brk_pool_match() ขึ้นชาร์ตฟังก์ชันที่กินเวลานานในรายงานของ Callgrind จึงพยายาม optimize ด้วยการทำให้ตัวฟังก์ชันเร็วขึ้นด้วยการแยกลูปเพื่อลด branching (rev 579 ตัวฟังก์ชันใช้เวลาลดลง 9.3%, runtime โดยรวมลดลง 0.067%) และด้วยการลดปริมาณงานของฟังก์ชันโดยค้นต่อจากจุดเดิมแทนการเริ่มที่ต้นลิสต์เสมอ (rev 582 ตัวฟังก์ชันใช้เวลาลดลง 8.85%, อันดับในชาร์ตเลื่อนลง 2 ขั้น, runtime โดยรวมลดลง 0.0388%) รวมแล้ว ตัวฟังก์ชันใช้เวลาลดลง 17.3% runtime โดยรวมลดลงประมาณ 0.1%

สรุปแล้ว การตัดตำของ libthai โดยรวมใช้เวลาลดลงประมาณ 0.28% (รวมเวลาโหลดพจนานุกรม) พร้อมกับปลอดภัยสำหรับการทำงานหลาย thread โดยไม่ต้องล็อคด้วย

ถ้าไม่มีไอเดียใหม่อีก ก็คงจะออกรุ่นใหม่เร็ว ๆ นี้ครับ

ในอีกด้านหนึ่ง ทีม debian-cd ได้กระทุ้งมาอีกครั้งว่าช่วยทำ udeb ของ libthai ให้หน่อย จะได้ใช้ในโปรแกรมติดตั้งของเดเบียน (Debian #800369) ก็ทยอยทำตั้งแต่ libdatrie1-udeb (0.2.9-3) รอจนผ่าน NEW queue แล้วก็ทำ libthai-data-udeb และ libthai0-udeb ต่อ (ขณะที่เขียน blog ยังรออยู่ใน NEW)