Просмотров: 8107

Заметки об оптимизации: Функции с большим оверхедом


Эта заметка продолжение нашего разговора. В комментарии к предыдущей статье из этой серии было сделано справедливое замечание, что коэффициент 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. Существует общепризнанная оптимизация этого шага — использование пула установленных подключений к СУБД.

    3. Формирование и отправка SQL-запроса на сервер СУБД.
    4. Чтение и парсинг SQL-запроса сервером СУБД.
    5. Оптимизация и поиск наилучшего плана исполнения SQL-запроса на сервере СУБД. Для сложных запросов этот шаг может занимать очень много времени.
    6. Выполнение запроса. Если запрос не использует необходимые индексы, то этот шаг может очень сильно тормозить.
    7. Возвращение результата запроса клиенту. Этот шаг может тормозить, если результирующих данных слишком много.
    8. Чтение и преобразование результатов запроса в вид, требуемый нашей программой.

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

Выводы

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

twitter.com facebook.com vkontakte.ru odnoklassniki.ru mail.ru ya.ru pikabu.ru blogger.com liveinternet.ru livejournal.ru google.com bobrdobr.ru yandex.ru del.icio.us

Подписка на обновления блога → через RSS, на e-mail, через Twitter
Теги: , , , ,
Эта запись опубликована: Понедельник, 2 января 2012 в рубрике Программирование.

6 комментариев

Следите за комментариями по RSS
  1. Николай

    Несколько вопросов автору, возникших уже при беглом прочтении статьи:

    1. Что такое программные join-ы SQL (первый раз слышу о таких)?

    2. Почему это SQL запрос является частным случаем RPC?

    3. Как это SOAP или XML-основанный протокол не имеет ни каких преимуществ перед бинарным?

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

  2. > 1. Что такое программные join-ы SQL?

    Это когда вместо

    fоr (a_id, b_id, something) in query("SЕLЕCT a.a_id, a.b_id, b.something FRОM A JОIN B ОN (a.b_id=b.b_id)"):

    ...

    пишут вот так вот:

    fоr a_id, b_id in quеry("SЕLECT a_id, b_id FRОM A"):

    fоr something in quеry("SЕLECT something FRОM B whеre b_id=%d" % b_id):

    ...

    > 2. Почему это SQL запрос является частным случаем RPC?

    Потому что SQL запрос к СУБД можно представить в виде удаленного вызова функции, в качестве параметра к которой передан текст SQL запроса.

    > 3. Как это SOAP или XML-основанный протокол не имеет ни каких преимуществ перед бинарным?

    А вот так! :) Огласите эти преимущества, если они вам известны.

  3. 2. Ну в каком-то смысле, конечно, представить запрос к БД как RPC можно, но с другой стороны, отличий тоже хватает. RPC, например, часто делают асинхронно, потому что хз, как долго будет выполняться процедура, а с БД всё более или менее детерминированно и асинхронно его выполнять смысла нет.

    3. XML человекочитабелен. Как минимум в целях отладки гораздо удобней. Хотя, конечно, сам по себе XML слишком перегружен лишним текстом, тот же JSON в этом смысле гораздо быстрее сериализуется-десереализуется.

  4. 2 KEIL:

    > RPC, например, часто делают асинхронно, потому что хз, как долго будет выполняться процедура, а с БД всё более или менее детерминированно и асинхронно его выполнять смысла нет.

    Почему смысла нет? Операции модификации данных (INSERT, UPDATE, DELETE) спокойно могут быть выполнены асинхронно. Да и причин, препятствующих асинхронному выполнению операций чтения данных (SELECT), я не вижу.

    > 3. XML человекочитабелен. Как минимум в целях отладки гораздо удобней.

    Что мешает отладчику преобразовать бинарное представление данных в удобочитаемое текстовое? В конце концов XML тоже передается в бинарной кодировке по каналу связи и отладчики как-то умеют его преобразовывать в текст, а некоторые отладчики даже строят из него DOM-модель :)

  5. Данные, как правило, тянутся именно в тот момент, когда они нужны и без них всё равно дальнейшей работы нет. Например, нужно отобразить список товаров на странице - вытянули из базы, отобразили в браузере. Пока не вытянешь, отображать нечего. RPC - это уже другая парадигма, практически: экторы, колбеки, очереди выполнения. Конечно, можно и SQL-запросы делать асинхронно, и RPC синхронно, но ИМХО, тут скорее не отношение общее-частное, а пересекающиеся множества - есть общее, но есть и значительные различия.

    Скажем так, текст проще интерпретировать на любой стадии и для него нужно минимум специальных инструментов. Например, делаете вы простой REST-сервис, при работе с банарным протоколом вам сразу придётся писать и клиента, с текстовым же достаточно обычного браузера (по крайней мере для запросов GET и POST). Ну и к тому же, сложно даже представить, что какие нибудь Facebook или Twitter для своего API начнут использовать не простую в понимании XML/JSON схему, а сложный бинарный протокол с описанием вроде "имя пользователя начинается в пакете по смещению 50 байт, возраст - 120 байт, места учёбы - ...". Да и c HTTP сложнее было бы.

    Бинарные протоколы хороши, когда передаются сложные структуры данных, хорошо ужимающиеся при передаче: передал как есть, загрузил как есть - размер маленький, затраты на кодирование/декодирование отсутствуют. В остальных же случаях (пример с Fb API) тот же JSON вполне может посоперничать с ними.

    А за статью спасибо, да. С особым интересом читал про уровни кеширования процессора (ещё с прошлой статьи), TLB, переключение контекстов и т.п.

  6. 2 KEIL:

    > Данные, как правило, тянутся именно в тот момент, когда они нужны и без них всё равно дальнейшей работы нет.

    С помощью RPC данные тянутся в другой момент времени?

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

    По-моему, асинхронность вообще никак не связана с RPC и SQL запросами. Это ортогональные понятия - т.е. захотел - сделал асинхронные запросы, захотел - синхронные, не важно - RPC это или SQL запросы.

    Я не хотел сказать, что бинарные протоколы лучше текстовых. Просто есть ненормальные методы кодирования RPC сообщений (например, XML), а есть нормальные (например, JSON, protocol buffers). Первые отличаются от вторых ничем не обоснованными намного более высокими накладными расходами при создании, передаче и парсинге RPC сообщений.

    Если же выбирать между JSON и бинарным протоколом в public web API, то в первую очередь нужно смотреть на распространенность средств работы с этими протоколами. И тут пока выигрывает JSON, т.к. его можно читать с любого браузера :) Но у JSON есть один существенный недостаток по сравнению с тем же protocol buffers - отсутствие языка описания и автоматической валидации типов параметров, передаваемых в запросе.

Оставьте комментарий!

Не регистрировать/аноним

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

Зарегистрировать/комментатор

Для регистрации укажите свой действующий email и пароль. Связка email-пароль позволяет вам комментировать и редактировать данные в вашем персональном аккаунте, такие как адрес сайта, ник и т.п. (Письмо с активацией придет в ящик, указанный при регистрации)

(обязательно)


⇑ Наверх
⇓ Вниз