เตรียมเทียบความเร็วการตัดคำแบบใช้ multi-core

ในหมู่ programmer มักจะคุยกันบ่อย ๆ ว่าโปรแกรมช้าจัง ใช้ภาษานั้นเขียนสิจะได้เร็วอะไรทำนองนั้น

ก็เลยมีคนทำตัวเทียบออกมา

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

โปรแกรมตัดคำเคยเทียบไปรอบนึงแล้วแต่ลองบน single core แถม corpus ก็ใช้ตัวไหนแล้วก็ไม่รู้ ลืม! แล้วก็รู้สึกจะเป็นตัวที่แจกไม่ได้ เครื่องที่ test ก็เป็น laptop ของผมเองเวลารันก็ไม่สะดวกเพราะว่าต้องหยุดทำงาน

ในรอบใหม่นี้ก็เลยคิดมาได้ 2 อย่างคือ

  1. ต้องใช้ corpus ที่มันแจกได้ ก็เลยจัดมา 2 ตัวคือวิกิพีเดียไทยที่มีสัญญาอนุญาตครีเอทีฟคอมมอนส์แบบแสดงที่มา-อนุญาตแบบเดียวกัน และพระไตรปิฏกภาษาไทยฉบับหลวงซึ่งเก่าแล้วลิขสิทธิ์หมดอายุ ทั้งหมดโหลดได้ที่ http://file.veer66.rocks/langbench/
    วิกิพีเดียวิธีสร้างมาประมาณนี้

    โหลดก่อน

    wget https://dumps.wikimedia.org/other/cirrussearch/20171009/thwiki-20171009-cirrussearch-content.json.gz -O - | zcat > thwiki-20171009-cirrussearch-content.json

    แล้วก็เอา plain text ออกมา

    require 'json'
    
    File.open('thwiki-20171009-cirrussearch-content.json') do |f|
      f.each_line do |line|
        data = JSON.parse(line)
        if data['title'] and data['text']
          puts data['title']      
          puts "=" * data['title'].length
          puts
          puts data['opening_text'] if data['opening_text']
          puts
          puts data['text']
          puts
          puts data['auxiliary_text'].join("\n") if data['auxiliary_text']
          puts
          puts
        end
      end
    end
    
    

    ส่วนพระไตรปิฎกโหลดจาก http://download.watnapahpong.org/data/E-Tipitaka-latest.tar.gz และก็มาสั่ง SQLite แบบนี้


    echo 'select content from main;' | sqlite3 thai.db | bzip2 > ~/Develop/corpus/thai-etipitaka.txt.bz2

  2. ส่วน H/W จะใช้ Raspberry Pi 3 Model B ที่เสียบ MicroSD (HC) Class 10 ของ Sandisk (Ultra)

    rpi3.jpg

    ที่ใช้ rpi3 เพราะมันมี 4 core; RAM ไม่เยอะเกินไปไม่งั้นมันจะเขียนง่ายไป; เครื่องไม่แพงมากหาง่ายด้วย คนอื่นซึ้อมาทดลองตามได้ ส่วนใช้ OS อะไรยังเลือกไม่ได้ครับ ตัด NetBSD ออกไปก่อนเพราะ netbsd-evbarm target ของ Rust ยังไม่มี ก็น่าจะใช้ GNU/Linux แต่ไม่แน่ใจว่า distro ไหน

ส่วนกติกาก็คือว่าทุกตัวจะใช้ algorithm เดียวกัน จะปรับเฉพาะวิธีเขียนโปรแกรมเท่านั้น

สิ่งที่ขาดไปและควรจะมีมากคือตัวทดสอบว่าผลการตัดคำมันออกมาถูกตาม algorithm ที่วางไว้หรือเปล่า ถ้าไม่มีใน wordlist หรือกำกวมก็แล้วไป ประมาณว่าผิดก็ควรจะผิดเหมือนกันทุกตัว ถูกก็ถูกเหมือนกันทุกตัว ผมคิดว่า sample ออกมาสัก 2 บรรทัดก็พอ ที่เหลือก็ดูว่า output ออกมาจำนวนบรรทัดเท่ากันก็น่าจะพอแล้ว มั้ง

