รู้จักและทำให้โค้ดทำงานเร็วขึ้นด้วย Locality

เนื่องจากกำลังนั่งอ่านวิชา Computer System Architecture อยู่สำหรับสอบไฟนอลแล้วเจอตัวอย่างที่น่าสนใจและ(รู้สึกว่า)เข้าใจง่ายดี เลยอยากเอามาแชร์ให้หลายๆคนดูกัน

ผมมีโค้ดสั้นๆมาให้ดูสองแบบ

โค้ดทั้งสองแบบนี้ทำงานเหมือนกันคือ ทำการสร้าง Array 2 มิติขึ้นมา จากนั้นก็ทำการลูปเพื่อหาผลรวมของค่าใน Array นั้นเก็บไปที่ตัวแปร acc แล้วจบการทำงาน

จุดที่ต่างกันของโค้ดสองแบบนี้คือ แบบแรกจะลูปตัวแปร col ก่อน ส่วนแบบหลังจะลูปที่ตัวแปร row ก่อน ซึ่งก็ดูไม่น่าจะมีอะไร ดูน่าจะทำงานได้เร็วเท่าๆกัน หรืออาจจะต่างกันบ้างเล็กน้อย

มาดูผลลัพธ์กัน

แบบแรก ลูป col ก่อน ใช้เวลา 10.7 วิ

แบบหลัง ลูป row ก่อน ใช้เวลา 1.9 วิ

ผลลัพธ์ก็คือ แบบแรกใช้เวลาทำงาน 10.661 วินาที ส่วนแบบหลังใช้เวลาทำงาน 1.925 วินาที จะเห็นได้ว่า โค้ดแบบหลังของเราทำงานได้เร็วกว่าแบบแรกมาก

ทำไมแบบหลังถึงเร็วกว่า?

เนื่องจากโค้ดแบบหลังนั้นทำให้ Cache (เมมโมรีแบบนึงที่ทำงานได้เร็วกว่า RAM) สามารถใช้ประโยชน์จาก Spatial Locality ได้ จึงทำให้สามารถทำงานได้เร็วกว่า

เราเริ่มจากการทำความรู้จักกับคำว่า Locality กันก่อนดีกว่า

Locality หรือ Locality of reference คือ ปรากฏการณ์การที่โปรแกรมเรียกหาข้อมูลที่อยู่ตำแหน่งเดิมหรือใกล้ๆเดิมซ้ำในช่วงเวลาขณะหนึ่ง แบ่งเป็น 2 ประเภทหลักๆคือ

1. Temporal locality คือ การเรียกข้อมูลที่เคยถูกเรียกไปแล้วซ้ำ
2. Spatial locality คือ การเรียกข้อมูลใกล้ๆข้อมูลที่เคยถูกเรียกไปแล้ว

Locality เป็นปรากฏการณ์ที่เกิดขึ้นบ่อยในการเขียนโปรแกรม ทำให้ Cache ซึ่งบรรจุข้อมูลได้น้อย นำเรื่องนี้มาใช้ในการเลือกว่าข้อมูลไหนควรอยู่ใน Cache บ้าง

ในตอนที่ทำการสร้าง Array ขนาด 20000*20000 นั้น ด้านในเมมโมรี(RAM) จะทำการจองพื้นที่ที่ติดกันไว้เรียงกันไปแบบนี้

เมื่อมีการเข้าถึง arr[0][0] สิ่งที่เกิดขึ้นคือ Cache จะนำข้อมูลใกล้ๆ เช่น arr[0][1], arr[0][2], arr[0][3], etc. เข้าไปเก็บอยู่ใน Cache ด้วย เพราะว่ามีโอกาสถูกเรียกใช้ได้มาก จาก Spatial Locality

ข้อมูลก้อนแรกๆจะถูกเอาไปเก็บใน Cache ตั้งแต่ตอนขอ arr[0][0]

ตอนที่ CPU รันโปรแกรมนั้น จะหาข้อมูลที่ต้องการจากใน Cache ก่อน ถ้าหาไม่เจอจึงไปหาใน RAM ต่อ (ซึ่ง Cache ทำงานได้เร็วกว่า RAM อยู่แล้วในหลักสิบถึงร้อยเท่า)

กลับมาดูที่โค้ดเดิมกัน

โค้ดแรก รัน 10.7 วิ

ดูที่โค้ดแรก ลองพิจารณาลูปทีละรอบ

1. acc += arr[0][0] // หา arr[0][0] จาก RAM, Cache เก็บ arr[0][0], arr[0][1], arr[0][2] และอื่นๆไปด้วย
2. acc += arr[1][0] // หา arr[1][0] จาก RAM, Cache เก็บ arr[1][0], arr[1][1], arr[1][2] และอื่นๆไปด้วย

จะเห็นได้ว่าโค้ดนี้ใช้ประโยชน์จากความเร็วของ Cache ไม่ได้ เพราะไม่ได้เรียกข้อมูลซ้ำ และ ข้อมูลที่เรียกก็ไม่ได้อยู่ใกล้กับข้อมูลที่เคยถูกเรียก (ห่างกันตั้ง 20000 ช่องแน่ะ)

ในขณะที่ถ้าเราดูที่โค้ดแบบหลัง

โค้ดหลัง รัน 1.9 วิ

ในแต่ละลูปนั้น

1. acc += arr[0][0] // หา arr[0][0] จาก RAM, Cache เก็บ arr[0][0], arr[0][1], arr[0][2] และอื่นๆไปด้วย
2. acc += arr[0][1] // อ่าน arr[0][1] จาก Cache (เร็วมากๆ)

จะเห็นได้ว่าข้อมูลที่ถูกใช้ในลูปถัดไป จะถูกนำไปเก็บใน Cache แล้ว ซึ่งทำให้โค้ดนี้สามารถทำงานได้เร็วกว่า

ทดลองกับ Programming Language อื่นๆ

Nodejs

Python

ในภาษาอื่นๆก็เห็นถึงความเร็วที่แตกต่างกันอยู่ดี จะมากจะน้อยคิดว่าคงขึ้นกับ Optimization ของ interpreter/compiler ด้วย

สรุปและทิ้งท้าย

สรุปง่ายๆว่า การทำให้โค้ดทำงานเร็วขึ้นนั้น สามารถทำได้ง่ายๆโดยทำให้เกิด Locality ขึ้น เช่น ใช้ข้อมูลตัวเดิม ใช้ข้อมูลที่อยู่ใกล้ๆตัวเดิมให้เสร็จก่อน เพื่อที่ Cache จะได้ทำงานได้อย่างเต็มที่

สำหรับหัวข้อนี้ก็คิดว่ามีประโยชน์ในด้านความเข้าใจเรื่อง Locality, Cache, RAM มากกว่า แต่ถ้ามีงานที่จำเป็นต้องทำให้โค้ดทำงานได้เร็วแล้ว Optimize ที่ Algorithm ไม่ได้แล้ว ก็คิดว่าสามารถเอาเรื่องนี้ไปใช้ให้เกิดประโยชน์ได้เหมือนกัน

ขอบคุณครับ