среда, 20 февраля 2013 г.

MVP Summit. День 1. Об эффективности

В большинстве приложений оптимизации, о которых я писал в прошлый раз, совершенно неинтересны: будет ли экземпляр делегата создаваться каждый раз или он будет создаваться лишь первый раз и сохраняться в кэше. Но в таких проектах, как РеШарпер, Visual Studio или компилятор, этому придается важное значение, поэтому не удивительно, что во многих сессиях вопросы эффективности так или иначе затрагиваются.

Я не могу сказать, что такое же внимание к эффективности требуется для “обычных” проектов, тем не менее, понимание того, что происходит за кулисами может помочь тогда, когда в этом появится необходимость. Вот на парочке подобных примеров я и хочу остановиться.

Ненужные аллокации

Управляемая среда, которой является платформа .NET, славится невероятной эффективностью выделения памяти. Скорость выделения памяти в управляемой куче соизмерима с выделением памяти на стеке, да и алгоритмы этих аллокаций весьма похожи: для этого достаточно инкрементировать один указатель (ну и выделить память под новый сегмент, если старый закончился). Этот процесс значительно более эффективный, по сравнению с выделением памяти в неуправляемой куче, так почему нам нужно беспокоиться о ненужных аллокациях?

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

Неявная упаковка

Предположим, у нас есть такой простой класс:

enum EmployeeType
{ 
    Worker, Manager, }
class Employee
{
   
public int Id { get; set
; }
   
public EmployeeType EmployeeType { get; set; } }

Ну и у него есть пара дополнительных методов, типа ToString() и GetHashCode(), реализованных следующим образом:

public override string ToString()
{ 
   
return Id.ToString() + ' '
+ EmployeeType.ToString(); } public override int GetHashCode() {
   
return Id.GetHashCode() ^ EmployeeType.GetHashCode(); }

Есть ли здесь ненужные аллокации? Да, причем в каждом методе!

В методе ToString() происходит создание двух объектов в куче. Конкатенация строк, приведенная в методе ToString() является лишь синтаксическим сахаром для вызова метода String.Concat(object, object, object); а поскольку символ пробела (' ') является экземпляром значимого типа Char, то первая упаковка происходит здесь. Второе выделение памяти более хитрое и связано с тем, что в методе ToString() происходит вызов методов EmployeeType.ToString(), который реализован в типе System.Enum, а раз так, то для вызова правильной реализации нам нужно воспользоваться таблицей виртуальных функций, существующей лишь в упакованной версии перечисления.

Аналогичная проблема существует и в методе GetHashCode(), в котором вызывается EmployeeType.GetHashCode(), вызов которого приводит к упаковке экземпляра перечисления.

ПРИМЕЧАНИЕ
Я не знаю другого места в языке C# при котором выделение памяти было бы столь неочевидным. Ведь на самом деле правила еще более сложные и упаковка будет в следующих случаях: (1) вызов невиртуального метода GetType(), (2) вызов непереопределенного виртуального метода значимого типа (структуры), (3) вызовы методов ToString() и GetHashCode() перечисления.
Самым простым правилом, которое приходит в голову, является следующее: любые вызовы методов, реализованных в типах System.ValueType или System.Enum приводят к упаковке, поскольку эти типы сами по себе являются ссылочными!

UPDATE Для упрощения этого понимания я нарисовал рисунок.

BoxingStuff

В общем так: если “тело метода” определено в верхней части рисунка – упаковка будет, иначе – нет!.

Решаются данные проблемы следующим образом:

