Память: LOH и Chunked Lists

    Управляемая память в .Net поделена на стек и несколько хипов. Самые важные из хипов – это обычная (эфемерная) куча и LOH. Эфемерная куча – это то место, где живут все обычные объекты. LOH – это то место где живут большие (больше 85000 байт) объекты.

    LOH обладает некоторыми особенностями:
    • Объекты в LOH никогда не перемещаются
    • LOH только растет и никогда не уменьшается (т.е. если объект собран сборщиком мусора, размер LOH все равно остается неизменным)
    • Хип LOH освобождается только тогда, когда LOH полностью пуст

    Из этих двух особенностей LOH происходят два важных следствия, про которые часто забывают:
    • Память в LOH может оказаться фрагментированной. Т.е. происходит то, с чем так боролись в unmanaged мире: в какой-то момент у вас может быть 10Mb свободной памяти, но вы не сможете выделить память под объект размером 1Mb
    • Если вы однажды выделили память под большой объект, а потом используете только маленькие, то вы фактически лишаете себя большого куска памяти. При чем, если у вас в LOH был список или хэш-таблица размером N, а вы добавили в него один элемент, то список реаллоцируется и растет в два раза, сответственно размер LOH составит как минимум 3*N (N – исходные данные, 2N – копия данных и резерв под новый размер). Следующий рост потребует в LOH непрерывный кусок памяти размером в 4*N, а так как такого куска в LOH у нас нет (есть только N), его придется позаимствовать из адресного пространства процесса. В итоге размер LOH вырастет до 7*N, и так далее.


    Если вспомнить, что LOH аллоцируется кусками по 16Mb, то все происходящее покажется еще более разрушительными. С первым следствием можно бороться аккуратно переиспользуя объекты. Со вторым — не используя большие объекты. Получается как-то не очень, особенно если с большими коллекциями работать все-таки хочется. Посмотрим, что как можно решить эту проблему.


    Реализация контейнеров на chunk-ах


    Можно попытаться реализовать свои контейнеры на chunk-ак (на кусках, т.е. выделять память под массив не целиком, а небольшими частями, которые не попадут в LOH). При чем непосредственно на chunk-ах надо делать надо реализовать только IList<T>, все остальные контейнеры будут использовать IList<T> как хранилище для своих данных.

    Начнем реализовывать такой список:

    public class ChunkList<T> : IList<T>
    {
      private readonly int _ChunkSize = 4096;

      private int _Count;
      private T[][] _Chunks;
    }


    * This source code was highlighted with Source Code Highlighter.


    В _Chunks будем хранить N страниц по _ChunkSize объектов в каждой, динамически удаляя или добавляя новые страницы. Собственно, саму реализацию я оставлю желающим в качестве домашнего задания. Она не так и сложна, надо только аккуратно написать все операции.

    Но уже в том коде, который я привел, есть ошибка. Ошибка в значении по-умолчанию для _ChunkSize. Дело в том, что для reference-типов это значение адекватно, а для структур – нет. Ведь структура будет занимать в массиве _Chunks столько памяти, сколько ее данные. Значит надо как-то узнать размер данных типа T, а количество chunks посчитать как 85000/sizeof(T). Но не смотря на кажущуюся простоту, эта задача легко не решается.

    Если обратиться к статье Computing the Size of a Structure, то можно найти такое решение задачи поиска размера:

    public static int GetSize<T>()
    {
     Type tt = typeof(T);
     int size;
     if (tt.IsValueType)
     {
      if (tt.IsGenericType)
      {
       var t = default(T);
       size = Marshal.SizeOf(t);
      }
      else
      {
       size = Marshal.SizeOf(tt);
      }
     }
     else
     {
      size = IntPtr.Size;
     }
     return size;
    }


    * This source code was highlighted with Source Code Highlighter.


    Таким образом можно дополнить наш ChunkList:

    public class ChunkList<T> : IList<T>
    {
      static ChunkList()
      {
        _ChunkSize = 80000 / GetSize<T>();
      } 

      private static readonly int _ChunkSize = 4096;

      private int _Count;
      private T[][] _Chunks;
    }


    * This source code was highlighted with Source Code Highlighter.


    Все хорошо, но только в каких-то случаях (достаточно редких) этот код будет создавать экземпляр структуры. Если это неважно, то можно так и оставить. Если важно, то придется создать конструктор, в который каждый пользователь списка сможет самостоятельно передавать размер объекта или желаемый размер chunk-ов.

    А вы как боретесь с большими объектами?

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 88

      0
      Чтобы сильно не заморачиваться, используем MyList: Dictionary
        +2
        Ой, извините, парсер все съел. Должно было быть так:

        class MyList<U> : Dictionary<int/long, U> {… }
          0
          отличная идея! браво!

          если вот только вы память экономите, то придется все равно заморачиваться! но браво )!
            0
            Извините, я не понял, в чем идея использовать class MyList <U>: Dictionary<int/long, U> {… }?
              0
              Прочитал ниже:
              > List, Stack, HashSet — все хранятся непрерывным куском. Исключение только для Dictionary, о чем есть замечательнейший комментарий выше.

              Спасибо, не знал.
                0
                читайте ниже, что-то мы сглупили с Dictionary. Короче, все коллекции негодны )
              0
              Dictionary разве не использует вариант Open addressing? Согласно Reflector ипользуется одномерный массив из Entry который вполне может вырасти выше 85000 байт (при достаточно большом числе элементов).
                0
                Если я не ошибаюсь, там используются buckets (пучки), списки списков, в результате одномерные массивы для индексов имеют характерный размер O(logN). Этого уже вполне достаточно.
                  0
                  Ошибаетесь. Есть buckets который просто массив int индексов в массиве entries который есть массив от Entry(K, V). Достаточно странная реализация open addressing hash в отличие от более канонической в старой non-generic Hashtable.
                    0
                    Кажется, мы друг друга не поняли. Я о том, что в случае хранения списка больших структур (а именно с этим возникают проблемы при использовании List, насколько я понял автора) сам объект вместе со структурами помещается в LOH.

                    При использовании: Dictionary в LOH помещается только Dictionary, который имеет размер ~~4N как раз за счет непрерывного массива _entries, в котором лежат ссылки, а не сами структуры
                      +2
                      Учтите что ссылки будут лежать только если K и V классы. Структуры имеют by value семантику. Сам Entry тоже описан как структура, так что его размер в памяти никак не меньше 16 байт плюс CLR метаданные получится все 32. 85000/32=2600 элементов, что достаточно легко употребить.
                        0
                        именно в этом и проблема, что что-то вообще попадает в LOH. Я просто и забыл уже, что там внутри Dictionay, думал, что он методом цепочек сделан. А нет. На цепочках HashTable сделан, но он все равно хранит внутри коллекцию всех значений и всех ключей, что опять же делает его бесполезным.
                          0
                          Нет, в этом случае проблема менее острая: списки начинаются с ~~0-вой длины и постепенно ресайзятся, так что фрагментация LOH будет стоять менее остро. По крайней мере, у нас в проектах так.
                            0
                            для нас LOH — это сэкономленные драгоценные мегабайты, которые спасут жизнь при всплесках потребления памяти. и дело не в фрагментации, дело в том, что то память из LOH не переиспользуется потом для маленьких объектов.
                              0
                              А, т.е. у вас специфика приложения такая, что вы то работаете с множеством больших объектов — линейными списками, то требуется как можно больше адресного пространства под объекты из gen0-2, при том что самих списков нет (иначе память из LOH не была бы так досадно недоступна, т.к. была бы пристроена в дело).

                              Достаточно странно, но тогда я боюсь, что вы правы: нужна кастомная реализация IList[T] на чанках, что вы и предложили.
                            +1
                            Поправка — System.Collections.Hashtable реализует open addressing hash (http://en.wikipedia.org/wiki/Hash_table#Open_addressing) да еще с спользованием double hashing (http://en.wikipedia.org/wiki/Double_hashing) и load factor по умолчанию ~0.7 (то есть всегда есть 30% свободных элементов). Так что он тоже достатосно подвержен разбуханию и попаданию в LOH.
                      0
                      Эх, да, что-то мы тут сглупили (
                +1
                первая часть, где теория, показалась интересной, а вот разработка велосипеда на chunk-ах — это глупость
                  0
                  если все что написано в теории — правда, то как быть? :)
                    0
                    Следить за собственным жором памяти, как быть.

                    И смотреть на поведение реального приложения.

                    Как всегда — баланс производительности и прожорливости.
                      +1
                      :) Я память не жру. Могу предположить, что автор тоже. А ваш пост ничего не говорит, что делать в ситуациях, описанных автором. Кроме того, что нужно следить. Ну последил, все хреново. Делать что?
                        0
                        Не использовать дотнет?
                          0
                          При всем богатстве выбора — достойных альтернатив нет
                    0
                    а поясните, пожалуйста, что в этой ситуации не глупость? )
                      –1
                      пояснить не могу, т.к. не знаю. разве что пытаться избегать такую ситуацию вообще, хотя, сами понимаете, это далеко не всегда возможно
                    0
                    почему вы уверены, что коллекции хранятся непрерывным куском?
                      +1
                      List, Stack, HashSet — все хранятся непрерывным куском. Исключение только для Dictionary, о чем есть замечательнейший комментарий выше.

                      Почему уверен? Потому что читал исходники фреймофрка и MSDN.
                      +1
                      Либо я чего-то не понимаю, либо вот это предложение не может быть правдой:
                      «LOH только растет и никогда не уменьшается (т.е. если объект собран сборщиком мусора, размер LOH все равно остается неизменным)»
                        0
                        msdn.microsoft.com/en-us/magazine/cc534993.aspx — тут рассказано как проверить это с помощью windbg, но вообще google: CLR + LOH + MSDN

                        Тоже самое можно посмотреть с помощью CLR Profiler.
                          +2
                          Я бы вам посоветовал для этих целей воспользоваться последней vmmap от Руссиновича — чУдная утилитка в деле исследования распределения памяти процесса; понимает CLR.
                            0
                            спасибо, посмотрю )
                          +1
                          Имеется в виду, что виртуальная память, отобранная у системы под LOH, ей (системе) не возвращается, и не может быть задействована под работу обычного generational GC.

                          Грубо говоря: если ваше приложение разместило в LOH, скажем, 100MB, а затем полностью его освободило, затем стало размещать не больше ~10M только в пуле поколений, то приложение отнимет у системы 100MB VRAM дополнительно к тому, что будет затрачено на пул поколений и код.
                            0
                            В общем-то проблема не велика, так как неиспользуемые страницы уйдут в своп.

                            Процесс можно ускорить
                            msdn.microsoft.com/en-us/library/ms686234%28VS.85%29.aspx
                              0
                              проблема велика, потому что адресное пространство процесса ограничено (в x86 процессах <3Gb). и если у вас оно все занято под LOH, то вы просто получите OutOfMemoryException при совершенно свободной, по сути, памяти.
                                0
                                Ну это вы какие-то просто огромные объекты создаёте, да ещё и по нарастающей. Достаточно специфическая ситуация непосредственно с LOH вообще не связанная. Обычное Си++ приложение слокнётся с теми же проблемами. Надо было тогда писать про то как хранить в оперативной памяти большие объекты, не акцентируя на LOH.
                                  0
                                  но мы же живем в managed мире, у нас другие привычки и другой взгляд на мир. а C++ приложение с этим не столкнется, т.к. у него нет разделения на хипы для маленьких и больших объектов, а в CLR есть, поэтому большие объекты «крадут» память у всех остальных.

                                  к тому же 3GB — это на самом деле ОЧЕНЬ мало. ведь в этих 3GB у вас живут имиджи ваших DLL-ек и ваши данные, возможно еще и unmanaged данные, значит память сильно фрагментирована (особенно если DLL небольшие), а CLR аллоцирует память непрерывными кусками по 32MB или по 16MB для LOH. К тому же Gen0 и Gen1 вообще умеют жить только в целиком непрерывном куске памяти. Поэтому при наличии фрагментации памяти для CLR может остаться совсем немного места.
                                    0
                                    Не знаю как вы, я живу в мире программирования, а не managed. Проекты на двух-трёх языках привычное дело.

                                    3Гб это очень много. У меня .Net 3.5 сетевые сервера (WCF) работают с 512Мб-1024Мб памяти и ещё остаётся не мало.

                                    Вот скажите честно, как часто вы упираетесь в нехватку оперативной памяти? И как часто создаются объекты больше 85000 байт? Я структуры использую практически только для интеропа, да и там они быстро уничтожаются и крайне редко группируются в массивы. Если у вас другой опыт, поделитесь.
                                      0
                                      Упираемся в нехватку оперативной памяти мы постоянно. Потому что живем в смешанном (managed + unmanaged) окружении 32-битного приложения с сильной фрагментацией памяти. В 64-битных операционных системах это почти незаметно, на 32-битных частные (несколько раз в день у каждого пользователя) OutOfMemory.

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

                                      И про структуры (большие) в статье ни слова ;) с ними и так все понятно — не создавать.
                                        0
                                        Разделить на процессы пробовали?
                                          0
                                          Ваша проблема именно в нарастающем потреблении памяти. Вот этот код

                                          for (; ; )
                                          {
                                          	Console.WriteLine(GC.GetTotalMemory(false));
                                          	byte[] array = new byte[512 * 1024 * 1024];
                                          }
                                          


                                          работает без ООМ.

                                          Думаю, спасением было бы явное указание Capacity при создании.
                                            0
                                            это вы пример к чему привели?

                                            понятно, что в нем количество свободной памяти не будет уменьшаться, и что? И OOM не будет. Но так вы не делаете того, что я описываю в статье. Создайте в LOH объектов на всю почти свободную память. Вызовите GC. Убедитесь, что свободной памяти столько же, сколько было до заполнения LOH. Потом попытайтесь создать немного маленьких объектов. Вот тогда будет OOM.

                                            И почитайте вот это: msdn.microsoft.com/en-us/magazine/cc534993.aspx
                                              0
                                              Эффекта можно добиться гораздо проще
                                              for (long index = 128 * 1024; ; index += index)
                                              {
                                              	Console.WriteLine("{0}", GC.GetTotalMemory(false));
                                              	byte[] array = new byte[index];
                                              }
                                              


                                              Проблема не в том, что в LOH большие объекты, а в том, что там сперва были маленькие объекты, а уже потом большие. С этим то и надо бороться.
                                                0
                                                проблема в том, что в LOH вообще что-то было.

                                                Но ваш этот пример опять же не про мой случай. Понятно, что случится OOM, потому что в определенный момент вы запросите память под объект размером больше свободной памяти, ну и что? )
                                                  0
                                                  Объём занятой памяти примерно в два раза больше объёма данных. Больше ничего.
                                                    0
                                                    это другой аспект. в реальных программах так почти никогда не бывает. но вот умрут ваши объекты в LOH, но остальной программе от этого ничуть не лучше, память-то уже не вернуть.
                                                      0
                                                      Возвращаемся к вопросу — Разделить на процессы пробовали?
                                                        0
                                                        у вас это прям как дежурное «сам дурак» ))

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

                                                            давайте постараемся жить в реальном мире с реальными историческими, и не всегда собственными проблемами.
                                                              +1
                                                              Этот аргумент не становится менее правомерным.

                                                              Я понимаю что осознание правильной архитектуры приходит только после написания первой версии программы. В лучшем случае первой… Но, с другой стороны, выделить ту же unmanaged часть в отдельный процесс и вообще сделать multi-tier систему, решения не такие уж редкие, чтобы не было повода посмотреть в их сторону.

                                                              Мне часто приходилось сопрягать managed и unmanaged и это всегда очень больно. Если речь не идёт о потоковом видео, то вынос в отдельный процесс приемлем по производительности, а общие последствия положительны. А код легче поддерживать и качество улучшается.

                                                              Что касается разбиения на уровни, то я не буду вас оскорблять доказательствами полезности данного процесса.

                                                              У LOH есть подводные камни, ваша статья полезна, но мотивация не верна. Я так думаю.
                                  0
                                  Ну, поэтому я и написал VRAM, обращая внимание на то, что физическая память под это дело не будет расходоваться.

                                  Уход в своп можно ускорить, не спорю :) Тока мне вот не нравится «мастурбировать» Working Set вверх-вниз, чтобы таки сработало — однозначно это свидетельствует о том, что дизайн подсистемы вынуждает заниматься сексом в гамаке на лыжах.
                                  Впрочем, среднему пользователю подсистемы памяти (имея в виду прикладного программиста) и не придется этим заниматься — алгоритмы управления в VRAM в Windows достаточно хороши.

                                    0
                                    Какая разница VRAM или физическая память? Адресное пространство процесса все равно ограничено. Проблема не в том, что что-то куда-то не свопиться, а в том, что память занята, но при этом не хранит никаких данных, что крадет адресное пространство у всей остальной части программы.
                                      0
                                      Относительно адресного пространства — никакой разницы: не влезло — так не влезло, получите-распишитесь OutOfMemory :) Тем более с ростом LOH шансы на это серьезно увеличиваются.

                                      Я просто отвечал товарищу выше, что насчет своп-файла он прав в той части, что из физической памяти этот блоб будет выдавлен.

                                      То, что это, тем не менее, не решает проблемы, повторяться не стал — вы и так ниже все доступно расписали.
                              +1
                              Это одна из самых полезных статей о .Net на Хабре, которую я видел. Большое спасибо за интересный материал.
                                0
                                > LOH – это то место где живут большие (больше 85000 байт) объекты.
                                А случайно никто не знает почему выбрано значение 85000 байт? Какое-то неровно значение: 83,008 Кб
                                  +2
                                  Насколько я знаю, команда CLR проводила тестирование производительности сборщика мусора на определенных «стандартных тест-кейсах» с разными значениями этого порога. Экспериментальным путем было установленно, что 85000 байт — оптимальный порог. Другое дело, что он был оптимальным в конце 1990-х, начале 2000-х, когда создавался .Net, и насколько актуальны были бы их тест-кейсы сейчас — неизвестно, ведь железо и ОС шагнули вперед. Впрочем, скорее всего проводить повторные тесты и перерасчет порога никто не будет просто потому, что это:
                                  а) не даст существенного прироста производительности.
                                  б) может затронуть существующие системы.
                                  в) работает — не трогай.
                                  +1
                                  Хотелось бы увидеть хабратопик про то, почему я как программист на Java, глубоко несчастен из-за отсутствия LOH.

                                  Почему бы не помещать всё в Small Object Heap? Или, как он называется, generational gc? Есть где-нибудь сравнение производительности с включенным и отключенным LOH? (в статье на msdn ничего нет, кроме каких-то странных рассуждений про сборку мусора «из расчёта 2 тика на байт»)
                                    0
                                    Когда у вас OOM, то какая производительность? Тут главное, чтобы не падало. Но вообще, конечно, интересно.

                                    А вы в Java действительно так несчастны без LOH? Мои знакомые Java-люди никак своего несчастья н выдавали, хотя мне было интересно. Расскажите, будет познавательно.
                                      +1
                                      В следующий раз буду ставить тег «ирония» :) Мне кажется, что надо радоваться, раз в Java этого нет.

                                      В Java нет, а в .NET есть. Стало интересно, feature это или bug? Пытаюсь перевести в Java-термины, и пока не понимаю, какая вообще выгода от LOH?

                                      Если память не экономит, а наоборот, препятствует сбору, то должна быть выгода в производительности. Но какая? Хотя бы в попугаях.
                                        0
                                        освобождение и перемещение больших объектов — это дорого. видимо, пытались выиграть именно это.
                                          0
                                          Выгода простая, эмпирически установленная.

                                          Среднестатистическая программа _очень_ редко занимается активными выделениями и освобождениями крупных объектов. Если помещать их вместе с остальными объектами в область поколений, это будет сильно фрагментировать кучу, вызывая ненужные движения GC в generation 0 (eden), которое переведет много 0-ых объектов в 1-ое поколение, куда GC придет гораздо позже. Поэтому крупные объекты размещаются отдельно от мелких.

                                          Конечно, любой алгоритм управления памяти имеет «смертельную стратегию» выделения памяти, на которой он ведет себя худшим образом.
                                          Для алгоритма с LOH, это следующая последовательность:
                                          — большой объект в LOH (~MBs
                                          — маленький объект в LOH (100 Kb)
                                          :loop
                                          — большой объект в LOH (больше предыдущего)
                                          — маленький объект в LOH (100 Kb)
                                          — удаление первого с начала маленького объекта
                                          — jump :loop

                                          Ну и как правильно заметили — предел 85К был установлен ~~10 лет назад. Пора бы уже и пересмотреть )

                                          Теперь вы расскажите, как в Java борются с Permanent Generation Space, а также почему она не может выделять памяти у системы, когда ей не хватает :)
                                            0
                                            Мне понятно, в каких случаях может произойти плохое поведение. Мне интересны цифры показывающие прирост из-за использования LOH хоть в каких-нибудь сценариях.

                                            В Java сценарий такой:
                                            — объект создаётся в gen eden
                                            — после первой сборки мусора он перемещается в gen surv
                                            — после заполнения предыдущего поколения в нём проходит GC и выжившие объекты переносятся в permanent generation

                                            При этом нет ограничений на перемещение объектов внутри PG. Однако это происходит редко, так как после заполненности кешей фиг туда что попадёт относительно крупное.

                                            От OOM ничего не спасёт, как на Java, так и в .NET. Отличие в том, что Java сама себя ограничивает объёмом памяти «сверху», но это ограничение можно и снять (установить его заведомо большим с вылезанием в «своп»). Тогда Java будет запрашивать память у системы до тех пор, пока не достигнет системного предела (или установленного из командной строки).

                                            На моём опыте приложения могут улезать в своп только по одной причине — когда они не активны. Если они работают, то свопа быть не должно — выигрыша в производительности это не даёт, а управление хранением данных и синхронизацией лучше отдать какой-нибудь embedded СУБД, той же Derby.

                                            А раз свопа быть не должно, устанавливаем максимальный допустимый размер всей кучи (всех поколений) в 80% от оперативки и радуемся.
                                              0
                                              >>В Java нет, а в .NET есть. Стало интересно, feature это или bug?
                                              >>Мне понятно, в каких случаях может произойти плохое поведение
                                              Ну вот судя по первой цитате, все-таки непонятно.

                                              Вместе с этим…
                                              >>Хотелось бы увидеть хабратопик про то, почему я как программист на Java, глубоко несчастен из-за отсутствия LOH
                                              … создается ощущение, что вы решили потроллить дотнетчиков. .net не нужен, LOH не нужен, ага :)

                                              Понятное дело, что цифры для разных сценариев выделения памяти будут разные. Так же, как и для разных JVM тоже. В MS Research этим занимался (занимается) Ben Zorn, у него были бенчмарки и научные работы на эту тему. Если я правильно понимаю, в том числе и на основании их было принято решение делать не как в Java (где большие объекты помещаются в tenured space — аналого gen2 в .net), а в LOH.

                                              Если я найду ссылки на репрезентативные результаты тестов, я вам сообщу. Мне и самому интересно.
                                                0
                                                Сначала хочу разобраться, а уже потом — потроллить, вспомнить про G1 и т.д. :)

                                                Большие объекты в Java помещаются в tenured space не сразу, а на второй проход GC по ним, кажется.
                                      0
                                      Объекты располагаются в LOH или не LOH автоматически в зависимости от собственного размера.

                                      Неужели ввтор научился перегружать оператор new в C#?

                                        0
                                        Проблема, как выяснилось, все же не с самими объектами, а со списками/массивами, содержащими ссылки на эти объекты.
                                          0
                                          А! Дошло!

                                          Под большими объектами подразумеваются массивы T[].
                                          Идея автора порезать массивы на более мелкие массивчики, чтобы они не попадали в LOH.

                                          Если в LOH после 16мб, то возникают следующие вопросы:
                                          1) А правда, что чтобы List
                                            0
                                            1) А правда, что чтобы List<object> попал в LOH, в него надо насовать 4 миллиона объектов.
                                            2) А правда, что чтобы List<double> попал в LOH, в него надо напихать 2 миллиона даблов.
                                            3) МС рекомендует использовать object вместо struct, начиная с 16 байтного размера. Стоит ли овчинка выделки тогда?
                                              0
                                              Извиняюсь, был дезинформирован 4 абзацем.

                                              85Кb это около 21 тысяч объектов в списке, или 10 тысяч даблов.

                                              Не настолько астрономические, но все равно, достаточно нереальные размеры массивов в прикладных задачах.

                                              Присоединяюсь к мнению, что Dictionary<K,V> спасет и от LOHов, и от медленного поиска объекта по ключу :)

                                                0
                                                Dictionary от LOH не спасет, потому что 21тысяча объектов в в нем — и он сам попадет в LOH. Все контейнеры должны быть заново реализованы на основе ChunkedList.
                                                  0
                                                  Пардон, я имел ввиду SortedDictionary<K,V> — этот класс использует red-black tree индексы, которые строятся из небольших node-классов, которые точно не попадут в LOH
                                                    0
                                                    SortedDictionary — да. Наконец-то подходит.

                                                    Но. Он тратит лишнюю память. И операция поиска в нем O(log n), а не O(1) как в хеше. И добавление тоже дорогое.
                                                      0
                                                      Мне почему-то кажется, что добавление дешевле. Потому как раздвигать километровые массивы не нужно, нужно просто создать ноду и переписать пару поинтеров.

                                                      Бинарный поиск vs подсчет хэша и полный перебор группы — сложно сказать, что быстрее.

                                                      А вот памяти — да, памяти нужно больше. Но это оправдывает то, что эта память будет garbage collected, ибо не LOH :)

                                                        0
                                                        Добавление O(log n), потому что надо найти место вставки. В хеше O(1), если массив не переполнен, если переполнен O(n) — но это происходит редко, и вообще добавление N элементов в хэш стоит 2N.

                                                        Подсчет хэша — это константное время. Бинарный поиск — зависит от n. Быстрее в итоге хэш, потому что не растет время доступа.
                                                          0
                                                          Поскольку hash не является уникальным, один и тот же hash могут иметь несколько объектов.
                                                          Это значит, что в группе элементов под одним hash-ем нужно делать полный перебор ключей.

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

                                                          В red-black-trees деревья балансируются, поэтому поиск всегда быстрый и вставка всегда одинаково производительна.
                                                            0
                                                            вы заново пытаетесь изобрести теорию алгоритмов.
                                                              0
                                                              Упаси Б-г :) Я уже успел ее несколько раз забыть…
                                          0
                                          Мне интересно :) Я за несколько лет, что знаком с .NET про LOH услышал впервые (спасибо автору статьи). В комментах уже ломаются копья на тему «будет ли плохо от LOHа». А хоть у кого-нибудь из-за такого специфического поведения LOH за все те годы, что .NET существует были проблемы? Хоть у кого-нибудь? :)
                                            +1
                                            Были. Именно такие, как автор описывает. Исчерпать 85 килобайт не так сложно — как выше подсчитывали, это всего лишь примерно 10 тысяч даблов в списке. Если не помнить про такое поведение LOH, то начнутся проблемы с потреблением памяти. В нашем случае решилось быстро — пришлось создать все большие контейнеры сразу и потом аккуратно переиспользовать их все время.
                                            Плюс, дело сначала происходило в asp.net — поэтому мы словили сложности с recycle рабочих потоков. Пришлось выносить в отдельный сервисный процесс и заводить всю фигню с wcf.

                                            И все это из-за специфики потребления памяти большими контейнерами. В итоге все получилось нормально и красиво, конечно — но от простой реализации в лоб большая разница получилась, согласитесь. И по времени, и по сложности проекта.
                                              0
                                              Какие именно проблемы вы испытывали? Я имею ввиду, как это проявлялось?
                                              >сложности с recycle рабочих потоков
                                              Какие именно?

                                              Вы не могли бы написать поподробнее? Это довольно интересно.
                                                0
                                                Проблемы — неконтролируемый рост потребляемой памяти. Отсюда попросту нехватка памяти на вебсервере. Отсюда

                                                  0
                                                  Проблемы — неконтролируемый рост потребляемой памяти. Отсюда попросту нехватка памяти на вебсервере. Отсюда падение производительности из-за свопов. Плюс, видимо, из-за постоянных попыток GC освободить память из области маленьких объектов. Новые объекты выделяются все медленнее, сборки мусора происходят все чаще. Плюс iis вдруг дропает рабочий поток по факту превышения памяти и у пользователей сбрасывается сессия, а мы стартуем приложение заново и перечитываем из базы наши кэши. Все это небыстро.

                                                  Сильно мы не исследовали этот феномен — поняли в чем проблема, да и сделали по-правильному. Нефик делать емкие вычисления на веб-сервере.

                                                  Не знаю, какой именно конфигурации был сервер, и сколько там всего RAM — мы там только хостились. Может, вообще виртуализированный. В любом случае, мы со своим приложением даже привлекли внимание админов продакшн серверов :)

                                                  Кстати, про LOH написано у нашего любимого Рихтера. Если не читали — то прочитайте, очень рекомендую. Лучшая книжка по шарпу. Вот, кстати, немного msdn.microsoft.com/en-us/magazine/bb985011.aspx
                                                    0
                                                    может у вас были просто memory leaks? и LOH тут не при чем?
                                                    но вообще, конечно перед OOM делается попытка GC, так что может и LOH
                                            0
                                            Давно копал эти дебри, вроде бы раньше в .NET было два или 3 разных сборщика мусора, которые настраивались политикой. Возможно, что для другого GC проблема с LOH не так актуальна? (Правда есть вероятность, что фигню щас несу :) ).
                                              0
                                              Скорее всего Вы имеете в виду то, что описано вот тут. Судя по всему актуальна проблема.
                                                0
                                                Да, спасибо, именно это я и имел ввиду, но я так и не понял, меняется ли кроме некоторой части алгоритма вся концепция сборки мусора или нет. Судя по всему — проблемы остаются те же, решаются только небольшие косвенные задачи.
                                              –1
                                              Честно говоря, моё ИМХО в том, что перекидывая данные из LOH в SOH мы сильно увеличиваем нагрузку на GC, которому сложнее теперь поддерживать SOH дефрагментированной. Т.е. он вынужден всё время её реупорядочивать. В общем, LOH не просто так придумали от нечего делать — явно с какими-то проблемами боролись.
                                                0
                                                >>LOH – это то место где живут большие (больше 85000 байт) объекты
                                                Не, ты не шаришь, лох — это тот, кого лоханули.

                                                >>LOH только растет и никогда не уменьшается
                                                Вот это правда! Сколько лоха не лоши, он все равно лохом и остается!

                                                >>«будет ли плохо от LOHа»
                                                От лоха плохо только самому лоху) Ха-ха.

                                                Only users with full accounts can post comments. Log in, please.