Pretty Feb Calendar Solution

ใน blog ที่แล้ว ผมได้ตั้งคำถามเกี่ยวกับปฏิทินที่ลงตัวของเดือนกุมภาพันธ์ว่ามีปีใดบ้าง ปรากฏว่ามีผู้ร่วมสนุกมาใน คอมเมนต์ โดยคิดแยกเป็นกรณีต่าง ๆ ของการเลื่อนวันในสัปดาห์ของวันที่เดิมของแต่ละปี

ก่อนอื่น เงื่อนไขของปีปฏิทินสวยก็คือ วันที่ 1 กุมภาพันธ์ของปีนั้นจะตรงกับวันอาทิตย์ และปีนั้นต้องเป็นปีปกติสุรทิน คือเดือนกุมภาพันธ์มี 28 วัน

คุณ Hisoft Manager ได้ตรวจสอบการเลื่อนวันในสัปดาห์ของวันที่ 1 กุมภาพันธ์ของแต่ละปีที่ติดกัน และแยกอธิบายเป็นกรณี ๆ ความคิดเริ่มแรกผมก็คิดด้วยวิธีคล้าย ๆ กันนี้ โดยคิดเป็นเศษเหลือจากการหารด้วย 7 โดยในปีปกติสุรทินซึ่งมี 365 วัน จะทำให้ 1 กุมภาพันธ์ของปีถัดไปเลื่อนวันในสัปดาห์ไป 1 วัน (365 หารด้วย 7 เหลือเศษ 1) และในปีอธิกสุรทินซึ่งมี 366 วัน จะทำให้ 1 กุมภาพันธ์ของปีถัดไปเลื่อนวันในสัปดาห์ไป 2 วัน (366 หารด้วย 7 เหลือเศษ 2) จากนั้นก็ใช้เงื่อนไขนี้ตรวจสอบรูปแบบการเลื่อนที่ทำให้ 1 กุมภาพันธ์เลื่อนกลับมาตรงกับวันอาทิตย์อีกครั้ง โดยมีเงื่อนไขเพิ่มเติมว่าปีนั้นต้องไม่เป็นปีอธิกสุรทินด้วย

ผลที่ได้คือ ปีปฏิทินสวยจะเป็นลำดับที่สมาชิกเพิ่มค่าเป็นรูปแบบ 6-11-11 คือปี 2009, 2015, 2026, 2037, 2043, 2054, 2065, ... คิดเป็นสูตรทั่วไปได้ว่า เป็น ค.ศ. ที่หารด้วย 28 แล้วเหลือเศษ 10, 21 หรือ 27 แต่ลำดับนี้จะเปลี่ยนรูปแบบเมื่อผ่านจุดที่เป็นข้อยกเว้น คือเมื่อ ค.ศ. หารด้วย 100 ลงตัว แต่หารด้วย 400 ไม่ลงตัว คำตอบจึงต้องแบ่งเป็นช่วง ๆ เช่น ระหว่าง ค.ศ. 1801-1899 จะเป็นปีที่หารด้วย 28 แล้วเหลือเศษ 9, 15, 26 เป็นต้น และจะต้องพิจารณาตรงช่วงรอยต่อระหว่างช่วงเป็นจุด ๆ ไป

ผมจึงพยายามหาสูตรทั่วไปที่ครอบคลุมทุกช่วง โดยเริ่มตั้งแต่ ค.ศ. 1753 ซึ่งเป็นปีแรกที่ปฏิทินนับเป็นปกติหลังจากที่ เริ่มใช้ปฏิทิน Gregorian แทนปฏิทิน Julian ตามที่คำสั่ง cal ของ GNU ได้ implement โดยตัดวันที่ 3-13 กันยายน 1752 ออกจากปฏิทิน:

$ cal 9 1752
    กันยายน 1752
อา จ. อ. พ. พฤ ศ. ส.
       1  2 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

จุดเริ่มต้นของเราจึงเป็นวันที่ 1 กุมภาพันธ์ 1753 ซึ่งเป็นวันพฤหัสบดี:

$ cal 2 1753
  กุมภาพันธ์ 1753
อา จ. อ. พ. พฤ ศ. ส.
             1  2  3
 4  5  6  7  8  9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28

ผมกำหนดให้เศษเหลือจากการหารด้วย 7 แทนวันต่าง ๆ ในสัปดาห์ โดย 0 แทนวันอาทิตย์, 1 แทนวันจันทร์, 2 แทนวันอังคาร, ... 6 แทนวันเสาร์ ดังนั้น เศษเหลือเริ่มต้นในปี 1753 ของเราจึงเป็น 4 คือวันพฤหัสบดี

สมมุติให้ y แทนปีที่ต้องการพิจารณา นับจากปี 1753 ถึงปี y ถ้าทุกปีมี 365 วัน วันในสัปดาห์จะเลื่อนไปข้างหน้าปีละ 1 วัน (365 หารด้วย 7 เหลือเศษ 1) นับได้ y - 1753 วัน หากนำมาบวกวันเริ่มต้นคือวันพฤหัสบดี (เศษ 4) แล้วหารด้วย 7 เพื่อดูเศษเหลือ ก็จะรู้วันในปฏิทินของปีนั้นว่าเป็นวันอะไร แต่นี่คือกรณีที่ทุกปีมี 365 วัน โดยยังไม่คิดปีอธิกสุรทิน:

วันในสัปดาห์ของ 1 ก.พ. ปี y = (4 + (y - 1753)) mod 7 ถ้าทุกปีเป็นปกติสุรทิน