ถ้าหากท่านใดสนใจก็สามารถโหลด source code ภาษาที่ท่านชอบแล้วก็ลองโมลอง optimize กันได้เลยครับ แล้ว pull request เข้ามา ในอนาคตถ้ามีคนสนใจมาก ๆ ผมอาจจะเขียน script ไว้ให้รันทุกคืนไปเลย ส่วน source code เอาได้จาก link ที่ http://veer66.rocks/2017/06/04/thai-word-break-in-various-programming-languages.html ครับ

ส่วนเวลาทำสอบผมก็จะแตก bzip2 ก่อนนะครับ แล้วครับมารัน


time ./wordcut thai-wtipitaka.out.txt

ถ้าพวกที่ใช้ JVM ก็จะรันทำนองนี้


time java -jar wordcut.jar thai-wtipitaka.out.txt

Advertisements

Rich Hickey พูดถึง RDF ด้วย

Rich Hickey เป็นบิดาของภาษา Clojure ซึ่งอาจจะเรียกได้ว่าสวนกระแสปี 2017 ก็ได้ เพราะว่าภาษาส่วนมากจะออกไปทาง static typing + function programming แบบนี้ แต่ Clojure เน้น dynamic typing แต่จะเขียน spec ใส่ก็ได้เป็น option

ตอนที่ RDF ออกมาใหม่ ๆ ผมรู้สึกว่าจะทำออกมาทำไม ใช้ database ธรรมดา ๆ แบบ PostgreSQL แทนก็ได้ จะแลกเปลี่ยนข้อมูลก็ใช้ CSV สิงี้

Screenshot-2017-10-14 Opening Keynote - Rich Hickey - YouTube.png

ใน video เขาพูดได้เห็นภาพมาก ๆ พอมี scheme มี table ของตัวเองแต่ละองค์กรมันก็ไม่ค่อยจะเหมือนกันหรอก เวลาจะเอามาใช้งานร่วมกันก็ต้องมานั่งแปลงก็รากแตกรากแตนอยู่ดี

ตัวย่อชื่อภาษา

เห็นเว็บหนึ่งเขียนตัวย่อหน้าเว็บภาษาญี่ปุ่นว่า jap. version ไม่รู้ตั้งใจหรือไม่ตั้งใจ ถ้าใครเคยดูหนังสงครามโลกบ้างก็น่าจะพอทราบว่า คำนี้มันเป็นคำที่เรียกแบบอย่างเกลียดชัง

ถ้าต้องย่อมีมาตรฐานตัวต่ออยู่คือ ISO 639-3 ภาษาญี่ปุ่นใช้ JPN ครับ ไทยใช้ THA อังกฤษใช้ ENG

https://en.wikipedia.org/wiki/Jap

Parallel processing แบบง่าย ๆ ใน Ruby

ขั้นแรกเลยคือลง gem นี้ก่อน Parallel แบบชื่อตรงมาก พอลงแล้วเขียนอะไรประมาณนี้ได้เลย


require 'parallel'
a_mul_10 = Parallel.map([1,2,3,4,5]) {|elem| elem + 10}

หรือถ้าอยากให้มันเยอะ ๆ หน่อยจะได้ top ดูทันว่าใช้กี่ core แล้วก็สั่งแบบ


require 'parallel'
a_mul_10 = Parallel.map(0..1000000) {|elem| elem + 10}

ก็ได้

ผมอยากจะเขียน client ไปเรียก API แบบพร้อมกัน เพราะประมาณว่าเขียนแบบธรรมดาช้าใช้ CPU ได้แค่ 23% ของ 1 core ก็เลยจัดไปประมาณนี้ (ตัดรายละเอียดออกแล้ว)


Parallel.each(id_orgs, in_processes: 4) do |id|
   metadata = get_metadata(api_key, id)
   metadata = do_sth(metadata)
   send_metadata(api_key, metadata)
end

ผลคือแค่ใช้ 2 processor นี่ server ก็ไม่ไหว เพิ่มเป็น 16 นี่ถึงกับเว็บหลักเดี้ยงไปเลย T_T

Python async? web app แบบไม่โม code

