Abnormal programming
Comments 40
+12
Меня статья ввела в недоумение.
Во-первых, зачем это? Какие плюсы, минусы, выводы?
Во-вторых, статья называется «ручное управление памятью», а про реализацию управления ничего и не рассказано.

Я посмотрел код. Вся суть «управления памятью» в том, что мы кладём объекты в массив и меняем размер массива при надобности. Стоило это упомянуть в статье. Или я чего-то недопонял?
-1
Плюсы — скорость. Минусы — трёхуровневые генерики. Выводы — лучше пока только смотреть и не использовать, в конце концов — это ненормальное программирование. :)

Признаться мне было лень повторять двусвязный список на основе этого, чтобы полноценно сравнить со стандартным LinkedList'ом. Но односвязный список, реализация которого есть по ссылке делает его в 4 раза по времени добавления элементов когда их много.

Про непосредственно реализацию управления не рассказано, так как задача была в том, чтобы показать как положить какую-нибудь стандартную технику на .NET и как обойти проблемы.

Для управления памятью используется алгоритм с аллокацией и деаллокацией за среднее время O(1). Лучше только гарантированное O(1).
+2
> Выводы — лучше пока только смотреть и не использовать
Ну хорошо, пока, но перспектива какая, вообще смысл этой статьи какой? Просто покодить? Вот могу математическую задачку подкинуть, баян бабаян, но веселее чем бессмысленный кодинг:

Вводим 3 первые цифры вашего телефона(без регионов)
Умножаем на 80
Плюс 1
Умножаем на 250
Плюс 4 последние цифры вашего номера телефона
Плюс 4 последние цифры вашего номера телефона ещё раз
Минус 250
Делим на 2
Медленно офигеваем

ЗЫ: Я бы советовал на C++ сборщик мусора написать, мне кажется было бы больше смысла хотя бы из серии «потренироваться».
0
Эм, а что интересного в том, что xxxyyyy = 10000*xxx + yyyy?
А сборщиков мусора для ++ и так полно.
UFO landed and left these words here
+2
Если объединить все ваши классы в один, то получится ArrayLinkedList. И ручное выделение памяти окажется не причем. Более того, в него еще для полноты нужно будет добавить «сборку мусора», чтобы не становилось слишком много удаленных элементов.
0
Это, безусловно, верно, но вот вопрос: зачем объединять классы, имеющие различную функциональность? Класс, управляющий памятью на основе массива со списком свободных узлов, достаточно универсален, чтобы на его основе можно было строить деревья, графы и другие структуры данных, состоящие из множества однотипных элементов.

