html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Заметки об оптимизации: О пользе 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
Одноклассники
Мой Мир

материал с blogerator.ru

5

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • pleshner
          • домен blogerator.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции