Большой объект Heap friendly IDictionary

У нас есть приложение, которое содержит большое количество объектов в нескольких Dictionary s, некоторые из которых постоянно растут в течение всего жизненного цикла приложения (торговое приложение с множеством инструментов и постоянно растущими заказами/сделками).

У нас возникают проблемы с OutOfMemoryException из-за фрагментации кучи больших объектов.

Чтобы противостоять этому, я попытался написать "большой" словарь, который реализован как двухуровневый словарь, где все листовые словари недостаточно велики для распределения на LOH. Я использовал последовательный алгоритм хэширования, чтобы избежать необходимости перефразировать весь словарь, когда одно ведро становится слишком большим. Согласованный хеширующий "круг" представляет собой TreeDictionary из библиотеки коллекций C5.

Мой вопрос: есть ли какие-нибудь лучшие структуры данных (или, возможно, лучшие реализации того, что я описал) для С#?

Обновление

Это реализация для "большого" словаря: https://gist.github.com/956621

Я понимаю, что это не безошибочно, так как в спецификации не указано ни порог кучи LOH, ни размер каждого словаря или алгоритма масштабирования. Однако в настоящее время это лучшее, что я могу придумать, чтобы избежать взрыва приложения в середине дня.

Ответ 1

Словарь - это неудачная структура данных, когда она является самой большой в вашем приложении. Хэш-таблица часто удваивается по размеру, когда она становится слишком заполненной и требует 150% -ного общего назначения во время изменения размера, в критический момент. Хэш-таблица работает превосходно, когда она гигантская, но требует последовательного распределения, которое подчеркивает алгоритмы кучи.

Вы можете уменьшить эти недостатки с помощью многоуровневых хеш-таблиц, например, используя байт хэш-кода в качестве индекса в 256 хэш-таблицах. Это добавляет некоторые накладные расходы наверняка, но что более важно, эта и другие стратегии наполнены опасностью, путаясь случайностью, например, с хэш-кодами, которые вы получаете, и потенциально делаете что-то много, намного худшее по производительности. Использование этого подхода требует хорошей теоретической основы и твердых эмпирических испытаний. Но он может работать.

Другая стратегия заключается в том, чтобы предварительно выделить самую большую структуру данных для наихудшего случая и распределить ее на ранней стадии. Никакого мелкозернистого выделения не требуется, но теперь вы сталкиваетесь с призраком катастрофического отказа, если он когда-либо закончится. Это вариант.

Ответ 2

Я думаю, что это требует изменения алгоритма.

Из того, что я слышал и понял, GC неплохо разбирается и дефрагментирует память. Таким образом, ваш пролет основывается на простом факте, что вы сохраняете слишком много данных в памяти.

Сколько данных вы храните в памяти?

Вы думали об использовании базы данных? компактного может быть достаточно.

Или просто скажите своему клиенту, что для правильного запуска вашего приложения ему требуется 16 ГБ памяти. И если вашему приложению нужны все эти 16 ГБ памяти, то, безусловно, что-то не так.

Edit: Глядя на вашу проблему с другой стороны, и после прочтения вашего редактирования у меня возник вопрос: насколько велики ваши объекты? Или они содержат длинные списки или массивы? Как часто вы удаляете/добавляете эти объекты?

Я думаю, что проблема может быть не в самом словаре, а в объектах, которые слишком велики и слишком часто удаляются/добавляются. Возможно, использование какой-либо ловли или пула может оказаться выгодным. И если вы используете списки, тогда создайте эти списки с предварительно выделенным.

И, возможно, использование imutable structs вместо изменчивых классов может облегчить фрагментацию.