Theppitak's blog

My personal blog.

27 ธันวาคม 2551

LibThai Optimization

การปรับไปใช้ datrie 32 บิต ก็ทำให้ libthai สามารถเพิ่มคำในพจนานุกรมได้อีกเยอะ แต่ปรากฏว่า ราคาที่ต้องจ่ายไป นอกเหนือจากการใช้หน่วยความจำเพิ่มขึ้นอีกเท่าตัว (จาก 16 บิตเป็น 32 บิต) ก็คือ performance ที่ตกลงอีกราว 66% จากเวลาในการโหลดพจนานุกรมที่นานขึ้น และปริมาณการ access หน่วยความจำที่เพิ่มขึ้น

แต่การเพิ่มขนาดของ trie ก็เป็นเรื่องจำเป็นสำหรับการตัดคำไทย เพราะภาษาไทยมีจำนวนคำมากกว่าที่ trie 16 บิตจะรองรับได้ เพราะฉะนั้น ก็เลยต้องมาปรับปรุงเรื่องประสิทธิภาพ

เครื่องมือที่ใช้ช่วย ก็คือ valgrind โดยเขียนโปรแกรมง่าย ๆ ขึ้นมาลิงก์กับ libthai เพื่อทดสอบ

แต่ก่อนอื่น เนื่องจาก libthai มีการใช้งานอยู่ในระบบ ผมจึงเลี่ยงการกระทบกับระบบระหว่างทดสอบ ด้วยการติดตั้ง libthai และ datrie ฉบับ CVS ลงใน $HOME/libthai โดยตั้งตัวแปรระบบดังนี้:

$ export PATH=$HOME/libthai/bin:$PATH
$ export PKG_CONFIG_PATH=$HOME/libthai/lib/pkgconfig
$ export LD_LIBRARY_PATH=$HOME/libthai/lib

แล้วใช้ configure option สำหรับ datrie และ libthai ดังนี้:

$ ../configure CFLAGS="-Wall -g -O0" --prefix ~/libthai

คอมไพล์ ติดตั้ง ตามปกติ จากนั้นก็มาเขียนโปรแกรมทดสอบแบบง่าย:

#include <string.h>
#include <stdio.h>

#include <thai/thbrk.h>

int main ()
{
    char line [1024];
    char bline [1024];

    while (fgets (line, sizeof line, stdin)) {
        if (line [strlen (line) - 1] == '\n')
            line [strlen (line) - 1] = '\0';

        th_brk_line (line, bline, 1024, "|");
        printf ("%s\n", bline);
    }

    return 0;
}                                   

คอมไพล์โปรแกรมทดสอบ:

$ cc -o wbrk-test `pkg-config --cflags --libs libthai` wbrk-test.c

แล้วใช้ valgrind ตรวจสอบ โดยเริ่มจาก Memcheck:

$ cat testmsg | valgrind --leak-check=yes ./wbrk-test

เจอ memory leak จากการเปิดพจนานุกรมเป็น static data ซึ่งเป็นความจงใจ เพื่อให้โปรแกรมที่มาลิงก์กับ libthai ไม่จำเป็นต้องโหลดพจนานุกรมจนกว่าจะได้เรียกรูทีนตัดคำไทยจริง ๆ เป็นการโหลดเพียงครั้งเดียว แล้วใช้ในครั้งต่อ ๆ ไป แต่การทิ้ง memory leak ไว้ก็ไม่สวย โดยเฉพาะโปรแกรมที่โหลด libthai ด้วย dlopen() จะทิ้งร่องรอยไว้หลังจาก dlclose() ไปแล้ว ความจริงอยากแก้นานแล้ว ก็ถือโอกาสแก้เสียเลย (commit เข้า CVS ไปแล้ว)

หมดจากกรณีนี้ ก็ไม่มี memory leak เหลืออยู่อีกเลย ว้าว รอดตัวไป

จากนั้น ก็วัดประสิทธิภาพ หาจุดคอขวดด้วย Callgrind:

$ cat testmsg | valgrind --tool=callgrind ./wbrk-test

