Оптимизация на асемблерните езикови програми. Част 2

Рей Дънкан.

В предишната част обсъдихме някои общи проблеми с оптимизацията и след това говорихме за компромисите, които трябва да се направят при оптимизиране на производителността и размера на програмата. В това и следващото ще разгледаме по-подробно някои от класическите примери за „локална“ оптимизация. Но е важно да запомните, че тези конкретни техники трябва да се използват само при определени обстоятелства - а именно, след като сте се уверили, че сте приложили правилните алгоритми и структури от данни, че сте дебъгвали програмата изцяло и инструментите за профилиране имат ви показа самите фрагменти от програмата, които ограничават производителността.

Отхвърляне на универсалността

Операциите на умножение и деление изискват много усилия от почти всеки процесор, тъй като те трябва да бъдат внедрени (в хардуер или софтуер) чрез съответно смени и добавяния или отмествания и изваждания. Старите 4- и 8-битови процесори не съдържаха машинни инструкции за умножение или деление, така че тези операции трябваше да бъдат изпълнени с помощта на дълги подпрограми, където изрично бяха извършени премествания и добавяния или изваждания. Първите 16-битови микропроцесори, като 8086 и 68000, позволяват умножение и деление в хардуера, но процедурите са били изключително бавни: на 8086, например, е необходимо около 150, за да се раздели 32-битово число на 16 -битово число. кърлежи.

Нека първо разгледаме най-простата процедура за оптимизиране за умножение. За да умножите число по степен две, просто трябва да го преместите наляво с необходимия брой двоични (битови) позиции. Например, така изглежда някаква обща, но бавна последователност от команди при умножаване на стойността на променливата myvar по 8:

На процесори 8086/88 тази програма може да бъде преобразувана в по-бърза последователност от смени:

или дори това: shl myvar, 1 shl myvar, 1 shl myvar, 1

Ако се изисква смяна на една или две позиции, обикновено е най-лесно да се извършат тези операции върху операндите в паметта. Ако се нуждаете от смяна с много позиции, тогава увеличената скорост на работа върху операндите на регистрите напълно компенсира допълнителна команда за зареждане на число в регистър и извличането му от там след смяната.

Но не бързайте - дори тази проста оптимизация не е толкова тривиална, колкото звучи! Опашката от инструкции в 80x86 процесори, конкретният модел процесор, използван във вашия компютър, и наличието или липсата на кеш памет могат да изиграят най-странните шеги. В някои случаи и на някои модели процесори понякога е възможно да се използва тази команда в опцията "смяна на броя позиции, посочени в CX":

А в процесора 80186 и по-късно има опция "изместване по броя на позициите, посочени от непосредствения операнд", което е още по-удобно:

Ако трябва да умножите по степен от две числа, по-дълги от 16 бита, използвайте флага за носене, за да организирате операции върху два или повече регистри. Например, за да умножите 32-битово число в DX: AX по 4, можете да напишете:

Чрез креативно комбиниране на смени и умножения можете да организирате бързо умножение с почти всяка конкретна стойност. Следният фрагмент умножава стойността в AX регистъра по 10:

Използването на отказ от гъвкавост за разделяне е малко по-ограничено. Разделянето на степента на две е, разбира се, много просто. Просто премествате номера надясно, като следите избора на първоначалната команда за смяна за желания тип разделение (подписан или неподписан). Например, за да извършите неподписано деление на 4 върху съдържанието на AX регистъра, можете да напишете:

а за процесори 80186 и по-нови версии можете вместо това да използвате командата

Подписаното разделяне на 4 би осигурило например последователността

или за процесор 80186 и по-нови

Единствената разлика между логическата (неподписана) команда за превключване SHR и аритметичната (подписана) команда за преместване SAR е, че SHR копира най-значимия (знаков) бит към следващия и след това заменя знаковия бит с нула, докато SAR копира знаковия бит към следващия най-малко значителен бит, оставяйки първоначалната си стойност непроменена.