ปีอธิกสุรทินที่เกิดแต่ละครั้งจะทำให้วันในปฏิทินเลื่อนเพิ่มอีก 1 วัน หากรู้จำนวนปีอธิกสุรทินตั้งแต่ปี 1753 ถึงปี (y - 1) ก็จะนำมาบวกเพิ่มเข้ากับการเลื่อนวันในสูตรข้างต้นนี้ก่อนหารด้วย 7 เอาเศษ

จำนวนปีอธิกสุรทินตั้งแต่ปี 1753 ถึงปี (y - 1) คำนวณได้จากจำนวนปีอธิกสุรทินตั้งแต่ปี 1 ถึงปี (y - 1) ลบด้วยจำนวนปีอธิกสุรทินตั้งแต่ปี 1 ถึงปี 1753

จำนวนปีอธิกสุรทินตั้งแต่ปี 1 ถึงปี (y - 1) = floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400)

จำนวนปีอธิกสุรทินตั้งแต่ปี 1 ถึงปี 1753 = floor(1753/4) - floor(1753/100) + floor(1753/400) = 438 - 17 + 4 = 425

จำนวนปีอธิกสุรทินตั้งแต่ปี 1753 ถึงปี (y - 1) = floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400) - 425

ดังนั้นจึงได้ว่า วันที่ 1 ก.พ. ปี y จะตรงกับวัน: (4 + (y - 1753) + floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400) - 425) mod 7

หักลบตัวเลขแล้วจะได้เป็น (y - 2174 + floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400)) mod 7

และในเมื่อ 2174 mod 7 = 4 จึงแทน 2174 ด้วย 4 ใน modulo ได้ ได้เป็น:

วันในสัปดาห์ของ 1 ก.พ. ปี y = (y - 4 + floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400)) mod 7

และได้ว่า ปีปฏิทินสวย คือปีที่เป็นปกติสุรทิน และวันในสัปดาห์ของ 1 ก.พ. เป็น 0 ซึ่งเขียนเป็นนิพจน์เงื่อนไขภาษา C ได้เป็น:

  ((y % 4 != 0) || (y % 100 == 0 && y % 400 != 0)) &&
  (y - 4 + floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400)) % 7 == 0

QED.

Feb 2015 Calendar

เมื่อเดือนที่แล้ว ผมได้รับข้อความจากเพื่อน ซึ่งส่งต่อมาจากคนอื่นอีกที ความว่า:

ปีนี้เดือนกุมภาพันธ์ มี 4 อาทิตย์, 4 จันทร์, 4 อังคาร, 4 พุธ, 4 พฤหัส, 4 ศุกร์ และ 4 เสาร์ ซึ่งจะเกิดได้ทุก 823 ปี ชาวจีนถือเป็นปีถุงเงิน ถ้าส่งให้เพื่อนหรือ กลุ่มเพื่อน อย่างน้อย 5 คน จะมีเงินไหลเข้ามาใน 4 วัน ส่งภายใน 11 นาที หลังอ่านจบ

เพื่อนคงส่งมาขำ ๆ แต่ความ geek ในตัวผมไม่เข้าใครออกใคร เลยตอบเพื่อนไปว่า ความจริงแล้วมันเกิดได้ทุกปี ยกเว้นปีที่ ค.ศ. หารด้วย 400 ลงตัว หรือไม่ก็หารด้วย 4 ลงตัว แต่หารด้วย 100 ไม่ลงตัว ผมซีเรียสนะเฟ้ย! ;-P

ก็ปีไหนเดือนกุมภาพันธ์มี 28 วัน ก็ปีนั้นแหละ กุมภาพันธ์จะมี 4 อาทิตย์, 4 จันทร์ ฯลฯ 4 เสาร์ (4*7 = 28) ซึ่งมันก็แทบทุกปี

แต่อย่างไรก็ตาม ปฏิทินเดือนกุมภาพันธ์ปีนี้ก็ยังมีอะไรพิเศษที่น่าสนใจ:

$ cal 2 2015
  กุมภาพันธ์ 2015     
อา จ. อ. พ. พฤ ศ. ส.  
 1  2  3  4  5  6  7  
 8  9 10 11 12 13 14  
15 16 17 18 19 20 21  
22 23 24 25 26 27 28  

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

ตัวอย่างของปีที่ว่าก็เช่น:

$ cal 2 2009
  กุมภาพันธ์ 2009
อา จ. อ. พ. พฤ ศ. ส.
 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28


$ cal 2 2026
  กุมภาพันธ์ 2026
อา จ. อ. พ. พฤ ศ. ส.
 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28


$ cal 2 2037
  กุมภาพันธ์ 2037
อา จ. อ. พ. พฤ ศ. ส.
 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28


$ cal 2 2043
  กุมภาพันธ์ 2043
อา จ. อ. พ. พฤ ศ. ส.
 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28

แล้วจะมีปีไหนอีกนะ?

หมายเหตุ: ยังไงรอบก็ยังไม่ถึง 823 ปีอย่างที่เขาว่าอยู่ดี ก็ยังเดาไม่ออกว่าปีถุงเงิน เขาเอามาจากตำราไหน :-P

ข้อสังเกต:

• ปฏิทินโหราศาสตร์จีนเป็นปฏิทินจันทรคติ
• ข้อความเรื่องปีถุงเงินนี้ มีแพร่ในอินเทอร์เน็ตมาหลายรอบแล้ว

ขอบคุณเพื่อนที่ส่งข้อความนี้มา ทำให้ผมได้อะไรคิดเล่นสนุก ๆ ผมทิ้งไว้ให้ผู้อ่านลองคิดกันดูนะครับ

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