สำหรับผลลัพธ์ที่ Callgrind เขียนออกมานั้น คู่มือ เขาแนะนำให้เปิดดูด้วย KCachegrind แต่ทราบมาว่า Alleyoop หรือกระทั่ง Anjuta ก็ใช้เป็น frontend ได้เหมือนกัน แต่ผมมันพวกขี้เกียจ เพราะกว่าจะเซ็ตอะไร ๆ ให้พร้อมใช้ก็คงนาน อีกทั้งไม่แน่ใจว่าจะสามารถตั้ง environtment ต่าง ๆ ได้อย่างใจหรือเปล่า เลยเล่นง่าย ๆ ไปก่อน ด้วยการเปิดดูด้วย vim แล้วแกะข้อมูลตาม เอกสารทางเทคนิค ก็ทำให้เจอคอขวดได้เหมือนกัน

ที่ผ่านมา ก็ลดคอขวดไปได้สองแห่ง ลดเวลาลงได้ราว 15% ก็ต้องพยายามกำจัดจุดอ่อนต่อไป

การ optimize โดยใช้ Callgrind ช่วยในครั้งนี้ เป็นการ optimize โค้ดล้วน ๆ ด้วยการ implement ตรรกะเดิมให้เร็วขึ้น ยังไม่ใช่การทำ cut-off ในระดับตรรกะเหมือน รอบที่แล้ว ที่ทำหลังจากเปลี่ยนมาใช้พจนานุกรมภายนอก

ปล. พักหลัง ๆ นี้ ผมเขียน blog ด้วยการ "เล่าข่าวคราว" เท่านั้น ว่าทำอะไรคืบหน้าไปบ้าง โดยไม่ได้ลงรายละเอียดทางเทคนิค ก็หวังว่าการ blog โดยเพิ่มรายละเอียดด้วย จะเป็นประโยชน์กับผู้อ่านมากขึ้นบ้าง รวมทั้งกับตัวผมเองในอนาคตด้วย เป็นบันทึกกันลืม

ป้ายกำกับ:

19 ธันวาคม 2551

datrie migrations

นับจาก blog ที่แล้ว เรื่อง datrie ก็ได้ทำเพิ่มอีกนิดหน่อย และออก Alpha 1 และ Alpha 2 สำหรับ libdatrie 0.2.0 เพื่อให้มีรุ่นอ้างอิงสำหรับการ configure ซอร์สของ libthai และ swath ที่จะย้ายมาใช้ libdatrie1

ล่าสุด ก็ได้ ย้ายทั้ง libthai และ swath มาใช้ libdatrie1 เรียบร้อยแล้วใน CVS ซึ่งทำให้ขณะนี้:

  • libthai สามารถเพิ่มคำในพจนานุกรมต่อได้แล้ว เมื่อข้อจำกัดเรื่องจำนวนคำหมดไป
  • swath สามารถปรับแก้พจนานุกรมได้แล้ว หลังจากที่ติดปัญหาเรื่องบั๊กในโค้ด Trie รุ่นดึกดำบรรพ์มานาน

เพราะฉะนั้น ผู้ใช้แพกเกจทั้งสอง ไม่ว่าจะใช้ libthai ตัดคำผ่าน Firefox/Iceweasel (บนลินุกซ์เท่านั้น), Epiphany, Konqueror หรือโปรแกรมบน GNOME/KDE อื่น ๆ หรือใช้ swath ในการตัดคำสำหรับ LaTeX หรือ HTML ทั่วไป แล้วพบกรณีการตัดผิด ก็กรุณาแจ้งให้ผมทราบด้วยนะครับ จะทาง blog นี้หรือทาง t-l-f-d mailing list ก็ได้ เพื่อที่จะได้พิจารณาเพิ่มคำในพจนานุกรมต่อไป

ส่วนถ้าเป็นกรณีกำกวม เช่น "ตากลม" นี่ เป็น known bug นะครับ เพราะทั้งสองตัวนี้ ยังไม่มีการใช้ข้อมูลสถิติใด ๆ ทั้งสิ้นมาประกอบการตัดคำ

ป้ายกำกับ: ,

08 ธันวาคม 2551

Unicode datrie

จาก แผนงานครั้งที่แล้ว ที่ได้วางแผนปรับฟอร์แมตของแฟ้มและปรับ API ไปนั้น ตอนนี้ทำเสร็จไปแล้วใน CVS

