понедельник, 30 мая 2016 г.

О сомнительных советах об эффективности

Давать советы об эффективности тех или иных языковых конструкций довольно сложно, поскольку мало в каком языке есть конструкции с заведомо плохой эффективностью. Обычно разные языковые конструкции предназначены для решения хоть и похожих, но несколько разных задач. Например, цикл for в C# работает только с индексируемыми коллекциями, поэтому сравнивать его с циклом foreach в общем случае некорректно.

Но самая главная проблема появляется тогда, когда в совете об эффективности той или иной фичи не объясняется ситуация, в которой этот совет является применимым. Вроде бы, цитату Кнута/Хоара о преждевременной оптимизации знают все, но продолжают давать советы об эффективности в ультимативной форме.

Вот и сегодня мне встретился такой совет, который ретвитнули несколько человек в моей ленте. Совет с самой мудростью, доступной лишь посвященным, но якобы полезной любому .NET разработчику:

Проблема #1. Отсутствие контекста

Как обычно, когда дается совет о производительности, должен быть DISCLAIMER: «Не меняйте свой код исходя из нижележащих советов. Задайте перф-цель, измерьте текущую производительность; если есть проблема запустите профайлер и найдите проблемные участки и в них, возможно, воспользуйтесь моими советами».

Например, совет по поводу LINQ-а валиден. Но ведь он валиден в 0.001% кода. В кишках Розлина LINQ и правда запрещен, как и запрещен он в кишках Решарпера и в критических кусках нового билд-движка, над которым работает моя команда. Но запрещен он не во всех этих проектах, а лишь в нескольких участках, наиболее требовательных к производительности.

Вообще, совет с LINQ-ом особенно плох, поскольку C# не предоставляет средств с соизмеримой выразительностью. Если не особо разобравшийся в теме разработчик начнет следовать этому совету в своем чудо ЫнтЫрпрайз проекте, то он существенно испоганит код, не получив никакой выгоды.

В перф-критикал коде вполне возможно использование кастомных коллекций (что делают каждый из перечисленных мною проектов), поскольку накладные расходы стандартных по памяти будут неприемлемыми. В перф-критикал коде действительно выделение памяти на енумератор может быть проблемным. Но в абсолютном же числе случаев, LINQ будет вполне ОК, и не нужно от него отказываться!

Проблема #2. Совет по поводу лямбд: Do not use lambdas, as they cause allocations

Совет очень плох, поскольку он ну, очень плох. Я могу понять совет подобного рода: «остерегайтесь использования делегатов, поскольку они имеют несколько большую цену вызова чем экземплярный метод и неосторожное их создание может привести к ненужным выделениям памяти. Но, как всегда, пожалуйста, запустите профайлер и убедитесь, что проблема есть».

Я для нашего проекта портировал компилятор TypeScript на C# (пока не скажу «зачем»), и вместе с кодом парсера и сканнера, перевел и код обхода дерева. Метод обхода рекурсивный и он вызывает себя для всех дочерних узлов. При этом, в теле метода был такой код:

public static void WalkTree(Node node, Action<Node> callBack)
{
   
// Создавем функцию обхода
    Action<Node> walker =
ProcessNode;
           
   
// Используем ее внутри!
    walker(node);
}

private static void ProcessNode(Node node)
{           
}

Поскольку Method Group Conversion, который происходит при создании переменной walker всегда приводит к аллокации нового делегата, то профайлер показал, что 10% процентов времени обхода занимает создание делегата. Замена этого кода на лямбда-выражение устранило проблему, поскольку лямбда-выражения могут быть закешированы, если они не захватывают внешнего контекста:

public static void WalkTree(Node node, Action<Node> callBack)
{
   
// Создавем функцию обхода
    Action<Node> walker = (n) =>
ProcessNode(n);
           
   
// Используем ее внутри!
    walker(node);
}

Да, компилятор сможет закешировать лишь незахватывающие лямбда-выражения, но ведь совет говорит, что лямбды плохо – ибо аллокации. А это в общем случае не совсем верно, а в некоторых случаях не верно совсем;)

