Разработка findcolor, findimage, Pure lua Опции

[cirus]

 ImageTest.zip ( 439 байт ) Кол-во скачиваний: 73

Код

findimage_benchmark_Release_x64 --s Big.bmp --i Small.bmp --d 0 --a 50 --sr > benchmark_test.txt

Найдено 0. При 50% должно находится 6 изображений.

[DarkMaster]

Выполнил хорошее раздробление структуры кода

Как раз на днях читал особенности оптимизации циклов с точки зрения прогнозирования ветвлений. Если в двух словах - чем меньше функция, тем лучше, увеличение количества вложенных циклов не есть хорошо, прерывания и ифы имеют большие шансы сброса прогнозирования ветвлений. Результат выкидывание инфы из L1 кэша и большие задержки при работе через оперативку. Это по сути объясняет те проблемы которые были в чистом луа. Так же львиная доля проблем в луа была из-за cast'ов.
Лично для меня по большому счету библиотека должна выполнять только одну функцию, если говорить об интеграции дллок: это получив три массива(искомое с мин deviation, искомое с макс deviation, изображение в котором идет поиск) адрес/ширина/высота/длина, зону поиска, %точности и количество искомых изображений, собственно искать эти изображения. Вся остальная логика имхо должна быть исключительно снаружи, т.к. нагрузка там уже формальная, а вот логики и вариантов там уже море.

[Cockney]

У меня нет проблемы ветвлений. И вложенности экстремальной у меня нет. Больший прирост даст только переход на 32 бит изображение и использование всяких sse расширений процессора.

 ImageTest.zip ( 439 байт ) Кол-во скачиваний: 73

Код

findimage_benchmark_Release_x64 --s Big.bmp --i Small.bmp --d 0 --a 50 --sr > benchmark_test.txt

Найдено 0. При 50% должно находится 6 изображений.

Классно, давно держал в голове мысль о том, что если картинка экрана довольно малая, то смысла нет использовать потоки. Видимо тут сыграло точно это. Проверю.

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

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

[DarkMaster]

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

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

Больший прирост даст только переход на 32 бит изображение

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

смысла нет использовать потоки

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

Ну и немаловажный момент скорости в один поток. Я понимаю, что можно взять threadripper и сказать "смотрите, как круто! у нас теперь быстрее в 2 раза", а то, что оно на 64 ядрах вместо одного пахало - это не важно =) По сути имхо нужна скорость в один поток, а потом уже масштабировать.

ко всему вышесказанному прошу относиться, как к попытке конструктивной критики в поисках правильных решений =)

Сообщение отредактировал DarkMaster - 22.4.2022, 13:25

[Cockney]

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

Сейчас вообще приходится обходить выравнивание, что относительно не дешево и ничего. В случае 32 бит будет читаться 4 байта + 4*n в кеш пойдет, если мы про х32 архитектуру. И строка за строкой.... Вообще не стал бы я заострять так внимание на кеш процессора, основной и главный тезис - доступ должен идти последовательно по памяти, а не скакать вперед-назад, как это обычно в циклах и бывает.

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

это приводит к идеи о пуле потоков, которую я уже протестировал довольно давно. накладных расходов там куда больше чем профита. в условиях ограничений на i/o это норм подход, а в задачах на cpu они вообще никак не помогут. Даже на моем дохлом ноуте создание 4х потоков н стоит ничего, буквально меньше 1ms.

Ну и немаловажный момент скорости в один поток. Я понимаю, что можно взять threadripper и сказать "смотрите, как круто! у нас теперь быстрее в 2 раза", а то, что оно на 64 ядрах вместо одного пахало - это не важно =) По сути имхо нужна скорость в один поток, а потом уже масштабировать.

ну скажем запускал я свой алгоритм когда то в один поток. 11 секунд) Это релевантное значение ? По моему его даже смысла нет рассматривать как оно есть.

Смысл использовать потоки имхо есть всегда

даже когда на вход поступает область экрана НА которой ищем 10х10 пикселей ?)

[DarkMaster]

ну скажем запускал я свой алгоритм когда то в один поток. 11 секунд) Это релевантное значение ? По моему его даже смысла нет рассматривать как оно есть.