ในครั้งนี้ ได้เพิ่มข้อมูล alphabet map ลงในแฟ้ม trie ด้วย จากเดิมที่แยกโค้ด Trie กับ SBTrie (single-byte-domain trie) ออกจากกัน โดย SBTrie เป็น wrapper สำหรับแปลงรหัสอักขระไบต์เดียว (TIS-620 หรือรหัส 8 บิตอื่น ๆ) ให้เป็นชุดอักขระที่เป็นโดเมนของ trie คือเป็นค่าลำดับ 1, 2, 3, ... ของแต่ละอักขระเป็นค่าต่อเนื่องกัน เพื่อจำกัดขนาดของโดเมน และเพิ่มความกระชับของ sparse table ที่แทน transition ของแต่ละ state โดยในครั้งนี้ ได้ตัดสินใจผนวก map นี้เข้าใน Trie เสียเลย และเขียนข้อมูลลงในแฟ้มไบนารีของ trie ด้วย เพื่อลดความสับสนของการแยกแฟ้ม *.sbm ใน datrie รุ่นก่อน

แต่ก็หมายความว่า แผนเดิมที่คิดจะทำ wrapper แยกระหว่างรหัสอักขระ 8 บิตกับยูนิโค้ด เช่น SBTrie, UniTrie, ... ก็กลายเป็นว่าต้องรองรับทุกอย่างในโค้ดเดียว จึงถือโอกาสเพิ่มแผนงานอีกอย่าง คือรองรับยูนิโค้ดไปเลย แล้วให้ client แปลงทุกอย่างให้เป็นยูนิโค้ดเอา หรือจะใช้รหัส 8 บิตตามเดิมแต่เก็บในเนื้อที่อักขระ 32 บิตแทนก็ตามแต่ เพราะไม่ว่าจะมาแบบไหน trie ก็จะแปลงเป็นโดเมนของ trie อยู่แล้ว ขอให้ใช้รหัสแบบเดียวกันทั้งตอนสร้าง trie และตอนสืบค้นเป็นอันใช้ได้

ขณะที่แก้ ๆ ไปนั้น กลายเป็นการแก้โค้ดขนานใหญ่ เพราะมีหลายประเด็นให้ทำพร้อมกัน โดยที่ไม่สามารถทดสอบโค้ดในระหว่างกลางได้เลย เพราะเป็นการแก้ API ไปด้วย จึงคอมไพล์ไม่ผ่านจนกว่าจะแก้เสร็จ

เพราะฉะนั้น จึงแยกแพตช์ที่จะ commit นั้นออกเป็นแพตช์ย่อย ๆ ทำทีละเรื่อง เพราะในโครงการซอฟต์แวร์ใด ๆ ก็ตาม:

อย่าทำทุกอย่างในแพตช์เดียว ให้แยกแพตช์เป็นเรื่อง ๆ ค่อย ๆ เปลี่ยนทีละขั้น

การค่อย ๆ เปลี่ยนทีละขั้นนี้ เปิดโอกาสให้ได้ทดสอบและแก้บั๊กทีละเรื่องได้ ช่วยลดโอกาสการเกิดบั๊ก และลดความซับซ้อนในการดีบั๊กได้

ก็เลย checkout CVS ออกมาอีกชุดหนึ่ง แล้วแยกร่างแพตช์ใหญ่นั้นมาทำทีละเรื่อง พร้อมทดสอบก่อน commit ทุกขั้น ขั้นที่ทำเพิ่มไปก็คือ:

  • ผนวก alphabet map เข้าใน class Trie และตัด class SBTrie ออกไป (เขียนภาษาซีแต่เรียก class ซะงั้น เพราะแนวคิดในการออกแบบก็เป็นกึ่ง ๆ OOP อยู่แล้ว)
  • ปรับ API เพื่อให้สามารถใช้ trie แบบไม่อ่าน-เขียนแฟ้มได้ด้วย โดยยังมีเมธอดให้อ่านเขียนแฟ้มได้ถ้าต้องการ

ขั้นต่อไปที่จะทำ ซึ่ง blog นี้จะบอกกล่าวไว้ก่อนสำหรับผู้ที่อาจจะนำ datrie ไปใช้ คือต่อไป datrie จะใช้อักขระขนาด 32 บิตแล้ว แต่ชุด alphabet ที่รองรับ ก็ยังคงจำกัดที่ไม่เกิน 255 ตัวอยู่ดี เพราะไม่มีประโยชน์ที่จะรองรับ alphabet ขนาดโต ๆ (เช่นภาษาจีน) เนื่องจาก transition table จะกว้างเกินเหตุ และทำให้แฟ้ม trie ใช้เนื้อที่อย่างไม่มีประสิทธิภาพ

