Заметки об оптимизации программ. Часть 1: о пользе Loop-invariant Code Motion

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

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

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

void Foo(IBar bar) {
  for (int i = 0; i 

Чтобы компилятор сумел доказать, что в следующем цикле результат вычисления 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 

Уже слышу недовольные голоса - "а что, если 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() больше никогда не появляется в профилировщике.

Заключение

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