Рекомендации по оптимизации критичного по времени кода

  • Статья

Написание быстрого кода требует понимания всех аспектов приложения и его взаимодействия с системой. В этой статье приводятся альтернативные варианты некоторых из более очевидных методов написания кода, которые помогут вам убедиться, что критически важные части кода выполняются удовлетворительно.

В целом для улучшения срочного кода требуется следующее:

  • знание того, какие части программы должны выполняться быстро;

  • знание размера и скорости выполнения кода;

  • знание затрат на реализацию новых возможностей;

  • знание минимального объема работы, необходимого для выполнения задания.

Чтобы собрать сведения о производительности кода, можно использовать системный монитор (perfmon.exe).

Содержание этой статьи

Промахи кэша и ошибки страниц

Промахи кэша (как внутреннего, так и внешнего) и ошибки страниц (при обращении к дополнительному хранилищу за программными инструкциями и данными) снижают производительность программы.

Попадание в кэше ЦП позволяет программе выиграть 10–20 тактов. Попадание во внешнем кэше позволяет выиграть 20–40 тактов. Ошибка страницы может стоить миллион циклов часов (если процессор, обрабатывающий 500 миллионов инструкций/секунду и время 2 миллисекунда для сбоя страницы). Поэтому для оптимального выполнения программы необходимо написать код, который снизит число промахов кэша и ошибок страниц.

Одной из причин медленной работы программ являются слишком частые ошибки страниц и промахи кэша. Чтобы избежать этой проблемы, важно использовать структуры данных с хорошей локализацией ссылок, что означает сохранение связанных вещей вместе. Иногда внешне великолепная структура данных оказывается ужасной из-за неправильного расположения ссылок, и наоборот. Вот два примера:

  • Динамически выделенные связанные списки могут снизить производительность программы. При поиске элемента или при переходе по списку к концу каждая пропущенная ссылка может пропустить кэш или вызвать сбой страницы. Реализация списка на основе простых массивов может быть быстрее из-за лучшего кэширования и меньше ошибок страниц. Даже если вы разрешаете тот факт, что массив будет труднее расти, он все еще может быть быстрее.

  • Хэш-таблицы, использующие динамически размещаемые связанные списки, могут ухудшить производительность. По мере расширения такие хэш-таблицы могут начать работать значительно медленнее. В конечном итоге, простой линейный поиск по массиву может быть фактически более быстрым (в зависимости от ситуации). Использование хэш-таблицы на основе массива (так называемой "закрытой хэширования") часто игнорируется реализацией, которая часто имеет более высокую производительность.

Сортировка и поиск

Сортировка является, по существу, более затратной по времени в сравнении с другими стандартными операциями. Чтобы не снижать без необходимости производительность, избегайте выполнения сортировки в критические моменты времени. Возможны следующие решения.

  • Отложите сортировку на период времени, некритичный для производительности.

  • Выполните сортировку данных до периода времени, критичного для производительности.

  • Отсортируйте только часть данных, которая действительно требует сортировки.

Иногда можно составить список в отсортированном порядке. Будьте внимательны, так как если нужно будет вставлять данные в отсортированный порядок, потребуется более сложная структура данных с неоптимальным размещением ссылкой, что приведет к промахам кэша и ошибкам страниц. Во всех случаях нет никакого подхода. Испробуйте несколько подходов и оцените разницу.

Вот несколько общих советов по сортировке.

  • Используйте стандартную сортировку, чтобы свести к минимуму число ошибок.

  • Имеет смысл любая работа, которую можно выполнить предварительно для снижения сложности сортировки. Если однократная передача данных упрощает сравнение и уменьшает сортировку от O(n log 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 для отдельных типов.

  • CListCList является двусторонне связанным списком, поэтому вставка элементов быстро находится в голове, хвосте и в известной позиции (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++.

См. также

Оптимизация кода