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

Заметки об оптимизации: О пользе Loop-invariant Code Motion


Это первая заметка из серии статей, посвященных введению в теорию оптимизации программ.

Приведенные ниже примеры кода написаны на гипотетическом языке программирования, который больше всего похож на C# и Java. Это сделано лишь для того, чтобы сделать публикуемый материал доступным для понимания широкому кругу читателей, без привязки к какому-то одному конкретному языку (и  автоматически к фобиям его фанатов/антифанатов).

В первой части, мы начнем с рассмотрения так называемого Loop-invariant Code Motion (LICM), то есть как понятно из термина — рассмотрим правильность создания циклов.

Выполнение Loop-invariant Code Motion (LICM) вручную

Никогда не надейтесь на компилятор в плане LICM — он не такой умный, как вам кажется. Теоретическое доказательство того, что компилятор сумеет провести LICM для заданного цикла, часто бывает на порядок сложнее, чем доказательство возможности применения LICM для данного цикла.

Рассмотрим классический пример цикла, многочисленные вариации которого присутствуют почти в любом проекте:

void Foo(IBar bar) {
for (int i = 0; i < bar.Count(); i++) {
Baz(bar);
}
}

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

  • Знать все реализации IBar.Count(). Это невозможно, если данный цикл находится в динамически подключаемой библиотеке с экспортированным интерфейсом IBar, т.к. все реализации IBar.Count() не могут быть известны на момент компиляции цикла по определению.
  • Доказать, что Baz() не может повлиять на значения, возвращаемые bar.Count().
  • Доказать, что код, исполняемый в параллельных потоках, не может повлиять на значения, возвращаемое bar.Count().

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

Для вышеприведенного случая типична следующая очевидная оптимизация:

void Foo(IBar bar) {
int c = bar.Count();
for (int i = 0; i < c; i++) {
Baz(bar);
}
}

Уже слышу недовольные голоса моих читателей —

«а что, если bar.Count() просто возвращает значение поля bar.count без каких-либо побочных эффектов? В этом случае вышеприведенная оптимизация нисколько не ускорит цикл».
  • Во-первых, на то, чтобы вернуть bar.count, требуется минимум одна инструкция процессора на каждую итерацию цикла — чтение bar.count из памяти. Если каждая итерация цикла выполняется за 200 миллисекунд, а каждое чтение bar.count — за 100 наносекунд, то кэширование результата bar.Count() перед циклом позволяет ускорить цикл в два раза. Это не такие невероятные цифры, как могут показаться на первый взгляд, если вспомнить, что операция чтения из памяти на современных компьютерах может занимать сотни тактов процессора. Также не забывайте про накладные расходы на вызов виртуальной функции.
  • Во-вторых, откуда вы знаете, что взбредет в голову другим разработчикам, решившим написать собственную реализацию IBar? Может, они решат вытягивать возвращаемое значение из базы данных или вычислять его с помощью 100500 последовательных запросов к тормозному веб-сервису, находящемуся на другом конце света?

Второй по распространенности пример неэффективного программирования — обращение к синглтонам внутри наиболее часто вызываемого цикла:

for (;;) {
FooSingleton.GetInstance().Bar();
}}

или, что почти то же самое:

void Foo() {
FooSingleton.GetInstance.Baz();
}
for (;;) {
Foo();
}

Самое интересное начинается, когда профилирование программ с такими циклами показывает, что узким местом является вызов FooSingleton.GetInstance(). Обычно его начинают оптимизировать с помощью печально известного метода Double-checked locking, хотя на самом деле нужно было всего лишь вручную произвести простейшую LICM-оптимизацию:

Foo foo = FooSingleton.GetInstance();
for (;;) {
foo.Bar();
}

или, для второго примера:

void Foo(Foo foo) {
foo.Baz();
}
Foo foo = FooSingleton.GetInstance();
for (;;) {
Foo(foo);
}

И, вуаля, FooSingleton.GetInstance() больше никогда не появляется в профилировщике.

