Из-за падения форума всё по удалялось, ну да ладно. Вот ещё одна ревизия, код переделан на манер С (используется только библиотека Windows и внутренний System), используется инструкция POPCNT, так что на старых процессорах не заработает. Код не слишком оптимизирован, в точности функция popcnt не инлайн, странно, ключевое слово inline есть, но в Делфи 6 не работает. Хотя конечно надо бы переделать на C/C++, но это потом.
В общем, переписал сначала на UASM, потом на С++, за одно создал учётку на M$... короче вот. https://nanobot-amk-yandex.visualstudio.com/problem19queen/_git/problem19queen Не знаю, быдлокод или нормально, но лучше чем паскале. Что интересно, на асме чуть быстрей всё равно, но компилятор VS C++2017 не плох, создал почти такой же эффективный код, только один такт за итерацию проиграл. Не захотел использовать lea [b0+b1-CountBitBlock * 2]. Так что, это доказывает хорошую эффективность компиляторов, конечно, при условии, что код изначально оптимальный, но при этом, можно хоть чуть чуть, да и ускорить код, если переписать на ассемблере. ЗЫ Проект можно использовать для теста как и компиляторов, так и самих процессоров. ЗЫЫ Да, ещё можно добавить многопроцессорность, но это потом, может быть.
Тест версии 2010. https://yadi.sk/d/5UrOtbiMTO_oNQ Asm x86 UASM https://yadi.sk/d/EkE_f_RYP6lm8Q Посмотрим как там ноутбуке Lenova. Хотя там процессор какой-то медленный. --- Сообщение объединено, 16 ноя 2018 --- Asm x86 UASM https://yadi.sk/d/35YQVnU7bt1RcQ Выше я ошибся, там для х64 --- Сообщение объединено, 17 ноя 2018 --- 12.2 тактов celeron B820 и атлон 11 Х640 11.5 тактов.
На самом деле сам компилятор создал не оптимальный код для AMD Athlon ll, возможно такой код будет работать быстро на современных Intolах, но на моём процессоре код работает меннее быстро. Хотя компилятор VSC++ работает довольно хорошо, особенно с быдло-кодом. VS C++ 2010 с быдло-кодом работает хуже, но для этой программы создал код более оптимальный. ЗЫ Кстати, код С++ сгенерировал Hex-Ray, плагин для IDA Pro, из кода на UASM. Я его почти не изменял. --- Сообщение объединено, 25 ноя 2018 --- ЗЫ И самое главное, в англонете такая задача фигурирует под названием "Peaceably Coexisting Armies of Queens". Они смогли ее решить, вроде, но у меня всё равно быстрей алгоритм получился.
Intro, я наибольшее ускорение получал с помощью полиморфных схем + использовал векторные регистры для кэширования переменных + подгонял последовательность команд под out-of-order execution == таким дикобразом из камня можно максимум выжимать, но асм-портянка получается сплошной страх и ужасть
И так у меня новая машина с процессором AMD Ryzen 5 3600X. Частота номинальная 3.8 ГГц. Вот результат. Найдено вариантов: 17 Время: 7.009564 сек, 25964131351 тактов Количество итераций: 5791229853 Скорость: 826189792 итераций/сек, 4.483 тактов за итерацию Текущая частота процессора: 3704.101 МГц Четыре с половиной тактов за итерацию. Круто! В прочим это не точно, т.к. частота может прыгать до 4.4 ГГц, тогда скорость по тактам более скромная. Да, надо бы мультипоточное решение сделать, тогда скорость увеличится раз в 8. --- Сообщение объединено, 6 июл 2021 --- Хотя скорость тактов/итер = TicksPerIt = double(Tm2)/double(CountIter); где Tm2 кол. тактов. Получается 4.5 т/ит довольно точное значение, если счётчик тактов работает точно. Всё равно что-то быстро. Тест проводился на Windows 7 SP1. --- Сообщение объединено, 6 июл 2021 --- А понял. Это версия с сильно мудрёной оптимизацией, результат отличается, и возможно алгоритм сломался. Так бывает если используешь слишком агрессивные оптимизации. ЗЫ Проверил старую версию. Всё равно 4.564 тактов за итерацию. Быстро однако, там же зависимости, и всё равно быстро. Сложно работают современные камни.
Что ещё интересно. Запустил ограниченный тест. Размер поля: 16x16, количество ферзей, чёрных: 35, белых: 35 При этом прога останавливается после первого варианта. Код (Text): Найдено вариантов: 1 Время: 5.742608 сек Количество итераций: 4999000704 Скорость: 870510452 итераций/сек, 4.357 тактов за итерацию Текущая частота процессора: 3793.082 МГц А вот атлон. Код (Text): Найдено вариантов: 1 Время: 15.747337 сек Количество итераций: 4999000704 Скорость: 317450539 итераций/сек, 9.493 тактов за итерацию Текущая частота процессора: 3013.710 МГц На 5 тактов быстрей, и как видно конвейеры райзена 5 я так и не смог перегрузить. Так же есть проблемы с прогой на С++, там всё медленно, не понятно почему. Может что-то с ключами оптимизации сделал не то, VS пока не установил.
Запустил тест на 10ки, результат аналогичен 7ки, даже чуть быстрей. Но во время работы теста диспетчер показывает турбобуст 4.3 ГГц, но вот тест показывает 3793 МГц. Получается буста на самом деле нет, или что-то у меня не так работает, может rdtsc не правильно работает.
