.Net 2.0 - Насколько эффективны общие списки?
Я создаю приложение, которое хранит множество пользовательских данных в памяти, и в основном хранит их в List
И мне интересно ...
Насколько эффективны списки? Сколько накладных расходов памяти я получу для каждого из них? (то есть, пространство памяти в дополнение к тому, что занимают объекты, которые они содержат) Какую сумму штрафа я выплачиваю каждый раз, когда устанавливаю новый?
Есть более эффективный способ?
Словари - это просто HashTables, верно? Или это менее эффективная структура данных?
Я хотел бы использовать массивы, но у меня типичная проблема с постоянным добавлением и удалением вещей из них, поэтому необходимость увеличивать / уменьшать их было бы проблемой.
Есть идеи / предложения?
Обновлено: я знаю свои основные структуры данных 101 и почему связанный список лучше для добавления / удаления, а HashTable лучше для произвольного доступа.
Меня больше всего беспокоит идиосинкразия .Net. Например, сколько памяти тратит каждая из этих структур. И время потрачено на их инициализацию / уничтожение.
Такие вещи, как, например, если требуется много времени для создания экземпляра / сборки списка List, но не так много, чтобы очистить его, возможно, мне стоит оставить небольшой пул списков, ожидающих меня, и очистить их и отправить их обратно в пул когда это будет сделано, вместо того, чтобы просто разыменовать их.
Или, если хеш-таблицы быстрее доступны, но тратят много памяти, я мог бы предпочесть использовать списки и просматривать их для подсчета небольших элементов.
И я также действительно хотел бы сосредоточиться на использовании памяти, поскольку мое приложение чрезвычайно интенсивно использует память (подумайте, как memcached) ... Кто-нибудь знает, где я могу найти такую информацию?
Ответы 10
Списки представляют собой массивы внизу, поэтому снижение производительности при добавлении элемента, если он не находится в конце, будет очень дорогостоящим.
В противном случае они будут в основном такими же быстрыми, как массив.
List использует массив внутри, а Dictionary использует хеш-таблицу.
Они быстрее, чем старые неуниверсальные классы ArrayList и HashTable, потому что у вас нет затрат на преобразование всего в объект / из объекта (упаковка, распаковка и проверка типов), а также потому, что MS оптимизировала их лучше, чем старые классы.
Возможно, вам стоит подумать об использовании какой-либо базы данных в памяти, если у вас есть столько данных, которые должны храниться в памяти,
О какой базе данных в памяти вы думаете? Наборы данных? Насколько я понимаю, они чертовски медленные ... Или вы думаете о какой-то внепроцессной базе данных, например, о MySQL с таблицей в памяти? (или memcached?)
Во-первых, если вы собираетесь прокомментировать ответ, используйте функцию «добавить комментарий». Во-вторых, я подозреваю, что он думает о чем-то вроде SQLite (sqlite.org).
Если вам нужна эффективность при вставке или удалении в случайных местах в списке, существует структура данных LinkedList - Статья MSDN дает подробную информацию. Очевидно, что случайный доступ к связанному списку неэффективен.
Я всегда добавляю в конец списка. Много раз я удалял из середины некоторых из самых больших списков. Чем отличаются связанные списки, помимо времени вставки / удаления, от обычных списков? (память, время прохождения и т. д.)
Добавление и удаление объекта LinkedList займет меньше времени из-за характера связанных списков. Когда вы добавляете элемент, ему не нужно изменять размер массива, как это делает обычный список. Помимо этого улучшения, я подозреваю, что LinkedList будет работать примерно так же, как обычный список.
См. Это в Википедии: Связанные списки и массивы
Но разве LinkedList .Net не оборачивает каждый из моих объектов в новый объект? Разве это не приведет к потере много памяти? Меня действительно беспокоит потребность в памяти для этого приложения, я бы хотел, чтобы ее объем был как можно меньше.
@Daniel: Будучи связанными списками, они эффективны при случайных вставках и удалениях, либо отсутствуют, либо неэффективны при произвольном доступе (я не играл с ними, поэтому не знаю, что именно), и их можно перемещать от начала до конца. Если вам нужен произвольный доступ, я считаю, что List
Он оборачивает объект в объект LinkedListNode, но этот объект состоит из 4 свойств, но 3 из них являются просто ссылками на другие объекты, занимающие очень небольшой объем памяти, а 4-е - ваш фактический объект. Вы всегда можете написать свой собственный связанный список, чтобы уменьшить накладные расходы, добавленные типом .NET. Первоначально я сказал использовать структуру, но это, вероятно, также работает в C#.
Если вас беспокоит использование памяти, реальный ключ - сохранить ваш массив на диске и отобразить в память только те части, которые вам нужны в это время.
Ключ состоит в том, чтобы использовать FILE_FLAG_NO_BUFFERING и всегда читать / записывать данные размером ровно в один сектор.
К сожалению, мне все-таки нужно держать все в памяти, я думаю ... Большую часть наверняка ... Но ваш ответ открыл мне много интересных идей. Может быть, мне удастся сохранить на диске кое-что из того, что я использую реже. Есть идеи, как разрешить Windows PAGE автоматически переходить в HD? Например, могу ли я хранить свои менее часто используемые данные в отдельном процессе и каким-то образом дать этому другому процессу меньший «приоритет памяти», чем основному? Таким образом, когда системе не хватает памяти, она может сначала публиковать ТАКИЕ менее приоритетные вещи, а мои самые важные вещи хранить в ОЗУ? Я мечтаю?
Вы можете повысить вероятность того, что ваши менее часто используемые данные будут выгружаться на страницы, если будете использовать их реже.
Список .Net не использует связанный список. Это массив, по умолчанию он начинается с 4 позиций, и я думаю, что он удваивается в размере по мере добавления элементов. Таким образом, производительность может немного отличаться в зависимости от того, как вы ее используете.
Если вы используете VS 2008, запустите профилировщик, прежде чем вы слишком далеко зайдете в эту крысиную нору. Когда мы начали искать, на что мы теряем время, нам не потребовалось много времени, чтобы понять, что обсуждение тонкостей связанных списков на самом деле не имеет значения.
Хорошая идея о профайлере. Могу ли я запустить это против живого процесса на сервере, не устанавливая в него всю VS 2008? Может быть, я могу вставить туда небольшую программу, которая даст мне журнал? Какие-нибудь инструменты, похожие на профилировщик, которые позволят мне увидеть, на что используется моя память? (например, сколько экземпляров каждого класса или сколько байтов в экземплярах каждого класса)
Относительно инструментов: см. stackoverflow.com/questions/134086. Лично я добился успеха с WinDbg + SOS.
Я думаю, что двухпроцессный подход был бы излишним; плюс межпроцессное взаимодействие, вероятно, будет иметь некоторую медлительность (хотя я никогда не пробовал такую вещь, поэтому воспринимайте мое мнение как щепотку скептицизма). Я работаю над приложением, управляемым данными, где каждая единица данных крошечная, но в любой момент времени у нас может быть до миллиарда единиц данных. В основном мы используем следующие методы:
- Все находится на диске, несмотря ни на что
- Данные блокируются по «кускам»; каждый фрагмент знает, когда к нему в последний раз обращались
- Чанки перетаскиваются с диска в память, когда они нужны
- Поток с низким приоритетом отслеживает использование памяти и удаляет наименее недавно использованный материал.
Другими словами, это домашняя схема кеширования. Преимущество заключается в том, что вы можете с очень высокой точностью контролировать, какие данные находятся в памяти, чего нельзя сделать, если вы полагаетесь на схему подкачки ОС. Если какая-то часто используемая переменная оказывается смешанной с вашими данными на странице, эта страница будет подвергаться многократному обращению и не позволит ей попасть на диск. Если вы спроектируете в своем приложении приспособление, при котором одни запросы данных займут больше времени, чем другие, тогда это будет работать очень хорошо. В частности, если вы заранее знаете, какие куски вам понадобятся (мы не знаем).
Имейте в виду, что все в приложении .NET должно умещаться в пределах 2 ГБ памяти, и из-за того, как работает сборщик мусора, и накладных расходов вашего приложения, у вас, вероятно, есть несколько меньше, чем это нужно для работы.
Чтобы следить за тем, как выглядит ваша куча и кто ее выделяет, используйте Профилировщик CLR: http://www.microsoft.com/downloads/details.aspx?familyid=86ce6052-d7f4-4aeb-9b7a-94635beebdda&displaylang=en
Ограничены ли процессы .Net 2 ГБ в Windows x64? Эээ ... Ой ... Я рассчитывал на противоположное: -S
Отвечу на свой вопрос: нет, это не так.
Я думаю, что x64 позволит вам адресовать 4 ГБ, я не учел. Однако я бы не стал рассчитывать на то, что полностью избегу OutOfMemory до этого предела, поскольку сборщик мусора не будет идеально «упаковывать» ваши объекты в это пространство (фрагментация кучи).
Если вы действительно хотите увидеть все кровавые подробности того, как реализованы List и Dictionary, используйте замечательно полезный .NET Reflector.
См. Также документацию по превосходному Библиотека общих коллекций C5, в котором есть очень хорошие реализации ряда типов коллекций, отсутствующих в BCL.
Я бы и пальцем не пошевелил, пока не возникла проблема с производительностью и профилировщик не показал, что она есть. Тогда вам нужно будет решить серьезную проблему, и это будет намного проще.
Почему вы восстанавливаете эту тему сейчас, спустя более двух лет после того, как вы ее впервые опубликовали? Обратите внимание: редактируя его, вы переносите его на первую страницу. Если вы не хотите, чтобы интерес к вашему вопросу возобновился, оставьте его как есть, с бородавками и всем остальным.