В зависимости от того, что это было. Можно искать картинку 500*500 с точностью 5% на рандомно сгенерированных изображениях 8к(да хотя бы full hd). Там и 15 норм будет. Тут имхо оценивать скорость работы нужно именно в ключе количества пикселей проверяемых в секунду на один поток, а как эталон брать стандартный имидж

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

А в чем там расходы? Ну висят потоки, не отсвечивают, врубаешь по мере надобности.

даже когда на вход поступает область экрана НА которой ищем 10х10 пикселей ?)

Не вижу оснований этого не делать. Код должен быть унифицированным и вести себя логично, а в случаях высокой нагруженности получать падение производительности при переходе с области 11х11 на 10х10 очень странно. К тому же область не всегда определяющая. В этой области вполне может проиходить поиск нескольких сотен изображений с deviation и низким процентом точности (из реальной задачи по работе с инвентарем, навигация по минимапу, мелкие тонкие шрифты с неотключемым сглаживанием). В итоге ты получаешь ОЧЕНЬ нагруженный код в микрообласти. Лично в моей практике по иронии были самые тяжелые в плане выполнения по производительности были именно поиски в маленьких областях большого количества изображений.

[Cockney]

В зависимости от того, что это было. Можно искать картинку 500*500 с точностью 5% на рандомно сгенерированных изображениях 8к(да хотя бы full hd). Там и 15 норм будет. Тут имхо оценивать скорость работы нужно именно в ключе количества пикселей проверяемых в секунду на один поток, а как эталон брать стандартный имидж

область 1980на1000 с чем то. картинка +- 20на20. эталонность пилотовского файнда тоже под вопросом как по мне.

А в чем там расходы? Ну висят потоки, не отсвечивают, врубаешь по мере надобности.

Поток одноразовая вещь, чтобы его "врубить по надобности" нужно поддерживать синхронизированную очередь тасок, а это минимум 1 мьютекс и одна очередь с распределением памяти.

Не вижу оснований этого не делать. Код должен быть унифицированным и вести себя логично, а в случаях высокой нагруженности получать падение производительности при переходе с области 11х11 на 10х10 очень странно. К тому же область не всегда определяющая. В этой области вполне может проиходить поиск нескольких сотен изображений с deviation и низким процентом точности (из реальной задачи по работе с инвентарем, навигация по минимапу, мелкие тонкие шрифты с неотключемым сглаживанием). В итоге ты получаешь ОЧЕНЬ нагруженный код в микрообласти. Лично в моей практике по иронии были самые тяжелые в плане выполнения по производительности были именно поиски в маленьких областях большого количества изображений.

а я и не писал про падения. область 10на10 при поиске ОДНОЙ картинки 3на3 проскочит мгновенно. парралелить имеет смысл по целым изображениям, а не по областям поиска в одном изображении в таком случае

кстати как предлагаешь считать кол-во пикселей, проверяемых в секунду одним потоком ?
ну понятно, счетчик, но он же "грязный"

[DarkMaster]

эталонность пилотовского файнда тоже под вопросом как по мне

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

Поток одноразовая вещь, чтобы его "врубить по надобности" нужно поддерживать синхронизированную очередь тасок, а это минимум 1 мьютекс и одна очередь с распределением памяти.

Ну про мьютекс понятно, а память под что распределять? Туда поидее только указатели должны улетать в потоки.

область 10на10 при поиске ОДНОЙ картинки 3на3 проскочит мгновенно.

3 на 3 там не будет. Нужно рассчитывать на какие-нибудь 8*6 и изображений пару сотен с точностью 80% и получается уже печальнее, причем в стандартных решениях ну очень печально и приходится что-то изобретать.

парралелить имеет смысл по целым изображениям

