Сканирование массива C# занимает больше времени для больших объектов
Просто поигрался с кодом C# и обнаружил, что время сканирования массива в памяти зависит от размера объекта.
Позвольте мне объяснить, что для двух коллекций одинаковой длины, но с разным размером объекта, время, затрачиваемое на цикл, больше для больших объектов.
Тестирование с Linqpad:
- Если у меня есть массив 20M
SimpleObjectзацикливание всех объектов занимает ~221 мс - Если у меня есть массив 20M
BigObjectзацикливание всех объектов занимает ~756 мс
Почему время не близко к постоянному? Если это не использовать kind of арифметика указателя?
Спасибо
public class SmallObject{
public int JustAnInt0;
public static SmallObject[] FakeList(int size){
var res = new SmallObject[size];
for(var c = 0; c != size; ++c)
res[c] = new SmallObject();
return res;
}
}
public class MediumObject{
public int JustAnInt0;
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
public static MediumObject[] FakeList(int size){
var res = new MediumObject[size];
for(var c = 0; c != size; ++c)
res[c] = new MediumObject();
return res;
}
}
public class BigObject{
public int JustAnInt0;
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
public int JustAnInt5;
public int JustAnInt6;
public int JustAnInt7;
public int JustAnInt8;
public int JustAnInt9;
public int JustAnInt10;
public int JustAnInt11;
public int JustAnInt12;
public int JustAnInt13;
public int JustAnInt14;
public int JustAnInt15;
public int JustAnInt16;
public int JustAnInt17;
public int JustAnInt18;
public int JustAnInt19;
public static BigObject[] FakeList(int size){
var res = new BigObject[size];
for(var c = 0; c != size; ++c)
res[c] = new BigObject();
return res;
}
}
void Main()
{
var size = 30000000;
var small = SmallObject.FakeList(size);
var medium = MediumObject.FakeList(size);
var big = BigObject.FakeList(size);
var sw = System.Diagnostics.Stopwatch.StartNew();
for(var c = 0; c != size; ++c){
small[c].JustAnInt0++;
}
string.Format("Scan small list took {0}", sw.ElapsedMilliseconds).Dump();
sw.Restart();
for(var c = 0; c != size; ++c){
medium[c].JustAnInt0++;
}
string.Format("Scan medium list took {0}", sw.ElapsedMilliseconds).Dump();
sw.Restart();
for(var c = 0; c != size; ++c){
big[c].JustAnInt0++;
}
string.Format("Scan big list took {0}", sw.ElapsedMilliseconds).Dump();
}
// Define other methods and classes here
ОБНОВИТЬ:
В этом случае комментарий @IanMercer, а также @erisco, указали мне правильное направление, поэтому после небольшой настройки объектов я получаю ожидаемое поведение. В основном то, что я сделал, это обернул дополнительные данные в объект. Таким образом, малые, средние и большие имеют более или менее одинаковый размер, способный соответствовать кэш-памяти ЦП. Теперь тест показывает то же время.
public class SmallObject{
public int JustAnInt0;
public static SmallObject[] FakeList(int size){
var res = new SmallObject[size];
for(var c = 0; c != size; ++c)
res[c] = new SmallObject();
return res;
}
}
public class MediumObject{
public int JustAnInt0;
public class Extra{
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
}
public Extra ExtraData;
public static MediumObject[] FakeList(int size){
var res = new MediumObject[size];
for(var c = 0; c != size; ++c)
res[c] = new MediumObject();
return res;
}
}
public class BigObject{
public int JustAnInt0;
public class Extra{
public int JustAnInt1;
public int JustAnInt2;
public int JustAnInt3;
public int JustAnInt4;
public int JustAnInt5;
public int JustAnInt6;
public int JustAnInt7;
public int JustAnInt8;
public int JustAnInt9;
public int JustAnInt10;
public int JustAnInt11;
public int JustAnInt12;
public int JustAnInt13;
public int JustAnInt14;
public int JustAnInt15;
public int JustAnInt16;
public int JustAnInt17;
public int JustAnInt18;
public int JustAnInt19;
}
public Extra ExtraData;
public static BigObject[] FakeList(int size){
var res = new BigObject[size];
for(var c = 0; c != size; ++c)
res[c] = new BigObject();
return res;
}
}
void Main()
{
var size = 30000000;
var small = SmallObject.FakeList(size);
var medium = MediumObject.FakeList(size);
var big = BigObject.FakeList(size);
var times = Enumerable
.Range(0, 10)
.Select(r => {
var sw = System.Diagnostics.Stopwatch.StartNew();
for(var c = 0; c != size; ++c){
small[c].JustAnInt0++;
}
// string.Format("Scan small list took {0}", sw.ElapsedMilliseconds).Dump();
var smalltt = sw.ElapsedMilliseconds;
sw.Restart();
for(var c = 0; c != size; ++c){
big[c].JustAnInt0++;
}
// string.Format("Scan big list took {0}", sw.ElapsedMilliseconds).Dump();
var bigtt = sw.ElapsedMilliseconds;
sw.Restart();
for(var c = 0; c != size; ++c){
medium[c].JustAnInt0++;
}
//string.Format("Scan medium list took {0}", sw.ElapsedMilliseconds).Dump();
var mediumtt = sw.ElapsedMilliseconds;
return new {
smalltt,
mediumtt,
bigtt
};
})
.ToArray();
(new {
Small = times.Average(t => t.smalltt),
Medium = times.Average(t => t.mediumtt),
Big = times.Average(t => t.bigtt)
}).Dump();
}
Несколько полезных ссылок:
- http://igoro.com/archive/gallery-of-processor-cache-effects/
- https://msdn.microsoft.com/en-us/library/ms973852.aspx
- https://technet.microsoft.com/en-us/sysinternals/cc835722.aspx
Спасибо вам всем!
3 ответа
Мой ответ - чистое предположение, но, надеюсь, он предлагает некоторые вещи для проверки и исключения.
public static SmallObject[] FakeList(int size){
var res = new SmallObject[size];
for(var c = 0; c != size; ++c)
res[c] = new SmallObject();
return res;
}
FakeList выделяет много объектов один за другим и сохраняет их в массиве. Распределитель будет хранить все эти объекты непрерывно. В поколенческом GC распределение выполняется путем увеличения указателя (поиск свободных мест отсутствует) (см. Здесь).
Допустим, служебные данные для объекта составляют 16 байтов. Исходя из этого, давайте угадать размер SmallObject составляет 20 байтов, MediumObject составляет 36 байт, и BigObject составляет 96 байтов.
Итак, у нас есть три массива объектов, хранящихся непрерывно. Когда процессор выбирает целые 4 байта, он также выбирает группу памяти, смежную с целым числом (чтение по кэшу ЦП и строкам кеша). Допустим, процессор выбирает 64 байта за раз.
Сколько объектов помещается в строку кэша?
0 20 40 60 84
| SmallObject | SmallObject | SmallObject | SmallObject |
0 36 72
| MediumObject | MediumObject |
0 96
| BigObject |
Примечание: мы не рассматриваем выравнивание данных здесь.
Строка кэша соответствует 3, 2 SmallObjects, 1,77 MediumObjects и 0,66 BigObjects.
Мы увеличиваем JustAnInt0 в цикле, который оказывается первым полем объекта. Компилятор, вероятно, размещает поля в том же порядке, в котором вы их объявили (поскольку все они являются целыми числами, в противном случае, возможно, он переупорядочивает их для выравнивания памяти).
Принимая это во внимание, скажем JustAnInt0 это байты с 16 по 20 во всех SmallObject, MediumObject и BigObject. Это означает, что мы можем получить 3 JustAnInt0от SmallObjects сразу, 2 JustAnInt0от MediumObject сразу, и только 1 JustAnInt0 от BigObject сразу.
Поэтому причина, по которой вы можете увеличить JustAnInt0 самый быстрый на SmallObject массив, потому что процессор может загрузить три JustAnInt0сразу в локальный кеш. Это означает, что требуется треть обращений к основной памяти по сравнению с BigObject, Доступ к основной памяти на порядок на два порядка медленнее, чем доступ к кэшу ЦП (см. Здесь). Доступ к основной памяти является одной из самых медленных инструкций для вашего процессора и может доминировать в общей стоимости времени алгоритма.
Опять же, это все спекуляция. Единственный реальный способ узнать это - понять ваше оборудование и провести некоторое тестирование. Надеюсь, это станет отправной точкой для начала расследования.
Разве это не должно использовать вид арифметики указателей?
Хотя CLR действительно использует "арифметику указателей" для определения местоположения элемента в памяти, то, что происходит дальше, происходит по-другому: как только вы начинаете доступ JustAnInt0s, CLR начинает читать данные из этих указателей.
Вот тут-то и запутывается: современное оборудование сильно оптимизировано для кеша, поэтому, когда вы запрашиваете JustAnInt0аппаратное обеспечение предсказывает, что JustAnInt1, JustAnInt2и так далее, будем следовать, потому что для большинства реальных программ это так. Это называется местностью ссылки. Количество предметов, которые загружаются вместе с JustAnInt0 зависит от размера строки кэша в вашем оборудовании. Когда объект маленький, а строка кэша большая, один или два объекта в соседних областях памяти также могут быть загружены.
Похоже, что когда объект маленький, ваша программа непреднамеренно использует преимущество ссылочной локализации, потому что несколько маленьких объектов оказываются в кеше при доступе small[c],
Это поведение зависит от небольших объектов, расположенных рядом друг с другом. Если вы примените случайное перемешивание к small, medium, а также big, время доступа должно стать намного ближе.
Как говорит другой ответ, это из-за кэширования процессора и других оптимизаций.
Smaller arrays: level 1 cache (very fast)
Larger arrays: level 2 cache (fast)
Huge arrays: not cached (normal)
Gigantic arrays: paged to disk (slow)
Смотрите это простое объяснение.