Войти
ФлеймФорумПрограммирование

[C++] Как такая фигня с дизайном языка получилась? (9 стр)

Страницы: 16 7 8 9 10 11 Следующая »
#120
19:37, 6 июля 2019

1 frag / 2 deaths
> Офигенно вы боретесь с фрагментацией ребята.

А чем плохо? Аллокация сплошных массивов произвольной длины - это потреблядство от мира программирования. Зачем тебе сплошные массивы? только ради того, чтоб индексация элементов работала через адресную арифметику?

Если на индексацию через адресную арифметику в огромных массивах закатать губу, то вполне неплохим вариантом были бы библиотечные векторы, за кулисами балансирующие между деревьями, связными списками и массивами фиксированной длины. А освобождение памяти свелось бы к добавлению освобождаемого объекта к связному списку соответствующего типа. И затем аллокатор при наличии освобожденных объектов практически мгновенно мог бы "аллоцировать" новые, тупо вытаскивая объект из начала списка.

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


#121
19:53, 6 июля 2019

Dmitry_Milk
> Зачем тебе сплошные массивы?

+ Показать
#122
19:54, 6 июля 2019

Dmitry_Milk
> не получили бы мы гораздо больший выигрыш от такой скоростной аллокации
http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf

#123
20:41, 6 июля 2019

1 frag / 2 deaths
> Фрагментация

Так сама по себе она не страшна. Она страшна тем, что плохо переиспользует (или вообще не может пересипользовать, в зависимости от обстоятельств) освобожденную память при аллокации сплошных массивов произвольной длины. Избавься от этой необходимости - и фрагментация тебе будет пофиг, т.к. освобожденная память всегда будет переиспользользоваться по максимуму.

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

#124
(Правка: 20:50) 20:49, 6 июля 2019

1 frag / 2 deaths
> http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf

Какое это имеет отношение к моему предложению? Я предлагал "освобожденные объекты" держать в виде связного списка. Там аллокация и деаллокация - микроскопическое фиксированное время работы с началом списка. А в этой статье good average response times, да еще и unconstrained (всю статью, конечно не читал, только первую страницу).

#125
21:34, 6 июля 2019

Dmitry_Milk
> good average response times
Нет, там именно гарантия на время аллокации.

#126
15:33, 7 июля 2019

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

1 frag / 2 deaths
> Нет, там именно гарантия на время аллокации.

Ок, да, первый раз первую страницу прочел по диагонали, показалось, что DSA они свой алгоритм называют, оказывается под DSA они подразумевали любые алгоритмы работы с кучей. Но тем не менее, их TLSF все также борется с фрагментацией, причем не самыми тривиальными методами - и двухуровневая структура организации набора списков, и попытки слияния блоков через анализ заголовков блоков. А все проблемы фрагментации, как и в большинстве случаев, вот из-за этого - malloc(N) - по-прежнему аллокация рассматривается как "дайте мне N байтов". А кто сказал, что должно быть именно так?

Если пользоваться терминологией из этой статьи, то я подразумевал крайний идеальный случай Segregated Free Lists, когда сегрегация списков идет не просто по размерам блоков, а вообще по типам освобожденных объектов. И в таком случае:

- пофиг на фрагментацию. Она никогда не приведет к исчерпанию памяти из-за невозможности переиспользования, потому что набор типов в программе - конечный
- пофиг на все эти First Fit или Best Fit. Можно брать самый первый же блок в списке, и он будет Perfect Fit, потому что это память, оставшаяся от объекта точно такого же типа. (Более того, из этого можно даже извлечь некий профит, считая, что освобожденные объекты вообще никогда не "умирают" по-настоящему, а лишь переходят в состояние IsDead. Я где-то уже высказывал свою мысль про язык, в котором бы вообще не было бы понятия "освобождения памяти", ни ручного, ни автоматического. Что-то типа "Rust наоборот", когда компилятор не давал бы избавиться от владения объектом в куче просто выходом за пределы видимости или присвоением указателя на новый объект, а только предварительно передав владение кому-то еще. При этом можно было бы заимствовать ссылки сколь угодно долго).
- нет необходимости в сложных структурах для сегрегации списков. Указатель начала списка - это часть RTTI типа, адрес которой изизвестн на этапе компиляции, либо доступен через указатель на RTTI (вместо просто таблицы виртуальных методов) у объектов с виртуальными функциями. Соответственно и аллокация и деаллокация работают мгновенно, просто работая с началом связного списка. Естественно, аллокация так работает только при наличии уже освобожденных объектов. Иначе используется отрезание нового куска от пула (возможно, с наращиванием пула). Но никаких обратных слияний блоков друг с другом или с пулом - в этом нет необходимости, т.к. фрагментация уже не является врагом.

