Planet TLWG

Syndicate content
Planet TLWG - http://linux.thai.net/planet
Updated: 1 hour 5 min ago

Kitt: Yellow Padlock on Chrome/iOS

8 May, 2015 - 12:06
วันนี้ได้รับแจ้งจากผู้ใช้เรื่อง https ของ มข. ตรงช่อง URL ขึ้นเป็นสีเหลือง (yellow padlock) อย่างที่ปรากฏในภาพบน แทนที่จะเป็นสีเขียว (green padlock) เหมือนทุกครั้ง เท่าที่ตรวจสอบ พบว่าเกิดกับ Google Chrome / iOS บางรุ่น และเป็น bug ในส่วนการตรวจสอบ certificate chain ของ Google Chrome / iOS เอง Google Chrome / iOS รุ่นถัดไปน่าจะแก้ไข bug นี้ ระหว่างนี้ ถ้าต้องการยืนยันเพื่อความมั่นใจ ให้แตะที่ icon สีเหลืองตรงช่อง URL และดูรายละเอียดที่ปรากฏตามภาพข้างล่าง icon ที่หนึ่ง เป็นตัวยืนยัน identity ของ website ว่าถูกต้องหรือไม่ icon ที่สอง … Continue reading Yellow Padlock on Chrome/iOS →

Thep: LibThai/LibDATrie Optimization Summary

2 May, 2015 - 17:28

นับจาก 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

Thep: Thanks

30 April, 2015 - 16:13

ขอขอบคุณย้อนหลัง สำหรับผู้สนับสนุนงานพัฒนาซอฟต์แวร์เสรีของผมในช่วงเดือนมกราคม 2558 ถึงเมษายน 2558 ที่ผ่านมาครับ คือ:

ขอให้ทุกท่านและครอบครัวมีความสุขความเจริญ สุขภาพแข็งแรงทั้งกายใจครับ

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

นอกจากการ optimize libthai/libdatrie ที่เคยเขียนไปแล้ว ก็มีงานจิปาถะอื่น ๆ อีก เช่น

  • งานแปล Xfce [ต้องล็อกอิน] ทั้งไล่กวดและไล่หลัง Xfce 4.12 ที่ออกไป จนขณะนี้อัตราการแปลของภาษาไทยอยู่ที่ 95% แล้ว
  • งานแปล GNOME ซึ่งผมเข้าสู่สถานะ review only (ไม่แปลเองอย่าง active) แล้ว ก็ได้ตรวจทานคำแปลที่มีนักแปลส่งเข้ามา
  • งาน Debian ในช่วงที่ Jessie freeze อยู่ ผมก็ได้แต่เตรียมปรับแก้ประเด็นเล็ก ๆ น้อย ๆ ที่ระบบ QA ต่าง ๆ ของ Debian ตรวจพบเพื่อรออัปโหลดในรอบ Stretch (Jessie + 1) ต่อไป เช่น:
    • lintian ส่วนใหญ่เป็นปัญหารูปแบบแฟ้ม debian/copyright ที่เครื่องแจงอ่านได้ และแฟ้มที่ขาดข้อมูลลิขสิทธิ์ ซึ่งบางส่วนต้องแก้ที่ต้นน้ำ ผมก็ทำเตรียมไว้
    • reproducible ตรวจพบการใช้ timestamp ขณะ build ซึ่งทำให้แพกเกจต่าง ๆ build หลายครั้งแล้วได้ checksum ไม่เท่ากัน ซึ่งทั้งหมดต้องแก้ที่ต้นน้ำ
    • Debian font review ซึ่งแสดงตัวอย่างฟอนต์จากแพกเกจฟอนต์ต่าง ๆ ใน Debian พร้อมผลลัพธ์จากโปรแกรม fontlint ที่ตรวจหาปัญหาต่าง ๆ ในฟอนต์ ทำให้ต้องมา validate ฟอนต์ที่ต้นน้ำทีละตัว ทำให้ได้แก้ปัญหาต่าง ๆ ในเส้นโค้งตัวอักษรของฟอนต์ เช่น การซ้อนทับกันของเส้น, การขาดจุด extrema, การระบุพิกัดของจุดแบบไม่ใช่จำนวนเต็ม, การใช้ชื่อ glyph ที่ไม่ตรงตามมาตรฐาน, ความผิดปกติของตาราง GPOS ฯลฯ แล้วก็เลยเถิดไปถึงการปรับเส้นอักษรแบบยกเครื่องในบางฟอนต์ ซึ่งส่งผลให้ได้เส้นที่คมชัดขึ้นเมื่อแสดงบนจอภาพ
    ประเด็นอื่นที่นอกเหนือจากที่ QA ตรวจพบ เช่น ปรับให้แพกเกจบางตัวที่สามารถใช้เอกสารใน /usr/share/doc ร่วมกันได้ทำเป็น symlink ถึงกัน ตาม Policy 12.3 วรรค 5 เพื่อลดขนาดติดตั้ง
  • งานปรับปรุงฟอนต์ในชุด fonts-tlwg ตามที่ได้รับข้อเสนอแนะจากคุณ Martin Hosken ซึ่งจะนำไปสู่การปรับปรุงการรองรับภาษาชาติพันธุ์ต่อไป
  • การแก้บั๊กใน libdatrie ตามที่มีผู้รายงานเข้ามาทางเมลลิงลิสต์

