Сейчас ясно что все сводят к треугольникам. Но я тут про 2D ускорители и алгоритмическую сложность. То что задача заливки треугольника сводиться к описанным двум трапециям я упомянул. А не наоборот! Достаточно вспомнить классический алгоритм заливки треугольника. (см. compgraphics.info/2D/triangle_rasterization.php ) Потому более гибким вариантом 2D апи будет, — иметь ускоритель трапеции. Не говоря уже о том, что она рендериться эффективнее.
А треугольник современный, это вообще другое! Он учитывает перспективу при текстурировнии. Т.е. у его вершин есть глубина! И это сразу привет 4х4 матрицы! Кстати как тут уже обсуждалось, матрицы в 2D таки приходили (см. SNES Mode7), но только Афинные 3х3 (можно и 2х3, норма на плоскости довольно бесполезна).
И подводя итог про апогей 2D функционала ускорителей:
— На мой взгляд он почему-то не наступил. Может из-за того, что поддержка более ресурсозатратных треугольников просто пришла раньше.
Вроде же в статье обьяснил. Или вам интересно конкретно зачем я хочу их нарезать? Но это тогда не корректный вопрос — Just we can, как говориться. Но могу ответить о практическом применении.
В действительности статья с практической т.з. слегка запоздала. Лет так на 50, во времена ZX Spectrum, когда набирали популярность видео ускорители. Она больше как «развлекательная математика». Однако, если постараться то практическое применение и кроме «разминки для мозга» этому еще можно найти:
— ПЛИСы для собственных задач графической отрисовки.
— Микроконтроллеры БЕЗ графического ускорения.
Да я понимаю что нарицательным, сам его так же использую, потому что keyword гуглиться. Просто лично его не застал, не достаточно олд я…
Хотя при анализе приема, для чего писался бенч, — Возможности этого режима позволят рендерить не только пол/небо, но даже что-то вроде DOOM1 like рейкастинга, теоретически. Только кастить надо будет интеллектуально, что бы получать углы стен.
— Кстати нужно заметить что HTML5 Canvas окружение без webGL является по сути тем же окружением. Встречал на этом алгоритмы развертки сферической панорамы в проекцию 3д камеры. Что бы сделать как в yandex панорамах. Как один из fallback'ов для неподдерживающих ничегошеньки устройств. Причем на CSS2 то же есть реализации, но суть не меняется — Суметь нарезать кривое на плоское
Да я писал его на высоком уровне по приколу. Но на сколько я узнавал исторически. На консолях это был специальный режим рисования спрайта, который аппаратно брал на себя ускорение конкретно афинных преобразований. Этого хватало только для поворота, масштаба и сдвига. Потому оси X и Y вращать было можно, — это есть в афинных. А вот Z нету, и ни как виртаульно она не добавлялась. Впрочем прямого управления ею нет в большинстве 3д игр. Перспектива же добавлялась хаком нарезания полос, но не обязательно только по строкам растра, иногда даже по несколько строк одним ректом, в зависимости от требований скорость/качество. Чем ближе была полоса, тем больше зум. А в консолях шел этот режим за номером семь. Я вспомнил его здесь как пасхалочку для знатоков.
Нашел сейчас его у себя в загашниках, но версию с классическим MODE7 для поворота/наклона/смещения положенного в перспективу пола деплоить лень (она не тема этой статьи и для интересующих это гуглиться) Зато могу задеплоить бенчмарк, который как раз не тривиально использует наклон:
codepen.io/impfromliga/full/qBNomVO
Скрол меняет угол наклона в поверхность.
Дополнительно колесо мыши меняет «скважность» полос для теста скорость/качество
Очень наглядно видно насколько большими полосами можно было относительно качественно эту перспективу хакать.
Если слои будут очень разряженные и их будет много выйгрыш потеряется.
хотя это скорее редкая ситуация. Более чем достаточно использовать 8-16 слоев, чтобы реализовать ВСЕ. И так и нужно делать.
500 вызовов это более чем достаточно, с огромным запасом!!!
Если учесть что рекурсия оправдана лишь там где идет ветвление.
Ведь не зря существует такое понятие как Хвостовая оптимизация рекурсии, ее смысл в том, что последний рекурсивный вызов функцией самой себя ВСЕГДА может (и по хорошему должен) быть повешен на цикл. Исходя из этого если у вас ветвление к примеру всего 2 рекурсивных вызова с глубиной стека 500, то функция отработает 2**500 раз (это число со 150 десятичными нулями) Т.е. глубина стека для рекурсивного алгоритма это 500я степень какого то коэффициента ветвления, поэтому это Очень много. Даже если представить странный случай «разреженной рекурсии» где второй вызов случается всего в 10% случаев — количество вызовов будет числом с 20ю нулями.
Т.о. проблема не в том, что стек мал. Да пусть он хоть стремится к бесконечности, если рекурсия была бы действительно оправдана, время выполнения вашего алгоритма было бы астрономическим… Вы просто используете рекурсию в алгоритме в котором она является антипатерном.
И «рекурсивный вызов» в setTimeout'е это не рекурсия, потому что это не «вызов», а «добавление события» в eventloop, это совершенно архитектурно разные вещи, вы просто тянете «визуально рекурсивный» паттерн туда где он не нужен. Есть async идеально подходящий для этого. Для кроссбраузерности есть промисы (которые в крайнем случае прекрасно полифилятся на callback'ах).
Если у вас проблема с переполнением стека, при дебаге оправданных рекурсивных функций можно добрасывать в параметр функции maxCallLength=const уменьшая его на каждый вызов. И обрабатывая кейс когда он стал нулевым. В иных случаях если при рекурсии происходит переполнение — у вас что то не так с алгоритмом.
Ничего не буду объяснять, нет времени, достал из своих загашников, в апи все и так написано, просто оставлю здесь этот лаконичный, быстрый, надежный, универсально расширяемый вариант:
Очень круто! Смотрю вы оперируете наверное почти всеми (включая малоизвестные) хаками!
Еще и своих добавили… Вдохновило! (Я тоже =) Вношу лепту:
!Disclaimer! Не бейте, сейчас будет JS. Сями я лишь под МК балуюсь, и тестить не где, да и нет толка от теста в отрыве от собирательного на одной машине.
Оно считает до 16 бит, используя 32х битную арифметику. Соответственно сравнивать его имеет смысл с аналогичным
Кодом из вашей статьи, (как я понимаю этим):
0 u8 CountOnes5 (u16 n) {
1 n -= (n>>1) & 0x5555;
2 n = ((n>>2) & 0x3333) + (n & 0x3333);
3 n = ((((n>>4) + n) & 0x0F0F) * 0x0101) >> 8;
4 return n; // Здесь происходит неявное обрезание по 8 младшим битам.
5 }
Я уже писал раньше такие штуки. Но сейчас, открыл у вас новый алгебраический хак (в первой строке) и захотел с ним миксануть. Кстати, в конце отдельно выскажу свои мысли по поводу его скрытого потенциала.
(Тестить бинарником не буду)
Но на примитивных инструкциях примерно можно сравнить на глазок. Все вычисления зависимые (кроме одной инструкции в вашей второй строке). Если считать с конца 3-4-5 строки не содержат скоростных различий и даже (почти) порядка операций. Да у меня IF, но (внимание) у меня вместо этого совсем отсутствует ваша 2я строка…
Это получилось сделать т.к. я на шаг раньше (и в итоге дважды) ухожу в тиражирование.
Однако из-за этого второе тиражирование приходиться делать по-16ти-разрядно, потому результат не может хранить значение больше 15. И это нужно проверять. Хотя на архитектурах с Brunch Prediction это будет вероятно быстрее, чем 4, пусть и простейшие инструкции, пусть одна из них и может попасть под Hyperthreading
Прокомментирую отдельно еще не свойственный для JS imul()
— дело в том, что переполнение при умножении в JS дает (float) Infinity
А используя прием тиражирования бит мне собстеннно абсолютное значение до лампочки. imul() появился как решение и в частности в связи с AsmJS и активной сейчас разработкой WASM. Как заявлено в доке это C-like умножение. (т.е. без неявностей с float'ами)
И теперь еще слово о найденном у вас замечательном арифметическом хаке:
По сути своей такое действие эквивалентно попарному полусумматору: // ab - a = a + b //буквы в литералах - это одинаковые битовые разряды
//x-=(x»1& 0b...0101) //многоточия в 0b литералах означают периодическое повторение бит константы
x-=x»1&0x55555555;
// a.b - aa = a + b //точки в литералах - любые сторонние битовые разряды
//x-=(x»2& 0b...001001)*0b...011011;
x-=(x»2& 0x49249249)*0xDB6DB6DB;
т.е. можно попарно одновременно получать AND и XOR от групп битов
а эти операции, являются достаточными для Жигалкина для любых сочетаний…
и еще в сочетании с возможностью не сильно дорого сдвигать их более чем на одну позицию
я подозреваю пригодность этой техники для быстрой криптографии и прочих стремительных, в особенности итеративных алгоритмов… быть может даже на длинной арифметике, ибо есть возможность мульти-одновременно протаскивать группы бит (скользящий накопитель — ядро вычета) на заранее не определенные позиции при итеративном проходе
Отличная статья, очень широко обозревает возможности. Нашел в ней упоминание практически всего, что до этого накопал раздельно.
Есть у меня одна идейка, не дающая покоя. Хочется сделать точную (<1метра) пеленгацию bluetooth смартфонов в помещении (скажем до 30х30м). Собирая информацию я видел пока что в основном это делают за счет анализа мощности сигнала до опорных узлов. (вероятно потому что предназначаются такие системы в основном для «тонких» максимально дешевых маячков) Но с этим есть довольно сильные ограничения на точность (ибо интерференция и препятствия создают рандомные затухания).
Возможно ли применить сканирование вращая диаграмму? Ведь для таких частот (и малых размеров излучателей) совершенно не обязательно изготавливать сложную систему динамической направленности через множество излучателей с фазосдвигателями. Может достаточно было бы быстро вращать вокруг диполя цилиндрический щелевой экран. (Или каким то более подходящим механическим методом) Получив идейно что то похожее на строчную развертку луча в кинескопах. Добившись передачи пакетов данных с координатами углов только по соответствующим направлениям. Линейная скорость вращения экрана будет мизерной по сравнению со скоростями микроконтроллера занимающегося синхронизацией.
В bluetooth 5 вроде появились смутные намеки на получение угла прихода радиосигнала, но стандартизация говорят ужасна, да и не распространен он пока.
Кто нибудь из знающих людей может развеять или подтвердить предположение о такой возможности? (Желательно со ссылкой на теоретическую часть.)
Поканальное деление (на 2 с потерей бита) оптимизировать можно, но даленейшее вычисление зависимо через накопитель. Потому будет какой то оверхед на доп операции, какой — вопрос тестирования. Но может и получиться что то ещё выйграть. В любом случае гарантировано ускорить вертикальный проход в ~четверо было бы неплохо.
Но сейчас основным минусом Алга является константный радиус. Я думаю что возможно рассчитать более качественные константы для больших радиусов.
Про универсальность (не бейте палкой) — v8 aka Самый популярный движок вездесущего интернета, а по совместительству и webapp, — с вами не согласен. 32бит все что он стандартизировал для всех платформ.
SIMD — Отличная идея для «шейдерного» подхода под CPU, соседние строки/столбцы проходов являются независимыми, потому если оставлять хотя бы 2 прохода, можно. Но на горизонталях вопрос перепаковки (столбцов в строки) встает утяжеляя алгоритм (это даже если все попадает в кеш), так что прирост может на выходе захлебнуться. Надо проверять. В прочем ускорить только вертикальный проход так получиться.
На самом деле я уже пробовал вынимать из ARGB G в отдельный канал, зануляя его в исходнике, чтоб работать с запасом бит, но диже это оказалось медленнее. В исходном алгоритме итак предельно быстрые инструкции
Именно так как вы и пишите, не затрагивая сам блюр фильтр и можно добавить, только «после» сказали и тут же опровергли вы, а не я. Естественно коррекция на входе и выходе.
Про битность я уточнил как раз перед вами, habr.com/post/427077/#comment_19292437
(И тот факт, что это будет означать, что для удобной коррекции гаммы придется либо отказаться от 3х-канального хака, либо не повышая битность, терпеть большие погрешности)
Кстати для 64бит архитектур возможен качественный запил того же 3х канального хака только с int64 (просто на стадии коррекции понадобиться перепаковать)
(вопрос наверное забыл поставить)
Я его не знаю, у меня просто в закладках уже была хорошая статья, спросил только своего друга, красноглазого сишника, на предмет оценки ее валидности. Он сказал, что результаты похожи на то что он получал. Но в любом случае на это нельзя сколько нибудь строго опираться.
upd: а все понял. Ну просто вы тоже спрашивали про оценку, я решил ответить сразу в эту ветку (не думаю что я особо много тут комментариев соберу, тема то специфичная)
Понял свою ошибку.
Ну теперь ради фана и желая идти до конца, — пишем Дизеринг-Блюр!
*иронично* Он может быть еще быстрее (Битовая сложность позволяет)
1.Увеличить размытие в данной реализации нет нельзя, это связанно со скоростным битовым хаком. Данный алгоритм для константного радиуса. Однако константа может быть х7 х15 х31 (однако учтите, что каждая следующая имеет большую погрешность 31 так тот вообще нежелательно использовать без дополнительного прохода х7), если интересно можете попробовать демо тут codepen.io/impfromliga/pen/VERzPJ блюр х7 х15 х31 прибинжен на клавиши 1,2,3
+ в принципе имеющихся уровней размытия достаточно чтобы если нужно больше получать даунсемплированием (масштабировать сжимая -> блюрить -> масштабировать увеличивая) т.к. пикселизация тем менее заметна глазу на картинках, чем более они размыты. (естественно есть потолок у такого способа) реализация такого блюра через даунсемплирование может быть сделано так же однопроходно (встроена в алг, чтоб ни чего не пережимать предварительно, и не тратя памяти и времени, слышал такая практика существует для облегчения шейдеров)
2.Края темнеют (это называется стратегия заполнения, фон за пределами растра считается черным, потому такое размытие вполне честно, стратегии бывают разные, можно поменять алгоритм под белый/серый цвет/ под взятие цвета с противоположной стороны/ под взятие ближайшего крайнего/ под медианку из некоторых пикселей в краевой зоне… по вашему вкусу)
— Здесь чтобы не перегружать суть алгоритма, стратегия была выбрана простейшая
В каком смысле? Думаете он не успеет? (Я просто по его скоростям и возможностям не шарю) Или имеете ввиду что под него уже ни кому не надо?
Во втором случае хочу немного заступиться, если не за спеку, то хотя бы за алгоритмы в целом. Сами по себе они в принципе бесполезны, но будучи реализованы под одно дают идеи и подходы, чаще всего переносимые под нужды. Хотя бы ради открытия/освежения этих идей и подходов они оправданы.
Неудобно мне как то давать столь не точные ответы на техническом ресурсе.
Но если вы настаиваете потеоретизировать на предмет прироста скорости на AMDx64
(снимаю с себя какую либо ответственность за дальнейшие размышления)
То предположив точной выдержку из habr.com/company/otus/blog/343566 о скорости инструкций:
Сдвиг ~1 такт (если автор статьи относил его к простым инструкциям)
Целое деление — 12-44 тактов (DIV/IDIV)
Float деление — до 37-39 тактов (FDIV)
SEE деление — 10-40 тактов
SEE умножение — 0.5-5 тактов
Можно предположить что мой выигрыш против CPU реализации гаусса отсюда habr.com/post/151157 (быстрее этой реализации я не видел, хотя она тоже аппроксимация, но не ограничено точная)
посчитав даже по минимому
4x SSE умножения = +4такта
2х сложения = +2 такта
2х вычитания = +2 такта
(игнорируя чтения которых тут больше, но предположим, что все попало в кеш)
= 8 тактов
х 3 канала
= 24 такта
против
2х сдвига = 2 такта
2х маскирование = 2 такта
2х сложение = 2 такта
= 6 тактов (все три канала сразу)
отсюда грязная оценка может быть даже выше х4 прирост относительно «intel-точного» гаус блюра, но с погрешностью 97% и для константного радиуса, зато с понижением требований к окружению исполнения (не требуется SSE, ни плавающей арифметики, ни даже деления, а уж маски и сдвиги и сложения есть везде)
А треугольник современный, это вообще другое! Он учитывает перспективу при текстурировнии. Т.е. у его вершин есть глубина! И это сразу привет 4х4 матрицы! Кстати как тут уже обсуждалось, матрицы в 2D таки приходили (см. SNES Mode7), но только Афинные 3х3 (можно и 2х3, норма на плоскости довольно бесполезна).
И подводя итог про апогей 2D функционала ускорителей:
— На мой взгляд он почему-то не наступил. Может из-за того, что поддержка более ресурсозатратных треугольников просто пришла раньше.
вам показать не удержусь и свой JS'ный The Life код:
codepen.io/impfromliga/pen/pyBJvM — в размер до 256b
codepen.io/impfromliga/pen/qZwbQN — с коментариями
В действительности статья с практической т.з. слегка запоздала. Лет так на 50, во времена ZX Spectrum, когда набирали популярность видео ускорители. Она больше как «развлекательная математика». Однако, если постараться то практическое применение и кроме «разминки для мозга» этому еще можно найти:
— ПЛИСы для собственных задач графической отрисовки.
— Микроконтроллеры БЕЗ графического ускорения.
Хотя при анализе приема, для чего писался бенч, — Возможности этого режима позволят рендерить не только пол/небо, но даже что-то вроде DOOM1 like рейкастинга, теоретически. Только кастить надо будет интеллектуально, что бы получать углы стен.
— Кстати нужно заметить что HTML5 Canvas окружение без webGL является по сути тем же окружением. Встречал на этом алгоритмы развертки сферической панорамы в проекцию 3д камеры. Что бы сделать как в yandex панорамах. Как один из fallback'ов для неподдерживающих ничегошеньки устройств. Причем на CSS2 то же есть реализации, но суть не меняется — Суметь нарезать кривое на плоское
Нашел сейчас его у себя в загашниках, но версию с классическим MODE7 для поворота/наклона/смещения положенного в перспективу пола деплоить лень (она не тема этой статьи и для интересующих это гуглиться) Зато могу задеплоить бенчмарк, который как раз не тривиально использует наклон:
codepen.io/impfromliga/full/qBNomVO
Скрол меняет угол наклона в поверхность.
Дополнительно колесо мыши меняет «скважность» полос для теста скорость/качество
Очень наглядно видно насколько большими полосами можно было относительно качественно эту перспективу хакать.
хотя это скорее редкая ситуация. Более чем достаточно использовать 8-16 слоев, чтобы реализовать ВСЕ. И так и нужно делать.
Если учесть что рекурсия оправдана лишь там где идет ветвление.
Ведь не зря существует такое понятие как Хвостовая оптимизация рекурсии, ее смысл в том, что последний рекурсивный вызов функцией самой себя ВСЕГДА может (и по хорошему должен) быть повешен на цикл. Исходя из этого если у вас ветвление к примеру всего 2 рекурсивных вызова с глубиной стека 500, то функция отработает 2**500 раз (это число со 150 десятичными нулями) Т.е. глубина стека для рекурсивного алгоритма это 500я степень какого то коэффициента ветвления, поэтому это Очень много. Даже если представить странный случай «разреженной рекурсии» где второй вызов случается всего в 10% случаев — количество вызовов будет числом с 20ю нулями.
Т.о. проблема не в том, что стек мал. Да пусть он хоть стремится к бесконечности, если рекурсия была бы действительно оправдана, время выполнения вашего алгоритма было бы астрономическим… Вы просто используете рекурсию в алгоритме в котором она является антипатерном.
И «рекурсивный вызов» в setTimeout'е это не рекурсия, потому что это не «вызов», а «добавление события» в eventloop, это совершенно архитектурно разные вещи, вы просто тянете «визуально рекурсивный» паттерн туда где он не нужен. Есть async идеально подходящий для этого. Для кроссбраузерности есть промисы (которые в крайнем случае прекрасно полифилятся на callback'ах).
Если у вас проблема с переполнением стека, при дебаге оправданных рекурсивных функций можно добрасывать в параметр функции maxCallLength=const уменьшая его на каждый вызов. И обрабатывая кейс когда он стал нулевым. В иных случаях если при рекурсии происходит переполнение — у вас что то не так с алгоритмом.
//lib
function bsrc(arr, search){
var toValue = arguments[2] || search.toValue || (f=>f);
search = toValue(search);
for(var x1=0, mid, x2=arr.length; x1 < x2;){
mid = x2+x1-1>>1;
if(toValue(arr[mid]) > search) x2=mid;
else x1=mid+1;
}
return (x1%=arr.length) && toValue(arr[x1-=1])==search ? x1:-1;
}
//prepare 1:
var arr = [3, 24, 32, 35, 38, 45, 46, 49, 52, 52, 69, 71, 75, 77, 78, 89, 89, 90, 96, 99];
//usage 1:
bsrc(arr,35);
//prepare 2:
var arr = [3, 24, 32, 35, 38, 45, 46, 49, 52, 52, 69, 71, 75, 77, 78, 89, 89, 90, 96, 99];
arr.bsrc = bsrc.bind(this,arr);
//usage 2:
arr.bsrc(38);
//prepare 3:
var arr = [{key:8, val:3}, {key:10, val:24}, {key:15, val:32}, {key:21, val:35}, {key:39, val:38}];
arr.bsrc = bsrc.bind(this,arr);
//usage 3:
arr.bsrc({val:32},f=>f.val);
arr.bsrc({key:21},f=>f.key);
Еще и своих добавили… Вдохновило! (Я тоже =) Вношу лепту:
!Disclaimer! Не бейте, сейчас будет JS. Сями я лишь под МК балуюсь, и тестить не где, да и нет толка от теста в отрыве от собирательного на одной машине.
Оно считает до 16 бит, используя 32х битную арифметику. Соответственно сравнивать его имеет смысл с аналогичным
Кодом из вашей статьи, (как я понимаю этим):
0 u8 CountOnes5 (u16 n) {1 n -= (n>>1) & 0x5555;
2 n = ((n>>2) & 0x3333) + (n & 0x3333);
3 n = ((((n>>4) + n) & 0x0F0F) * 0x0101) >> 8;
4 return n; // Здесь происходит неявное обрезание по 8 младшим битам.
5 }
Я уже писал раньше такие штуки. Но сейчас, открыл у вас новый алгебраический хак (в первой строке) и захотел с ним миксануть. Кстати, в конце отдельно выскажу свои мысли по поводу его скрытого потенциала.
Итак вот мой код:
0 var popu16=x=>{1 if(x>=65535)return 16;
2 x-=x>>1&0x5555;
3 x=(x<<14|x)&0x33333333;
4 return Math.imul(x,0x11111111)>>>28;
5 }
(Тестить бинарником не буду)
Но на примитивных инструкциях примерно можно сравнить на глазок. Все вычисления зависимые (кроме одной инструкции в вашей второй строке). Если считать с конца 3-4-5 строки не содержат скоростных различий и даже (почти) порядка операций. Да у меня IF, но (внимание) у меня вместо этого совсем отсутствует ваша 2я строка…
Это получилось сделать т.к. я на шаг раньше (и в итоге дважды) ухожу в тиражирование.
Однако из-за этого второе тиражирование приходиться делать по-16ти-разрядно, потому результат не может хранить значение больше 15. И это нужно проверять. Хотя на архитектурах с Brunch Prediction это будет вероятно быстрее, чем 4, пусть и простейшие инструкции, пусть одна из них и может попасть под Hyperthreading
Прокомментирую отдельно еще не свойственный для JS imul()
— дело в том, что переполнение при умножении в JS дает (float) Infinity
А используя прием тиражирования бит мне собстеннно абсолютное значение до лампочки. imul() появился как решение и в частности в связи с AsmJS и активной сейчас разработкой WASM. Как заявлено в доке это C-like умножение. (т.е. без неявностей с float'ами)
И теперь еще слово о найденном у вас замечательном арифметическом хаке:
По сути своей такое действие эквивалентно попарному полусумматору:
// ab - a = a + b //буквы в литералах - это одинаковые битовые разряды
//x-=(x»1& 0b...0101) //многоточия в 0b литералах означают периодическое повторение бит константы
x-=x»1&0x55555555;
// a.b - aa = a + b //точки в литералах - любые сторонние битовые разряды
//x-=(x»2& 0b...001001)*0b...011011;
x-=(x»2& 0x49249249)*0xDB6DB6DB;
// a..b -aaa = a+b
//x-=(x»3& 0b...00010001)*0b...01110111;
x-=(x»3& 0x11111111)*0x77777777;
т.е. можно попарно одновременно получать AND и XOR от групп битов
а эти операции, являются достаточными для
Жигалкинадля любых сочетаний…и еще в сочетании с возможностью не сильно дорого сдвигать их более чем на одну позицию
я подозреваю пригодность этой техники для быстрой криптографии и прочих стремительных, в особенности итеративных алгоритмов… быть может даже на длинной арифметике, ибо есть возможность мульти-одновременно протаскивать группы бит (скользящий накопитель — ядро вычета) на заранее не определенные позиции при итеративном проходе
Есть у меня одна идейка, не дающая покоя. Хочется сделать точную (<1метра) пеленгацию bluetooth смартфонов в помещении (скажем до 30х30м). Собирая информацию я видел пока что в основном это делают за счет анализа мощности сигнала до опорных узлов. (вероятно потому что предназначаются такие системы в основном для «тонких» максимально дешевых маячков) Но с этим есть довольно сильные ограничения на точность (ибо интерференция и препятствия создают рандомные затухания).
Возможно ли применить сканирование вращая диаграмму? Ведь для таких частот (и малых размеров излучателей) совершенно не обязательно изготавливать сложную систему динамической направленности через множество излучателей с фазосдвигателями. Может достаточно было бы быстро вращать вокруг диполя цилиндрический щелевой экран. (Или каким то более подходящим механическим методом) Получив идейно что то похожее на строчную развертку луча в кинескопах. Добившись передачи пакетов данных с координатами углов только по соответствующим направлениям. Линейная скорость вращения экрана будет мизерной по сравнению со скоростями микроконтроллера занимающегося синхронизацией.
В bluetooth 5 вроде появились смутные намеки на получение угла прихода радиосигнала, но стандартизация говорят ужасна, да и не распространен он пока.
Кто нибудь из знающих людей может развеять или подтвердить предположение о такой возможности? (Желательно со ссылкой на теоретическую часть.)
Поканальное деление (на 2 с потерей бита) оптимизировать можно, но даленейшее вычисление зависимо через накопитель. Потому будет какой то оверхед на доп операции, какой — вопрос тестирования. Но может и получиться что то ещё выйграть. В любом случае гарантировано ускорить вертикальный проход в ~четверо было бы неплохо.
Но сейчас основным минусом Алга является константный радиус. Я думаю что возможно рассчитать более качественные константы для больших радиусов.
SIMD — Отличная идея для «шейдерного» подхода под CPU, соседние строки/столбцы проходов являются независимыми, потому если оставлять хотя бы 2 прохода, можно. Но на горизонталях вопрос перепаковки (столбцов в строки) встает утяжеляя алгоритм (это даже если все попадает в кеш), так что прирост может на выходе захлебнуться. Надо проверять. В прочем ускорить только вертикальный проход так получиться.
На самом деле я уже пробовал вынимать из ARGB G в отдельный канал, зануляя его в исходнике, чтоб работать с запасом бит, но диже это оказалось медленнее. В исходном алгоритме итак предельно быстрые инструкции
Про битность я уточнил как раз перед вами, habr.com/post/427077/#comment_19292437
(И тот факт, что это будет означать, что для удобной коррекции гаммы придется либо отказаться от 3х-канального хака, либо не повышая битность, терпеть большие погрешности)
Кстати для 64бит архитектур возможен качественный запил того же 3х канального хака только с int64 (просто на стадии коррекции понадобиться перепаковать)
Я его не знаю, у меня просто в закладках уже была хорошая статья, спросил только своего друга, красноглазого сишника, на предмет оценки ее валидности. Он сказал, что результаты похожи на то что он получал. Но в любом случае на это нельзя сколько нибудь строго опираться.
upd: а все понял. Ну просто вы тоже спрашивали про оценку, я решил ответить сразу в эту ветку (не думаю что я особо много тут комментариев соберу, тема то специфичная)
Ну теперь ради фана и желая идти до конца, — пишем Дизеринг-Блюр!
*иронично* Он может быть еще быстрее (Битовая сложность позволяет)
+ в принципе имеющихся уровней размытия достаточно чтобы если нужно больше получать даунсемплированием (масштабировать сжимая -> блюрить -> масштабировать увеличивая) т.к. пикселизация тем менее заметна глазу на картинках, чем более они размыты. (естественно есть потолок у такого способа) реализация такого блюра через даунсемплирование может быть сделано так же однопроходно (встроена в алг, чтоб ни чего не пережимать предварительно, и не тратя памяти и времени, слышал такая практика существует для облегчения шейдеров)
2.Края темнеют (это называется стратегия заполнения, фон за пределами растра считается черным, потому такое размытие вполне честно, стратегии бывают разные, можно поменять алгоритм под белый/серый цвет/ под взятие цвета с противоположной стороны/ под взятие ближайшего крайнего/ под медианку из некоторых пикселей в краевой зоне… по вашему вкусу)
— Здесь чтобы не перегружать суть алгоритма, стратегия была выбрана простейшая
В каком смысле? Думаете он не успеет? (Я просто по его скоростям и возможностям не шарю) Или имеете ввиду что под него уже ни кому не надо?
Во втором случае хочу немного заступиться, если не за спеку, то хотя бы за алгоритмы в целом. Сами по себе они в принципе бесполезны, но будучи реализованы под одно дают идеи и подходы, чаще всего переносимые под нужды. Хотя бы ради открытия/освежения этих идей и подходов они оправданы.
Но если вы настаиваете потеоретизировать на предмет прироста скорости на AMDx64
(снимаю с себя какую либо ответственность за дальнейшие размышления)
То предположив точной выдержку из habr.com/company/otus/blog/343566 о скорости инструкций:
Сдвиг ~1 такт (если автор статьи относил его к простым инструкциям)
Целое деление — 12-44 тактов (DIV/IDIV)
Float деление — до 37-39 тактов (FDIV)
SEE деление — 10-40 тактов
SEE умножение — 0.5-5 тактов
Можно предположить что мой выигрыш против CPU реализации гаусса отсюда habr.com/post/151157 (быстрее этой реализации я не видел, хотя она тоже аппроксимация, но не ограничено точная)
Там в центре стреляет такая функция:
посчитав даже по минимому
4x SSE умножения = +4такта
2х сложения = +2 такта
2х вычитания = +2 такта
(игнорируя чтения которых тут больше, но предположим, что все попало в кеш)
= 8 тактов
х 3 канала
= 24 такта
против
2х сдвига = 2 такта
2х маскирование = 2 такта
2х сложение = 2 такта
= 6 тактов (все три канала сразу)
отсюда грязная оценка может быть даже выше х4 прирост относительно «intel-точного» гаус блюра, но с погрешностью 97% и для константного радиуса, зато с понижением требований к окружению исполнения (не требуется SSE, ни плавающей арифметики, ни даже деления, а уж маски и сдвиги и сложения есть везде)