Theppitak's blog

My personal blog.

05 กุมภาพันธ์ 2558

Yet Another LibThai Optimization Effort

ความพยายามในการ 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

ป้ายกำกับ:

0 ความเห็น:

แสดงความเห็น (มีการกลั่นกรองสำหรับ blog ที่เก่ากว่า 14 วัน)

<< กลับหน้าแรก

hacker emblem