Очень может быть, что вышенаписанное уже кем-то предлагалось и исследовалось...

#127
16:17, 7 июля 2019

Dmitry_Milk
Ты предлагаешь чтоб когда мы грузили скажем текстуру, доступ к пикселю был за логарифм от размера текстуры (иногда. В зависимости от времени работы приложения и положения звёзд)?
Ну в js как-то так строки и сделаны, но в языках претендующих на производительность это, по-моему, не вариант.

#128
(Правка: 16:49) 16:48, 7 июля 2019

Все эти ваши проблемы со сферической фрагментацией в вакууме сродни охоте на ведьм.

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

http://www.paulgraham.com/knuth.html

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

#129
18:19, 7 июля 2019

kipar
> грузили скажем текстуру

Ну если какая-то универсальная софтина, которой надо мгновенно работать с текстурами в большом диапазоне размеров (от несколько-на-несколько пикселей до тысячи-на-тысячи) - то да, проблема. Если же конкретная софтина, скажем, игра, то мы скорее всего заранее знаем ориентировочные размеры текстур, а значит можем заранее определить типы-массивы достаточных фиксированных размеров (причем не обязательно одного, можно набор - для мелких, для средних, для больших; виртуальные функции с базовым классом или интерфейс позволят работать с ними унифицированно).

#130
18:20, 7 июля 2019

Dmitry_Milk
> Но тем не менее, их TLSF все также борется с фрагментацией, причем не самыми
> тривиальными методами - и двухуровневая структура организации набора списков, и
> попытки слияния блоков через анализ заголовков блоков.
Там под капотом тривиальная идея - тупо блоки фиксированного размера, составляющие связные списки, что ты и предлагал. Фиксированных размеров там несколько - 2,4,8,16,32 в простом случае. В аллокаторе по ссылке сделали чуть продвинутее, там градация 2,3,4,6,8,12,!6,24,32,...
Ну собсна и всё. Обычный маллок на самом деле тоже не так уж плох, гарантии у него правда нет, но в среднем он не хуже.

#131
(Правка: 18:26) 18:24, 7 июля 2019

1 frag / 2 deaths
> 2,4,8,16,32 в простом случае
В виндовом heapalloc (в который уходят маллок и крестонью) такое уже лет 15 для размеров меньше 16 KB
https://docs.microsoft.com/en-us/windows/win32/memory/low-fragmentation-heap

#132
18:25, 7 июля 2019

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

#133
18:36, 7 июля 2019

kipar
> грузили скажем текстуру

Вот, кстати, еще вариант придумался - нужен тип-массив фиксированного размера не под всю текстуру целиком, а только чтоб у самой большой целиком умещалась строка. Строки выделять независимо, указатели на них - в другой Y-массив, то есть просто вместо дереференса со сложением [y*width+x] будет двойной дереференс [y][x]. Причем этот же самый тип-массив можно использовать и для более мелких текстур, просто умещая по несколько строк в одном массиве, и ссылая их из Y-массива прямо на внутренние части X-массивов.

Скорей всего подобный метод можно и универсализировать (и вообще скрыть за библиотечной реализацией).

#134
18:36, 7 июля 2019

Dmitry_Milk
> пофиг на фрагментацию. Она никогда не приведет к исчерпанию памяти из-за невозможности переиспользования, потому что набор типов в программе - конечный
Ты предлагаешь завести по pool-у на каждый тип?
Это работает только если у тебя всего один тип, на крайняк несколько.
Когда типов много, то память, зарезервированная под один тип, не может быть использована под другой — это, по сути, фрагментация, причем в наихудшем ее проявлении.

Страницы: 16 7 8 9 10 11 Следующая »
ФлеймФорумПрограммирование