// Перебор списка 2
var lst2 = new ArrayListBase<double> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
T = DateTime.Now;
for (int i = 0; i < count; i++)
for (int j = 0, length = lst2.Count; j < length; j++)
lst2[j]++;
Console.WriteLine(" Перебор списка 2 : " + (DateTime.Now - T));
NET быстрая работа с содержимым List<T>
Вообщем. Пишу на C# библиотеку для которой очень важна скорость.
И есть в ней, скажем так критический участок, который состоит из 2х фаз:
Фаза 1: Заполнение списка List<T>
Фаза 2: N-кратная Индексация по списку(перебор элементов)
Соответственно поскольку индексирование по списку более чем в 2 раза медленне чем по массиву есть желание добавить промежуточную фазу:
Фаза 1.5: List<T>.ToArray()
И в дальнейшем индексировать уже массив. И при больших N это себя оправдает, НО(!) нет уверенности что N будет большим. А при небольших N именно List<T>.ToArray() станет критической и ненужной операцией.
Следовательно пришлось отказаться от использования List<T>.ToArray();
На ум пришла рефлексия:
Но ее недостатки - она сама по себе медленная.
Что же тут на ум пришло? - покопаться в IL.
Внутренности класса Lisy<int> выглядит следующим образом:
Причем массив идет первым(!) полем класса.
Любой ссылочный тип в IL - это ссылка на первое поле со смещением 4байта для x32 и 8байт для x64.
Немного пошаманив с IL получил следующий код:
Скорость работы DeCapsulate<T[]>(List<T>) примерно в 700 раз выше чем через рефлексию.
Но вот вопрос который меня мучает - образуется ли строгая ссылка на массив? Не приведут ли мои манипуляции к конфлику во время сборки мусора?
Т.е. если ссылок на List<T> больше не остается то он попадает под "уборку мусора". Но если перед тем, как умрет последняя ссылка я с помощью DeCapsulate<T[]> извлеку из списка массив, то он ведь не попадет под уборку мусора?....
Буду рад советам, идеям...
И есть в ней, скажем так критический участок, который состоит из 2х фаз:
Фаза 1: Заполнение списка List<T>
Фаза 2: N-кратная Индексация по списку(перебор элементов)
Соответственно поскольку индексирование по списку более чем в 2 раза медленне чем по массиву есть желание добавить промежуточную фазу:
Фаза 1.5: List<T>.ToArray()
И в дальнейшем индексировать уже массив. И при больших N это себя оправдает, НО(!) нет уверенности что N будет большим. А при небольших N именно List<T>.ToArray() станет критической и ненужной операцией.
Следовательно пришлось отказаться от использования List<T>.ToArray();
На ум пришла рефлексия:
Код:
FieldInfo Fi = typeof(List<int>).GetField("_items", BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic);
var Lst = new List<int> { 1, 2, 3, 4, 5 };
int[] Arr = Fi.GetValue(Lst) as int[];
var Lst = new List<int> { 1, 2, 3, 4, 5 };
int[] Arr = Fi.GetValue(Lst) as int[];
Но ее недостатки - она сама по себе медленная.
Что же тут на ум пришло? - покопаться в IL.
Внутренности класса Lisy<int> выглядит следующим образом:
Код:
public class List`1[T]
{
T[] _items;
Int32 _size;
Int32 _version;
Object _syncRoot;
}
{
T[] _items;
Int32 _size;
Int32 _version;
Object _syncRoot;
}
Причем массив идет первым(!) полем класса.
Любой ссылочный тип в IL - это ссылка на первое поле со смещением 4байта для x32 и 8байт для x64.
Немного пошаманив с IL получил следующий код:
Код:
.method public hidebysig static !!TOutput
DeCapsulate<TOutput>(object 'class') cil managed
{
// Code size 17 (0x11)
.maxstack 8
IL_0000: ldarga.s 'class' //загрущить адрес объектра в стек вычислений.
IL_0002: conv.u //конверсировать его в int8
IL_0003: ldind.i //поместить в стек размер смещения
IL_0004: sizeof void* //вычислить размер смещения (для платформонезависимости)
IL_000a: add //добавить к адресу смещение
IL_000b: ldobj !!TOutput //копировать объект с типом значения, размещенный по указанному адресу, на вершину стека вычислений.
IL_0010: ret //завершить
} // end of method Kernel::DeCapsulate
DeCapsulate<TOutput>(object 'class') cil managed
{
// Code size 17 (0x11)
.maxstack 8
IL_0000: ldarga.s 'class' //загрущить адрес объектра в стек вычислений.
IL_0002: conv.u //конверсировать его в int8
IL_0003: ldind.i //поместить в стек размер смещения
IL_0004: sizeof void* //вычислить размер смещения (для платформонезависимости)
IL_000a: add //добавить к адресу смещение
IL_000b: ldobj !!TOutput //копировать объект с типом значения, размещенный по указанному адресу, на вершину стека вычислений.
IL_0010: ret //завершить
} // end of method Kernel::DeCapsulate
Код:
var Lst = new List<int> { 1, 2, 3, 4, 5 };
int[] Arr = Kernel.DeCapsulate<int[]>(Lst);
int[] Arr = Kernel.DeCapsulate<int[]>(Lst);
Скорость работы DeCapsulate<T[]>(List<T>) примерно в 700 раз выше чем через рефлексию.
Но вот вопрос который меня мучает - образуется ли строгая ссылка на массив? Не приведут ли мои манипуляции к конфлику во время сборки мусора?
Т.е. если ссылок на List<T> больше не остается то он попадает под "уборку мусора". Но если перед тем, как умрет последняя ссылка я с помощью DeCapsulate<T[]> извлеку из списка массив, то он ведь не попадет под уборку мусора?....
Буду рад советам, идеям...
мне вот тоже стало интересно, сейчас ковыряюсь.
Цитата:
поскольку индексирование по списку более чем в 2 раза медленне чем по массиву
поясните, как и что делаете
deleted
//хотя я кажется сообразил, просто не внимательно читал
Цитата: bagie2
поясните, как и что делаете
Что конкретно пояснить?
1. Зачем мне это?
2. Или как это делается(IL код)?
P.S. Кстати если интересно - прицепляю готовую библиотеку в которую я запихал IL код.
Кстати провел тестирование по поводу скорости индексации:
Код:
DateTime T;
int count = (int)1e+7;
Console.WriteLine("Число итераций : " + count);
// Перебор списка
var lst = new List<double> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
T = DateTime.Now;
for (int i = 0; i < count; i++)
for (int j = 0, length = lst.Count; j < length; j++)
lst[j]++;
Console.WriteLine(" Перебор списка : " + (DateTime.Now - T));
// Перебор списка с извлечением
T = DateTime.Now;
for (int i = 0; i < count; i++)
{
var arr = Kernel.DeCapsulate<double[]>(lst); // извлечение
for (int j = 0, length = lst.Count; j < length; j++)
arr[j]++;
}
Console.WriteLine(" Перебор c извлечением массива : " + (DateTime.Now - T));
int count = (int)1e+7;
Console.WriteLine("Число итераций : " + count);
// Перебор списка
var lst = new List<double> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
T = DateTime.Now;
for (int i = 0; i < count; i++)
for (int j = 0, length = lst.Count; j < length; j++)
lst[j]++;
Console.WriteLine(" Перебор списка : " + (DateTime.Now - T));
// Перебор списка с извлечением
T = DateTime.Now;
for (int i = 0; i < count; i++)
{
var arr = Kernel.DeCapsulate<double[]>(lst); // извлечение
for (int j = 0, length = lst.Count; j < length; j++)
arr[j]++;
}
Console.WriteLine(" Перебор c извлечением массива : " + (DateTime.Now - T));
Число итераций : 10000000
Перебор списка : 00:00:00.5205078
Перебор c извлечением массива : 00:00:00.2822266
Как и говорил - почти в 2 раза;
P.S. Кстати опытным путем установлено что GC не захватит извлеченный объект. ))))
вот что у меня получилось
Число итераций : 10000000
Перебор списка : 00:00:01.6875000
Перебор списка 2 : 00:00:00.3906250
Перебор c извлечением массива : 00:00:00.4843750
я к тому, что наверное лучше реализовать свой аналог List, поубирать внутри лишние проверки можно например на границы индексов. там есть не очень понятные мне штуки в коде, например метод Add внутри используется Array.Copy вместо Array.Resize, второй у меня намного шустрее работает и не надо создавать временных массивов (+экономия памяти)
у меня ошибки еще есть в реализации ArrayListBase
Цитата:
Число итераций : 10000000
Перебор списка : 00:00:01.6875000
Перебор списка 2 : 00:00:00.3906250
Перебор c извлечением массива : 00:00:00.4843750
правда в Debug конфигурации и под отладчиком второй вариант оочень долго (8 сек) работает нов релизе и без отладчика так
Код:
я к тому, что наверное лучше реализовать свой аналог List, поубирать внутри лишние проверки можно например на границы индексов. там есть не очень понятные мне штуки в коде, например метод Add внутри используется Array.Copy вместо Array.Resize, второй у меня намного шустрее работает и не надо создавать временных массивов (+экономия памяти)
у меня ошибки еще есть в реализации ArrayListBase
А почему бы не работать с банальным массивом?
Цитата: bagie2
вот что у меня получилось правда в Debug конфигурации и под отладчиком второй вариант оочень долго (8 сек) работает
Ваш List действительно более быстрый. СSC его хорошо компилит. Кэширует размер и не проверяет индексы.
А при моем извлечении вылазит пресловутая проверка индексов.
Цитата: bagie2
нов релизе и без отладчика так я к тому, что наверное лучше реализовать свой аналог List, поубирать внутри лишние проверки можно например на границы индексов.
Цитата: hardcase
А почему бы не работать с банальным массивом?
Желательно все же работать именно с List<T> потому что предполагается передача имненно List<T> пользователем в качестве параметра.
Хотя теперь наверное будет предусмотрен и вариант передачи пользователем массива.
bagie2 спасибо за помощь!
Цитата: sigmov
предполагается передача имненно List<T> пользователем в качестве параметра
Почему бы не ограничивать пользователя в выборе коллекции и принимать от пользователя экземпляр IEnumerable<T>. А полученное перечисление далее приводить к известным типам.