ประโยค if 4 พันล้านบรรทัด

 (andreasjhkarlsson.github.io)
3 คะแนน โดย GN⁺ 2023-12-29 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ไอเดียขำ ๆ ที่พยายามตัดสินเลขคู่/เลขคี่โดยใช้เพียง การไล่เรียงเงื่อนไขเปรียบเทียบ โดยไม่ใช้ % ถูกขยายจาก 8 บิตไปถึง 32 บิต จนเผยให้เห็นข้อจำกัดของคอมไพเลอร์และรูปแบบไฟล์ปฏิบัติการ
  • เมื่อใช้ตัวสร้างโค้ด Python สร้าง if (number == n) อัตโนมัติ ช่วง 8 บิตและ 16 บิตยังทำงานได้ แต่ที่ 32 บิต จำนวนค่าที่ต้องเปรียบเทียบพุ่งเป็น ราว 4.2 พันล้านค่า
  • เวอร์ชัน C แบบ 32 บิตสร้างไฟล์ C ขนาดประมาณ 330GB หลังผ่านไป 48 ชั่วโมง และ MSVC คอมไพล์ไม่สำเร็จเพราะชนทั้งขีดจำกัดเลขบรรทัดและหน่วยความจำ heap ไม่พอ
  • เพื่อเลี่ยงข้อจำกัด 4GB ของไฟล์ปฏิบัติการแบบ PE ผู้เขียนจึงสร้างคำสั่ง x86-64 โดยตรงจนได้ไบนารี isEven.bin ขนาด 40GB และเรียกใช้มันเสมือนเป็นโค้ดผ่านการแมปหน่วยความจำของ Windows
  • โปรแกรมสุดท้ายเปลี่ยนจาก atoi เป็น strtoul ทำให้ตัดสินค่าขนาดใหญ่แบบ 32 บิตได้ถูกต้อง และอินพุตขนาดใหญ่ก็คืนผลภายในราว 10 วินาทีบนเครื่อง Core i5 12600K, RAM 32GB และ SSD แบบ M.2

ตัดสินเลขคู่/เลขคี่ด้วยประโยคเปรียบเทียบล้วน ๆ

  • จุดเริ่มต้นมาจากภาพแคปโค้ดที่เห็นบนโซเชียลมีเดีย เป็นวิธีแก้ปัญหาคลาสสิกเรื่องเลขคู่/เลขคี่โดยไม่ใช้ modulus operation
  • โครงสร้างคือวาง if (number == n) สำหรับแต่ละตัวเลข แล้วพิมพ์ผลว่าเป็นเลขคู่หรือเลขคี่ด้วย printf
  • ตัวอย่าง C ชุดแรกใช้ uint8_t number = atoi(argv[1]); และเขียนเงื่อนไขเปรียบเทียบตั้งแต่ 0 ถึง 10 ด้วยมือ
  • คอมไพล์ด้วย /Od เพื่อปิดการปรับแต่ง ให้คอมไพเลอร์ไม่เปลี่ยนอัลกอริทึม
    • 0, 4 เป็น even
    • 3, 7 เป็น odd
    • 50, 11, 99 ไม่แสดงผลอะไรเลย
  • สาเหตุคือหลัง if ตัวสุดท้ายไม่มีเงื่อนไขสำหรับค่าถัดไป จึงต้องมี ประโยค if เพิ่มอีกมาก

สร้างประโยค if ด้วย Python

  • แทนที่จะเขียนทุกเงื่อนไขด้วยมือ ผู้เขียนใช้แนวทาง meta programming ให้ Python พิมพ์โค้ด C ออกมา
  • สคริปต์ Python ใช้ for i in range(2**8) เพื่อสร้างเงื่อนไขตั้งแต่ 0 ถึง 255
    • ถ้า i % 2 == 0 ก็ใส่ printf("even\n");
    • ไม่เช่นนั้นก็ใส่ printf("odd\n");
  • โปรแกรม C ที่สร้างขึ้นมาทำงานได้ครบทั้งช่วง 8 บิต
    • 99 เป็น odd
    • 50 เป็น even
    • 240 เป็น even
    • 241 เป็น odd

