Loop Optimize

พอดีว่าผมอ่านเรื่อง Locality of reference แล้วมันน่าสนใจ มันเป็น topic เกี่ยวกับการ optimize ของ memory access ว่าเราจะเขียนโปรแกรมยังไงให้การเข้าถึง memory นั้นเร็วที่สุด ( ถ้าหากเราเข้าถึงเร็วมันก็หมายถึงว่า โปรแกรมของเราก็เร็วขึ้นด้วย ) โดยปกติแล้วในภาษา c/c++ เมื่อเราเขียนข้อมูลในลักษณะของ Array นั้นตัวเลขที่อยู่ด้านซ้ายสุดจะเป็น row ส่วนตัวต่อมาจะเป็น column และวิธีการเขียนให้เพิ่มประสิทธิภาพของเรานั้น ก็ควรจะเขียนให้มันมีการเคลื่อนที่ของตำแหน่งที่จะอ่านต่อไปในลักษณะอ่านอยู่ใน memory page เดียวกัน ดูรูปประกอบ

จากภาพ ประกอบ Memory Page นั้นจะเรียงเป็นลักษณะ เหมือนลิ้นชักที่เป็นชั้นๆ (row) มันก็เหมือนกับ เมื่อเราเปิดตู้เอกสาร ที่มีหลายๆลิ้นชัก ถ้าเราจะหาเอกสารสักชิ้น ลองคิดว่าถ้าเราหาทีละชั้น โดยหยิบออกมาทีละชิ้นจนหมดชั้นนั้นแล้วค่อยไปเริ่มชั้นใหม่ เทียบกับ เปิดออกมาหนึ่งชั้นและหยิบมาหนึ่งชั้นแล้วก็ปิด หลังจากนั้นก็เปิดชั้นต่อไปแล้วก็หยิบมาตรวจอีก 1 ชิ้นแล้วก็ไปชั้นใหม่ แบบไหนเร็วกว่า

ก็แน่นอนว่า การค้นหาทีละชั้นแล้วค่อยไปหาชั้นต่อไปนั้นเร็วกว่า การเขียนโปรแกรมก็ไม่ได้ต่างอะไร เพื่อเป็นการเห็นชัดๆ ผมมีตัวอย่าง Code ภาษา C ที่ทำการคำนวนการคูณของ Matrix

ตัวอย่าง code แรก ผมทำการคำนวนโดยที่ ตำแหน่งที่ต้องเปลี่ยนบ่อยที่สุดก็คือ k และแน่นอนว่ามันเป็นตำแหน่งของ row

และ code ที่สอง โดยผมสลับตำแหน่งของ Loop ให้ตำแหน่งที่ต้องเปลี่ยนบ่อยที่สุดคือ j และมันก็เป็น column

ก็อย่างที่ผมบอกไป ว่าถ้าเราเข้าถึงข้อมูลทีละชั้น (row) แล้วค่อยๆเลี่อนไปทีละอัน กับหา 1 อันแล้วเปลี่ยนชั้น (row ) อะไรจะ เร็วกว่า ก็ตอบแทบไม่ต้องคิดเลย นั่นก็คือ code อันที่สองมันย่อมเร็วกว่าแน่ๆ เอาละ งั้นเรามาลองทดสอบกันดูเลยดีกว่า ว่ามันจะเร็วกว่าสักเท่าไหร่กันเชียว

จาก code ข้างบน ผลลัพธ์ของ สอง Loop นี้ทำงานเหมือนกัน แต่วิธีการต่างกัน
และผลลัพธ์จากการทำงานได้แบบนี้
Loop A Total time: 23
Loop B Total time: 6

โอ้โห จะเห็นว่า มันทำงานเร็วกว่าถึง 4 เท่า !!!

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

Download Source Code

5 thoughts on “Loop Optimize”

Leave a Reply