การเดินทางการปรับปรุงประสิทธิภาพที่น่าทึ่งได้ดึงดูดความสนใจของชุมชนโปรแกรมเมอร์ โดยแสดงให้เห็นว่าการปรับปรุงอัลกอริทึมสามารถให้ประสิทธิภาพที่ดีกว่าการอัปเกรดฮาร์ดแวร์อย่างมาก โครงการนี้เกี่ยวข้องกับการสร้างตัวถอดรหัสภาพ Quicktake 150 สำหรับคอมพิวเตอร์ Apple II ที่ทำงานบนโปรเซสเซอร์ 6502 ที่ความเร็วเพียง 1MHz - โปรเซสเซอร์จากช่วงทศวรรษ 1970 ที่มีข้อจำกัดอย่างรุนแรงเมื่อเทียบกับมาตรฐานปัจจุบัน
ข้อมูลจำเพาะของโปรเซสเซอร์ 6502 :
- ความเร็วสัญญาณนาฬิกา: 1MHz
- สถาปัตยกรรม: โปรเซสเซอร์ 8-bit
- รีจิสเตอร์: มีรีจิสเตอร์ 8-bit เพียง 3 ตัวเท่านั้น
- หน่วยความจำ: พื้นที่หน่วยความจำที่สามารถกำหนดที่อยู่ได้สูงสุด 64KB
- RAM ทั่วไป: มี RAM ที่ใช้งานได้ 16-32KB (ส่วนที่เหลือใช้โดยระบบปฏิบัติการและการแสดงผล)
- คุณสมบัติพิเศษ: การกำหนดที่อยู่แบบ zero-page สำหรับ 256 ไบต์แรกของหน่วยความจำ
พลังของการทำน้อยลงมากกว่าการทำให้มีประสิทธิภาพมากขึ้น
ข้อมูลเชิงลึกที่โดดเด่นที่สุดจากเรื่องราวการปรับปรุงประสิทธิภาพนี้ท้าทายความคิดแบบเดิมเกี่ยวกับการปรับปรุงประสิทธิภาพ แทนที่จะเพียงแค่ทำให้การดำเนินงานที่มีอยู่เร็วขึ้น ผลตอบแทนที่ใหญ่ที่สุดมาจากการกำจัดงานที่ไม่จำเป็นออกไปทั้งหมด ชุมชนได้ยอมรับหลักการนี้ โดยหลายคนสังเกตว่าการทำหลายสิ่งอย่างรวดเร็วไม่ดีเท่ากับการทำสิ่งที่จำเป็นน้อยที่สุดให้เร็วขึ้น
การเปลี่ยนแปลงของตัวถอดรหัสเริ่มต้นด้วยการยกเลิกการประมวลผลสีทั้งหมด เนื่องจากผลลัพธ์สุดท้ายเป็นโมโนโครมอยู่แล้ว การเปลี่ยนแปลงเพียงครั้งเดียวนี้ลดภาระการคำนวณจาก 101 ล้านคำสั่ง x86_64 เหลือเพียง 26 ล้าน - การปรับปรุง 75% จากการตัดสินใจเชิงกลยุทธ์ครั้งเดียว
หมายเหตุ: 6502 เป็นไมโครโปรเซสเซอร์ 8 บิตที่มีเพียงสามรีจิสเตอร์และหน่วยความจำสูงสุดที่อยู่ได้ 64KB ทำให้มีข้อจำกัดด้านทรัพยากรอย่างมากเมื่อเทียบกับโปรเซสเซอร์สมัยใหม่
เทคนิคการปรับปรุงประสิทธิภาพหลัก:
- การตัดการประมวลผลสี: 101M → 26M คำสั่ง (ลดลง 75%)
- การกำจัดบัฟเฟอร์: ลบการจัดเก็บข้อมูลชั่วคราวและลูปที่ไม่จำเป็น
- การปรับปรุงการหาร: แทนที่การหาร 153,600 ครั้งด้วยการหาร <1,500 ครั้งโดยใช้ตารางค้นหา
- การปรับปรุงการเข้าถึงหน่วยความจำ: การจัดทำดัชนีแบบทีละบรรทัดแทนการกำหนดที่อยู่แบบใช้การคูณ
- การถอดรหัส Huffman: การประมวลผลแบบทีละบิตแทนวิธีบัฟเฟอร์ 16 บิต
ข้อจำกัดด้านหน่วยความจำขับเคลื่อนโซลูชันที่สร้างสรรค์
การอภิปรายได้เน้นย้ำว่าการทำงานภายใต้ข้อจำกัดด้านหน่วยความจำที่รุนแรงบังคับให้นักพัฒนาคิดแตกต่างเกี่ยวกับการออกแบบซอฟต์แวร์ Apple II โดยทั่วไปมี RAM น้อยกว่า 64KB ที่ใช้ได้ โดยส่วนใหญ่สงวนไว้สำหรับระบบปฏิบัติการและหน่วยความจำแสดงผล
ซอฟต์แวร์สมัยใหม่มีหน่วยความจำเกือบไม่จำกัดเมื่อเทียบกับน้อยกว่า 1MB ที่เป็นเรื่องปกติในโครงการเหล่านี้ มันเป็นบทเรียนที่ฉันต้องเรียนรู้อย่างแน่นอน
ข้อจำกัดนี้นำไปสู่แนวทางที่นวัตกรรม เช่น การประมวลผลภาพในแถบ 16 พิกเซลและการกำจัดบัฟเฟอร์กลางทุกที่ที่เป็นไปได้ กระบวนการปรับปรุงประสิทธิภาพเกี่ยวข้องกับการทำความเข้าใจว่าบัฟเฟอร์ชั่วคราวแต่ละตัวทำอะไรและกำจัดสิ่งที่ไม่จำเป็นสำหรับผลลัพธ์สุดท้ายออกไปอย่างเป็นระบบ
การปรับปรุงอัลกอริทึมเทียบกับการปรับแต่งภาษาแอสเซมบลี
แม้ว่าภาษาแอสเซมบลีที่ปรับแต่งด้วยมือจะให้การปรับปรุงที่สำคัญ การอภิปรายของชุมชนเน้นว่าการเปลี่ยนแปลงอัลกอริทึมให้ผลลัพธ์ที่ยิ่งใหญ่กว่ามาก โครงการนี้แสดงให้เห็นสิ่งนี้โดยการแทนที่การดำเนินการหาร 153,600 ครั้งด้วยน้อยกว่า 1,500 ครั้งผ่านตารางค้นหาที่คำนวณล่วงหน้า
การใช้งานแอสเซมบลีสุดท้ายรวมถึงการปรับปรุงที่ชาญฉลาด เช่น การใช้โค้ดที่แก้ไขตัวเองเพื่อปรับแต่งที่อยู่บัฟเฟอร์แทนที่จะรักษาตัวแปรพอยน์เตอร์ และการสร้างตารางค้นหาเฉพาะสำหรับการดำเนินงานทั่วไป อย่างไรก็ตาม การปรับปรุงระดับไมโครเหล่านี้มาหลังจากการปรับโครงสร้างอัลกอริทึมหลักได้บรรลุผลตอบแทนด้านประสิทธิภาพส่วนใหญ่แล้ว
หมายเหตุ: โค้ดที่แก้ไขตัวเองเปลี่ยนคำสั่งของตัวเองระหว่างการทำงาน ซึ่งเป็นเทคนิคการปรับปรุงประสิทธิภาพทั่วไปบนโปรเซสเซอร์ยุคแรก แต่โดยทั่วไปจะหลีกเลี่ยงในการเขียนโปรแกรมสมัยใหม่
การประมวลผลภาพและการรับรู้ของมนุษย์
การอภิปรายด้านข้างที่น่าสนใจเกิดขึ้นเกี่ยวกับวิธีที่ระบบการมองเห็นของมนุษย์ประมวลผลภาพกลางระหว่างการถอดรหัส สมาชิกชุมชนบางคนสังเกตว่าภาพที่มีพิกเซลสีดำกระจายอยู่จริงๆ แล้วดูมีคุณภาพภาพที่สูงกว่าเวอร์ชันที่ประมวลผลสุดท้าย แม้จะมีข้อมูลปริมาณเท่ากัน
ปรากฏการณ์นี้อาจเกี่ยวข้องกับวิธีที่สมองของเราแทรกข้อมูลภาพที่หายไป โดยทำการประมวลผลภาพที่ถูกลบออกจากอัลกอริทึมอย่างมีประสิทธิภาพ พิกเซลสีดำอาจทำหน้าที่เป็นรูปแบบของการกระจายสีที่ช่วยให้ระบบการมองเห็นของเราเติมช่องว่างได้อย่างมีประสิทธิภาพมากกว่าอัลกอริทึมการแทรกแบบดั้งเดิม
ผลลัพธ์การปรับปรุงประสิทธิภาพ:
- การใช้งานเริ่มต้น: เวลาในการถอดรหัส 70 นาที
- เวอร์ชันที่ปรับปรุงแล้วขั้นสุดท้าย: เวลาในการถอดรหัสต่ำกว่า 1 นาที
- การปรับปรุงโดยรวม: ประสิทธิภาพเร็วขึ้น 70 เท่า
- การลดจำนวนคำสั่ง: จาก 101M เหลือ 2M คำสั่ง x86_64 (ลดลง 95%)
ศิลปะที่สูญหายของการเขียนโปรแกรมที่จำกัดทรัพยากร
โครงการนี้ได้จุดประกายการไตร่ตรองในวงกว้างเกี่ยวกับวิธีที่การพัฒนาซอฟต์แวร์สมัยใหม่ได้ห่างไกลจากการเขียนโปรแกรมที่ใส่ใจทรัพยากร หลายคนในชุมชนสังเกตว่านักพัฒนาปัจจุบันที่ได้รับการฝึกฝนหลักในภาษาที่มีการจัดการขยะอัตโนมัติพร้อมหน่วยความจำอุดมสมบูรณ์ มักขาดความตระหนักถึงต้นทุนการคำนวณของโค้ดของพวกเขา
การเปลี่ยนแปลงนี้แสดงถึงการเปลี่ยนแปลงพื้นฐานในวัฒนธรรมการเขียนโปรแกรม ในขณะที่นักพัฒนายุคแรกต้องพิจารณาทุกไบต์ของหน่วยความจำและรอบโปรเซสเซอร์อย่างรอบคอบ การพัฒนาสมัยใหม่มักให้ความสำคัญกับการปรับใช้อย่างรวดเร็วมากกว่าประสิทธิภาพ การปรับปรุงประสิทธิภาพ 70 เท่าที่บรรลุในโครงการนี้แสดงให้เห็นถึงผลตอบแทนที่เป็นไปได้เมื่อนักพัฒนากลับไปสู่การคิดที่เน้นการปรับปรุงประสิทธิภาพ
การอภิปรายชี้ให้เห็นว่าการมีสมาชิกทีมอย่างน้อยบางคนที่เน้นการปรับปรุงประสิทธิภาพโดยเฉพาะอาจเป็นประโยชน์ต่อโครงการสมัยใหม่หลายโครงการ ซึ่งอาจให้การปรับปรุงอย่างมากคล้ายกับที่บรรลุบนฮาร์ดแวร์ที่เก่าแก่กว่าหลายทศวรรษนี้
อ้างอิง: Optimizing a 6502 image decoder, from 70 minutes to 1 minute