Заметки об оптимизации программ. Часть 3: Функции с большими накладными расходами

В комментарии к предыдущей статье было сделано справедливое замечание, что коэффициент C1 в выражении O(f(n)) = С1+C2*f(n) не имеет смысла согласно теоретическому определению вычислительной сложности алгоритмов. Но практика плохо согласуется с теорией. Не будет преувеличением сказать, что в большинстве программ присутствует множество вызовов функций, в которых коэффициент С1 является доминирующим при типичных значениях n.

Рассмотрим типичные классы функций с большими накладными расходами

• Системный вызов

  Накладные расходы при системном вызове могут быть очень большими. Ведь для этого требуется:
  1. переход из пользовательского режима в режим ядра. На этом этапе может потребоваться переключение из адресного пространства процесса в адресное пространство ядра;
  2. чтение и проверка параметров, переданных пользователем в системный вызов. На этом этапе может потребоваться копирование переданных данных (например, длинных строчек) из адресного пространства процесса в адресное пространство ядра. Если не скопировать данные, то злонамеренный поток в адресном пространстве процесса может успеть подменить данные в интервале между их проверкой и их использованием в коде системного вызова;
  3. исполнение кода системного вызова. На этом этапе операционная система может переключиться на исполнение другого потока, если системный вызов оказался блокирующим. Переключение между потоками требует дополнительных накладных расходов;
  4. копирование результирующих данных из адресного пространства ядра в адресное пространство процесса;
  5. возвращение из режима ядра в пользовательский режим.
  В дополнение к вышеперечисленным накладным расходам при выполнении системного вызова может произойти сборос кэшей процессора (в первую очередь TLB), что приведет к временному замедлению исполнения программы, т.к. код и данные нужно будет заново кэшировать из медленной памяти.
  Как же бороться с накладными расходами системных вызовов? Самый действенный способ - не использовать их :). Например, для функций, результат которых не зависит от переданных параметров и которые не имеют побочных эффектов (gettimeofday() и getpid()), программа может считывать результат этих функций из региона памяти, проецируемого из пространства ядра в пользовательское пространство, вместо того, чтобы выполнять системный вызов. Этот вид оптимизаций реализован в системных библиотеках как под linux, так и под windows.
  Очевидно, что результаты системных вызовов, которые не имеют побочных эффектов, можно кэшировать в адресном пространстве процесса.
  Вместо блокриующих системных вызовов можно использовать неблокирующие. Это позволяет избежать лишних переключений контекста. Но не забывайте, что использование неблокирующих фукнций может существенно усложнить и запутать код вашего приложения.
  Отдельно следует обсудить системные вызовы ввода-вывода. Для уменьшения накладных расходов таких функций операционная система может предоставлять дополнительные системные вызовы, позволяющие передавать и принимать данные группами (aka scatter-gather I/O или vectored I/O). Системные библиотеки, в свою очередь, предоставляют возможность буферизации ввода-вывода, которая позволяет существенно сократить количество системных вызовов.
  Сейчас мало кто пишет программы, работающие напрямую с системными вызовами, т.к. они успешно спрятаны за более высокоуровневыми библиотеками функций. Но знания о накладных расходах системных вызовов и о том, как используемые библиотечные функции работают с ними, позволяют писать более эффективный код. Также некоторые знания о методах оптимизации системных вызовов могут быть применены при оптимизации кода на высокоуровневых языках программирования, работающего с функциями с большими накладными расходами.

• Отрисовка изменившихся веб-страниц в браузере

  Это очень ресурсоемкая и медленная операция, о которой мало кто задумывается. Ведь для отрисовки изменившейся веб-страницы браузер должен пересчитать координаты всех элементов, положение которых могло поменяться, после чего перерисовать все элементы, затронутые изменившимися элементами, и сами изменившиеся элементы. Во многих случаях это означает полную перерисовку содержимого веб-страницы.
  Браузеры не предоставляют явного вызова функции отрисовки веб-страницы. Как же определить, в каких случаях страница будет перерисована, и уменьшить количество отрисовок? Есть следующие эмпирические правила:
  • Любое изменение DOM-модели видимого на данный момент документа может привести к перерисовке веб-страницы. Отсюда вытекает очевидная оптимизация - как можно реже менять DOM-модель видимого на данный момент документа.
    Например, если в таблицу нужно добавить несколько строчек, то лучше это сделать с помощью table.innerHtml += html_for_new_rows вместо того, чтобы добавлять эти строчки в таблицу по одной. То же самое касается удаление элементов - лучше удалить нужные элементы за один раз, чем удалять их по одному. Но как это сделать, если они разбросаны по DOM-модели какого-нибудь элемента? Можно либо сконструировать новое значение innerHTML для этого элемента и затем заменить им старое значение за один раз, либо скопировать элемент с помощью element.cloneNode(true), произвести необходимые манипуляции с клоном, после чего подменить видимый элемент на измененный клон.
    Также должно быть очевидно, что конструировать сложный элемент, содержащий в себе много дочерних элементов, нужно до того, как он будет помещен в видимый документ. Т.е. elementInDocument.appendChild(complex_element) нужно делать лишь после того, как complex_element полностью сконструирован.
  • Изменение элементов, размер и позиция которых фиксированы, обычно не требует полной перерисовки страницы. Значит, если на сложной веб-странице присутствуют элементы, которые будут часто меняться, то постарайтесь зафиксировать их размер и позицию с помощью стилей (т.е. указать display:block, position:absolute, width, height, top, left).

