কারণ: ব্রাঞ্চ প্রিডিকশন (Branch Prediction)। আধুনিক CPU-র পাইপলাইনে শর্তাধীন জাম্প (if-else) অনুমান করে আগাম থেকে ইনস্ট্রাকশন ফেচ করে।
উদাহরণ
if(arr[i] > 50) {
// Operation B
} else {
// Operation A
}
সোর্টেড অ্যারে: 1, 2, 3... 50, 51... 100
A, A, A, ... A, A, B, B, B... Branch Predictor: সহজে প্রিডিক্ট করতে পারে (প্রথমে সব A, পরে সব B) Pipeline: সঠিক ব্রাঞ্চ লোড হয়, মিসপ্রিডিকশন কম
আনসোর্টেড অ্যারে: 5, 51, 6, 90, 4, 49, 60...
A, B, A, B, A, A, B... Branch Predictor: প্রিডিক্ট করা খুব কঠিন Pipeline: বারবার মিসপ্রিডিকশন, ফ্লাশ, রি-ফেচ → স্লো
নোট: এটি কম্পাইলার অপ্টিমাইজেশন নয়, CPU হার্ডওয়্যার ব্রাঞ্চ প্রিডিক্টরের বৈশিষ্ট্য। সোর্টেড ডেটা ব্রাঞ্চ প্রিডিকশন ফ্রেন্ডলি।
সুপারিশ: হট লুপে যদি ব্রাঞ্চ থাকে, ডেটা সোর্ট করলে স্পিডআপ পাওয়া যায় (বিশেষ করে সিমপ্ল-if)।
