فرادرسبهینه سازی کد های C و ++C – راهنمای کاربردی
ما همچنان از سوی توان سخت‌افزارهای خود محدود شده‌ایم. برخی حوزه‌ها هستند که سخت‌افزار کنونی ما عملاً کافی نیست و از آن جمله شبکه‌های عصبی و واقعیت مجازی هستند. بسیاری از دستگاه‌ها هستند که درگیر مسئله عمر باتری هستند و باید در مورد هر تیک CPU محتاط باشیم. حتی زمانی که از کلودها و میکروسرویس‌ها صحبت می‌کنیم، مراکز داده زیادی هستند که حجم بسیار بالایی از برق را مصرف می‌کنند. بنابراین بهینه سازی کد های نرم‌افزاری همواره یک ضرورت جدی محسوب می‌شود.
حتی رویه‌های تست خسته‌کننده نیز این اواخر تا 5 ساعت طول می‌کشند و این مسئله پیچیده‌ای است. عملکرد برنامه‌ها البته تا زمانی که ما را به دردسر بیندازد، مهم نیست. یک روش مدرن برای بهره‌برداری عملکرد بیشتر از تراشه‌های سیلیکونی این است که سخت‌افزار را هر چه پیچیده طراحی کنیم. بدین ترتیب ما وارد عصری می‌شویم که رایانه‌ها ریزتر می‌شوند، هسته‌ها افزایش می‌یابند و حافظه یک تنگنا محسوب می‌شود.
سخت‌افزارهای مدرن
در این بخش به بررسی خصوصیات سخت‌افزارهای امروزی می‌پردازیم.
CPU
- میلیاردها ترانزیستور
- تلاش برای پیش‌بینی آینده
- ردگیری وابستگی‌های داده‌ها و دستورها
- اجرای دستورها به صورت موازی و خارج از ترتیب
- قابل برنامه‌ریزی (یعنی میکروکد خاص خود را دارند)
- آگاه از حافظه و تکنیک‌های مجازی‌سازی CPU
- دارا بودن برخی دستورهای سطح بالا (مانند تابع‌های هش رمزنگاری)
- حتی برخی کدهای شبکه‌های عصبی برای پیش‌بینی بعضی موارد وجود دارند
- چند آسیب‌پذیری بسیار مهم تاکنون شناسایی شده‌اند
DRAM
- میلیاردها خازن
- میلیاردها خازن (واقعاً چیزی جز این نمی‌توان گفت!)
DRAM که اختصاری برای عبارت «حافظه با دسترسی تصادفی دینامیک» (Dynamic random-access memory) است از سلول‌های حافظه شامل یک خازن و یک ترانزیستور برای ذخیره‌سازی هر بیت استفاده می‌کند. این فناوری دارای ارزان‌ترین و متراکم‌ترین حالت ممکن است و از این رو به عنوان حافظه اصلی برای رایانه‌ها مورد استفاده قرار می‌گیرد.
ظرفیت بارگذاری و ذخیره‌سازی حافظه در اغلب موارد تنگنای یک سیستم محسوب می‌شود.
هر ارجاع به حافظه هزینه زمانی در حدود 100 نانوثانیه دارد. این بدان معنی است که یک CPU با سرعت 1 گیگاهرتزی باید 100 تیک یا بیشتر را صرف گرفتن یک پاسخ از حافظه بکند. بنابراین کش کردن مقادیر در حافظه به جای محاسبه مجدد در هر بار، می‌تواند عملاً 100 برابر کندتر باشد. اما دلیل این وضعیت چیست؟
حتی با این که CPU به قدر کافی هوشمند است تا داده‌های خود را از قبل آماده کند، اما در بسیاری موارد برنامه‌نویسان هنوز مسئول طرح‌بندی حافظه و الگوهای دسترسی هستند.
بنابراین در یک سو میلیون‌ها خط کد داریم و در سمت دیگر نیز تنوع معماری‌های سخت‌افزاری قرار دارند. معماری‌های زیادی متدهای دلخواه خود را برای دستیابی به بیشینه عملکردی یا کمینه کردن کاهش مصرف انرژی معرفی کرده‌اند. برای این که این شکاف را پر کنیم باید بیشترین بهره را از یک کامپایلر بهینه‌ساز بگیریم.
کامپایلرهای مدرن می‌توانند اصلاح‌های زیادی در کد ایجاد کنند و عملکرد را بهبود ببخشند. دانستن این که کامپایلر می‌تواند چه بکند یا نکند برای برنامه‌نویس‌ها مفید است.
کد منبعی که می‌نویسیم از سوی رایانه و یا برنامه‌نویسان دیگر خوانده می‌شود. اکنون بر روی خوانایی کد هنگامی که کامپایلرها آن را به زنجیره‌ای از دستورالعمل‌های بهینه برای ماشین تبدیل می‌کنند متمرکز می‌شویم.
متأسفانه هیچ فرایندی در دنیا به صورتی جادویی و خودکار صورت نمی‌گیرد. کامپایلرهای بهینه‌ساز C و ++C فاصله زیادی با وضعیت ایده‌آل دارند و درک این نکته که در پشت پرده چه می‌گذرد حائز اهمیت بالایی است. در هر حال این ابزاری است که ما هر روز از آن استفاده می‌کنیم.
«درک عملکرد به معنای درک بهینه‌سازی است.»
چندلر کاروث «سخنرانی آغازین همایش ++C در سال 2015»
با این که در ادامه این نوشته به توضیح موارد مرتبط با LLVM یا (clang) پرداخته‌ایم؛ اما همان مفاهیم در مورد GCC و تا حدود زیادی در مورد هر کامپایلر مدرن بهینه‌ساز دیگر نیز صدق می‌کند.
درک مقدماتی از LLVM IR
کامپایلرها تا حد زیادی وابسته به شکل انتساب منفرد استاتیک (SSA) هستند. یعنی نیازمند این هستند که هر متغیر دقیقاً یک بار انتساب یابد و هر متغیر پیش از استفاده تعریف شده باشد.
declare i32 @g(i32 %x)
define i32 @f(i32 %a, i32 %b) {
entry:
%c = add i32 %a, %b
%d = call i32 @g(i32 %c)
%e = add i32 %c, %d
ret i32 %e
}
کد فوق به نظر کاملاً سرراست می‌رسد:
- تابع‌ها: g@ و f@
- انواع: i32
- مقادیر (متغیرها): a%, %b, …
- دستورالعمل‌ها: — add, call, ret
گردش کنترل
declare i32 @g(i32 %x)
define i32 @f(i32 %a, i32 %b, i1 %flag) {
entry:
%c = add i32 %a, %b
br i1 %flag, label %then, label %else
then:
%d = call i32 @g(i32 %c) ret i32 %d
else:
ret i32 %c
}
- عملیات br: ایجاد انشعاب روی یک فلگ و رفتن به عملیات برچسب (متناظر). بدین ترتیب کل گردش کنترل اجرا می‌شود.
گردش داده
در این مورد نیز هر متغیر دقیقاً یک بار انتساب می‌یابد و هر متغیر پیش از استفاده تعریف می‌شود. اما چگونه می‌توان مقداری را که تنها در یک شاخه شرطی مانند %d در مثال فوق تعریف شده است، دریافت کرد؟
پاسخ دستورالعمل phi است که مقادیر شاخه را بر اساس این که از کدام مسیر آمده‌اید، در یک محل واحد ادغام می‌کند.
declare i32 @g(i32 %x)
define i32 @f(i32 %a, i32 %b, i1 %flag) {
entry:
%c = add i32 %a, %b
br i1 %flag, label %then, label %end
then:
%d = call i32 @g(i32 %c) br label %end
end:
%result = phi i32 [ %entry, %c ], [ %then, %d ]
ret i32 %result
}
اگر از entry آمده باشیم، در این صورت %result = %c و اگر از then آمده باشیم در این صورت %result = %d است.
به همین سادگی
در واقع LLVM IR به همین سادگی است. دستورالعمل‌های بسیار زیادی دیگری نیز هستند، اما چیزی جز این مفهوم در آن‌ها نخواهید یافت. صرفاً بر اساس همین بازنمایی می‌توان درک کرد که چه اتفاقی در پشت پرده رخ می‌دهد.
بهینه‌سازها چه می‌کنند؟
در این بخش به توضیح عملکرد درونی کامپایلرهای بهینه‌ساز می‌پردازیم.
مرحله 1: پاکسازی
فرانت‌اند کامپایلر یک کد ad-hoc IR را طوری تولید می‌کند گویی مقدار نامحدودی از حافظه را در اختیار دارد در واقع صرفاً برایش مهم است که الگوی روال‌ها برای بهینه‌ساز «آشنا» باشند. به مثال زیر توجه کنید:
int main(int argc, char * argv[]) {
if (argc != 2)
return -1;
printf("%s", argv[1]);
return 0;
}
این همان چیزی است که در صورت اجرای دستور clang -cc1 -emit-llvm -O0 example.c -o example.ll به دست می‌آوریم (بدون بهینه‌سازی). فرانت‌اند LLVM همه چیز را در حافظه قرار می‌دهد و از این رو زنجیره‌ای از alloca, store و load وجود دارند:
define i32 @main(i32 %argc, i8** %argv) #0 {
%1 = alloca i32, align 4
%2 = alloca i32, align 4
%3 = alloca i8**, align 8
store i32 0, i32* %1, align 4
store i32 %argc, i32* %2, align 4
store i8** %argv, i8*** %3, align 8
%4 = load i32, i32* %2, align 4
%5 = icmp ne i32 %4, 2
br i1 %5, label %6, label %7
; <label>:6 ; preds = %0
store i32 -1, i32* %1, align 4
br label %12
; <label>:7 ; preds = %0
%8 = load i8**, i8*** %3, align 8
%9 = getelementptr inbounds i8*, i8** %8, i64 1
%10 = load i8*, i8** %9, align 8
%11 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i32 0, i32 0), i8* %10)
store i32 0, i32* %1, align 4
br label %12
; <label>:12 ; preds = %7, %6
%13 = load i32, i32* %1, align 4
ret i32 %13
}
در مرحله پاکسازی یک کامپایلر تلاش می‌کند که دستورالعمل‌های وابسته به حافظه را با SSA حاصل از مقادیر جایگزین کند. متعاقباً کامپایلر تصمیم می‌گیرد که حافظه را تخصیص دهد یا از رجیسترها استفاده کند. برخی متغیرها (در واقع اکثر آن‌ها) به طور کامل حذف خواهند شد.
این آن اتفاقی است که هنگام فعال‌سازی بهینه‌سازی (O1-) رخ می‌دهد:
define i32 @main(i32 %argc, i8** nocapture readonly %argv) #0 {
%1 = icmp eq i32 %argc, 2
br i1 %1, label %2, label %6
; <label>:2 ; preds = %0
%3 = getelementptr inbounds i8*, i8** %argv, i64 1
%4 = load i8*, i8** %3, align 8, !tbaa !1
%5 = tail call i32 (i8*, ...) @printf(i8* nonnull getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* %4) #1
br label %6
; <label>:6 ; preds = %0, %2
%.0 = phi i32 [ 0, %2 ], [ -1, %0 ]
ret i32 %.0
البته این کد نه تنها پاکسازی بلکه بهینه‌سازی نیز شده است. اکنون می‌توانید ببینید که LLVM IR چگونه کد C را که از آن حاصل شده است تکرار می‌کند.
Icmp اعداد صحیح، اشاره‌گرها یا بردارها را مقایسه می‌کند و مقادیر بولی بازمی‌گرداند. آرگومان نخست یک کلیدواژه است که نوع فشرده‌سازی را مشخص می‌سازد. در اینجا icmp eq به معنی مقایسه برابری است. نمونه‌های دیگر می‌توانند شامل ult («کمتر از» به صورت بی علامت)، sge («بزرگ‌تر از» به صورت با علامت) و غیره باشد.
Getelementptr دستورالعملی است که همه عملیات حسابی اشاره‌گر را در LLVM مدیریت می‌کند. مهم نیست که یک عنصر آرایه باشد یا یک فیلد struct، در هر صورت آرگومان آخر getelementptr یک اندیس عنصر است.
<result> = getelementptr inbounds <ty>, <ty>* <ptrval>{, [inrange] <ty> <idx>}*
مرحله 2: Canonicalization
روش‌های مختلف زیادی برای نوشتن یک کد با استفاده از عبارت‌های گردش کنترل وجود دارند:
/*..1..............*/
int x;
if (flag)
x = y;
else
x = z;
/*..2..............*/
int x = flag ? y : z;
/*..3..............*/
int x = y;
if (!flag)
x = z;
/*..4..............*/
if (flag)
z = y;
int x = z;
یک بهینه‌ساز، گردش کنترل را به شکل canonical می‌نویسد و تلاش نمی‌کند که همه نسخه‌های ممکن را در یک کد منبع به رسمیت بشناسد.
بنابراین هر حلقه‌ای به صورت یک حلقه canonical درمی‌آید، گزاره‌های if-then به صورت گزاره‌های if-then با حالت canonical درمی‌آیند و همین طور موارد دیگر.
اگر به مثال نخست خود بازگردیم:
int main(int argc, char * argv[]) {
if (argc != 2)
return -1;
printf("%s", argv[1]);
return 0;
}
در اینجا با فهرست‌بندی LLVM IR متناظر مواجه هستیم؛ اما اندکی تغییر یافته است تا خوانایی آن بهبود یابد.
کد بدون بهینه‌سازی:
define i32 @main(i32 %argc, i8** %argv) {
entry:
%ret = alloca i32, align 4
%argc.ptr = alloca i32, align 4
%argv.ptr = alloca i8**, align 8
store i32 0, i32* %ret, align 4
store i32 %argc, i32* %argc.ptr, align 4
store i8** %argv, i8*** %argv.ptr, align 8
%argc_2 = load i32, i32* %argc.ptr, align 4
%flag = icmp ne i32 %argc_2, 2
br i1 %flag, label %if.then, label %if.end
if.then:
store i32 -1, i32* %ret, align 4
br label %return
if.end:
%argv_2 = load i8**, i8*** %argv.ptr, align 8
%array_index = getelementptr inbounds i8*, i8** %argv_2, i64 1
%array_value = load i8*, i8** %array_index, align 8
%printf_ret = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i32 0, i32 0), i8* %array_value)
store i32 0, i32* %ret, align 4
br label %return
return:
%ret_2 = load i32, i32* %ret, align 4
ret i32 %ret_2
}
کد if-then به صورت Canonical
define i32 @main(i32 %argc, i8** nocapture readonly %argv) {
entry:
%flag = icmp eq i32 %argc, 2
br i1 %flag, label %if.end, label %return
if.end:
%array_index = getelementptr inbounds i8*, i8** %argv, i64 1
%array_value = load i8*, i8** %array_index, align 8, !tbaa !1
%printf_ret = tail call i32 (i8*, ...) @printf(i8* nonnull getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* %array_value) #1
br label %return
return:
%retval.0 = phi i32 [ 0, %if.end ], [ -1, %entry ]
ret i32 %retval.0
}
ابتدا کدی هست که تعداد آرگومان‌ها را بررسی می‌کند: (if (argc!= 2.
قبلاً icmp ne وجود داشت که عدم برابری با دستورالعمل را مقایسه می‌کرد. اینک icmp eq را می‌بینیم که برابری را بررسی می‌کند. یک بهینه‌ساز نیازی به مدیریت دستورالعمل icmp ne ندارد؛ هر چند از سوی LLVM IR پشتیبانی می‌شود.
تفاوت دیگر این است که برچسب if.then و مسیر اجرای کد حذف شده‌اند. اینک برچسب return از همان منطق گره phi پیروی می‌کند.
مرحله 3: حذف تجریدها
آن چه ++C را از هر زبان برنامه‌نویسی دیگری متمایز می‌کند، توانایی آن برای ساخت تجریدهایی با collapse است.
چندلر کورث، «سخنرانی آغازین همایش ++C در سال 2015»
از نقطه نظر کامپایلر سه نوع اصلی از تجرید وجود دارند:
- تابع‌ها، فراخوانی‌ها و گراف فراخوانی
- حافظه، بارگذارها و ذخیره‌سازها
- حلقه‌ها
تابع‌ها، فراخوانی‌ها و گراف فراخوانی
تابع اساسی‌ترین تجرید انسانی است؛ اما پردازنده به آن نیازی ندارد. در این مرحله یک بهینه‌ساز این فرصت را دارد که دستورالعمل‌ها را به روشی بازآرایی کند که برای پردازنده مناسب‌تر است و از شر مقادیر زیادی از آن خلاص شود.
LLVM تلاش می‌کند که یک گراف فراخوانی روی کلاسترهای تابع‌ها تنظیم کند تا در چارچوبی گسترده‌تر عمل کند. برگ‌های این گراف، موارد طبیعی مناسب برای inline کردن هستند، چون این موارد هیچ تابع دیگری را فراخوانی نمی‌کنند. inline کردن باعث حذف شدن برگ‌ها می‌شود و برگ‌های جدیدی ایجاد می‌کند که آن‌ها را نیز می‌توان حذف کرد. این فرایند به همین ترتیب تکرار می‌شود. این تصمیم لازم نیست حتماً باینری باشد، چون inline کردن به صورت جزئی و حجم بالایی از shuffling نیز امکان‌پذیر است.
Inline کردن یا نکردن مهم‌ترین تصمیم در مورد تولید کد سریع محسوب می‌شود.
خوشبختانه تابع‌های زیادی صرفاً به منظور میانبرهایی برای تابع‌های دیگر ارائه می‌شوند. این تابع‌ها را می‌توان به سادگی حذف کرد.
int g(double x, double y, double z);
int f(struct S* s, double y, double x) {
return g(x, y, s->z);
}
اما موارد دشواری نیز وجود دارند که تصمیم در مورد inline کردن یا نکردن به مقدار آرگومان یا شرط انشعاب وابسته است. چنین مواردی تا زمانی که LLVM بتواند اطلاعات بیشتری کسب کند به تعویق می‌افتند. برای نمونه شما ممکن است یک الگوریتم مرتب‌سازی را بر مبنای اندازه بردار انتخاب کنید. در چنین مواردی بهینه‌ساز یک SSA از درخت می‌سازد تا بتواند اندازه واقعی این تصمیم را محاسبه کند. متأسفانه بهینه‌سازهای cross-function ممکن است نیازمند مقدار بالایی از منابع باشند تا بتوانند تصمیم صحیحی بگیرند و ممکن است گزینه‌های بسیار زیادی برای انتخاب کردن وجود داشته باشند. همچنین مواردی هستند که ممکن است در ابتدا ساده به نظر برسند؛ اما کدی که بهینه‌ساز ها تولید می‌کنند، بهترین کد ممکن نباشد.
HHVM (ماشین مجازی HipHop) یک ماشین مجازی PHP با JIT است. این ماشین برای جایگزینی HipHop که یک transpiler سورس PHP به ++C در فیسبوک بود، ایجاد شده است. زمانی که همه کدهای فیسبوک پس از گذشت 12 ماه از زمان توسعه روی HHVM اجرا می‌شدند، تا 7 برابر کند شده بودند.
تیم HHVM یک بررسی همه جانبه صورت دادند تا سبب این مشکل را بیابند و نتیجه کار memcpy بود که به شدت inline شده بود. اندازه کد تابع memcpy روی پلتفرم آن‌ها برابر با 11 کیلوبایت بود و موجب یک کوبیدگی کَش (cache thrashing) می‌شد. داده‌های مفیدی از طریق این کد در همه جای برنامه از کش CPU خارج می‌شدند.
راه‌حل آن‌ها پیاده‌سازی یک نسخه ساده‌تر از memcpy بود که به چند مسیر مختلف کد بر اساس اندازه داده‌های کپی شده، مدل CPU و غیره وابسته باشد. کد تابع ساده‌تر به جای کد اصلی در دو مسیر کش قرار گرفت.
تابع memcpy جدید در میکروبنچمارک‌های مختلف حافظه عملکردی به مراتب بدتر داشت؛ اما عملکرد کلی اپلیکیشن به طور کلی بهبود یافت.
به هر حال کلیدواژه inline هیچ وجه اشتراکی با فرایند واقعی inline کردن ندارد. کلیدواژه inline در واقع به عنوان یک سرنخ در gcc و احتمالاً کامپایلرهای دیگر استفاده می‌شود. در O1 تنها تابع‌هایی که به صورت inline نشانه‌گذاری شده‌اند، به منظور inline کردن استفاده می‌شوند.
حافظه، بارگذارها و ذخیره‌سازها
همان‌طور که گفته شد فرانت‌اند کامپایلر، کدها را چنان ایجاد می‌کند که گویی حافظه نامتناهی در اختیار دارد. در مورد تابع زیر:
int plus(int a, int b) {
int c = a + b;
return c;
}
LLVM کد غیر بهینه زیر را تولید می‌کند:
define i32 @plus(i32, i32) #0 {
%a.ptr = alloca i32, align 4
%b.ptr = alloca i32, align 4
%c.ptr = alloca i32, align 4
store i32 %a, i32* %a.ptr, align 4
store i32 %b, i32* %b.ptr, align 4
%a2 = load i32, i32* %a.ptr, align 4
%b2 = load i32, i32* %b.ptr, align 4
%c = add nsw i32 %a2, %b2
store i32 %c, i32* %c.ptr, align 4
%c2 = load i32, i32* %c.ptr, align 4
ret i32 %c2
}
در این حالت هر متغیر منفرد تخصیص یافته، ذخیره شده و بی درنگ از حافظه بازیابی می‌شود. با این حال کد بهینه بسیار معقول‌تر به نظر می‌رسد:
define i32 @plus(i32, i32) local_unnamed_addr #0 {
%c = add nsw i32 %b, %a
ret i32 %c
}
شکل SSA کاملاً مناسب است. یک بهینه‌ساز به دنبال بارگذارها و ذخیره‌سازهای حافظه می‌گردد و تلاش می‌کند مقادیر واقعی را بیابد. در مثال فوق این کار به سهولت صورت گرفته است. اکنون نمونه کمی پیچیده‌تر را بررسی می‌کنیم:
struct Point {
long long x, y;
Point plus(Point arg) const;
};
Point Point::plus(Point arg) const {
Point r;
r.x = x + arg.x;
r.y = y + arg.y;
return r;
}
IR غیر بهینه به صورت زیر است:
%struct.Point = type { i64, i64 }
; Function Attrs: noinline nounwind optnone ssp uwtable
define { i64, i64 } @Point.plus(%struct.Point*, i64, i64) #0 align 2 {
%r.ptr = alloca %struct.Point, align 8
%arg.ptr = alloca %struct.Point, align 8
%this.ptr = alloca %struct.Point*, align 8
%arg.rawptr = bitcast %struct.Point* %arg.ptr to { i64, i64 }*
%arg.x.ptr = getelementptr inbounds { i64, i64 }, { i64, i64 }* %arg.rawptr, i32 0, i32 0
store i64 %arg.x, i64* %arg.x.ptr, align 8
%arg.y.ptr = getelementptr inbounds { i64, i64 }, { i64, i64 }* %arg.rawptr, i32 0, i32 1
store i64 %arg.y, i64* %arg.y.ptr, align 8
store %struct.Point* %this, %struct.Point** %this.ptr, align 8
%this.ptr_2 = load %struct.Point*, %struct.Point** %this.ptr, align 8
%this.x.ptr = getelementptr inbounds %struct.Point, %struct.Point* %this.ptr_2, i32 0, i32 0
%this.x = load i64, i64* %this.x.ptr, align 8
%arg.x.ptr = getelementptr inbounds %struct.Point, %struct.Point* %arg.ptr, i32 0, i32 0
%arg.x = load i64, i64* %arg.x.ptr, align 8
%r.x = add nsw i64 %this.x, %arg.x
%r.x.ptr = getelementptr inbounds %struct.Point, %struct.Point* %r.ptr, i32 0, i32 0
store i64 %r.x, i64* %r.x.ptr, align 8
%this.y.ptr = getelementptr inbounds %struct.Point, %struct.Point* %this.ptr_2, i32 0, i32 1
%this.y = load i64, i64* %this.y.ptr, align 8
%arg.y.ptr = getelementptr inbounds %struct.Point, %struct.Point* %arg.ptr, i32 0, i32 1
%arg.y = load i64, i64* %arg.y.ptr, align 8
%r.y = add nsw i64 %this.y, %arg.y
%r.y.ptr = getelementptr inbounds %struct.Point, %struct.Point* %r.ptr, i32 0, i32 1
store i64 %r.y, i64* %r.y.ptr, align 8
%r.rawptr = bitcast %struct.Point* %r.ptr to { i64, i64 }*
%r.rawptr_2 = load { i64, i64 }, { i64, i64 }* %r.rawptr, align 8
ret { i64, i64 } %r.rawptr_2
}
دقت کنید که امضای تابع تغییر یافته است. امضای جدید به کامپایلر امکان می‌دهد که آرگومان‌ها را در رجیستر قرار دهد.
حالت قبل
(Point * this, Point arg)
حالت بعد
(Point * this, i64 arg.x, i64 arg.y)
گردش داده‌ها در این نمونه بسیار پیچیده‌تر شده است. به چند موقعیت حافظه دسترسی می‌یابیم و نتایج آن را در یک پشته ذخیره می‌کنیم و با اشاره‌گر صریح this سر و کار داریم.
روشی که LLVM برای توجیه آن چه رخ می‌دهد استفاده می‌کند، افراز حافظه است. LLVM تلاش می‌کند تا بارگذارها و ذخیره‌سازهای مجاور منفرد را به صورت struct ها و لایه‌ها بازسازی کند. در ادامه روش مدیریت این وضعیت از سوی بهینه‌ساز را می‌بینیم.
LLVM IR با O1-:
define { i64, i64 } @Point.plus(%struct.Point* nocapture readonly, i64, i64) local_unnamed_addr #0 align 2 {
%this.x.ptr = getelementptr inbounds %struct.Point, %struct.Point* %this, i64 0, i32 0
%this.x = load i64, i64* %this.x.ptr, align 8, !tbaa !3
%r.x = add nsw i64 %this.x, %1
%this.y.ptr = getelementptr inbounds %struct.Point, %struct.Point* %this, i64 0, i32 1
%this.y = load i64, i64* %this.y.ptr, align 8, !tbaa !8
%r.y = add nsw i64 %this.y, %2
%r_1 = insertvalue { i64, i64 } undef, i64 %r.x, 0
%r_2 = insertvalue { i64, i64 } %r_1, i64 %r.y, 1
ret { i64, i64 } %r_2
}
دستور insertvalue در بخش فوق یک مقدار را درون فیلد عضو در یک آرایه با مقدار sturct درج می‌کند. طرز کار آن با اندیس عنصر همانند getelementptr است.
<result> = insertvalue <aggregate type> <val>, <ty> <elt>, <idx>{, <idx>}*; yields <aggregate type>
نخستین بار یک مقدار پیچیده {i64, i64} را می‌گیریم و %r.x را در اندیس 0 درج می‌کنیم:
%r_1 = insertvalue { i64, i64 } undef, i64%r.x, 0
سپس شکل %r_2 را از %r_1 می‌سازیم.
%r_2 = insertvalue { i64, i64 } %r_1, i64%r.y, 1
اکنون هیچ alloca را نمی‌بینیم، زیرا struct میانی حذف شده و اینک مقادیر را می‌توان در رجیسترهای پردازنده ذخیره کرد. در حالت متضاد، دسترسی RAM می‌تواند عملاً 100 برابر کندتر باشد.
سریع‌ترین کد، کدی است که اجرا نمی‌شود.
حلقه‌ها
حلقه جایی است که اغلب زمان برنامه در آن صرف می‌شود، بنابراین حلقه‌ها به طور طبیعی اهداف اصلی بهینه‌سازها هستند. در این زمینه تحقیق‌های زیادی در دنیای کامپایلر صورت گرفته است. حلقه زیر را در نظر بگیرید:
int sum(const std::vector<int> & array) {
int result = 0;
for (auto i: array) {
result += i;
}
return result;
}
در مجموع در حدود 160 خط کد غیر بهینه LLVM IR وجود دارد. توجه کنید که هزاران تخصیص حافظه، ده‌ها فراخوانی تابع STL و کد زمان اجرای ++C وجود دارند. بنابراین وقایع زیادی در این حلقه اتفاق می‌افتند. در ادامه بخش کوچکی از IR غیر بهینه را می‌بینید:
; ... %36 = load %vector*, %vector** %27, align 8 %37 = bitcast %vector* %36 to %"class.std::__1::__vector_base"* %38 = getelementptr inbounds %"class.std::__1::__vector_base", %"class.std::__1::__vector_base"* %37, i32 0, i32 0 %39 = load i32*, i32** %38, align 8 store %vector* %36, %vector** %24, align 8 store i32* %39, i32** %25, align 8 %40 = load %vector*, %vector** %24, align 8 %41 = load i32*, i32** %25, align 8 store %"class.std::__1::__wrap_iter"* %23, %"class.std::__1::__wrap_iter"** %21, align 8 store i32* %41, i32** %22, align 8 %42 = load %"class.std::__1::__wrap_iter"*, %"class.std::__1::__wrap_iter"** %21, align 8 %43 = load i32*, i32** %22, align 8 store %"class.std::__1::__wrap_iter"* %42, %"class.std::__1::__wrap_iter"** %19, align 8 store i32* %43, i32** %20, align 8 %44 = load %"class.std::__1::__wrap_iter"*, %"class.std::__1::__wrap_iter"** %19, align 8 %45 = getelementptr inbounds %"class.std::__1::__wrap_iter", %"class.std::__1::__wrap_iter"* %44, i32 0, i32 0 %46 = load i32*, i32** %20, align 8 store i32* %46, i32** %45, align 8 %47 = getelementptr inbounds %"class.std::__1::__wrap_iter", %"class.std::__1::__wrap_iter"* %23, i32 0, i32 ; ...
LLVM این 160 خط کد را به تقریباً 170 خط کاملاً متفاوت از کد IR تبدیل می‌کند. به صورت مرحله به مرحله آن را بررسی می‌کنیم. با فرض این که همه تکنیک‌های بهینه‌سازی فوق به همراه فشرده‌سازی حافظه، و تجرید تابع‌ها اعمال شوند، در این مرحله کد IR تابع sum به صورت زیر درمی‌آید:
define i32 @sum(%vector* nocapture readonly dereferenceable(24)) #0 {
entry:
%begin_ptr = getelementptr inbounds %vector, %vector* %0, i64 0, i32 0, i32 0
%begin = load i32*, i32** %begin_ptr, align 8, !tbaa !2
%end_ptr = getelementptr inbounds %vector, %vector* %0, i64 0, i32 0, i32 1
%end = load i32*, i32** %end_ptr, align 8, !tbaa !8
br label %loop.head
loop.head:
%ptr = phi i32* [ %begin, %entry ], [ %ptr.next, %loop.latch ]
%x = phi i32 [ 0, entry], [ %x.next, %loop.latch ]
%cond = icmp eq i32* %ptr, %end
br i1 %cond, label %exit, label %loop.latch
loop.latch:
%i = load i32, i32* %ptr, align 4
%x.next = add nsw i32 %x, %i
%ptr.next = add nsw i32 %x, %i
br label %loop.head
exit:
ret i32 %x
}
در این مورد نیز یک شکل canonical وجود دارد. تمییز بین شکل حلقه از هر نوع عبارت گردش کنترلی دیگر برای بهینه‌سازی بسیار حائز اهمیت است.
define i32 @sum(%vector* nocapture readonly dereferenceable(24)) #0 {
entry:
%begin_ptr = getelementptr inbounds %vector, %vector* %0, i64 0, i32 0, i32 0
%begin = load i32*, i32** %begin_ptr, align 8, !tbaa !2
%end_ptr = getelementptr inbounds %vector, %vector* %v, i64 , i32 0, i32 1
%end = load i32*, i32** %end_ptr, align 8
%empty = icmp eq i32* %begin, %end
br i1 %empty, label %exit, label %loop.ph
loop.ph: ; preds = %entry
br label %loop
loop: ; preds = %loop.ph, %loop
%x = phi i32 [ 0, %loop.ph ], [ %x.next, %loop ]
%ptr = phi i32* [ %begin, %loop.ph ], [ %ptr.next, %loop ]
%i = load i32, i32* %ptr, align 4
%x.next = add nsw i32 %x, %i
%ptr.next = getelementptr inbounds i32, i32* %ptr, i64 1
%cond = icmp eq i32* %ptr.next, %end
br i1 %cond, label %loop.exit, label %loop
loop.exit: ; preds = %loop
%x.lcssa = phi i32 [ %x.next, %loop ]
br label %exit
exit: ; preds = %loop.exit, %entry
%x.result = phi i32 [ %x.lcssa, %loop.exit ], [ 0, %entry ]
ret i32 %x.result
اکنون ما loop.ph را داریم که pre-header حلقه و گره‌های loop.exit را شامل می‌شود. هدف از آن‌ها صرفاً ارائه ورودی و خروجی حلقه است. برچسب loop شامل loop.ph و خودش به عنوان یک عنصر پیشین است و loop.exit شامل حلقه به عنوان تنها عنصر پیشین خود است.
برچسب exit در تابع متفاوت است چون در آنجا کل حلقه پایان می‌یابد.
loop.exit دارای گره نامعمول phi است که تنها یک آرگومان (در خط 32) دارد:
%x.lcssa = phi i32 [%x.next, %loop]
این روش SSA برای بیان ادامه حیات x.next خارج از حلقه است. بنابراین یک مقدار از درون حلقه می‌توان برداشت. این شکل canonical حلقه است. پس از شناسایی چند تکنیک بهینه‌سازی مورد استفاده قرار می‌گیرد.
قبل از هر چیز، بهینه‌ساز تلاش می‌کند که تصمیم بگیرد آیا کلاً به یک حلقه نیاز دارد یا نه. برای نمونه اگر بهینه‌ساز بتواند اندازه یک آرایه را حدس بزند، اقدام به حذف حلقه می‌کند. این کاری است که هر کامپایلر ++C به خوبی انجام می‌دهد، چون شکل SSA به طور طبیعی انتشار ثابت‌ها را تسهیل می‌کند.
دسته دوم بهینه‌سازی‌ها نیازمند انتقال عملیات دارای افزونگی به خارج از حلقه هستند و شکل SSA امکان انجام آسان این کار را فراهم می‌سازد. تنها یک مدخل loop.ph وجود دارند و loop.exit مدخلی است که باید خارج شود. بهینه‌ساز رد هر گره phi را نگهداری می‌کند و از این رو می‌داند که چه چیزی داخل و خارج حلقه تغییر یافته است. هیچ نیازی به یک برنامه‌نویس برای کش کردن vector.size() یا فراخوانی‌های مشابه در یک متغیر محلی وجود ندارد. چون ما در زبان پایتون کار نمی‌کنیم. بهینه‌ساز همه کدهای غیر ضروری را از متن حلقه خارج می‌کند.
تکنیک دیگر به شرط انشعاب درون یک حلقه مرتبط است. به طور کلی بهینه‌ساز میل دارد نه تنها شرط را به خارج از حلقه منتقل کند؛ بلکه می‌خواهد حلقه‌های خاص مجزایی برای هر مورد ایجاد کند.
پس از این که تکنیک‌های فوق‌الذکر اجرا شدند یک کد حلقه کوچک‌تر و تمیزتر ایجاد می‌شود و این همان جایی است که برای بیشینه بهره‌برداری از پردازنده بهینه‌سازی می‌شود.
پردازنده‌های مدرن برای اجرای خط لوله (pipelines) های با دستورالعمل منفرد و داده چندگانه (SMID) بسیار بهینه هستند. از این رو بهینه‌ساز اقدام به بردار سازی حلقه (loop vectorization) می‌کند که حالت خاصی از SMID است. در مثال ما در مورد تابع sum وضعیت فوق به این معنی است که دستورالعمل add یکسانی چندین بار در هر تکرار اجرا می‌شود.
کد بهینه شده ممکن است تا حدودی ترسناک به نظر بیاید. پیش از آن که تلاش کنید با آن آشنا شوید یک مقدمه خلاصه را برای شما آماده کرده‌ایم.
- loop.vec32 حلقه برداری شده اصلی است. درون این حلقه یک <add nsw 4 x i32> می‌بینیم که دو بردار از 4 عدد صحیح 32 بیتی را با هم جمع می‌کند (نتیجه یک بردار <4 x i32> است). به علاوه این حلقه باز شده است و از این رو در هر تکرار اعداد صحیح 32 × 32 بیتی را می‌بلعد. البته یک آرایه باید به تعداد 32 یا بیشتر عنصر داشته باشد که به طرز صحیحی جایگیری شده باشند.
- <4 x i32> یک حلقه برداری شده کوچک‌تر است که با بردارهای <4 x i32> کار می‌کند که شامل اعداد صحیح 8 × 32 بیتی هستند.
- loop.scalar حلقه اصلی ما است. همه کاری که این حلقه انجام می‌دهد، جمع زدن دو عدد صحیح 32 بیتی به صورت یک به یک add nsw i32 است. این حلقه زمانی که آرایه کمتر از 8 عنصر داشته باشد از کار می‌افتد.
define i32 @sum(%"vector"* nocapture readonly dereferenceable(24)) local_unnamed_addr #0 {
%2 = getelementptr inbounds %"vector", %"vector"* %0, i64 0, i32 0, i32 0
%start_ptr = load i32*, i32** %2, align 8, !tbaa !3
%4 = getelementptr inbounds %"vector", %"vector"* %0, i64 0, i32 0, i32 1
%end_ptr = load i32*, i32** %4, align 8, !tbaa !9
%is_empty = icmp eq i32* %start_ptr, %end_ptr
br i1 %is_empty, label %exit, label %choose.array.size
; <label>:choose.array.size: ; preds = %1
%8 = ptrtoint i32* %start_ptr to i64
%last_elem_ptr = getelementptr i32, i32* %end_ptr, i64 -1
%10 = ptrtoint i32* %last_elem_ptr to i64
%size = sub i64 %10, %8
%size_log2 = lshr i64 %size, 2
%size_log2_plus1 = add nuw nsw i64 %size_log2, 1
%14 = icmp ult i64 %size_log2_plus1, 8
br i1 %14, label %loop.scalar.ph, label %has.min.vector.iterations
; <label>:loop.scalar.ph: ; preds = %loop.vec8.exit, %choose.array.size
%16 = phi i32 [ 0, %choose.array.size ], [ %103, %loop.vec8.exit ]
%17 = phi i32* [ %start_ptr, %choose.array.size ], [ %20, %loop.vec8.exit ]
br label %loop.scalar
; <label>:has.min.vector.iterations: ; preds = %choose.array.size
%size_log2_plus1_higher_bits = and i64 %size_log2_plus1, 9223372036854775800
%20 = getelementptr i32, i32* %start_ptr, i64 %size_log2_plus1_higher_bits
%21 = add nsw i64 %size_log2_plus1_higher_bits, -8
%22 = lshr exact i64 %21, 3
%23 = add nuw nsw i64 %22, 1
%24 = and i64 %23, 3
%25 = icmp ult i64 %21, 24
br i1 %25, label %loop.vec32.exit, label %loop.vec32.ph
; <label>:loop.vec32.ph: ; preds = %has.min.vector.iterations
%27 = sub nsw i64 %23, %24
br label %loop.vec32
; <label>:loop.vec32: ; preds = %loop.vec32, %loop.vec32.ph
%offset0 = phi i64 [ 0, %loop.vec32.ph ], [ %offset.next, %loop.vec32 ]
%vec.sum1 = phi <4 x i32> [ zeroinitializer, %loop.vec32.ph ], [ %vec.sum8, %loop.vec32 ]
%vec.sum0 = phi <4 x i32> [ zeroinitializer, %loop.vec32.ph ], [ %vec.sum9, %loop.vec32 ]
%chunks.left = phi i64 [ %27, %loop.vec32.ph ], [ %chunks.left.next, %loop.vec32 ]
%chunk1_begin = getelementptr i32, i32* %start_ptr, i64 %offset0
%34 = bitcast i32* %chunk1_begin to <4 x i32>*
%chunk1 = load <4 x i32>, <4 x i32>* %34, align 4, !tbaa !10
%chunk2_begin = getelementptr i32, i32* %chunk1_begin, i64 4
%37 = bitcast i32* %chunk2_begin to <4 x i32>*
%chunk2 = load <4 x i32>, <4 x i32>* %37, align 4, !tbaa !10
%vec.sum2 = add nsw <4 x i32> %chunk1, %vec.sum1
%vec.sum3 = add nsw <4 x i32> %chunk2, %vec.sum0
%offset1 = or i64 %offset0, 8
%chunk3_begin = getelementptr i32, i32* %start_ptr, i64 %offset1
%43 = bitcast i32* %chunk3_begin to <4 x i32>*
%chunk3 = load <4 x i32>, <4 x i32>* %43, align 4, !tbaa !10
%chunk4_begin = getelementptr i32, i32* %chunk3_begin, i64 4
%46 = bitcast i32* %chunk4_begin to <4 x i32>*
%chunk4 = load <4 x i32>, <4 x i32>* %46, align 4, !tbaa !10
%vec.sum4 = add nsw <4 x i32> %chunk3, %vec.sum2
%vec.sum5 = add nsw <4 x i32> %chunk4, %vec.sum3
%offset2 = or i64 %offset0, 16
%chunk4_begin = getelementptr i32, i32* %start_ptr, i64 %offset2
%52 = bitcast i32* %chunk4_begin to <4 x i32>*
%chunk4 = load <4 x i32>, <4 x i32>* %52, align 4, !tbaa !10
%chunk5_begin = getelementptr i32, i32* %chunk4_begin, i64 4
%55 = bitcast i32* %chunk5_begin to <4 x i32>*
%chunk5 = load <4 x i32>, <4 x i32>* %55, align 4, !tbaa !10
%vec.sum6 = add nsw <4 x i32> %chunk4, %vec.sum4
%vec.sum7 = add nsw <4 x i32> %chunk5, %vec.sum5
%offset3 = or i64 %offset0, 24
%chunk6_begin = getelementptr i32, i32* %start_ptr, i64 %offset3
%61 = bitcast i32* %chunk6_begin to <4 x i32>*
%chunk6 = load <4 x i32>, <4 x i32>* %61, align 4, !tbaa !10
%chunk7_begin = getelementptr i32, i32* %chunk6_begin, i64 4
%64 = bitcast i32* %chunk7_begin to <4 x i32>*
%chunk7 = load <4 x i32>, <4 x i32>* %64, align 4, !tbaa !10
%vec.sum8 = add nsw <4 x i32> %chunk6, %vec.sum6
%vec.sum9 = add nsw <4 x i32> %chunk7, %vec.sum7
%offset.next = add i64 %offset0, 32
%chunks.left.next = add i64 %chunks.left, -4
%70 = icmp eq i64 %chunks.left.next, 0
br i1 %70, label %loop.vec32.exit, label %loop.vec32, !llvm.loop !12
; <label>:loop.vec32.exit: ; preds = %loop.vec32, %has.min.vector.iterations
%72 = phi <4 x i32> [ undef, %has.min.vector.iterations ], [ %vec.sum8, %loop.vec32 ]
%73 = phi <4 x i32> [ undef, %has.min.vector.iterations ], [ %vec.sum9, %loop.vec32 ]
%74 = phi i64 [ 0, %has.min.vector.iterations ], [ %offset.next, %loop.vec32 ]
%75 = phi <4 x i32> [ zeroinitializer, %has.min.vector.iterations ], [ %vec.sum8, %loop.vec32 ]
%76 = phi <4 x i32> [ zeroinitializer, %has.min.vector.iterations ], [ %vec.sum9, %loop.vec32 ]
%77 = icmp eq i64 %24, 0
br i1 %77, label %loop.vec8.exit, label %loop.vec8.ph
; <label>:loop.vec8.ph: ; preds = %loop.vec32.exit
br label %loop.vec8
; <label>:loop.vec8: ; preds = %loop.vec8, %loop.vec8.ph
%80 = phi i64 [ %74, %loop.vec8.ph ], [ %92, %loop.vec8 ]
%81 = phi <4 x i32> [ %75, %loop.vec8.ph ], [ %90, %loop.vec8 ]
%82 = phi <4 x i32> [ %76, %loop.vec8.ph ], [ %91, %loop.vec8 ]
%83 = phi i64 [ %24, %loop.vec8.ph ], [ %93, %loop.vec8 ]
%84 = getelementptr i32, i32* %start_ptr, i64 %80
%85 = bitcast i32* %84 to <4 x i32>*
%86 = load <4 x i32>, <4 x i32>* %85, align 4, !tbaa !10
%87 = getelementptr i32, i32* %84, i64 4
%88 = bitcast i32* %87 to <4 x i32>*
%89 = load <4 x i32>, <4 x i32>* %88, align 4, !tbaa !10
%90 = add nsw <4 x i32> %86, %81
%91 = add nsw <4 x i32> %89, %82
%92 = add i64 %80, 8
%93 = add i64 %83, -1
%94 = icmp eq i64 %93, 0
br i1 %94, label %loop.vec8.exit, label %loop.vec8, !llvm.loop !15
; <label>:loop.vec8.exit: ; preds = %loop.vec8, %loop.vec32.exit
%96 = phi <4 x i32> [ %72, %loop.vec32.exit ], [ %90, %loop.vec8 ]
%97 = phi <4 x i32> [ %73, %loop.vec32.exit ], [ %91, %loop.vec8 ]
%98 = add <4 x i32> %97, %96
%99 = shufflevector <4 x i32> %98, <4 x i32> undef, <4 x i32> <i32 2, i32 3, i32 undef, i32 undef>
%100 = add <4 x i32> %98, %99
%101 = shufflevector <4 x i32> %100, <4 x i32> undef, <4 x i32> <i32 1, i32 undef, i32 undef, i32 undef>
%102 = add <4 x i32> %100, %101
%103 = extractelement <4 x i32> %102, i32 0
%104 = icmp eq i64 %size_log2_plus1, %size_log2_plus1_higher_bits
br i1 %104, label %exit, label %loop.scalar.ph
; <label>:exit: ; preds = %loop.scalar, %loop.vec8.exit, %1
%106 = phi i32 [ 0, %1 ], [ %103, %loop.vec8.exit ], [ %111, %loop.scalar ]
ret i32 %106
; <label>:loop.scalar: ; preds = %loop.scalar.ph, %loop.scalar
%108 = phi i32 [ %111, %loop.scalar ], [ %16, %loop.scalar.ph ]
%109 = phi i32* [ %112, %loop.scalar ], [ %17, %loop.scalar.ph ]
%110 = load i32, i32* %109, align 4, !tbaa !10
%111 = add nsw i32 %110, %108
%112 = getelementptr inbounds i32, i32* %109, i64 1
%113 = icmp eq i32* %112, %end_ptr
br i1 %113, label %exit, label %loop.scalar, !llvm.loop !17
}
پیگیری عملیات حسابی اندازه آرایه کار دشواری است و LLVM دستورالعمل‌های پر هزینه تقسیم مانند div یا mod را با lshr/and/or جایگزین می‌کند، زیرا عملوند راست توانی از 2 است. به جز مشکل اندازه، این کد باید کاملاً سرراست باشد.
آرایه‌ای با طول 129 به صورت loop.vec32 درمی‌آید و سپس به شکل loop.scalar تبدیل می‌شود و انشعاب loop.vec8 حذف می‌شود. در حالی که داشتن 130 عنصر باعث می‌شود که همه انشعاب‌ها شامل باشند. آرایه با اندازه کوچک 7 تنها از طریق loop.scalar پیاده‌سازی می‌شود.
چه زمانی برنامه‌نویس مؤثر است
کامپایلر تنها در حالت‌های میانگین و با شعار «چیزی را خراب نکن» وارد عمل می‌شود. شما به عنوان برنامه‌نویس باید با مسیرهای خاص کد و گردش داده‌های سطح بالایی که نیاز به تنظیم دارند، آشنایی داشته باشید.
بنچمارک کردن دشوار است
در اغلب موارد رفع یک تنگنا به اندازه یافتن سبب پیدایش آن دشوار نیست، چون یافتن سرنخی در این مورد، کاری واقعاً چالش‌برانگیز محسوب می‌شود. پروفایلرهای غیر نمونه‌بردار و توکار می‌توانند با کد اصلی مواجه شوند و مسائل عملکردی را پنهان کنند. پروفایلر نمونه‌برداری اطلاعات مهم را حذف می‌کند و می‌تواند به دلیل خطای دقت نتایج نادرستی ارائه کند.
در این خصوص هر چه اطلاعات بیشتری داشته باشید، بهتر است. درک ابزارها و محیط کاملاً ضروری است. پروفایلر چگونه کار می‌کند؟ کدام فلگ‌های کامپایلر یک بازرسی را تحت تأثیر قرار می‌دهند؟ کار دقیق آن‌ها چیست؟ چگونه می‌توان نویز سخت‌افزار و سیستم عامل را کاهش داد؟ درون یک syscall طولانی چه اتفاقاتی رخ می‌دهد؟ آیا این دستورالعمل‌ها برای این مدل CPU کارآمد هستند؟ آیا ما عملکرد حلقه خالی را اندازه‌گیری کرده‌ایم؟ درک کد اسمبلی کار دشواری نیست، یا شاید بهتر باشد بگوییم در طی زمان دشواری آن کاهش می‌یابد.
کنترل دسترسی RAM
بارگذارها و ذخیره‌سازهای حافظه همواره تنگنای برنامه محسوب می‌شوند؛ مگر این که محاسبات بسیار سنگینی روی CPU در حال اجرا باشد. این مسئله پیچیده است و جنبه‌های مختلفی دارد. CPU های مدرن این واقعیت را که حافظه کُند است از ما پنهان می‌کنند. با این حال دانستن طرز کار سخت‌افزار باعث می‌شود که بتوانیم بیشترین بهره‌برداری را از آن‌ها بکنیم.
دسترسی ترتیبی به RAM بسیار بهتر از دسترسی تصادفی است
دسترسی ترتیبی چنان مهم است که در برخی موارد الگوریتم‌های مرتب‌سازی native عملکردی به مراتب بالاتر از الگوریتم‌های کاملاً بهینه شده روی مجموعه داده‌های خاص ارائه می‌کنند. دستکاری ماتریس بسته به ترتیب دسترسی به سطرها/ستون‌ها می‌تواند عملکردی چندین برابر بهتر ارائه کند.
الگوریتم رمزپول CryptoNote تلاش می‌کند که با استفاده از حجم‌های بالایی از حافظه که نیاز به دسترسی تصادفی دارند در برابر ماینرهای سخت‌افزاری (ASIC ها) حفاظت ایجاد کند. دسترسی تصادفی به حافظه به روش‌های مختلفی اجرای موازی را دچار مشکل می‌کند.
همسوسازی داده‌ها
برخی پردازنده‌ها باعث شده‌اند ما باور کنیم که واقعاً چیزی به نام دسترسی ناهمسو وجود دارد. برخی اوقات ما آن قدر خوش‌شانس هستیم که هیچ افت عملکردی را شاهد نباشیم و این حالت در مواردی رخ می‌دهد که به مرزهای کَش سی‌پی‌یو نزدیک نشویم.
علی‌رغم این که عملیات خواندن و نوشتن روی CPU های مبتنی بر x86 معمولاً به صورت روانی اجرا می‌شود؛ اما atomic ها و دستورالعمل‌های SMID نیازمند همسوسازی صریح داده‌ها هستند. دسترسی ناهمسوی حافظه باعث ایجاد مشکل برای سخت‌افزار روی اغلب پردازنده‌های ARM می‌شود.
نوعی از کد سریال‌سازی/سریال‌زدایی منبع اصلی داده‌ها ناهمسو است.
کش‌های CPU
در این مورد نیز باید جنبه‌های مختلفی را بررسی کرد تا به طرح‌بندی بهینه‌ای از حافظه دست یافت.
قاعده سرانگشتی ساده از نقطه نظر عملکردی این است که هر آنچه معمولاً در کنار هم مورد دسترسی قرار می‌گیرد، باید در کنار هم نگهداری شود. برای مثال فرض کنید می‌خواهیم عناصری را بر مبنای bit mask شان بررسی کنیم. کد آن چنین است:
struct Foo {
int mask;
double value1;
double value2;
double value3;
// ...
};
void search(int needle, const std::vector<Foo>& haystack, std::ostream& out) {
for (auto f : haystack) {
if (f.mask & needle) {
out << f;
}
}
}
در این کد ما همه عناصر (بیش از 32 بایت) را از کش‌های CPU انتقال می‌دهیم، داده‌ها را از کش پاک کنیم و آن را در تکرار بعدی بیرون می‌اندازیم. اما می‌توانیم از طریق تغییر دادن مناطق حافظه، از کش استفاده بسیار بهتری بکنیم.
در ادامه اقدام به حذف int mask از struct به نام foo می‌کنیم و همه ماسک‌ها را به یک آرایه مجزا می‌بریم:
struct Foo {
double value1;
double value2;
double value3;
// ...
};
void search(int needle, const std::vector<int>& foomasks, const std::vector<foo>& foodata, std::ostream& out) {
for (int i = 0; i < foomasks.size(); ++i) {
if (foomasks[i] & needle) {
out << foodata[i];
}
}
}
به این ترتیب کش‌های CPU روی مقادیر بی‌استفاده value1, value2, … به هدر نمی‌روند و یک کامپایلر، متن حلقه یعنی foomasks[i] & needle را به صورت یک کد برداری شده تبدیل می‌کند که هر بار با چندین mask تطبیق دارد.
یک چنین بهینه‌سازی موجب بهبودهای بسیار قابل توجهی می‌شود. هر چند خوانایی کد تا حدود زیادی کاهش می‌یابد و برخی باگ‌های نامناسبی نیز ممکن است پدید آیند.
نوشتن حافظه، کش‌های CPU را دور می‌زند
اگر قصد دارید مقادیر بالایی از حافظه را برای استفاده‌های آتی بنویسید، می‌توانید این کار را از طریق دور زدن کش CPU انجام دهید. در این حالت، پردازنده صرفاً به مسائل مربوط به نوشتن می‌پردازد و به خواندن قبلی حافظه و این که چه چیزی اهمیت دارد نمی‌پردازد. از این رو کش‌ها با داده‌هایی که فعلاً به آن‌ها نیاز نداریم پر نمی‌شوند.
خانواده intrinsic های _mm_stream_siXXX بارهایی را با استفاده از حافظه غیر موقت ایجاد می‌کنند.
پیش‌واکشی (Prefetch) داده‌ها از حافظه
پردازنده‌ها در اغلب موارد این کار را انجام می‌دهند؛ اما با دانستن موارد کاربرد و نیازهای خاص خود می‌توانیم در این حالت دست بالا را داشته باشیم.
فقط در خاطر داشته باشید که دریافت داده‌ها فرایندی زمان‌بر است و از این رو پیش‌واکشی داده‌ها درست پیش از زمانی که نیاز دارید کاربردی ندارد. ما باید داده‌ها را زمانی پیش‌واکشی کنیم که قرار است کاری را تمام کنیم.
یک روش برای پیش‌واکشی داده‌ها استفاده از دستورالعمل‌های توکار کامپایلر مانند __builtin_prefetch روی GCC یا _mm_prefetch از هدر xmmintrin.h است.
روش دیگر آغاز به خواندن داده‌های مطلوب از نخ دیگر است. البته گفتن همه این‌ها ساده‌تر از انجام دادنشان است. پیش‌واکشی داده‌ها ممکن است باعث کوبیدگی کش (cache thrashing) شود و منجر به دریافت نتایج کاملاً معکوس حالت مورد انتظار شود.
پیش‌بینی انشعاب
موضوع‌های دسترسی حافظه و پیش‌بینی انشعاب‌ها کاملاً همبسته هستند. نکته‌ای که در این میان به کار می‌آید پیشنهاد احتمال بروز یک انشعاب به کامپایلر است. این کار از طریق ماکروهای مشهور likely/unlikely (در GCC به صورت __builtin_expect است) و یا بهتر از آن بهینه‌سازی به کمک پروفایل است.
می‌توان برنامه‌ای را تحت بار کاری معمول اجرا کرد و یک پروفایل از این اجرا به دست آورد. این پروفایل می‌تواند به عنوان یک ورودی اضافی برای یک بهینه‌ساز مورد استفاده قرار گیرد. این داده‌ها می‌توانند مواردی شامل تعداد انشعاب، فراوانی فراخوانی‌های تابع و دیگر اطلاعات به دست بدهند که به کامپایلر امکان می‌دهد تا تصمیم‌های دقیقی بسته به بار کاری ارائه شده بگیرد.
با این وجود فرایند فوق بهینه‌سازی چندان در خور توجهی ایجاد نمی‌کند. چنین بهینه‌سازی‌هایی باید به عنوان آخرین گام برای دستیابی به ارتقای کلی هر چند ناچیز در نظر گرفته شوند.
بررسی شمارنده‌های عملکرد CPU
در اغلب موارد یک تنگنای واحد وجود ندارد و از این رو حتی محلی که باید کار خود را آغاز کنیم نامشخص است. در چنین مواردی شمارنده‌های عملکرد CPU به صورت سخت‌افزاری اطلاعات بسیار مهمی ارائه می‌کنند که شامل تعداد انشعاب‌های با پیش‌بینی نادرست، تعداد فقدان کش‌ها برای کد و داده‌ها، نوشتن حافظه و موارد دیگر می‌شود. بنابراین به جای کاهش تأخیر تابع‌های ناشناس می‌توانیم به بهینه‌سازی این موارد بپردازیم.
ابزار perf و OProfile در لینوکس امکان دسترسی به شمارنده‌های عملکرد سخت‌افزار را می‌دهند و Xcode این کار را روی Mac انجام می‌دهد. ابزارهای زیادی دیگری نیز از سوی سازندگان CPU ها ارائه شده است، برای مثال Intel® Performance Counter Monitor (+).
مقاصد خود را برای کامپایلر روشن کنید
در برخی موارد بهینه‌سازی‌های دستی مانند حذف حلقه‌ها یا جایگزینی انشعاب‌ها با عملیات حسابی اشاره‌گر باعث بهبود شایان توجهی می‌شود؛ اما ممکن است باعث کاهش زیادی در عملکرد کلی شود.
همواره یک نقطه تعادلی بین خوانایی کد و عملکرد آن وجود دارد. توجه به خوانایی کد برای انسان نیز مهم است. شما نباید کامپایلر و همکاران برنامه‌نویس خود را با ترفندهایی که باعث کاهش خوانایی کد می‌شوند شگفت‌زده کنید، چون همه این ترفندهای پیچیده در یک نقطه زمانی منسوخ خواهند شد. رفتار سخت‌افزارها تغییر خواهد یافت؛ اما یک codebase می‌تواند همچنان تا مدت‌ها زنده بماند.
برای نمونه مثال sum ما را که قبلاً مطرح کردیم در نظر بگیرید و آن را با یک مقدار ثابت فراخوانی کنید:
int sum(const std::vector<int> & array) {
int result = 0;
for (auto i: array) {
result += i;
}
return result;
int main() {
const std::vector<int> elems{1,2,3,4};
return sum(elems);
}
LLVM IR -O2:
define i32 @main() #1 personality i8* bitcast ... ret i32 10 }
کل برنامه در زمان کامپایل اجرا می‌شود. همه کد زیر حذف شده است و تنها چیزی که مانده یک return 10 است:
std::__XZZF_you_re_sick_of_this_cr*p_::__iterator__Stable_v1_XYZ_operator
تخصیص هیپ برداری از طریق فراخوانی‌های std::allocator نیز حذف شده است.
با این حال این مثال عادلانه نیست چون شکل SSA انتشار ثابت‌ها را بسیار تسهیل می‌کند؛ اما در هر حال این مثال کاملاً گویا است.
ارسال آرگومان‌ها با ارجاع (اشاره‌گر) ممکن است هزینه‌های پنهانی داشته باشد
int foo(int a, int b) {
int c;
bar(a, b, c);
return a + b + c;
}
void bar(int a, int b, int& c) {
c = a * b;
}
کد فوق می‌تواند بهینه‌ساز را با دشواری مواجه کند. در این حالت تصمیم‌گیری در مورد inline کردن foo به دسترسی حافظه (وابستگی داده) و به یک تابع bar (وابستگی کد) بستگی دارد.
const
متأسفانه بهینه‌سازها چیزی مانند اشاره‌گر const ندارند. موقعیتی مانند کد زیر را تصور کنید:
template <typename To, typename From>
inline To union_cast(From x) {
union {
From from;
To to;
} converter;
converter.from = x;
return converter.to;
}
یا اشاره‌گری به cast اشاره‌گر، یا ترفندهای آرایه‌ای، یا سرریز عدد صحیح، یا سرریز بافر. لازم به ذکر نیست که const_cast در این جا دارای امکان‌های بی‌شماری برای ایجاد اسم مستعار برای مناطق یکسانی از حافظه در C و ++C دارد و این کار چه آگاهانه و چه تصادفی ممکن است رخ دهد.
رویکرد دوم، موازی‌سازی (parallelism) است. اگر هیچ داده مشترکی وجود نداشته باشد، هیچ چیز نیست که روی آن قفل کنیم. CPU-های چندهسته‌ای مدرن قابلیت بالایی برای اجرای موازی دارند و نیازی به صرف چرخه‌های گران‌بها روی قفل‌ها وجود ندارد. در اغلب موارد بازگشت دادن آرگومان‌ها به جای ارسال آن‌ها با ارجاع، باعث می‌شود که کامپایلر یک گردش داده را ببیند و کد بسیار بهینه‌تری را تولید کند.
از اعضای struct برای ذخیره‌سازی نتایج میانی استفاده نکنید
این هم یک روش دیگر است که کارها را برای بهینه‌ساز ها دشوار می‌سازد:
struct Foo {
double a;
double b;
double c;
double compute();
};
double Foo::compute() {
a = heavy_calc_a();
b = heavy_calc_b();
c = heavy_calc_c();
return a+b+c;
}
بهینه‌ساز در چنین مواردی باید در مورد اشاره‌گر this و این که آیا عوارض جانبی دارد یا نه تأمل کند. برنامه‌نویس‌ها نیز برای خواندن چنین کدهایی با دشواری مواجه هستند.
خواندن تابع‌های محض هم برای انسان و هم کامپایلر بسیار آسان‌تر است.
استانداردهای مدرن ++C/C را مورد استفاده قرار دهید
++C نسخه 11 و استانداردهای جدیدتر، بهینه‌سازی مقادیر بازگشتی (RVO) را تضمین می‌کنند. هم C و هم ++C حالت‌های زیادی دارند که رفتار برنامه به پیاده‌سازی درونی کامپایلر وابسته است. استانداردهای جدیدتر تلاش می‌کنند این گوشه‌های تاریک را حذف کند و آسیب‌های احتمالی ناشی از UB را به حداقل برسانند.
ضمناً کامپایلرهای جدید ابزارهای تکمیلی مانند linter-ها، checker-ها، formatter-ها و غیره را ارائه می‌کنند.
در کار کامپایلر دخالت نکنید
تلاش کنید در حلقه باز شده دستی زیر یک خطا را بیابید:
static int rr_cmp(uchar *a, uchar *b)
{
if (a[0] != b[0])
return (int) a[0] - (int) b[0];
if (a[1] != b[1])
return (int) a[1] - (int) b[1];
if (a[2] != b[2])
return (int) a[2] - (int) b[2];
if (a[3] != b[3])
return (int) a[3] - (int) b[3];
if (a[4] != b[4])
return (int) a[4] - (int) b[4];
if (a[5] != b[5])
return (int) a[1] - (int) b[5];
if (a[6] != b[6])
return (int) a[6] - (int) b[6];
return (int) a[7] - (int) b[7];
}
در خط 14 کد فوق یک [a[1 در زمان کپی/چسباندن قرار گرفته است که باید [a[5 می‌بود. در این مورد باید توجه داشته باشید که باز کردن حلقه کاری است که کامپایلرهای C و ++C به خوبی انجام می‌دهند و نیازی به دخالت برنامه‌نویس وجود ندارد.
استثناها روی پردازنده‌های مدرن، سرباری نزدیک به صفر دارند
نکته مهمی که باید توجه داشت این است که «سربار صفر» به معنی هزینه صفر نیست. البته استفاده از هر چیزی همواره بهایی دارد. با این حال مفهوم سربار صفر در ++C همواره به این معنی است که
- الف: «شما برای آن چه استفاده نمی‌کنید، بهایی نمی‌پردازید»
- و ب: «وقتی از چیزی استفاده می‌کنید، نمی‌توانید آن را به صورت دستی به روشی بهینه‌تر بنویسید»
البته سربار نزدیک به صفر تنها در مسیرهای سرراست صدق می‌کند. زمانی که استثنایی رخ می‌دهد، پردازنده باید frame finalizer ها را اجرا کند و روی پشته حرکت کند که نیازمند از دست دادن چند کش، TLB shuffling و غیره است.
ما در هر حال زمانی که استثنایی رخ می‌دهد نمی‌توانیم تطبیق الگو را شبیه‌سازی کنیم و وجود استثنا موجب می‌شود که وظیفه بهینه‌ساز کندتر شود.
هر چه قدر می‌توانید از sanitizer-ها و تحلیل‌گرهای استاتیک استفاده کنید
این یک نکته مربوط به عملکرد نیست؛ اما چون تا این جا این مقاله را مطالعه کرده‌اید باید اشاره کنیم مهم‌ترین کاری که باید به عنوان برنامه‌نویس انجام دهید، این است که تا می‌توانید از تحلیل‌گرهای کد استاتیک استفاده کنید.
ابزارهای مدرن بسیار مفید هستند. حتی یک هشدار مثبت نادرست (false-positive) در اغلب موارد به کدی اشاره می‌کند که به طرز غیر ضروری پیچیده است. امروزه هر کامپایلر، خود یک تحلیل‌گر عالی محسوب می‌شود. همه آن چیزی که نیاز دارید این است که آن‌ها را به wall-- تبدیل کنید و تنها هزینه آن این است که کد کمی تمیزتر می‌شود و یک بازی برد-برد محسوب می‌شود.
کامپایلر نیز یک برنامه است
کامپایلر خود یک برنامه است و طراحی یک کامپایلر بهینه‌سازی کاری چنان دشوار است که نمی‌توان گفت یک کامپایلر بهینه‌سازی کاملاً عاری از خطا است.
در واقع یک کامپایلر بهینه‌سازی نیز قطعاً باگ‌هایی دارد برای نمونه ممکن است بخشی از کد مرتبط با امنیت را دور بیندازد چون استفاده مشخصی برای آن نیافته است. حتی چنین کامپایلری ممکن است خودش آسیب‌پذیری‌هایی را در کد ایجاد کند.
شاید یک روز هوش مصنوعی قدرتمندی پیدا شود که باگ‌های ما را رفع کند؛ اما تا آن روز ما باید کدهای خود را در حد احمقانه‌ای ساده نگه‌داریم تا احتمال ایجاد باگ در کامپایلرها را پایین نگه داریم.
سخن پایانی
در ادامه مفاهیمی که در این مقاله ارائه شده‌اند را جمع‌بندی کرده‌ایم:
- پیچیدگی سیستم‌های نرم‌افزاری رو به افزایش است.
- سخت‌افزارها در حال پیچیده‌تر و متنوع‌تر شدن هستند.
- CPU سریع و پیچیده است در حالی که DRAM کند و ارزان است.
- ما باید از بهینه‌سازی‌ها در پایین‌ترین سطح CPU برای یک کامپایلر استفاده کنیم و روی گردش داده برنامه و تولید کد خوانا از دید انسان متمرکز شویم.
- درک عملکرد به معنی درک بهینه‌سازی کامپایلر نیز هست.
- کامپایلرهای بهینه‌سازی مدرن بسیار پیشرفت کرده‌اند؛ اما هنوز از حالت ایده‌آل فاصله زیادی دارند.
- بهینه‌سازی طرح‌بندی حافظه و الگوهای دسترسی کاملاً ارزشش را دارد.
- در برخی موارد بهینه‌سازی‌های محلی می‌توانند نتایج شگفت‌انگیزی در بنچمارک های خُرد داشته باشند؛ اما باعث کاهش عملکرد کلی اپلیکیشن شوند.
اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزش‌های برنامه‌نویسی
- آموزش طراحی کامپایلر
- مجموعه آموزش‌های دروس مهندسی کامپیوتر
- آموزش طراحی کامپایلر — مجموعه مقالات جامع وبلاگ فرادرس
- آموزش طراحی کامپایل (مرور و حل تست های کنکور کارشناسی ارشد)
- آموزش تجزیه انتقال (کاهش) در طراحی کامپایلر
- تولید کد میانی (Intermediate Code) در طراحی کامپایلر – راهنمای جامع
==
