چرا پردازش یک آرایه مرتب سریع تر از پردازش یک آرایه نامرتب است؟
در اینجا قطعه ای از کد ++C قرار داده شده که رفتاری عجیبی از خود نشان می دهد. به دلایلی عجیب، مرتب کردن داده ها به طور معجزه آسایی کد را شش برابر سریع تر می کند:
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! With this, the next loop runs faster.
std::sort(data, data + arraySize);
// Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}
- بدون
std::sort(data, data + arraySize);، کد در 11.50 ثانیه اجرا می شود. - اگر داده ها مرتب شده باشد، کد در 1.93 ثانیه اجرا می شود.
در ابتدا، فکر می کردم این موضوع فقط یک مشکل مربوط به زبان یا کامپایلر است، بنابراین جاوا را امتحان کردم.
import java.util.Arrays;
import java.util.Random;
public class Main
{
public static void main(String[] args)
{
// Generate data
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
data[c] = rnd.nextInt() % 256;
// !!! With this, the next loop runs faster
Arrays.sort(data);
// Test
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Primary loop
for (int c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}
که نتیجه ای مشابه ولی با شدت کمتری داشت.
اولین ایده ای که داشتم این بود که مرتب کردن داده ها را وارد کش می کند، اما بعد ها متوجه شدم که ایده احمقانه ای است چرا که آرایه ها در همان زمان ایجاد می شوند.
- چرا چنین نتیجه ای به وجود می آید؟
- چرا پردازش یک آرایه مرتب شده سریع تر از پردازش یک آرایه نامرتب صورت می گیرد؟
کد نتایج مختلف و مستقلی را جمع بندی می کند، بنابراین ترتیب آن نباید اهمیتی داشته باشد.
برای این پرسش 4 پاسخ وجود دارد
شما قربانی شکست در پیش‌بینی پرش شدی.
پیش‌بینی‌کننده پرش چیست؟
محل اتصال یک راه آهن را در نظر بگیر:
Image توسط Mecanismo, از طریق Wikimedia Commons. استفاده شده تحت لیسانس CC-By-SA 3.0 .
بر فرض مثال، در نظر بگیر که این مربوط به سده 1800 میلادی هست - پیش از این که ارتباطات رادیویی یا راه های ارتباطی از راه دور وجود داشته باشند.
شما اپراتور یک محل اتصال هستی و می شنوی که یک قطار در حال آمدن هست. هیچ ایده ای نداری که قراره از کدوم راه بره. شما قطار رو متوقف می کنی و از راهبر می پرسی که به کدام جهت می ره. سپس سوئیچ درست رو انجام میدی.
قطارها سنگین هستند و لختی زیادی دارند. بنابراین زمان زیادی نیاز داره که شروع به حرکت کنه و متوقف بشه.
راه بهتری وجود داره؟ شما می تونی مسیر قطار رو حدس بزنی!
- اگر درست حدس زدی، قطار به حرکت خودش ادامه می ده.
- اگر اشتباه حدس زدی، کاپیتان توقف می کنه و برای سوئیچ کردن بین مسیر سر شما داد می زنه.
اگر هر بار درست حدس بزنی، قطار هیچ وقت نیازی به توقف نداره.
اگر اکثرا اشتباه حدس بزنی، قطار کلی زمان رو صرف متوقف شدن و شروع دوباره خواهد کرد.
یک عبارت شرطی رو در نظر بگیر: در مرحله پردازش، یک دستور پرش هست:
شما یک پردازنده هستی و یک پرش می بینی. هیچ ایده هم نداری که کدوم مسیر رو باید بری. چکار می کنی؟ اجرا رو متوقف می کنی و منتظر می مونی تا دستورات قبلی تمام و کمال انجام بشن. حالا راه درست رو ادامه میدی.
پردازنده های امروزی پیچیده هستند و پایپ لاین های طولانی دارند. در این صورت زمان زیادی براشون طول میکشه تا "شروع به کار کنند" و "متوقف بشن"
راه بهتری هست؟ حدس بزن که پرش به کدوم سمت باید انجام بشه!
- اگر درست حدس زده باشی، به اجرا کردن دستورات ادامه میدی
- اگر اشتباه حدس زده باشی، باید پایپ لاین رو تخلیه کنی و به نقطه پرش برگردی. حالا میتونی مسیر دیگه رو امتحان کنی.
اگر هربار درست حدس بزنی، هیچ وقت لزومی نداره که روند اجرا متوقف بشه.
اگر اکثرا اشتباه حدس بزنی، کلی زمان صرف متوقف کردن، برگشت و شروع دوباره میشه.
این پیش بینی پرش هست. قبول دارم که این بهترین قیاسی که میشه مثال زد نیست چرا که قطار میتونه با داشتن یک پرچم مسیر رو اطلاع بده. اما در کامپیوترها، پردازنده تا آخرین لحظه نمیدونه که پرش رو باید به کدوم سمت بزنه.
بنابراین از نظر استراتژیکی چطور میشه به شکلی حدس بزنی که تعداد دفعاتی که قطار باید متوقف بشه و مسیر دیگه ای رو امتحان کنه رو به حداقل برسونی؟ میتونی به گذشته نگاه کنی! اگر قطار در 99 درصد از مواقع به سمت چپ میره، در این صورت حدس تو به سمت چپ میشه. اگر هم فرق کنه حدس تو هم فرق می کنه. اگر هر سه بار در میون یک مسیر رو انتخاب میکنه، تو هم همون شکلی حدس میزنی...
به عبارت دیگه، سعی می کنی که یک الگو شناسایی کنی و طبق اون پیش بری. این تا حدودی روش کار پیش بینی کنندگان پرش هست.
اکثر اپلیکیشن ها پرش هایی دارند که به خوبی قابل پردازش هستند. بنابراین پیش بینی کنندگان پرش امروزی معمولا بالای 90 درصد از پیش بینی ها را درست انجام میدن. اما اگر با پرش های غیر قابل پیش بینی روبرو بشن که هیچ الگوی شناخته شده ای ندارند، پیش بینی کنندگان پرش از منظر مجازی ناکارآمد می شن.
برای بیشتر خواندن: مقاله "پیش بینی کننده پرش" در ویکی پدیا
همونطور که در پاسخ بعدی اشاره شده، مقصر این عبارت شرطی هست:
if (data[c] >= 128)
sum += data[c];
به یاد داشته باش که داده ها به طور مساوی بین 0 و 255 تقسیم شدند. زمانی که داده ها مرتب می شن، تقریبا نصفه اول وارد عبارت شرطی نمیشن. بعد از اون، همه داده ها وارد عبارت شرطی میشن.
این حالت برای پیش بینی کنندگان پرش بسیار آشناست چرا که پرش پشت سر هم یک مسیر رو برای چند بار طی می کنه. حتی یک saturating counter ساده هم درست پیش بینی میکنه مگر برای تعداد کمی از موارد بعد از این که مسیر عوض میشه.
تجسم سریع:
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)با این حال، وقتی داده ها کاملا تصادفی هستند، پیش بینی کننده پرش ناکارآمد میشه چرا که نمیتونه داده های تصادفی رو پیش بینی کنه. بنابراین احتمالا حدود 50 درصد از پیش بینی ها نادرست از آب در میاد (که بهتر از حدس زنی تصادفی نیست).
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completely random - hard to predict)
بنابراین چه کار میشه کرد؟
اگر کامپایلر قادر به بهینه کردن پرش ها به یک حرکت شرطی نباشه، در صورتی که بخوای خوانایی رو قربانی عملکرد کنی، میتونی یک سری تکنیک ها رو امتحان کنی.
جایگزینی:
if (data[c] >= 128)
sum += data[c];
با:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
با این کار پرش از بین میره و با چند عملیات بیتی جایگزین میشه.
(توجه داشته باش که این تکنیک دقیقا برابر با عبارت شرطی اصلی نیست. ولی در این حالت، برای تمامی مقادیر ورودی داده ها معتبر هست[].)
بنچمارک ها: Core i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 Release
// Branch - Random
seconds = 11.777
// Branch - Sorted
seconds = 2.352
// Branchless - Random
seconds = 2.564
// Branchless - Sorted
seconds = 2.587
Java - NetBeans 7.1.1 JDK 7 - x64
// Branch - Random
seconds = 10.93293813
// Branch - Sorted
seconds = 5.643797077
// Branchless - Random
seconds = 3.113581453
// Branchless - Sorted
seconds = 3.186068823
مشاهدات:
- با پرش: تفاوت زیادی بین داده مرتب شده و نشده وجود داره.
- با تکنیک: تفاوتی بین داده مرتب شده و نشده نیست.
- در رابطه با ++C، تکنیک در واقع نسبت به زمان با پرش در حالتی که داده ها مرتب شده هستند خیلی کم آهسته تره.
یک قائده تجربی کلی اینه که در حلقه های کوتاه از پرش های وابسته به داده خودداری بشه(مثل چیزی که در این همین مثال هست)
بروزرسانی:
GCC 4.6.1 با
-O3یا-ftree-vectorizeدر x64 توانایی ایجاد حرکت شرطی رو داره. بنابراین تفاوتی بین داده مرتب شده و نشده نیست و در هر دو حالت سریعه
یا یکجورایی سریعه: در حالت مرتب شده،cmovمیتونه آهسته تر باشه به ویژه اگر GCC اون رو در مسیر اساسی قراره بده به جای این که فقطaddکنه، به ویژه در Intel پیش از Broadwell حالتی کهcmovتاخیر 2 سیکله داره: gcc optimization flag -O3 makes code slower than -O2)- VC++ 2010 در ایجاد حرکات شرطی برای این پرش حتی تحت
/Oxناتوان هست. - Intel C++ Compiler (ICC) 11 به طور معجزه آسا عمل میکنه. دو تا حلقه رو به هم تبدیل میکنه، در نتیجه پرش های غیر قابل پیش بینی به حلقه بیرونی منتقل میشه (hositing). در این صورت نه تنها در برابر پیش بینی اشتباه در امانه، بلکه دو برابر نسبت به چیزی که GCC و ++VC میتونه ایجاد کنه، سریع تره! به عبارت دیگه، ICC از مزیت حلقه تست برای فائق اومدن به بنچمارک بهره می بره.
- اگر به کامپایلر Intel کد بدون پرش بدی، اون فقط به طور کامل وکتوریزش میکنه... و به همون اندازه که با پرش، سریعه (با تغییر حلقه ها به هم)
چیزی که میخوام بگم اینه که حتی کامپایلر های کامل امروزی میتونن در بهینه کردن کد به شدت نسبت به هم متفاوت عمل کنند.
امتیاز31525👍
پیش بینی کننده پرش.
در رابطه با یک آرایه مرتب شده، شرط data[c] >= 128 در ابتدا برای مقادیری false هست، سپس برای تمامی مقادیر بعدی تبدیل به true میشه. پیش بینی این ساده هست. اما در صورتی که آرایه نامرتب باشه، باید برای پرش ها هزینه کنید.
امتیاز4046👍
Daniel Fischer
همونطور که به خوبی در پاسخ Mysticial به خوبی توضیخ داده شده، دلیل بهبود عملکرد در حالتی که داده ها مرتبه این هست که جریمه پیش بینی پرش حذف میشه.
حالا، اگر به کد نگاه کنیم
if (data[c] >= 128)
sum += data[c];
می تونیم متوجه بشیم که معنی این پرش if... else... به خصوص اینه که زمانی که یک شرط برقرار شد چیزی اضافه بشه. این نوع از پرش به سادگی قابل تبدیل به یک عبارت حرکت شرطی هست، که میتونه به یک دستورالعمل حرکت شرطی کامپایل بشه:cmovlدر یک سیستم x86. پرش و جریمه احتمالی برای پیش بینی اون پرش حذف میشه.
در C، حتی ++C، عبارت که قراره به طور مستقیم (بدون هیچ بهینه سازی) به یک دستورالعمل حرکت شرطی در x86 کامپایل بشه، اپراتور سه بخشی ... ? ... : ...هست. بنابراین عبارت بالا رو به حالت برابر با اون بازنویسی می کنیم:
sum += data[c] >=128 ? data[c] : 0;
با در نظر داشتن خوانایی، می تونیم عوامل سرعت دهنده رو بررسی کنیم.
در روی یک Intel Core i7-2600K @ 3.4 GHz و Visual Studio 2010 Release Mode، بنچمارک(فرمتش از روی پاسخ Mysticial کپی شده):
x86
// Branch - Random
seconds = 8.885
// Branch - Sorted
seconds = 1.528
// Branchless - Random
seconds = 3.716
// Branchless - Sorted
seconds = 3.71
x64
// Branch - Random
seconds = 11.302
// Branch - Sorted
seconds = 1.830
// Branchless - Random
seconds = 2.736
// Branchless - Sorted
seconds = 2.737
نتیجه در چند بار آزمایش قوی هست. زمانی که نتیجه پرش غیر قابل پیش بینی هست، افزایش سرعت زیادی رو داریم، اما زمانی که قابل پیش بینی باشه کمی مشکل ایجاد میکنه. در واقع، در زمان استفاده از یک حرکت شرطی، عملکرد بدون توجه به الگوی داده یکسان هست.
حالا نگاهی نزدیک تر با تحقیق بر روی اسمبلی x86 که می سازند، میاندازیم. برای سادگی، از دو تابع max1 و max2 استفاده می کنیم.
max1از پرش شرطی if... else ... استفاده میکنه:
int max1(int a, int b) {
if (a > b)
return a;
else
return b;
}
max2 از اپراتور چندبخشی استفاده میکنه ... ? ... : ...:
int max2(int a, int b) {
return a > b ? a : b;
}
روی یک ماشین x86-64، چیزی که GCC -S میسازه:
:max1
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jle .L2
movl -4(%rbp), %eax
movl %eax, -12(%rbp)
jmp .L4
.L2:
movl -8(%rbp), %eax
movl %eax, -12(%rbp)
.L4:
movl -12(%rbp), %eax
leave
ret
:max2
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl %eax, -8(%rbp)
cmovge -8(%rbp), %eax
leave
ret
max2کد خیلی کمتری ایجاد میکنه چرا که از دستورالعمل cmovge استفاده می کنه. اما مزیت اصلی اینه که max2 درگیر پرش های شاخه ای،jmp نمیشه، که اگر نتیجه پیش بینی درست نباشه، مجازات قابل توجهی از نظر عملکرد خواهد داشت.
بنابراین، چرا حرکت شرطی عملکرد بهتری داره؟
در یک پردازنده عادی x86، اجرای دستورالعمل به چندین مرحله تقسیم میشه. تقریبا، برای کار با هر مرحله سخت افزار متفاوتی داریم. بنابراین نیازی نیست که برای به پایان رسیدن یک دستورالعمل منتظر بمونیم تا یک دستورالعمل جدید رو شروع به پردازش کنیم. به این محاسبات موازی می گن.
در مورد یک پرش، دستورالعمل زیر از روی قبلی تعیین میشه، بنابراین نمی تونیم از محاسبات موازی استفاده کنیم. باید یا منتظر بمونیم یا پیش بینی کنیم.
در مورد یک حرکت شرطی، دستورالعمل اجرای حرکت شرطی به چندین مرحله تقسیم میشه، اما اولین مراحل مثل Fetchو Decodeوابسته به نتیجه دستورالعمل قبلی نیستند؛ فقط مراحل بعدی نیازمند نتیجه هست. بنابراین، ما بخشی از زمان اجرای یک دستورالعمل رو منتظر می مونیم. به همین خاطر هست که نسخه حرکت شرطی زمانی که پیش بینی ساده به حساب میاد، کندتر از پرش هست.
کتاب Computer Systems: A Programmer's Perspective, second edition این مورد رو با جزئیات توضیح میده. میتونی بخش 3.6.6 رو برای Conditional Move Instructions، کل فصل 4 رو برای Processor Architecture و بخش 5.11.2 رو برای مطالعه بیشتر درباره Branch Prediction و Misprediction Penalties بررسی کنی
بعضی مواقع، بعضی از کامپایلر های امروزی میتونن کد های ما رو با عملکرد بهتری به اسمبلی تبدیل کنند. بعضی وقت بعضی از کامپایلر ها نمی تونند (کد داخل سوال از کامپایلر داخلی Visual Studio استفاده میکنه). دونستن تفاوت عملکرد بین پرش و حرکت شرطی زمانی که غیر قابل پیش بینی هست میتونه به ما کمک کنه که کد با عملکرد بهتری بنویسیم در حالتی که سناریو تا این حد پیچیده میشه که کامپایلر نمیتونه اون ها به طور خودکار بهینه سازی کنه.
امتیاز3276👍
WiSaGaN
اگر میخوای در رابطه با بهینه سازی بیشتری که میشه روی این کد انجام داد بیشتری بدونی، این رو در نظر بگیر:
با شروع از حلقه اصلی:
for (unsigned i = 0; i < 100000; ++i)
{
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
sum += data[j];
}
}
با تبدیل حلقه به همدیگه، می تونیم با به طور ایمن این حلقه رو به
for (unsigned j = 0; j < arraySize; ++j)
{
for (unsigned i = 0; i < 100000; ++i)
{
if (data[j] >= 128)
sum += data[j];
}
}
تغییر بدیم.
حالا، میتونی ببینی که if در کل اجرای حلقه i ثابت هست، بنابراین میتونی ifرو به بیرون انتقال بدی:
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
for (unsigned i = 0; i < 100000; ++i)
{
sum += data[j];
}
}
}
حالا، می بینی که با در نظر گرفتن این که floating point model این اجازه رو میده، حلقه داخلی میتونه به یک عبارت تکی ساده بشه:
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
sum += data[j] * 100000;
}
}
این یکی 100,000 برابر سریع تر از قبلی هست.
امتیاز2250👍
vulcan raven