ขณะนี้ Jessie ก็ได้ออกไปแล้ว รอบการพัฒนาใหม่ของ Stretch ก็กำลังเริ่ม ก็คงใกล้ได้เวลาปล่อยของที่ทำสะสมไว้

Kitt: Linux kernel 4.0

23 April, 2015 - 05:01
รีลีสไปแล้ว และเรื่องใหญ่สุดของ 4.0 คือ infrastructure สำหรับอัพเกรดเคอร์เนลโดยไม่ต้อง reboot อีกต่อไป :) ที่จริงไม่ใช่ของใหม่เสียทีเดียวมันคือฟีเจอร์เดียวกันกับ Ksplice (Oracle), Kpatch (RedHat) นั่นเอง

Kitt: สัปดาห์หนังสือแห่งชาติ ครั้งที่ 43

15 April, 2015 - 11:10
ลืมบันทึก เดินไป Talent 1 ซื้อมาสองเล่ม คินดะอิจิยอดนักสืบ ตอนที่ 31 ปิศาจฆาตกร ยักษ์ มิเกะเนะโกะออกจากโรงพิมพ์ไม่ทัน รอ Book Expo ค่อยสอยก็ได้

Kitt: มหาสงกรานต์ ๒๕๕๘

13 April, 2015 - 18:19
คำนวณหาวันสงกรานต์กัน ใช้สูตรเดิม คำนวณ ปี จ.ศ. = 2558 – 1181 = 1377 หาวันเถลิงศก = 1377 * 0.25875 + floor(1377 / 100 + 0.38) – floor(1377 / 4 + 0.5) – floor(1377 / 400 + 0.595) – 5.53375 = 356.29875 + 14 – 344 – 4 – 5.53375 = 16.765 (วันที่ 16 + 0.765 วัน) วันมหาสงกรานต์ = … Continue reading มหาสงกรานต์ ๒๕๕๘ →

LookHin: การวัดระยะทางระหว่างโลก-ดวงจันทร์-ดวงอาทิตย์และเส้นรอบวงของโลกในสมัยกรีกโบราณ

12 April, 2015 - 22:34