Проблема #3. Beware of boxing!

И далее:

“A common case for that is passing structs to a method that takes an interface as a parameter. Instead, make the method take the concrete type (by ref) so that it can be passed without allocation.”

Тут есть несколько моментов. Во-первых, мне сложно сказать, насколько статистика верна и что проблема с упаковкой действительно зачастую проявляется именно из-за передачи структур в методы, которые принимают интерфейсы. Во-вторых, фраза не точная, ведь если обобщенный метод принимает интерфейс через ограничение, то упаковки не будет:

public static void NoAllocations<T>(T comparable) where T : IComparable
{ }

 

Ну и в третьих, в совете говорится о передаче структур по ссылке, что может сильно запутать читателя кода, поскольку семантика передачи чего-то по значению и по ссылке очень и очень разные.

Проблема #4. Prefer structs to classes whenever you can.

Этот совет тоже оторван от реальности и является опасным. В предыдущем совете о передаче аргументов метода кратко упоминается передача по ссылке. Хотя объяснения там нет, причина передачи по ссылке заключается в том, что это избавляет от копирования структур при вызове метода, что может быть существенным для структур большого размера.

Но проблема заключается в том, что структуры по своей природе копируются еще во многих других случаях, и даже тогда, когда мы с вами можем и не подозревать, и там, где ключевое слово ref всунуть нельзя:

  • Возвращаемое значение метода
  • Свойство
  • Readonly поле (!!!)

Причем последнее неоднократно являлось причиной лулзов, причем даже среди весьма опытных и даже именитых товарищей (читайте подробнее у Джона Скита - Micro-Optimization: The Surprising Inefficiency Of Readonly Fields). И это я не говорю о том, что вам могут понадобиться мутабельный типы, которые реализовывать в виде структур категорически не рекомендуется.

(да, и тут нужно не забывать, что значимые типы не сильно дружат с ООП, а значит ваш дизайн может серьезно пострадать, если вы ненароком последуете этому совету).

Проблема #5. Ложь и провокации

… которая заключается в последнем совете: “Avoid foreach loops on everything except raw arrays. Each call on a non-array allocates an enumerator. Prefer regular for loops whenever possible.”

Так вот, енумераторы всех коллекций в BCL являются структурами (да, изменяемыми структурами!). Так что foreach на них не будет приводить к аллокациям! Точка!

Foreach с массивами работает быстрее, просто потому что там вообще не используются никакие итераторы. Компилятор C# для цикла foreach с массивами просто берет и генерирует цикл for. Именно поэтому он в микробенчмарке будет быстрее, чем foreach на списке.

К тому же, существует сверх малое число сценариев, когда накладные расходы перебора элементов будут играть хоть какую-то роль по сравнению с телом самого цикла. Если вдруг, этот случай настанет, то нужно оптимизировать именно его, а не переводить все циклы на for!

К тому же, если перебор элементов массива быстрее, чем перебор элементов других коллекций, означает ли это, что нам нужно избегать любых других коллекций кроме массивов? Если да, то как быть, если размер заранее неизвестен?

Вместо заключения

Производительность – тема сложная. Она сложна сам по себе, но она становится еще сложнее, когда разработчике в проекте начинают подходить к ней фанатично. Я как-то немного устал разгребать низкокачественный низкоуровневый код, который был написан разработчиками, слишком буквально следовавшими подобным советам. В результате всегда получался код, который тяжело читать, понимать и развивать. А значит и находить, и исправлять в нем настоящие проблемы с производительностью всегда было очень сложно.

Давайте думать о производительности, но давайте не следовать культу карго и не портить дизайн решения вслепую. Если уж придется его портить, то пусть это будут те самые 2-3% кода, где это действительно нужно.

P.S. Ну и, на всякий случай, это не только я, кому показался этот набор советов сомнительным. Вот мнение ПМ-а .NET-а:

