.Net 2.0-Насколько эффективны общие списки?




performance generics (7)

Я создаю приложение, которое содержит множество загрузок пользовательских данных в памяти, и в основном это сохраняет все в структурах List <T> (и некоторый словарь <T, T>, когда мне нужно найти).

И мне интересно ...

Насколько эффективны списки? Сколько накладных расходов памяти я получаю для каждого из них? (то есть, пространство памяти в дополнение к тому, что будут содержать объекты, которые они содержат). Сколько штрафа я плачу каждый раз, когда я экземпляр нового?

Есть ли более эффективный способ?

Словари - это просто хэш-таблицы, верно? Или это менее эффективная структура данных?

Я бы хотел использовать массивы, но у меня есть типичная проблема добавления и удаления вещей от них все время, поэтому необходимость выращивать / сжимать их будет больно.

Любые идеи / предложения?

Изменить: я знаю основные базовые структуры данных 101 и почему Linked List лучше добавлять / удалять, а HashTable лучше для Random Access.

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

Такие вещи, как, например, если для экземпляра требуется много времени / GC List, но не так много, чтобы очистить его, возможно, мне нужно оставить немного пула списков, ожидающих меня, и очистить их и отправить обратно в пул когда это делается, а не просто разыгрывать их.

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

И я также очень хотел бы сосредоточиться на использовании памяти, поскольку мое приложение интенсивно использует память (думаю, memcached) ... Кто-нибудь знает, где я могу найти такую ​​информацию?


Возможно, вам стоит рассмотреть возможность использования какой-либо базы данных в памяти, если у вас есть много данных, которые должны храниться в памяти,


Если вам нужна эффективность при вставке или удалении случайно выбранных мест в списке, есть структура данных LinkedList - в статье MSDN дается подробная информация. Очевидно, что случайный доступ связанного списка неэффективен.


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

См. Это в Википедии: Связанные списки против массивов


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

В противном случае они будут в основном такими же быстрыми, как массив.


Я думаю, что проблема с двумя процессами может быть излишней; плюс межпроцессное общение, вероятно, будет иметь некоторую медлительность (хотя я никогда не пробовал такую ​​вещь, поэтому я считаю, что это как соль). Я работаю над приложениями, основанными на данных, где каждый блок данных крошечный, но у нас может быть более миллиарда единиц данных в любой момент времени. Метод, который мы используем, в основном:

  • Все находится на диске, независимо от того, что
  • Данные блокируются в «куски»; каждый кусок знает, когда последний доступ
  • Чанки перетаскиваются с диска в память, когда они необходимы
  • Низкоприоритетный поток отслеживает использование памяти и удаляет наименее недавно используемые материалы

Другими словами, это схема кэширования доморощенного. Преимуществом является то, что вы можете точно контролировать то, что данные хранятся в памяти, чего вы не можете, если будете полагаться на схему подкачки ОС. Если какая-то часто используемая переменная заканчивается смешением с вашими данными на странице, эта страница будет многократно ударяться и помешать ей перейти на диск. Если вы создадите в своем приложении размещение, в котором некоторые запросы данных будут занимать больше времени, чем другие, то это будет работать очень хорошо. В частности, если вы знаете, какие куски вам понадобятся раньше времени (мы этого не делаем).

Имейте в виду, что все в приложении .NET должно быть в пределах 2 ГБ памяти, и из-за того, как работает GC и накладных расходов на ваше приложение, вы, вероятно, несколько меньше, чем для работы.

Чтобы посмотреть, как выглядит ваша куча и кто распределяет, используйте профилировщик CLR : http://www.microsoft.com/downloads/details.aspx?familyid=86ce6052-d7f4-4aeb-9b7a-94635beebdda&displaylang=en


Если вы действительно хотите увидеть все детали gory о том, как List <> и Dictionary <,> реализованы, используйте чудесно полезный .NET Reflector .

См. Также документацию для отличной C5 Generic Collection Library , которая имеет очень хорошие реализации ряда типов коллекций, отсутствующих в BCL.


Список .Net не использует связанный список. Это массив, он начинается с 4 позиций по умолчанию, и я думаю, что он удваивается по размеру, когда вы добавляете вещи. Таким образом, производительность может немного отличаться в зависимости от того, как вы ее используете.

Если вы используете VS 2008, прогоните профайлер, прежде чем вы окажетесь слишком далеко от этой крысиной дыры. Когда мы начали смотреть на то, где мы теряем время, не нужно долго размышлять над тем, что обсуждение тонкостей связанных списков просто не имеет значения.







memory