ใน C++ การประมวลผลอาร์เรย์ที่เรียงลำดับแล้ว (sorted array) เร็วกว่าอาร์เรย์ที่ไม่ได้เรียง (unsorted array) เนื่องจาก Branch Prediction (การคาดการณ์การแบ่งทาง)
ในสถาปัตยกรรมคอมพิวเตอร์ Branch prediction กำหนดว่า conditional branch (การกระโดดเงื่อนไข) ใน instruction flow ของโปรแกรม มีแนวโน้มจะถูกนำไปใช้ (taken) หรือไม่ (not taken)
ตัวอย่าง
if (arr[i] > 50) {
// Do some operation B
} else {
// Do some operation A
}
กรณีอาร์เรย์เรียงแล้ว (Sorted):
1, 2, 3, 4, 5, ... 50, 51, ... 100 A, A, A, A, A, A, A, B, B, ... CPU คาดการณ์ได้ถูกต้อง: โหลด branch ที่ถูกต้องล่วงหน้า (pipeline) ไม่มี pipeline flush
กรณีอาร์เรย์ไม่ได้เรียง (Unsorted):
5, 51, 6, 90, 4, 49, 60, ... A, B, A, B, A, A, B, ... CPU คาดการณ์ไม่ได้: branch prediction fail บ่อย → pipeline flush บ่อย → ช้าลงมาก
สรุป: ข้อมูลที่เรียงแล้วทำให้ branch pattern น่าคาดเดาได้ (predictable) CPU สามารถ speculative execution ได้มีประสิทธิภาพ ข้อมูลสุ่มทำให้ branch prediction ล้มเหลวบ่อย ทำให้ pipeline ต้อง flush และ refetch บ่อย = ช้าลง
ข้อสังเกต: สมัยใหม่ CPU มี branch predictor ทรงพลัง (TAGE, perceptron) และ compiler อาจ optimize branchless code (cmov, SIMD) แต่หลักการยังคงใช้ได้ โดยเฉพาะในลูปที่ซ้ำซากมาก
