Навигация
· XNA FAQ
· С чего начать
· Конкурсы
· Обратная связь
· XNA Блоги
Сейчас на сайте
· Гостей: 2

· Пользователей: 0

· Всего пользователей: 3,684
· Новый пользователь: headron
Последние фото
Эх, чуть не проспал закрытие.
Эх, чуть не проспал ...
Альбом: XNA Engine

GB
GB
Альбом: XNA Engine

South Park Coon & Friends
South Park Coon & Fr...
Альбом: XNA Games

Блоги
yavshoke
» XboxOne - интерес...
dampirik
» Push уведомления ...
dampirik
» Реклама,статистик...
Chort
» XNA и StartCoroutine
Chort
» Curve Class
dampirik
» Реклама, статисти...
dampirik
» Увеличение скорос...
dampirik
» Реклама, статисти...
general
» Распаковка DxtCom...
general
» Как работать с XN...
Поддержка
microsoft.com
1gb.ru - Дом для вашего сайта
Статистика посещений:

Использование перечисления в качестве ключа для словаря
Неявная генерация объектов в процессе работы .NET приложения является неоспоримым злом, а в процессе работы .NET приложения, которые по совместительству еще и являются играми реального времени, такое поведение и вообще смерти подобно. Сам по себе вызов сборки мусора к краху приложения конечно ни в коем случае не приведет, но желательно, чтобы их в процессе жизни нашего приложения происходило, как можно меньше. В данной статье я хочу рассмотреть довольно частый прием, который применяется программистами .NET – использование перечисления (enum) в качестве ключа для объекта словаря (Dictionary). Во-первых, применение данного метода удобно, объекты одного типа собраны в один контейнер и доступ к ним осуществляется фактически по имени (значение перечисления), IntelliSince тоже вносит свою немалую лепту в написании кода при таком подходе. Во-вторых, данный подход помогает избежать ошибок, в отличие от применения скажем string в качестве ключа.

Но как всегда найдется ложка с дегтем, нависающая над нашей бочкой с прополисом. Использование перечисления, как ключа для словаря ведет к генерации мусора, в бизнес приложении можно конечно забить на сей факт (что конечно тоже нежелательно), но в играх XNA, где фреймрейт показатель довольно значительный с этим мериться никак нельзя.
В общих чертах суть проблемы Вы можете посмотреть в докладе Ивана Андреева на сайте www.techdays.ru под названием «XNA: Производительность». Вот слайд из его презентации
Images: XNASpeed.jpg
Если вкратце, то при использовании в качестве ключа ссылочного типа мы ограничиваемся только вызовом метода GetHashCode и по вычисленному хэшу получаем значение из HashTable, то при использовании в качестве ключа типа значение, для получения хэша нам приходится неявно приводить значение в ссылочный тип, в нашем случае – это object и уже затем вычислять хэш. А этот объект отбрасывается в виде мусора за ненадобностью, при накоплении достаточного количества таких мусорных объектов будет инициирована сборка, которая сама по себе является не легкой операцией. В своем докладе Иван обошел это применением кэширования, он просто закэшировал ссылку на объект текстуры, которую до этого получал из словаря по ключу для каждого объекта звезды.

Теперь давайте более подробно разберемся в сложившейся ситуации, а точнее покопаемся внутри объекта Dictionary.
К моему удивлению reflectior не показал мне объекта Dictionary в пространстве имен System.Collections.Generic, где он по теории обитает, поэтому я взял исходники .NET Framework с сайта Microsoft.

Итак, что у нас происходит, когда мы объявляем и инициализируем словарь?
public static Dictionary<TextureEnum, Texture2D> Textures = new Dictionary<TextureEnum, Texture2D>();

 

Не параметризированный конструктор вызывает свою реализацию, но уже с двумя параметрами, передавая 0 и null.
public Dictionary(): this(0, null) {}

 

