Эта заметка продолжение нашего разговора. В комментарии к предыдущей статье из этой серии было сделано справедливое замечание, что коэффициент C1 в выражении O(f(n)) = С1+C2*f(n)
и не имеет смысла согласно теоретическому определению вычислительной сложности алгоритмов.
Но реальная практика в очередной раз плохо согласуется с правильной теорией! Не будет преувеличением сказать, что в большинстве программ присутствует множество вызовов функций, в которых коэффициент С1 является доминирующим при типичных значениях n.
Рассмотрим типичные классы функций с большими накладными расходами.
Накладные расходы при системном вызове могут быть очень большими. Ведь для этого требуется:
В дополнение к вышеперечисленным накладным расходам при выполнении системного вызова может произойти сборос кэшей процессора (в первую очередь TLB), что приведет к временному замедлению исполнения программы, т.к. код и данные нужно будет заново кэшировать из медленной памяти.
Как же бороться с накладными расходами системных вызовов? Самый действенный способ — не использовать их :) Например, для функций, результат которых не зависит от переданных параметров и которые не имеют побочных эффектов (gettimeofday() и getpid()), программа может считывать результат этих функций из региона памяти, проецируемого из пространства ядра в пользовательское пространство, вместо того, чтобы выполнять системный вызов. Этот вид оптимизаций реализован в системных библиотеках как под Linux, так и под Windows.
Очевидно, что результаты системных вызовов, которые не имеют побочных эффектов, можно кэшировать в адресном пространстве процесса. Вместо блокирующих системных вызовов можно использовать неблокирующие. Это позволяет избежать лишних переключений контекста. Но не забывайте, что использование неблокирующих фукнций может существенно усложнить и запутать код вашего приложения.
Отдельно следует обсудить системные вызовы ввода-вывода. Для уменьшения накладных расходов таких функций операционная система может предоставлять дополнительные системные вызовы, позволяющие передавать и принимать данные группами (aka scatter-gather I/O или vectored I/O). Системные библиотеки, в свою очередь, предоставляют возможность буферизации ввода-вывода, которая позволяет существенно сократить количество системных вызовов.
Сейчас мало кто пишет программы, работающие напрямую с системными вызовами, т.к. они успешно спрятаны за более высокоуровневыми библиотеками функций. Но знания о накладных расходах системных вызовов и о том, как используемые библиотечные функции работают с ними, позволяют писать более эффективный код.
Также некоторые знания о методах оптимизации системных вызовов могут быть применены при оптимизации кода на высокоуровневых языках программирования, работающего с функциями с большими накладными расходами.
Это очень ресурсоемкая и медленная операция, о которой мало кто задумывается. Ведь для отрисовки изменившейся веб-страницы браузер должен пересчитать координаты всех элементов, положение которых могло поменяться, после чего перерисовать все элементы, затронутые изменившимися элементами, и сами изменившиеся элементы. Во многих случаях это означает полную перерисовку содержимого веб-страницы.
Браузеры не предоставляют явного вызова функции отрисовки веб-страницы. Как же определить, в каких случаях страница будет перерисована, и уменьшить количество отрисовок?
Есть следующие чисто эмпирические правила:
Например, если в таблицу нужно добавить несколько строчек, то лучше это сделать с помощью 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-запросов всегда нужно минимизировать. К сожалению, популярные на данный момент ORM’ы с LINQ’ами не способствуют этому. Наоборот, они часто приводят к проблеме N+1 selects.
Как же минимизировать количество SQL-запросов?
Также не забывайте фильтровать данные с помощью SQL-запросов, а не с помощью логики в вашем коде. Старайтесь возвращать ровно столько данных, сколько вам необходимо.
В принципе, SQL-запрос является лишь частным случаем для RPC, поэтому оптимизации, описанные выше, подходят и для этого случая. Для RPC можно добавить следующие методы оптимизаций:
К сожалению, хотя это и отчасти звучит параноидально, — функции с большими накладными расходами окружают нас повсюду :) Но в большинстве случаев мы можем успешно противостоять этому с помощью различных методов оптимизации, в т.ч. описанных в данной серии статей.
6 комментариев
Несколько вопросов автору, возникших уже при беглом прочтении статьи:
1. Что такое программные join-ы SQL (первый раз слышу о таких)?
2. Почему это SQL запрос является частным случаем RPC?
3. Как это SOAP или XML-основанный протокол не имеет ни каких преимуществ перед бинарным?
И давайте все-таки при разговоре об оптимизации ПО говорить об устранении узких мест, потому, что оптимизация тонкого клиента, функционирующего в том-же браузере, может никак не повлиять на производительность ПО вцелом.
> 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-основанный протокол не имеет ни каких преимуществ перед бинарным?
А вот так! :) Огласите эти преимущества, если они вам известны.
2. Ну в каком-то смысле, конечно, представить запрос к БД как RPC можно, но с другой стороны, отличий тоже хватает. RPC, например, часто делают асинхронно, потому что хз, как долго будет выполняться процедура, а с БД всё более или менее детерминированно и асинхронно его выполнять смысла нет.
3. XML человекочитабелен. Как минимум в целях отладки гораздо удобней. Хотя, конечно, сам по себе XML слишком перегружен лишним текстом, тот же JSON в этом смысле гораздо быстрее сериализуется-десереализуется.
2 KEIL:
> RPC, например, часто делают асинхронно, потому что хз, как долго будет выполняться процедура, а с БД всё более или менее детерминированно и асинхронно его выполнять смысла нет.
Почему смысла нет? Операции модификации данных (INSERT, UPDATE, DELETE) спокойно могут быть выполнены асинхронно. Да и причин, препятствующих асинхронному выполнению операций чтения данных (SELECT), я не вижу.
> 3. XML человекочитабелен. Как минимум в целях отладки гораздо удобней.
Что мешает отладчику преобразовать бинарное представление данных в удобочитаемое текстовое? В конце концов XML тоже передается в бинарной кодировке по каналу связи и отладчики как-то умеют его преобразовывать в текст, а некоторые отладчики даже строят из него DOM-модель :)
Данные, как правило, тянутся именно в тот момент, когда они нужны и без них всё равно дальнейшей работы нет. Например, нужно отобразить список товаров на странице - вытянули из базы, отобразили в браузере. Пока не вытянешь, отображать нечего. RPC - это уже другая парадигма, практически: экторы, колбеки, очереди выполнения. Конечно, можно и SQL-запросы делать асинхронно, и RPC синхронно, но ИМХО, тут скорее не отношение общее-частное, а пересекающиеся множества - есть общее, но есть и значительные различия.
Скажем так, текст проще интерпретировать на любой стадии и для него нужно минимум специальных инструментов. Например, делаете вы простой REST-сервис, при работе с банарным протоколом вам сразу придётся писать и клиента, с текстовым же достаточно обычного браузера (по крайней мере для запросов GET и POST). Ну и к тому же, сложно даже представить, что какие нибудь Facebook или Twitter для своего API начнут использовать не простую в понимании XML/JSON схему, а сложный бинарный протокол с описанием вроде "имя пользователя начинается в пакете по смещению 50 байт, возраст - 120 байт, места учёбы - ...". Да и c HTTP сложнее было бы.
Бинарные протоколы хороши, когда передаются сложные структуры данных, хорошо ужимающиеся при передаче: передал как есть, загрузил как есть - размер маленький, затраты на кодирование/декодирование отсутствуют. В остальных же случаях (пример с Fb API) тот же JSON вполне может посоперничать с ними.
А за статью спасибо, да. С особым интересом читал про уровни кеширования процессора (ещё с прошлой статьи), TLB, переключение контекстов и т.п.
2 KEIL:
> Данные, как правило, тянутся именно в тот момент, когда они нужны и без них всё равно дальнейшей работы нет.
С помощью RPC данные тянутся в другой момент времени?
Что мешает вытягивать данные с помощью асинхронных или параллельных запросов с последующим ожиданием события "все данные успешно вытянуты"? Или что мешает группировать маленькие запросы в один большой запрос, чтобы вытянуть все данные за один раз?
По-моему, асинхронность вообще никак не связана с RPC и SQL запросами. Это ортогональные понятия - т.е. захотел - сделал асинхронные запросы, захотел - синхронные, не важно - RPC это или SQL запросы.
Я не хотел сказать, что бинарные протоколы лучше текстовых. Просто есть ненормальные методы кодирования RPC сообщений (например, XML), а есть нормальные (например, JSON, protocol buffers). Первые отличаются от вторых ничем не обоснованными намного более высокими накладными расходами при создании, передаче и парсинге RPC сообщений.
Если же выбирать между JSON и бинарным протоколом в public web API, то в первую очередь нужно смотреть на распространенность средств работы с этими протоколами. И тут пока выигрывает JSON, т.к. его можно читать с любого браузера :) Но у JSON есть один существенный недостаток по сравнению с тем же protocol buffers - отсутствие языка описания и автоматической валидации типов параметров, передаваемых в запросе.