по логике вещей - да, на практике есть сомнения в существенной разнице в производительности и не забываем про то, что это распараллеливание еще нужно будет организовать при том, что зачем-то выключается многопоточность. А выключается она для того чтобы что? Чтобы не держать пул? Ну будет там пул и что? Что он жрет то? При многопоточке ты все равно получишь либо мьютекс либо просто вернешь данные по указателю и все будет ок (если это флаг окончания работы, то тебе не нужен в обязательном порядке именно мьютекс, т.к. у тебя нечего синхронизировать и ты не можешь считать одно поле в состоянии до записи, а второе поле после записи, запись флага окончания работы потока осуществляется так же в один поток, соответственно конфликтов записи и вылета не будет).
В моем понимании:
На этапе инициализации:
1) Есть общий буфер(изображение в котором происходит поиск).
2) Есть два буфера состояния паттерна в максимальном и минимальном deviation.
3) В пул прилетают именно указатели на эти буферы и параметры поиска(область, точность).
4) Основной поток встает в чтение флагов успеха (мьютексы дело не самое дешевое, а они тут по сути не нужны).
5) Потоки обрабатывают изображения, записывают результат(тоже бы в основном потоке паммять выделил).
6) Встают в suspend.
7) Основной поток дожидается получения всех флагов.
8) Основной поток собирает все результаты в кучу, возвращает результат.

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

кстати как предлагаешь считать кол-во пикселей, проверяемых в секунду одним потоком ?

Всмысле? Ну сделать некоторое изображение, скажем полностью однотонное, искать в нем такое же однотонное изображение с точностью 100%. Смотреть результат. По сути ты можешь изображение само в себе искать с точностью 100%, но тут может получиться какая-нибудь иллюзия неожиданная. Я бы рекомендовал все-таки искать серое на сером с разной точностью и смотреть, как меняется результат - он должен быть совсем линейным, обратно пропорциональным точности. Повторить N раз для получения достоверных результатов.

Сообщение отредактировал DarkMaster - 22.4.2022, 22:05

[Cockney]

По поводу пула потоков: мне лень расписывать свои мытырства с ним, скажу лишь то, что на задачах поиска картинок он работает плохо. У меня результат был в ~120 медленней с ним именно за счет обслуживания пула. он вообще не бесплатен. то что предлагаешь ты мне не понятно, скажу честно. быстрее одноразовых потоков у меня н выходило. Вообще вот ссылка https://github.com/bshoshany/thread-pool#su...ue-with-futures если интересно. Это вот классический пул, который я тестил и как он работает можешь по коду глянуть, там строк 500 вряд ли будет.

По поводу счета пикселей в секунду: ну и что это дает ? Во первых у нас разные механизмы с кнайтом, я, как и он, не перебираем все подряд. а как то выбираем зоны для поиска. условно у него будет 10 точек для поиска, у меня 20, но обойти я их смогу быстрее. при этом у него выигрыш за счет меньшего числа сравнений. ну я утрирую. В общем, мне этот момент тоже не ясен. как по мне самое объективное: вот картинки, 1000 запусков и средняя скорость на весь поиск. Это и сравниваем. все остальное это что-то странное

Касательно передачи в поток параметров поиска - я бы вообще не заморачивался и пока поток в suspend просто перезаписал бы ему переменные с адресом, областью, точностью.

а кто тебе скажет что поток саспенд ? апи системы ? удивительно, но там тоже будет мьютекс) а если и узнал, начал писать и поток ожил ? Все пути ведут к синхронизации.

[DarkMaster]

а кто тебе скажет что поток саспенд

А зачем мне это вообще говорить? Встал и встал. При следующем поиске просто разбужу. Если вопрос в том, что я могу его в теории разбудить раньше, чем он уснет(хотя для меня это очень спорная казуистика и на практике очень тяжело себе представляю на столь сильный асинхрон), то ничего не мешает этот suspend выставить из основного потока и жить спокойно.

По поводу счета пикселей в секунду: ну и что это дает ?

Понимание реальной производительности, а не когда сложились звезды под оптимизацию. Т.е. это покажет правильно ли оптимизирован перебор.
Утрированно: зачем мне быстрый финдимидж, я просто буду вызывать его раз в минуту и все будет ок для моей задачи. Ну для части задач да, но в итоге ногу подвернет.

Во первых у нас разные механизмы с кнайтом, я, как и он, не перебираем все подряд

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

[Cockney]

А что точность ? Есть набор точек который дает самую лучшую комбинацию скорости поиска/точности. Смысла лопатить все нет, как по мне. На реальных задачах это работает (как минимум пример sutra из моего архива). На супер синтетических как вот скинул cirus - нет (я немного доработал, теперь работает, но не так как пилот, и обсужу скорее всего отдельно).