В которой уже происходит нечто интересное
public Dictionary(int capacity, IEqualityComparer<TKey> comparer) {
            if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity); 
            if (capacity > 0) Initialize(capacity); 
            if (comparer == null) comparer = EqualityComparer<TKey>.Default;
            this.comparer = comparer; 
        }

 

Во-первых, передается количество элементов словаря, под которое будет сразу же выделена память, но более интересен для нас сейчас – это объект comparer. Если мы нечего не скармливаем в конструктор, то будет создан экземпляр стандартной реализации EqualityComparer<TKey>.Default;  Не буду вдаваться в подробности его реализации, но если пройтись по коду, то станет видно, что в случае с перечислениями он инициализируется реализацией internal class ObjectEqualityComparer<T>: EqualityComparer<T>. Собственно данный класс и подписывает нам приговор при использовании перечисления, а точнее его универсальность, в связке со спецификой реализации перечислений дают просто убийственный эффект в производительности.

Нас в нем интересует два метода
public override bool Equals(T x, T y) {
            if (x != null) { 
                if (y != null) return x.Equals(y);
                return false; 
            } 
            if (y != null) return false;
            return true; 
        }
public override int GetHashCode(T obj) {
            if (obj == null) return 0; 
            return obj.GetHashCode();
        }

 

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

public override int GetHashCode()
{
    return this.GetValue().GetHashCode();
}
 
private object GetValue()
{
    return this.InternalGetValue();
}
 
[MethodImpl(MethodImplOptions.InternalCall)]
private extern object InternalGetValue();
 
[MethodImpl(MethodImplOptions.InternalCall)]
public override extern bool Equals(object obj);

 

Метод GetValue() возвращает нам object, по которому у нас и высчитывается хэш, по окончанию расчетов он будут отброшен, как мусорный объект.

Но к счастью разработчики .NET дали нам возможность передавать в словарь свой класс для сравнения ключей, а природа наделила нас мозгом. Мы можем написать свою реализацию для сравнения типов значений, реализовав интерфейс IEqualityComparer<T> и передав его в конструктор словаря.

За основу для кода я взял исходники Ивана Андреева из его доклада, который упоминался выше.

Простейшая реализация класса для сравнения значений ключей для перечисления текстур:
    public class TextureEqualityComparer : IEqualityComparer<TextureEnum>
    {
        private static TextureEqualityComparer defaultInstance;
        public static TextureEqualityComparer Default
        {
            get
            {
                if (defaultInstance == null)
                    defaultInstance = new TextureEqualityComparer();
                return defaultInstance;
            }
        }
 
        public bool Equals(TextureEnum x, TextureEnum y)
        {
            return x == y;
        }
 
        public int GetHashCode(TextureEnum obj)
        {
            return (int)obj;
        }
    }

 

Если кому-нибуть непонятно, что мы этим добились, ведь у нас все так-же продолжает вызываться GetHashCode, поясняю, реализация методов GetHashCode и Equals у типов значений (наследованные от ValueType), в частности наше перечисление TextureEnum отличается от реализации у объектов ссылочного типа, которые напрямую наследуют от object, в них учитывается именно значение, которое находится в объекте.

Далее мы просто скармливаем наш класс для сравнения в конструктор словаря.
Textures = new Dictionary<TextureEnum, Texture2D>(TextureEqualityComparer.Default);

 

Ну говорить я тут могу все что угодно, но неплохо бы провести тестирование…


Создадим простое консольное приложение
using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
 
namespace TestDictionaryEnum
{
    class Program
    {
        public enum TextureEnum
        {
            Star,
            Ship,
            Asteroid,
            Bullet,
            Enemy,
            Logo
        }
 