ไปถึง 16 บิตได้สำเร็จด้วยการคอมไพล์ C

  • วิธีเดียวกันถูกขยายไปเป็น uint16_t และ range(2**16)
  • ไฟล์ C ที่สร้างได้มีขนาดราว 130,000 บรรทัด
  • หลังคอมไพล์ด้วย MSVC ก็ทำงานถูกต้องกับหลายค่า
    • 21000 เป็น even
    • 3475 เป็น odd
    • 3 เป็น odd
    • 65001 เป็น odd
    • 65532 เป็น even
  • ขนาดไฟล์ปฏิบัติการอยู่ที่ประมาณ 2MB และบนพีซีที่มีหน่วยความจำ 31.8GB ก็ไม่มีปัญหา

ไฟล์ C แบบ 32 บิตและขีดจำกัดของคอมไพเลอร์

  • เป้าหมายถัดไปคือใช้ uint32_t และ range(2**32) เพื่อรองรับค่าทั้งช่วง 32 บิตด้วยประโยคเปรียบเทียบ
  • ช่วง 32 บิตมีจำนวนตัวเลขมากกว่า 16 บิตถึง 65,536 เท่า
  • หลังปล่อยให้ตัวสร้าง Python ทำงาน 48 ชั่วโมง ก็ได้ไฟล์ C ขนาดประมาณ 330GB
  • การคอมไพล์ด้วย MSVC ชนขีดจำกัดอย่างรวดเร็ว
    • warning C4049: คอมไพเลอร์ถึงขีดจำกัดเลขบรรทัดและหยุดปล่อยข้อมูล line number
    • ขีดจำกัด line number คือ 16777215
    • fatal error C1060: compiler is out of heap space
  • รูปแบบไฟล์ Portable Executable (.exe) ของ Windows เองก็มีข้อจำกัดในการเกิน 4GB ทำให้แนวทางคอมไพล์ C เพื่อบรรจุการเปรียบเทียบกว่า 4 พันล้านครั้งลงในไฟล์ปฏิบัติการไปต่อไม่ได้
  • มีการอ้างถึงข้อจำกัดที่เกี่ยวข้องใน ขนาดสูงสุดของไฟล์ PE

สร้าง machine code โดยตรงเพื่อรันจริง

  • เพื่อหลบข้อจำกัดของคอมไพเลอร์และรูปแบบไฟล์ปฏิบัติการ ผู้เขียนจึงเปลี่ยนไปสร้างคำสั่ง x86-64 ลงเป็นไบนารีโดยตรง
  • ฟังก์ชันเป้าหมายมีรูปแบบ IsEven รับอาร์กิวเมนต์ผ่าน ECX และคืนค่าผ่าน EAX
    • ใช้ XOR EAX, EAX เพื่อตั้งค่าคืนต้นทางเป็น 0 สำหรับเลขคี่
    • สำหรับแต่ละตัวเลข ใช้ CMP ECX, i
    • ถ้าเป็นเลขคู่ก็ INC EAX แล้ว RET
    • ถ้าเป็นเลขคี่ก็ RET ทันที
  • มีการใช้ x86-64 assembly และ opcode โดย opcode ของแต่ละคำสั่งถูกถามจาก ChatGPT
  • สคริปต์ Python เปิด isEven.bin แบบไบนารี แล้วเขียนคำสั่งเปรียบเทียบสำหรับทุกค่าตั้งแต่ 0 ถึง 2**32 - 1
  • isEven.bin ที่ได้มีขนาดประมาณ 40GB และมีการเปรียบเทียบครบประมาณ 4.2 พันล้านครั้งสำหรับจำนวนเต็ม 32 บิตทั้งหมด

