ประโยค If 4 พันล้านอัน

 (andreasjhkarlsson.github.io)
3 คะแนน โดย GN⁺ 2023-12-29 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

if 4 พันล้านบรรทัด

  • ระหว่างที่กำลังไล่อ่านโซเชียลมีเดียเมื่อไม่นานมานี้ ผู้เขียนเจอสกรีนช็อตนี้บนรถไฟ
  • โค้ดนี้เป็นตัวอย่างที่สมบูรณ์แบบของ time-memory tradeoff
  • จึงพยายามทำมันด้วยภาษา C เพื่อเพิ่มประสิทธิภาพ

โครงสร้างโค้ด

  • เขียนโค้ดภาษา C สำหรับตรวจสอบว่าเป็นเลขคู่หรือเลขคี่
  • คอมไพล์โดยปิดการทำ optimization
  • ทำงานได้ถูกต้องกับตัวเลข 0 ถึง 10 แต่มีปัญหาเมื่อมากกว่านั้น

เมตาโปรแกรมมิง

  • ใช้ Python ทำเมตาโปรแกรมมิงเพื่อสร้าง if statement
  • สร้างโปรแกรมสำหรับตรวจสอบเลขคู่และเลขคี่ของจำนวนเต็ม 8 บิต

ขยายเป็น 16 บิต

  • ขยายโปรแกรมด้วยวิธีเดียวกันสำหรับจำนวนเต็ม 16 บิต
  • สร้างไฟล์ C ขนาดประมาณ 130k บรรทัดและคอมไพล์มัน

ความท้าทายของ 32 บิต

  • พยายามขยายโปรแกรมไปยังจำนวนเต็ม 32 บิต
  • สร้างไฟล์ C ขนาด 330GB ได้ แต่คอมไพเลอร์ล้มเหลวเพราะ heap space ไม่พอ
  • และด้วยข้อจำกัดของฟอร์แมต Portable Executable จึงไม่สามารถจัดการไฟล์ที่ใหญ่กว่า 4GB ได้

เขียน machine code โดยตรง

  • เขียนฟังก์ชัน IsEven ด้วยภาษาแอสเซมบลี x86-64 โดยตรง
  • ใช้ Python คอมไพล์ machine code ด้วยมือ

สร้างไฟล์ executable

  • สร้างไฟล์ขนาด 40GB เพื่อระบุเลขคู่หรือเลขคี่สำหรับจำนวนเต็ม 32 บิตทั้งหมด
  • แมปไฟล์เข้าหน่วยความจำและใช้ function pointer เพื่อรันโค้ด

แก้บั๊กสุดท้าย

  • เปลี่ยนไปใช้ฟังก์ชัน strtoul เพื่อแก้ปัญหาการ parse จำนวนเต็มแบบ unsigned
  • โปรแกรมเร็วมาก และสามารถคืนผลลัพธ์ได้ภายใน 10 วินาทีแม้กับตัวเลขขนาดใหญ่

ความเห็นของ GN⁺

  • ความสำคัญ: บทความนี้ช่วยให้เข้าใจแนวคิดพื้นฐานของการเขียนโปรแกรมอย่าง time-memory tradeoff ได้ดี อีกทั้งยังเป็นตัวอย่างที่ดีว่าการไม่ทำ optimization ส่งผลต่อประสิทธิภาพจริงอย่างไร
  • ความน่าสนใจ: กระบวนการทดลองสำรวจความต่างด้านประสิทธิภาพระหว่างภาษาโปรแกรมและข้อจำกัดของคอมไพเลอร์นั้นน่าสนใจมาก โดยเฉพาะความพยายามเปรียบเทียบ Python กับภาษา C เพื่อเพิ่มประสิทธิภาพ
  • บทเรียน: บทความนี้แสดงให้เห็นว่าแนวทางที่ดูไม่มีประสิทธิภาพในตอนแรก บางครั้งก็อาจมีประโยชน์จริงในการแก้ปัญหาที่ซับซ้อน และยังเน้นย้ำความสำคัญของการมองหาวิธีแก้แบบสร้างสรรค์ในวิทยาการคอมพิวเตอร์

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

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

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

  • สรุปความคิดเห็นแรก:

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

  • สรุปความคิดเห็นที่สอง:

    • ยกตัวอย่างว่าจริง ๆ แล้วสามารถแก้ได้ด้วย for loop แบบง่าย ๆ แทนการใช้วิธีที่ซับซ้อนผ่านการสร้างโค้ด

  • สรุปความคิดเห็นที่สาม:

    • มุกเกี่ยวกับแพ็กเกจ npm is-even และ is-odd
    • จินตนาการว่าถ้าใช้ npm install จะมีการดาวน์โหลดแพ็กเกจขนาด 40GB

  • สรุปความคิดเห็นที่สี่:

    • เสนอให้ใช้ฐานข้อมูลเพื่อจำแนกเลขคู่และเลขคี่
    • แมปตัวเลขกับประเภทของมันไว้ในฐานข้อมูล SQLite เพื่อให้ไม่ต้องอัปเดตโปรแกรม

  • สรุปความคิดเห็นที่ห้า:

    • มองว่าบทความนี้สนุกมาก
    • เห็นว่าควรเผยแพร่ซอร์สโค้ดออนไลน์เพื่อให้ ChatGPT นำไปเรียนรู้ได้

  • สรุปความคิดเห็นที่หก:

    • เสนอไอเดียเกี่ยวกับเวอร์ชันแบบกระจาย
    • ให้แต่ละโฮสต์ตรวจสอบว่าเลขตรงกับชื่อโดเมนของตัวเองหรือไม่ แล้วส่งผลลัพธ์กลับมา

  • สรุปความคิดเห็นที่เจ็ด:

    • เสนอให้นำเทคโนโลยีนี้ไปขายให้ AWS แล้วให้บริการเป็น AWS EvenOrOdd API
    • เห็นว่าถ้าใช้พลังของคลาวด์ โปรแกรมนี้จะยิ่งทรงพลังขึ้น

  • สรุปความคิดเห็นที่แปด:

    • ตั้งคำถามว่าจะประมวลผลคำสั่ง 40GB ได้อย่างไร ด้วยความเร็วในการอ่านดิสก์ 800MB/s * 10 วินาที
    • คาดเดาว่าน่าจะมีการแคชอัจฉริยะระดับ OS หรือการเพิ่มประสิทธิภาพที่ทำให้ CPU ข้ามคำสั่งบางส่วนไปได้

  • สรุปความคิดเห็นที่เก้า:

    • อธิบายเทคนิคการใช้ lookup table เพื่อหลีกเลี่ยงการคำนวณที่มีต้นทุนสูง
    • แชร์ประสบการณ์ที่ใช้ไลบรารี libdivide และแทนการหารจำนวนเต็ม 8 บิตด้วย lookup table

  • สรุปความคิดเห็นที่สิบ:

    • เสนอการปรับแต่งด้วยการค้นหาแบบทวิภาค
    • เล่นมุกเกี่ยวกับการใช้ if-else แบบซ้อนกันเพื่อให้ทำงานด้วยความซับซ้อนเวลา O(logN)