Моя новая любимая ошибка в Rust

Я сегодня много думал.
Думал о битсетах и Блум-фильтрах.
Захотелось мне создать Блум-фильтр-лайк структуру, по которой можно было бы итерироваться.
То есть вот буквально 3 операции. Добавить индекс, проверить наличие и проитерироваться.
С возможностью получить ложно положительные результаты в двух последних.

И вот идея.
Наверное многие из нас знакомы с иерархическими битсетами. Где мы ставим биты на нижнем уровне для отдельных индексов, а выше для все больших диапозонов, и так 3-4 и более уровней.
При итерации мы пропускаем огромные диапазоны если бит не выставлен. А если выставлен, то смотрим биты суб-диапазонов, спускаемся все ниже до отдельных индексов на каждый бит.

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

Как насчет использовать Блум-фильтр на каждом уровне? Сильно меньше чем целый бит на возможный индекс, а стремиться к 2 * сколько одновременно храним индексов.
А итерируемся так же. Просто с ложными индексами с небольшой вероятностью (пока не переполнили слишком фильтр).

Грубые подсчеты говорят, что должно быть сильно экономно.

Поставил Inkscape и нарисовал дракончика для логотипа Арканы.

Что скажете, сойдет или вообще ни к месту там дракон?

Все лошади одной масти и у меня есть доказательство.

Я докажу, что для любого натурального N, группа из N лошадей всегда одной масти.

Сначала рассмотрим базовый случай N = 1.
Очевидно, что любая группа из одной лошади будет одной масти, масти этой лошади.

Теперь построим индукцию.
Допустим что любая группа лошадей размера N одной масти.

Теперь рассмотрим группу размером N+1.

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

Значит из справедливости того что любая группа лошадей размера N одной масти следует что любая группа лошадей размером N+1 одной масти.

Мы имеем базовый кейс с N=1, а значит по вышеописанной индукции мы доказали это для N=2, а следовательно N=3 и так далее для любого натурального N

QED

Когда делал блюпринты для арканы, пришлось создавать и удалять много Box<dyn Any>, поэтому я сделал другой type-erased контейнер, который обходится без аллокаций для маленьких значений.
Назвал TAny от tiny any.
Понадобилось такое же вне арканы, поэтому я вытащил в отдельную либу и опубликовал ее.
Пришлось конечно сделать по этому поводу нормальную документацию и тесты. Зато баг нашел :)

https://docs.rs/tany

Может кто не видел, но ранее я публиковал подобную либу для функций

https://crates.io/crates/tiny-fn

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

Мы ждали ждали и дождались еще почти год будем ждать :)

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

Схема будет в комментарии, а пока милости прошу гадать :)

Когда сидишь олнайтер что бы добить этот мелкий бажок

Хотите научиться дефайнить числовые константы как эксперты уровня писателей стандартных либ?
Учитесь вот.

Я вам вот что могу сказать. 30 часовой рабочий день это очень фигово.
Недавно меня очень просили дофиксить все баги в фиче.
Фичу делал я и еще один чел и там было много чего тяп-ляп написано лишь бы показать в нужный день.
Потом снова подкрадывался день показа, а оно совсем не работало.
Значит фиксить целиком мне (ну не второму челу же).

В предпоследний день я решил задержаться на работе, что бы успеть сделать все же.
Задержался так что закончил только к вечеру следующего дня.
Потом всю неделю дико тормозил. Продуктивность упала до 10%, если не меньше.
А еще каждую ночь были кошмары про умножения матриц, лучи и градиентные спуски.

А показали то хоть? Да, но только еще через неделю 🙂

Вывод - кранчи того не стоят.

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

Я долго бился с ускорением ML рендер техники. Но тренировка никак не получалась быстрее 4мс.

Я пробовал:
1. Развернуть циклы. Видимо слишком много регистров надо, стало медленее.
2. Саккумулировать данные со всех тредов волны прежде чем писать их через atomicAdd.
3. Аккумулировать по всей группе, а не по волне. Стало еще хуже без wave-instrinsic-ов
4. Вместо атомиков писать в отдельные слоты и суммировать позже. Еще чуть хуже.
5. Кооперативную обработку одного сэмпла несколькихи тредами. Вообще жуть.


Я попробовал все сразу. И войля. 1.3мс

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

https://www.twitch.tv/randomrustdev

Первый стрим с кодингом на расте.
С места в карьер.
Разрабатывается Аркана.
Система импорта ассетов.

Сейчас начнется новый стрим.
Разработка импортера для картинок.
Ссылка та же

https://www.twitch.tv/videos/2277544249
Ссылка на запись стрима.
Я немного покосячил с окнами, но в целом получилось не так плохо, как мне кажется.

Сделали импортер для картинок, сделали UI для импорта, увидели, что что-то заимпортилось и получило AssetID.

Как вы думаете, на сколько надо подготавливаться заранее к стриму?

Я не имею в виду звук и настройку окон и вот это, что непосредственно стрим составляет. Это конечно надо все подготовить 🍳

Я про сам код. Я пробовал кодить с наскоку 🏇
Сегодня вот только убедился что создание плагина работает. Из-за чего эдитор перестал запускаться, когда я плагин удалил 🤦‍♂️
Но совершенно не продумывал как я буду писать. Только что.

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

Как по вашему мнению, где золотая середина?