Ответ 1
Хорошо, сначала посмотрим на простые части картины. Шипы вызваны перераспределением, копированием и сборкой мусора - нет большого сюрприза. Аномально низкие времена для нескольких первых дополнений к списку легко объясняются местностью кэш-памяти - в то время как куча все еще вписывается в память целиком, доступ к памяти может быть случайным, но при этом очень малой задержкой. Как только куча становится достаточно большой, а значение длины массива (а также значение счетчика списка) становится достаточно далеко от вставленного значения, локальность кэша становится заметным эффектом - при тестировании на моем компьютере в 32-разрядном коде x86, оптимизация для местоположения кеша улучшает производительность всего теста в четыре раза.
Однако, хотя эти эффекты хорошо объясняют как сами шипы, так и тот факт, что операции после каждого всплеска занимают больше времени, чем до всплеска, они действительно не объясняют следующую тенденцию - нет очевидной причины, почему вставка 600-го элемента должен занимать больше времени, чем вставить 550-й (при условии, что последний размер был равен 512 или около того). Профилирование прекрасно показывает, что постоянные издержки достаточно высоки, но со временем не заметно заметно увеличиваются.
Мой тестовый код обрезается до самых оснований:
var collections = new List<int>[100000];
for (var i = 0; i < collections.Length; i++)
{
collections[i] = new List<int>();
}
for (var i = 0; i < 1024; i++)
{
for (var j = 0; j < collections.Length; j++)
{
collections[j].Add(i);
}
}
Несмотря на то, что единственная абстракция, которая остается, - это сама Add, тренд все еще виден в тестовых данных, хотя я должен отметить, что моя кривая нигде не является такой же гладкой, как ваша, а отклонения огромны. Типичный цикл может занять около 20 мс, а шипы достигают 5 с.
Хорошо, пора посмотреть на разборку. Мой тестовый код очень прост (только тело внутреннего цикла):
002D0532 mov eax,dword ptr [ebp-18h]
002D0535 mov ecx,dword ptr [eax+esi*4+8]
002D0539 mov edx,ebx
002D053B cmp dword ptr [ecx],ecx
002D053D call 7311D5F0
collections ссылка хранится в стеке. Оба i и j находятся в регистрах, как и ожидалось, и на самом деле j находится в esi, что очень удобно. Итак, сначала возьмем ссылку на collections, добавим j * 4 + 8, чтобы получить фактическую ссылку на список, и сохраните ее в ecx (this в методе, который мы собираемся вызывать). i хранится в ebx, но его нужно переместить в edx, чтобы вызвать Add - нет большой передачи значения между двумя регистрами общего назначения, хотя:) Тогда есть простая оптимистическая нулевая проверка и, наконец, называть себя.
Прежде всего следует отметить, что в нем нет ветвлений, поэтому нет разветвлений неверных прогнозов. Во-вторых, у нас есть два доступа к памяти - первый находится в стеке, который в значительной степени гарантированно всегда находится в кеше. Во-вторых, хуже - это то, где мы получаем проблемы с локальным кэшем. Однако отставание от этого полностью зависит от длины (и количества) массивов, поэтому должно (и действительно) коррелировать с размерами массива.
Время для просмотра самого метода Add:) Помните, ecx содержит экземпляр списка, а edx - элемент, который мы добавляем.
Во-первых, там обычный метод пролога, ничего особенного. Затем мы проверим размер массива:
8bf1 mov esi, ecx
8bfa mov edi, edx
8b460c mov eax, DWORD PTR [esi+0xc] ; Get the list size
8b5604 mov edx, DWORD PTR [esi+0x4] ; Get the array reference
3bf204 cmp eax, DWORD PTR [edx+0x4] ; size == array.Length?
741c je HandleResize ; Not important for us
У нас есть еще три доступа к памяти. Первые два по существу идентичны, так как загружаемые значения располагаются достаточно близко. Массив будет располагаться только до первого изменения размера массива, что еще больше улучшит производительность кеша в первых нескольких вставках. Обратите внимание, что здесь не так много, что CPU может делать параллельно, но три обращения к памяти должны по-прежнему оплачивать только затраты времени ожидания. Ветвь почти всегда будет предсказана правильно - она берется только после достижения размера массива, после чего мы делаем одну и ту же ветку один раз для каждого списка.
Остаются две части: добавление самого элемента и обновление внутренней версии списка (для отказа от текущих перечислений в списке):
_items[_size++] = item;
_version++;
Это немного словнее в сборке:)
8b5604 mov edx, DWORD PTR [esi+0x4] ; get the array reference again
8b4e0c mov ecx, DWORD PTR [esi+0xc] ; ... and the list size
8d4101 lea eax, [ecx+0x1] ; Funny, but the best way to get size + 1 :)
89460c mov DWORD PTR [esi+0xc], eax ; ... and store the new size back in the list object
3b4a04 cmp ecx, DWORD PTR [edx+0x4] ; Array length check
7318 jae ThrowOutOfRangeException ; If array is shorter than size, throw
897c8a08 mov DWORD PTR [edx+ecx*4+0x8], edi ; Store item in the array
ff4610 inc DWORD PTR [esi+0x10] ; Increase the version
; ... and the epilogue, not important
Что это. У нас есть ветвь, которая никогда не будет принята (при условии однопоточной, мы уже проверяем размер массива ранее). У нас довольно много доступа: четыре, которые относятся к самому списку (включая два обновления) и еще два в массиве (включая одно обновление). Теперь, пока нет причин для промаха в кеше в списке (он почти всегда уже загружен), из-за обновлений возникают недостоверности. Напротив, доступ к массиву всегда будет приводить к провалу кеша в нашем сценарии, за исключением того, что до первого изменения размера массива. Фактически, вы можете видеть, что вначале нет промаха в кеше (массив и объект, размещенный, маленький), затем одна промашка (все еще размещена, но элемент за пределами строки кэша), затем два (как длина, так и элемент доступа за пределами строки кэша).
Это, безусловно, интересно (и может принести небольшую пользу от ручной оптимизации: P), но это снова дает нам "лестницы" на профилирующие данные. Важно отметить, что никаких ассигнований нет, поэтому нет GC.
Со всем этим в руке, я бы пришел к выводу, что List.Add действительно O (1), когда размер массива не требуется. Для очень маленьких массивов (и массивов, помеченных их refrence), есть несколько дополнительных оптимизаций, которые делают вещи быстрее, но это не важно здесь.
Таким образом, тренд, который вы видите в ваших профилирующих данных, должен быть либо экологическим, либо напрямую связан с самим профилированием, либо просто плохо выбранным методом усреднения. Например, если я запустил это на 100 000 списков:
- Добавьте первые 550 элементов
- Добавить еще 100 элементов
- И еще 100 элементов
Существует разница между временем 2 и 3, но нет тенденции - это так же вероятно, как 2, чтобы быть быстрее, так как это для 3, чтобы быть быстрее (порядка разницы в 2 мс на временных интервалах ~ 400 мс, поэтому около 0,5% отклонения). И все же, если я сделаю "разминку" с 2100 предметами, последующие шаги займут почти половину времени, как раньше. Изменение количества списков не имеет заметного эффекта для каждой коллекции (если все вписывается в вашу физическую память, конечно:)).
Хорошо, это очень заметно даже при простом Stopwatch, запущенном за пределами отладчика в режиме деблокирования, и с простой выборкой данных результата. Поэтому мы можем исключить как профилирующие эффекты, так и статистические ошибки.
Но какова может быть экологическая причина?
- GC не участвует вообще, вне массива изменяется размер. Там нет ассигнований, и профилировщик очень четко говорит о том, что никакой GC не произошло между изменениями размеров (хотя это имеет ограниченную ценность с одновременным GC:)). Настройка настроек GC делает все гораздо медленнее, но опять же, влияет только на изменения размера и их близкое окружение. Самое главное, что количество списков (и, следовательно, размер кучи) не оказывает никакого влияния на тренд, что было бы весьма неожиданным, если бы была причина GC.
- Куча фрагментирована, но очень упорядочена. Это приводит к тому, что перераспределения имеют меньшие накладные расходы под давлением памяти, но снова влияют только на размеры массива. В любом случае, это ничего удивительного и на самом деле хорошо документировано.
Итак, глядя на все это... Я понятия не имею, почему существует тренд. Однако обратите внимание, что тренд определенно не является линейным: увеличение быстро уменьшается при увеличении размера списка. От примерно 15 тыс. Элементов на тренде исчезает полностью, поэтому Add - это действительно O (1), исключая размеры массива - у него просто какое-то странное поведение при некоторых размерах:)
... если вы не предварительно выделите списки. В этом случае результаты на 100% согласуются с моими прогнозами, основанными только на локальности кэш-памяти. Что, по-видимому, говорит о том, что модели изменения размера и GCing оказывают огромное влияние на эффективность обычных алгоритмов кеширования (по крайней мере, на моем процессоре - это будет сильно отличаться, я соглашусь). Помните, когда мы говорили о промахах кеша, которые были получены во время всей операции Add? Там есть трюк - если мы сможем поддерживать достаточное количество линий кэша между двумя циклами, промаха в кеше будет предотвращена очень часто; если мы предположим, что в 64-байтной строке кэша и алгоритмах оптимальной кэш-аннулирования вы не получите пропусков в доступе к членам списка и доступе к длине массива, а всего один промах на массив один раз в 16 добавляет. Нам совсем не нужна остальная часть массива! Вам понадобится еще несколько строк кеша (например, экземпляры списка), но массивы - самая большая сделка.
Теперь сделаем математику. Сто тысяч коллекций, 2 * 64B кеша, каждый в худшем случае, добавляет до 12 MiB, и у меня есть 10 MiB кеша на мне - я могу почти подобрать все соответствующие данные массива в кеше! Теперь, конечно, я не единственное приложение (и поток), использующее этот кеш, поэтому мы можем ожидать, что точка перевертывания будет несколько ниже идеального - посмотрим, как изменение количества коллекций меняет наши результаты.
Списки, предварительно выделенные для 8000 элементов (32 кБ), добавление 2000 элементов, 100, 100
Lists A B C
400 18 1 1
800 52 2 2
1600 120 6 6
3200 250 12 12
6400 506 25 25
12800 1046 52 53
25600 5821 270 270
Ха! Довольно приятно. Тайминги красиво увеличиваются линейно с подсчетом списка, до последнего элемента - это, когда закончился наш кеш. Это где-то около 3-8 мегабайт общего использования кеша - скорее всего, это результат того, что я пренебрегаю какой-то важной вещью, которая также нуждается в кешировании, или некоторой оптимизации на части ОС или CPU, чтобы я не мог запугать весь кеш или что-то:)
Небольшая нелинейность в очень малых подсчетах списка, скорее всего, связана с медленным переполнением кэша более низкого уровня - 400 удобно помещается в моем кэше L2, 800 уже переполняется немного, 1600 - немного больше и к тому времени, когда мы достигнем 3200, кэш L2 можно пренебречь почти полностью.
И для нашей окончательной проверки, тот же сценарий, но добавив 4000 позиций вместо 2000:
Lists A B C
400 42 1 1
800 110 3 2
1600 253 6 6
3200 502 12 12
6400 1011 25 25
12800 2091 52 53
25600 10395 250 250
Как вы можете видеть, количество элементов не влияет на время вставки (за элемент), вся тренда просто исчезла.
Итак, вот оно. Тенденция вызвана GC косвенно (через субоптимальное распределение в вашем коде и шаблоны уплотнения в GC, которые нарушают локальность кэш-памяти) и переполнение кеша напрямую. При меньших количествах элементов, скорее всего, любой данный кусок требуемой памяти будет находиться в кеше прямо сейчас. Когда массивы должны быть изменены, большая часть кэшированной памяти практически бесполезна и будет медленно отменена и заменена более полезной памятью, но весь шаблон использования памяти - это нечто очень далекое от того, для чего оптимизирован процессор. В отличие от этого, сохраняя предварительно распределенные массивы, мы гарантируем, что как только у нас будет список в памяти, мы также увидим длину массива (бонус 1), а строки кэша, уже указывающие на конец массива, будут полезны для нескольких циклов (бонус 2). Поскольку нет размера массива, ни один из этих объектов не должен вообще перемещаться в памяти, и там есть хороший colocation.