Theppitak's blog

My personal blog.

02 พฤษภาคม 2558

LibThai/LibDATrie Optimization Summary

นับจาก blog เรื่องการ micro-optimize libthai ซึ่งได้ทดลองใช้ LIKELY/UNLIKELY ในการลดการสะดุดของ pipeline ของ CPU ขณะทำ branching ซึ่งลดเวลาของการตัดคำของ libthai ลงได้เพียง 0.014% เท่านั้น แต่ปรากฏว่าเมื่อไปทำกับ libdatrie กลับให้ผลที่ดีกว่านั้น

โค้ดที่เป็นคอขวดจริง ๆ คือ da_get_base(), da_get_check() ซึ่งใช้อ่านช่องข้อมูล double array โดยมีการตรวจสอบขอบเขตของค่า index ของ array ด้วย เมื่อใส่ LIKELY() กำกับเงื่อนไขที่จะไม่ error แล้ว ปรากฏว่าเวลาที่ใช้ในการตัดคำลดลงอย่างมากเมื่อเทียบกับจุดอื่น ๆ โดยทั่วไป

แต่ก็อย่าคาดหวังอะไรมากกับ micro-optimization เพราะเวลาที่ลดลงได้จากการ micro-optimize libdatrie รวมแล้วคือ 1.94% แต่เมื่อเทียบกับ 0.014% ที่ได้ใน libthai ก็ถือว่าน่าตื่นตาตื่นใจไม่น้อย

อย่างไรก็ดี ในช่วงต่อมา ก็ได้มี คำแนะนำจากคุณ edgehogapp ว่าสามารถลดเวลาตัดคำของ libthai ลงได้ ถ้าแปลงรหัสข้อความจาก TIS-620 เป็น Unicode เพียงครั้งเดียวก่อนวิเคราะห์ แทนที่จะแปลงทุกครั้งที่วิเคราะห์แต่ละตัวอักษร ซึ่งเมื่อทดลองแล้วก็ปรากฏว่าสามารถลดเวลาลงได้อีกถึง 0.28%

ก่อนที่จะเตรียมออกรุ่น libdatrie และ libthai รุ่นใหม่ จึงมาวัดเวลาสรุปอีกครั้ง ว่าการออปติไมซ์ส่วนไหนให้ผลเท่าไร โดยใช้ test case เดียวกัน เวลาที่ callgrind วัดได้ในแต่ละกรณีคือ:

  • libthai เก่า + libdatrie เก่า: 39,000,827
  • libthai เก่า + libdatrie ใหม่: 38,242,294 (ลดลง 1.94%)
  • libthai ใหม่ + libdatrie เก่า: 38,851,449 (ลดลง 0.38%)
  • libthai ใหม่ + libdatrie ใหม่: 38,089,676 (ลดลง 2.34%)

เมื่อคิดเป็นอัตราเร็วที่เพิ่มขึ้น (1 / (1 - อัตราส่วนเวลาที่ลดลง) - 1):

  • libthai เก่า + libdatrie ใหม่: เร็วขึ้น 1.98%
  • libthai ใหม่ + libdatrie เก่า: เร็วขึ้น 0.38%
  • libthai ใหม่ + libdatrie ใหม่: เร็วขึ้น 2.39%

กล่าวคือ ความเร็วที่เพิ่มขึ้นส่วนใหญ่มาจากการออปติไมซ์ libdatrie และโดยรวมแล้วทำให้การตัดคำเร็วขึ้น 2.39%

ในการวัด ครั้งก่อน ผมได้แยกวัดเฉพาะเวลาที่ใช้ในการตัดคำจริง ไม่นับเวลาโหลดพจนานุกรม เพราะไม่ได้มีการเปลี่ยนแปลงใน libdatrie แต่ครั้งนี้ การออปติไมซ์ libdatrie จะมีผลทั้งสองส่วน ซึ่งเมื่อแยกวัดดูก็ได้ผลดังนี้:

เวลาที่ใช้ในการโหลดพจนานุกรม:

  • libthai ใหม่ + libdatrie เก่า: 663,463
  • libthai ใหม่ + libdatrie ใหม่: 633,318 (ลดลง 4.54%; เร็วขึ้น 4.76%)

เมื่อคิดเฉพาะเวลาที่ใช้ในการตัดคำ:

  • libthai ใหม่ + libdatrie เก่า: 38,851,449 - 663,463 = 38,187,986
  • libthai ใหม่ + libdatrie ใหม่: 38,089,676 - 633,318 = 37,456,358 (ลดลง 1.92%; เร็วขึ้น 1.95%)

กล่าวคือ การ micro-optimize libdatrie ส่งผลต่อการโหลดพจนานุกรมมากกว่าการตัดคำ และเฉพาะสำหรับการตัดคำ มีผลมากกว่าการ micro-optimize ตัว libthai เอง อย่างมาก (ลดเวลาลง 1.92% เมื่อเทียบกับ 0.014% จาก libthai)

นอกเหนือจากการ micro-optimize แล้ว libdatrie ยังมีรายการแก้บั๊กอีกรายการหนึ่ง ซึ่งคุณ Sergei Lebedev ได้รายงานเข้ามาทางอีเมลส่วนตัว โดยอ้างถึง บั๊กใน python wrapper ของ libdatrie เกี่ยวกับการ iterate trie ที่ว่างเปล่า

เตรียมออกรุ่นใหม่เร็ว ๆ นี้ละครับ ทั้ง libdatrie และ libthai

ป้ายกำกับ: ,

hacker emblem