Техника оптимизации под линуха


Содержание


Техника оптимизации под линуха
Общие соображения по оптимизации
Общие соображения по оптимизации - часть 2
Свертка констант
Объединение констант
Листинг1 не оптимизированный кандидат в объединение констант
Листинг2 частично оптимизированный вариант
Листинг3 полностью оптимизированный вариант
Константная подстановка в условиях
Константная подстановка в функциях
Листинг4 кандидат на константную подстановку
Удаление мертвого кода
Удаление неиспользуемых функций
Удаление неиспользуемых переменных
Удаление неиспользуемых выражений
Листинг 6 пример программы с неиспользуемыми выражениями
Удаление лишних обращений к памяти
Листинг 7 пример с лишними обращениями к памяти, от которых нельзя избавиться
Листинг8 пример с лишними обращениями к памяти, от которых можно избавиться вручную
Удаление копий переменных
Листинг 10 переменные a и b — лишнее
Размножение переменных
Листинг 11 ложная зависимость по данным
Листинг12 размножение переменной a устраняет зависимость по данным
Распределение переменных по регистрам
Листинг 13 глубоко вложенный цикл чувствителен к качеству распределения переменных по регистрам
Регистровые ре-ассоциации
Листинг 14 неоптимизированный кандидат на регистровую ре-ассоциацию
Листинг15 оптимизированный вариант — счетчик цикла совмещен с указателем на массив
Упрощение выражений
Листинг 16 это так Microsoft нас учит писать программы
Листинг17 неоптимизированный кандидат на алгебраическое упрощение
Листинг18 загадочный код, сгенерированный компилятором vc
Листинг 19еще один кандидат на алгебраическое упрощение
Упрощение алгоритма
Листинг 20 кандидат на упрощение алгоритма
Использование подвыражений
Листинг 21 подвыражение (x*y) – общее
Листинг 22оптимизированный вариант
Листинг 23пример с неочевидной разбивкой на подвыражения
Листинг24 полностью оптимизированный вариант (ручная оптимизация)
Листинг25 случай удаления частичной избыточности
Сводная таблица качества оптимизации
Заключение
Техника оптимизации под LINUX III оптимизация циклов
Введение
Выравнивание циклов
Разворот циклов
Листинг 1 цикл до разворота
Листинг2 цикл после разворота (меньшей размер, большая скорость)
Листинг3 цикл после разворота
Листинг3 цикл после разворота - часть 2
Шелушение циклов
Листинг 4 кандидат на оптимизацию
Листинг5 оптимизированный вариант
Фальцевание циклов
Листинг 6 не оптимизированный вариант – один поток данных на итерацию
Листинг7 оптимизированный вариант — четыре потока данных на итерацию
Векторизация
Листинг 8 цикл до векторизации
Листинг9 тот же цикл, записанный в векторной нотации
Листинг10 цикл после векторизации
Листинг 11 цикл который нельзя векторизовать
Авто-параллелизм
Листинг12 нерптимизированный вариант
Листинг13 оптимизированный вариант
Программная конвейеризация
Листинг 15 оптимизированный вариант
Предвычисление индуктивных циклов
Листинг 16 индуктивный цикл до оптимизации
Листинг17 индуктивный цикл после оптимизации
Разбивка длинных цепочек зависимостей
Листинг 18 индуктивный цикл до оптимизации
Листинг19 индуктивный цикл после оптимизации
Устранение хвостовой рекурсии
Листинг 20 хвостовая рекурсия до оптимизации
Листинг21 хвостовая рекурсия после оптимизации
Объединение циклов
Листинг 22 циклы до объединения (не оптимизированный вариант)
Листинг23 циклы после объединения (оптимизированный вариант)
Листинг24 кандидат в оптимизацию путем объединения
Листинг 25оптимизированный вариант
Трепание циклов
Листинг 26 два цикла с различным количеством итераций (не оптимизированный вариант)
Листинг27 частичное объединение циклов путем "трепки" (оптимизированный вариант)
Расщепление циклов
Листинг 28 не оптимизированный вариант
Листинг29 оптимизированный вариант
Нормализация циклов
Листинг 30 ненормализованный цикл
Листинг31 нормализованный цикл
Листинг32 ненормализованный цикл
Листинг33 нормализованный цикл
Масштабирование циклов
Листинг 34 исходный цикл (неоптимизированный вариант)
Листинг35 цикл после масштабирования (оптимизированный вариант)
Замена циклов с предусловием на циклы с пост-условием
Стремление циклов к нулю
Листинг36 не оптимизированный вариант
Листинг37 не оптимизированный вариант
Листинг38 оптимизированный вариант
Отказ от branch-count-reg
Вынос инвариантных ветвлений
Листинг39 цикл с инвариантным ветвлением (не оптимизированный вариант)
Листинг40 оптимизированный вариант
Ротация ветвлений
Листинг 41 неоптимизированный вариант
Листинг42 оптимизированный вариант
Упорядочивание обращений к памяти
Листинг 44 обработка массивов по столбцам (не оптимизированный вариант)
Листинг45 обработка массивов по столбцам (оптимизированный вариант)
Листинг46 сложный случай обработки данных по столбцам
Листинг47 оптимизированный вариант
Свободная таблица качества оптимизации
Заключение
Техника оптимизации под LINUX частьII — ветвления
Оптимизация ветвлений/branch
Выравнивание переходов
Частичное вычисление условий
Удаление избыточных проверок
Удаление проверок нулевых указателей
Листинг 5 не оптимизированный вариант
Совмещение проверок
Листинг 6 не оптимизированный вариант, 2 проверки
Листинг7 оптимизированный вариант, только одна проверка
Сокращение длины маршрута
Листинг 8 не оптимизированный вариант
Листинг9 оптимизированный вариант
Листинг10 не оптимизированный вариант
Листинг11 оптимизированный вариант
Листинг12 не оптимизированный вариант
Листинг13 оптимизированный вариант
Листинг14 трансформация условных переходов, до которых процессор не может "дотянуться"
Листинг15 не оптимизированный вариант
Уменьшение кол-ва ветвлений
Листинг 17 не оптимизированный вариант
Листинг18 оптимизированный вариант
Листинг19 не оптимизированный вариант, 2 ветвления
Сокращение количества сравнений
Листинг 21 сравнение двух чисел на языке ассемблера
Листинг22 сравнение двух чисел на языке высокого уровня
Избавление от ветвлений
Листинг 23 поиск максимума среди двух целых чисел без использования ветвлений
Листинг24 не оптимизированный вариант с ветвлениями
Листинг25 устранение ветвлений путем использования функции select_gt библиотеки классов Intel SIMD
Оптимизация switch
Балансировка логического древа
Листинг 26 не оптимизированный вариант оператора множественно выбора
Рисунок1 несбалансированное (слева) и сбалансированное (справа) switch/case-дерево
Рисунок2 троичное дерево, частично сбалансированное методом отрезков
Создание таблицы переходов
Листинг 27 не оптимизированный
Листинг28 дизассемблерный листинг оптимизированного варианта оператора switch
Листинг29 не оптимизированный
Свободная таблица
Заключение
>>> Мини-врезка советы



- Начало -