R
Буквально такое же устройство памяти, только сплиты делаются за О(1) с помощью битмапной магии.
Мы когда обсуждали, я как чувствовал что такое уже где-то видел
Size: a a a
2020 October 26
MS
Я тем временем думаю как можно уменьшить амортизацию чтоб оно аллоцировало за О(1) или как можно более близкое к нему О(N) в как можно большем количестве случаев. Ну кроме сохранения индекса последнего заведомо свободного блока.
MS
(Не то чтоб это было нужно, просто это весело)
P🍣
Формула Родрига выводится из клиффордовой алгебры.
Чел вывел ее из линейки. Можно по разному одно и тоже доказывать.
R
Я тем временем думаю как можно уменьшить амортизацию чтоб оно аллоцировало за О(1) или как можно более близкое к нему О(N) в как можно большем количестве случаев. Ну кроме сохранения индекса последнего заведомо свободного блока.
Между O(1) и O(N) есть еще sweet spot O(log N)
MS
Между O(1) и O(N) есть еще sweet spot O(log N)
Ты предлагаешь как-то сортировать мапы по степени заполненности чтоб можно было искать по ним бисекцией?
R
Сортировать долго
R
Разве что сортировать амортизировано как-то
MS
Проблема эффективно найти мапу с дыркой нужного размера, при том что размеры бывают разные. По чему сортировать?
MS
То есть сама мапа - это по сути дерево, но в этом дереве можно проверить доступность и зааллоцировать за фиксированное количество битовых операций, так что все [интересные нам] операции над ним О(1). Но таких мап у нас может быть много, и я хочу с помощью какого-нибудь хитрого способа гарантировать при аллокации что нужная мапа окажется на подхвате.
MS
Если что, сейчас вот так происходит чек на свободное место: https://gitlab.com/niksaak/lofi/-/blob/master/src/alloc.rs#L88
А вот так аллокация:
https://gitlab.com/niksaak/lofi/-/blob/master/src/alloc.rs#L93
А вот так аллокация:
https://gitlab.com/niksaak/lofi/-/blob/master/src/alloc.rs#L93
A
С деревом обычно log n и получается, хотя я мимокрокодил и не до конца понял ваши проблемы))))
MS
Там мапа это ненастоящее дерево. Это полное бинарное дерево булеанов в котором каждый парент - это одновременно и свой собственный левый чайлд.
MS
За счет чего с ним можно работать с помощью кучки масок и битовых операций.
MS
(см. низ файла и коммент вверху)
2020 October 27
ДС
кто-нибудь грузил dds через крейт image? мне нужны сырые данные из dds, без декодирования, просто залить на гпу сразу
ВМ
Вопрос залу -- как мне исправить мой неарест фильтр в софтаче чтобы не было этих "зигзагов"?
ВМ
или это зло неизбежное?
ВМ
есть идея "суперсемплить" и усреднять