การวัดระยะทางระหว่างโลก-ดวงจันทร์-ดวงอาทิตย์
อริสตาร์คัสแห่งซามอน (Aristarchus) นักคณิตศาสตร์และดาราศาสตร์ชาวกรีก (320-230 ปีก่อนคริสตกาล) อริสตาร์คัสเป็นคนแรกที่เสนอว่าดวงอาทิตย์เป็นศูนย์กลางของจักรวาล และกลางวัน-กลางคืนเกิดจากโลกหมุนรอบตัวเอง อริสตาร์คัสวัดระยะระหว่างโลก-ดวงอาทิตย์-ดวงจันทร์ โดยใช้หลักการของตรีโกณมิติ อริสตาร์คัสใช้ช่วงเวลาที่มองเห็นดวงจันทร์ครึ่งดวงบนท้องฟ้าซึ่งเป็นช่วงเวลาที่โลก-ดวงจันทร์-ดวงอาทิตย์ทำมุมกัน 90 องศา (มุม a) จากนั้นต้องทำการวัดมุมระหว่างดวงจันทร์-โลก-ดวงอาทิตย์ (มุม b ส่วนมุม c ที่เหลือคำนวณได้จาก c=180-a-b) ซึ่งตอนนั้นอริสตาร์คัสวัด (มุม b) ได้ 87 องศา (ปัจจุบันวัดได้ 89.85 องศา ด้วยความไม่แม่นยำของเครื่องมือสมัยก่อนทำให้อริสตาร์คัสวัดผิดพลาดไป 2.85 องศา) อริสตาร์คัสคำนวณว่าระยะทางระหว่างโลกกับดวงอาทิตย์ยาวเป็น 19 เท่าของระยะทางระหว่างโลกกับดวงจันทร์ ซึ่งจริงๆแล้วระยะห่างระหว่างโลกกับดวงอาทิตย์จะเป็น 390 เท่าของระยะทางระหว่างโลกกับดวงจันทร์ ความคลาดเคลื่อนนี้ไม่ได้เกิดจากการคำนวณที่ผิดพลาด แต่เกิดจากความคลาดเคลื่อนของเครื่องมือวัดทำให้มุมที่ได้ขาดความเที่ยงตรง

การวัดเส้นรอบวงของโลก
เอราทอสเทนีส (Eratosthenes) นักภูมิศาสตร์ชาวกรีก (276-194 ปีก่อนคริสตกาล) ว่ากันว่าเอราทอสเทนีสเคยร่ำเรียนที่สำนัก “อะคาเดมี” ของ “เพลโต” มาด้วย เอราทอสเทนีสยอมรับว่าโลกกลมและเขาพยายามคำนวณเส้นรอบโลก โดยเอราทอสเทนีสได้ทำการวัดเงาในเวลาเที่ยงวันของเสาที่ตั้งอยู่ในเมือง Syene และ Alexandria ซึ่งทั้งสองเมืองอยู่ห่างกัน 5,000 Stades (10 Stades เท่ากับ 1 ไมล์) จากการคำนวณของเอราทอสเทนีสเงาในเวลาเที่ยงของเสาจากทั้งสองเมืองต่างกันอยู่ 7.2 องศา เอราทอสเทนีสรู้อยู่แล้วว่าโลกกลม ฉะนั้น 1 วงกลมก็จะแบ่งเป็น 7.2 องศาได้ 50 ชิ้น (360/7.2 = 50) ดังนั้นความยาวรอบโลกก็จะเท่ากับ 50×5,000 = 250,000 Stades หรือเท่ากับ 25,000 ไมล์ ซึ่งความยาวรอบวงของโลกที่วัดด้วยเครื่องมือสมัยใหม่คือ 24,860 ไมล์ คลาดเคลื่อนไปนิดหน่อย

ข้อมูลจาก : วิกิพีเดีย, ไซแอนซ์ อิลลัสเตรเต็ด, กูเกิล

Kitt: The next version of Linux Kernel

3 March, 2015 - 21:18
เมื่อกลางเดือนกุมภา Linus Torvalds บอกว่า เลข minor version ของ Linux Kernel นี่มันชักจะสูงเกินไปแล้ว (เหมือนตอน 2.6.3x) เลยทำโพล (ผ่าน G+) ว่า Linux Kernel version ถัดไปจะเป็น 3.20 หรือเปลี่ยน major เป็น 4.0 ไปเลย มีคนกดเลือกไปสามหมื่นกว่าคน (/me ด้วย) สรุปผลโพลได้ว่า 44% เลือก 3.20 56% เลือก 4.0 ดังนั้น รุ่นถัดจาก 3.19 ก็เลยจะเป็น Linux Kernel 4.0 จ้ะ และเมื่อปลายเดือนกุมภา Linus ก็ปล่อย 4.0-rc1 ก็ออกมาแล้ว

Kitt: Superfish & Lenovo