public override string ToString()
{ 
   
// Используем строку " ", а не символ ' '     return Id.ToString() + " "
+ EmployeeType.ToString(); } public override int GetHashCode() {
   
// Приводим к int (или к long, если нижележащий тип перечисления     // это long) и вызываем на нем GetHashCode()     return Id.GetHashCode() ^ ((int)EmployeeType).GetHashCode(); }

К сожалению, от одной упаковки в методе ToString() (при вызове EmployeeType.ToString()), избавиться никак не получится (не реализуя подобный метод руками в своем классе).

LINQ

LINQ – это один из самых лучших инструментов в языке C#; эта штука позволяет повысить декларативность кода, делая его более понятным и читабельным. Но не будет секретом и то, что с точки зрения потребления памяти это может быть далеко не лучшим вариантом (да, в подавляющем большинстве случаев разницы не будет, но в некоторых случаях она может оказаться существенной).

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

private List<Employee> _employees = new List<Employee>();
public Employee FindEmployee(int id)
{ 
   
return _employees.FirstOrDefault(e => e.Id == id); }

Я могу насчитать 3: 2 аллокации на анонимный метод с замыканием и еще одна – для перебора элементов. Лямбда-выражение выворачивается в создание экземпляра объекта-замыкания и экземпляра делегата (мы говорили об этом в прошлый раз и ранее, до этого, поэтому останавливаться подробнее я не буду). Но насколько очевидно (или неочевидно), что при вызове метода FirstOrDefault мы получим еще одну аллокацию?:

LINQ – это набор методов расширения, расширяющих интерфейс IEnumerable of T, который выглядит следующим образом:

public interface IEnumerable<T> : IEnumerable
{ 
   
IEnumerator<T> GetEnumerator(); }

Я уже неоднократно писал о том, что итераторы всех типов BCL являются изменяемыми структурами; иногда это может приводить к отстрелу конечностей, но эта жертва принесена в угоду эффективности. Перебирая элементы списка циклом foreach мы не получим выделение памяти, благодаря “утиной типизации”, но эта магия исчезает, когда мы приведем List of T к типу IEnumerable of T и вызовем GetEnumerator() через интерфейс (мы получим упаковку итератора).

Кстати, интересно, что метод Where оптимизирован таким образом, чтобы использовать итераторы конкретных типов коллекций, это явно нарушает все принципы проектирования (OCP, SRP, LSP), но это вполне нормально, когда речь заходит о столь распространенных библиотеках.

ПРИМЕЧАНИЕ
Кстати, именно поэтому при рассмотрении 8 ошибок выяснилось, что метод FirstOrDefault(predicate) работает медленнее, чем пара Where(predicate).FirstOrDefault().

Кэширование task-ов

Возможно кто-то из вас слышал о том, что в Java есть довольно забавная оптимизация, которая заключается в кэшировании экземпляров типа Integer со значениями от –10 до 10. Поскольку Integer – это что-то вроде ссылочного типа, то вызывая код вида: object.ReferenceEquals(new Integer(1), new Integer(1)) мы получим True.

Так вот, в языке C# есть подобная оптимизация, но в контексте асинхронных методов. Вот простой пример, демонстрирующий эту стратегию:

static async Task<int> SimpleAsyncMethod(int i)
{ 
   
return
i; } var cachedValues =
   
from n in Enumerable
.Range(-100, 200)
   
let
t1 = SimpleAsyncMethod(n)
   
let
t2 = SimpleAsyncMethod(n)
   
let cached = object
.ReferenceEquals(t1, t2)
   
where
cached
   
select
n; Console.WriteLine("Cached values: {0}",
   
string.Join(", ", cachedValues));

Метод SimpleAsyncMethod всего лишь возвращает значение, которое автоматически “заворачивается” компилятором в Task of T. Затем, с помощью LINQ запроса я вызываю метод дважды для каждого целого числа в диапазоне от –100 до 100 и получаю только те значения, для которых возвращается та же самая задача. В результате выполнения этого кода мы увидим следующее: “Cached values: –1, 0, 1, 2, 3, 4, 5, 6, 7, 8”.

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

-----------------

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

21 комментарий:

  1. я вот этой фразы, если честно, совсем не понял:
    "любые вызовы методов, реализованных в типах System.ValueType или System.Enum приводят к упаковке, поскольку эти типы сами по себе являются ссылочными". можете объяснить более развернуто? Спасибо.

    ОтветитьУдалить
  2. Про Card Tables забыл. Аллокация бывает ведь не ради самой аллокации.

    ОтветитьУдалить
  3. @Alexander попробуйте запустить следующий код и посмотреть что выведет на консоль

    int? t = 5;
    Console.WriteLine (t.GetType() == typeof(int?));

    Если посмотреть созданый IL, то можно увидеть box операцию. Упаковка так-же будет присутствовать, будь наша переменая типа int. Думаю Сергей сможет обьяснит глубже почему именно так происходит и почему среде выполнения нужно привести переменую к типу, в котором определена виртуальная функция, но в таком поведении можно удостоверится простыми примерами.

    p.s. при упаковке Nullable в коде сверху Nullable преобразуется в T и упаковывается, именно поэтому выводит false, т.к. сам тип уже int, a не Nullable

    ОтветитьУдалить
  4. Речь идет не только о Nullable типах, а, цитирую о System.ValueType. Я сейчас попробую поэксперементировать...

    ОтветитьУдалить
  5. я правильно понимаю, что вот такое, например
    int i = 10;
    i.GetHashCode();


    вызовет операцию упаковки?

    ОтветитьУдалить
  6. Нет, неправильно. Боксинг будет при вызове НЕвиртуальных методов, унаследованных от референсных предков. GetType - как раз такой. Он из System::Object. А GetHashCode - виртуальный и переопределенный в System::Int32. Поэтому при его вызове боксинга не будет.

    ОтветитьУдалить
  7. @Alexander GetHashCode определен в классе Int32 (декомпилятор это хорошо покажет). Так-же в Int32 определен ToString, поэтому при их вызове упаковка происходить не будет. Только GetType приведет к упаковке в случае Int32, так как его нет в Int32 (определен на уровне Object).

    Сергей писал, что если вы определяете enum Foo и вызываете у экземпляра этого типа тот-же GetHashCode, то будет произведена упаковка, т.к. GetHashCode определен на уровне ValueType, который является классом, не структурой.

    ОтветитьУдалить
  8. 1: Int32 какбе не совсем класс:
    public struct Int32
    (воспользовался декомпилятором ;) )
    Сергей писал, что(цитирую еще раз буквально):"любые вызовы методов, реализованных в типах System.ValueType приводят к упаковке". Так вот: Int32 - ValueType, GetHashCode - любой метод, упаковки не происходит. На месте Сергея я был бы поаккуратнее с определениями.

    ОтветитьУдалить
  9. @Alexander: я осторожен, как сапер!
    (я сейчас нарисую диаграмму классов с пояснениями, а пока так расскажу).

    Вы путаете value types (семейство типов, к которым относится Int32) и System.ValueType - абстрактный тип из .NET фреймворка, от которого (явно или неявно) унаследованы все value types.

    Так вот, System.ValueType - это не структура, это класс, поэтому если для экземпляра типа Int32 вызвать метод GetType(), реализация которого находится в типе System.Object, то произоуйдет упаковка.

    Если для кастомной структуры (вашей личной), не переопределить метод GetHashCode(), то будет использована реализация, которая располагается в типе System.ValueType, что и приветет к упаковке.

    int i = 10;
    i.GetHashCode();

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

    В общем, value type != System.ValueType и их не следует трактовать одинаково. Когда речь идет о втором, то я всегда добавляю пространство имен System, или, как минимум, пишу их слитно.

    ОтветитьУдалить
  10. @Андрей: card table - это деталь реализации, которая налагает постоянные расходы, от которых мы избавиться не можем. В данном случае я хотел показать неявные выделения, от которых избавиться все же в наших силах.

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

    ОтветитьУдалить
  11. Кстати, в статье упоминаются правила упаковки (1), (2) и (3), так вот (3) - полне себе подпункт (2). Но это так, придирка :)

    ОтветитьУдалить
  12. Ну да, эти тэйблы - часть оверхеда, про который все умалчивают, когда говорят об аллокации. Создается ложное ощущение, что .NET быстрее чистых плюсов работает по части памяти :)

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

    ОтветитьУдалить
  14. @Alexander Int32 какбе не совсем класс да конечно, все типы наследованые от ValueType - значимые типы, моя вина, опечатался. Надеюсь в свете всех вышесказаных комментариев ситуация прояснилась. Остался один вопрос Сергею - следующий код:

    new Foo().ToString();

    приводит к упаковке, если Foo это enum, но не в случае если Foo это struct. В последнем случае использывается IL инструкция constrained. Как я понял из msdn помогает избежать упаковки путем единого доступа к виртуальным методам структур и классов.

    ОтветитьУдалить
  15. @Alexander: я добавил рисунок, посмотрите, насколько теперь стало понятнее.

    ОтветитьУдалить
  16. Мне кажется, проще показать логику этого, а она проста, как 3 копейки: имея на руках тот факт, что любому инстансному методу передается this соответствующего типа, то все остальное просто является следствием этого.

    ОтветитьУдалить
  17. ага. в целом вы правы, но я бы таки это правило как-то разжевал бы.

    ОтветитьУдалить
  18. 2Ivanov Ilya: http://msdn.microsoft.com/en-us/library/system.reflection.emit.opcodes.constrained.aspx

    Если внимательно прочитать, то можно найти вот такое: If thisType is a value type and thisType does not implement method then ptr is dereferenced, boxed, and passed as the 'this' pointer to the callvirt method instruction.

    Все равно есть боксинг, иначе и быть не может просто потому, что метод, определенный в референсном типе будет просить this своего же типа, семантика меняться НЕ БУДЕТ

    ОтветитьУдалить
  19. Еще кое-что заметил: в Джаве кеширование не только int-врапперов, но и short, и byte, и long-врапперов. Диапазон там не от -10 до 10, а от -128 до 127, причем, верхняя планка регулируется сиспропертями наподобие java.lang.Integer.IntegerCache.high

    ОтветитьУдалить
  20. И таки int(и другие)-врапперы есть полноценные ссылочные типы, которые служат обертками над примитивами типа int, log и т.д. А у примитивов название говорит само за себя - это просто ячейки памяти, у них нет методов, конструкторов и проч.

    ОтветитьУдалить
  21. А все-таки она вертится. Сорри, не смог удержаться. :). Интересно, что ломаем копья здесь по темам, которые вряд ли пригодятся при прикладном проектировании. Напоминает, как ценители вина разговаривают о каких-то особых винах. А остальные - их просто пьют :)

    ОтветитьУдалить