В List не ограничения на T, такого как where T:IEqualityComparer<T> поскольку не для всех кейсов нужно реализовывать IEqualityComparer, в большинстве случаев лист используется просто как хранилище элементов, да и реализация типом IEqualityComparer может противоречить Single Responsibility. Поэтому в листе Comparer явно не задан.
Поэтому, если не передать компарер в метод явно будет использоваться свойство EqualityComparer.Default, инициализация которого происходит только один раз. (Инициализация статического свойства происходит при первом обращении).
В случае generic статического свойства оно будет инициализироваться по одному разу для каждого типа T. Таким образом проседание производительности будет только один раз, в далее все будет отрабатывать быстро. Сам компарер просматривает тип T, реализует ли он IEquatable<T>. Если реализует, то будет использоваться GenericEqualityComparer:
Если наш пользовательский тип не реализует IEquatable, то будет использоваться ObjectEqualityComparer
Т.е достаточно просто переопределить Equals и GetHashCode правильным образом, тем не менее рекомендуется реализовывать IEquatable, потому что Object.Equals(object o), принимает object, т.e его сравнение придется кастить, а это уже расходы
В Java generic'и существуют только до компиляции, далее они вырождаются в object, этим сохраняется обратная совместимость с предыдущими версиями java(без generic'ов).
Разница в том, что методы generic типов закрытых ссылочных типами переиспользуются в отличие от методов generic типов закрытых структурами. Среда создает по типу для каждой реализации generic типа, но когда эта реализация закрыта ссылочными типами, то они используют одни и те же методы, без jitting'a каждого метода по отдельности.
List<object> o = new List<object>();
o.Add(new object());
List<Person> p = new List<Person>();
p.Add(new Person());В данном случае jitting произойдет на второй строке, при повторном обращении к методу на строке 4 будет использован только что обработанный jit'ом метод. Это возможно поскольку работа с ссылочными типами в asm идентична(потому что это работа с указателем), а с типами значений нет(потому что каждый value type имеет разный размер).
Приведу пример для кода:
public class Generic<R>
{
public void Print() => Console.WriteLine("writeline");
}
var g = new Generic<object>();
var g1 = new Generic<PersonClass>();
var g2 = new Generic<int>();
Debugger.Break();Далее приведена расшифровка с использованием SoS.dll, как видно, EEClass и дескриптор метода для ссылочных generic параметров одинаковый, а для int, совершенно другое и то, и то. EEClass - структура используемая механизмом рефлексии, в которой лежит обратная ссылка на MT, для generic типов закрытых ссылочными generic параметрами обратный указатель из EEClass на MT, указывает на MT ConsoleApp1.Generic`1[[System.__Canon, System.Private.CoreLib]].
Получается, что для ссылочных параметров создаются разные MT, но они содержат ссылки на одни и те же методы. Для структур создаются разные MT и все методы - разные.
Как происходит вызов generic метода и чем он отличается от вызова обычного метода? Насколько ниже производительность?
Когда вызывается generic метод, то происходит передача дополнительного параметра через регистр rdx. В этом параметре на самом деле реальный тип метода который нужно вызвать(его methodDesc). Инструкция call - это промежуточный узел вызова, который на самом деле вызовет метод, переданный в descriptor'e.
Я сделал такой бенчмарк:
public class Test
{
}
public class MyTester
{
[MethodImpl(MethodImplOptions.NoInlining)]
public T[] Q<T>(T item)
{
var q = new T[] {item};
return q;
}
}
public class Tester1
{
[MethodImpl(MethodImplOptions.NoInlining)]
public Test[] Q(Test item)
{
var q = new Test[] {item};
return q;
}
}
public class InterfaceMethodCallBenchmark
{
private MyTester Generic = new MyTester();
private Tester1 NonGeneric = new Tester1();
private Test Test = new Test();
[Benchmark]
public void GenericTest_10001()
{
for (int i = 0; i < 10001; i++)
Generic.Q(Test);
}
[Benchmark]
public void GenericTest_10000()
{
for (int i = 0; i < 10000; i++)
Generic.Q(Test);
}
[Benchmark]
public void NonGenericTest_10001()
{
for (int i = 0; i < 10001; i++)
NonGeneric.Q(Test);
}
[Benchmark]
public void NonGenericTest_10000()
{
for (int i = 0; i < 10000; i++)
NonGeneric.Q(Test);
}
}Вот результаты :
| Method | Mean | Error | StdDev |
|---|---|---|---|
| GenericTest_10001 | 143.1 us | 0.68 us | 0.60 us |
| GenericTest_10000 | 142.0 us | 0.41 us | 0.36 us |
| NonGenericTest_10001 | 126.4 us | 0.60 us | 0.53 us |
| NonGenericTest_10000 | 126.3 us | 1.02 us | 0.90 us |
Интересно, что размотка цикла при 10000 значений(если она была) практически не помогла. Получается, что generic реализация все-таки может просадить производительность. Интересно как происходит вызов метода с несколькими generic'ами. На самом деле ничего не отличается, также через регистр rdx передается дескриптор реального метода.
Далее я добавил еще один generic параметр:
public class Test
{
}
public class Test1
{
}
public class MyTester
{
[MethodImpl(MethodImplOptions.NoInlining)]
public T[] Q<T, T1>(T item, T1 item1)
{
var q = new T[] {item};
var qq = new T1[] {item1};
return q;
}
}
public class Tester1
{
[MethodImpl(MethodImplOptions.NoInlining)]
public Test[] Q(Test item, Test1 item1)
{
var q = new Test[] {item};
var q1 = new Test1[] {item1};
return q;
}
}
public class InterfaceMethodCallBenchmark
{
private MyTester Generic = new MyTester();
private Tester1 NonGeneric = new Tester1();
private Test Test = new Test();
private Test1 Test1 = new Test1();
[Benchmark]
public void GenericTest_10001()
{
for (int i = 0; i < 10001; i++)
Generic.Q(Test, Test1);
}
[Benchmark]
public void GenericTest_10000()
{
for (int i = 0; i < 10000; i++)
Generic.Q(Test, Test1);
}
[Benchmark]
public void NonGenericTest_10001()
{
for (int i = 0; i < 10001; i++)
NonGeneric.Q(Test, Test1);
}
[Benchmark]
public void NonGenericTest_10000()
{
for (int i = 0; i < 10000; i++)
NonGeneric.Q(Test, Test1);
}
}Результат:
| Method | Mean | Error | StdDev |
|---|---|---|---|
| GenericTest_10001 | 280.8 us | 1.83 us | 1.71 us |
| GenericTest_10000 | 279.8 us | 1.68 us | 1.40 us |
| NonGenericTest_10001 | 238.8 us | 0.83 us | 0.78 us |
| NonGenericTest_10000 | 237.2 us | 0.84 us | 0.79 us |
Разница выросла пропорционально количеству переданных параметров ((143.1-126.3)*2 ==(примерно) 280.8 - 238.8). Подробно при вызов generic методов можно прочитать здесь
В данном примере само тело метода занимает намного больше, чем просто его вызов, парадоксально, а вот какие бенчмарки получаются, если убрать тело метода:
| Method | Mean | Error | StdDev |
|---|---|---|---|
| GenericTest_10001 | 18.02 us | 0.054 us | 0.048 us |
| GenericTest_10000 | 17.17 us | 0.074 us | 0.069 us |
| NonGenericTest_10001 | 21.02 us | 0.058 us | 0.054 us |
| NonGenericTest_10000 | 14.99 us | 0.019 us | 0.017 us |
| Method | Mean | Error | StdDev |
|---|---|---|---|
| GenericTest_10001 | 17.18 us | 0.045 us | 0.042 us |
| GenericTest_10000 | 17.16 us | 0.046 us | 0.043 us |
| NonGenericTest_10001 | 15.01 us | 0.033 us | 0.031 us |
| NonGenericTest_10000 | 14.99 us | 0.028 us | 0.026 us |
| Method | Mean | Error | StdDev |
|---|---|---|---|
| GenericTest_10001 | 17.97 us | 0.033 us | 0.030 us |
| GenericTest_10000 | 17.13 us | 0.050 us | 0.047 us |
| NonGenericTest_10001 | 18.50 us | 0.245 us | 0.229 us |
| NonGenericTest_10000 | 18.10 us | 0.042 us | 0.040 us |
| Method | Mean | Error | StdDev |
|---|---|---|---|
| GenericTest_10001 | 17.63 us | 0.038 us | 0.034 us |
| GenericTest_10000 | 17.85 us | 0.220 us | 0.206 us |
| NonGenericTest_10001 | 21.03 us | 0.072 us | 0.060 us |
| NonGenericTest_10000 | 14.99 us | 0.056 us | 0.052 us |
Как видите, тут все вообще неоднозначно, одно можно точно сказать, если как-то
Основные коллекции и их реализации. В чем преимущества использования коллекцией массива и связного списка?
-
List Это просто обертка над массивом, из интересного в таких обертках это увеличение массива, когда его размера не хватает. Начальный размер - 4, каждый раз происходит удвоение массива, максимальный размер Array.MaxArrayLength = 0X7FEFFFFF. Вставка - O(1), амортизированная, иногда O(n); Удаление - O(n), происходит копирование элементов в новый массив . Сортировка - нет . Поиск - O(n) . Доступ по индексу - да . Можно сделать вывод, что List, это обертка, позволяющая удалять и добавлять элементы, причем удаление очень долгое.
-
LinkedList - это уже не обертка над массивом, а двусвязный список, что добавляет свои накладные расходы(приходится хранить дополнительно SyncBlock index и ссылку на таблицу виртуальных методов для каждой ноды + ссылки на предыдущий и последующий элементы.
Вставка - O(1) . Удаление- O(1) . Сортировка - нет . Поиск - нет . Доступ по индексу - нет . Стоит предпочесть листу, когда элементы могут добавляться и удаляться, причем удаление происходит довольно часто. -
Dictionary<TKey,TValue> - Обертка над хэш-таблицей, внутри хранится массив bucket'ов и массив entries, массив bucket'ов - это int[], индекс в массиве bucket'ов это хэш код значения, а значение это номер элемента в массиве entries, в котором лежит это значение. Например:
bucket[1] = 1;
entries[0].next = -1;
entries[1].key = 5;
entries[1].next = 0;
entries[1].key = 5;Пример выше, показывает, как можно указать, чтобы первый элемент entries, имеет коллизию по хэшу и указывает на следующий элемент с таким же значением хэша. Вставка: O(1) . Удаление: O(1) . Поиск: O(1) . Доступ по индексу: напрямую нет, но индексатор определен, он принимает ключ, возвращает значение . Сортировка:нет .
-
Hashset Похож на словарь, только метод Add не кидает Exception при попытке добавления одинаковых элементов, а просто не добавляет. И еще работает только со значением без ключа. В плане алгоритмов все идентично Dictionary<TKey,TValue>.
-
Queue - обертка над массивом, RingBuffer, есть
int head`` иint tail, при добавление изменяется элементtail+1, а при удалении сдвигаетсяhead = head-1;. При расширении происходит копирование,head = 0,tail = _size``` Вставка: O(1), амортизированно, если нужна расширить, то происходит выделение нового массива и копирование Удаление: O(1)
Поиск: нет
Сортировка: нет
Доступ по индексу:нет . Конечно можно сделать и дополнительный массив, и не удваивать лист, однако, если сделать так, то пропадет локальность данных, это может быть важно, например, при массового извлечения содержимого из очереди. При удалении значение напрямую не удаляется из массива entries, но hashcode приравнивается к -1, тем самым указывая, это значение удалено. При расширении удаление также не происходит, но есть метод TrimExcess(int capacity), который может вручную пройти и выкинуть удаленные значения(этот метод создает новый массив размера capacity, и вручную проходится по старому массиву, копируя только те элементы для которых hashcode!=-1; Но если в словарь еще будет происходить добавление элементов, то не стоит запускать TrimExcess, потому что в свободные entries(которые были удалены), будут записаны новые добавленные значения. -
Stack: Реализация также на основе масссива. Все характеристики как у очереди
-
Set Устройство такое же как и у Dictionary, разница в том, что тут при вставке вычисляется хэш значения, а не ключа. Используется когда ключом может являться само значение. Все значение в Set уникальны, при попытке добавить значение, уже имеющееся в словаре(для которого hashcode'ы совпадает с уже имеющимся и equals также true) вставки не происходит. Из отличий при расширении Set выбирает первое нечетное число вдвое большее текущего размера, а Dictionary первое простое число вдвое большее текущего размера.Не содержит метода TrimAccess. Эта структура данных используется в LINQ методах связанных с множествами, например Distinct, Union,Intersect и т.д