เรียกโค้ดขนาด 40GB ผ่าน memory mapping ของ Windows

  • โปรแกรม C ฝั่งโฮสต์เปิด isEven.bin แล้วใช้ Windows API ทำ memory mapping แทนการอ่านทั้งไฟล์เข้าหน่วยความจำ
  • ลำดับการทำงานมีดังนี้
    • ใช้ CreateFileA เปิด isEven.bin ด้วยสิทธิ์ GENERIC_READ | GENERIC_EXECUTE
    • ใช้ GetFileSizeEx เพื่อตรวจสอบขนาดไฟล์แบบ 64 บิต
    • กำหนด PAGE_EXECUTE_READ ให้ CreateFileMapping
    • ใช้ MapViewOfFile เพื่อสร้างแมปที่อ่านได้และรันได้
    • แคสต์พอยน์เตอร์ที่แมปแล้วเป็นฟังก์ชันพอยน์เตอร์ int (*isEven)(int) แล้วเรียกใช้
  • วิธีนี้ทำให้ไฟล์ 40GB ทั้งก้อนถูกใช้งานราวกับอยู่ในหน่วยความจำอยู่แล้ว โดยปล่อยให้ระบบปฏิบัติการจัดการการวางข้อมูลจริงผ่าน virtual memory
  • การทดสอบครั้งแรกส่วนใหญ่ทำงานถูกต้อง แต่ค่า 4200000000 กลับออกมาเป็น odd ซึ่งผิด
  • สาเหตุคือ atoi จัดการค่าบวกแบบ unsigned ที่มีขนาดใหญ่มากได้ไม่ถูกต้อง พอเปลี่ยนเป็น strtoul(argv[1], NULL, 10) แล้ว 4200000000 ก็แสดงเป็น even และ 4200000001 เป็น odd

