Поделиться через

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

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

Подытожим, для улучшения времязависимого кода требуется следующее:

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

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

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

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

Чтобы собрать сведения о производительности кода, можно использовать системный монитор (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 для отдельных типов.

  • 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++.

См. также

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

  • Last updated on