Основная проблема, с которой вы сталкиваетесь, когда вы начинаете увеличивать количество экземпляров классов, заключается в том, что все они должны учитываться и отслеживаться во время операции сбора мусора, даже если вы никогда не освобождаете эти экземпляры, сборщик мусора все еще должен отслеживать их . Наступает момент, когда программа тратит больше времени на сборку мусора, чем на фактическую работу. Мы столкнулись с такой проблемой производительности при использовании бинарного дерева поиска, которое в итоге содержало несколько миллионов узлов, которые изначально были экземплярами классов.
Мы смогли обойти это, используя List<T> структур, а не классов. ( Память списка поддерживается массивом, а для структур сборщик мусора должен отслеживать только одну ссылку на этот массив ). Теперь вместо ссылок на класс мы сохраняем индексы в этом списке, чтобы получить доступ к нужному экземпляру структуры.
Фактически мы также столкнулись с проблемой (обратите внимание, что более новые версии .NET Framework устраняют это ограничение) , что резервный массив не может быть больше 2 ГБ даже под 64-битными, поэтому мы разбили хранение в нескольких списках (256) и использование 32-битного индекса, где 8 битов действовали как селектор списка, а оставшиеся 24 бита служили индексом в списке.
Конечно, удобно создать класс, который абстрагирует все эти детали, и вы должны знать, что при изменении структуры вам действительно нужно скопировать ее в локальный экземпляр, изменить и затем заменить исходную структуру на копия измененного экземпляра, в противном случае ваши изменения будут происходить во временной копии структуры и не будут отражены в вашей коллекции данных. Кроме того, это влияет на производительность, которая, к счастью, окупается, как только сбор становится достаточно большим, с чрезвычайно быстрыми циклами сбора мусора.
Вот некоторый код (довольно старый), показывающий эти идеи на месте, и перешел с сервера, тратящего около 100% процессорного времени, до около 15%, просто перенеся наше дерево поиска на этот подход.
public class SplitList<T> where T : struct {
// A virtual list divided into several sublists, removing the 2GB capacity limit
private List<T>[] _lists;
private Queue<int> _free = new Queue<int>();
private int _maxId = 0;
private const int _hashingBits = 8;
private const int _listSelector = 32 - _hashingBits;
private const int _subIndexMask = (1 << _listSelector) - 1;
public SplitList() {
int listCount = 1 << _hashingBits;
_lists = new List<T>[listCount];
for( int i = 0; i < listCount; i++ )
_lists[i] = new List<T>();
}
// Access a struct by index
// Remember that this returns a local copy of the struct, so if changes are to be done,
// the local copy must be copied to a local struct, modify it, and then copy back the changes
// to the list
public T this[int idx] {
get {
return _lists[(idx >> _listSelector)][idx & _subIndexMask];
}
set {
_lists[idx >> _listSelector][idx & _subIndexMask] = value ;
}
}
// returns an index to a "new" struct inside the collection
public int New() {
int result;
T newElement = new T();
// are there any free indexes available?
if( _free.Count > 0 ) {
// yes, return a free index and initialize reused struct to default values
result = _free.Dequeue();
this[result] = newElement;
} else {
// no, grow the capacity
result = ++_maxId;
List<T> list = _lists[result >> _listSelector];
list.Add(newElement);
}
return result;
}
// free an index and allow the struct slot to be reused.
public void Free(int idx) {
_free.Enqueue(idx);
}
}
Вот фрагмент того, как наша реализация двоичного дерева в итоге выглядела с использованием этого SplitList класса контейнера поддержки:
public class CLookupTree {
public struct TreeNode {
public int HashValue;
public int LeftIdx;
public int RightIdx;
public int firstSpotIdx;
}
SplitList<TreeNode> _nodes;
…
private int RotateLeft(int idx) {
// Performs a tree rotation to the left, here you can see how we need
// to retrieve the struct to a local copy (thisNode), modify it, and
// push back the modifications to the node storage list
// Also note that we are working with indexes rather than references to
// the nodes
TreeNode thisNode = _nodes[idx];
int result = thisNode.RightIdx;
TreeNode rightNode = _nodes[result];
thisNode.RightIdx = rightNode.LeftIdx;
rightNode.LeftIdx = idx;
_nodes[idx] = thisNode;
_nodes[result] = rightNode;
return result;
}
}