Задача о 19 ферзях.

Тема в разделе "WASM.A&O", создана пользователем Intro, 18 мар 2010.

  1. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    591
    Из-за падения форума всё по удалялось, ну да ладно.
    Вот ещё одна ревизия, код переделан на манер С (используется только библиотека Windows и внутренний System), используется инструкция POPCNT, так что на старых процессорах не заработает. Код не слишком оптимизирован, в точности функция popcnt не инлайн, странно, ключевое слово inline есть, но в Делфи 6 не работает. Хотя конечно надо бы переделать на C/C++, но это потом.
     

    Вложения:

  2. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    591
    В общем, переписал сначала на UASM, потом на С++, за одно создал учётку на M$... короче вот.
    https://nanobot-amk-yandex.visualstudio.com/problem19queen/_git/problem19queen
    Не знаю, быдлокод или нормально, но лучше чем паскале. Что интересно, на асме чуть быстрей всё равно, но компилятор VS C++2017 не плох, создал почти такой же эффективный код, только один такт за итерацию проиграл. Не захотел использовать lea [b0+b1-CountBitBlock * 2].
    Так что, это доказывает хорошую эффективность компиляторов, конечно, при условии, что код изначально оптимальный, но при этом, можно хоть чуть чуть, да и ускорить код, если переписать на ассемблере.
    ЗЫ
    Проект можно использовать для теста как и компиляторов, так и самих процессоров.
    ЗЫЫ
    Да, ещё можно добавить многопроцессорность, но это потом, может быть.
     
  3. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    591
    Тест версии 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 тактов.
     
  4. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    скорей всего компиль довески вставил (типа рантаймы, защита стека..)
     
  5. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    591
    На самом деле сам компилятор создал не оптимальный код для AMD Athlon ll, возможно такой код будет работать быстро на современных Intolах, но на моём процессоре код работает меннее быстро. Хотя компилятор VSC++ работает довольно хорошо, особенно с быдло-кодом. VS C++ 2010 с быдло-кодом работает хуже, но для этой программы создал код более оптимальный.
    ЗЫ
    Кстати, код С++ сгенерировал Hex-Ray, плагин для IDA Pro, из кода на UASM. Я его почти не изменял.
    --- Сообщение объединено, 25 ноя 2018 ---
    ЗЫ
    И самое главное, в англонете такая задача фигурирует под названием "Peaceably Coexisting Armies of Queens". Они смогли ее решить, вроде, но у меня всё равно быстрей алгоритм получился.
     
    Последнее редактирование: 25 ноя 2018
  6. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    Intro, я наибольшее ускорение получал с помощью полиморфных схем + использовал векторные регистры для кэширования переменных + подгонял последовательность команд под out-of-order execution == таким дикобразом из камня можно максимум выжимать, но асм-портянка получается сплошной страх и ужасть :)
     
  7. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    591
    И так у меня новая машина с процессором 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 тактов за итерацию. Быстро однако, там же зависимости, и всё равно быстро. Сложно работают современные камни.
     
  8. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    591
    Что ещё интересно. Запустил ограниченный тест. Размер поля: 16x16, количество ферзей, чёрных: 35, белых: 35
    При этом прога останавливается после первого варианта.
    Код (Text):
    1. Найдено вариантов: 1
    2. Время: 5.742608 сек
    3. Количество итераций: 4999000704
    4. Скорость: 870510452 итераций/сек, 4.357 тактов за итерацию
    5. Текущая частота процессора: 3793.082 МГц
    А вот атлон.
    Код (Text):
    1. Найдено вариантов: 1
    2. Время: 15.747337 сек
    3. Количество итераций: 4999000704
    4. Скорость: 317450539 итераций/сек, 9.493 тактов за итерацию
    5. Текущая частота процессора: 3013.710 МГц
    На 5 тактов быстрей, и как видно конвейеры райзена 5 я так и не смог перегрузить.
    Так же есть проблемы с прогой на С++, там всё медленно, не понятно почему. Может что-то с ключами оптимизации сделал не то, VS пока не установил.
     
  9. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    591
    Запустил тест на 10ки, результат аналогичен 7ки, даже чуть быстрей. Но во время работы теста диспетчер показывает турбобуст 4.3 ГГц, но вот тест показывает 3793 МГц. Получается буста на самом деле нет, или что-то у меня не так работает, может rdtsc не правильно работает.
     
  10. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    591
    Версия х64 1.13. Вроде ещё не выкладывал.
    ЗЫ
    Батник.
     

    Вложения: