Рекомендации по оптимизации срочного кода
Написание быстрого кода требует понимания всех аспектов приложения и его взаимодействия с системой. В этой статье даны альтернативы некоторым обычным способам написания кода, помогающие обеспечить удовлетворительное выполнение части кода, для которой время выполнения имеет критически важное значение.
В целом для улучшения срочного кода требуется следующее:
знание того, какие части программы должны выполняться быстро;
знание размера и скорости выполнения кода;
знание затрат на реализацию новых функций;
знание минимального объема работы, необходимого для выполнения задания.
Чтобы собрать сведения о производительности кода, можно использовать системный монитор (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++ или системный монитор, чтобы оценить эффект перемещения объектов между кучами.
Измерьте кучи, чтобы можно было рассчитать каждое выделение памяти в них. Используйте подпрограммы времени выполнения C для отладки кучи, чтобы проверить и вывести дамп кучи. Выходные данные можно передать в программу для работы с электронными таблицами, такую как Microsoft Excel, и использовать сводные таблицы для просмотра результатов. Обратите внимание на общее число, размер и распределение выделенных объемов памяти. Сравните эти значения с размером рабочих наборов. Также обратите внимание на кластеризацию объектов соответствующего размера.
Для мониторинга использования памяти можно также использовать счетчики производительности.
Потоки
Для задач, выполняемых в фоновом режиме, эффективная обработка простоя событий может быть более быстрой, чем использование потоков. В однопоточной программе легче понять расположение ссылок.
Потоки рекомендуется использовать, только если блокируемое уведомление операционной системы находится в корневом процессе фоновой работы. В таком случае использование потоков будет лучшим решением, так как непрактично блокировать основной поток в событии.
Потоки также вызывают проблемы со взаимодействием. Каналом взаимодействия между потоками необходимо управлять с помощью списка сообщений или путем выделения и использования общей памяти. Управление каналом взаимодействия обычно требует синхронизации во избежание состояний гонки и взаимоблокировки. Такое усложнение легко может обернуться ошибками и проблемами с производительностью.
Подробнее см. в статьях Обработка пустых циклов и Многопоточность.
Небольшой рабочий набор
Чем меньше размер рабочих наборов, тем лучше расположение ссылок, меньше число ошибок страниц и больше попаданий в кэше. Рабочий набор процессов является наиболее точным показателем, который операционная система непосредственно предоставляет для оценки расположения ссылок.
Чтобы задать верхнее и нижнее ограничение для рабочего набора, используйте функцию SetProcessWorkingSetSize.
Чтобы получить верхнее и нижнее ограничение для рабочего набора, используйте функцию GetProcessWorkingSetSize.
Чтобы просмотреть размер рабочего набора, используйте Spy++.