47 комментариев:

  1. У Скита в конце статьи приписочка, что в Roslyn что-то поменяется (он надеется). Поменялось или нет, ты не знаешь?

    ОтветитьУдалить
  2. Вот соглашусь. Писать более-менее вменяемый код с т.з. алгоритмов - нормально. Ну т.е. не надо углубляться и писать свою сортировку каждый раз, но попросту стоит избавиться (точнее, сразу не писать таким образом) от какого-нибудь lazy load в цикле при использовании ORM.
    Но вот заниматься микрооптимизациями вслепую - большое зло. Читать это потом становится трудно. Не говоря о том что у самих разработчиков появляется ощущение что они "всё правильно сделали" и любые замечания будут зачастую восприниматься в штыки с формулировкой "ты что, хочешь чтобы мы писали тормозную гадость?".
    Ну и как обычно - очень часто разработчики плохо на самом деле представляют где и что на самом деле тормозит (потому что это зачастую действительно неочевидно). И тыкаться вслепую вместо использования профайлера довольно глупо.
    У меня был случай, когда понадобилось оптимизировать долгоработающий метод (мог занимать несколько минут, хитрая обработка документов с кучей IO). Но вместо того чтобы кинуться убирать foreach-и, переписывать всё на структуры и избавляться от Linq-а, я сделал наоборот - постарался сделать код максимально понятным. Потом уже профайлер + устранение ставших очевидными косяков помогли ускорить всё это раз в 15 (что было уже приемлемо, хотя можно было и больше выжать). Сохранив функциональность и улучшив читабельность при этом. И, кстати, основной источник тормозов крылся там, где я бы ни в жизнь не подумал его искать - одно из безобидных на вид read-only свойств класса для аутентификации делало вызовы к сервису при каждом вызове. Без профайлера я бы это не нашел.

    ОтветитьУдалить
  3. Обычно в разговорах про избегание преждевременной оптимизации фигурирует и обратная сторона монеты — избегание (преждевременной?) пессимизации. Базовая мысль проста — не надо писать заведомо плохой код. Ну например — конкатенацию строк в цикле. Или использовать list.Count() вместо list.Count.

    У Саттера есть огромный список того, что он относит к пессимизации (правда в рамках C++). И вроде бы понятно, чем пессимизация отличается от преждевеременной оптимизации — в случае пессимизации и хорошее и плохое решения имеют примерно одинаковые характеристики по времени написания и читабельности, то есть написать "плохой" вариант ничем не выгоднее, чем "хороший". Например Саттер относит к пессимизации бездумное использование постфиксного инкремента вместо префиксного — ясно же, что от написания i++ вместо ++i выигрыша нет никакого (кроме случаев, когда реально нужен i++).

    Но когда отходишь от простых примеров, встает вопрос — где грань? На мой взгляд, чтобы правильно принимать такие решения, нужно хорошо понимать, чем приходится платить за каждый из вариантов. И вот поэтому мне особенно не нравятся конкретные советы по эффективности (типа рассматриваемых) — они не включают объяснения скрытых механизмов.

    "Prefer structs to classes whenever you can?" Да вы что? Если мне нужен совет такого рода, то мне вероятно нужно объяснить, когда это - "whenever I can", и почему я могу быть не "can"? Если я не понимаю разницы между классами и структурами, то как я могу определить, когда мне нельзя использовать структуры?

    Или вот рекомендация про GetHashCode, которую Сергей обошел вниманием. Она как будто бы разумная, но лучше бы дать ссылку на описание реализации (например такую: https://habrahabr.ru/post/188038/) и упомянуть, что вообще-то написать хороший GetHashCode может быть ни разу не тривиально.

    ОтветитьУдалить
    Ответы
    1. Да, отличное дополнение. Михаил, спасибо.

      Удалить
    2. С гранью реально сложный вопрос
      Вот ваш пример: "Или использовать list.Count() вместо list.Count."
      А что если лист превратится в IEnumerable? В первом случае не придется переписывать код, а во втором придется.

      Удалить
    3. Михаил, в проектировании и управлении проектами есть такой подход: нужно оценивать стоимость некоторого изменения в случае изменения требований сейчас и когда они произойдут. И если стоимость изменения сейчас значительно ниже изменения потом, то изменение нужно делать заблаговременно (поэтому нужно продумывать ключевые архитектурные решения, поскольку стоимость изменения будет высоким).

      В этом же случае, стоимость изменения сейчас и через год - одна и та же. Если список станет IEnumerable, то код перестанет компилироваться и вы внесете изменение. Но ведь вполне вероятно, что этого никогда и не произйдет (ведь будущее предвидеть мы не можем). И в этом случае мы будем жить с более эффективным и простым решением все время жизни проекта.

      Удалить
    4. Сергей то, что я хотел сказать, только более подробно! Спасибо! С формулировкой об оценки стоимости изменений "потом" не сталкивался, возьму на вооружение.

      Что касается конкретного примера, кроме того, что сказал Сергей, мне вообще не очень нравится эта мотивация - "что если изменится тип переменных?". Как часто в вашем опыте случалось, чтобы тип переменных менялся после "фиксации" кода? В моем - буквально пару раз всего, и в каждом случае, мне было важно просмотреть те места, где код перестал компилироваться - поскольку там как раз изменилась семантика - собственно то, о чем Сергей и сказал.

      Этой же фразой мотивируют и использование var вместо конкретных значений типов переменных сквозь весь код. Не хотелось бы разжигать холивар, но это же полный финиш!

      Кстати, наши с Сергеем комментарии еще раз подчеркивают фразу Михаила - "С гранью реально сложный вопрос".

      Удалить
  4. Чтобы критикуемые советы остались полезными и не вызывали недогования, достаточно в каждом пункте заменить "Не используйте! ..." на "Обратите внимание, что ...".

    ОтветитьУдалить
    Ответы
    1. Ну, не совсем. По поводу структур - это не так, поскольку там нужно талмуд написать нужно, чтобы структуры действительно были эффективными (скрытые копии, которые не видны невооружонным взглядом могут и правда задеть перф). Ну и последний совет сформулирован не корректно (точнее, там сделаны неправильные выводы, которые могут повлиять на восприятие мира).

      Удалить
  5. >>Например, цикл for в C# работает только с индексируемыми коллекциями
    Можно пояснить, что имеется в виду?
    У меня такой код вполне работает
    for(var enumerator = enumerable.GetEnumerator(); enumerator.MoveNext();)
    {
    Console.WriteLine(enumerator.Current);
    }


    И второй пример кривой какой то. В нем вообще убрать walker нужно и тупо вызвать ProccessNode(node).

    ОтветитьУдалить
    Ответы
    1. >>>> Например, цикл for в C# работает только с индексируемыми коллекциями
      >>Можно пояснить, что имеется в виду?
      Ну, нельзя циклом for пройтись по стеку или линкд-листу. А приведенный пример с енумератором абсолютно ничем не отличается от foreach-а с точки зрения эффективности.

      По поводу второго примера: там есть коммент, что делается много всего. Он очень сильно упрощен. Просто я показал, что если на каждой итерации будет method group conversion, то приводит к тонне аллокаций, а вот использование лямбда-выражения уберет их.

      Удалить
  6. Да таких советов полн интернет, а джуниоры часто не умеют фильтровать

    ОтветитьУдалить
  7. Думаю, что пост был исключительно холивара ради. Ну так - буря в стакане воды. Как по-мне на это никто не поведется вообще. Если же говорить о действительно time critical участках кода, то на мой взгляд надо разговаривать о выборе сборщика мусора и его режиме. В общем, без контекста - это так - пук в воду.

    ОтветитьУдалить
    Ответы
    1. Жень, я бы с тобой, возможно, согласился бы, если бы не был свидетелем следования подобным советам в своей собственной команде.

      Поверь, радости мало, когда на ревью тебе рекомендуют отказаться от LINQ-а, поскольку он не очень эффективный и этот же человек городит трехэтажные for-ы, только чтобы им не пользоваться. А потом он же будет тебе доказывать, что as быстрее is-а или наоборот, потому что кто-то ему пару лет назад сказал об этом

      Так что это совсем не буря:)

      Удалить
  8. Это 3.14пец, товарищи. Таким советчикам надо минимум на год запрещать писать.

    >Как по-мне на это никто не поведется вообще.
    Уверен, что куча людей поведётся. К сожалению, я сам слышал такие советы от вроде бы опытных разработчиков :(

    ОтветитьУдалить
  9. Насколько я помню, for быстрее еще и потому, что часто позволяет JIT-у вынести index range checking вне цикла таким образом, что при доступе к каждому элементу они не происходят. Ну и в базовом случае foreach над массивом и List'ом, кажется, генерировал идентичный IL/native code. Для других IEnumerable это не так, конечно.

    ОтветитьУдалить
    Ответы
    1. Я не уверен, что проверка выхода за границы работает, но это один из вариантов

      З.Ы. foreach другой только для массива, для листа он не оптимизированный. А вот для массива код аналогичный коду цикла for. (потому что CLR "знает" только о работе с массивами).

      Удалить
  10. Этот комментарий был удален автором.

    ОтветитьУдалить
  11. А я вот на счет того, чтобы по возможности избегать Linq соглашусь. Может он и хорош в плане сокращения кода и удобности восприятия для нечастых операций, но во всех случаях что я переписывал Linq на обычные варианты алгоритмов давали прирост производительности от нескольких десятков % до нескольких порядков!!

    ОтветитьУдалить
    Ответы
    1. Я уверен, что прибавка в производительности на порядки была обусловлена тем, что поменялась сложность алгоритма. Ну и такой вопрос: а в случае ускорения алгоритма на проценты, насколько изменилась работа приложения. Т.е. насколько это изменение в производительности было выгодным/видным пользователю и насколько ухушдилась сопровождаемость?;)

      Удалить
    2. Этот комментарий был удален автором.

      Удалить
    3. Я все примеры не упомню уже. Вот пример последней из правок.
      Исходник
      https://github.com/staff0rd/polygon-map-unity/blob/master/demo/Assets/Map/Graph.cs
      С 207 по 216 строку алгоритм выборки узла
      переписан на обычный for с прямым сравнением ключа и индекса сократило общее время отработки построения карты с 550 до 400 млс, а это только одно место. Как вы понимаете на сопровождении кода это не отразилось ровным счетом никак (1 строчка запроса заменилась циклом и сравнением). В общей сложности внеся еще некоторые правки я ускорил общее построение в 4 раза.
      А потом в итоге плюнул и написал свою менее универсальную, но более прозрачную и простую реализацию построения подобной карты со схожим функционалом где нет ни одного LINQ запроса которая отрабатывает всего за 14 млс. Естественно что дело не только в LINQ, но в правильных алгоритмах.

      Удалить
    4. Судя по данному коду (детально не вчитывался), надо было вообще заморочиться на тему Dictionary для _cornerMap с Key, для того чтобы избегать вложенных циклов и время поиска там должно стать околонулевым. Но это, конечно, очень беглый взгляд и надо проверять/смотреть детальнее.

      Удалить
  12. В случае с foreach. Его я стараюсь так же избегать по возможности. У меня есть собственные реализации Dictionary и других хеш коллекций и когда мне нужно перебрать все элементы, я просто возвращаю массив ключей, значений или пар и перебираю его for-ом. Этот перебор вместе с выборкой и созданием нужного массива отрабатывает в 2-2,5 раза быстрее простого foreach перебора.

    ОтветитьУдалить
    Ответы
    1. У меня есть два варианта: вы работаете над очень специфическим проектом или вы делаете что-то не то.

      Я сейчас занимаюсь тулой, которая является тулой системного уровня и в ней я не вижу выгод от подобных микрооптимизаций.

      З.Ы. Я был бы рад увидеть пруф последнего заявления, поскольку он мне кажется очень подозрительным и не логичным (если только вы не меряете время самого перебора, без учета работы тела цикла).

      Удалить
    2. Этот комментарий был удален автором.

      Удалить
    3. Этот комментарий был удален автором.

      Удалить
    4. Пруф в открытом доступе, пользуйтесь коль сочтете полезным.
      https://github.com/LuchunPen/Fast-Hash-Collection

      И не совсем понятно, при чем тут работа тела цикла. Я соглашусь, что нет никакой разницы что использовать foreach или for или вообще собственную в 10 раз более медленную реализацию, если тело цикла отрабатывает со скорость 100 операций в секунду. Но на быстрых одно-двух строчных операциях прирост заметен.

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

      Удалить
    5. Спасибо, посмотрю на код.
      Ну, смысл в том, что тело цикла выполняется заведомо значительно дольше, что делает подобную оптимизацию видимой лишь в бенчмарках, кои бывают чаще вредными, чем полезными.

      Удалить
    6. А что мешает обходить возвращаемый массивы форичем? Мерили? Прозводительность сильно хуже фора!?

      Удалить
    7. Этот комментарий был удален автором.

      Удалить
    8. Я лишь высказал мнение, что стараюсь его избегать исходя из своих собственных тестов и тех неэффективных реализации IEnumerators, что я видел и не в коем случае не настаиваю придерживаться его.

      Не везде есть возможность избежать его использования, а в некоторых случаях действительно проще использовать foreach.

      В качестве дополнения, for банально удобнее при отладке: допустим у вас есть цикл и в теле цикла с определенной вероятностью вылетают ошибки. Для того чтобы понять вероятное место и стабильность вылетов в foreach вам необходимо будет вводить дополнительную переменную текущей итерации - мелочь, но после отладки про нее можно банально забыть и этот баласт так и будет висеть в теле, что нарушит чистоту кода.
      А если вам нужно добавить дополнительное условие итерации - будете еще тонну условий в тело пихать ?
      А если вдруг вас осенит новая идея и вы решите изменить порядок итерации на обратный или с середины - будете переписывать на for или создавать кучу выражений :)?

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

      Удалить
    9. @А что мешает обходить возвращаемый массивы форичем? Мерили? Прозводительность сильно хуже фора!?@
      А еще лучше давайте представим себе эту ситуацию:
      Я возвращаю массив структур. Для того, чтобы вернуть я делаю его первоначальный перебор а значит копию, затем я foreach (struct str in structsArray) { } снова копирую ее в каждой итерации.

      Представим себе другую ситуацию:
      Я имею массив структур размером 30 байт (ну мало ли вот так получилось, что структуры такие большие, см. к примеру исходники Entry в стандартной реализации Dictionary) и мне нужно провести чтение переменной из каждой и некую простую операцию:
      foreach(struct str in structArray) { делаем что то } я снова каждую итерацию копирую структуру, а если их миллион - получу 30 мб memory traffic.
      А for-ом, поскольку чтение идет из массива лишних копий создаваться не будет.

      Удалить
  13. Этот комментарий был удален автором.

    ОтветитьУдалить
  14. Пожелание. Внесите пожалуйста возможность редактирования сообщения, а то появляется мысль, а чтоб дополнить приходится удалять и отправлять новый комментарий :).

    ОтветитьУдалить
    Ответы
    1. Знал бы как это сделать:(. Я чего-то думаю, что эта фича должна быть доступна в движке блоггера, хотя может быть это где-то настроить и можно...

      Удалить
  15. Сергей, поясни пожалуйста, зачем в проблеме #2 нужно вообще использовать делегат, почему нельзя напрямую вызывать ProcessNode?

    ОтветитьУдалить
    Ответы
    1. Максим, пример этот синтетический. В оригинале этот же делегат потом передается в рекурсивный вызов, так что он нужен именно в виде делегата.

      Удалить
  16. Ради интереса проверил: разницы между 'ProcessNode' как method group и '(n) => ProcessNode(n)' нет никакой, в обоих случаях компилятор возвращает один и тот же объект.
    Тестировал вот так: https://gist.github.com/ivan-danilov/70f09edada47a28d86bab5f35ec6db2b на Розлине, .NET 4.6.1. Release/Debug и наличие или отсутствие дебаггера ничего не меняют.
    ЧЯДНТ?

    ОтветитьУдалить
    Ответы
    1. Ага, все, разобрался. Забыл, что '==' для делегатов переопределен. Заменил на 'Object.ReferenceEquals' - получил разное.

      Удалить