В принципе, этот класс может дать заметный прирост в скорости бенчмарку binary trees на shootout'е. Вероятно я в течении дня это проверю.
0
А вот и результат в binary trees: 47 секунды в среднем — реализация дерева в лоб с использованием кастомного аллокатора, 64 секунды — решение F# Mono от Don Syme'а (слегка улучшенное дерево).
0
Дык, вроде, везде пишут, что не нужно пытаться оптимизировать сборщик мусора. Не нужно хранить временные объекты — их дешевле создать заново, а при уборке мусора совершается регулярная лишняя работа по обработке и копированию неиспользуемых объектов. Откуда скорость-то?!
0
Во– первых, где это пишут?
Во– вторых, приведенный алгоритм работает за константное время в среднем, что означает, что он асимптотически оптимален. Сборщик мусора дот нета же работает за число живых / число выделений памяти, что при большом количестве постоянно живых объектов далеко от константной средней сложности.
0
Т.е. вы хотите сказать, что в вашем случае сборщик мусора задействован не будет? :)
Кстати, вы там смело используете Array.Resize:
This method allocates a new array with the specified size, copies elements from the old array to the new one, and then replaces the old array with the new one.
Т.е. при достаточно большом размере массива он поедет в LOH, и словим memory leak, о производительности я даже не говорю. Одни недостатки, если честно. А весь «аллокатор» можно свести к IDictionary<int, T> :)
0
При обходе графа живых объектов сборщик мусора не будет обходить объекты, выделенные с помощью этого аллокатора и не имеющие в себе обычных ссылок. Для него эти объекты будут представлены одним массивом, который обходить не надо.
Да, он поедет в LOH, да, если неграмотно обрабатывать получим утечку памяти — на то оно и ручное управление.
Производительность создания объектов у этого аллокатора выше, чем у стандартного дотнетовского по описанной выше причине (вы можете в этом сами убедиться, запустив тестовый пример. теперь для этого, правда, придётся немного повозиться с F#). Полагаю Вы «даже не говорите», потому что вам сказать нечего.
Ну сведите его к IDictionary<int, T>, посмотрим как быстро оно у Вас работать будет.
0
Все равно не слишком понимаю. Допустим, у меня по адресу pointer есть объект obj1. Если я сделаю Free(pointer) и потом запишу значение, последняя ссылка на мой obj1 — поле Value — исчезнет и объект попадет под сборку мусора. Верно? Т.е. сборщик так или иначе будет работать, но придется еще тратить время на заполнение структуры аллокатора.

Заранее определенный нужный размер массива, конечно, частично избавит от проблемы фрагментации LOH, но и добавит неудобства — а если я не знаю количество объектов заранее?

Я вот прямо в лоб набросал тест pastebin.com/T2u7tUmc — создаем кучу объектов типа string с вашим аллокатором и банальным new + устанавливаем какое-то значение в объект.
Last.Core = 357ms
New = 175ms
0
Разумеется в Вашем коде не будет никакого выигрыша, хотя бы потому что первый цикл содержит все операции второго и ещё дополнительно аллокацию места для хранения ссылки на i.ToString()

Чтобы сборщик мусора .NET не обрабатывал объект, он должен иметь тип-значение (struct в данном случае).

Код с примером ускорения приведён в репозитории. Достаточно вызвать в файле Test.fs «Tests.listPerfTest 10 10000000» вместо Shootout.runBinaryTrees, чтобы увидеть, как однонаправленный список, узлы которого выделяются и освобождаются аллокатором, обходит по скорости создания и добавления элементов стандартный двунаправленный System.Collections.Generic.LinkedList, узлы которого создаются и удаляются сборщиком мусора.
0
Сборщик мусора вынужден копировать области памяти, не содержащие данных.
0
Скорость. Бенчмарк по ссылке показывает выигрыш в 4 раза по сравнению с оригинальным списком на 64 битной .NET CLR на втором феноме.
+1
Вполне возможно, что подобное ускорение можно было бы получить за счет использования пула объектов.
0
Совершенно не обязательно, так как сборщик мусора всё равно должен обойти все объекты в пуле при поиске достижимых.
0
Если пул будет представлен массивом структур (а по сути дела структуры рассматриваются и в статье), то это будет один объект с точки зрения GC — весь массив.
0
Я что–то не понимаю чем Ваш «пул» отличается от того, что реализовано?
0
гм… а где результаты и код бенчмарка?

Кстати, не забываем что List — это просто обертка над динамическим массивом и со «списком» как структурой данных мало связан. А LinkedList — двойной список. Если хочется «чистого» списка можно его стандартными способами реализовать (контейнер + нод), но, мне кажется, разница в скорости будет минимальная.

Кстати, в 64-битной CLR тесты как правило показывают меньшую скорость, чем в 32-битной, так что если интересует именно скорость, лучше сравнивать в х32 + все оптимизации.

— ПС. И все-таки имхо в реальном проекте работа с памятью не будет ботл-неком. А если есть кусок системы, сильно зависящий от работы с памятью, то может стоит переложить именно эту задачу на unmanaged-C++, благо средств для IPC у нас много.
0
Я думаю в продакшене это использовать не будет ни кто и не когда, ибо не для того в шарпе уберали указатели, чтобы кто-то нашел спосб их там сделать. Все таки ну не для того.

Хотя автору за не ординарный подход истинное от меня уважение. Tips and triks -круто.
+4
Похоже на «Как все-таки убиться инструментом, создатели которого предусмотрели 5 уровней защиты от самоубийства этим инструментом».
+1
Хммммм. ListBasedAllocator это же практически List. Зачем было изобретать свои классы? Вполне естественно, что в ситуациях, когда требуется оперировать над большим множеством объектов, особенно иерархическим (далее — сложная структура) — производительнее держать сами объекты в структруре с линейным временем доступа (далее — простая структура), а в сложной структуре данных держать индексы из простой структуры, типов производных от ValueType. Однако такой подход имеет смысл только тогда, когда операции модификации сложной структуры превалируют по отношению к операциям удаления объектов и доступа к содержимому сложной структуры, по тому что:
— Возникает дополнительная операция получения данных по индексу.
— Возникает необходимость следить за сохранностью целостности данных в линейной структуре.
Второй пункт не такой простой как может показаться, по тому, что запрещено внутри линейной структуры перемещать объекты без корректировки индексов. Это обозначает, что операция удаления объекта не может приводить к компактизации объектов в структуре без того чтобы обойти всю сложную структуру и произвести корректировку индексов :) На самом деле — если реализовать «дефрагменацию» простой структуры то получится, по сути, ВНЕЗАПНО копия кусочка функциональности управляемой кучи :)
Из плюсов можно отметить, что такой подход способен существенно уменьшить число ссылок на объекты. Таким образом:
— Увеличивается производительность за счет уменьшения числа операций копирования ссылок.
— Увеличивается производительность за счет уменьшения нагрузки на сборщик мусора из-за уменьшения количества ссылок на объекты, ака GCRoot'ов.
В общем нужно осторожно думать, когда такой подход выгодно применять.

Статью надо было назвать, например: «Увеличение производительности операций за счет уменьшения количества ссылок на объекты». Но уж никак не «Превращаем C# в C++».