ช่วงนี้ขอจดจ่อหน่อยนะครับ เรื่องอื่นขอพักไว้ก่อน

ป้ายกำกับ: ,

03 ธันวาคม 2551

32-bit datrie

จากที่เคย เกริ่น ไว้นานแล้ว ถึงปัญหาเรื่อง dict ใน swath ที่เพิ่ม-ลบคำไม่ได้ จำเป็นต้องแทนที่โค้ด trie ด้วย datrie ตัวใหม่ แต่มีปัญหาว่า datrie นั้นใช้ node index ขนาด 16 บิต ซึ่งทำให้จำนวนโหนดไม่เพียงพอกับรายการคำของ swath ประกอบกับปัญหา dict ตัดคำของ libthai ก็มาชนลิมิตนี้เหมือนกัน รวมทั้งมีผู้รายงานเข้ามาบ่อย ว่าต้องการเพิ่มคำให้ได้มากกว่านี้ ก็สรุปว่าต้องแก้ datrie ให้รองรับ node index ขนาดใหญ่ขึ้น

ก็ได้ ประกาศแผน ใน thai-linux-foss-devel mailing list ว่าจะตัดสินใจ break ABI โดยล้มเลิกความคิดเรื่อง backward compatibility กับ trie 16 บิต หรือการใช้ index 24 บิต แต่จะใช้ index 32 บิตอย่างเดียวไปเลย เพื่อความเรียบง่ายของโค้ด พร้อมกันนี้ก็ถือโอกาสปรับ API ให้รองรับการใช้งานที่กว้างขึ้นด้วย สรุปแผนคือ:

  • แตก branch r_0_1_x-branch สำหรับ maintain datrie 0.1.x แล้วพัฒนารุ่นใหม่ใน HEAD ซึ่งจะมุ่งสู่รุ่น 0.2.0 ต่อไป
  • break ABI โดยเปลี่ยน SONAME ของไลบรารีเป็น libdatrie.so.1
  • เปลี่ยนขนาดของ node index จาก 16 บิต เป็น 32 บิต
  • ปรับฟอร์แมตของแฟ้ม จากเดิมที่แยกเป็น *.br และ *.tl ให้รวมอยู่ในแฟ้มเดียว
  • ปรับ API จากที่ต้องอ่าน-เขียนกับแฟ้มเสมอ ให้กลายเป็นแค่ทางเลือกหนึ่งในการ load/save เท่านั้น และให้ใช้ trie ใน memory ล้วน ๆ ได้ด้วย

ตอนนี้ใน CVS ได้ใช้ node index ขนาด 32 บิตแล้ว รวมทั้งปรับโค้ดเรื่องการจัดการ overflow นิดหน่อย ขั้นต่อไปคือทำเรื่อง API และฟอร์แมตของแฟ้ม

ป้ายกำกับ: , ,

02 ธันวาคม 2551

The Smiling Moon

ไม่ได้ blog เรื่องวิทยาศาสตร์-ดาราศาสตร์เสียนาน จนกระทั่งเกินพระจันทร์ยิ้มเมื่อคืนนี้ ก็โชคดี เก็บรูป ได้นิดหน่อย

โอกาสเก็บรูปปรากฏการณ์จริง ผ่านมาแล้วก็ผ่านไป ไม่หวนกลับมาอีก เป็นประสบการณ์ที่ยากจะพบอีกครั้ง เพราะดาวเคียงเดือนแต่ละครั้ง ไม่บ่อยนักที่จะมีดาวมาเคียงถึงสองดวง และโดยเฉพาะอย่างยิ่ง มาจัดเรียงหันข้างจนเป็นรูปหน้ายิ้มได้อย่างนี้

เพื่อดูว่าช่วงเวลาที่พระจันทร์ยิ้มนั้น สั้นแค่ไหน ก็ลองจำลองด้วย stellarium ดู โดยอาศัยพิกัดจังหวัดขอนแก่น (ประมาณ 16.11 องศาเหนือ 102.84 องศาตะวันออก) เป็นจุดสังเกตการณ์:

วันที่ 30 พ.ย. เวลา 19.10 น.

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

Stellarium shot for 2008-11-30 19:10 +0700

วันที่ 1 ธ.ค. เวลา 05.12 น.