ตั้งแต่มี node.js มาหลายคนก็อยากจะเขียน web app แบบ async บ้างเพราะมันรับ request ต่อวินาทีได้เยอะ ที่มันทำได้เพราะมันมาจัดการ schedule task เอง มี event loop เอง แล้วก็ไม่ต้องไป switch task บ่อย ๆ แบบที่ไม่จำเป็น ใช้ I/O หรืออย่างอื่นที่กำหนดทีค่อย switch ใน task queue

แต่มันก็มีประเด็นว่า (1) ไม่เขียน JS ได้ไหม ทีมใช้ Python งี้ (2) เขียนธรรมดาไม่ callback ไม่ async/await เพิ่มมาได้ไหม สองประเด็นนี้นอกจากจะเป็นเรื่องความยุ่งยากแล้ว บางทีก็มี code เก่าด้วย

ท่าแรกที่ผมนึกออกเลยคือใช้ Tornado มันเป็น async แน่ใช้ Python ด้วย แต่ว่า code นีเปลี่ยนเยอะเลย

อีกท่าคือใช้ Meinheld ดู code ก็เขียนธรรมดานี่เอง แต่ใช้ non-blocking I/O และ event loop จะ async ได้หรือเปล่าผมก็ไม่แน่ใจ

Meinheld มี task queue ของตัวเองโดยใช้ picoev ที่ไปใช้ประโยชน์จาก epoll ของ Linux (kernel) อีกที เวลาสลับ task ใช้ greenlet มาช่วย; event ตอนที่ทำ I/O มาจาก socket ที่เขาเขียนใหม่ ใช้ non-blocking I/O แล้วก็ไปใช้ wait คล้าย ๆ promise ในนั้นเลย แล้วก็เอาไปแทนที่ socket มาตรฐาน โดยใช้ท่า monkey patch ที่มักจะโดนทัดทานไม่ให้ใช้นั่นเอง

วิธีใช้ก็แค่ pip install ให้เรียบร้อย แล้วไปเรียก gunicorn แล้วเพิ่ม option นี้ไป –worker-class=”egg:meinheld#gunicorn_worker”

ประสิทธิภาพจากที่ไปดู Benchmark ตัวที่ใช้ Bottle.py + Meinheld ผลออกมาดีกว่า Express.js และดีกว่า Framework ที่ใช้ Go บางตัวด้วยซ้ำ

มันก็ดูจะมีข้อจำกัดอยู่บ้างที่ว่า event loop นี่มัน switch ตาม socket ของ Python อย่างเดียว สมมุติว่าใช้ PostgreSQL ผ่าน libpq หรือไปอ่านเขียนไฟล์มันก็คงไม่ switch ให้ อีกประเด็นหนึ่งคือ ผมเดา ๆ ว่า context ที่ต้องเก็บไปกับ task queue มันน่าจะใหญ่กว่า node.js เพราะน่าจะต้องไปยุ่งกับ stack ด้วยมั้ง

เรื่องว่า stable ไหมนี่ผมก็ไม่ทราบเหมือนกัน นอกจากนั้นแล้วก็ยังไม่เคยใช้ และไม่มีแผนที่จะใช้ด้วย

ผมยกตัวอย่างนี้ขึ้นมาเพื่อจะบอกว่าการเพิ่มประสิทธิภาพของ web app โดยใช้ async ที่ใช้ประโยชน์ของ event loop และ non-blocking I/O อาจจะไม่ต้องเปลี่ยนไปเขียน JS หรือ Go หรือไม่ต้องแม้แต่จะแก้ code เลยก็ได้ วิธีที่ยกมาอาจจะใช้ในภาษาอื่นนอกจาก Python ได้ด้วยและอาจจะมีคนทำอยู่แล้วด้วย

update1: จะใช้ Tornado ก็ได้ จริงท่าที่เขียนข้างบนมันก็คือการใช้ Async worker ของ Gunicorn นี่เอง ซึ่งเลือกเป็น Tornado  ได้ด้วย

reduce

เวลาใช้ reduce ในภาษาที่แบบกึ่ง ๆ จะ function แบบ JS ตอนที่ function return พวก integer หรือข้อมูลอะไรที่ copy ได้เลยมันก็จะรู้สึก ok

