На данную статью меня вдохновила статья: Dmitry Timofeev: Компромисс в выборе между классом и структурой
Повторное использование
В компьютерных играх зачастую присутствуют такие объекты как снаряды, осколки, бонусы, лут, мобы, вэйпоинты, частицы и пр. - объекты которые рождаются и умирают сотнями каждую секунду. Уже использованные они становятся мусором, а мусор в нашем мире проблема не самая последняя, особенно если вы разрабатываете игру в среде с автоматическим управлением памятью посредством сборки мусора (например CLR).
Процессы высвобождения памяти могут погасить значительную часть производительности если ничего не предпринять. Поэтому умные люди придумали повторно использовать старые объекты.
Пул
Пул - это патерн, реализующий механизм повторного использования. Объект пул отвечает за создание и "удаление" объектов некоторого типа T. Внешние объекты при необходимости запрашивают у пула новый экземпляр типа T (GetObject()), и после окончания работы ним возвращают его пулу (Release()). Пул сохраняет все использованные объекты, а потом когда извне приходит запрос нового экземпляра, отдаёт их на повторное использование. Пул старается по возможности не создавать новые экземпляры, а повторно использовать старые.
public class Pool<T>
where T : class
{
Func<T> _instancer;
List<T> _list;
int _released = 0;
int _instanced = 0;
int _limit;
public int Count
{
get
{
return _list.Count;
}
}
public Pool(Func<T> instancer, int capacity = 10, int limit = 1000)
{
_instancer = instancer;
_list = new List<T>(capacity);
_limit = limit;
}
private T RemoveObject()
{
if (_released > 0)
{
T obj = _list[_released - 1];
_released--;
if (obj != null)
return obj;
}
return null;
}
private T CreateObject()
{
T newObject = _instancer();
_instanced++;
//
if (_instanced > _limit)
throw new ApplicationException("Pool overflow");
return newObject;
}
public T GetObject()
{
T thisObject = RemoveObject();
if (thisObject != null)
return thisObject;
return CreateObject();
}
public void Release(T obj)
{
//
if (obj == null)
throw new NullReferenceException();
//
if (_released == _list.Count)
_list.Add(obj);
else
_list[_released] = obj;
_released++;
}
}
При программировании с использованием пула нужно следить чтобы все использованые объекты типа T сдавались на хранение в пул - это является основной проблемой. Если в некоторых ситуациях объекты типа T не будут сдаваться в пул, то они не смогут повторно использоваться и попадут под действие сборщика мусора, эффект от пула не будет полным, можно назвать это "утечкой мусора". Порой проблема даже не в том чтобы не забыть сдать использованный объект, а в том чтобы определить когда объект перестает использоваться. Так если объект используется одновременно несколькими объектами, нужно отслеживать момент когда он не используется ни одним объектом. К тому же нужно следить чтобы пул не получил один объект дважды, или чтобы пул не получил ещё использующийся объект.
Пул хотя и простейшее решение, но не самое лучшее. Больше возможностей мы получаем от особых коллекций снабженных возможностью повторного использования. О них и пойдёт речь далее.
Объекты типа частиц, снарядов, осколков и т.п., о которых говорилось ранее, не только грозят засорением, но и создают огромную работу по вставке и удалению этих объектов в коллекциях, в которых они числятся. Не каждая коллекция может быстро справится с задачей.
Представляю вашему вниманию FastCollection - коллекция в которой вставка и удаление элементов очень быстрые, к тому же она выполняет функции пула. Реализация моя, а сам подход был предложен Дмитрием Тимофеевым (general):
public abstract class FastCollectionElement
{
int _fastCollectionIndex = -1;
internal int FastCollectionIndex
{
get
{
return _fastCollectionIndex;
}
}
internal void SetFastCollectionIndex(int index)
{
_fastCollectionIndex = index;
}
}
public class FastCollection<T> : IEnumerable<T>
where T : FastCollectionElement, new()
{
T[] _elements;
int _top = -1;
int _enumerators = 0;
public FastCollection(int capacity)
{
_elements = new T[capacity];
}
public T GetNewElement()
{
//
if (_enumerators > 0)
throw new ApplicationException();
//защита от переполнения
if (_top == _elements.Length - 1)
throw new ApplicationException();
//
_top++;
if (_elements[_top] == null)
{
_elements[_top] = new T();
_elements[_top].SetFastCollectionIndex(_top);
}
return _elements[_top];
}
public void Clear()
{
//
if (_enumerators > 0)
throw new ApplicationException();
//
_top = -1;
}
public void Remove(T element)
{
//
int index = element.FastCollectionIndex;
//
if (index > _top)
throw new ApplicationException();
//
if (_enumerators > 0)
throw new ApplicationException();
//рокировка
if (index < _top)
{
//
T temp = _elements[_top];
_elements[_top] = _elements[index];
_elements[index] = temp;
//
_elements[_top].SetFastCollectionIndex(_top);
_elements[index].SetFastCollectionIndex(index);
}
//
_top--;
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return new FastCollectionEnumerator(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return new FastCollectionEnumerator(this);
}
public class FastCollectionEnumerator : IEnumerator<T>
{
FastCollection<T> _collection;
int _curIndex = -1;
public FastCollectionEnumerator(FastCollection<T> collection)
{
_collection = collection;
_collection._enumerators++;
}
public T Current
{
get
{
return _collection._elements[_curIndex];
}
}
object IEnumerator.Current
{
get
{
return _collection._elements[_curIndex];
}
}
public bool MoveNext()
{
_curIndex++;
return (_curIndex <= _collection._top);
}
public void Reset()
{
throw new NotImplementedException();
}
public void Dispose()
{
_collection._enumerators--;
}
}
}
FastCollection суть список (List). Как и лист она представляет собой массив в котором используются только первые n элементов. n (в коде _top) - это виртуальная граница между используемыми и неиспользуемыми элементами. Добавление нового элемента осуществляется простым увеличением виртуальной границы n = n + 1. Если при этом на позиции n+1 находится элемент(неиспользуемый элемент) то коллекция использует его(повторное использование) иначе создает новый.
Рис.1 FastCollection
При удалении элемента удаляемый элемент меняется местами с последним и виртуальная граница уменьшается на единицу. Таким образом удалённый элемент оказывается в области неиспользуемых.
Плюсы коллекции - это в первую очередь скорость: скорость удаления, скорость создания, скорость очистки и скорость обхода(foreach) объектов. Это пожалуй самый быстрый вариант для объектов критичных в отношении мусора.
Минус - это не сохранение порядка следования элементов: при многократных удалениях элементы в коллекции перемешиваются случайным образом. Отсюда же следует второй минус: не возможность изменения коллекции во время обхода. В реализации приведённой выше вы можете видеть как происходит контроль за тем чтобы изменение коллекции во время обхода не происходило.
Первый минус незначителен для большинства встречающихся ситуаций. Второй минус, по словам Дмитрия, тоже не значительный. Все стандартные коллекции .NET не позволяют производить изменения во время обхода. Но я считаю иначе. Ведь зачастую во время обхода сам элемент решает что его нужно удалить. Так цикл по всем снарядам проверяет столкновение, после которого нужно уничтожить снаряд, но если это нельзя сделать во время цикла приходится накапливать информацию о предстоящих удалениях в какой-то вспомогательной коллекции или как-то ещё. Может я заблуждаюсь и противоречу принципам "правильного" программирования, но я считаю, что нужно создать коллекцию, позволяющую удалять во время обхода. Новички наверное меня поймут. :)
Связный список
В первую очередь в глаза бросается двусвязный список. Именно в нём возможно удаление во время обхода(foreach). Действительно, если мы удалили элемент L, на который в данный момент указывает итератор, то ссылка на следующий элемент L.Next позволит итератору идти дальше(см Рис.2)
Рис.2 Удаление элемента из связного списка
Если удалённые элементы складывать в стек, можно избежать утечки мусора - получится довольна неплохая коллекция.
ReusingLinkedList - связный список с повторным использованием:
public abstract class ReusingLinkedListElement
{
internal ReusingLinkedListElement Next;
internal ReusingLinkedListElement Prev;
}
public class ReusingLinkedList<T> : IEnumerable<T>
where T : ReusingLinkedListElement, new()
{
ReusingLinkedListElement _first;
ReusingLinkedListElement _last;
int _count = 0;
public int Count
{
get
{
return _count;
}
}
Stack<ReusingLinkedListElement> _cache;
ReusingLinkedListElement _zero; // необходим для работы итератора
public ReusingLinkedList(int capacity)
{
_cache = new Stack<ReusingLinkedListElement>(capacity);
_zero = new T();
}
private ReusingLinkedListElement NewElement()
{
if (_cache.Count > 0)
return _cache.Pop();
else
return new T();
}
public T GetNewElementAsFirst()
{
//
ReusingLinkedListElement element = NewElement();
//
if (_count == 0)
{
element.Next = null;
element.Prev = null;
_last = element;
_first = element;
}
else
{
element.Next = _first;
element.Prev = null;
_first.Prev = element;
_first = element;
}
//
_count++;
return (T)element;
}
public T GetNewElementAsLast()
{
ReusingLinkedListElement element = NewElement();
//
if (_count == 0)
{
element.Next = null;
element.Prev = null;
_last = element;
_first = element;
}
else
{
element.Next = null;
element.Prev = _last;
_last.Next = element;
_last = element;
}
//
_count++;
return (T)element;
}
public T GetNewElementAfter(T baseElement)
{
if (baseElement == _last)
{
return GetNewElementAsLast();
}
else
{
ReusingLinkedListElement element = NewElement();
element.Next = baseElement.Next;
element.Prev = baseElement;
baseElement.Next.Prev = element;
baseElement.Next = element;
_count++;
return (T)element;
}
}
public T GetNewElemenBefore(T baseElement)
{
if (baseElement == _first)
{
return GetNewElementAsFirst();
}
else
{
ReusingLinkedListElement element = NewElement();
element.Next = baseElement;
element.Prev = baseElement.Prev;
baseElement.Prev.Next = element;
baseElement.Prev = element;
_count++;
return (T)element;
}
}
public void Remove(T element)
{
//
if (element == _first)
_first = element.Next;
else
element.Prev.Next = element.Next;
//
if (element == _last)
_last = element.Prev;
else
element.Next.Prev = element.Prev;
//
_cache.Push(element);
_count--;
}
public void Clear()
{
foreach (ReusingLinkedListElement element in this)
this.Remove((T)element);
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return new ReusingLinkedListEnumerator(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return new ReusingLinkedListEnumerator(this);
}
public class ReusingLinkedListEnumerator : IEnumerator<T>
{
ReusingLinkedList<T> _collection;
ReusingLinkedListElement _curElement;
public ReusingLinkedListEnumerator(ReusingLinkedList<T> collection)
{
_collection = collection;
_curElement = _collection._zero;
_curElement.Next = _collection._first;
}
public T Current
{
get
{
return (T)_curElement;
}
}
object IEnumerator.Current
{
get
{
return _curElement;
}
}
public bool MoveNext()
{
_curElement = _curElement.Next;
return _curElement != null;
}
public void Reset()
{
throw new NotImplementedException();
}
public void Dispose()
{
}
}
}
Здесь поле _zero помогает организовать работу итератора т.к. по правилам в начале работы итератор должен занимать позицию перед первым элементом.
ReusingLinkedList сохранят порядок следования элементов при удалении и вставке, он обладает широкими возможностями вставки (в начало, в конец, перед, после), к тому же вставка и удаление возможны во время обхода без побочных эффектов (смотря что считать побочным эффектом, ну вы меня поняли). Вставка и удаление не такие быстрые как в FastCollection, но всё ещё O(1). Обход коллекции наверное даже быстрее чем в FastCollection. Однако очистка коллекции (Clear()) медленная порядка О(n).
ReusingLinkedList использует больше памяти чем FastCollection.
Я считаю ReusingLinkedList - лучшим выбором во многих ситуациях нежели FastCollection за счёт возможности изменения во время обхода.
Почему я так люблю связный список? Наверное потому, что я начинал свой путь с движка Blitz3D. Там двусвязный список является центральным типом данных, и я думаю не просто так разработчик Blitz3D сделал такой выбор - двусвязный список это действительно мощный инструмент.
Доступ по индексу
Для интереса я решил реализовать коллекцию с повторным использованием и индексными привязками элементов.
IndexedReusingCollection - это суть массив, где все элементы снабжены булевым флагом(valid). Флаг несет информацию о том используется объект или нет. Отчасти работа IndexedReusingCollection напоминает FastCollection: так же массив разделён на две части используемые и неиспользуемые объекты, но при удалении объекта не происходит рокировка. Если удаляется крайний используемый объект то просто сдвигается виртуальная граница, а если удаляется один из элементов в середине коллекции то его индекс добавляется в стек неиспользуемых индексов(_unusedIndeces). При добавлении нового элемента в первую очередь заполняются индексы из стека неиспользуемых, а если стек пуст тогда как и в FastList сдвигается виртуальная граница.
public class IndexedReusingCollection<T> : IEnumerable<T>
where T : class, new()
{
T[] _elements;
bool[] _valid;
int _elementsTop = -1;
int[] _unusedIndeces;
int _unusedIndecesTop = -1;
int _count = 0;
public int Count
{
get
{
return _count;
}
}
public T this[int index]
{
get
{
if (!_valid[index])
throw new ApplicationException();
return _elements[index];
}
}
public IndexedReusingCollection(int capacity)
{
_elements = new T[(capacity * 3) / 2];
_valid = new bool[_elements.Length];
_unusedIndeces = new int[capacity / 2];
}
public T GetNewElementAsLast(out int index)
{
//защита от переполнения
if (_elementsTop == _elements.Length - 1)
throw new ApplicationException();
//
_elementsTop++;
if (_elements[_elementsTop] == null)
{
_elements[_elementsTop] = new T();
}
//
_valid[_elementsTop] = true;
_count++;
index = _elementsTop;
return _elements[_elementsTop];
}
public T GetNewElement(out int index)
{
if (_unusedIndecesTop < 0)
{
//Добавление или повторное использование элемента в конце коллекции
return GetNewElementAsLast(out index);
}
else
{
//Повторное использование одного из лементов в середине колекции.
index = _unusedIndeces[_unusedIndecesTop];
_valid[index] = true;
_unusedIndecesTop--;
_count++;
return _elements[index];
}
}
public void Remove(int index)
{
if (index == _elementsTop)
_elementsTop--;
else
{
//Защита от переполнения массива
if (_unusedIndecesTop == _unusedIndeces.Length - 1)
throw new ApplicationException();
//
_unusedIndecesTop++;
_unusedIndeces[_unusedIndecesTop] = index;
}
_valid[index] = false;
_count--;
}
public void Clear()
{
for (int i = 0; i <= _elementsTop; i++)
_valid[i] = false;
_elementsTop = -1;
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return new IndexedReusingCollectionEnumerator(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return new IndexedReusingCollectionEnumerator(this);
}
public class IndexedReusingCollectionEnumerator : IEnumerator<T>
{
IndexedReusingCollection<T> _collection;
int _curIndex = -1;
public IndexedReusingCollectionEnumerator(IndexedReusingCollection<T> collection)
{
_collection = collection;
}
public T Current
{
get
{
return _collection._elements[_curIndex];
}
}
object IEnumerator.Current
{
get
{
return _collection._elements[_curIndex];
}
}
public bool MoveNext()
{
_curIndex++;
while (
!_collection._valid[_curIndex] &&
_curIndex <= _collection._elementsTop)
_curIndex++;
return _curIndex <= _collection._elementsTop;
}
public void Reset()
{
throw new NotImplementedException();
}
public void Dispose()
{
}
}
}
IndexedReusingCollection - обладает самым медленным обходом среди рассмотренных коллекций, по идее она для этого не приспособлена. Вставка и удаление как всегда быстрые.
Данная коллекция обладает двумя уникальными плюсами - это доступ по индексу и то, что она не требует чтобы её элементы наследовались от какого-то специального базового класса.
Возможно в некоторых редких случаях IndexedReusingCollection будет незаменим.
P.S. Скачать пример:
P.S. Скачать пример:
Комментариев нет:
Отправить комментарий