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

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

  1. Intro

    Intro Active Member

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

    Вложения:

  2. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    601
    В общем, переписал сначала на 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
    Сообщения:
    601
    Тест версии 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.243
    скорей всего компиль довески вставил (типа рантаймы, защита стека..)
     
  5. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    601
    На самом деле сам компилятор создал не оптимальный код для 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.243
    Intro, я наибольшее ускорение получал с помощью полиморфных схем + использовал векторные регистры для кэширования переменных + подгонял последовательность команд под out-of-order execution == таким дикобразом из камня можно максимум выжимать, но асм-портянка получается сплошной страх и ужасть :)
     
  7. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    601
    И так у меня новая машина с процессором 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
    Сообщения:
    601
    Что ещё интересно. Запустил ограниченный тест. Размер поля: 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
    Сообщения:
    601
    Запустил тест на 10ки, результат аналогичен 7ки, даже чуть быстрей. Но во время работы теста диспетчер показывает турбобуст 4.3 ГГц, но вот тест показывает 3793 МГц. Получается буста на самом деле нет, или что-то у меня не так работает, может rdtsc не правильно работает.
     
  10. Intro

    Intro Active Member

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

    Вложения:

  11. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    601
    Нечто непонятное.
    https://www.gams.com/latest/gamslib_ml/libhtml/gamslib_coex.html
    По описанию это некий листинг кода, который решает ЭТУ задачу. Только я ничего не понимаю, что ты такое.
    ЗЫ
    Оууу! Задачка есть на розетке!
    https://rosettacode.org/wiki/Peaceful_chess_queen_armies
    Правда это вариант задачи, найти одинаковое кол. ферзей. А у меня точней задача из ж. НиЖ. Надо найти максимальное кол. ферзей, короче сколько влезет на поле.
     
    Последнее редактирование: 4 ноя 2024
  12. alex_dz

    alex_dz Active Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    455
    Intro
    include macroses.asm
    include utils.asm

    где взять?
    и что за ассемблер у вас испльзуется для сборки x64

    2) GAMS = General Algebraic Modeling System
    своя екосистема
     
  13. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    601
    alex_dz, я там глянул, там под старый формат библиотек, так что решил переделать код, так что позже. А асм используется UASM.