        static void Main(string[] args)
        {
            // Создаем словарь
            Dictionary<TextureEnum, string> testDictionary = new Dictionary<TextureEnum, string>();
 
            // Заполняем
            testDictionary.Add(TextureEnum.Asteroid, TextureEnum.Asteroid.ToString());
            testDictionary.Add(TextureEnum.Bullet, TextureEnum.Bullet.ToString());
            testDictionary.Add(TextureEnum.Enemy, TextureEnum.Enemy.ToString());
            testDictionary.Add(TextureEnum.Logo, TextureEnum.Logo.ToString());
            testDictionary.Add(TextureEnum.Ship, TextureEnum.Ship.ToString());
            testDictionary.Add(TextureEnum.Star, TextureEnum.Star.ToString());
 
            const int counter = 10000000; // кол-во итераций 
            Stopwatch timer = Stopwatch.StartNew();
            string testData;
            for (int i = 0; i < counter; i++)
            {
                testData = testDictionary[TextureEnum.Enemy]; // получаем наше значение
            }
 
            TimeSpan timeSpan = timer.Elapsed;
 
            // Вывод статистики
            Console.WriteLine("Затраченное время {0}", timeSpan);
            Console.WriteLine("Вызовов сборщика мусора \r\nПоколение 0 - {0} \r\nПоколение 1 - {1} \r\nПоколение 2 - {2}", 
                GC.CollectionCount(0), GC.CollectionCount(1), GC.CollectionCount(2));
 
            Console.ReadLine();
        }
    }
}

 


При запуске приложения в среднем мне на моем «железе» выдает:
Затраченное время 00:00:02.3281013
Вызовов сборщика мусора
Поколение 0 - 458
Поколение 1 - 1
Поколение 20

 

Значения более менее средние и от количества запусков значения меняются не очень сильно.
Теперь допишем класс для сравнения и пропишем его экземпляр в конструктор нашего словаря:

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
 
namespace TestDictionaryEnum
{
    class Program
    {
        public class TextureEqualityComparer : IEqualityComparer<TextureEnum>
        {
            private static TextureEqualityComparer defaultInstance;
            public static TextureEqualityComparer Default
            {
                get
                {
                    if (defaultInstance == null)
                        defaultInstance = new TextureEqualityComparer();
                    return defaultInstance;
                }
            }
 
            public bool Equals(TextureEnum x, TextureEnum y)
            {
                return x == y;
            }
 
            public int GetHashCode(TextureEnum obj)
            {
                return (int)obj;
            }
        }
 
        public enum TextureEnum
        {
            Star,
            Ship,
            Asteroid,
            Bullet,
            Enemy,
            Logo
        }
 
        static void Main(string[] args)
        {
            // Создаем словарь
            Dictionary<TextureEnum, string> testDictionary = new Dictionary<TextureEnum, string>(TextureEqualityComparer.Default);
 
            // Заполняем
            testDictionary.Add(TextureEnum.Asteroid, TextureEnum.Asteroid.ToString());
            testDictionary.Add(TextureEnum.Bullet, TextureEnum.Bullet.ToString());
            testDictionary.Add(TextureEnum.Enemy, TextureEnum.Enemy.ToString());
            testDictionary.Add(TextureEnum.Logo, TextureEnum.Logo.ToString());
            testDictionary.Add(TextureEnum.Ship, TextureEnum.Ship.ToString());
            testDictionary.Add(TextureEnum.Star, TextureEnum.Star.ToString());
 
            const int counter = 10000000; // кол-во итераций 
            Stopwatch timer = Stopwatch.StartNew();
            string testData;
            for (int i = 0; i < counter; i++)
            {
                testData = testDictionary[TextureEnum.Enemy]; // получаем наше значение
            }
 
            TimeSpan timeSpan = timer.Elapsed;
 
            // Вывод статистики
            Console.WriteLine("Затраченное время {0}", timeSpan);
            Console.WriteLine("Вызовов сборщика мусора \r\nПоколение 0 - {0} \r\nПоколение 1 - {1} \r\nПоколение 2 - {2}", 
                GC.CollectionCount(0), GC.CollectionCount(1), GC.CollectionCount(2));
 
            Console.ReadLine();
        }
    }
}

 