Понимание реальной производительности, а не когда сложились звезды под оптимизацию. Т.е. это покажет правильно ли оптимизирован перебор.
Утрированно: зачем мне быстрый финдимидж, я просто буду вызывать его раз в минуту и все будет ок для моей задачи. Ну для части задач да, но в итоге ногу подвернет.

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

А зачем мне это вообще говорить? Встал и встал. При следующем поиске просто разбужу. Если вопрос в том, что я могу его в теории разбудить раньше, чем он уснет(хотя для меня это очень спорная казуистика и на практике очень тяжело себе представляю на столь сильный асинхрон), то ничего не мешает этот suspend выставить из основного потока и жить спокойно.

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

[Cockney]

 ImageTest.zip ( 439 байт ) Кол-во скачиваний: 73

Код

findimage_benchmark_Release_x64 --s Big.bmp --i Small.bmp --d 0 --a 50 --sr > benchmark_test.txt

Найдено 0. При 50% должно находится 6 изображений.

На текущий момент удалось добиться нахождения 2х картинок, они по центру Big.bmp. Одно найдено 100%, другое 66%. Остальные плавают в пределах 10-44%. И вопрос касательно того а как ищет пилот. Мои рассуждения: Small.bmp - 10 пикселей, из них 1 фон, итого 9 пикселов. 1 пиксел имеет вес = 1/9 = 11%. Просто берем искомое и прикладываем к участкам где должны найти. Сравниваем по пикселям и считаем. Центральные точно найдутся, а вот почему находятся другие да еще и с точностью 50% ?

[DarkMaster]

Идеи

Код

do    
    -- передается массив всех псевдомьютексов
    -- и отдельно номер элемента чтобы передача
    -- была по ссылке (фишки луа)
    -- фактически нормально просто передать указатель на bool.
    local main = function(pseudo_mutex, pseudo_mutex_i,
                          image_pointer,
                          pattern_min_pointer,
                          pattern_max_pointer,
                          fi_opt_pointer,
                          result_pointer) 
                          
        local fi_thread = function()
            for ...
                for ...
                        if  image_pointer[i] > pattern_min_pointer[j]
                        and image_pointer[i] < pattern_max_pointer[j]
                        then
                            result_pointer[#result_pointer] = {x, y}
                        end
                end
            end
            complete_flag = true
        end
    
    
        -- встаем после инициализации в suspend
        this:suspend()
        repeat
            fi_thread(...)
            -- ждем пока основной поток поставит
            -- текущий поток в suspend
            while pseudo_mutex[pseudo_mutex_i] do
                wait(0)
            end
        until false
    end
    main()
end


local thread_pool = {}
local thread_fi_opt = {}
local result_pool = {}
local pseudo_mutex = {}
for i = 1, 8 do
    thread_pool[#thread_pool+1] = create_thread(if_thread)
    result_pool[#thread_pool+1] = {data={}, complete_flag = false}
    thread_fi_opt[i] = {x1=0, y1=0, x2=0, y2=0, acc=0, count=0}
end


local check_complete = functon(result_pool)
    for i = 1, #result_pool do
        if not result_pool[i].complete_flag then
            return false
        end
    end
    return true
end


fi_main = function(...)
    -- закидываем настройки в поток
    for i = 1, #thread_pool do
        thread_fi_opt[i] = {x1=0, y1=0, x2=0, y2=0, acc=0, count=0})
    end
    
    -- размораживаем потоки
    for i = 1, #thread_pool do
        thread_fi_opt[i]:resume
    end
    
    repeat
    until check_complete()
    
    -- замораживаем потоки до следующего финда
    for i = 1, #thread_pool do
        thread_pool[i]:suspend()
    end

    -- собираем в кучу результат, возварщаем
end

Я подчеркиваю, что это только идеи, а не какая-то проработка и реально работающий код. Общий смысл в том, что потоки вообще ничего не выделяют по памяти и работают напрямую с указателями переданными из основного потока. В т.ч. результат улетает в уже размеченную область. При подобной реализации натуральных мьютексов и переключений потоков нет. Функции поиска в потоке находятся в вечном цикле, между поисками основной поток втихаря подсовывает новые указатели/настройки.
В моем понимании при подобной реализации накладных расходов на пул быть не должно. Из дополнительных паразитных расходов я вижу:
1) suspend/resume - беспонятия сколько это жрет, но вряд ли очень много.
2) сбор результата в кучу, но это будет при любой многопоточке.

