Рекомендации по оптимизации срочного кода
Обновлен: Ноябрь 2007
Написание срочного кода требует понимания всех аспектов приложения и его взаимодействия с системой. В этом разделе даны альтернативные методы некоторых обычных способов кодирования, которые помогают убедиться, что срочная часть кода выполняется удовлетворительно.
В целом для улучшения срочного кода требуется следующее:
Знание того, для каких частей программы требуется написать срочный код.
Знание размера и скорости кода.
Знание ресурсов, которые потребляются новыми возможностями.
Знание минимальной работы, которая будет затрачена на выполнение задания.
Чтобы собрать сведения о производительности кода, можно использовать монитор производительности (perfmon.exe).
Ошибки страниц и попадания в кэш
Сортировка и поиск
MFC и библиотеки классов
Общие библиотеки
Кучи
Потоки
Небольшое рабочее множество.
Промахи в кэше и ошибки страниц
Промахи попаданий в кэш (как внешний, так и внутренний), как и ошибки страниц (при обращении к дополнительному хранилищу за программными инструкциями и данными), снижают производительность программы.
При обращении к кэшу ЦП программе может потребоваться 10–20 тактов. Попадания во внешний кэш могут требовать 20–40 тактов. Ошибка страницы может затратить один миллион тактов (предполагая, что процессор обрабатывает 500 миллионов инструкций в секунду и тратит 2 миллисекунды времени на ошибку страницы). Поэтому для лучшей работы программы необходимо написать код, который снизит число пропусков попаданий в кэш и ошибок страниц.
Одной из причин медленной работы программ являются более частые, чем нужно, ошибки страниц и пропуски кэша. Чтобы этого избежать, важно использовать структуры данных с правильным расположением ссылок, что означает поддержку отношений связанных элементов. Иногда внешне великолепная структура данных будет ужасной из-за неправильного расположения ссылок, и наоборот. Два примера:
Динамически размещаемые связанные списки могут снизить производительность программы, так как при поиске элемента или прохождении до конца списка каждая пропускаемая ссылка может не попадать в кэш или вызывать ошибку страницы. Списки, реализованные на основе простых массивов, могут быть фактически значительно более быстрыми из-за лучшего кэширования и меньшего числа ошибок страниц –они даже были бы еще быстрее, учитывая тот факт, что возможность увеличения массива была бы ограничена.
Хэш-таблицы, использующие динамически размещенные связанные списки, могут ухудшить производительность. Из-за наращивания хэш-таблицы, которые используют динамически размещенные связанные ссылки, могут снизить производительность при сохранении их содержимого. В действительности, простой линейный поиск через массив может быть фактически более быстрым (в зависимости от ситуаций). Реализация хэш-таблиц на базе массивов (так называемое закрытое хеширование), которая часто имеет высшую производительность, зачастую не принимается во внимание.
Сортировка и поиск
Сортировка является, по-существу, затратой времени в сравнении с другими типичными операциями. Чтобы не замедлять без необходимости производительность, избегайте выполнения сортировки в критические моменты времени. Можно использовать следующие варианты:
Отложить сортировку после времени, критического для производительности.
Выполнить сортировку данных до времени, критического для производительности.
Отсортировать только часть данных, действительно требующих сортировки.
Иногда можно составить список в отсортированном порядке. Будьте внимательны, так как если нужно вставить данные в отсортированный порядок, может потребоваться более сложная структура данных с плохо размещенной ссылкой, что приведет к пропускам попаданий в кэш и ошибкам страниц. Не существует подхода, работающего во всех случаях. Испробуйте несколько подходов и измерьте разницу.
Вот несколько обычных советов по сортировке:
Используйте стандартную сортировку, чтобы минимизировать ошибки.
Имеет результат любая работа, которую можно выполнить предварительно для снижения сложности сортировки. Если одноразовый проход по данным упрощает сравнения и снижает значение сортировки с O(n записей n) до O(n), это почти определенно будет продвижением вперед*.*
Продумайте расположение ссылки алгоритма сортировки и данных, которые планируется сортировать.
Для поиска имеется меньше альтернатив, чем для сортировки. Если поиск выполняется в критический момент времени, почти всегда лучше использовать двоичный поиск или поиск с помощью хэш-таблицы, однако в случае сортировки необходимо учитывать расположение. Линейный поиск через небольшой массив может быть более быстрым, чем двоичный поиск в структуре данных с большим числом указателей, который приводит к ошибкам страниц и пропускам попаданий в кэш.
MFC и библиотеки классов
Библиотека Microsoft Foundation Classes (MFC) может значительно упростить написание кода. При написании срочного кода следует знать о непременной дополнительной нагрузке в некоторых классах. Проверьте код MFC, который используется срочным кодом, чтобы увидеть, соответствует ли он требованиям производительности. В следующем списке указаны классы MFC и функции, о которых следует знать:
CString MFC вызывает библиотеку времени выполнения языка C для динамического выделения памяти для строки CString. В сущности, строка CString столь же эффективна, как любая другая динамически размещаемая строка. Она так же занимает дополнительные ресурсы для динамического размещения и удаления. Зачастую, простой массив char в стеке может быть более быстрым и служить тем же целям. Не используйте класс CString для хранения постоянной строки. Вместо него используйте const char *. Любые операции, выполняемые над объектом CString, требуют некоторых дополнительных ресурсов. Использование строковых функций библиотеки времени выполнения может быть более быстрым.
CArray CArray предоставляет гибкость, которой не обладает обычный массив, но программа может в ней не нуждаться. Если известны отдельные ограничения для массива, вместо этого можно использовать глобальный фиксированный массив. При применении объекта CArray используйте параметр CArray::SetSize, чтобы установить его размер и указать число элементов для возрастания при повторном размещении, если это необходимо. В противном случае добавление элементов может вызвать частое повторное размещение и копирование массива, что приведет к неэффективному использованию и фрагментации памяти. Также следует знать, что при вставке элемента в массив объект CArray перемещает последующие элементы в памяти, и может потребоваться увеличение массива. Эти действия могут вызвать пропуски попаданий в кэш и ошибки страниц. Если просмотреть код, который используется библиотекой MFC, можно увидеть и вписать дополнительные возможности специально для сценария улучшения производительности. Так как CArray является шаблоном, можно, например, добавить специализации CArray для отдельных типов.
CList CList является двусвязным списком, поэтому вставка элемента быстрее выполняется в заголовке, конце и известном положении (POSITION) в списке. Поиск элементов по значению или индексу требует последовательного поиска, который, однако, может быть медленным, если список длинный. Если код не требует двунаправленного связанного списка, можно пересмотреть использование объекта CList. Применение однонаправленного списка экономит ресурсы обновления и добавления указателя для всех операций, а также память для этого указателя. При экономии дополнительной памяти, однако, имеются другие обстоятельства, способствующие пропуску попаданий в кэш и ошибкам страниц.
IsKindOf Эта функция создает много вызовов и обращается к большому количеству памяти в разных областях данных, приводя к плохому расположению ссылки. Она полезна для отладки построения (например в вызове ASSERT), однако избегайте использовать ее в сборке выпуска.
PreTranslateMessage Используйте PreTranslateMessage, когда для одного из деревьев окон требуется отдельное сочетание клавиш или необходимо вставить обработку сообщений в конвейер сообщений. PreTranslateMessage изменяет сообщения об отправке MFC. При переопределении PreTranslateMessage делайте это только на необходимом уровне. Например, не требуется переопределять CMainFrame::PreTranslateMessage, если интересуют только сообщения, отправляемые дочерним элементам отдельного представления. Вместо этого переопределите PreTranslateMessage для класса представления.
Не обходите нормальный путь отправки с помощью PreTranslateMessage, чтобы обработать сообщение, отправленное в какое-либо окно. Используйте для этой цели оконные процедуры и схемы сообщений MFC.
OnIdle События простоя могут создаваться непредвиденно, например между событиями WM_KEYDOWN и WM_KEYUP. Возможно, чтобы запустить код, более эффективным будет использование таймеров. Не рекомендуется повторно вызывать событие OnIdle созданием сообщений об ошибке или постоянным возвращением значения TRUE из переопределения события OnIdle, которое никогда не позволит задать для потока спящий режим. Опять же, таймер или отдельный поток может быть более соответствующим решением.
Общие библиотеки
Повторное использование кода желательно. Однако если планируется использовать код другого разработчика, необходимо точно знать, что он делает в тех случаях, когда производительность критически важна. Лучшим способом узнать это будет пошаговое рассмотрение исходного кода или измерение с помощью таких средств, как PView или монитор производительности.
Кучи
Используйте несколько куч с осторожностью. Дополнительные кучи, созданные с помощью HeapCreate и HeapAlloc, позволяют управлять связанными наборами выделенной памяти и затем предоставлять их. Не выделяйте слишком много памяти. При использовании нескольких куч особое внимание уделите изначально выделенному количеству памяти.
Вместо нескольких куч можно использовать вспомогательные функции для взаимодействия между кодом и кучей по умолчанию. Вспомогательные функции помогают создавать пользовательские стратегии, которые могут улучшить производительность приложения. Например, если часто выделяется небольшое количество памяти, можно локализовать ее в одной части кучи по умолчанию. Можно выделить большой блок памяти и затем использовать вспомогательную функцию для дополнительного выделения памяти из этого блока. В результате, не будет дополнительных куч с неиспользуемой памятью, так как память выделяется из кучи по умолчанию.
В некоторых случаях, однако, использование кучи по умолчанию может сократить локальность ссылки. Используйте средство просмотра процессов, Spy++ или монитор производительности, чтобы измерить эффект перемещения объектов между кучами.
Измерьте кучи, чтобы можно было рассчитать каждое выделение для них памяти. Используйте программы из библиотеки DLL отладочной кучи времени выполнения C для проверки и вывода дампа кучи. Можно считать вывод в программу для работы с электронными таблицами, такую как Microsoft Excel, и использовать сводные таблицы для просмотра результатов. Запишите общее число, размер и распределения выделения памяти. Сравните этот размер с рабочими множествами. Также просмотрите кластеризацию размерно-связанных объектов.
Для мониторинга использования памяти можно также использовать счетчики производительности.
Потоки
Для задач, выполняемых в фоновом режиме, эффективная обработка простоя событий может быть более быстрой, чем использование потоков. Она более легко понимает расположение ссылок в однопоточной программе.
Рекомендуется использовать потоки, только если блокируемое уведомление операционной системы находится в корне фоновой работы. В таком случае использование потоков будет лучшим решением, так как непрактично блокировать основной поток в событии.
Потоки также представляют проблемы связи. Требуется управление каналами связи между потоками с помощью списка сообщений или выделения и использования общей памяти. Управление каналом связи обычно требует синхронизации, чтобы избежать состояниц гонки и взаимоблокировки. Такое усложнение может легко обернуться ошибками и проблемами производительности.
Дополнительные сведения см. в разделах Обработка циклов простоя и Многопоточность.
Небольшое рабочее множество
Более мелкие рабочие множества означают лучшее расположение ссылок, меньшее число ошибок страниц и больше попаданий в кэш. Рабочее множество процессов является ближайшим показателем, который операционная система непосредственно предоставляет для измерения расположения ссылок.
Чтобы задать верхнее и нижнее ограничение рабочего множества, используйте параметр SetProcessWorkingSetSize.
Чтобы вернуть верхнее и нижнее ограничение рабочего множества, используйте параметр GetProcessWorkingSetSize.
Чтобы просмотреть размер рабочего множества, используйте Spy++.