Результат:
Затраченное время 00:00:00.2425216
Вызовов сборщика мусора
Поколение 0 - 0
Поколение 1 - 0
Поколение 20

 



Комментарии, думаю, излишни, а выводы делать Вам.

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

P.S.S. Выражаю благодарность пользователю Zubaloo за конструктивную критику и внесение ясности в некоторые спорные моменты.

Комментарии
#1 | Zubaloo 12.08.2009 16:16:49
Проблема есть, решение есть, но объяснение почему это решение решает эту проблему не совсем верно. Кто-то из философов сказал, что хуже всего когда приходишь к правильному ответу неправильным путём - это наш случай: объяснение того почему происходит упаковка, извините, чушь, цитирую

ObjectEqualityComparer<T>: EqualityComparer<T>. Собственно данный класс и подписывает нам приговор при использовании перечисления. Так как нет синтаксиса where T: struct при объявлении класса, то <T> означает, что по умолчанию мы работаем с типом ссылочного типа.

Generics задумывались как раз для того что бы не было этого "по умолчанию" и мы работали каждый раз именно с тем типом с которым хотим работать.
А приговор подписывает нам класс от которого собственно и присходит наше перечисление, а конкретно "System.Enum" и его переопределённые методы GetHashCode() и Equals(object), которые выглядят следующим образом (взято из рефлектора):

GeSHi: C#
  1. public override int GetHashCode()
  2. {
  3. return this.GetValue().GetHashCode();
  4. }
  5. private object GetValue()
  6. {
  7. return this.InternalGetValue();
  8. }
  9. [MethodImpl(MethodImplOptions.InternalCall)]
  10. private extern object InternalGetValue();
  11. [MethodImpl(MethodImplOptions.InternalCall)]
  12. public override extern bool Equals(object obj);
  13.  
Добавлено за 0.006 секунд, используя GeSHi 1.0.8.2


Собственно ларчик просто открывался - именно эти методы и упаковывают объект которым представляется перечисление. Переопределяя в примере IEqualityComparer<T> удаётся избежать вызова GetHashCode и Equals(object) у объекта типа Enum кастуя этот Enum к int (то допущение на которое создатели не могли поити из-за того что Enum может создаваться не только на базе int).
#2 | SolarWind 12.08.2009 16:54:01
Спасибо за коммент! все правильно, признаю был неправ, собака именно тут порылась но не до конца, если к примеру в последнем тестовом приложении заменить преобразование к int
GeSHi: C#
  1. public int GetHashCode(TextureEnum obj)
  2. {
  3. return (int) obj;
  4. }
Добавлено за 0.004 секунд, используя GeSHi 1.0.8.2


на
GeSHi: C#
  1. public int GetHashCode(TextureEnum obj)
  2. {
  3. return obj.GetHashCode();
  4. }
Добавлено за 0.004 секунд, используя GeSHi 1.0.8.2


количество сборок мусора по сравнению с первым тестом изменяется примерно в два раза, вывод - метод Equals у enum, доблестно похороненный вот в таком хитром вызове
GeSHi: C#
  1. MethodImplAttribute(MethodImplOptions.InternalCall)]
  2. public extern override bool Equals(Object obj);
Добавлено за 0.004 секунд, используя GeSHi 1.0.8.2


тоже не идеален.

Два дня ломал голову, над причинами такого поведения при выборке из словаря, но просмотрел получение хэша из перечисления, будет время отредактирую статью, еще раз спасибо.
#3 | vanka 13.08.2009 16:38:38
Помнится, когда я делал этот доклад и в рефлекторе наткнулся на строчки
GeSHi: C#
  1. MethodImplAttribute(MethodImplOptions.InternalCall)]
  2. public extern override bool Equals(Object obj);
Добавлено за 0.004 секунд, используя GeSHi 1.0.8.2