И, к слову, unsafe вполне прекрасно работает, и не особо ухудшает переносимость. Не путайте с PInvoke.
0
За исключением того, что ListBasedAllocator относится к List примерно так же как, и к массиву (от List тут только экспоненциальный рост), всё верно. А про unsafe я просто неудачно выразился.
0
Гм… проглянул bitbucket.org/lost/lostlib/src/13ad253cb08c/Lost.Core/MemoryManager/ListBasedAllocator.cs
и стандартный код от List<T>… много похожего.

Все внутри в «private T[] _items», при добавлении элемента больше чем Capacity идет ресайз массива.

Можно все-таки в двух словах концептуальное отличие List<T> и ListBasedAllocator<T> кроме того, что ListBasedAllocator<T> сильно упрощен (нет проверок, версионности, synchonized-версии и т.д. Пока я вижу просто очень сильно облегченный List<T>
0
В двух словах: List не реализует метод void Free(TPointer) (аналоги остальных методов в List есть), то есть он не пригоден для ручного управления памятью. На всякий случай напомню, что удаление элемента по произвольному индексу в List, во-первых, выполняется за O(n), во-вторых, изменяет индексы всех элементов после удаляемого.
0
гм… а почему бы тогда не сделать просто враппер над листом, с уточнением что T — Nullable и записывать null где удалили (+ мелкие изменения в итераторе и Count — в нем можно просто уменьшать внутренний счетчик при удалении).

Звучит как довольно простое решение, а «удалять» (точнее помечать как удаленный) можно за O(1) :)

0
А что нам даст помечание элемента как удалённого? Память-то не окажется доступной для повторного использования.
0
Почему нет?
Если говорить про GC, то обнулление убьет ссылку на объект.
Если говорить о повторном использовании элемента в массиве, то достаточно просто найти первый null элемент и записать в него — вот и повторное использование.
0
Если говорить про GC, то это уже не будет ручным управлением памятью, и, соотвественно, будет обладать присущими GC недостатками.
Если говорить о повторном использовании элемента в массиве, то на его поиск в среденем уйдёт O(длина массива), в то время как в ListBasedAllocator такой элемент будет найден за среднее константное время.
0
ну «ручное упрвление памятью» как я понимаю только для valuetype-ов? Иначе «ручного управления» не выйдет.

Смысл — повторное использование «слотов» как я понял…

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

Просто чаще теряется больше на том же yuild'e и его замыканием контекста (при котором создается новый класс), чем получаем выиграш от повторного использования слотов value-type-ов.
0
Согласен, GC редко является боттлнеком. Однако в специфических задачах прирост производительности может быть весьма и весьма существенным.

Сейчас в репозитории лежит реализация бенчмарка binary-trees из language shootout, написанная на F# (реализация дерева в лоб)и использующая ListBasedAllocator. Так она обходит по скорости на 20% и в несколько раз по памяти решение на F#, приведённое на том же сайте, при параметре 20 (по умолчанию). При параметре 22 разница во времени исполнения наблюдается уже >3 раз и более 10 раз по памяти.
0
Не, ну не сравнивайте F# и C#. Там же DLR работает — вот он на себя и берет.
0
Не следует неучам учить учёных :)

DLR имеет к F# весьма опосредованное отношение, по сути такое же, как к C#. F#, как и C#, — статически типизированный язык, который лишь имеет синтаксический сахар для работы с DLR. В коде, о котором я говорю нет ни одной строчки, использующей DLR.
0
Проблема поиска пустых блоков — основной недостаток классических менеджеров памяти. Продвинутые реализации всё время добавляют объект в конец блока выделенной памяти, и откладывают процесс дефрагментации до наступления критического момента. В такой момент выполнение malloc может занять приличное количество времени. В общем от накладных расходов всё равно уйти нельзя, как ни крути. Проблема древняя — возникла вместе с появлением компьютеров, содержащих RAM и обмусолена по моему уже до основания. Разных стратегий управления памятью просто гигантское количество. Есть нацеленные на специфичное поведение клиентской части, есть обобщенные.
Естественно, LinkedList<T> будет потормознее List<T>, это самый базовый класс, не знаю кто его использует.
Разработчики BCL не дураки. Падение производительности при удалении элемента окупается линейной скоростью доступа. В вашем списке скорость доступа к произвольному элементу как раз O(n).
0
Мой список по сути эквивалент LinkedList и обходит его по скорости создания+удаления элементов. Двоичное дерево, реализованное на том же аллокаторе будет быстрее обычного двоичного дерева при сохранении той же асимптотики.
0
Прикольная идея, буду иметь ввиду. А связанный список действительно очень тормозит из-за GC, об этом я видел статью в мсдн. Есть идея как сделать «ручную» память потокобезопасной? Возможно ли конвертировать указатели типа int* в byte*?
Only those users with full accounts are able to leave comments. , please.