Данная статья является продолжением статьи:
http://hale32bit.blogspot.com/2011/07/blog-post.html
Pool vs FastCollection
Все коллекции, представленные в предыдущей статье, могут использоваться вместо пула. Возникает вопрос: в каких случаях всё же лучше использовать пул? Какие есть преимущества Fast Collection перед Pool? Я вижу всего два преимущества:
1) Возможность обхода всех активных объектов
2) Защита от дублирования элементов
Первое преимущество можно выкинуть т.к. очевидно, что если нам нужен обход элементов, то мы выберем FastCollection, а не Pool т.к. в Pool его просто нет.
Защита от дублирования элементов означает, что мы можем дважды возвратить в Pool один и тот же объект, что в конечном итоге может привести к тяжёлым последствиям, в FastCollection невозможно удалить один объект дважды. Pool, на мой взгляд, очень опасный паттерн, ошибки которого довольно трудно отлавливать, а FastCollection чуть более надёжен. Эту тему я продолжу чуть позже, а пока рассмотрим преимущества паттерна Pool.
1) Немного быстрее
2) Использует меньше памяти
3) Не требует наследования объектов от специального класса
Как можно заметить Pool немного быстрее удаляет объекты т.к. при этом не происходит рокировка и перезапись индексов. К тому же Pool не требует памяти под хранение индексов элементов. Поэтому, несмотря на всю опасность, нам всё ещё хочется использовать Pool. Какие ошибки возникают при работе с пулом и как их можно обнаружить? Далее я расскажу свой взгляд на эту проблему.
Возможные ошибки
1) Утечка мусора.
Может так случиться, что по окончанию использования объекта программа (т.е. программист) забудет вернуть его в пул, а вместо этого просто обнулит ссылки. Тогда им займётся сборщик мусора. Если мы используем FastCollection, тогда ссылка на объект никогда не будет потеряна и получится утечка памяти.
2) Дублирование элементов.
Если вернуть в пул один и тот же объект два раза, тогда он потенциально может быть выдан два раза, получится полный кавардак. В FastCollection такое невозможно т.к. каждому объекту соответствует уникальный индекс в массиве.
3) Призраки.
Если программа возвратит объект в пул, но при этом продолжит его использовать – это, в конечном счёте, может привести к утечке мусора или дублированию элементов в пуле. С FastCollection – та же проблема.
4) Элементы без прописки.
Это самая безобидная проблема. Просто если программист забудет, что есть пул и будет создавать объекты напрямую с помощью конструктора, то возможно он забудет их и вернуть в пул, что приведёт к утечке мусора. Хотя он может не забыть их вернуть в пул – что приведёт к нерациональному использованию памяти, т.к. созданием объектов занимается не пул, который старается инстацировать по возможности меньше объектов. При использовании FastCollection элементы без прописки довольно опасны, однако далее будет показано, как можно изменить код, чтобы контролировать ситуацию.
Утечка мусора и дублирование элементов.
Обе проблемы опасны для пула, и трудно отловить баг в момент, когда он происходит. Однажды в конце игры, или в момент, когда один игровой уровень выгружен, а следующий ещё не загружен, все объекты должны быть возвращены в пул, назовём это нормальным состоянием пула. Я предлагаю проверять нормальное состояние пула, действительно ли оно нормальное. Так мы можем узнать, произошло ли в течение игры дублирование элементов или утечка мусора.
Анализ заключается в том чтобы сравнить число элементов пуле с числом уникальных элементов в пуле – таким образом, будет обнаружено наличие дубликатов. Но и это ещё не всё. В нормальном состоянии все объекты должны быть возвращены в пул. Поэтому если сравнить полное число инстацированых элементов и число уникальных элементов в пуле можно узнать была ли утечка мусора. Конечно, для этого необходимо вести подсчёт инстацированых объектов. Далее приведён код, которым я пользуюсь и который мне очень помог:
public interface IPoolable { }
/// <summary>
/// Базовый класс для пула
/// </summary>
public class PoolBase
{
//Список всех пулов в приложении
static protected readonly List<PoolBase> _pools = new List<PoolBase>(10);
/// <summary>
/// Анализ всех пулов
/// </summary>
[Conditional("DEBUG")]
public static void AnalyzePools()
{
foreach (PoolBase pool in _pools)
pool.Analyze();
_pools.Clear();
}
[Conditional("DEBUG")]
protected virtual void Analyze()
{
}
}
public class Pool<T> : PoolBase
where T : class, IPoolable
{
Func<T> _instancer;
T[] _elements;
int _released = 0;
int _instanced = 0;
public int Count
{
get
{
return _elements.Length;
}
}
public Pool(Func<T> instancer, int capacity = 1000)
{
_instancer = instancer;
_elements = new T[capacity];
#if DEBUG
_pools.Add(this);
#endif
}
private T RemoveObject()
{
if (_released > 0)
{
T obj = _elements[_released - 1];
_released--;
if (obj != null)
return obj;
}
return null;
}
private T CreateObject()
{
T newObject = _instancer();
_instanced++;
//
if (_instanced + _released > _elements.Length)
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 == _elements.Length)
throw new ApplicationException("Pool overflow");
else
_elements[_released] = obj;
_released++;
}
/// <summary>
/// Вспомогательный иттератор
/// </summary>
/// <returns></returns>
private IEnumerable<T> ReleasedElements()
{
for (int i = 0; i < _released; i++)
yield return _elements[i];
yield break;
}
protected override void Analyze()
{
//Подсчёт уникальных объектов
int unique = ReleasedElements().Distinct().Count();
//Проверка нормального состояния пула
if (unique != _instanced || unique != _released)
{
throw new ApplicationException("Несоответствие инстацированных, возвращённых и уникальных объектов пула "
+ this.ToString() + "\n" +
"Инстацировано : " + _instanced.ToString() + "\n" +
"Возвращено : " + _released.ToString() + "\n" +
"Уникальных : " + unique.ToString()
);
}
}
}
Чтобы проверить нормальное состояние достаточно вызвать метод PoolBase.AnalyzPools() по окончанию игры.
К сожалению, не представляю, как можно было бы обнаружить утечку памяти при использовании FastCollection. Может с помощью слабых ссылок?
Призраки
Призраков пожалуй невозможно отловить не в случае пула не в случае FastCollection.
Элементы без прописки
Чтобы в других частях программы объекты не создавались помимо пула, можно сделать закрытый конструктор:
public class Class1 : IPoolable
{
private Class1() { }
static Pool<Class1> _pool = new Pool<Class1>(() => new Class1());
static Class1 InstantFromPool()
{
return _pool.GetObject();
}
public void ReleaseToPool()
{
_pool.Release(this);
}
}
В случае FastCollection можно по умолчанию выдавать новым объектам отрицательный индекс, при этом исключение будет возникать каждый раз, когда мы пытаемся удалить из коллекции элемент не существующий в ней.
В отличие от пула может оказаться нужным создать несколько FastCollection одного типа. Например, две FastCollection спрайтов, спрайты заднего плана, и спрайты переднего плана. Чтобы можно было сначала рисовать спрайты заднего плана, а потом переднего, иначе если бы они были в одной FastCollection, то перемешались бы. Как защитится от удаления не из той коллекции, и как реализовать перекидывание элемента из одной коллекции в другую. Можно модифицировать FastCollection как показано ниже, все изменения отмечены комментариями.
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 _absoluteTop = -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);
_absoluteTop++; //Увеличение верхней границы неиспользуемых элементов
}
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 (!Contains(element))
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--;
}
/// <summary>
/// Проверка на принадлежность объекта коллекции O(1)
/// </summary>
public bool Contains(T element)
{
return _elements[element.FastCollectionIndex] == element;
}
/// <summary>
/// Извлечение элемента из коллекции
/// </summary>
public void Pop(T element)
{
int index = element.FastCollectionIndex;
//Проверка на принадлежность
if (!Contains(element))
throw new ApplicationException();
//Проверка на используемость
if (index > _top)
throw new ApplicationException();
//Специальная рокировка
_elements[index] = _elements[_top];
_elements[_top] = _elements[_absoluteTop];
_top--;
_absoluteTop--;
_elements[index].SetFastCollectionIndex(index);
//Пометка что элемент не используется ни в какой коллекции
element.SetFastCollectionIndex(-1);
}
/// <summary>
/// Вставка в коллекцию элемента, ранее не пренадлежавшего ей
/// </summary>
public void Push(T element)
{
//Проверка на принадлежность элемента какой-либо коллекции
if (element.FastCollectionIndex != -1)
throw new ApplicationException();
//Проверка на переполнение
if (_absoluteTop == _elements.Length - 1)
throw new ApplicationException();
//увеличение границы
_top++;
_absoluteTop++;
//специальная рокировка
_elements[_absoluteTop] = _elements[_top];
_elements[_top] = element;
element.SetFastCollectionIndex(_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, хотя уже не такая быстрая, но более гибкая. Кстати этот код я ещё не испытывал, он может содержать ошибки.
