Ну отлично, а я свой алгоритм переделал — результат за 5 мс и никакой лесенки. Вот соотношение сигнал/шум в сравнении 8SED с брутом: 91.58 dB. Ошибки всего в паре пикселей. 90 децибелл это отличный результат, при сжатии изображений нормальным отклонением является где-то 50 dB.
Я вспомнил как я делал. Сначала нашёл алгоритм 8SSEDT, он в общем работал, но очень медленно. Затем нашёл статью, где предполагался более быстрый метод и реализовал его. Но математики тоже шутят и в статье оказались баги (на глаз не отличить, но благодаря вашему посту я заметил разницу). Переделаю обратно на улучшенный 8SED.
Так как мы храним дельты по осям: dx и dy, а сравнивать нам нужно дистанцию (и записывать минимальную), то нам придется каждый раз вычислять квадрат расстояния dx*dx+dy*dy, чтобы мы могли его сравнить. Авторы решили сэкономить на этом.
Это на самом деле я и есть автор этого бреда. С математической точки зрения это выглядит как неоптимизированный код, но на самом деле эта функция написана специально под компилятор (ветвления выкидываются путём подстановки констант) — то есть в финальном скомпилированном варианте не будет практически ни единого ветвления. И доп. переменную с квадратом расстояния тоже делал я:) Поскольку мне надо было добиться скорости алгоритма менее 1 секунды для изображения 4к, получился вот такой монстр. Сделать лучше при той же производительности не получилось (этот код быстрее где-то на 15%).
Но комментарий не мешало бы оставить, так как с бородатых лет я уже сам не помню, что я тут натворил. Причем я потом нашёл такую же оптимизацию в китайской статье, которую приводил в ссылках, но там сам алгоритм неточный.
Для сравнения, картинка, которую я получил методом брутфорса. Прямолинейный простейший алгоритм. И тут тоже лесенка:
Так что это либо повод задуматься, либо я где-то ошибся… Но рискну предположить, что ваш метод на GPU ещё как-то учитывает антиалиасинг и сглаживает переходы в ущерб точности, но в пользу красоты результата.
Далее по производительности (Core 2 quad):
брутфорс — 462 сек
8SSEDT — 0.046 сек (46 мс)
Как видно, практически также быстро как GPU. У меня правда он ещё два прохода считает (знаковая карта расстояний), эти два прохода можно запустить на двух процессорах без особых проблем. SIMD там прикрутить тоже можно, но лениво.
У меня алгоритм 8SSEDT, только что выяснил. Дело давно было, а ступеньки и прочее — ошибки реализации. Я когда искал хоть какой-то алгоритм, было днём с огнём не сыскать. Сейчас если чуть-чуть копнуть — оказывается существует десяток методов.
Хоть вы и ссылаетесь на мою реализацию, у меня не получается такая ярко выраженная «звезда»:
Принцип такой же (окно 3х3), но возможно алгоритм модифицированный. Ещё на картинки видны какие-то артефакты на удалении, но это похоже на ошибку в реализации.
Более того, нормальные компиляторы уже давно умеют выдавать предупреждения практически по всем описанным в статье нюансам, и это я даже не говорю про компилятор-анализатор clang. Оба компилятора доступны студентам безо всяких унижений.
Но проще сказать чем сделать — кто из студентов смотрит на предупреждения компилятора, сдавая зачёт в последний день? И кто сказал, что такие студенты начнут пользоваться анализаторами, стыдливо показывая пустую зачётку?:)
Хм, а с каких пор научились удалять данные из оперативной памяти методом Гутманна, можно поподробнее?
Из заголовка статьи я так понял, что смысл всего этого — ленивое освобождение памяти, с чем пул справляется превосходно, более того, объектная система GTK вообще позволяет практически не освобождать память за счёт выстраивания иерархии указателей. Когда мы говорим о защите памяти, то как правило я подразумеваю что-то вроде ASLR, NX-bit, PaX, но никак не Гутманна.
Скорее всего, другие читатели вас тоже не поймут, так как статья начинается со слов «чтобы не пичкать код вызовами free», а далее начинается отдельная история про защиту памяти и надёжность.
Лично я выбрал для себя Linux-like стиль программирования с активным использованием goto (да-да).
Тогда смысл песочницы я вообще не понял, хотя пролистал статью несколько раз. В принципе, я могу и при помощи malloc выделить кусок памяти размером 64 килобайт и потом сделать для него free в конце программы (кстати GNU не считает за ошибку, если free вообще не делать для долгоживущих объектов), а что станет с песочницей, когда 64 КБ будет мало и нужно будет сделать realloc?
* запускаем наше хозяйство с выводом в простой текстовый файл, и сохраняем его куда-нибудь в укромное место как «эталон»
* повторный запуск — сравниваем результат с эталонным файлом чем-то вроде diff
* обновляем тесты — обновляем эталон
Просто потому что пост-инкремент ведёт себя в понимании программистов «правильно», но если поменять его на пре-инкремент, большинство удивляется результату. То что компилятор генерирует правильный код ещё не означает, что это не UB. Хотя конечно компилятор мог бы кинуть хотя бы предупреждение, gcc молчит как партизан, зато clang выдаёт:
test.c:4:29: warning: unsequenced modification and access to 'i' [-Wunsequenced]
for(i = 0; i < 10; a[i] = i++);
Если вас и компилятор не убедит, то мне и подавно никто не поверит.
Это кстати есть в Frequently Reported Bugs GCC. Если кратко — всё, что происходит между точками следования, может происходить в произвольном порядке на усмотрение компилятора. Просто компиляторы научились предугадывать такие финты программистов, поэтому если отбросить экзотику, остаются только gcc, clang и VS, которые старательно избегают подобного рода багов в программах — в противном случае общественность обвинит компилятор в том, что «нормальные» программы в нём не собираются.
Так и речь не о том, что анализатор взял и выдал: «у вас CVE-2014-XXXX в строке номер 150», а о том, насколько реально помогли анализаторы при ловле этих самых CVE. Касательно аудита безопасности успешных примеров пока маловато, чтобы говорить о том, что анализатор помогает в обнаружении уязвимостей. Ибо уязвимость — это не просто ошибка, а ошибка, которую (пусть даже в теории) можно проэксплуатировать, но анализатор не может подсказать, как именно, он не знает особенности этой программы и не знает, что в этой строке может оказаться пароль или внешние данные. Именно поэтому мы редко видим новости «Анализатор ХХХ помог найти уязвимость YYY», хотя уязвимости в СПО отстреливают ежедневно.
Доля уязвимостей, найденных статическими анализаторами ничтожно мала по сравнению с тем, на что натыкаются эксперты при анализе кода. Стоило обратить внимание людей на шеллшок, как там нашли сразу по меньшей мере 6 (!) уязвимостей и наложили около 30 патчей.
Из последних на моей памяти реально присвоенных CVE, что нашли анализаторы — уязвимость в Х.org, которую нашёл cppcheck. Это капля в море в пересчёте на адское количество ложных срабатываний.
В итоге так и живём — вся суть отечественного аудита кода заключается в гуглении CVE-шек из OpenSource проектов.
Там не так остро стоит проблема зависимостей. Даже опенсорсный софт для винды пакуется со всеми библиотеками в то время как в линуксе он честно тянет зависимости.
В некоторых случаях это даже лучше. В Linux наоборот идут в сторону контейнеров для софта.
Я вспомнил как я делал. Сначала нашёл алгоритм 8SSEDT, он в общем работал, но очень медленно. Затем нашёл статью, где предполагался более быстрый метод и реализовал его. Но математики тоже шутят и в статье оказались баги (на глаз не отличить, но благодаря вашему посту я заметил разницу). Переделаю обратно на улучшенный 8SED.
На очереди попробовать алгоритм с антиалиасингом.
Это на самом деле я и есть автор этого бреда. С математической точки зрения это выглядит как неоптимизированный код, но на самом деле эта функция написана специально под компилятор (ветвления выкидываются путём подстановки констант) — то есть в финальном скомпилированном варианте не будет практически ни единого ветвления. И доп. переменную с квадратом расстояния тоже делал я:) Поскольку мне надо было добиться скорости алгоритма менее 1 секунды для изображения 4к, получился вот такой монстр. Сделать лучше при той же производительности не получилось (этот код быстрее где-то на 15%).
Но комментарий не мешало бы оставить, так как с бородатых лет я уже сам не помню, что я тут натворил. Причем я потом нашёл такую же оптимизацию в китайской статье, которую приводил в ссылках, но там сам алгоритм неточный.
P.S. То что сейчас в гите — сильно устарело.
Так что это либо повод задуматься, либо я где-то ошибся… Но рискну предположить, что ваш метод на GPU ещё как-то учитывает антиалиасинг и сглаживает переходы в ущерб точности, но в пользу красоты результата.
Далее по производительности (Core 2 quad):
брутфорс — 462 сек
8SSEDT — 0.046 сек (46 мс)
Как видно, практически также быстро как GPU. У меня правда он ещё два прохода считает (знаковая карта расстояний), эти два прохода можно запустить на двух процессорах без особых проблем. SIMD там прикрутить тоже можно, но лениво.
Вот оригинальная реализация: www.codersnotes.com/algorithms/signed-distance-fields (ступеньки прилагаются).
Потом я похоже что-то нахимичил когда переделывал, но у меня ощущение, что в оригинале тоже есть ошибки.
Принцип такой же (окно 3х3), но возможно алгоритм модифицированный. Ещё на картинки видны какие-то артефакты на удалении, но это похоже на ошибку в реализации.
Но проще сказать чем сделать — кто из студентов смотрит на предупреждения компилятора, сдавая зачёт в последний день? И кто сказал, что такие студенты начнут пользоваться анализаторами, стыдливо показывая пустую зачётку?:)
Из заголовка статьи я так понял, что смысл всего этого — ленивое освобождение памяти, с чем пул справляется превосходно, более того, объектная система GTK вообще позволяет практически не освобождать память за счёт выстраивания иерархии указателей. Когда мы говорим о защите памяти, то как правило я подразумеваю что-то вроде ASLR, NX-bit, PaX, но никак не Гутманна.
Скорее всего, другие читатели вас тоже не поймут, так как статья начинается со слов «чтобы не пичкать код вызовами free», а далее начинается отдельная история про защиту памяти и надёжность.
Лично я выбрал для себя Linux-like стиль программирования с активным использованием goto (да-да).
Я бы такой авиакомпанией никогда не полетел несмотря на все меры безопасности:)
* пишем тесты с выводом в stdout, вроде такого:
* запускаем наше хозяйство с выводом в простой текстовый файл, и сохраняем его куда-нибудь в укромное место как «эталон»
* повторный запуск — сравниваем результат с эталонным файлом чем-то вроде diff
* обновляем тесты — обновляем эталон
А когда не лень делают так: github.com/danmar/cppcheck/blob/master/test/testtokenize.cpp
А __LINE__?
Если вас и компилятор не убедит, то мне и подавно никто не поверит.
RtlSecureZeroMemory.В каком таком стандарте описан тип BYTE?
Как бальзам на душу разработчикам кроссплатформенной библиотеки.
Не проще ли так?
Из последних на моей памяти реально присвоенных CVE, что нашли анализаторы — уязвимость в Х.org, которую нашёл cppcheck. Это капля в море в пересчёте на адское количество ложных срабатываний.
В итоге так и живём — вся суть отечественного аудита кода заключается в гуглении CVE-шек из OpenSource проектов.
В некоторых случаях это даже лучше. В Linux наоборот идут в сторону контейнеров для софта.