Проект фактично являє собою онлайн сховище вільно поширюваного програмного коду. Свої розробки тут можуть розміщувати всі охочі, а доступ до проектів можна отримати всім користувачам з будь-якої точки світу.
- У нас є бібліотека в якій багато цікавих прикладів коду на різних мовах програмування.
Заміна ділення множенням на Асемблері
Заміна ділення множенням на Асемблері
При написанні на Асемблері алгоритмів, що використовують поділ на константу, операції ділення можна замінювати на операції множення. Навіщо це треба? Справа в тому, що процесор виконує операцію множення в кілька разів швидше, ніж операцію ділення. Наприклад, на множення витрачається 5-9 тактів процесора (знакова множення) або 4-8 (беззнаковое множення), тоді як для поділу необхідно 22-47 тактів (знакова поділ) або 17-41 тактів (беззнаковое розподіл). У високооптимізовані алгоритмах, таких як шифрування, математичні розрахунки, архівація великих обсягів даних, підрахунок контрольних сум і інших подібних завданнях, економія кожного такту процесора може дати значний приріст загальної швидкості роботи програми.
У керівництві по оптимізації "AMD Athlon Processor x86 Code Optimization Guide" питання заміни ділення множенням розписаний дуже докладно. Розглянуто окремі випадки ділення, такі як поділ на ступінь двійки, описаний вибір алгоритму для знакового і беззнакового ділення і приведений код для обчислення допоміжних коригувальних значень. Крім цього, в керівництві описані методи оптимізації та інших математичних операцій. Навіть якщо ви ніколи не будете використовувати на практиці заміну ділення множенням, почитати про інші способи оптимізації буде дуже корисно.
Спершу розглянемо оптимізацію беззнакового цілочисельного ділення. Тут є кілька варіантів в залежності від значень подільника. Перший варіант - якщо дільник знаходиться в діапазоні від 1 до (231 - 1):
Тип алгоритму, множник і коефіцієнт зміщення обчислюються на підставі значення дільника. В мануалі для цього наведені вихідні програми на C. Він наочний і зручний для розуміння.
Другий варіант беззнакового ділення - коли дільник знаходиться в інтервалі від 231 до (232 - 1). В цьому випадку приватне може приймати тільки два значення - 0 або 1. Відповідно, оптимізований алгоритм буде мати наступний вигляд:
У разі, якщо значення діленого неважливо для подальших розрахунків, цей варіант можна ще трохи оптимізувати, відмовившись від використання додаткового регістра:
В мануалі, до речі, в цьому місці допущена помилка. У тексті розповідається про позбавлення від другого регістра, і тут же наводиться непрацюючий код з цим же регістром (сторінка 117, якщо цікаво). Копіпаст не завжди буває корисним. Там же в мануалі рекомендується використовувати варіант з додатковим регістром, хоча особисто я якийсь принципової різниці в цьому не бачу. Ті ж яйця, тільки збоку.
Про всяк випадок нагадаю окремі випадки беззнакового цілочисельного ділення. На нуль натуральні числа ділити не можна, це без варіантів, так що і про оптимізацію тут мови бути не може. При розподілі на одиницю приватне завжди одно делимому, це ви теж повинні пам'ятати ще зі шкільної лави. Розподіл на ступінь двійки в Асемблері оптимізується з використанням команди бітового зсуву вправо SHR reg, степень_двойкі:
Під це ж правило, в принципі, можна притягнути і розподіл на одиницю, так як 20 = 1.
Целочисленное знакова поділ трохи складніше, тому що при отриманні результату доводиться враховувати знак діленого і дільника. Наведені нижче алгоритми працюють тільки з позитивними значеннями дільника. Якщо дільник негативний, то спершу обчислюється його модуль, який і використовується в подальших розрахунках, а до отриманого результату ділення застосовується асемблерна команда NEG. Це випливає з математичної аксіоми n / -d = - (n / d). Цілочисельний дільник повинен знаходитися в діапазоні від 2 до (231 - 1).
Як і в беззнакову розподілі, тип алгоритму, множник і коефіцієнт зміщення обчислюються на підставі значення дільника, а точніше його модуля. Исходник на C є в мануалі.
Окремі випадки целочисленного знакового розподілу також відрізняються від беззнакового. Ось, наприклад, розподіл на двійку і ступеня двійки з різними знаками.
Як ви вже зрозуміли, все оптимізації операцій ділення на заздалегідь відому константу виконуються на стадії написання програми, а не обчислюються динамічно в процесі її роботи. Інакше про яку оптимізації може йти мова? З цього ж випливає, що використовувати такі алгоритми для часто мінливих подільників не треба.