понял, что не смогу это доступно объяснить и решил сделать так как сделал :)
#4 | mike 14.08.2009 20:59:54
Хорошая статья, не смотря на то что в качестве первоисточника взяты доклады Vanka, унаследованные ляпы не так страшны и их можно исправить.

2Zubaloo Все вроде верно, ваш коммент справедлив, однако если быть точным до конца, то упаковку Enum вызывают не вышеописанные методы, а именно вызовы этих методов, что никогда не будет одним и тем же явлением, особенно с точки зрения JIT.

В остальном же - все точно так как пишет автор - лишний мусор при использовании Enum в словарях, нуждающихся в вызове GetHashCode(), возникает в следствие использования дефолтного компарера.
#5 | Zubaloo 17.08.2009 14:41:46
2 mike - Позвольте не согласиться, если уж быть точным до конца, упаковку вызывают именно вышеописанные методы класса Enum, а не методы их вызывающие; и не очень понятно причём здесь JIT.

В остальном же - вследствие того что я написал выше - лишний мусор при использовании Enum в словарях, нуждающихся в вызове GetHashCode(), возникает в следствие неоптимальной реализации GetHashCode и Equals в классе Enum, а не в следствие использования дефолтного компарера, который в общем ни в чём не виноват - он то, как раз, не делает никаких лишних телодвижений. А его кажущаяся вина проистекает из того что от проблемы избавились заменив дефолтный компарер на свой, который знает что не надо вызывать GetHashCode у Enum, а надо этот Enum сначала привести к int и только затем вызвать GetHashCode.
#6 | mike 17.08.2009 15:27:47
использую рефлектор и вижу что вышеописанные методы вызывают распаковку, что не порождает мусора, хоть и добавляет тормозов.

...
ldarg.1
unbox.any System.Enum
stloc.0
...


упаковка (создание временного объекта в куче - тот самый мусор), будет произведена в теле вызывающего метода.

Связь между MSIL и JIT думаю очевидна..
MSIL код вызываемого метода Enum.Equals будет всегда одним и тем же. а вот вызывающий код будет зависеть от типа передаваемых/принимаемых параметров. Если принимаемый параметр System.Object, то передав при вызове значение Enum, С# компилятор добавит инструкцию Box, которую JIT развернет в ASM код создания временного объекта в куче.

Универсальные вещи почти всегда не оптимальны, тут не так просто найти баланс и разработчики NET решили остановится именно на такой реализации GetHashCode и Equals в классе Enum, качество которой тут совсем не причем - просто по тому что у нас нет никакой возможности это изменить, но зато мы всегда можем использовать не дефолтный компарер для своего словаря.
#7 | Zubaloo 17.08.2009 18:24:47
Гм, не флуда ради, а только для внесения ясности в предмет спора - вините ли вы в описанном поведении дефолтный компарер или сам Enum?

Автор винил компарер, я - виню Enum и снимаю вину с компарера, указав методы обращение к которым приводит к упаковке объектов. Вы же, соглашаясь со мной, в тоже время оставляете вину за упаковку на компарере основываясь на том что фактически именно код компарера производит boxing (что фактически правда, так как прежде чем вызвать "истинного виновника"[метод принимающий в качестве параметра object] компареру приходится упаковать объект), но ведь компаратор это делает только потому что у него нет другой альтернативы (класс Enum не предоставляет таких методов GetHashCode и Equals которые принимали бы неупакованные объекты), но в случае если бы альтернатива была, то дефолтный компарер отработал бы без boxing'а.
В качестве примера моих слов хочу предложить такой вариант: в первый (неоптимизированный) вариант программы, который использует дефолтный компарер, вместо перечисления ввести структуру (не класс! то есть тоже value тип) следующего содержания:
GeSHi: C#
  1. public struct TextureEnum : IEquatable<TextureEnum>
  2. {
  3. private int Value;
  4. private TextureEnum(int value)
  5. {
  6. this.Value = value;
  7. }
  8.  
  9. public override int GetHashCode()
  10. {
  11. return this.Value.GetHashCode();
  12. }
  13.  
  14. #region IEquatable<TextureEnum> Members
  15.  
  16. public bool Equals(TextureEnum obj)
  17. {
  18. return this.Value == obj.Value;
  19. }
  20.  
  21. #endregion
  22.  
  23. public static TextureEnum Star = new TextureEnum(0);
  24. public static TextureEnum Ship = new TextureEnum(1);
  25. public static TextureEnum Asteroid = new TextureEnum(2);
  26. public static TextureEnum Bullet = new TextureEnum(3);
  27. public static TextureEnum Enemy = new TextureEnum(4);
  28. public static TextureEnum Logo = new TextureEnum(5);
  29. }