[Cockney]

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

И рассмотрим такую ситуацию: один пул потоков, библиотека. из луа потока №1 дергаем поиск и из луа потока №2 дергаем поиск. Что будет с пулом ? Как то сложно все таки это представить без стандартных примитивов

[DarkMaster]

И вопрос касательно того а как ищет пилот. Мои рассуждения: Small.bmp - 10 пикселей, из них 1 фон, итого 9 пикселов. 1 пиксел имеет вес = 1/9 = 11%. Просто берем искомое и прикладываем к участкам где должны найти. Сравниваем по пикселям и считаем. Центральные точно найдутся, а вот почему находятся другие да еще и с точностью 50% ?

Можно подробнее описать?
Вопрос кратности %? Там точно были косяки с количеством пикселей фона которые в % засчитывались, как совпавшие. Т.е. было по сути дела каждый пиксель 10%, просто фоновые считались совпавшими вне зависимости от цвета. Данный момент несколько раз перерабатывался.

Про бока не очень понял.

[Cockney]

У меня вопрос почему он находит 5 картинок, да еще с 50% точностью минимум, хотя адекватными картинкаи будут только те что в центре. Все остальные максимум 10-40% наберут, это основной вопрос.

я бы нарисовал, но картинка слишком маленькая

[DarkMaster]

Тут как я вижу работает только если железно знаем сколько найдем.

Ограничивать искуственно. Т.е. -1 у нас условно считается, скажем 1 млн. Памяти это особо не сожрет, результат будет в практическом использовании избыточным. Если совсем упарываться, то можно делать какие-то resize для увеличения буфера, но зачем? Ну даже если мы веделим 1МБ под результаты, то дальше то что? Ну не забьем мы его результатами, а лишний потерянный мегабайт памяти... ну не пофиг?

из луа потока №1 дергаем поиск и из луа потока №2 дергаем поиск. Что будет с пулом ?

Вообще сразу встает вопрос о том, откуда в двух потоках оказался один и тот же пул. Да и полноценные потоки в луа откуда взялись тоже вопрос. Т.е. мы что-то подключили из либ, либо извратились со стандартными псевдопотоками, передали туда сами же пул, чтобы он был именно одним и тем же, а потом решать проблемы синхронизации. Нафига?)
По умолчанию каждый поток в Lua имеет свой require, свои подключенные модули и как следствие свои пулы имиджа. В рамках луа очень часто указывается на то, что крайне не рекомендуется создавать потоки и уничтожать их без реальной надобности, т.к. это прям тормоз, что тормоз и рекомендуется использовать именно пулы.

[Cockney]

Нафига?)

Кол-во ядер == кол-во потоков. больше нельзя в рамках ПРОЦЕССА. Неэффективно будет иначе (на каждый поток луа свой пул потоков поиска).

[DarkMaster]

У меня вопрос почему он находит 5 картинок, да еще с 50% точностью минимум, хотя адекватными картинкаи будут только те что в центре. Все остальные максимум 10-40% наберут, это основной вопрос.

я бы нарисовал, но картинка слишком маленькая

Без картинок сложно ответить. Вообще в более ранних версиях был баг: пиксели перебирались только в указанной области, но сам паттерн мог быть смещен за ее пределы. Т.е. если у нас есть некоторый зеленый квадрат 10*10 на белом фоне и мы бы искали его исключительно в его реальных координатах, скажем, x100 y100 x109, y109, то по факту поиск был бы в области x91, y91, x118, y118, но вот пиксли бы проверялись только в рамках x100 y100 x109, y109. Если нифига не понятно, то нарисую.

[Cockney]

Без картинок сложно ответить. Вообще в более ранних версиях был баг: пиксели перебирались только в указанной области, но сам паттерн мог быть смещен за ее пределы. Т.е. если у нас есть некоторый зеленый квадрат 10*10 на белом фоне и мы бы искали его исключительно в его реальных координатах, скажем, x100 y100 x109, y109, то по факту поиск был бы в области x91, y91, x118, y118, но вот пиксли бы проверялись только в рамках x100 y100 x109, y109. Если нифига не понятно, то нарисую.

посмотри внимательней, в закрепе есть они