แต่ว่าเมื่อไหร่ต้อง return array ก็จะแปลก ๆ แล้ว เพราะถ้าจะเลี่ยงจะไม่ให้มีการแก้ array นั้นหลายที่ก็ต้อง copy ไปเลย ซึ่งภาษาพวก Lisp หรือที่คล้าย ๆ อย่าง ML หรือ Haskell มันจะมี Singly-linked list แบบ persistent มาให้ใช้ง่าย ๆ ก็สร้าง list ใหม่โดยเพิ่มสมาชิกไปตัวเดียวได้เลย

แต่พอคิดไปคิดว่า JS มันคงคงทำได้โดยใช้พวก lib เช่น ImmutableJS มาช่วยก็ได้

datalog

ผมแทบจะไม่สนใจ Prolog เลย แต่ว่าเป็น TA วิชา knowledge representation ก็เลยต้องมาอ่าน แล้วก็พบว่ามี Datalog ด้วยซึ่งเป็น subset ของ Prolog อีกที [1] อันนี้ที่อ้างไปเขาไปอ้างงานปี 1982 ีอกทีผมยังหาอ่านไม่ได้

datalog ก็เอามาใช้ในงาน query ต่าง ๆ คล้าย SQL นี่เอง, datalog เป็นของเก่าแต่กลายเป็นว่ากลับมานิยมในยุคนี้ เก่ากว่า SQL; Clojure นี่ Datatomic ก็ใช้ datalog ด้วยแต่ว่าก็ปรับ syntax ให้กลายเป็น Clojure แบบเนียน ๆ

datalog แน่นอนว่าเขียนแบบ logic แล้วก็ recursive ได้[2] [4] เขาเอามา define path จาก edge แบบ recursive ก็ดูสวยงามดี สั้นด้วย


Path(t, d) :- Edge(1, t, d).
Path(t, d) :- Path(s, d1), Edge(s, t, d2), d=d1+d2

แต่ผมไม่แน่ใจว่าถ้า recursive ไม่ได้ออกมาเป็นแบบไหน

อีกประเด็นหนึ่งที่อ่านเจอคือ complexity ของ SQL query evalulate เป็น NP-complete [5] ส่วนของ Ground positive Datalog เป็น PTIME-complete ซึ่งผมก็ยังงง ๆ ว่า ground positive คืออะไร ptime นี่คือ space ไม่ P หรือเปล่า ?

อีกเป็นที่เจอใน Wikipedia[6] คือ datalog ไม่มี cut แบบใน Prolog เพราะรับประกันได้ว่าโปรแกรม query จะหยุดถ้า query บน finite set ทำให้ Datalog นี้เป็น declarative ยิ่งกว่า Prolog อีก

ผมว่า Datalog มันน่าสนใจว่า Prolog ที่เรียน ๆ ไปนอกจากจะยังไม่ตายแล้วแล้วมันก็คึกคักในวงการวิจัยมาหลายปี ดู ๆ แล้วในภาควิสาหกิจ (Enterprise) ก็จะเริ่มเอาไปใช้แล้วด้วย

ป.ล. ถึงผมจะไม่ค่อยรู้เรื่องก็ตาม SQL:1999 ก็ recursive ได้ [3] แต่เขียนใส่ MySQL แล้วผมก็ไม่แน่ใจว่ามันจะได้หรือเปล่า (ยังไม่ได้ลอง)

[1] https://pdfs.semanticscholar.org/6304/44d76e5aa81867344cb11aaddaab8dc8174c.pdf
[2] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5470845/
[3] http://www.seas.upenn.edu/~cse400/CSE400_2006_2007/GuptaSyrotkin/writeup.pdf
[4] https://suif.stanford.edu/~courses/cs243/lectures/l12-socialite.pdf
[5] http://www.dis.uniroma1.it/~rosati/krst/comparison.pdf
[6] https://en.wikipedia.org/w/index.php?title=Datalog&oldid=799521469

concurrency ใน Crystal-lang

อ่านแล้วคิดว่า concurrency ใน Crystal-lang น่าจะดีพอ ๆ กับ Golang

หรือจะเรียกว่าทำตาม Golang เลยก็ได้ ?

code ที่ใช้ switch fiber นี่อัด assembly กันเลย


https://crystal-lang.org/docs/guides/concurrency.html

https://github.com/crystal-lang/crystal/blob/c26fbc9714c700d65190e89bf48f2743bb0122d0/src/fiber.cr