Производительность коллекции .Net для особого случая использования
Я ищу хорошую отправную точку для моего варианта использования. Мой вариант использования несколько особенный, поэтому простой тест производительности со всеми доступными коллекциями не поможет. Производительность – это все. Потребление памяти может быть сколько угодно, меня это не волнует.
Примечание. Я уже пробовал кое-что с экземплярами SortedDictionary. Но мне интересно, подойдут ли какие-нибудь другие коллекции лучше. Я также сам реализую решение, если существует более совершенный алгоритм для обработки этих вещей, поэтому нет необходимости придерживаться существующих реализаций.
Вариант использования такой.
В форме {BigInterger key1, Guid key2, BigInteger quantity} есть некоторая структура данных. Guid не является случайным, а генерируется так, что каждый новый Guid имеет более высокую ценность, чем предыдущий.
Примечание. Я начал с SortedDictionary, используя ключ1 в качестве ключа и удерживая другой SortedDictionary, используя ключ2 в качестве ключа, но пришел к выводу, что, возможно, лучше использовать более плоскую структуру данных только с одним SortedDictionary, использующим ключ1+ключ2.
Требования
- Вставки могут быть случайными, однако большинство вставок будут происходить в топ-100 элементов, отсортированных по ключу. Вставки всегда представляют собой отдельные элементы.
- Команда «Удалить элементы» всегда сначала удаляет первые n элементов. Таким образом, с точки зрения удаления коллекция похожа на стек. Удалить всегда удаляет от 1 до n элементов.
- Поиск не является случайным, но возвращает все n верхних элементов с ключами ниже или равными ключу поиска.
- Поиск также должен фильтроваться по количеству. Таким образом, поиск будет принимать параметр количества. Товары возвращаются до тех пор, пока количество всех возвращаемых товаров не превышает искомое количество. Кроме того, все возвращенные предметы будут удалены из коллекции.
- Операция вставки/удаления всегда выполняется после операции поиска. Возможные цепочки операций: (поиск [15%], поиск->вставка [15%], поиск->удаление [15%], поиск->удаление->вставка [55%]). Вероятности — это предположения, и невозможно заранее предсказать, что произойдет чаще.
- Коллекция будет содержать от 1 до 100 миллионов предметов. Может быть, даже больше.
Примечание. Я также думал об использовании связанного списка. возможно, они подходят для этого лучше, чем SortedDictionary.
Каков будет ваш подход к этому?
Примечание. Текущее состояние: сравнение производительности между SortedDictionary<BigInteger, SortedDictionary<Guid, OrderData>>» и SortedDictionary<MergedKey, OrderData>
Результаты на данный момент
Я также подумал об использовании связанного списка. Связанные списки, как правило, плохо влияют на эффективность кэша, и это очень важная проблема. Ваш вариант использования звучит так, как будто он должен быть достаточно дружественным к кэшу, поскольку кажется, что к вершине обращаются чаще всего.
В вашем вопросе упоминаются ключи, но у вас есть два ключа, которые используются для поиска? Вам действительно нужно использовать BigInt? Если вам удастся использовать int64 или int128, это может значительно помочь с локальностью данных и использованием памяти. Знание распределения количеств, а также ожидаемых значений запроса также может помочь.
Ответы 1
Использование отсортированного массива
Давайте рассмотрим алгоритмическую сложность ваших операций с использованием отсортированного (динамического) массива. Предположим также, что для сортировки и поиска используется один ключ.
Вставки могут быть случайными, однако большинство вставок будут происходить в топ-100 элементов, отсортированных по ключу. Вставки всегда представляют собой отдельные элементы.
Таким образом, в типичном случае требуется перемещение ~ 50 элементов, т. е. O (1), и я бы не стал беспокоиться о постоянной времени для 50 элементов. В худшем случае будет O(n). Существует также штраф за перераспределение для динамических массивов, но этого можно избежать, установив достаточно большую начальную емкость.
Команда «Удалить элементы» всегда сначала удаляет первые n элементов. Таким образом, с точки зрения удаления коллекция похожа на стек. Удалить всегда удаляет от 1 до n элементов.
Это должно занять постоянное время, т.е. O(1), поскольку вы будете изменять только свойство count.
Поиск не является случайным, но возвращает все n верхних элементов с ключами ниже или равными ключу поиска.
Это будет означать бинарный поиск, чтобы найти самый большой ключ, меньший, чем ключ поиска, O(log n), и тогда должно быть тривиально вернуть диапазон для данного диапазона.
Поиск также должен фильтроваться по количеству. Таким образом, поиск будет принимать параметр количества. Товары возвращаются до тех пор, пока количество всех возвращаемых товаров не превышает искомое количество. Кроме того, все возвращенные предметы будут удалены из коллекции.
Если я правильно понимаю, вы все равно выполняете двоичный поиск, как указано выше, с последующим повторением значений до тех пор, пока сумма количеств не сравняется со значением запроса. Это должно занять O(log n + m), где m — количество возвращаемых элементов.
Заключение
Большинство операций должно быть O(log n) или лучше, и это очень хорошо. Даже если существуют структуры данных, поддерживающие O(1), вам необходимо учитывать постоянную времени. Фактическое время выполнения может во многом зависеть от эффективного использования кэша.
Насколько мне известно, не существует встроенной коллекции, которая бы эффективно поддерживала все эти операции «из коробки». Поэтому я бы, вероятно, просто создал свой собственный, используя List<T> или простой массив в качестве резервного хранилища, существуют существующие методы двоичного поиска как для списка, так и для массива, которые можно использовать. Массив допускает доступ к более низкому уровню, но требует, чтобы вы сами обрабатывали увеличение размера, если это необходимо.
Если профилирование предполагает, что вставки занимают слишком много времени из-за худшего случая O(n), возможно, вам стоит взглянуть на что-то вроде списка пропуска или развернутого связанного списка. Но у меня недостаточно опыта работы с ними, чтобы предложить что-то конкретное.
Другие примечания
Я бы постарался держаться подальше от BigInt, если производительность вызывает беспокойство. Для значений менее 32 бит BigInt будет использовать 12 байт. Для значений в диапазоне 32–64 бит будет использоваться 36 байт. BigInt также медленнее, поскольку операции будут включать в себя циклы и ветвления. Поэтому, если вы можете использовать типы фиксированного размера, такие как int64 или int128, это может значительно помочь с использованием кэша и производительностью. Если значения, превышающие int128, существуют, но встречаются редко, возможно, лучше рассматривать их как особый случай.
Я бы, вероятно, рекомендовал использовать структуру вместо класса, чтобы уменьшить использование памяти и косвенность. Вы можете использовать Span , в параметрах и т. д., чтобы уменьшить накладные расходы на копирование.
Я бы порекомендовал Benchmark .net для оценки. Это должно помочь обеспечить хорошие измерения. Просто обязательно напишите репрезентативные тестовые примеры.
Дело не только в том, что BigInteger использует много памяти, но и в том, что его операции ОЧЕНЬ медленны. Все они используют циклы и побайтовую обработку, и вам придется выполнять много хеширования (в исходном коде словаря, а не в вашем), проверки на равенство и сравнения. Также существуют специализированные реализации Int256 с использованием AVX2, которые демонстрируют более чем 20-кратное улучшение по сравнению с BigInteger.
Спасибо за вклад. В настоящий момент я экспериментирую с вариантом списка пропуска, чтобы посмотреть, даст ли он какие-либо преимущества. Я не знал о развернутых связанных списках, но я изучу это. На самом деле я уже использую структуру в качестве контейнера данных, чтобы уменьшить использование памяти. Я обязательно посмотрю на Benchmark.net. На данный момент я использую для этого MSTest с StopWatch. К сожалению, я не могу избавиться от того, что BigInteger, key1 в моем примере представляет собой значение, представляющее число с 18 десятичными знаками, хранящееся как натуральное число, просто умноженное на 10 ^ 18. Я не знаю ни одного другого типа данных, который мог бы хранить такие большие числа.
@Blindy, о Int256 и даже тип данных UInt256. Это интересно. И я думаю, что он тоже будет достаточно большим... спасибо за совет.
@lamanSwtrse uint64 должен поддерживать до 1.8446744e+19, uint128 будет обрабатывать 3.4028237e+38. Так что 18 десятичных цифр не должны быть проблемой. Но если это «ключ», действительно ли это должно быть фактическое число, а не просто поддерживать ограниченный набор операций, таких как равенство и сравнение? А что касается «количества», что вы считаете, когда 1e+38 недостаточно, но вам все равно нужен точный подсчет?
@Blindy Короткое обновление. Я только что заменил BigInteger на UInt256 и использовал структуру Key, которая предоставляет только функции сравнения, необходимые для комбинированного ключа, вместо BigInteger (UInt256 был слишком мал). Я сделал это, а затем запустил тесты Insert. Однако результат несколько неожиданный. При этом время, необходимое для добавления 1 предмета, в каждом случае сокращается вдвое. Добавление элементов 1M, 10M, 100M показывает либо точно такую же производительность, что и вариант BigInteger, либо немного худшую производительность. Это могут быть мои тестовые примеры, но они в основном предназначены только для циклов, вызывающих метод Insert запрошенное количество раз.
@JonasH Значения могут увеличиваться и в левой части десятичной точки. Технически контракты Ethereum хранят суммы токенов в типе данных uint256, поэтому в данном случае это будет верхняя граница. Однако мои тесты показывают, что реализация Nethereum Uint256 не имеет никаких преимуществ в производительности по сравнению с BigInteger, по крайней мере, если она помещена в SortedDictionary. Чтобы ключ был уникальным, мне понадобится uint256+uint128 (значение, используемое в контракте+guid). Даже если мы говорим, что цифры никогда не станут такими высокими. Но значения в контракте могут, и моя библиотека C# должна справиться с этим.
@all Спасибо за все отзывы, особенно за совет по BenchmarkDotNet, о котором я раньше не знал. Сейчас я уточнил свои тесты с помощью BenchmarkDotNet. Это действительно прояснило многие вещи, хотя правильное написание тестов было немного сложным. В настоящий момент я экспериментирую с тремя пользовательскими типами коллекций: 1) SkipList 2) CacheSensitiveSkipList 3) Список пропуска, оптимизированный для использования в кэше. 2 и 3 выглядят очень многообещающе.
Если производительность имеет решающее значение, то какая операция имеет наибольшую значимость. Вставить, удалить, найти? Вы не получите «оптимального» поведения для всех трех операций одновременно. Так что вам нужно решить.