Оптимізація програм на асемблері
У попередній частині ми обговорювали деякі загальні питання оптимізації, а потім поговорили про ті компроміси, на які доводиться йти, оптимізуючи швидкодію та розмір програми. У цій та наступній частинах ми докладніше розглянемо деякі класичні зразки "локальної" оптимізації. Але важливо пам'ятати, що ці приватні методики слід використовувати лише за певних обставин - а саме: після того, як ви переконаєтеся, що застосували правильні алгоритми та структури даних, що повністю налагодили програму і що засоби профілювання показали вам ті самі фрагменти програми, які обмежують продуктивність.
Відмова від універсальності
Операції множення та поділу вимагають чималих зусиль від майже будь-якого ЦП, оскільки мають бути реалізовані (апаратно чи програмно) через зрушення та додавання або зрушення та віднімання відповідно. Старовинні 4- і 8-розрядні процесори не містили машинних команд для множення або поділу, так що ці операції доводилося реалізовувати за допомогою довгих підпрограм, де явно виконувались зрушення та додавання або віднімання. Перші 16-розрядні мікропроцесори, такі, як 8086 і 68000, дійсно дозволяли проводити операції множення та поділу апаратними засобами, але відповідні процедури були неймовірно повільними: у процесорі 8086, наприклад, для поділу 32-розрядного числа на 15-розрядне тактів.
Давайте спочатку розглянемо найпростішу процедуру оптимізації множення. Щоб помножити число на степернь двійки, досить просто зрушити вліво на необхідне число двійкових (бітових) позицій. Так, наприклад, виглядає деяка загальна, але повільна послідовність команд при множенні значеннязмінної 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 - bus interface unit), черга випереджальної вибірки і виконавчий модуль (EU - execution unit). Коли шина пам'яті знаходиться в неробочому стані (наприклад, при виконанні команди з багатьох циклів, операнди якої знаходяться в регістрах), шинний інтерфейс витягує байти команд з пам'яті і поміщає їх у чергу випереджальної вибірки, послідовно просуваючись від поточного положення командного лічильника ЦП. Коли виконавчий модуль завершує виконання чергової команди, він насамперед шукає наступну команду в черзі попереджувальної вибірки: якщо вона там дійсно є, то її розшифровку можна приступити відразу ж, не звертаючись зайвий раз до пам'яті.
У той же час, якщо програма має головним чином працювати на комп'ютерах з процесорами 8086 або 80286, слід зробити вирівнювання в межах WORD, а якщо вона розрахована на процесори 80386DX, 80486DX - використовуйте вирівнювання DWORD. (Для процесора 80486, в якому є внутрішня кеш-пам'ять, краще, коли позиції лежать на 16-байтових межах, але витрачати в середньому 8 байт на кожну мітку мені здається недозволеною розкішшю.)
Якщо програма потребує умовного переходу, проаналізуйте точку прийняття рішення та організуйте програму так, щоб ймовірність переходу була нижчою, ніж її відсутність. Таким чином, ви зменшите кількість скидів черги команд. Наприклад, якщо програма здійснює перевірку знака змінної, яка може бути негативною лише в окремих випадках, за особливих обставин, то зробіть так, щоб ваша прогама "проскакувала" через точку розгалуження при позитивному значенні змінної:
Аналогічно, якщо різні значення певної змінної ініціюють різні дії і вам потрібно зробити множинні порівняння, за якими йдуть умовні переходи, то спробуйте перемістити порівняння з найбільш ймовірним значенням ближче до початку ланцюжка:
перетворюється на швидшу
Усунення рекурсивних викликів дуже нагадує зрощування хвостів. Коли програма послідовно викликає сама себе і цей виклик розташований безпосередньо перед командою RETURN в програмі, виклик може бути перетворений на перехід, що і збільшить швидкість, і зменшить необхідний обсяг пам'яті в стеку. Наприклад, програма
може бути перетворена на
Така рекурсивна програма часто може бути оптимізована за рахунок перетворення рекурсії в цикл.