• SQL запрос к базе данных

  Вызов SQL-запроса имеет очень большие накладные расходы.
  1. Создание подключения к базе данных, если оно не было создано до этого. Эта операция может быть очень медленной и трудоемкой, если подключение к СУБД осуществляется по сети. Взгляните еще раз на вот эту табличку и не забудьте, что создание TCP-подключения состоит из трех шагов, т.е. требует в три раза больше времени, чем просто передача данных по сети.
     Существует общепризнанная оптимизация этого шага - использование пула установленных подключений к СУБД.
  2. Формирование и отправка SQL запроса на сервер СУБД.
  3. Чтение и парсинг SQL запроса сервером СУБД.
  4. Оптимизация и поиск наилучшего плана исполнения SQL запроса на сервере СУБД. Для сложных запросов этот шаг может занимать очень много времени.
  5. Выполнение запроса. Если запрос не использует необходимые индексы, то этот шаг может очень сильно тормозить.
  6. Возвращение результата запроса клиенту. Этот шаг может тормозить, если результирующих данных слишком много.
  7. Чтение и преобразование результатов запроса в вид, требуемый нашей программой.
  Теперь вам должно быть очевидно, что количество SQL запросов всегда нужно минимизировать. К сожалению, популярные на данный момент ORM'ы с LINQ'ами не способствуют этому. Наоборот, они часто приводят к проблеме N+1 selects.
  Как же минимизировать количество SQL запросов?
  1. Тщательно проинспектируйте каждый запрос и подумайте, как можно от него избавиться.
  2. Кэшируйте наиболее часто используемые результаты запросов везде, где это возможно. Только не забывайте контролировать размер кэшей, иначе вы скоро узнаете, что такое OutOfMemoryException и 100% CPU in GC.
  3. Старайтесь группировать несколько запросов в один. Например, вместо того, чтобы реализовывать программные join'ы, всегда пользуйтесь средствами, предоставляемыми для join'ов в вашей СУБД. SQL join'ы будут работать быстрее даже хотя бы потому, что вы избегаете накладных расходов для большого количества SQL запросов, необходимых в программной реализации join'ов.
  4. Буферизируйте данные перед записью в СУБД, где это возможно, для того, чтобы затем записать их в базу данных с помощью одного SQL запроса.
  Также не забывайте фильтровать данные с помощью SQL запросов, а не с помощью логики в вашем коде. Старайтесь возвращать ровно столько данных, сколько вам необходимо.

• Удаленный вызов процедур (aka RPC, aka Web Service)

  В принципе, SQL запрос является частным случаем RPC, поэтому оптимизации, описанные выше, подходят и для этого случая. Для RPC можно добавить следующие методы оптимизаций:
  1. Не используйте XML-based сериализацию данных и протоколы типа SOAP. Они имеют очень большие накладные расходы по сравнение с binary протоколами типа protocol buffers и у них нет никаких преимуществ перед последними.
  2. Не передавайте лишние данные в RPC.
  3. Проектируйте RPC функции таким образом, чтобы клиент мог получить/передать всю необходимую информацию за минимальное количество вызовов RPC функций. Помните - чем меньше вызовов RPC функций, тем меньше накладных расходов и меньше время отклика.
  4. Добавляйте поддержку группировки мелких (похожих) RPC запросов в один большой RPC запрос.

Выводы

К сожалению, функции с большими накладными расходами окружают нас повсюду :) Но в большинстве случаев мы можем противостоять этому с помощью различных методов оптимизации, в т.ч. описанных в данной статье.

16 лет dev.by — «дефолтный» источник информации о беларусском ИТ

Вы можете...