Добавлено за 0.007 секунд, используя GeSHi 1.0.8.2

Что же мы имеем при запуске программы? Ноль вызовов GC - ч.т.д.
Не важно что мы имеем структуру как ключ - важно то что эта структура обладает необходимыми методами GetHashCode и Equals для того что бы не вызывать упаковку объектов, даже при использовании дефолтного компарера.
#8 | mike 17.08.2009 18:46:01
в связке Enum + Dictionary в образовании лишнего мусора виноват дефолтный компарер.
в случае struct + Dictionary виновным будет отсутствие или кривой GetHashCode/Equals у struct.

согласен что был бы у нас Enum:IEquatable<Enum> все было бы проще и прозрачнее для таких таких вещей как словари.
#9 | general 17.08.2009 22:47:41
зачем так усложнять? все приведенные инструменты не приемлемы в 3d приложении. что лишний раз укрепляет миф о проблеме со сборщиком мусора.
#10 | mike 18.08.2009 02:45:10
2general - ты хочешь сказать что 458 сборок в поколении 0 это не страшно? или имеешь ввиду что тут можно обойтись обычным массивом индексированным перечислением?
Добавить комментарий
Пожалуйста, залогиньтесь для добавления комментария.
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Отлично! Отлично! 100% [2 Голоса]
Очень хорошо Очень хорошо 0% [Нет голосов]
Хорошо Хорошо 0% [Нет голосов]
Удовлетворительно Удовлетворительно 0% [Нет голосов]
Плохо Плохо 0% [Нет голосов]
Авторизация
Логин

Пароль



Вы не зарегистрированы?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Мини-чат
Вы должны авторизироваться, чтобы добавить сообщение.

27.08.2014
Я умею немного на asp.net + html и css

22.08.2014
на ASP mvc 3 есть пару проектов. Могу помочь, если нужно. Обидно, если закроется Frown

21.08.2014
я тоже ноль

21.08.2014
Я в вебе только с php занимался да и то на уровне чтоб работало.

21.08.2014
Я в вебе полный ноль…

21.08.2014
Переводить его надо, хоть на ту же азуру. И двиг менять на что-то современное. Если есть веб-разрабы - можем скооперироваться. Один делать не буду.

21.08.2014
не знаю всех нюансов по оплате и все хорошее когда нибудь заканчивается

21.08.2014
А что случилось?

21.08.2014
похоже сайт будет работать до 28го числа

09.08.2014
Апи пока не видел. Но есть приложение в магазине Live Lock Screen BETA, так что думаю скоро будет

08.08.2014
Я про API для Update1. На нем работает это

08.08.2014
А что именно нужно? Чтото и сейчас открыто http://msdn.micro.
...105).aspx

06.08.2014
Кто-нибудь слышал об открытии доступа к Lock Screen Api?

31.07.2014
VPDExpress на базе MVS 2012, ни в какую не ловит исключения. Даже если их сам создаешь. И всех так?

25.07.2014
С днем системного администратора причастных к этой профессии! По случаю - тортик от жены

RSS каналы сайта
XNA - Новости
XNA - Статьи
XNA - Форум
XNA - Галерея
XNA - Файлы
Время загрузки: 0,24 секунд 8,710,298 уникальных посетителей