21 February, 2015 - 09:21
Superfish กลายเป็นข่าวดังเมื่อไม่นานมานี้ เนื่องจากมีคนพบว่า Lenovo preload adware ตัวนี้มาจากโรงงาน ว่าง่ายๆ มันทำ targeted/personalized ads โดยเอาข้อมูลการใช้งานของผู้ใช้ไปวิเคราะห์ดูว่าน่าจะส่งโฆษณาอะไรดี แต่ความน่ากลัวของ Superfish มันอยู่ที่กลไกการทำงานของมัน เพราะจะทำแบบนั้นได้แปลว่ามัน intercept ข้อมูลที่ผู้ใช้เยี่ยมชมเว็บต่างๆ ซึ่งก็คือมันทำงานเป็น Man-in-the-Middle นั่นแหละ ที่แสบคือมัน intercept HTTPS ได้ โดย browser จับผิดไม่ได้ เท่าที่เข้าใจ หลักการของ Superfish คือ ทำตัวเองเป็น root CA ที่ browser เชื่อถือ ด้วยการใช้ adware เป็นตัวฝัง root certificate ไว้ใน browser พอผู้ใช้เข้าเว็บที่เป็น HTTPS มันก็จะ intercept ถอดรหัส เก็บข้อมูล ใช้ key ใน root … Continue reading Superfish & Lenovo →

Neutron: บันทึกช่วยจำ: ขยายขนาด LVM partition ขณะกำลังใช้งาน

17 February, 2015 - 23:55

ความสะดวกในการใช้งาน virtual disk ที่สามารถเพิ่มเข้าสู่ระบบได้ตลอดเวลา ทำให้ต้องขวนขวายหาวิธีขยายขนาด partition ขณะกำลังใช้งาน และนี่คือ บันทึกช่วยจำ

* เงื่อนไข - LVM partition ต้องไม่เป็น root partition

#!/bin/sh VG=test-vg VOLUME=data DEV=/dev/${VG}/${VOLUME} # Install parted apt-get -y install parted # Rescan disk echo 1 > /sys/class/scsi_disk/0:0:0:0/device/rescan # 2,5 is the extended, LVM partition respectively parted /dev/sda resizepart 2 100% parted /dev/sda resizepart 5 100% # /dev/sda5 is the LVM partition pvresize /dev/sda5 lvresize -l+100%FREE ${DEV} resize2fs ${DEV}

Kitt: GRUB timeout options

14 February, 2015 - 11:58
There are many timeout configuration for grub2 that you can put in /etc/default/grub GRUB_TIMEOUT GRUB_HIDDEN_TIMEOUT GRUB_RECORDFAIL_TIMEOUT The last one may help to boot normally in case power loss. Also try FSCKFIX in /etc/default/rcS :)

Thep: Pretty Feb Calendar Solution

12 February, 2015 - 15:14

ใน 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.

Thep: Feb 2015 Calendar

8 February, 2015 - 22:32

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

ปีนี้เดือนกุมภาพันธ์ มี 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

ข้อสังเกต:

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

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

Kitt: Term Ended

5 February, 2015 - 21:56
ปักหมุด – วันสุดท้ายของการทำงานในตำแหน่งผู้ช่วยอธิการบดีฝ่ายเทคโนโลยีสารสนเทศ และ ผู้อำนวยการสำนักนวัตกรรมการเรียนการสอน มหาวิทยาลัยขอนแก่น – จบ

Thep: Yet Another LibThai Optimization Effort

5 February, 2015 - 15:06

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

Kitt: 2015 leap second

2 February, 2015 - 21:45
อ้างอิงจาก IERS : A positive leap second will be introduced at the end of June 2015. Leap second (ภาษาไทย: อธิกวินาที) เป็นการชดเชยเวลา ระหว่างการวัด 1 วันของ เวลาตามนาฬิกาที่เราใช้ (24 * 60 * 60 = 86400 วินาที/วัน) กับ mean solar time ซึ่งวัดตามนิยามหมุนรอบตัวเองของโลกครบ 1 รอบ ทีนี้ การหมุนรอบตัวเองของโลกมันไม่ได้ลงตัวที่ 86400 วินาทีทุกวันหรอก มันเป็นการหมุนของวัตถุเหมือนๆ กับลูกข่างที่เรียนในฟิสิกส์นั่นแหละ มันเปลี่ยนแปลงได้ถ้ามีแรงมาบวกหรือลบ moment of inertia และก็พบกันว่า แรงเสียดทานจากกระแสน้ำ แผ่นดินไหว สึนามิ การเคลื่อนตัวของเปลือกโลก และอื่นๆ … Continue reading 2015 leap second →