کامپایلر بهینهساز
یک کامپایلر بهینهساز، کامپایلری است که برای تولید کدی طراحی شده است که از جنبههایی مانند به حداقل رساندن زمان اجرای برنامه، استفاده از حافظه، اندازه ذخیرهسازی و مصرف انرژی بهینه شده باشد.[۱]
کامپایلرها برای تولید کد بهینه از مجموعهای از الگوریتمهای تبدیل بهینهسازی استفاده میکنند. این الگوریتمها کد برنامه را تغییر میدهند تا در نهایت خروجیای تولید کنند که از نظر معنایی با کد اصلی یکسان است، اما منابع کمتری مصرف میکند یا سریعتر اجرا میشود.
با این وجود، بهینهسازی کد همواره با چالشهایی روبرو است. برخی از مسائل بهینهسازی ذاتاً پیچیده هستند و حتی ممکن است NP-کامل یا غیرقابل حل باشند. علاوه بر این، محدودیتهای عملی نیز بر سر راه بهینهسازی وجود دارد. به عنوان مثال، میزان حافظه موجود و زمان قابل قبول برای کامپایل، توسط برنامهنویس تعیین میشود و میتواند مانع از اعمال بهینهسازیهای پیچیدهتر شود.
بهینهسازی فرآیندی پردازندهمحور و حافظهبر است. در گذشته، محدودیت حافظه رایانه نیز مانع بزرگی در مسیر بهینهسازیهای پیشرفته بود. به دلیل این محدودیتها، بهینهسازیها به ندرت میتوانند خروجی کاملاً بهینه تولید کنند. در واقع، گاهی اوقات یک "بهینهسازی" ممکن است باعث کاهش عملکرد در برخی جنبهها شود. به همین دلیل، بهینهسازیها بیشتر به عنوان روشهای اکتشافی برای بهبود استفاده از منابع در برنامههای معمول در نظر گرفته میشوند. به عبارت دیگر، هدف بهینهسازی یافتن بهترین راه حل ممکن نیست، بلکه بهبود نسبی در استفاده از منابع در برنامههای رایج است.
انواع بهینه سازی
ویرایشتکنیک های مورد استفاده در بهینه سازی می تواند در زمینه های مختلف به کار برود که می تواند هر چیزی را از یک جمله واحد به کل برنامه تحت تأثیر قرار دهد. به طور کلی ، تکنیکهای محلی مورد استفاده در مقایسه با روشهای جهانی آسانتر هستند اما منجر به دستاوردهای کوچکتر می شوند. برخی از نمونه های دامنه شامل موارد زیر است:
معمولاً پس از تولید کد دستگاه ، دیر هنگام در مراحل تلفیقی انجام می شود. این شکل از بهینه سازی چند دستورالعمل مجاور را بررسی می کند (مانند "نگاه کردن از طریق یک گیره" در کد) تا ببیند آیا می توان آنها را با یک دستورالعمل واحد یا یک دستورالعمل کوتاه تر جایگزین کرد. به عنوان مثال ، ضرب یک مقدار توسط 2 ممکن است با تغییر دادن مقدار چپ یا اضافه کردن مقدار به خود ، کارایی بیشتری داشته باشد (این مثال نیز نمونه ای از کاهش قدرت است ).
بهینه سازی های محلی
ویرایشاینها فقط اطلاعات محلی را به یک بخش اصلی در نظر می گیرند .[۲] از آنجا که بلوک های اساسی جریان کنترلی ندارند ، این بهینه سازی ها نیاز به تجزیه و تحلیل بسیار کمی دارند (صرفه جویی در زمان و کاهش نیازهای ذخیره سازی) ، اما این بدان معنی است که هیچ اطلاعاتی در پرش ها حفظ نمیشود.
بهینه سازی های جهانی
ویرایشبه این روشها "روشهای درونگرا" نیز گفته می شود و بر روی توابع کامل عمل می کند.[۲] این به آنها اطلاعات بیشتری می دهد تا با آنها کار کنند اما اغلب محاسبات گران را ضروری می کند. هنگامی که تماسهای عملکردی رخ می دهد یا به متغیرهای جهانی دسترسی پیدا می کند ، فرض های بدتری را باید انجام داد (زیرا اطلاعات کمی در مورد آنها در دسترس است).
اینها در مورد جمله هایی که یک حلقه را تشکیل می دهند ، مانند حلقه for (مانند حرکت کد حلقه بدون تغییر ) عمل می کنند. بهینه سازی حلقه می تواند تأثیر بسزایی داشته باشد زیرا بسیاری از برنامه ها درصد زیادی از زمان خود را در حلقه ها می گذرانند.
اینها همه کد منبع برنامه را تجزیه و تحلیل می کند. مقدار بیشتری از اطلاعات استخراج شده بدان معنی است که بهینه سازی ها می توانند در مقایسه با زمانی که فقط به اطلاعات محلی دسترسی داشته باشند (به عنوان مثال ، در یک عملکرد واحد) موثرتر باشند. این نوع بهینه سازی همچنین می تواند تکنیک های جدیدی را انجام دهد. برای عملکرد به عنوان مثال inlining ، که در آن یک تماس به تابع توسط یک کپی از بدن تابع جایگزین شده است.
بهینه سازی کد دستگاه و بهینه ساز Object code
ویرایشبرخی از تکنیک هایی که می توانند در محدوده محدودتری اعمال شوند ، مانند فشرده سازی کلان (که با از بین بردن توالی های متداول از دستورالعمل ها موجب صرفه جویی در فضا می شود) وقتی کل تصویر وظیفه اجرایی برای تجزیه و تحلیل در دسترس باشد ، مؤثرتر هستند.[۳]
عوامل مؤثر بر بهینهسازی
ویرایشخود دستگاه
ویرایشبسیاری از گزینه هایی که در مورد آنها بهینه سازی ها می توانند و باید انجام شوند به ویژگی های دستگاه هدف بستگی دارد. پارامتر کردن بعضی از این عوامل وابسته به ماشین گاهی اوقات امکان پذیر است ، به گونه ای که می توان تنها با تغییر پارامترهای توصیف دستگاه ، از یک قطعه کد کامپایلر برای بهینه سازی ماشینهای مختلف استفاده کرد. GCC کامپایلری است که نمونه این رویکرد را نشان می دهد.
معماری CPU هدف
ویرایشتعداد ثبت های CPU : تا حدودی هرچه تعداد ثبت ها بیشتر باشد ، بهینه سازی کارایی آسان تر است. متغیرهای محلی را می توان در رجیسترها اختصاص داد و نه روی پشته . نتایج موقت / واسط می توانند بدون ثبت و خواندن از حافظه در ثبت ها باقی بمانند.
- RISC vs CISC : مجموعه های دستورالعمل CISC معمولاً دارای طول دستورالعمل متغیر هستند ، معمولاً تعداد بیشتری دستورالعمل ممکن را دارند که می توانند استفاده شوند و هر دستورالعمل می تواند زمانهای مختلفی را ببرد. مجموعه های دستورالعمل RISC سعی در محدود کردن تغییرپذیری در هر یک از این موارد دارند: مجموعه دستورالعمل ها معمولاً دارای طول ثابت هستند ، با استثنائات اندک ، معمولاً تعداد کمتری از ثبت ها و عملیات حافظه ، و میزان انتشار دستورالعمل ها (تعداد دستورالعمل های انجام شده در هر دوره زمانی ، کمتر) وجود دارد. معمولاً یک عدد صحیح از چرخه ساعت) معمولاً در مواردی که تأخیر حافظه عاملی نباشد ، ثابت است. ممکن است روش های مختلفی برای انجام یک کار خاص وجود داشته باشد ، که CISC معمولاً گزینه های بیشتری نسبت به RISC ارائه می دهد. کامپایلرها باید در بین دستورالعمل های مختلف هزینه های نسبی را بدانند و بهترین دنباله دستورالعمل را انتخاب کنند (به انتخاب دستورالعمل مراجعه کنید).
- خطوط لوله : در واقع یک خط لوله CPU است که به یک خط مونتاژ شکسته می شود. این کار با استفاده از بخش هایی از CPU برای دستورالعمل های مختلف با شکستن اجرای دستورالعمل ها در مراحل مختلف امکان پذیر است: رمزگشایی دستورالعمل ، رمزگشایی آدرس ، انتقال حافظه ، ثبت نام fetch ، محاسبه ، ثبت فروشگاه و غیره. یک دستورالعمل می تواند در مرحله ثبت نام باشد ، در حالی که دیگری می تواند در مرحله ثبت نام باشد. درگیری خط لوله زمانی اتفاق می افتد که یک دستورالعمل در یک مرحله از خط لوله به نتیجه یک دستورالعمل دیگر در پیش روی آن در خط لوله بستگی دارد اما هنوز کامل نشده است. درگیری های خط لوله می تواند به غرفه های خط لوله منجر شود: جایی که CPU چرخه ها را در انتظار حل و فصل یک درگیری می کند.
معماری دستگاه
ویرایش- نرخ انتقال حافظه پنهان / حافظه: اینها نشانگر جریمه برای خطاهای حافظه پنهان است. این مورد عمدتاً در کاربردهای تخصصی مورد استفاده قرار می گیرد.
استفاده در نظر گرفته شده از کد تولید شده
ویرایشدر حین نوشتن برنامه ، یک برنامه نویس اغلب مجدداً کامپایل می شود و آزمایش می کند ، بنابراین تدوین باید سریع باشد. این یکی از دلایلی است که اکثر بهینه سازی ها در مرحله آزمایش / اشکال زدایی از عمد اجتناب می کنند. همچنین ، کد برنامه معمولاً با استفاده از یک اشکال زدایی سمبولیک "قدم به قدم" می گذارد (به انیمیشن برنامه مراجعه کنید) و بهینه سازی دگرگونی ها ، به ویژه آنهایی که کد را دوباره ترتیب می دهند ، می توانند ارتباط کد خروجی را با شماره خط در کد منبع اصلی دشوار کنند. این می تواند هر دو ابزار اشکال زدایی و برنامه نویسان را که از آنها استفاده می کنند اشتباه گرفته شود.
استفاده عمومی
ویرایشانتظار می رود نرمافزار Prepackaged در ماشین آلات و CPU های مختلفی اجرا شود که ممکن است یک مجموعه دستورالعمل یکسان را به اشتراک بگذارند ، اما دارای ویژگی های مختلف زمان بندی ، حافظه پنهان یا حافظه هستند. بنابراین ، ممکن است کد به هیچ CPU خاصی تنظیم نشده باشد ، یا ممکن است تنظیم شود تا در محبوب ترین CPU بهترین کار را داشته باشد و در عین حال هنوز هم در سایر پردازنده ها به خوبی قابل قبول کار کند.
استفاده خاص
ویرایشاگر این نرمافزار برای استفاده در یک یا چند ماشین بسیار مشابه و با مشخصات شناخته شده کامپایل شده باشد ، کامپایلر می تواند کد تولید شده را به شدت به آن دستگاه های خاص تنظیم کند (در صورت وجود چنین گزینه هایی). موارد ویژه مهم شامل کدی است که برای پردازنده های موازی و بردار طراحی شده است ، که برای آن کامپایلرهای موازی سازی ویژه ای استفاده شده است.
اینها یک مورد معمول از کاربردهای خاص است. نرمافزار جاسازی شده را می توان به طور دقیق با یک CPU و اندازه حافظه دقیق تنظیم کرد. همچنین ممکن است هزینه سیستم یا قابلیت اطمینان نسبت به سرعت کد اهمیت بیشتری داشته باشد. بنابراین ، برای مثال ، کامپایلرهای نرمافزار تعبیه شده معمولاً گزینه هایی را ارائه می دهند که اندازه کد را با هزینه سرعت کاهش می دهد ، زیرا حافظه اصلی ترین هزینه یک کامپیوتر تعبیه شده است. ممکن است زمان کد به جای سریعترین سرعت ممکن باشد قابل پیش بینی باشد ، بنابراین ممکن است حافظه پنهان کد به همراه بهینه سازی کامپایلر که به آن نیاز دارد غیرفعال شود.
مضامین متداول
ویرایشتا حدود زیادی ، تکنیک های بهینه سازی کامپایلر دارای مضامین زیر هستند که گاهی اوقات با هم در تضاد اند.
مورد مشترک را بهینه کنید
ویرایشمورد مشترک ممکن است خصوصیات منحصر به فردی داشته باشد که اجازه می دهد یک مسیر سریع و به جای یک مسیر کند انجام شود. اگر بیشتر اوقات مسیر سریع طی شود ، نتیجه عملکرد کلی بهتر است.
از حشو اجتناب کنید
ویرایشبه جای محاسبه مجدد نتایج ، از نتایج محاسبه شده دوباره استفاده کرده و آنها را برای استفاده های بعدی ذخیره کنید.
کمتر کد نویسی کنید
ویرایشمحاسبات غیرضروری و مقادیر میانی را حذف کنید. کار کمتر برای پردازنده ، حافظه پنهان و حافظه معمولاً منجر به اجرای سریعتر می شود. متناوباً ، در سیستم های تعبیه شده ، کد کمتر محصول کم هزینه تری را به همراه دارد.
با استفاده از کد خط مستقیم که به آن کد بدون شاخه نیز گفته می شود ، پرش های کمتری انجام می شود
ویرایشکد با پیچیدگی کمتر. پرش ها (شاخه های شرطی یا بدون قید و شرط) با واکشی اولیه دستورالعمل ها تداخل دارند و به این ترتیب سرعت کد را کاهش می دهند. استفاده از درون خطی یا باز کردن حلقه می تواند انشعاب را کاهش دهد ، در ازای افزایش اندازه فایل باینری با طول کد تکرار شده. این کار تمایل دارد چندین بلوک اساسی را در یکی ادغام کند.
موقعیت
ویرایشکد و داده هایی که از به طور نزدیک به هم مورد دسترسی قرار می گیرند باید در حافظه نزدیک یکدیگر قرار بگیرند تا ارجاع مکان محلی را افزایش دهند.
از سلسله مراتب حافظه بهره برداری کنید
ویرایشدسترسی به حافظه برای هر سطح از سلسله مراتب حافظه به طور فزاینده ای گران تر است ، بنابراین قبل از رفتن به دیسک ، بیشترین موارد مورد استفاده را ابتدا در ثبات ها ، سپس حافظه پنهان ، سپس حافظه اصلی قرار دهید.
موازی سازی کنید
ویرایشترتیب عملیات را تغییر دهید تا اجازه دهید چندین محاسبه به صورت موازی ، یا در سطح دستورالعمل ، حافظه یا سطح نخ اتفاق بیفتد.
اطلاعات دقیق تر بهتر است
ویرایشهرچه اطلاعات کامپایلر دقیق تر باشد ، بهتر می تواند از تکنیک های بهینه سازی یا همه اینها استفاده کند.
ماتریس های زمان اجرا می تواند کمک کند
ویرایشاز اطلاعات جمع آوری شده در حین اجرای آزمون می توان در بهینه سازی با راهنمای مشخصات استفاده کرد. اطلاعات جمع آوری شده در زمان اجرا ، در حالت ایده آل با حداقل هزینه سربار ، می تواند توسط یک کامپایلر JIT برای بهبود پویا بهینه سازی استفاده شود.
کاهش قدرت
ویرایشکارهای پیچیده یا دشوار یا گران قیمت را با کارهای ساده تر جایگزین کنید. به عنوان مثال ، جایگزینی تقسیم بر یک ثابت با ضرب با معکوس آن ، یا استفاده از تجزیه و تحلیل متغیر القایی برای جایگزینی ضرب با یک شاخص حلقه با جمع.
تکنیک های خاص
ویرایشبهینه سازی های حلقه
ویرایشمقاله اصلی: بهینه سازی حلقه
برخی از تکنیک های بهینه سازی که اساساً برای کار با حلقه ها طراحی شده اند ، عبارتند از:
تجزیه و تحلیل متغیر القایی
ویرایشتقریباً ، اگر یک متغیر در یک حلقه یک تابع خطی ساده از متغیر شاخص باشد ، مانند j: = 4 * i + 1 ، هر زمان که متغیر حلقه تغییر می کند ، می تواند به طور مناسب به روز رسانی شود. این یک کاهش قدرت است ، و همچنین ممکن است اجازه دهد که تعاریف متغیر شاخص به کد مرده تبدیل شوند. این اطلاعات همچنین برای حذف بر اساس بررسی مرزها و تجزیه و تحلیل وابستگی ، از جمله موارد دیگر ، مفید است.
شکاف حلقه یا توزیع حلقه
ویرایششکاف حلقه تلاش می کند تا یک حلقه را به چندین حلقه در یک محدوده شاخص تبدیل کند ، اما هر یک فقط بخشی از بدن حلقه را می گیرد.
همجوشی حلقه یا حلقه ترکیبی یا حلقه رامینگ یا گرفتگی حلقه
روش دیگری که سعی در کاهش سربار حلقه دارد. هنگامی که دو حلقه مجاور بدون توجه به اینکه این تعداد در زمان کامپایل مشخص است ، تعداد دفعات تکرار یکسان را انجام می دهد ، تا زمانی که هیچ اشاره ای به داده های یکدیگر نداشته باشند ، می توان اجسام آنها را ترکیب کرد.
وارونگی حلقه
ویرایشاین تکنیک یک حلقه while استاندارد را به حلقه do / while تبدیل می کند (همچنین به عنوان تکرار / تا شناخته می شود) که در یک شرط مشروط قرار گرفته و برای مواردی که حلقه اجرا می شود، تعداد پرش ها را دو تا کاهش می دهد. انجام این کار بررسی وضعیت را کپی می کند (اندازه کد را افزایش می دهد) ، اما کارآمدتر است زیرا پرش ها معمولاً باعث توقف خط لوله می شوند. بعلاوه ، اگر شرط اولیه در زمان کامپایل شناخته شده باشد و بدون عوارض باشد ، می توان از نگهبان if صرف نظر کرد.
تبادل حلقه
ویرایشاین بهینه سازی ها حلقه های داخلی را با حلقه های خارجی عوض می کنند. وقتی متغیرهای حلقه به یک آرایه تبدیل می شوند ، بسته به طرح آرایه ، چنین تحولی می تواند محل مرجع را بهبود بخشد.
حرکت کد حلقه ثابت
ویرایشاگر در هر بار تکرار حلقه یک مقدار در داخل حلقه محاسبه شود و مقدار آن برای هر تکرار یکسان باشد ، می تواند کارایی را برای بالا بردن آن در خارج از حلقه و محاسبه مقدار آن فقط یک بار قبل از شروع حلقه افزایش دهد. این امر به ویژه در عبارات محاسبه آدرس که توسط حلقه ها روی آرایه ها ایجاد می شود ، بسیار مهم است. برای پیاده سازی صحیح ، این روش باید با وارونگی حلقه مورد استفاده قرار گیرد ، زیرا بالا بردن همه کدها در خارج از حلقه ایمن نیست.
بهینه سازی لانه حلقه
ویرایشبرخی از الگوریتم های فراگیر مانند ضرب ماتریس رفتار حافظه پنهان بسیار ضعیف و دسترسی بیش از حد حافظه دارند.بهینه سازی آشیانه حلقه با انجام عملیات بر روی بلوک های کوچک و با استفاده از تبادل حلقه تعداد بازدید از حافظه نهان را افزایش می دهد.
- ↑ «Optimizations in C++ Compilers - ACM Queue». queue.acm.org. دریافتشده در ۲۰۲۴-۱۱-۱۰.
- ↑ ۲٫۰ ۲٫۱ Cooper, Keith D.; Torczon, Linda (2003) [2002-01-01]. Engineering a Compiler. Morgan Kaufmann. pp. 404, 407. ISBN 978-1-55860-698-2.
- ↑ Clinton F. Goss (August 2013) [First published June 1986]. "Machine Code Optimization - Improving Executable Object Code" (PDF) (Ph.D. dissertation). Computer Science Department Technical Report #246. Courant Institute, New York University. arXiv:1308.4815. Bibcode:2013arXiv1308.4815G. Retrieved 22 Aug 2013. Lay summary.
{{cite journal}}
: Cite journal requires|journal=
(help); Cite uses deprecated parameter|lay-url=
(help)