В комментарии к предыдущей статье было сделано справедливое замечание, что коэффициент C1 в выражении O(f(n)) = С1+C2*f(n) не имеет смысла согласно теоретическому определению вычислительной сложности алгоритмов. Но практика плохо согласуется с теорией. Не будет преувеличением сказать, что в большинстве программ присутствует множество вызовов функций, в которых коэффициент С1 является доминирующим при типичных значениях n.
Рассмотрим типичные классы функций с большими накладными расходами
-
Системный вызов
Накладные расходы при системном вызове могут быть очень большими. Ведь для этого требуется:- переход из пользовательского режима в режим ядра. На этом этапе может потребоваться переключение из адресного пространства процесса в адресное пространство ядра;
- чтение и проверка параметров, переданных пользователем в системный вызов. На этом этапе может потребоваться копирование переданных данных (например, длинных строчек) из адресного пространства процесса в адресное пространство ядра. Если не скопировать данные, то злонамеренный поток в адресном пространстве процесса может успеть подменить данные в интервале между их проверкой и их использованием в коде системного вызова;
- исполнение кода системного вызова. На этом этапе операционная система может переключиться на исполнение другого потока, если системный вызов оказался блокирующим. Переключение между потоками требует дополнительных накладных расходов;
- копирование результирующих данных из адресного пространства ядра в адресное пространство процесса;
- возвращение из режима ядра в пользовательский режим.
Как же бороться с накладными расходами системных вызовов? Самый действенный способ - не использовать их :). Например, для функций, результат которых не зависит от переданных параметров и которые не имеют побочных эффектов (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).
-
Любое изменение DOM-модели видимого на данный момент документа может привести к перерисовке веб-страницы. Отсюда вытекает очевидная оптимизация - как можно реже менять DOM-модель видимого на данный момент документа.
-
SQL запрос к базе данных
Вызов SQL-запроса имеет очень большие накладные расходы.-
Создание подключения к базе данных, если оно не было создано до этого. Эта операция может быть очень медленной и трудоемкой, если подключение к СУБД осуществляется по сети. Взгляните еще раз на вот эту табличку и не забудьте, что создание TCP-подключения состоит из трех шагов, т.е. требует в три раза больше времени, чем просто передача данных по сети.
Существует общепризнанная оптимизация этого шага - использование пула установленных подключений к СУБД. - Формирование и отправка SQL запроса на сервер СУБД.
- Чтение и парсинг SQL запроса сервером СУБД.
- Оптимизация и поиск наилучшего плана исполнения SQL запроса на сервере СУБД. Для сложных запросов этот шаг может занимать очень много времени.
- Выполнение запроса. Если запрос не использует необходимые индексы, то этот шаг может очень сильно тормозить.
- Возвращение результата запроса клиенту. Этот шаг может тормозить, если результирующих данных слишком много.
- Чтение и преобразование результатов запроса в вид, требуемый нашей программой.
Как же минимизировать количество SQL запросов?- Тщательно проинспектируйте каждый запрос и подумайте, как можно от него избавиться.
- Кэшируйте наиболее часто используемые результаты запросов везде, где это возможно. Только не забывайте контролировать размер кэшей, иначе вы скоро узнаете, что такое OutOfMemoryException и 100% CPU in GC.
- Старайтесь группировать несколько запросов в один. Например, вместо того, чтобы реализовывать программные join'ы, всегда пользуйтесь средствами, предоставляемыми для join'ов в вашей СУБД. SQL join'ы будут работать быстрее даже хотя бы потому, что вы избегаете накладных расходов для большого количества SQL запросов, необходимых в программной реализации join'ов.
- Буферизируйте данные перед записью в СУБД, где это возможно, для того, чтобы затем записать их в базу данных с помощью одного SQL запроса.
-
Создание подключения к базе данных, если оно не было создано до этого. Эта операция может быть очень медленной и трудоемкой, если подключение к СУБД осуществляется по сети. Взгляните еще раз на вот эту табличку и не забудьте, что создание TCP-подключения состоит из трех шагов, т.е. требует в три раза больше времени, чем просто передача данных по сети.
-
Удаленный вызов процедур (aka RPC, aka Web Service)
В принципе, SQL запрос является частным случаем RPC, поэтому оптимизации, описанные выше, подходят и для этого случая. Для RPC можно добавить следующие методы оптимизаций:- Не используйте XML-based сериализацию данных и протоколы типа SOAP. Они имеют очень большие накладные расходы по сравнение с binary протоколами типа protocol buffers и у них нет никаких преимуществ перед последними.
- Не передавайте лишние данные в RPC.
- Проектируйте RPC функции таким образом, чтобы клиент мог получить/передать всю необходимую информацию за минимальное количество вызовов RPC функций. Помните - чем меньше вызовов RPC функций, тем меньше накладных расходов и меньше время отклика.
- Добавляйте поддержку группировки мелких (похожих) RPC запросов в один большой RPC запрос.
Релоцировались? Теперь вы можете комментировать без верификации аккаунта.