ความพยายามในการ optimize libthai ยังคงดำเนินต่อไป หลังจากที่ได้ ปรับอัลกอริทึม ไปแล้วในรุ่น 0.1.21 ที่ได้ลดเวลาการ recover จาก error ลง
ทำแคชให้กับกระบวนการ recover (ไม่สำเร็จ)
รอบนี้ ผมได้พยายามลดจำนวนการ recover ลง แต่ต้องล้มเลิกในที่สุด
แนวคิดคือ การ recover จากจุดใดจุดหนึ่งจะได้คำตอบเหมือนเดิมไม่ว่าจะคำนวณกี่ครั้ง และในเมื่ออัลกอริทึมที่ผมใช้มีการพิจารณากรณีต่าง ๆ หลายกรณี จึงมีโอกาสที่กรณีเหล่านั้นจะมาพบ error ที่จุดเดียวกัน การเก็บแคชของจุด recover ไว้จึงช่วยให้ไม่ต้องคำนวณซ้ำอีก
ในโค้ดเดิมของ libthai มีการทำแคชอย่างง่ายไว้ โดยเก็บผลการ recover ครั้งล่าสุดไว้ ซึ่งแม้ hit rate จะต่ำมาก แต่ก็กลับช่วยลดเวลาได้ ถ้าเอาโค้ดนี้ออกเวลาที่ใช้จะเพิ่มขึ้น แนวคิดที่จะทำครั้งนี้คือขยายแคชให้ครอบคลุมทั้งข้อความ ซึ่งจากการทดลอง ผลที่ได้คือสามารถลดจำนวนการ recover ได้มากขึ้นจริง แต่โสหุ้ยของการทำแคชก็เพิ่มขึ้นด้วย และด้วย hit rate ที่ยังต่ำอยู่ ทำให้เวลาที่ลดได้ไม่สามารถหักลบกับเวลาที่เพิ่มขึ้นจากการ access แคชทุกรอบได้ ไม่ว่าจะลดโสหุ้ยต่าง ๆ ของแคชลงเท่าใดก็ตาม สรุปคือผมต้องโยนแพตช์นี้ทิ้ง เพราะการทำแคชกลับทำให้ใช้เวลาเพิ่มขึ้น!
อย่างไรก็ดี สิ่งที่ได้คือการได้พิสูจน์ว่าวิธีนี้ใช้ไม่ได้ ไม่ต้องพยายามอีก ไปหาวิธีอื่นต่อไป แต่ก็ขอเขียนบันทึกเป็น blog เพื่อช่วยเตือนความจำตัวเองในอนาคต
บทเรียน:
- จะทำแคช ให้ระวังโสหุ้ยของแคชด้วย
- ถูกย้ำเตือนอีกครั้งว่า
malloc() นั้นโสหุ้ยสูงมาก (แพตช์แรกผมใช้ malloc() จองแคช ปรากฏว่าเวลาพุ่งกระฉูด แพตช์ต่อมาจึงปรับเป็น fixed array แทน)
- แนวคิดในการ optimize ไม่สามารถสรุปเอาเองด้วยหลักเหตุผลได้ ควรพิสูจน์ด้วย profiler เสมอ
Micro-optimization ด้วย LIKELY/UNLIKELY
แนวคิดถัดมาคือการใช้ ส่วนขยายของ GCC คือ __builtin_expect() ที่ใช้ช่วยคอมไพเลอร์สร้างโค้ดที่ลดการสะดุดของ pipeline ของ CPU เมื่อมี branching (ด้วยการจัดให้โค้ดของ branch ที่ทำงานบ่อยวางต่อจาก condition เพื่อให้ถูก fetch มารอในแคชไว้) โค้ดในโครงการต่าง ๆ ได้สร้างเป็นแพตเทิร์น LIKELY และ UNLIKELY ไว้ใช้ เช่น Linux kernel, GLib ของ GNOME, MFBT ของ Mozilla
ผมเห็นโค้ดเหล่านี้มาพอสมควร และคิดจะใช้ในโค้ดของตัวเองอยู่เหมือนกัน แต่ก่อนที่จะใช้ก็ควรทดลองเสียก่อน ว่ามันช่วยได้จริงไหม และได้มากน้อยแค่ไหน
มีคนเขียน blog เรื่อง How much do __builtin_expect(), likely(), and unlikely() improve performance? ไว้ พร้อมโค้ดทดสอบ ผมลองเลียนแบบตามเล่น ๆ เมื่อนานมาแล้ว ก็ไม่พบความแตกต่างอย่างมีนัยสำคัญ ทั้งนี้เพราะเครื่องมือที่ใช้วัด คือคำสั่ง time ไม่ได้ละเอียดพอ และเวลาที่ใช้รันโปรแกรมแต่ละครั้งก็ไม่เท่ากัน ขึ้นอยู่กับโหลดของระบบในขณะนั้นด้วย แต่รอบนี้ผมต้องการคำตอบจริงจังขึ้น จึงเปลี่ยนไปใช้ callgrind วัด ซึ่งได้ค่าละเอียดและเที่ยงตรงกว่า
โค้ดทดสอบ:
#include <stdio.h>
#ifndef NOLIKELY
#define LIKELY(expr) (__builtin_expect (!!(expr), 1))
#define UNLIKELY(expr) (__builtin_expect (!!(expr), 0))
#else
#define LIKELY(expr) (expr)
#define UNLIKELY(expr) (expr)
#endif
#define N_LOOP 10
#define N_DATA 8300000
static __attribute__ ((noinline)) int
count (int a)
{
return ++a;
}
int main ()
{
char p[N_DATA];
int i, j;
int c1, c2;
for (i = 0; i < N_DATA; i++) {
p[i] = (i % 10 == 0) ? 1 : 0;
}
c1 = c2 = 0;
for (j = 0; j < N_LOOP; j++) {
for (i = 0; i < N_DATA; i++) {
if (LIKELY (p[i] == 0)) {
c1 = count (c1);
} else {
c2 = count (c2);
}
}
}
printf ("Likely: %d, Unlikely: %d\n", c1, c2);
return 0;
}
คอมไพล์:
$ cc -O2 likely.c -o likely
$ cc -O2 -DNOLIKELY likely.c -o nolikely
ทดสอบด้วยคำสั่ง time:
$ time ./nolikely
Likely: 74700000, Unlikely: 8300000
real 0m0.282s
user 0m0.272s
sys 0m0.008s
$ time ./likely
Likely: 74700000, Unlikely: 8300000
real 0m0.280s
user 0m0.272s
sys 0m0.004s
ไม่ได้แตกต่างกันมาก และวัดแต่ละเที่ยวก็ได้ค่าต่างกันจนถือว่าผลหยาบเกินไป ไม่สามารถเทียบกันได้
ทดสอบด้วย callgrind ซึ่งวัดแต่ละเที่ยวได้ค่าเดิมอย่างสม่ำเสมอ:
$ valgrind --tool=callgrind ./nolikely
==16287== Callgrind, a call-graph generating cache profiler
==16287== Copyright (C) 2002-2013, and GNU GPL'd, by Josef Weidendorfer et al.
==16287== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==16287== Command: ./nolikely
==16287==
==16287== For interactive control, run 'callgrind_control -h'.
Likely: 74700000, Unlikely: 8300000
==16287==
==16287== Events : Ir
==16287== Collected : 938005876
==16287==
==16287== I refs: 938,005,876
$ valgrind --tool=callgrind ./likely
==16313== Callgrind, a call-graph generating cache profiler
==16313== Copyright (C) 2002-2013, and GNU GPL'd, by Josef Weidendorfer et al.
==16313== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==16313== Command: ./likely
==16313==
==16313== For interactive control, run 'callgrind_control -h'.
Likely: 74700000, Unlikely: 8300000
==16313==
==16313== Events : Ir
==16313== Collected : 938005846
==16313==
==16313== I refs: 938,005,846
ผลที่ได้คือ callgrind วัดความแตกต่างของเวลาที่ใช้เมื่อใช้ LIKELY และ UNLIKELY ได้ แต่มีข้อสังเกตคือ
- สามารถลดเวลาลงได้เพียงเล็กน้อยเท่านั้น (ซึ่งก็ควรเป็นเช่นนั้น เรารู้ว่านี่คือ micro-optimization)
- ต้องคอมไพล์แบบออปติไมซ์ (
-O2 ขึ้นไป ซึ่งเปิดใช้ตัวเลือก -freorder-blocks) ถ้าไม่ออปติไมซ์ ผลจะไม่แน่นอน บางกรณีได้โค้ดที่ทำงานเร็วขึ้น บางกรณีได้โค้ดที่ทำงานช้าลง
- ถ้าใช้
LIKELY/UNLIKELY ในทางกลับกับที่ควรจะเป็น จะได้โค้ดที่ทำงานช้าลงเสมอ
นั่นคือสิ่งที่สังเกตได้ และเมื่อนำมาใช้กับ LibThai จริง ๆ ก็ได้พบกับความงุนงง เพราะจุดแรกที่ผมนำมาใช้ก็คือ การลดโสหุ้ยของแคชของการ recover ดังที่กล่าวไปข้างต้น โดยได้วัด hit rate คร่าว ๆ ซึ่งต่ำกว่า 2% และแน่ใจว่าการ hit cache นั้นควรใช้ UNLIKELY แน่ ๆ แต่ผลที่ได้คือ มันใช้เวลาเพิ่มขึ้น! (การใช้ LIKELY แทนก็ให้ผลไม่ต่างกัน)
ผมยังไม่สามารถเข้าใจได้ว่าทำไม มันอาจไปรบกวน dynamic branch prediction ของ CPU หรืออย่างไรก็ไม่ทราบได้
หลังจากโยนแพตช์เรื่องแคชของการ recover ทิ้งไปแล้ว ผมก็ถอยกลับมาลอง LIKELY และ UNLIKELY กับกรณีอื่นที่มีความแน่นอน 100% เช่น กับ lazy initialization ที่ทำงานเพียงครั้งเดียวเท่านั้น และกับ error handling ในกรณีที่ malloc() ไม่สำเร็จ ซึ่งปรากฏว่า มันลดเวลาได้จริง ๆ แฮะ
กล่าวคือ ลดเวลาที่ callgrind วัดได้ จาก 44,313,933 ลงเหลือ 44,307,666 คิดเป็น 0.014%
ถือว่าน้อยนิดสำหรับเป้าประสงค์ที่ต้องการ คือการ optimize LibThai แต่สิ่งที่ผมได้มากกว่านั้นคือการได้เรียนรู้ธรรมชาติของ LIKELY/UNLIKELY ว่าควรใช้กับเงื่อนไขที่แน่ใจ 100% เท่านั้น อย่าใช้พร่ำเพรื่อ!
และได้เข้าใจลึกซึ้งถึงสิ่งที่คู่มือ GCC เขียนไว้ว่า...
...as programmers are notoriously bad at predicting how their programs actually
perform...
เข้าใจแล้วคร้าบ... <(_ _)>
หมายเหตุ: commit ไปแล้วครับ โครงการต่อไปคือ หาทาง optimize libdatrie
ป้ายกำกับ: libthai
