Реклама в Telegram-каналах DzikPic и dev.by теперь дешевле. Узнать подробности 👨🏻‍💻
Support us

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

Оставить комментарий
Заметки об оптимизации программ. Часть 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 вручную. Обычно это приводит не только к повышению производительности, но и к улучшению читабельности кода.
Новый рекламный формат в наших телеграм-каналах.

Купить 500 символов за $150

Читайте также
12 онлайн-курсов по языку Java для новичков и профессионалов (август, 2023)
12 онлайн-курсов по языку Java для новичков и профессионалов (август, 2023)
12 онлайн-курсов по языку Java для новичков и профессионалов (август, 2023)
Java по-прежнему входит в список самых популярных языков программирования. Вместе с Digitaldefynd мы составили список курсов по Java, которые подойдут как новичкам, так и людям с опытом программирования, чтобы освоить этот востребованный язык.
Microsoft запустила обучающий сайт по Java
Microsoft запустила обучающий сайт по Java
Microsoft запустила обучающий сайт по Java
1 комментарий
Как оплачиваются самые популярные языки GitHub и какой прогноз
Как оплачиваются самые популярные языки GitHub и какой прогноз
Как оплачиваются самые популярные языки GitHub и какой прогноз
TIOBE: Java стремительно сдаёт позиции другим языкам
TIOBE: Java стремительно сдаёт позиции другим языкам
TIOBE: Java стремительно сдаёт позиции другим языкам
7 комментариев

Хотите сообщить важную новость? Пишите в Telegram-бот

Главные события и полезные ссылки в нашем Telegram-канале

Обсуждение
Комментируйте без ограничений

Релоцировались? Теперь вы можете комментировать без верификации аккаунта.

Комментариев пока нет.