‏وقتی if برنامه‌ت رو کند می‌کنه

حرف اصلی این مطلب اینه که روی پردازنده‌های امروزی، جلوگیری از خطای پیش‌بینی پرش یکی از کلیدی‌ترین راه‌های تندکردن برنامه‌ست، و مؤثرترین راهش هم اینه که اصلاً پرشی وجود نداشته باشه. مثالش هم عمداً ساده‌ست: یه آرایه رو بگرد و هر عدد کوچیک‌تر از ۵۰۰ رو تو آرایهٔ دوم کپی کن.

پیاده‌سازی مستقیمش تو زبان C همون چیزیه که همه می‌نویسیم؛ اگه عددها تصادفی باشن، نتیجهٔ شرط برای واحد پیش‌بینی پرش غیرقابل‌حدسه و نرخ خطا بالا می‌ره. هر خطا هم یعنی پردازنده باید خط لولهٔ اجراشو خالی کنه و از نو شروع کنه:

for (int i = 0; i < 1000; i++) {
    if (numbers[i] < 500) {
        small_numbers[smlen] = numbers[i];
        smlen += 1;
    }
}

نسخهٔ بدون پرش یه ترفند تمیز می‌زنه: همیشه مقدار رو می‌نویسه، ولی شمارنده رو فقط وقتی جلو می‌بره که شرط برقرار باشه — یعنی نتیجهٔ صفر یا یکِ مقایسه رو مستقیم به شمارنده اضافه می‌کنه. این کار یه نوشتن بی‌قیدوشرط تو حافظه اضافه می‌کنه، ولی هزینه‌ش معمولاً خیلی کمتر از جریمهٔ سنگین خطای پیش‌بینیه:

for (int i = 0; i < 1000; i++) {
    small_numbers[smlen] = numbers[i];
    smlen += (numbers[i] < 500);
}

برای اندازه‌گیری، هر دو تابع هزار بار روی صد هزار عدد تصادفی اجرا شدن. روی اپل M1 با بهینه‌سازی -O1 نسخهٔ شرطی ۰.۳۴۵ ثانیه و نسخهٔ بدون پرش ۰.۰۳۶ ثانیه طول کشیده. روی یه Xeon هم همین نسبت تکرار شده: ۰.۵۷۶ در برابر ۰.۱۱۰ ثانیه. نویسنده می‌گه -O3 سرعت بیشتری نداده و فقط کد تولیدشده رو بزرگ‌تر کرده.

نگاه به اسمبلی توضیح می‌ده چه اتفاقی افتاده. تو نسخهٔ شرطی کامپایلر یه پرش شرطی تولید می‌کنه ، ولی تو نسخهٔ بدون پرش سراغ cinc یا setle می‌ره که بدون هیچ جهشی شمارنده رو زیاد می‌کنن. جریان کنترل کاملاً خطی می‌مونه و پردازنده می‌تونه از تمام پهنای خط لوله‌ش استفاده کنه.

سؤال بعدی اینه که چرا خود کامپایلر این تبدیل رو انجام نمی‌ده. جواب نویسنده دو تیکه‌ست: اول اینکه کامپایلر ماهیت داده‌های تو رو نمی‌دونه و اگه فقط کسر کوچیکی از عددها شرط رو پاس کنن، نسخهٔ شرطی سریع‌تره چون پیش‌بینی تقریباً همیشه درسته. دوم اینکه نسخهٔ بدون پرش هر بار می‌نویسه، و کامپایلر مجاز نیست فرض کنه نوشتن بی‌قیدوشرط تو حافظه بی‌خطره؛ شاید اون شرط اصلاً برای جلوگیری از نوشتن بیرون بافر بوده.

یه جزئیات جالب دیگه هم اضافه می‌کنه: اگه اندازهٔ آرایه رو به ده هزار یا کمتر برسونی، فاصلهٔ کارایی کم می‌شه، چون جدول‌های تاریخچهٔ پیش‌بینی‌کننده اون‌قدر بزرگ هستن که الگو رو حفظ کنن و با تکرار روی همون آرایه به دقت تقریباً کامل برسن. صد هزار عنصر این حافظهٔ داخلی رو اشباع می‌کنه. آخر مطلب هم اشاره می‌کنه که کوییک‌سورت به‌خاطر ماهیت پارتیشن‌بندیش گزینهٔ عالی‌ای برای همین سبک برنامه‌نویسیه.

نکات کلیدی:

• خطای پیش‌بینی پرش، خط لولهٔ پردازنده رو خالی می‌کنه و هزینه‌ش سنگینه
• به‌جای شرط، نتیجهٔ صفر یا یکِ مقایسه رو مستقیم به شمارنده اضافه کن
• روی M1 زمان از ۰.۳۴۵ به ۰.۰۳۶ ثانیه رسیده؛ روی Xeon از ۰.۵۷۶ به ۰.۱۱۰
• کامپایلر خودش این کارو نمی‌کنه چون نه توزیع داده رو می‌دونه نه اجازهٔ نوشتن اضافه داره
• با داده‌های کوچیک‌تر، پیش‌بینی‌کننده الگو رو یاد می‌گیره و تفاوت کم می‌شه