Немного об double checked locking
DCL - это антипаттерн, который норовят использовать все, кто о нем впервые услышал, либо сам до него додумался. Он не работает почти во всех языках программирования, тем самым еще раз подтверждая вред преждевременной оптимизации. Если вам нужен быстрый доступ к синглтону из множества потоков, то кэшируйте указатель на синглтон, возвращаемый синхронизированной фабрикой в thread local storage. Смотрите очень наглядный пример "Fixing Double-Checked Locking using Thread Local Storage" здесь (там, правда, кэшируется не совсем указатель). Но делайте это только в том случае, если профилирование показывает, что доступ к синглтону - действительно узкое место, и другие способы оптимизации не помогают.

Заключение

В следующий раз, когда будете писать либо редактировать циклы, не поленитесь выполнить LICM вручную. Обычно это приводит не только к повышению производительности, но и к улучшению читабельности кода. Продолжение серии этих заметок можно увидеть здесь:

А поскольку впереди предстоит ещё целый длинный сериал заметок на эту тему, самое время уступить место злой самоиронии:

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 в рубрике ПрограммированиеМнения.

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

Следите за комментариями по RSS
  1. Дорогой Игорь!

    1. Оптимизация без конкретных измерений времени выполнения и требуемой памяти проведена не может быть в принципе!!! (дайте хоть один пример с процессором, ос, компилятором и результатами). Например, в JVM где JIT компицяция происходит постоянно (следовательно, оценку можно дать только в реальном приложении) производительность может серьезно пострадать от всяких "умных" предположений, так что для начала пишите лучше "глупый" прямолинейный и естественный код, который потом будет легко оптимизировать, если потребуется. Кстати, "преждевременная оптимизация корень всех зол" (думаю в Microsoft тоже ребята не глупые и CLR много чего умеет)

    2. bar.count может находиться в кеше или регистре процессора, а виртуальная функция (в том числе bar.Count()) может быть встроена, если в текущий момент существует только одна реализация. А цикл может быть развернут... и таких "а" большое количество

    3. Узкое место при вызове synchronized getInstance() побеждается убиранием lazy-init и следовательно synchronized (лучший вариант) или volatile полем в DCL (Java 5+, CLR, иначе она будет многосрадальной:) надо понимать что делаешь). Кстати, JIT вообще может убрать синхронизацию:D Повторюсь, он много чего умеет, только это видно в реальных приложениях, а не bar-baz-foo.

  2. 1. Прочтите еще раз заключение к статье.

    2. bar.count может находиться в регистре процессора, только в одном случае - если компилятор сможет доказать, что LICM оптимизация не изменит логику программы. Обычно компилятор проводит LICM оптимизацию лишь в простейших случаях, когда объект bar недостижим из других мест программы (например, он создан непосредственно перед началом цикла и больше никуда не передается) и значение bar.count не изменяется во время цикла. Во всех остальных случаях компилятор вряд ли будет проводить данную оптимизацию.

    Кэширование данных производится не компилятором, а железом, на котором исполняется код. Что, если железо не поддерживает кэширование данных? Что, если код, исполняющийся в цикле, будет постоянно вытеснять bar.count из кэша данных?

    Вызов виртуальной функции может быть заменен на непосредственный вызов функции только, если интерфейс IBar и функция Foo() не экспортированы. В этом случае компилятору могут быть доступны все реализации IBar и все контексты, из которых происходить вызов функции Foo(), после анализа которых он может произвести данную замену в контекстах, где она осуществима.

    Цикл может быть эффективно развернут только, если значение bar.Count() известно во время компиляции.

    3. Что проще - проводить оптимизацию хитроумного кода, ответственного за создание и менеджмент синглтона либо вручную провести LICM оптимизацию обращений к синглтонам в нескольких hot paths программы?

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

  3. >>3. Что проще - проводить оптимизацию хитроумного кода, ответственного за создание и менеджмент синглтона либо вручную провести LICM оптимизацию обращений к синглтонам в нескольких hot paths программы?

    Ну на на самом деле, уже проще со-оптимизировать GetInstance() один раз и в одном месте, чем бегать по всем местам где идет обращение к этому синглтону и применять LICM (а мест этих может быть очень и очень много). В этом вопросе я поддержу ad. В большом проекте лучше оптимизировать один кусочек кода локализованный в одном месте, чем искать все вызовы этого кусочка, размазанные по всему проекту, и пытаться их оптимизировать. Это заведомо быстрее и надежнее.

  4. Не менее уважаемый ad,

    Обращение к синглтонам нужно оптимизировать лишь в hot spots (см. : http://en.wikipedia.org/wiki/Hot_spot_(computer_programming)), кол-во которых редко превышает один-два на всю программу. Вы не понимаете устройство синглтона.

  5. и всёже, потенциальная проблема находится в компиляторе конкретного языка ищите не в том. если бы функцию bar.Count() компилятор бы гарантированно инлайнил, то данной статьи бы не появилось...

  6. Неа, появилась бы всё-равно :)

    Что, если за bar.Count() скрывается что-нибудь тормозное типа подсчета количества элементов в списке путем прохода по всему списку, либо аналог функции strlen() для динамически созданной строки, либо запрос к базе данных типа SELECT COUNT(*) FROM Table ? Кстати, SQL запрос может быть скрыт от посторонних глаз с помощью модных нынче LINQ ( http://en.wikipedia.org/wiki/Language_Integrated_Query ) или ORM ( http://en.wikipedia.org/wiki/Object-relational_mapping )).

    Если говорить более конкретно, то на примере C/С++ можно сказать, что спецификатор inline там является лишь _рекомендацией_, которую конкретный компилятор может свободно игнорировать. Более того, как показывает практика, в отличие от LICM-оптимизаций, компиляторы умеют инлайнить функции более оптимально, чем это способен сделать человек. (см. en.wikipedia.org/wiki/Inline_function#Problems_with_inline_function#Problems_with_inline_functions)

    Если отвечать ещё ширше, то о вреде inline-спецификатора в ядре Линукс можно почитать тут - http://lwn.net/Articles/82495/ , http://lwn.net/Articles/166172/. Аминь с этим инлайном, короче.

  7. Применять LICM желательно уже на первоначальном этапе написания кода. Я это делаю на автопилоте просто потому, что уже привык так писать код и не могу по другому. просто делайте вынос call за скобки на автомате. Даже если это не даст увеличения производительности, уменьшить её этим, мне кажется, точно не получится.

    Если память не изменяет, сущность описанной в статье оптимизации приводилась ещё в школьной информатике, правда, примеры там были на Бейсике ;-) Конечно, " Loop-invariant Code Motion" звучит намного внушительнее, чем "вынос за скобки". Если бы не прочитал статью, ни за что бы не догадался. А вообще, повторение, как известно, никому ещё не навредило.

    Если же код уже написан и работает, то будет довольно глупо бросаться оптимизировать LICM вслепую, не получив конкретных результатов профайлинга. Прежде чем начинать что-то оптимизировать, нужно знать точно какие места в программе представляют узкое место. Может так статься, что потратив кучу времени вы получите на выходе прирост производительности на 1-5%, к-й не будет никем замечен и оценен по достоинству.

  8. Я вот немного почитал эти комменты и пришел к выводу, что C++ -- это язык, который способен генерировать эпический срач даже там, где упоминается только вскользь. Моё почтение.

  9. Ваш пример крайне не удачен. На первый взгляд, вызов Bar(baz) может изменить значение возвращаемое bar.Count(), иначе зачем делать цикл по i от нуля до bar.Count(), когда можно сделдать ровно наоборот и ничего кэшировать не придется? Ведь переменная цикла, кроме как для подсчета количества итераций, больше не используется. Но тогда перестают работать дальнейшие ваши рассуждения.

    Интересно было бы рассмотреть ситуацию когда Bar генерирует исключение в случае изменения возвращаемого bar.Count() значения.

  10. >Более того, как показывает практика, в отличие от LICM-оптимизаций, компиляторы умеют инлайнить функции более оптимально, чем это способен сделать человек...

    >Аминь с этим инлайном, короче.

    Зря вы так категорично с ним. Из личной практики оптимизации модуля расчета гидродинамики, расставленные по подсказке профайлера __forceinline'ы ускорили производительность... тут забыл, давно дело было, не то на 15, не то на 25%%.

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

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

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

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

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

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


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