Разделянето по степени на две със смени може да се извърши с помощта на флага за носене и това не е по-трудно от умножението. Например, за да извършат подписано деление на 8 стойности, регистрите DX: AX могат да използват последователността

Но за разлика от операцията за умножение, използването на смени за бързо разделяне на произволни числа като 3 или 10, а не степени на две, е изненадващо обезпокоително. Ако решите да извършите упорита работа по писане на програма за бързо деление на 10, която използва метод, подобен на горния метод за умножение по 10, скоро ще установите, че получената програма е дълга, работи бавно и освен това имате вече е свършил 90% от работата. необходимо за съставяне на обобщена програма за разделяне, която използва отмествания и изваждания. Обикновено е по-добре да се преосмисли цялата ситуация вместо това и да се трансформира алгоритъмът или структурата на данните, за да се избегне разделяне на "неудобни" числа.

Сега, когато видяхте този нетривиален трик, вероятно имате много идеи за това как да организирате умножение или деление чрез относително големи степени на две: 256, 512 и т.н., като използвате последователности от команди XCHG или MOV.

Оптимизиране на клонове и извиквания на подпрограми

Програмите за тестени изделия, пълни с разклонения и скокове във всички посоки, са нежелани във всеки смисъл, и особено при работа с процесори от серия 80x86. Помислете за това твърдение като за разделителни думи, чиято цел е да насърчи програмистите за сглобяване и оптимизаторите на компилаторите да структурират правилно своите програми. Тук има някои проблеми, но преди да обсъдим оптимизирането на преходите и обажданията, нека обсъдим някои от спецификите на процесорите на Intel.

Ефективността на тези процесори до голяма степен се определя от тяхната архитектура, базирана на проста конвейерна схема, съдържаща три компонента: интерфейсен модул на шината (BIU), опашка за търсене и изпълнителен блок (EU). Когато шината на паметта не работи (например при изпълнение на инструкция в много цикли, чиито операнди са в регистрите), интерфейсът на шината извлича байтовете с инструкции от паметта и ги поставя в опашката за предварително извличане, постепенно напредвайки от текущата позиция на CPU инструкция брояч. Когато изпълнителният модул завърши изпълнението на следващата команда, той първо търси следващата команда в опашката за предварително извличане: ако тя наистина съществува там, тогава можете да пристъпите към нейното дешифриране незабавно, без да имате достъп отново до паметта.

В същото време, ако програмата трябва да работи главно на компютри с 8086 или 80286 процесори, подравняването трябва да се извърши в WORD граници, а ако е предназначено за процесори 80386DX, 80486DX, използвайте DWORD подравняване. (За процесора 80486, който има вътрешен кеш, е по-добре, когато позициите се намират на 16-байтови граници, но мисля, че е недопустим лукс да се харчат средно 8 байта на етикет.)

Ако програмата изисква условен клон, анализирайте точката за вземане на решение и организирайте програмата така, че вероятността за клон да е по-ниска от тази на нито един клон. Това ще намали броя на измиванията на командната опашка. Например, ако програмата проверява знака на променлива, която може да бъде отрицателна само в редки случаи, при специални обстоятелства, тогава накарайте вашата програма да "прескочи" през точката на разклонение, когато променливата е положителна:

По същия начин, ако различни стойности на променлива инициират различни действия и трябва да направите множество сравнения, последвани от условни скокове, опитайте да преместите сравненията с най-вероятната стойност по-близо до началото на веригата:

конвертирани в по-бързи

Елиминирането на рекурсивни разговори е много подобно на снаждането на опашки. Когато една програма се извиква последователно и това повикване се намира непосредствено преди инструкцията RETURN в програмата, повикването може да бъде преобразувано в клон, което едновременно ще увеличи скоростта и ще намали обема памет, необходим на стека. Например програмата

може да се преобразува в

Такава рекурсивна програма често може да бъде допълнително оптимизирана чрез преобразуване на рекурсията в цикъл.