เราตามดวงจันทร์ที่ตอนนี้ไปโผล่ที่อีกซีกโลกหนึ่ง และเตรียมจะขึ้นทางทิศตะวันออกในตอนสายต่อไป รูปนี้มองจากขอนแก่นเหมือนเดิม โดยตัดพื้นโลกแล้วมองทะลุโลกลงไป ตอนนี้ดวงจันทร์เคลื่อนเข้าใกล้ดาวทั้งสองมากขึ้น ถ้าคนที่อเมริกาดูดวงจันทร์ยามเย็นทางทิศตะวันตกในตอนนี้ ก็คงพอจะเห็นเค้าหน้ายิ้มที่เรียวยาวมาก ๆ ได้

Stellarium shot for 2008-12-01 05:12 +0700

วันที่ 1 ธ.ค. เวลา 12.00 น.

ทิ้งช่วงมาอีกราว 7 ชั่วโมง หลังจากดวงจันทร์ขึ้นไปแล้วในตอนสาย ตอนนี้ไต่ท้องฟ้าขึ้นมาทางตะวันออกเฉียงใต้ มุมเงยประมาณ 30 องศา ระยะห่างจากดาวทั้งสองลดลงเรื่อย ๆ เป็นการแอบเตรียมการแสดงคืนนี้ โดยอาศัยแสงอาทิตย์เวลากลางวันบังไว้

Stellarium shot for 2008-12-01 12:00 +0700

วันที่ 1 ธ.ค. เวลา 18.15 น.

Show Time! เมื่อดวงอาทิตย์ลับขอบฟ้าไป ดาวทั้งสามที่กำลังจะตกตามไปด้วยทางทิศตะวันตกก็เริ่มปรากฏโฉม เผยรอยยิ้มกริ่มให้ชาวเอเชียได้ชมเป็นบุญตา ที่มุมเงยประมาณ 25 องศา

Stellarium shot for 2008-12-01 18:15 +0700

วันที่ 1 ธ.ค. เวลา 20.23 น.

Bye Bye Thailand ภาพสุดท้ายที่พระจันทร์ยิ้มปรากฏให้ชาวไทยได้ยลโฉม ก่อนที่จะลับขอบฟ้าไป ตอนนี้หน้ายิ้มเริ่มกลมป้อมขึ้น เพราะดวงจันทร์เคลื่อนเข้าใกล้ดาวทั้งสองมากขึ้น 2-3 ชั่วโมงเศษที่ผ่านมา คือเวลาที่เรามีสำหรับเก็บภาพประวัติศาสตร์นี้!

Stellarium shot for 2008-12-01 20:23 +0700

วันที่ 1 ธ.ค. เวลา 23.51 น.

The End ดวงจันทร์เคลื่อนเข้าแทรกกลางระหว่างดาวทั้งสอง สิ้นสุดการยิ้มครั้งนี้ ถือว่าชาวโลกที่อยู่ในเขตเวลาประมาณ GMT+01 คือแถว ๆ เยอรมนี อิตาลี เป็นเขตสุดท้ายที่จะทันเห็นช่วงสุดท้ายของการยิ้ม

Stellarium shot for 2008-12-01 23:51 +0700

วันที่ 2 ธ.ค. เวลา 05.21 น.

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

Stellarium shot for 2008-12-02 05:21 +0700

วันที่ 2 ธ.ค. เวลา 12.09 น.

ระหว่างกลางวันที่แอบซ่อนในแสงแดด ดวงจันทร์ก็เคลื่อนห่างจากดาวทั้งสองออกไปเรื่อย ๆ

Stellarium shot for 2008-12-02 12:09 +0700

วันที่ 2 ธ.ค. เวลา 18.23 น.

แล้วคืนนี้เราจะเห็นอะไร? พระจันทร์ตีลังกาหน้าบึ้งเหรอ? คิดว่าไม่ เพราะดวงจันทร์ได้เคลื่อนห่างจากดาวทั้งสองไปมาก จนมองเป็นรูปหน้าได้ยากแล้ว หรือถ้าจะพยายามมอง ก็คงต้องมองกว้างหน่อย

Stellarium shot for 2008-12-02 18:23 +0700

ฟู่.. กว่าจะเขียนจบ เล่นเอาหลายชั่วโมง ไม่ใช่ว่าเขียนยากหรือ simulate ยากหรอก แต่ตั้งแต่เริ่มเขียนจนเขียนเสร็จ ต้องลุกไปทำโน่นทำนี่หลายเรื่อง เลยเขียนได้ไม่ต่อเนื่อง..

ป้ายกำกับ: ,

hacker emblem