ข้อสังเกตด้านประสิทธิภาพ

  • ค่าขนาดเล็กให้ผลแทบจะทันที ส่วนค่าขนาดใหญ่ที่ใกล้ขีดจำกัด 2^32 ก็ยังคืนผลได้ในเวลาประมาณ 10 วินาที
  • สภาพแวดล้อมทดสอบคือ Core i5 12600K, RAM 32GB และ SSD แบบ M.2
  • ระหว่างคำนวณ ความเร็วอ่านสูงสุดของ SSD ที่สังเกตได้อยู่ที่ประมาณ 800MB/s
  • แม้จะเป็นสถานการณ์ที่ต้องอ่านข้อมูล 40GB จากดิสก์ แมปเข้าสู่หน่วยความจำจริง และ CPU แทบไม่ได้ประโยชน์จากแคชมากนัก แต่ก็ยังได้ความเร็วระดับนี้ ซึ่งนับว่าน่าทึ่ง

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-12-29
ความคิดเห็นบน Hacker News

  • อยากให้ยังมีหนึ่งในโปรแกรมที่ผมเขียนช่วงแรก ๆ อยู่จัง ปี 1996 ตอนอายุ 16 ผมเห็นหัวข้อคอมพิวเตอร์กราฟิกในภาคผนวกของหนังสือพีชคณิตเชิงเส้น แล้วก็อินกับการใช้การเขียนโปรแกรมที่เพิ่งเรียนมาในเทอมก่อนทำโปรแกรมวาด wireframe แบบหมุนได้ ของรูปทรงไม่กี่แบบ
    เพราะแบบนั้นผมเกือบตกวิชานั้น ตอนนั้นยังไม่รู้จัก array เลย vertex ทั้งหมดและ element ของเมทริกซ์หมุนแต่ละตัวเป็นตัวแปรที่ hardcode ไว้หมด และการคูณเมทริกซ์ก็ไม่มี loop ต้องคัดลอกรายการนิพจน์คำนวณยาว ๆ ไปแก้สำหรับ vertex แต่ละจุด
    การวาดลงจอต้องเขียนลงหน่วยความจำตั้งแต่ address เฉพาะ จึงรู้จัก pointer อยู่ และมี loop สำหรับ rasterize เส้นระหว่าง vertex ด้วย สุดท้ายก็คือผมมี แนวคิดเรื่อง array และ indexing อยู่แล้ว แต่แค่ยังสร้างใช้เองไม่เป็น

    • ผมก็คล้ายกัน ราว ๆ อายุ 12 พยายามทำเกม Pac-Man ด้วย BASIC แล้วรู้สึกตัน เพราะคิดว่าต้องเขียน logic ของผี 4 ตัวแยกกันตั้งแต่ (x1,y1) ถึง (x4,y4)
      ผมบอกพ่อว่าอยากเขียนอะไรอย่าง xn, yn ใน loop for โดยให้ n บอกว่าเป็นผีตัวไหน พ่อก็หยิบหนังสือ BASIC มาเปิดให้ดูว่า x(n) ทำได้จริง
      เวลาพูดเรื่องการศึกษา ผมมักนึกถึงเหตุการณ์นี้ แนวคิดเชิงนามธรรม จะเข้าใจได้ดีที่สุดเมื่อนักเรียนมีความจำเป็นจริง ๆ และเรื่องที่อธิบายทั้งวันก็ยังงง จะเข้าล็อกได้ในไม่กี่วินาทีหรือไม่กี่นาทีเมื่อมันช่วยแก้ปัญหาของตัวเอง
    • ทางออกที่ชัดเจนคือใช้ด้านล่างของหน้าจอเป็น หน่วยความจำทำงาน แล้ววาดด้านบน พอวาดลงไปถึงด้านล่างก็คงเหลือการคำนวณไม่มากแล้ว และเพราะใช้หน่วยความจำ GPU ที่เร็ว จึงดูเป็น CUDA มากและ AI มาก
    • ทำให้นึกถึงช่วงแรก ๆ ที่ทำฟรีแลนซ์ ตอนนั้นมีแค่ VPS เล็ก ๆ ที่รัน PHP ได้ และต้องประมวลผลสเปรดชีต 5,000–10,000 แถว ซึ่งถือว่าค่อนข้างใหญ่สำหรับปี 2002/2003
      ผมไม่ได้จบวิทยาการคอมพิวเตอร์ เลยอ่านไฟล์ด้วยวิธีที่โง่ที่สุด และเพราะ loop ซ้อนกัน ทำให้เจอ error ใช้หน่วยความจำกับพื้นที่ไม่พออยู่เรื่อย ๆ เลยใส่ $variable = null ทุกที่เท่าที่ทำได้ แล้วมันก็รันได้จริง ๆ
    • Snake สำหรับ TI-83 ที่เป็นผลงานฮิตตอนมัธยมต้นของผมก็คล้ายกัน ผมใส่พิกัด x, y ของแต่ละท่อนงูไว้ในตัวแปรแยกทั้งหมด และเพราะจำนวนตัวแปรที่ใช้ได้ใน TI-83 BASIC มีจำกัด ความยาวงูก็ยาวเกินกว่านั้นไม่ได้
    • หลังจากอ่านเอกสารแล้วเรียน print, input, if, goto ด้วยตัวเอง ฟีเจอร์แรกของ GWBasic ที่ผมไปขอความช่วยเหลือจากคนอื่นจนได้เรียนรู้คือ chain

  • ดูเหมือนออกแบบเกินจำเป็นไปมาก ไม่เข้าใจว่าทำไมต้องถึงขั้น generate code ด้วย แก้ได้ด้วย loop for ง่าย ๆ
    ใน isOdd ให้วนจาก 0 ถึง n แล้วทำ odd = !odd ซ้ำ จากนั้นคืนค่า
    ลิงก์ Playground: https://go.dev/play/p/8TIfzGrdWDF
    ยังไม่ได้ profile แต่จากสัญชาตญาณและประสบการณ์ในวงการ นี่น่าจะเร็ว

    • ถ้าเป็น implementation คุณภาพระดับ production จริง ๆ ก็ควรใช้ recursion เสมอ ถ้า n == 0 ให้คืน false, ถ้าเป็นบวกให้คืน !isOdd(n-1), ถ้าเป็นลบให้คืน !isOdd(n+1)
    • ยืนยันได้ว่า เวอร์ชัน Rust ของวิธีนี้เร็ว
      assembly ออกมาประมาณ testq %rdi, %rdi, setg %al, andb %dil, %al, retq
      กด ... ข้าง build เพื่อดู assembly ได้: https://play.rust-lang.org/?version=stable&mode=release&edit...
      น่าเสียดายที่ Go Playground ดูเหมือนจะไม่รองรับการแสดงผล assembly
    • อย่าลืมฟังก์ชันคู่ด้วย isEven(n int64) bool { return !isOdd(n) }
    • ถ้า n = infinity ก็จะวนไปไม่สิ้นสุด
    • ปรับปรุงได้ด้วย tail recursion

  • วิธีนี้เหมาะสุด ๆ กับแพ็กเกจ npm อย่าง is-even[1] ที่มียอดดาวน์โหลดรายสัปดาห์ 196,023 ครั้ง หรือ is-odd[2] ที่มียอด 285,501 ครั้ง คงเจ๋งดีถ้าพิมพ์ npm install แล้วมันเริ่มดาวน์โหลด is-even ขนาด 40GB กับ is-odd ขนาด 40GB ลงมา
    [1] https://www.npmjs.com/package/is-even
    [2] https://www.npmjs.com/package/is-odd

    • เรื่องที่ควรพูดถึงเสมอคือ แพ็กเกจพวกนี้เป็นผลผลิตของ npm spammer ผู้ทุ่มเทคนหนึ่ง[1] ที่พยายามเข้าไปอยู่ในไดเรกทอรี node_modules ให้ได้มากที่สุด
      ansi-colors ก็ไม่ได้มีแค่แพ็กเกจรวมสีทั้งหมด แต่มีแพ็กเกจแยกตามสีด้วย และยังมีอะไรทำนองนี้อีกสารพัด สิ่งเหล่านี้ถูกแทรกเข้าไปในเครื่องมือ CLI หรือแพ็กเกจที่ดูสมเหตุสมผล แล้วก็อ้างอิงถึงกันเอง ทำให้แม้แต่โปรเจกต์จริงก็อาจดึงแพ็กเกจของ jonschlinkert เข้ามาหลายสิบตัวได้ เพียงเพราะ dependency ตัวเดียวที่ดูไม่มีพิษภัย
      [1] https://www.npmjs.com/~jonschlinkert
    • น่าทึ่งที่ผลลัพธ์จากการทำตาม “อย่าทำซ้ำ” อย่างบริสุทธิ์ที่สุดคือ is-even พึ่งพา is-odd
      ทั้งหมดมีแค่ var isOdd = require('is-odd'); ตามด้วย module.exports = function isEven(i) { return !isOdd(i); };
    • คนนี้ไม่รู้ แต่พอลองดูซอร์สทรีของแอปฟรอนต์เอนด์ 2 ตัวของเรา พบว่าแพ็กเกจ is-number ที่ is-odd พึ่งพา ถูกแพ็กเกจอื่น ๆ จำนวนไม่น้อยดึงไปใช้
      ถ้าการตัดสินว่าค่าใดเป็นชนิดตัวเลขใน JS มันยุ่งยากจริง ๆ แพ็กเกจนี้ก็อาจมีความหมาย แต่ก็น่าจะมีแพ็กเกจที่ทั่วไปกว่านี้ซึ่งจัดการชนิด built-in อื่น ๆ ด้วย
      อย่างไรก็ตาม isNumber ยังนับสตริงที่แปลงเป็นตัวเลขได้ว่าเป็นตัวเลขด้วย จึงอาจให้ผลลัพธ์แปลก ๆ ได้ เช่น const a = '1'; isNumber(a); // true แต่ const b = a + a; จะกลายเป็นสตริง '11'
      แน่นอนว่า 2*a จะได้ 2 และ 1+'1' กับ '1'+1 ต่างก็ได้ '11' ซึ่งเป็นความงี่เง่าแบบมาตรฐานของ JS แต่เพราะอย่างนั้น คำตอบที่บอกว่า '1' เป็นตัวเลขจึงอาจไม่ถูกต้องก็ได้ ทว่าแพ็กเกจนี้ถูกดาวน์โหลด 46 ล้านครั้งเมื่อสัปดาห์ที่แล้ว และที่ต่ำก็เพราะเป็นช่วงคริสต์มาสเท่านั้น สัปดาห์ก่อน ๆ เฉลี่ยราว 70 ล้านครั้ง ส่วนใหญ่คงเป็น dependency เหมือนโปรเจกต์ของเรา
    • เคยทำแพ็กเกจ nullll[1] ที่แค่ export ค่า null ค่าเดียวแต่ใช้หน่วยความจำ 400MB ไม่รู้ทำไมถึงโดน flag บน HN[2]
      มีดาว GitHub 41 ดวงและ test coverage 100%[3] ก็น่าจะพร้อมใช้ในโปรดักชันแน่นอน
      [1]: https://github.com/mickael-kerjean/nulll
      [2]: https://news.ycombinator.com/item?id=17072675
      [3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
    • จริง ๆ แล้วตัวเลขของ JavaScript เป็น f64 ไม่ใช่ u32 ดังนั้นแค่นั้นยังไม่พอ ต่อให้รองรับแค่ช่วงจำนวนเต็มที่ปลอดภัยก็ยังเป็น 2⁵⁴ ซึ่งใหญ่กว่า 2³² มากกว่า 4 ล้านเท่า
      ขนาดภาษาเครื่องน่าจะเพิ่มแค่ราว 4 ไบต์ต่อแต่ละ branch หรือประมาณ 40% ดังนั้นจะขึ้นไปได้ราว 224 exbibytes และนั่นยังเป็นกรณีที่ข้าม 10 บิตสุดท้ายไปแบบขี้เกียจด้วย
      ถ้าจะทำให้ถูกต้องจริง ๆ อาจต้องคูณเพิ่มอีก 1,000 เท่า และผมก็ยังไม่ได้คิดลึกเรื่องแพตเทิร์น NaN จึงอาจเล็กกว่านั้นเล็กน้อย ถ้ารองรับ bigint ด้วยก็อาจกลายเป็นอนันต์ไปเลย

  • ไม่รู้ว่าทำไมต้องทำแบบนี้ด้วย สิ่งที่ถูกคิดค้นมาเพื่อทำเรื่องแบบนี้ก็คือ ฐานข้อมูล นี่แหละ แค่เก็บ mapping ระหว่างตัวเลขกับการจัดประเภท even/odd ไว้ในฐานข้อมูล SQLite ก็พอ
    วิธีนี้ยังมีข้อดีคือไม่ต้องอัปเดตโปรแกรมทุกครั้งที่การจัดประเภทของตัวเลขใดตัวเลขหนึ่งเปลี่ยนจากคี่เป็นคู่

    • ฐานข้อมูลก็ยังต้องบำรุงรักษาและอัปเดตอยู่ดี สู้ตั้ง Ethereum contract แล้วให้แรงจูงใจทางเศรษฐกิจกับคนอื่น ๆ ให้ทำหน้าที่เป็น oracle และคืนคำตอบที่ถูกต้องได้ตลอดเวลาดีกว่า
    • นี่ดูเป็นข้อมูลประเภทที่ควรอยู่ใน Wikidata แบบนั้นก็ไม่ต้องมีฐานข้อมูลไว้ในเครื่อง แค่ยิงคำขอ HTTPS เร็ว ๆ ก็พอ
      ปัญหาเดียวอาจเกิดขึ้นถ้า TLS เองพึ่งพาฟังก์ชันคู่/คี่ แต่ก็คงไม่ใช่หรอก
    • สร้างตารางชื่อ even_or_odd แล้วมีคอลัมน์อย่าง is_odd, is_even, is_zero, is_one, is_two, is_three ก็พอ ใส่ 1 เป็น is_odd,is_one และ 2 เป็น is_even,is_two
    • ถูก แต่แน่นอนว่าต้องใช้ ฐานข้อมูล XML
      ยังช่วยเรื่องการพกพาข้อมูลด้วย และเวลาต้องตรวจด้วยมือก็รักษาให้อยู่ในรูปแบบที่มนุษย์อ่านง่ายได้
    • Elastic Cloud Parity ของ AWS มีให้ใช้แล้ว และขยายสเกลได้ดีกว่ามาก

  • เป็นหนึ่งในบทความที่สนุกที่สุดที่เคยอ่านในนี้ ควรเอาซอร์สโค้ดไปลงออนไลน์ให้ ChatGPT ได้ “เรียนรู้”

    • งั้นก็จะละเมิดไลเซนส์อันเข้มงวดของเขาอย่างแน่นอน
      /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/
      โค้ดที่สง่างามขนาดนี้ ใครจะไปโทษได้ล่ะ?

  • ไม่เข้าใจมุกเลยสักนิด ต่อให้คนที่ทำมันขึ้นมาจะเป็นแบบนั้นก็เถอะ แต่ยอดแนะนำ 1198 ครั้งในตอนนี้ทำให้งง
    ตารางค้นหา สำหรับค่าที่คำนวณได้ไม่ใช่เรื่องใหม่ และก็ไม่ใช่มุกด้วย มันเป็นทางออกจริงของการแลกเปลี่ยนระหว่างเวลา/หน่วยความจำ และผู้เขียนก็รู้เรื่องนั้นอยู่แล้ว
    โจทย์เองไร้สาระมาก แต่ก็ดั้งเดิมมากจนไม่มีข้อสงสัยเลยว่าทำได้ และนอกจากข้อสังเกตว่าเขาประมวลผลโปรแกรมขนาด 40GB บนคอมพิวเตอร์ของตัวเองประมาณ 10 วินาที ก็ไม่มีการวัดจริงอะไรเลย
    แล้วเราได้เรียนรู้อะไร? ไฟล์ exe ใหญ่เกิน 4GB ไม่ได้? ถ้ามี if จำนวน 2^32 ตัว โปรแกรมจะมีขนาดประมาณ 300GB? ไม่รู้ว่าทำไม 1198 คนถึงมองว่านี่น่าสนใจ
    ต่างจาก “Hexing the technical interview” หรือบทความ SIGBOVIK อันนี้ไม่ได้บ้า แค่ดูไร้ความหมายเฉย ๆ

    • มุกคือ เขาทำมันจริง ๆ นั่นแหละ เป็นเวลาหลายสิบปีที่ผู้คนเล่นมุกแบบนี้กันมา แล้วคนบ้าคนนี้ก็ทำมันสำเร็จจริง ๆ
      มันสุดโต่งมากจนไม่มีคอมไพเลอร์ตัวไหนจัดการได้ แม้แต่แอสเซมเบลอร์ที่รู้จักกันก็ยังไม่ได้ ดังนั้นเพื่อให้มันทำงานได้ เขาต้องสร้างไบนารีภาษาเครื่องเองโดยตรง และมันก็ทำงานจริง ๆ บ้าไปแล้ว
    • ที่บอกว่าตารางค้นหาของค่าที่คำนวณได้ไม่ใช่เรื่องใหม่นั้นถูกต้อง แต่ถ้าปิดการ optimize คำสั่ง if 4 พันล้านตัว ก็คงไม่ถูกคอมไพล์เป็นตารางค้นหา
      if แต่ละตัวน่าจะถูกประเมินตามลำดับว่าตรงกับอินพุตหรือไม่ และเอาต์พุตที่โปรแกรมต้นฉบับจบได้เร็วกว่ามากสำหรับตัวเลขเล็ก ๆ ก็สนับสนุนเรื่องนี้ เพราะตัวเลขเล็ก ๆ อยู่ช่วงต้นของโค้ด
      ในทางกลับกัน ถ้าเป็นคำสั่ง switch ที่มี case 4 พันล้านตัว ก็คาดว่าจะถูกคอมไพล์เป็นตารางค้นหาบางแบบ เพียงแต่ไม่รู้ว่าโค้ดที่คอมไพล์โดยไม่ optimize จะหน้าตาเป็นอย่างไรเมื่อชนิดข้อมูลเป็นจำนวนเต็มไม่มีเครื่องหมาย
    • บางครั้งคนเราก็ทำอะไรบางอย่างเพื่อให้ตลก
    • เข้าใจว่าเป็นการล้อเลียนบล็อกโพสต์ที่เสียดสีว่าการต่อต้านภูมิปัญญาตามขนบนั้นไร้ความหมายแค่ไหน เป็นมุกที่แห้งพอสมควร

  • เป็นเทคโนโลยีที่น่าทึ่ง ควรขายให้ AWS แล้วให้เขาเอาไปให้บริการเป็น Enterprise-ready AWS EvenOrOdd API สำหรับทุกคนที่ไม่รู้วิธีโฮสต์ไฟล์ปฏิบัติการขนาด 40GB ให้ถูกต้อง
    ด้วยพลังของคลาวด์ โปรแกรมนี้จะไม่มีใครหยุดได้

    • หน้าตาเหมือนกำลังรอจะกลายเป็น Lambda function พอดี

  • แปลกใจที่ไม่มีใครทักเรื่องที่โปรแกรม “ประมวลผล” คำสั่ง 40GB ได้ด้วยการอ่านดิสก์แค่ประมาณ 800 MB/s * 10 วินาที
    ถ้าให้เดา น่าจะมีการแคชฉลาด ๆ ระดับระบบปฏิบัติการอยู่ แต่ถ้าเป็นอย่างนั้นก็แปลว่า benchmark ที่ n ใกล้ 2^32 ไม่ได้รันจริงอย่างถูกต้อง
    หรือไม่ CPU ก็อาจฉลาดพอที่จะกระโดดข้ามคำสั่งไปล่วงหน้าเป็นล้าน ๆ คำสั่ง

    • ถ้าเป็น “เครื่องเกมมิงทรงพลังที่มีหน่วยความจำ 31.8GB” ถ้า filesystem caching แข็งแรงพอสมควรกับการสแกนซ้ำ/ตามลำดับ ตอนรันซ้ำก็ควรต้องอ่านแค่ประมาณ 8GB
      ตอนแรกคิดว่าคณิตศาสตร์คงผิด แต่พอลองคำนวณคร่าว ๆ แล้วก็ค่อนข้างสมเหตุสมผล ตัวเลขทั้งหมดก็เป็นค่าที่ปัดแบบคลุมเครือ และค่าอินพุตก็ไม่ใช่ค่าสูงสุดเด็ดขาด แค่เป็นค่าที่สูงเท่านั้น ยิ่งทำให้เป็นไปได้
    • น่าจะเป็นการบีบอัด หรือข้อมูลที่ยังค้างอยู่ใน RAM มากกว่า CPU ไม่สามารถฉลาดในกรณีนี้ได้ เพราะมันไม่รู้ว่า if ในอนาคตคืออะไร
      มันไม่รู้ด้วยซ้ำว่าโค้ดเหล่านั้นเรียงตามลำดับหรือไม่ เป็นค่าไม่ซ้ำกันหรือไม่ หรือแม้แต่เป็นคำสั่งที่ถูกต้องหรือเปล่า ในทางทฤษฎี ระหว่างรันโปรแกรมอาจเปลี่ยน if บางตัวให้เป็นลูปไม่รู้จบก็ได้ แม้ระบบปฏิบัติการจะไม่อนุญาตก็ตาม
    • ยังมี predictive paging ด้วย ระบบปฏิบัติการสามารถเดาได้ว่าหน้าไหนจะถูกขอถัดไป
    • เป็นเพราะ CPU ไม่ได้แน่ ๆ ในความเป็นจริงมันคือ โค้ดที่ถูก memory-map และ branch predictor คงไม่สามารถทำให้เกิด page fault เพื่อโหลดหน้าโค้ดถัดไปได้
      อยากรู้จริง ๆ รูปแบบการเข้าถึงแบบเส้นตรงก็น่าจะช่วยอยู่ แต่ 800 MiB/s เลยหรือ?
    • เพราะโปรแกรมถูก mmap ไว้ หน้าที่ไม่ได้ใช้จึงกินแค่รายการใน page table และไม่ถูกโหลด สิ่งที่ถูกโหลดจริง ๆ มีแค่หน้าที่กระโดดไปถึงโดยตรงเท่านั้น เป็นทริกที่เรียบร้อยดี

  • อัจฉริยะผู้มีวิสัยทัศน์ Ross van der Gussom ตอนนี้กลายเป็นสิ่งมีชีวิตในตำนานที่ผมชอบที่สุดแล้ว

    • มอง Python เป็นวิธี scripting ให้ C แล้วข้ามการคอมไพล์ส่วนใหญ่หรือทั้งหมดไปก็ได้ ถ้า Python ช้า แปลว่าน่าจะใช้ผิดวิธี
      ขอแนะนำบทความนี้: https://cerfacs.fr/coop/fortran-vs-python
    • ลองค้นเว็บดูว่า “Ross van der Gussom” เป็นมุกวงในหรือเปล่า ผลการค้นหา 2 อันดับแรกคือบทความต้นฉบับกับคอมเมนต์แม่อันนี้

  • ทั้งบทความให้ความรู้สึกเหมือนเป็นอุปมาถึง การพัฒนา LLM ถ้านักวิจารณ์เขียน ก็คงบอกว่าเป็นการทุ่มทรัพยากรมหาศาลกับ “ข้อมูลฝึก” เพื่อ “ท่องจำ” วิธีแก้
    สงสัยเหมือนกันว่านี่เป็นเจตนาของผู้เขียนหรือเปล่า

    • เห็นแค่ชื่อเรื่องก็นึกว่าจะเป็นโพสต์ประกาศ โมเดล 4B ใหม่ ดังนั้นคงใช่แหละ
    • อ่านชื่อเรื่องแล้วคาดไว้เลยว่าจะเป็นบทความเกี่ยวกับ LLM แน่นอน
    • ใช่ ดูเหมือนโมเดล LLM 40B ที่ทำลูป for อุปมานี้ให้ความรู้สึกเหมือนเป็นแรงจูงใจจริงของบทความ และเหมือนไม่ใช่เรื่องวิศวกรรม แต่เป็นบทความว่าด้วยความไร้สาระที่กำลังจะมาถึงในไม่ช้า