ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ассемблер - регистры MMX - команды условного перехода.
225 сообщений из 225, показаны все 9 страниц
  все  
Ассемблер - регистры MMX - команды условного перехода.
    #39654105
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
С целью ускорения целочисленной 64-битной арифметики решил попробовать использовать ассемблерную вставку с использованием регистров MMX (которые 64-битные и как нельзя лучше подошли бы для моей задачи).

Не знаю, как сделать цикл со счётчиком или условный переход по равенству/неравенству содержимого одного из MMX-регистров 0.
Некоторая сложность в том, что счётчик (кол-во повторений цикла) у меня тоже 64-битный.

Возможно ли это сделать?
Инструкции JZ, JNZ я так понимаю, для MMX-регистров не при делах?
...
Рейтинг: 0 / 0
01.06.2018, 16:20
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654174
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Старшие разряды счётчика будут константами много миллионов лет. И зачем оно тогда?
...
Рейтинг: 0 / 0
01.06.2018, 18:30
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654201
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Какие разряды Вы считаете старшими?
Мне будут нужны количества повторений цикла, лежащие в диапазоне 33-41 бит.
Всё это работает на "чистом" C++ в пределах 1 суток, но хотелось бы быстрее, вот за этим оно и нужно. :)
...
Рейтинг: 0 / 0
01.06.2018, 19:45
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654208
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
MMX это каменный век, 90-е, сейчас есть AVX-*, наверно надо в эту сторону копать. Как в асме их использовать не знаю, но все компиляторы С/С++ имеют соответствующий ключик для разрешения использования этого набора команд проца.
...
Рейтинг: 0 / 0
01.06.2018, 20:03
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654225
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Dima TMMX это каменный век, 90-е, сейчас есть AVX-*, наверно надо в эту сторону копать. Как в асме их использовать не знаю, но все компиляторы С/С++ имеют соответствующий ключик для разрешения использования этого набора команд проца.

Возможно, возможно.
Но мне ещё важна совместимость с разными компами, некоторые из них довольно старые, хотя SSE 4 есть уже на всех проверенных.
Мне не критично использование именно MMX, а нужна быстрая 64-битная арифметика (сложение-вычитание, сдвиги, and-or-xor).
...
Рейтинг: 0 / 0
01.06.2018, 21:46
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654226
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Не нужен asm

Достаточно воспользоваться intrinsics инструкциями.
https://software.intel.com/sites/landingpage/IntrinsicsGuide/
...
Рейтинг: 0 / 0
01.06.2018, 21:47
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654229
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Я правильно понял, что Вы предлагаете не выписывать явно работу с требуемыми регистрами, а довериться компилятору C ?
...
Рейтинг: 0 / 0
01.06.2018, 21:53
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654287
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®Какие разряды Вы считаете старшими?
Мне будут нужны количества повторений цикла, лежащие в диапазоне 33-41 бит.
Всё это работает на "чистом" C++ в пределах 1 суток, но хотелось бы быстрее, вот за этим оно и нужно. :)
Сделай цикл в цикле.
...
Рейтинг: 0 / 0
02.06.2018, 08:25
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654289
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Вряд ли цикл в цикле будет способствовать достижению главной цели (сделать быстрее, чем на C++ с оптимизациями).
...
Рейтинг: 0 / 0
02.06.2018, 08:41
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654291
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®Вряд ли цикл в цикле будет способствовать достижению главной цели (сделать быстрее, чем на C++ с оптимизациями).
Попробуй.
...
Рейтинг: 0 / 0
02.06.2018, 08:51
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654298
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®Вряд ли цикл в цикле будет способствовать достижению главной цели (сделать быстрее, чем на C++ с оптимизациями).
если индекс не нужен, то скорее всего быстрее будет раза 1.5-3

если у тебя в задаче нет использования сопроцессора, лучше не лезть в него, особенно при многопоточке
...
Рейтинг: 0 / 0
02.06.2018, 09:53
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654303
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
AR®Я правильно понял, что Вы предлагаете не выписывать явно работу с требуемыми регистрами, а довериться компилятору C ?
Работа с регистрами - явная,
Что касается набора команд - разные версии кода под разные наборы
...
Рейтинг: 0 / 0
02.06.2018, 10:10
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654316
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Толстый длинный регистр нормально сравнивается. Но я-бы делал по возможности 32-разрядные counters
а в теле цикла добавлял 41-битные константы если есть такая крайняя необходимость. В конце
концов основное мясо цикла приходится на полезную работу а не на проверки счетчиков.


Код: plaintext
1.
2.
3.
4.
5.
6.
7.
 printf("Size of long dick = %d bytes\n", sizeof(long));

   for(long dick = 6'000'000'000ul ; 
         dick < 6'000'000'000ul + 10 ; 
         dick++ ) {
      printf("Yet another fucken long dick %llu \n", dick);
   }



Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
        movabsq $6000000000, %rax
        movq    %rax, -8(%rbp)
.L3:
        movq    -8(%rbp), %rdx
        movabsq $6000000009, %rax
        cmpq    %rax, %rdx
        ja      .L2
        movq    -8(%rbp), %rax
        movq    %rax, %rsi
        leaq    .LC1(%rip), %rdi
        movl    $0, %eax
        call    printf@PLT
        addq    $1, -8(%rbp)
        jmp     .L3
...
Рейтинг: 0 / 0
02.06.2018, 11:06
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654346
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
AR®Вряд ли цикл в цикле будет способствовать достижению главной цели (сделать быстрее, чем на C++ с оптимизациями).
Не получится. Я пробовал. Как ни выкручивайся, чаще всего руками написанный ассемблерный код получается медленнее, чем сгенерированный GCC.
...
Рейтинг: 0 / 0
02.06.2018, 13:47
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654347
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ага. Или руками написанный LLVM
...
Рейтинг: 0 / 0
02.06.2018, 14:22
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654451
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Dimitry SibiryakovКак ни выкручивайся, чаще всего руками написанный ассемблерный код получается медленнее, чем сгенерированный GCC.

Пока могу лишь подтвердить это. :)
Сделал тело цикла в ассемблерной вставке, получается в 1,5 раза дольше. Но работает правильно.
...
Рейтинг: 0 / 0
03.06.2018, 11:19
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654452
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
maytonНо я-бы делал по возможности 32-разрядные counters а в теле цикла добавлял 41-битные константы если есть такая крайняя необходимость. В конце концов основное мясо цикла приходится на полезную работу а не на проверки счетчиков.


Количество возможных проходов цикла лежит в диапазоне чисел разрядностью 33-41 бит (это пока). Было бы естественно использовать 64-битный регистр для этого.
...
Рейтинг: 0 / 0
03.06.2018, 11:23
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654457
MBo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MBo
Гость
AR®Всё это работает на "чистом" C++ в пределах 1 суток, но хотелось бы быстрее

А какова реальная задача?
Может быть, есть алгоритмические пути оптимизации?
...
Рейтинг: 0 / 0
03.06.2018, 11:51
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654459
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®maytonНо я-бы делал по возможности 32-разрядные counters а в теле цикла добавлял 41-битные константы если есть такая крайняя необходимость. В конце концов основное мясо цикла приходится на полезную работу а не на проверки счетчиков.


Количество возможных проходов цикла лежит в диапазоне чисел разрядностью 33-41 бит (это пока). Было бы естественно использовать 64-битный регистр для этого.
Используй. Фрагмент gcc-шного ассемблерного выхода ты видел. Но не забывай что РОН-ы это ценный ресурс.
И если ты решил взять 1 регистр и прибить его гвоздями к счетчику циклов то ты лишаешь себя возможности
использовать его в других целях.

Кстати что у тебя внутри тела цикла?
...
Рейтинг: 0 / 0
03.06.2018, 12:03
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654478
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
AR®,

Расчетное - в mmx, переменную цикла - в обычный регистр (rcx, например). У меня так некоторые вставки (например - фильтры-свёртки) отлично работают.
...
Рейтинг: 0 / 0
03.06.2018, 13:05
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654497
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
AR®Количество возможных проходов цикла лежит в диапазоне чисел разрядностью 33-41 бит (это пока).
Даже пустой цикл такого размера займёт туеву хучу времени. На фоне полезной нагрузки в его теле расходы на сам цикл обычно ничтожны. Не парься, пиши цикл в С++ с long long счётчиком.
...
Рейтинг: 0 / 0
03.06.2018, 13:56
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654499
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dimitry SibiryakovAR®Количество возможных проходов цикла лежит в диапазоне чисел разрядностью 33-41 бит (это пока).
Даже пустой цикл такого размера займёт туеву хучу времени. На фоне полезной нагрузки в его теле расходы на сам цикл обычно ничтожны. Не парься, пиши цикл в С++ с long long счётчиком.
Мы занимаемся совершенно ненужным делом. Пытаемся додумать зачем ему (автору) нужен счетчик с 41 битом.
Чисто теоретически я могу предположить что у него шаг цикла растет или стартовое выражение уже изначально
велико.

Вобщем мой вопрос о "реальной задаче" по прежнему актуален.
...
Рейтинг: 0 / 0
03.06.2018, 14:11
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654503
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Зачем нужен MMX регистр в x64?
...
Рейтинг: 0 / 0
03.06.2018, 14:46
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654506
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ценное замечание. Я вот с любезного разрешения Intel сделал скриншотик с доки Introduction to x64 Assembly

Регистр RAX,RDX который участвовал в loop condition моего тестового примера архитектурно отделен от пачки регистров FPU/MMX.
И наверное есть здравый смысл в том что GCC собрал исходник без него. У компиллятора тоже есть свои
метрики стоимости.
...
Рейтинг: 0 / 0
03.06.2018, 14:58
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654550
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Dimitry SibiryakovНе парься, пиши цикл в С++ с long long счётчиком.
Так написан, работает.
...
Рейтинг: 0 / 0
03.06.2018, 19:24
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654551
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
[quot MBo]AR®Может быть, есть алгоритмические пути оптимизации?
Мне они не известны.
...
Рейтинг: 0 / 0
03.06.2018, 19:25
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654554
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
ИзопропилЗачем нужен MMX регистр в x64?

В x86. Было бы в x64, не было бы разговора.
...
Рейтинг: 0 / 0
03.06.2018, 19:26
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654822
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
В общем, вести с полей малоутешительны:
"чистый" C++ - 20 секунд
тело цикла на асм-вставке - 30 секунд
intrinsics-функции - 50 секунд.
...
Рейтинг: 0 / 0
04.06.2018, 12:46
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654868
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Опиши реальную задачу + показывай код )))
...
Рейтинг: 0 / 0
04.06.2018, 13:46
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654870
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®ИзопропилЗачем нужен MMX регистр в x64?

В x86. Было бы в x64, не было бы разговора.
Исторически первыми появились FPU регистры. А они нужны оуенно. Об этом скажет всякий кто уважает AutoCad.
...
Рейтинг: 0 / 0
04.06.2018, 13:48
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654897
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Leonid KudryavtsevОпиши реальную задачу + показывай код )))
Не буду. Задачу должен решить я. )
...
Рейтинг: 0 / 0
04.06.2018, 14:28
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654907
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
AR®Мне они не известны.
Вероятнее всего это из-за узости твоего кругозора. Потому и говорят тебе чтобы опубликовал задачу. У коллективного-то разума кругозор поширше будет.

AR®В x86. Было бы в x64, не было бы разговора.
А в чём проблема собрать под 64 бита?
...
Рейтинг: 0 / 0
04.06.2018, 14:42
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39654925
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Dimitry SibiryakovА в чём проблема собрать под 64 бита?
В имеющихся студии и процессоре в компе. ) Ну и в желании иметь результат, совместимый со старым оборудованием.
...
Рейтинг: 0 / 0
04.06.2018, 14:58
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39655179
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®Leonid KudryavtsevОпиши реальную задачу + показывай код )))
Не буду. Задачу должен решить я. )
Ты хитрый и лукавый. Не будет тебе респекта.
Давай сорцы! Ставлю коньяк что тебе ассемблер не нужен.
...
Рейтинг: 0 / 0
04.06.2018, 20:07
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39655963
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
mayton Ставлю коньяк что тебе ассемблер не нужен.
Я таки выписал свой алгоритм на ассемблерной вставке на 32 битах без использования регистров MMX.
Результат опять-таки малоутешителен: 37 секунд при прочих равных условиях.
Т.е. хуже, чем с MMX и хуже чем то, что сделал компилятор C++.

Куда за коньяком-то? :)
...
Рейтинг: 0 / 0
05.06.2018, 21:42
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39655964
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Вообще, насколько можно верить тому .asm, который остаётся рядом с .obj, если в свойствах проекта задать Assembly Output = "Assembly With Source Code (/FAs)"?
В смысле верить, что то, что там написано и будет в .exe ?
...
Рейтинг: 0 / 0
05.06.2018, 21:52
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39655967
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
AR®Вообще, насколько можно верить тому .asm, который остаётся рядом с .obj, если в свойствах проекта задать Assembly Output = "Assembly With Source Code (/FAs)"?
В смысле верить, что то, что там написано и будет в .exe ?
Можно
...
Рейтинг: 0 / 0
05.06.2018, 21:59
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39655971
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®,

А пруфы где?
...
Рейтинг: 0 / 0
05.06.2018, 22:06
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39655973
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
AR®,

Если компилятор породил код лучше - значит есть к чему стремиться
...
Рейтинг: 0 / 0
05.06.2018, 22:07
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39655976
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Без сорцов - никакого коньяка.
...
Рейтинг: 0 / 0
05.06.2018, 22:10
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39656294
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
AR®Dimitry SibiryakovА в чём проблема собрать под 64 бита?
В имеющихся студии и процессоре в компе. ) Ну и в желании иметь результат, совместимый со старым оборудованием.
Однако выше...
AR®Но мне ещё важна совместимость с разными компами, некоторые из них довольно старые, хотя SSE 4 есть уже на всех проверенных.
Мне не критично использование именно MMX, а нужна быстрая 64-битная арифметика (сложение-вычитание, сдвиги, and-or-xor).
Кажется, во всех процессорах, в которых есть SSE4, есть и поддержка 64 бит.
...
Рейтинг: 0 / 0
06.06.2018, 12:07
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39656330
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
BarloneКажется, во всех процессорах, в которых есть SSE4, есть и поддержка 64 бит.банально 32-битная винда, из-за принтера, например, старого
...
Рейтинг: 0 / 0
06.06.2018, 12:23
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39656661
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
BarloneКажется, во всех процессорах, в которых есть SSE4, есть и поддержка 64 бит.

Вот интересно, позволяет ли какая-нибудь студия скомпилировать 32-битное приложение, но в asm-вставках обращаться к регистрам R8-R15 (64-битным )?
...
Рейтинг: 0 / 0
06.06.2018, 16:33
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39656732
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®
Вот интересно, позволяет ли какая-нибудь студия скомпилировать 32-битное приложение, но в asm-вставках обращаться к регистрам R8-R15 (64-битным )?
большинство команд к регистрам преобрауется в один и тот же код, что в 32-битном, что 64 битном коде. Например, xor RAX,RAX и xor EAX,EAX даёт один и тот же бинарный код для своей разрядности.
Просто в одном случае они интерпретируются как 32-битные, а в другом как 64-битные

в 64-битном коде обращение к 32-битным регистрам добавляет префиксы смены разряда перед командой,обратно насколько мне известно такого префикса нет
...
Рейтинг: 0 / 0
06.06.2018, 17:16
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39656953
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
AR®BarloneКажется, во всех процессорах, в которых есть SSE4, есть и поддержка 64 бит.

Вот интересно, позволяет ли какая-нибудь студия скомпилировать 32-битное приложение, но в asm-вставках обращаться к регистрам R8-R15 (64-битным )?
Нет.
И дело не в студии
...
Рейтинг: 0 / 0
06.06.2018, 22:45
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657098
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
ИзопропилИ дело не в студии

32-битное приложение устанавливает режим процессора, делающий недоступными дополнительные регистры?

А вообще склоняюсь к мысли о безнадёжности темы.
В Intel'овском "Introduction to x64 Assembly.pdf" сказано "although it is difficult to outperform a good C++ compiler for most programmers".

Похоже, MS Visual Studio имеет вполне себе a good C++ compiler.
Вчера вечером сделал новую версию с асм-вставкой (без MMX), в которой минимизировал количество JMP'ов всех видов, но результат ещё хуже - 45 секунд вместо 37.
...
Рейтинг: 0 / 0
07.06.2018, 10:03
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657102
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
AR®Похоже, MS Visual Studio имеет вполне себе a good C++ compiler.
Интеловский еще лучше, тут замеряли 18108708
...
Рейтинг: 0 / 0
07.06.2018, 10:06
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657121
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
AR®32-битное приложение устанавливает режим процессора, делающий недоступными дополнительные регистры?
да
AR®В Intel'овском "Introduction to x64 Assembly.pdf" сказано "although it is difficult to outperform a good C++ compiler for most programmers".
AR®Вчера вечером сделал новую версию с асм-вставкой (без MMX), в которой минимизировал количество JMP'ов всех видов, но результат ещё хуже - 45 секунд вместо 37.
код покажи
...
Рейтинг: 0 / 0
07.06.2018, 10:33
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657217
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Кроме кол-ва Jump'ов они должы быть еще и "правильные". Дабы с Intel Pentium существуют достаточно простые правила для оптимизатора переходов. Т.ч. например условный jump с переходом наверх по коду и условный jump с переходом далее по коду - для процессора очень сильно отличаются. AFAIK

JMP'ы для современных процессоров уже не проблема. Тут скорее важнее, что бы арифметические операции между собой по операндам были не связаны и пенальти не получать. AFAIK

Ну и опять таки, нужно понимать, а под какой конкретно процессор ты собираешься оптимизировать. Первый Pentium от современных - все же очень сильно отличается.

IMHO & AFAIK собираешься оптимизировать Intel VTune иметь на компьютере обязательно. А уж дальше, читать про пенальти которые он тебе выдаст. Ну или выучивать пару томов Intel'овской документации с правилами оптимизаци под твой процессор

p.s.
На первых пентиумах и Pentium II, у меня в коде все время пенальти по частичному обращению к памяти лезли /обращение к байту, когда до этого по адресу записывали слово/. Банальный цикл преобразующий RGB <--> RGBA работал медленнее, чем декомпрессия JPEG'а ))) из оптимизированной Intel'ом библиотеки
...
Рейтинг: 0 / 0
07.06.2018, 11:46
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657460
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Разоблачение чёрной магии.
Не спрашивайте про постановку задачи целиком. Она большая и скучная. Важна суть, а не постановка, а она - ниже.

Есть функция:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
__int32 f(unsigned __int64 a, unsigned __int64 b)
{
	__int64 c = 0;
	__int64 d = 1;

	do
	{
		__int64 e = -(d & 1);
		d >>= 1;
		d ^= e & a;
		c++;
	}
	while (d != 1 && c != b);
                                                        
	return (d == 1 && c == b) ? 1 : 0;	// если выполнились одновременно оба условия, достаточных для выхода из цикла, возвращаем 1, иначе 0
}



Вот что сделал компилятор:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
; 202  : 	__int64 c = 0;

	xor	edx, edx
	push	esi
	push	edi
	mov	DWORD PTR _c$[ebp+4], edx

; 203  : 	__int64 d = 1;

	mov	eax, 1
	xor	ecx, ecx
$LN4@f:

; 204  : 
; 205  : 	do
; 206  : 	{
; 207  : 		__int64 e = -(d & 1);

	mov	esi, eax
	and	esi, 1
	xor	edi, edi

; 208  : 		d >>= 1;
; 209  : 		d ^= e & a;

	neg	esi
	adc	edi, edi
	and	esi, DWORD PTR _a$[ebp]
	shrd	eax, ecx, 1
	neg	edi
	and	edi, DWORD PTR _a$[ebp+4]
	sar	ecx, 1
	xor	eax, esi

; 210  : 		c++;

	mov	esi, DWORD PTR _c$[ebp+4]
	xor	ecx, edi
	add	edx, 1
	adc	esi, 0
	mov	DWORD PTR _c$[ebp+4], esi

; 211  : 	}
; 212  : 	while (d != 1 && c != b);

	cmp	eax, 1
	jne	SHORT $LN11@f
	test	ecx, ecx
	je	SHORT $LN10@f
$LN11@f:
	cmp	edx, DWORD PTR _b$[ebp]
	jne	SHORT $LN4@f
	cmp	esi, DWORD PTR _b$[ebp+4]
	jne	SHORT $LN4@f
$LN7@f:



Контрольный пример: f(4294967337, 8589934591) = 1. Это числа длиной 33 бита.
Требуется версия на ассемблере, работающая быстрее, чем скомпилированная.
...
Рейтинг: 0 / 0
07.06.2018, 15:08
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657499
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Кинь тогда хоть какие-то примерные входные данные и что должно получится.

На мой взгляд, код вполне можно упростить.
...
Рейтинг: 0 / 0
07.06.2018, 15:34
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657502
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Сорри, сразу не заметил

Контрольный пример: f(4294967337, 8589934591) = 1. Это числа длиной 33 бита.
...
Рейтинг: 0 / 0
07.06.2018, 15:35
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657503
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®,

напрашивается декремент b вместо инкремента c
...
Рейтинг: 0 / 0
07.06.2018, 15:35
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657510
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovAR®, напрашивается декремент b вместо инкремента c

Пробовал. А точнее, был декремент c при начальном c = b:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
__int32 f(unsigned __int64 a, unsigned __int64 b)
{
	__int64 c = b;
	__int64 d = 1;

	do
	{
		__int64 e = -(d & 1);
		d >>= 1;
		d ^= e & a;
		c--;
	}
	while (d != 1 && c != 0);
                                                        
	return (d == 1 && c == 0) ? 1 : 0;	// если выполнились одновременно оба условия, достаточных для выхода из цикла, возвращаем 1, иначе 0
}



Результат был хуже на ~5%.
...
Рейтинг: 0 / 0
07.06.2018, 15:45
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657512
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Leonid KudryavtsevНа мой взгляд, код вполне можно упростить.
Буду благодарен.
Но у меня теперь большие сомнения в этом.
...
Рейтинг: 0 / 0
07.06.2018, 15:48
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657513
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
маска e = -(d & 1) может иметь всего два значения (-1 или 0) в зависимости от младшего бита d

соответственно e & a может иметь 2 значения (a или 0) в зависимости от младшего бита d

поэтому для вычисления этого выражения проще всего использовать условную пересылку после проверки бита d
...
Рейтинг: 0 / 0
07.06.2018, 15:49
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657516
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Aleksandr SharahovAR®, напрашивается декремент b вместо инкремента c

Пробовал. А точнее, был декремент c при начальном c = b:

Результат был хуже на ~5%.

нафига тут вообще нужна доп. переменная с?
...
Рейтинг: 0 / 0
07.06.2018, 15:51
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657533
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Aleksandr Sharahovмаска e = -(d & 1) может иметь всего два значения (-1 или 0) в зависимости от младшего бита d

соответственно e & a может иметь 2 значения (a или 0) в зависимости от младшего бита d

поэтому для вычисления этого выражения проще всего использовать условную пересылку после проверки бита d
I think so

+ вместо __int64 для цикла, можно использовать два вложенных цикла по __int32. Максимум избавиться от арифметики над __int64
...
Рейтинг: 0 / 0
07.06.2018, 16:05
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657543
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я так понимаю это обращение к памяти, если использовать регистр проца, то быстрее должно стать
AR®
Код: plaintext
1.
2.
3.
	and	esi, DWORD PTR _a$[ebp]

	and	edi, DWORD PTR _a$[ebp+4]


 
У меня вот во что откомпилировалось
MSVC 2015 Release x64
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
int main() {
000000013F892420  sub         rsp,28h  
	int x = f(4294967337, 8589934591);
000000013F892424  mov         r9d,1  
	int x = f(4294967337, 8589934591);
000000013F89242A  xor         r8d,r8d  
000000013F89242D  mov         edx,r9d  
000000013F892430  mov         r11,100000029h  
000000013F89243A  mov         r10,1FFFFFFFFh  
000000013F892444  nop         dword ptr [rax]  
000000013F892448  nop         dword ptr [rax+rax]  
000000013F892450  mov         rcx,rdx  
000000013F892453  mov         rax,rdx  
000000013F892456  and         ecx,r9d  
000000013F892459  shr         rax,1  
000000013F89245C  dec         rcx  
000000013F89245F  inc         r8  
000000013F892462  and         rcx,r11  
000000013F892465  mov         rdx,rcx  
000000013F892468  xor         rdx,rax  
000000013F89246B  cmp         rdx,r9  
000000013F89246E  je          main+57h (013F892477h)  
000000013F892470  cmp         r8,r10  
000000013F892473  jne         main+30h (013F892450h)  
000000013F892475  jmp         main+5Ch (013F89247Ch)  
000000013F892477  cmp         r8,r10  
000000013F89247A  je          main+5Fh (013F89247Fh)  
000000013F89247C  xor         r9d,r9d  

	printf("%d\n", x);
...


Время 9.3 сек. на i7-6700K

Если не секрет - в чем суть этого цикла? что он делает? Может алгоритм можно сменить?
...
Рейтинг: 0 / 0
07.06.2018, 16:11
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657563
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr Sharahovнафига тут вообще нужна доп. переменная с?

Для её инкремента от 0 до b, т.к. вариант с декрементом оказался медленнее, хотя и не очень сильно.
...
Рейтинг: 0 / 0
07.06.2018, 16:29
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657564
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
AR®Leonid KudryavtsevНа мой взгляд, код вполне можно упростить.
Буду благодарен.
Но у меня теперь большие сомнения в этом.
Дай еще каких нибудь циферек для проверки.
А то я в циклах запустался )))

твой код 23-24 с., мой вариант 18 сек

ассемблер не смотрел. На C давно не программировал (лет 12), т.ч. извеняюсь за говно-код и плохое оформление)))

 

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
#include <QCoreApplication>

#include <windows.h>

__int32 f(unsigned __int64 a, unsigned __int64 b)
{
    __int64 c = 0;
    __int64 d = 1;

    do
    {
        __int64 e = -(d & 1);
        d >>= 1;
        d ^= e & a;
        c++;
    }
    while (d != 1 && c != b);

    printf( "d=%llu  c=%llu  a=%llu    b=%llu\n", d, c, a, b );

    return (d == 1 && c == b) ? 1 : 0;	// если выполнились одновременно оба условия, достаточных для выхода из цикла, возвращаем 1, иначе 0
}

__int32 f2(unsigned __int64 a, unsigned __int64 b)
{
    unsigned __int64 flags[2] = {0,a};
    __int64 c = 0;
    __int64 d = 1;
    unsigned __int64 *e_ptr;

    unsigned int count1;
    unsigned int count2;
    // Избавляемся от in64 счетчика цикла, заменяем просто на
    // два вложенных цикла
    unsigned int i1;
    unsigned int i2;

    count1 = b >> 32;
    count2 = b & 0xFFFFFFFF;
    // Цикл по старшему значению
    for ( i1=count1; i1 > 0;  ) {
        // Здесь мы должны повторить 0x10000000, но это уже не умешается в 32 разряда )))
        for ( i2=0xFFFFFFFF; i2 > 0;  ) {
            // __int64 e = -(d & 1);
            e_ptr = flags + ( d & 1 );
            d >>= 1;
            d ^= *e_ptr;
            i2--;
            // прерываем цикл если d == 1
            if ( d==1 ) {
                goto m_exit;
            }
        }
        // Нужен еще одна лишняя интерация. что бы кол-во интераций было 0x10000000
        // __int64 e = -(d & 1);
        e_ptr = flags + ( d & 1 );
        d >>= 1;
        d ^= *e_ptr;
        i1--;
        // прерываем цикл если d == 1
        if ( d==1 ) {
            goto m_exit;
        }
    }
    for ( i2=count2; i2 > 0; ) {
        // __int64 e = -(d & 1);
        e_ptr = flags + ( d & 1 );
        // заменяем
        d >>= 1;
        d ^= *e_ptr;
        i2--;
        // прерываем цикл если d == 1
        if ( d==1 ) {
            goto m_exit;
        }
    }
m_exit:

    printf( "i1=%i   i2=%i\n", i1, i2 );
    printf( "d=%llu  c=%llu  a=%llu    b=%llu\n", d, c, a, b );
    return (d == 1 && (i1==0 && i2==0) ) ? 1 : 0;	// если выполнились одновременно оба условия, достаточных для выхода из цикла, возвращаем 1, иначе 0
}



int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    __int32 res;
    DWORD start, end;

    start = GetTickCount();
    res = f(4294967337, 8589934591);
    end = GetTickCount();
    printf( "f=%i time=%i\n", res, (end-start) );

    start = GetTickCount();
    res = f2(4294967337, 8589934591);
    end = GetTickCount();
    printf( "f2=%i time=%i\n", res, (end-start) );

    return a.exec();
}



Код: sql
1.
2.
3.
4.
5.
d=1  c=8589934591  a=4294967337    b=8589934591
f=1 time=23078
i1=0   i2=0
d=1  c=0  a=4294967337    b=8589934591
f2=1 time=18688


...
Рейтинг: 0 / 0
07.06.2018, 16:30
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657566
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr Sharahovмаска e = -(d & 1) может иметь всего два значения (-1 или 0) в зависимости от младшего бита d

соответственно e & a может иметь 2 значения (a или 0) в зависимости от младшего бита d

поэтому для вычисления этого выражения проще всего использовать условную пересылку после проверки бита d
Затестил. Втрое медленнее как ни странно
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
	do
	{
		int e = (d & 1);
		d >>= 1;
		if(e) d ^= a;
		c++;
	} while (d != 1 && c != b);
...
Рейтинг: 0 / 0
07.06.2018, 16:31
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657571
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Leonid Kudryavtsev+ вместо __int64 для цикла, можно использовать два вложенных цикла по __int32. Максимум избавиться от арифметики над __int64

Мы избавлены от неё 32-битным компилятором. Напомню, что всё делается на 32-битном компе. И два 32-битных счётчика нам организовал сам компилятор. В случае инкремента так:
Код: plaintext
1.
2.
	add	edx, 1
	adc	esi, 0



А в случае декремента так:
Код: plaintext
1.
2.
	add	edx, -1
	adc	esi, -1



Последнее оказалось немного медленнее (почему?).
...
Рейтинг: 0 / 0
07.06.2018, 16:35
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657577
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Тут между командами взаимозависимость по регистру флагов. Т.е. теоретически "плохо". Но теоретически, практически там возможны исчезающие доли процентов
...
Рейтинг: 0 / 0
07.06.2018, 16:39
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657586
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Leonid KudryavtsevДай еще каких нибудь циферек для проверки.
А то я в циклах запустался )))

f(6777995264, 8589934591) = 1
f(5033164800, 8589934591) = 1

Второе число не трогайте (это маска 33 бита == 1), а первое можете уменьшить-увеличить на 1, функция должна вернуть 0.
...
Рейтинг: 0 / 0
07.06.2018, 16:44
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657599
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Dima TЗатестил. Втрое медленнее как ни странно
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
	do
	{
		int e = (d & 1);
		d >>= 1;
		if(e) d ^= a;
		c++;
	} while (d != 1 && c != b);



Это не странно.
Первоначальный алгоритм содержал if / else, а затем от них избавились путём подбора масок (000..00 и 111..11), позволяющих всегда делать одинаковые действия.
...
Рейтинг: 0 / 0
07.06.2018, 16:49
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657601
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TAleksandr Sharahovмаска e = -(d & 1) может иметь всего два значения (-1 или 0) в зависимости от младшего бита d

соответственно e & a может иметь 2 значения (a или 0) в зависимости от младшего бита d

поэтому для вычисления этого выражения проще всего использовать условную пересылку после проверки бита d
Затестил. Втрое медленнее как ни странно
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
	do
	{
		int e = (d & 1);
		d >>= 1;
		if(e) d ^= a;
		c++;
	} while (d != 1 && c != b);



Ну так компилер не такой же умный, чтоб понять, что о от него требуется
надо что-то вроде этого
e=0;
if (d and 1) e=a;
d^=e;
или сразу всю функцию на асме с условной пересылкой написать
...
Рейтинг: 0 / 0
07.06.2018, 16:49
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657605
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Dima TУ меня вот во что откомпилировалось

Так это всё под x64.
...
Рейтинг: 0 / 0
07.06.2018, 16:50
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657608
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В продолжение 21476642 добавлю x32 вариант, тут тоже нет обращений к памяти внутри цикла
 
Так компилируется в x32
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
__int32 f(unsigned __int64 a, unsigned __int64 b)
{
00A92260  push        ebp  
00A92261  mov         ebp,esp  
00A92263  sub         esp,0Ch  
00A92266  push        ebx  
00A92267  push        esi  
00A92268  xorps       xmm0,xmm0  
	__int64 c = 0;
	__int64 d = 1;
00A9226B  mov         esi,1  
00A92270  movlpd      qword ptr [ebp-8],xmm0  
00A92275  xor         eax,eax  
00A92277  mov         ebx,dword ptr [c]  
00A9227A  push        edi  
00A9227B  mov         edi,dword ptr [ebp-4]  
00A9227E  xchg        ax,ax  

	do
	{
		__int64 e = -(d & 1);
00A92280  mov         edx,esi  
00A92282  xor         ecx,ecx  
00A92284  and         edx,1  
		d >>= 1;
		d ^= e & a;
00A92287  neg         edx  
		d >>= 1;
		d ^= e & a;
00A92289  adc         ecx,ecx  
00A9228B  and         edx,29h  
00A9228E  shrd        esi,eax,1  
00A92292  neg         ecx  
00A92294  and         ecx,1  
00A92297  sar         eax,1  
00A92299  xor         esi,edx  
00A9229B  xor         eax,ecx  
		c++;
00A9229D  add         ebx,1  
00A922A0  adc         edi,0  
	} while (d != 1 && c != b);
00A922A3  cmp         esi,1  
00A922A6  jne         f+4Ch (0A922ACh)  
00A922A8  test        eax,eax  
00A922AA  je          f+5Fh (0A922BFh)  
00A922AC  cmp         ebx,0FFFFFFFFh  
00A922AF  jne         f+20h (0A92280h)  
00A922B1  cmp         edi,1  
00A922B4  jne         f+20h (0A92280h)  

	return (d == 1 && c == b) ? 1 : 0;	// если выполнились одновременно оба условия, достаточных для выхода из цикла, возвращаем 1, иначе 0
00A922B6  xor         eax,eax  
}
00A922B8  pop         edi  
00A922B9  pop         esi  
00A922BA  pop         ebx  
00A922BB  mov         esp,ebp  
00A922BD  pop         ebp  
00A922BE  ret  

	return (d == 1 && c == b) ? 1 : 0;	// если выполнились одновременно оба условия, достаточных для выхода из цикла, возвращаем 1, иначе 0
00A922BF  cmp         ebx,0FFFFFFFFh  
00A922C2  jne         f+56h (0A922B6h)  
00A922C4  cmp         edi,1  
00A922C7  jne         f+56h (0A922B6h)  
00A922C9  mov         eax,edi  
}
00A922CB  pop         edi  
00A922CC  pop         esi  
00A922CD  pop         ebx  
00A922CE  mov         esp,ebp  
00A922D0  pop         ebp  
00A922D1  ret


13.7 сек
...
Рейтинг: 0 / 0
07.06.2018, 16:51
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657615
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovНу так компилер не такой же умный, чтоб понять, что от него требуется
Мне теперь кажется, что он даже умнее, чем просто чтоб понять, что от него требуется. :)

Aleksandr Sharahovсразу всю функцию на асме с условной пересылкой написать
Писал (как вставку в C) 3 версии, все работают дольше, чем "компиляторская". :)
...
Рейтинг: 0 / 0
07.06.2018, 16:54
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657625
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Aleksandr SharahovНу так компилер не такой же умный, чтоб понять, что от него требуется
Мне теперь кажется, что он даже умнее, чем просто чтоб понять, что от него требуется. :)

Aleksandr Sharahovсразу всю функцию на асме с условной пересылкой написать
Писал (как вставку в C) 3 версии, все работают дольше, чем "компиляторская". :)

с использованием CMOV получилось медленнее? не верю )
...
Рейтинг: 0 / 0
07.06.2018, 16:59
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657630
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovНу так компилер не такой же умный, чтоб понять, что о от него требуется
надо что-то вроде этого
e=0;
if (d and 1) e=a;
d^=e;
или сразу всю функцию на асме с условной пересылкой написать
тоже тормоз
Код: plaintext
1.
2.
3.
4.
		__int64 e = 0;
		if(d & 1) e = a;
		d >>= 1;
		d ^= e;
...
Рейтинг: 0 / 0
07.06.2018, 17:01
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657634
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Dima TВ продолжение 21476642 добавлю x32 вариант, тут тоже нет обращений к памяти внутри цикла
Так компилируется в x32
Очень интересно. Особенно, в чём глубокий смысл "and edx, 29h "?
...
Рейтинг: 0 / 0
07.06.2018, 17:04
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657638
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TAleksandr SharahovНу так компилер не такой же умный, чтоб понять, что о от него требуется
надо что-то вроде этого
e=0;
if (d and 1) e=a;
d^=e;
или сразу всю функцию на асме с условной пересылкой написать
тоже тормоз
Код: plaintext
1.
2.
3.
4.
		__int64 e = 0;
		if(d & 1) e = a;
		d >>= 1;
		d ^= e;



Интересно, а
if(d & 1) e = a;
компилируется с переходом или с CMOV'ом?
...
Рейтинг: 0 / 0
07.06.2018, 17:05
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657644
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Dima Tтоже тормоз
Код: plaintext
1.
2.
3.
4.
		__int64 e = 0;
		if(d & 1) e = a;
		d >>= 1;
		d ^= e;



Не мучайтесь. :)
Разные варианты этого алгоритма с ветвлениями были испытаны, и все были в 2-3 раза медленнее. Причём это верно и для чисел до 32 бит (когда всё без __int64).
...
Рейтинг: 0 / 0
07.06.2018, 17:09
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657656
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Dima Tтоже тормоз
Код: plaintext
1.
2.
3.
4.
		__int64 e = 0;
		if(d & 1) e = a;
		d >>= 1;
		d ^= e;



Не мучайтесь. :)
Разные варианты этого алгоритма с ветвлениями были испытаны, и все были в 2-3 раза медленнее. Причём это верно и для чисел до 32 бит (когда всё без __int64).

тут нет ветвления, если у компилятора есть AI
...
Рейтинг: 0 / 0
07.06.2018, 17:16
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657665
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Aleksandr Sharahov.....
с использованием CMOV получилось медленнее? не верю )
А я такую полезную инструкцию даже и не помнил )))

Хорошая же идея. После сдвига в >> в регистре флагов окажется младший бит. Т.ч. можно & на ассемблере и не делать.

Но все равно. код можно сделать компактным, но скорости не добавит. Все шаги завязанны на переменную d, спекулятивное вычисление фиг получишь.
...
Рейтинг: 0 / 0
07.06.2018, 17:18
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657684
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Leonid KudryavtsevAleksandr Sharahov.....
с использованием CMOV получилось медленнее? не верю )
А я такую полезную инструкцию даже и не помнил )))


Просветите меня тёмного, CMOV - это что-то только для x64? Или и для x86 она есть? MS VS C++ её знает?
Что она делает?
...
Рейтинг: 0 / 0
07.06.2018, 17:25
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657692
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Leonid Kudryavtsevпропущено...

А я такую полезную инструкцию даже и не помнил )))


Просветите меня тёмного, CMOV - это что-то только для x64? Или и для x86 она есть? MS VS C++ её знает?
Что она делает?

есть везде, если комп не ископаемый, ассемблер точно знает
...
Рейтинг: 0 / 0
07.06.2018, 17:34
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657775
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
IMHO Т.к. от длинного счетчика цикла вполне можно уйти. Скорее всего, от MMX выйгрышь будет.

Избавление от ненужных __int64 дало +25% ( 24 сек -> 18 сек), наверное и MMX даст примерно столько же. Но дальше - уже чисто тактовая частота процессора. Тут оптимизировать особо нечего, одно число (d) в цикле крутится. Т.ч. все конвееры современных процессоров идут лесом.

Тут только в математику вдумываться. Т.к. мне кажется, что близкие циклы зависят только от младших битов A. Т.ч., мне кажется, вполне можно за одну операцию обрабатывать сразу несколько битов в D. "Перепрыгивая" циклы
...
Рейтинг: 0 / 0
07.06.2018, 18:22
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657782
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
AR®Dima TВ продолжение 21476642 добавлю x32 вариант, тут тоже нет обращений к памяти внутри цикла
Так компилируется в x32
Очень интересно. Особенно, в чём глубокий смысл "and edx, 29h "?
Похоже компилятор перестарался 4294967337 = 0x00000001000000 29
...
Рейтинг: 0 / 0
07.06.2018, 18:27
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657809
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
чуть больше 9 сек на i5-2300, не отлаживал, параметры передаются по адресу
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
function f(a, b: pint64): boolean;
asm
  push ebx
  push ebp
  push esi
  push edi
  //b
  mov ebx, dword ptr [edx]
  mov ebp, dword ptr [edx+4]
  //d:=1;
  mov esi, 1
  xor edi, edi
@loop:
  //shift d, calc mask
  shrd esi, edi, 1
  sbb ecx, 0
  mov edx, ecx
  shr edi, 1
  //e
  and ecx, dword ptr[eax]
  and edx, dword ptr[eax+4]
  //new d
  xor esi, ecx
  xor edi, edx
  //test d
  cmp esi, 1
  jne @1
  test edi, edi
  jz @done
@1:
  //test b
  test ebx, ebx
  jne @loop
  test ebp, ebp
  jne @loop
@done:
  xor eax, eax
  xor esi, 1
  or esi, edi
  or esi, ebx
  or esi, ebp
  jnz @false
  inc eax
@false:
  pop edi
  pop esi
  pop ebp
  pop ebx
  end;
...
Рейтинг: 0 / 0
07.06.2018, 18:44
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657817
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
увидел опечатку, наверно теперь пострадает скорость )

sbb ecx, 0

заменить на

sbb ecx, ecx
...
Рейтинг: 0 / 0
07.06.2018, 18:50
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657827
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Aleksandr Sharahov shrd esi, edi, 1
sbb ecx, 0

Красиво.
А я даже не знал, что в Intel есть инструкции с двойной точностью (((
...
Рейтинг: 0 / 0
07.06.2018, 18:57
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657836
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Aleksandr Sharahov
Код: pascal
1.
2.
3.
4.
5.
6.
@1:
  //test b
  test ebx, ebx
  jne @loop
  test ebp, ebp
  jne @loop


Это проверка на выход из цикла. А где сам декримент переменной цикла? Или я совсем ослеп (((
...
Рейтинг: 0 / 0
07.06.2018, 19:04
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657914
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Leonid KudryavtsevAleksandr Sharahov
Код: pascal
1.
2.
3.
4.
5.
6.
@1:
  //test b
  test ebx, ebx
  jne @loop
  test ebp, ebp
  jne @loop


Это проверка на выход из цикла. А где сам декримент переменной цикла? Или я совсем ослеп (((

Действительно, забыл,
исправленный вариант с новыми ошибками (менее 13 сек на i7-7700)
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
function f(a, b: pint64): boolean;
asm
  push ebx
  push ebp
  push esi
  push edi
  //d:=1;
  mov esi, 1
  xor edi, edi
  //b
  mov ebx, dword ptr [edx]
  mov ebp, dword ptr [edx+4]
  sub ebx, esi
  sbb ebp, edi
@loop:
  //shift d, calc mask
  shrd esi, edi, 1
  sbb ecx, ecx
  mov edx, ecx
  shr edi, 1
  //e
  and ecx, dword ptr[eax]
  and edx, dword ptr[eax+4]
  //new d
  xor esi, ecx
  xor edi, edx
  //test d
  cmp esi, 1
  jne @1
  test edi, edi
  jz @done
@1:
  //test b
  sub ebx, 1
  jnc @loop
  add ebp, ebx
  jge @loop
@done:
  xor eax, eax
  add ebx, edi
  or  ebx, ebp
  and esi, edi
  xor esi, -1
  or esi, ebx
  setz al
  pop edi
  pop esi
  pop ebp
  pop ebx
  end;
...
Рейтинг: 0 / 0
07.06.2018, 20:44
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657917
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®,

Пробовал развернуть цикл?
...
Рейтинг: 0 / 0
07.06.2018, 20:52
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657919
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Исправил неточность с выходом из цикла,
даже не надеюсь, что багов не осталось
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
function f(a, b: pint64): boolean;
asm
  push ebx
  push ebp
  push esi
  push edi
  //d:=1;
  mov esi, 1
  xor edi, edi
  //b
  mov ebx, dword ptr [edx]
  mov ebp, dword ptr [edx+4]
  sub ebx, esi
  sbb ebp, edi
@loop:
  //shift d, calc mask
  shrd esi, edi, 1
  sbb ecx, ecx
  mov edx, ecx
  shr edi, 1
  //e
  and ecx, dword ptr[eax]
  and edx, dword ptr[eax+4]
  //new d
  xor esi, ecx
  xor edi, edx
  //test d
  cmp esi, 1
  jne @1
  test edi, edi
  jz @done
@1:
  //test b
  sub ebx, 1
  jnc @loop
  add ebp, ebx
  jge @loop
  xor eax, eax
  jmp @ret
@done:
  xor eax, eax
  and ebx, ebp
  cmp ebx, -1
  setz al
@ret:
  pop edi
  pop esi
  pop ebp
  pop ebx
  end;
...
Рейтинг: 0 / 0
07.06.2018, 20:58
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657921
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Финальное исправление
все 3x3 контрольных примера проходят
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
function f(a, b: pint64): boolean;
asm
  push ebx
  push ebp
  push esi
  push edi
  //d:=1;
  mov esi, 1
  xor edi, edi
  //b
  mov ebx, dword ptr [edx]
  mov ebp, dword ptr [edx+4]
  sub ebx, esi
  sbb ebp, edi
@loop:
  //shift d, calc mask
  shrd esi, edi, 1
  sbb ecx, ecx
  mov edx, ecx
  shr edi, 1
  //e
  and ecx, dword ptr[eax]
  and edx, dword ptr[eax+4]
  //new d
  xor esi, ecx
  xor edi, edx
  //test d
  cmp esi, 1
  jne @1
  test edi, edi
  jz @done
@1:
  //test b
  sub ebx, 1
  jnc @loop
  add ebp, ebx
  jge @loop
  xor eax, eax
  jmp @ret
@done:
  xor eax, eax
  or  ebx, ebp
  setz al
@ret:
  pop edi
  pop esi
  pop ebp
  pop ebx
  end;
...
Рейтинг: 0 / 0
07.06.2018, 21:14
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657929
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
maytonAR®, Пробовал развернуть цикл?
В каком смысле развернуть?
...
Рейтинг: 0 / 0
07.06.2018, 21:32
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657930
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Leonid KudryavtsevAleksandr Sharahov shrd esi, edi, 1
sbb ecx, 0

Красиво.
А я даже не знал, что в Intel есть инструкции с двойной точностью (((

Только она не совсем двойной точности. Она двигает первый операнд, а второй использует только чтобы взять из него замещающие биты биты, а сам он остаётся не сдвигается.
Просветите пожалуйста: CMOV меняет состояние флага CF ?
...
Рейтинг: 0 / 0
07.06.2018, 21:40
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657933
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®maytonAR®, Пробовал развернуть цикл?
В каком смысле развернуть?
Ну... обычно если число итераций заранее известно то делают копи-пасту тела цикла.
Выглядит по индусски... Но работает для highload. У тебя второй аргумент - всегда
константа? На этом можно сыграть.

Твой код похож на криптографию. Есть раунд. Внутри некая последовательность
операций над ключом. Только крипто-раунд возвращает шифро-блок. А ты возвращаешь
какой-то булевый признак.
...
Рейтинг: 0 / 0
07.06.2018, 21:53
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657934
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Просветите пожалуйста: CMOV меняет состояние флага CF ?

не меняет
...
Рейтинг: 0 / 0
07.06.2018, 21:57
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657936
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonAR®пропущено...

В каком смысле развернуть?
Ну... обычно если число итераций заранее известно то делают копи-пасту тела цикла.
Выглядит по индусски... Но работает для highload. У тебя второй аргумент - всегда
константа? На этом можно сыграть.

Твой код похож на криптографию. Есть раунд. Внутри некая последовательность
операций над ключом. Только крипто-раунд возвращает шифро-блок. А ты возвращаешь
какой-то булевый признак.

Ну, не очень-то и по идусски.
В данном случае даже один лишний переход будет иметь большое значение, т.к. их тут немалая концентрация.
В общем, обязательно стоит попробовать. ща только сериальчик досмотрю )
...
Рейтинг: 0 / 0
07.06.2018, 22:17
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657937
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
maytonAR®пропущено...

В каком смысле развернуть?
... обычно если число итераций заранее известно... У тебя второй аргумент - всегда
константа?

Второй аргумент - максимальное возможное число проходов цикла, а фактическое число проходов заранее неизвестно. Для тех значений первого аргумента, для которых f() = 0, оно может быть и очень небольшим.
...
Рейтинг: 0 / 0
07.06.2018, 22:19
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657940
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
AR®,

Постановка задачи неверная. Нужно внешний цикл вызова твоей f параллелить.
Причем параллелить с SSE.

В лоб при таких условиях хороший компилятор не обогнать никак.
...
Рейтинг: 0 / 0
07.06.2018, 22:25
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657942
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Siemargl, насколько я понял автор ведет борьбу на ниве 32х битных легаси машин с ММХ.
...
Рейтинг: 0 / 0
07.06.2018, 22:29
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657943
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SiemarglAR®,

Постановка задачи неверная. Нужно внешний цикл вызова твоей f параллелить.
Причем параллелить с SSE.

В лоб при таких условиях хороший компилятор не обогнать никак.

Дык обогнал уже.
...
Рейтинг: 0 / 0
07.06.2018, 22:30
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657950
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Тут цена вопроса какая? Можно сделать мемоизацию.

Сделаем табличку на 2^33 bits = 2^(33-3) bytes. Для аргумента а. Аргумент b y нас константа.
Его можно хардкодить. И заполним табличку расчитанными значениями функции
f(a,b)==f'(a). Редукция подразумевается. Аргумент b уже учтен в новой функции b'

На расчет таблички уйдет много времени. Но это можно делать постепенно. И сохранять
результат на диск.

Вобщем насколько далеко готов автор зайти в попытке ускорить эту функцию.
...
Рейтинг: 0 / 0
07.06.2018, 22:51
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657956
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

надежды не оправдались: проверил развертывание цикла в 2 раза - ускорение ~ 0.6%
...
Рейтинг: 0 / 0
07.06.2018, 23:01
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657957
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
maytonSiemargl, насколько я понял автор ведет борьбу на ниве 32х битных легаси машин с ММХ.про ммх пора забыть, sse2 существенно быстрее и есть ну очень давно (лет этак 11c 2001г)
...
Рейтинг: 0 / 0
07.06.2018, 23:03
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657961
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahovmayton,

надежды не оправдались: проверил развертывание цикла в 2 раза - ускорение ~ 0.6%
Мда.. тут не те условия. В исходниках крипто-алгоритмов я часто видел такой хардкод

Код: plaintext
1.
#define ROUND_ENC(a,b,c,d,e,....) __asm{ ......}



А в основном коде шла копи-паста эдак штук 16 или 32 раза ROUND_ENC(...).
...
Рейтинг: 0 / 0
07.06.2018, 23:07
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657963
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Перестановка операторов дает небольшой прирост скорости (итого 12.64 сек на i7-7700)

 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
function f(a, b: pint64): boolean;
asm
  push ebx
  push ebp
  push esi
  push edi
  //d:=1;
  mov esi, 1
  xor edi, edi
  //b
  mov ebx, dword ptr [edx]
  mov ebp, dword ptr [edx+4]
  sub ebx, esi
  sbb ebp, edi
@loop:
  //shift d, calc mask
  shrd esi, edi, 1
  sbb ecx, ecx
  shr edi, 1
  //e
  mov edx, dword ptr[eax]
  and edx, ecx
  and ecx, dword ptr[eax+4]
  //new d
  xor esi, edx
  xor edi, ecx
  //test d
  cmp esi, 1
  jne @1
  test edi, edi
  jz @done
@1:
  //test b
  sub ebx, 1
  jnc @loop
  add ebp, ebx
  jge @loop
  xor eax, eax
  jmp @ret
@done:
  xor eax, eax
  or  ebx, ebp
  setz al
@ret:
  pop edi
  pop esi
  pop ebp
  pop ebx
  end;

...
Рейтинг: 0 / 0
07.06.2018, 23:08
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657965
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Небольшой флешбек.
AR®Не спрашивайте про постановку задачи целиком. Она большая и скучная. Важна суть, а не постановка, а она - ниже.
Знаешь ты всё таки заслужил коньяк. И хотя ты, хитрый лис не показал мне оригинальную полный стек
(а я всегда смотрел в суть вызова. Кто ? Зачем? Как часто? Какие цели .... и я всегда нудный и дотошный
в постановках и пытаюсь убедить бизнес-аналитика что тот не прав... и этот велосипед на костылях
нелетает просто по причине само-противоречий в ТЗ) я согласен тебе его отправить.

Скажи куда.
...
Рейтинг: 0 / 0
07.06.2018, 23:15
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657976
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Еще немного ускорил (итого 10.14 сек на i7-7700)

 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
function f(a, b: pint64): boolean;
asm
  push ebx
  push ebp
  push esi
  push edi
  //d:=1;
  mov esi, 1
  mov ecx, esi
  xor edi, edi
  //b
  mov ebx, dword ptr [edx]
  mov ebp, dword ptr [edx+4]
  sub ebx, esi
  sbb ebp, edi
@loop:
  //shift d
  shrd esi, edi, 1
  shr edi, 1
  //a & mask
  mov edx, dword ptr[eax]
  neg ecx
  and edx, ecx
  and ecx, dword ptr[eax+4]
  //new d
  xor esi, edx
  xor edi, ecx
  //test d
  cmp esi, 1
  jne @1
  test edi, edi
  jz @done
@1:
  mov ecx, esi
  and ecx, 1
  //test b
  sub ebx, 1
  jnc @loop
  add ebp, ebx
  jge @loop
  xor eax, eax
  jmp @ret
@done:
  xor eax, eax
  or  ebx, ebp
  setz al
@ret:
  pop edi
  pop esi
  pop ebp
  pop ebx
  end;

...
Рейтинг: 0 / 0
07.06.2018, 23:37
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657994
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

занафига все это, если есть теория )
...
Рейтинг: 0 / 0
08.06.2018, 00:14
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39657996
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Какая теория?
...
Рейтинг: 0 / 0
08.06.2018, 00:16
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658000
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

о которой молчит автор-партизан
...
Рейтинг: 0 / 0
08.06.2018, 00:21
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658003
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Хм.. да. Видимо топик живет своей жизнью. Отдельно от автора.
...
Рейтинг: 0 / 0
08.06.2018, 00:26
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658004
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Наверное крякает что-то. Стесняется.
...
Рейтинг: 0 / 0
08.06.2018, 00:28
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658017
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Еще ускорил - отнес сравнения подальше от вычислений (итого 9.75 сек на i7-7700)

 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
function f(a, b: pint64): boolean;
asm
  push ebx
  push ebp
  push esi
  push edi
  //d:=1;
  mov esi, 1
  xor edi, edi
  //b
  mov ebx, dword ptr [edx]
  mov ebp, dword ptr [edx+4]
  sub ebx, esi
  sbb ebp, edi
  jmp @entry

@loop:
  //new d
  xor esi, edx
  xor edi, ecx
  //test d
  cmp esi, 1
  jne @entry
  test edi, edi
  jz @false

@entry:
  mov ecx, esi
  and ecx, 1
  neg ecx
  shrd esi, edi, 1
  shr edi, 1
  mov edx, dword ptr[eax]
  and edx, ecx
  and ecx, dword ptr[eax+4]
  //test b
  sub ebx, 1
  jnc @loop
  add ebp, ebx
  jge @loop

  //test d
  xor eax, eax
  xor esi, edx
  xor edi, ecx
  xor esi, 1
  or esi, edi
  setz al
  jmp @done
@false:
  xor eax, eax
@done:
  pop edi
  pop esi
  pop ebp
  pop ebx
  end;

...
Рейтинг: 0 / 0
08.06.2018, 01:36
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658051
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
это уже за рамками добра и зла:

Код: plaintext
1.
2.
3.
4.
5.
6.
	DWORD d1, d2;
	d1 = GetTickCount();
	
	__int32 r = f(4294967337, 8589934591);
	
	d2 = GetTickCount();



резулт:

 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
; 24   : 	DWORD d1, d2;
; 25   : 	d1 = GetTickCount();

  00007	8b 35 00 00 00
	00		 mov	 esi, DWORD PTR __imp__GetTickCount@0
  0000d	57		 push	 edi
  0000e	ff d6		 call	 esi
  00010	8b f8		 mov	 edi, eax

; 26   : 	__int32 r = f(4294967337, 8589934591);
; 27   : 	d2 = GetTickCount();

  00012	ff d6		 call	 esi
  00014	83 ec 10	 sub	 esp, 16			; 00000010H
  00017	8b f0		 mov	 esi, eax
  00019	e8 00 00 00 00	 call	 ?f@@YAH_K0@Z		; f

...
Рейтинг: 0 / 0
08.06.2018, 08:48
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658053
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)это уже за рамками добра и зла
Нормально все. Ты же r нигде не используешь, вот компилятор его и выкинул. Добавь printf(r)
...
Рейтинг: 0 / 0
08.06.2018, 08:51
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658056
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

вот полный код:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
int test1()
{
	DWORD d1, d2;
	d1 = GetTickCount();
	
	__int32 r = f(4294967337, 8589934591);
	
	d2 = GetTickCount();
	printf("result = %d\n", r);
	printf("Time = %d - %d\n", d1, d2);
	return (d2 - d1);

}

int main()
{
	printf("Time = %d\n", test1());


    return 0;
}
...
Рейтинг: 0 / 0
08.06.2018, 08:55
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658060
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)вот полный код:
Т.е. получается компилятор сам посчитал f(4294967337, 8589934591) ? Однако слишком вумный

Долго компилировал? И что за компилятор?
...
Рейтинг: 0 / 0
08.06.2018, 08:59
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658061
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,
студия 15-я
да ничего он не посчитал, просто вызов GetTickCount всего 1 сделал (см листинг)
...
Рейтинг: 0 / 0
08.06.2018, 09:00
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658064
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

вернее он местами поменял вызовы
...
Рейтинг: 0 / 0
08.06.2018, 09:04
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658065
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Dima T,
студия 15-я
да ничего он не посчитал, просто вызов GetTickCount всего 1 сделал (см листинг)
Он расчет тебе в printf() заинлайнил, т.е. так получилось
Код: plaintext
1.
printf("result = %d\n", f(4294967337, 8589934591));


Веселый замер времени получился.
...
Рейтинг: 0 / 0
08.06.2018, 09:04
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658071
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

нет

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
	00		 mov	 esi, DWORD PTR __imp__GetTickCount@0
  0000d	57		 push	 edi
  0000e	ff d6		 call	 esi
  00010	8b f8		 mov	 edi, eax

; 26   : 	__int32 r = f(4294967337, 8589934591);
; 27   : 	d2 = GetTickCount();

  00012	ff d6		 call	 esi

видишь, вызов GetTickCount идёт раньше чем вызов f
...
Рейтинг: 0 / 0
08.06.2018, 09:13
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658076
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)видишь, вызов GetTickCount идёт раньше чем вызов f
Я про это и писал: как понимаю компилятор посчитал что эти вызовы никак не связаны меж собой поэтому соптимизировал: выкинул r и воткнул вызов f в printf().
...
Рейтинг: 0 / 0
08.06.2018, 09:18
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658077
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
ы
 
[SRC с++]f(unsigned long long, unsigned long long):
vmovdqa xmm0, XMMWORD PTR .LC0
push ebx
vmovq xmm3, QWORD PTR [esp+8]
vmovq xmm2, QWORD PTR [esp+16]
vmovd eax, xmm0
vpextrd edx, xmm0, 1
.L2:
vmovdqa xmm1, XMMWORD PTR .LC0
mov ecx, eax
mov ebx, edx
shrd ecx, edx, 1
sar ebx
vpand xmm0, xmm0, xmm1
vpxor xmm1, xmm1, xmm1
vpsubq xmm0, xmm1, xmm0
vpand xmm1, xmm0, xmm3
vmovd xmm0, ecx
vpinsrd xmm0, xmm0, ebx, 1
vpxor xmm0, xmm1, xmm0
vpcmpeqd xmm1, xmm1, xmm1
vpaddq xmm2, xmm2, xmm1
vpunpcklqdq xmm2, xmm2, xmm2
vmovd eax, xmm0
vpextrd edx, xmm0, 1
vmovdqa xmm1, XMMWORD PTR .LC0
vpxor xmm1, xmm0, xmm1
vpunpcklqdq xmm1, xmm1, xmm1
vptest xmm1, xmm1
sete cl
vptest xmm2, xmm2
sete bl
test cl, cl
jne .L4
test bl, bl
je .L2
.L4:
and ecx, ebx
pop ebx
movzx eax, cl
ret[/SRC]

это для Sandy Bridge (2011) и новее

https://godbolt.org/g/yzz7VJ
...
Рейтинг: 0 / 0
08.06.2018, 09:18
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658080
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

он функции переставляет потому что f ни на что не ссылается, добавил GetTickCount в f и перестановки уже нет

Код: plaintext
1.
2.
3.
4.
5.
__int32 f(unsigned __int64 a, unsigned __int64 b)
{
	GetTickCount();
	__int64 c = 0;
	__int64 d = 1;



Time = 14673

как-то дофига блин
...
Рейтинг: 0 / 0
08.06.2018, 09:18
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658082
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr Sharahovзанафига все это, если есть теория )

Теорий много. Все теории стоят одна другой ©. ))
Спасибо за примеры кода. Будет времечко, изучу.
Пара заметок:
1) корректно приводить время работы не просто для модели процессора, но с указанием его тактовой частоты
2) по ходу экспериментов я наступал как на "ложное срабатывание", так и на "ложное несрабатывание" своих асм-версий функции.
Поэтому вот более серьёзный тест: все числа от 4294967297 до 4294967550 в качестве 1-го аргумента функции, второй аргумент прежний - 8589934591. Весь цикл (254 шага) не займёт больше 20 минут.
Должно быть ровно 20 случаев f()==1. Если не 20, то в алгоритме ошибка.
...
Рейтинг: 0 / 0
08.06.2018, 09:21
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658083
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
если обратить внимание - то заинлайненный код вызова с параметрами-константами отличается от абстрактной функции.
наверно, при этих значениях, что то упростилось
...
Рейтинг: 0 / 0
08.06.2018, 09:21
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658085
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Siemarglесли обратить внимание - то заинлайненный код вызова с параметрами-константами отличается от абстрактной функции.
наверно, при этих значениях, что то упростилось
просто расчет пошел для int32_t - константы влезли в 32бита
...
Рейтинг: 0 / 0
08.06.2018, 09:23
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658086
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Time = 14673

как-то дофига блин
там 8589934591 итераций цикла.

Еще там другой прикол компилятора есть в x32: нельзя писать f(4294967337, 8589934591), он магические числа в код вставляет 21477188
...
Рейтинг: 0 / 0
08.06.2018, 09:25
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658090
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Aleksandr Sharahovзанафига все это, если есть теория )
Теорий много. Все теории стоят одна другой ©. ))

Конкретно по тому, что ты делаешь, есть довольно развитая теория.
Но ссылок не дам, т.к. "Задачу должен решить ты" (с).

AR®Спасибо за примеры кода. Будет времечко, изучу.

Что там изучать, просто используй, ибо:
a) Delphi+BASM=страшная сила,
б) хороший компилятор не заменяет мозг.

AR®Пара заметок:
1) корректно приводить время работы не просто для модели процессора, но с указанием его тактовой частоты

Начать надо сам знаешь с кого.
Частоты легко гуглятся, если чё.

AR®2) по ходу экспериментов я наступал как на "ложное срабатывание", так и на "ложное несрабатывание" своих асм-версий функции.
Поэтому вот более серьёзный тест: все числа от 4294967297 до 4294967550 в качестве 1-го аргумента функции, второй аргумент прежний - 8589934591. Весь цикл (254 шага) не займёт больше 20 минут.
Должно быть ровно 20 случаев f()==1. Если не 20, то в алгоритме ошибка.
А вот это проверим.
...
Рейтинг: 0 / 0
08.06.2018, 09:35
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658098
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Dima TЕще там другой прикол компилятора есть в x32: нельзя писать f(4294967337, 8589934591), он магические числа в код вставляет

Я для теста передаю их как аргументы командной строки консольного приложеньица, зовущего f().
...
Рейтинг: 0 / 0
08.06.2018, 09:47
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658106
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
maytonНебольшой флешбек. Знаешь ты всё таки заслужил коньяк.

Полагаю, что не заслужил. Ибо конкретно у меня пока быстрее C++ не получилось.
Работаем...
...
Рейтинг: 0 / 0
08.06.2018, 09:55
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658109
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Как будет угодно.
...
Рейтинг: 0 / 0
08.06.2018, 10:02
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658123
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Поэтому вот более серьёзный тест: все числа от 4294967297 до 4294967550 в качестве 1-го аргумента функции, второй аргумент прежний - 8589934591. Весь цикл (254 шага) не займёт больше 20 минут.
Должно быть ровно 20 случаев f()==1. Если не 20, то в алгоритме ошибка.

алгоритм 21477774 на i5-2300 проверку прошел, затратив 995.5 сек
тест с 4294967297 на i5-2300 проходится за 15.99 сек

частота i5-2300 плавает от 2.8 до 3.1, считаем 3.1.
...
Рейтинг: 0 / 0
08.06.2018, 10:18
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658137
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Версия на С++:
на i3-2120 @3.3 ГГц вышеописанный цикл из 254 шагов делается за 800..845 секунд.
...
Рейтинг: 0 / 0
08.06.2018, 10:30
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658155
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®,

значит, считаем 2.8 )
...
Рейтинг: 0 / 0
08.06.2018, 10:57
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658191
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
алгоритм 21477774 на i5-3470 (3.2 GHz) проверку прошел, затратив 758.7 сек
...
Рейтинг: 0 / 0
08.06.2018, 11:34
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658292
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Выяснил, что работу существенно тормозят ассемблерные команды сравнения вида

cmp ecx, <что-нибудь>

если в них стоит регистр не ecx и не edx.
Полагаю, бывалым ассемблерщикам эта ситуация ясна, но мне как новичку - нет.
Так и должно быть?
...
Рейтинг: 0 / 0
08.06.2018, 12:59
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658302
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Выяснил, что работу существенно тормозят ассемблерные команды сравнения вида

cmp ecx, <что-нибудь>

если в них стоит регистр не ecx и не edx.
Полагаю, бывалым ассемблерщикам эта ситуация ясна, но мне как новичку - нет.
Так и должно быть?

так не должно быть, сейчас должно быть пофигу
...
Рейтинг: 0 / 0
08.06.2018, 13:03
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658312
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
"Команды" нынче вообще НЕ тормозят. Нет такого понятия.
Есть конвееры, есть throughtinput, есть latency, есть пенальти (например зависимость от пред. значений, неверное предсказание перехода)

Более того, есть даже Zero Time Instruction (или как-то так, т.е. иструкции выполняемые за 0 тактов прямо декодером команд).

AFAIK
...
Рейтинг: 0 / 0
08.06.2018, 13:14
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658313
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
В каком смысле сейчас?
...
Рейтинг: 0 / 0
08.06.2018, 13:14
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658329
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®В каком смысле сейчас?

в смысле на твоем процессоре
...
Рейтинг: 0 / 0
08.06.2018, 13:33
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658348
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
В моём процессоре оно, к сожалению, есть. Причём не имеет значения, что будет 2-м аргументом CMP - память, константа, другой регистр.
Требовать замены проца? ))
...
Рейтинг: 0 / 0
08.06.2018, 13:55
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658356
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®В моём процессоре оно, к сожалению, есть. Причём не имеет значения, что будет 2-м аргументом CMP - память, константа, другой регистр.
Требовать замены проца? ))

... или попробовать переименовать регистры в программе.
Что-то другое влияет и подставляет регистры.
...
Рейтинг: 0 / 0
08.06.2018, 14:01
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658377
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Что же это за процессор такой ? )))

Дело не в регистре, важно что с этим регистром происходило до этого.

IMHO & AFAIK
...
Рейтинг: 0 / 0
08.06.2018, 14:17
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658378
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Время на прогон от 4294967297 до 4294967550 169сек

Это была реклама китайского i7-3770@4GHz
...
Рейтинг: 0 / 0
08.06.2018, 14:17
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658380
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Если собираетесь разбираться в производительности, ставьте Intel VTune (коммерческая цена от 800$)
он Вам и покажет, какие пенальти возникают и пр.

А так, это гадание на кофейной гуще
...
Рейтинг: 0 / 0
08.06.2018, 14:19
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658386
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
SiemarglВремя на прогон от 4294967297 до 4294967550 169сек
Это была реклама китайского i7-3770@4GHz
И получено 20 раз f()=1 ?
...
Рейтинг: 0 / 0
08.06.2018, 14:24
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658403
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Коллеги. У меня предложение. Абсолютные цифры в секундах что вы постите - неинформативны для других железяк.

Предлагаю взять за 100% первый вариант автора и если вы сделали удачную оптимизацию - укажите секунды и проценты ускорения.
...
Рейтинг: 0 / 0
08.06.2018, 14:50
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658417
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Еще бы хорошо компилятор указывать.

У меня QT ((( у него формат inline ассемблера совсем для меня не привычный (((
...
Рейтинг: 0 / 0
08.06.2018, 14:58
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658432
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Leonid KudryavtsevЕсли собираетесь разбираться в производительности, ставьте Intel VTune (коммерческая цена от 800$)
он Вам и покажет, какие пенальти возникают и пр.
А так, это гадание на кофейной гуще

Лирическое отступление: ваши слова, между прочим, неплохо иллюстрируют суть англосаксонской цивилизации: вещью владеешь, но полноценно воспользоваться ей просто так не сможешь, а только заплатив дополнительно. )
...
Рейтинг: 0 / 0
08.06.2018, 15:04
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658443
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Leonid KudryavtsevЕсли собираетесь разбираться в производительности, ставьте Intel VTune (коммерческая цена от 800$)
он Вам и покажет, какие пенальти возникают и пр.
А так, это гадание на кофейной гуще

Это подлинная магия, тасование инструкции ассемблера круче гадания на картах )

maytonКоллеги. У меня предложение. Абсолютные цифры в секундах что вы постите - неинформативны для других железяк.

Предлагаю взять за 100% первый вариант автора и если вы сделали удачную оптимизацию - укажите секунды и проценты ускорения.

А нету как такового вариант автора.
Предлагаю автору запостить *полный* *ассемблерный* листинг тестируемой функции.

Я пока остановился на таком варианте
1) 14.617 сек (i5-2300@2.8) 11.809 сек (i5-3470@3.2)
20) 910.780 сек (i5-2300@2.8) 727.574 сек (i5-3470@3.2)
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
function f(a, b: pint64): boolean;
asm
  push ebx
  push ebp
  push esi
  push edi
  //d:=1;
  mov esi, 1
  xor edi, edi
  //b:=count-1;
  mov ebx, dword ptr [edx]
  mov ebp, dword ptr [edx+4]
  sub ebx, esi
  sbb ebp, edi
  mov edx, esi
  jmp @entry

@loop:
  //new d
  xor edi, ecx
  xor esi, edx
  mov edx, esi
  //test d
  cmp edx, 1
  jne @entry
  test edi, edi
  jz @false

@entry:
  shrd esi, edi, 1
  and edx, 1
  xor ecx, ecx
  sub ecx, edx
  mov edx, dword ptr[eax]
  and edx, ecx
  and ecx, dword ptr[eax+4]
  shr edi, 1
  //test b
  sub ebx, 1
  jnc @loop
  add ebp, ebx
  jge @loop

  //test d
  xor eax, eax
  xor esi, edx
  xor edi, ecx
  xor esi, 1
  or esi, edi
  setz al
  jmp @done
@false:
  xor eax, eax
@done:
  pop edi
  pop esi
  pop ebp
  pop ebx
  end;

...
Рейтинг: 0 / 0
08.06.2018, 15:15
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658452
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Leonid KudryavtsevДело не в регистре, важно что с этим регистром происходило до этого.

Вы оказались абсолютно правы. Поигрался с "кадровыми перестановками" и выяснил: "долго" сравниваются cmp регистры, участвовавшие в shrd и shr, а "быстро" - участвовавшие только в add / adc.
...
Рейтинг: 0 / 0
08.06.2018, 15:33
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658462
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovА нету как такового вариант автора.

Есть вариант С++ без ассемблера на i3-2120 @3.3 ГГц.

Одиночный вызов f(4294967337, 8589934591) - 19..20 секунд.
Вышеописанный цикл из 254 шагов - 800..845 секунд.
...
Рейтинг: 0 / 0
08.06.2018, 15:47
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658493
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Aleksandr SharahovА нету как такового вариант автора.

Есть вариант С++ без ассемблера на i3-2120 @3.3 ГГц.

Одиночный вызов f(4294967337, 8589934591) - 19..20 секунд.
Вышеописанный цикл из 254 шагов - 800..845 секунд.

хотелось бы наконец увидеть ассемблерный листинг этого варианта С++ без ассемблера
...
Рейтинг: 0 / 0
08.06.2018, 16:37
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658499
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
AR®SiemarglВремя на прогон от 4294967297 до 4294967550 169сек
Это была реклама китайского i7-3770@4GHz
И получено 20 раз f()=1 ?да. и тесты с примерами ранее тоже прошли.
...
Рейтинг: 0 / 0
08.06.2018, 16:49
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658507
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Так был же: 21476315
...
Рейтинг: 0 / 0
08.06.2018, 16:57
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658509
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®,

если нетрудно, чтобы просто скопипастиь *всю* функцию от пушей до попов с ретами
...
Рейтинг: 0 / 0
08.06.2018, 17:04
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658523
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr SharahovAR®пропущено...


Есть вариант С++ без ассемблера на i3-2120 @3.3 ГГц.

Одиночный вызов f(4294967337, 8589934591) - 19..20 секунд.
Вышеописанный цикл из 254 шагов - 800..845 секунд.

хотелось бы наконец увидеть ассемблерный листинг этого варианта С++ без ассемблера
Я тоже голосую за C++.

Ассемблер заводит нас в дебри.
...
Рейтинг: 0 / 0
08.06.2018, 17:33
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658524
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®Так был же: 21476315
Ну ок. Давайте все брать его за эталон сравнения.
...
Рейтинг: 0 / 0
08.06.2018, 17:36
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658562
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonAleksandr Sharahov

хотелось бы наконец увидеть ассемблерный листинг этого варианта С++ без ассемблера
Я тоже голосую за C++.

Ассемблер заводит нас в дебри.

Никто и не против C++.
Просто покажите ассемблерный код функции.
А в Африку гулять пойдут только желающие.
...
Рейтинг: 0 / 0
08.06.2018, 18:52
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658584
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®,

это что, часть функции вычисления дискретного логарифма?
...
Рейтинг: 0 / 0
08.06.2018, 19:40
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658605
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
kealon(Ruslan)AR®, это что, часть функции вычисления дискретного логарифма?

Нет.
...
Рейтинг: 0 / 0
08.06.2018, 21:19
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658607
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovА в Африку гулять пойдут только желающие.
Тут надо бы решить, стоит ли туда, так сказать, идти. ) Пока я всё больше склоняюсь к мысли, что не стоит.
...
Рейтинг: 0 / 0
08.06.2018, 21:22
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658608
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovAR®, если нетрудно, чтобы просто скопипастиь *всю* функцию от пушей до попов с ретами

Завтра постараюсь.
...
Рейтинг: 0 / 0
08.06.2018, 21:23
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658624
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
SiemarglAR®пропущено...

И получено 20 раз f()=1 ?да. и тесты с примерами ранее тоже прошли.
>mmx64ompivy
....................result == 1 counter is 20
Time = 627404437 - 627586359
Time = 181922
каждая точка это единичка. добавил счетчик и синхронных вывод - результат чуть ухудшился
...
Рейтинг: 0 / 0
08.06.2018, 22:29
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658674
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Вы тут ассемблером балуетесь... А компилятор например не забывает перед началом цикла воткнуть .align 16
...
Рейтинг: 0 / 0
09.06.2018, 07:46
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658675
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
результат компиляции clang (в AT&T формате):
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
	.section	_TEXT,"xr"
	.globl	_f
	.align	16, 0x90
_f:                                     # @f
# BB#0:
	pushl	%ebp
	pushl	%ebx
	pushl	%edi
	pushl	%esi
	xorl	%esi, %esi
	movl	$1, %ebx
	movl	32(%esp), %ecx
	movl	28(%esp), %eax
	.align	16, 0x90
LBB0_1:                                 # =>This Inner Loop Header: Depth=1
	movl	%ebx, %edx
	andl	$1, %edx
	movl	$0, %edi
	cmovnel	24(%esp), %edi
	movl	%esi, %ebp
	sarl	%ebp
	xorl	%edi, %ebp
	testb	%dl, %dl
	movl	$0, %edx
	cmovnel	20(%esp), %edx
	shldl	$31, %ebx, %esi
	xorl	%edx, %esi
	movl	%esi, %edx
	xorl	$1, %edx
	addl	$-1, %eax
	adcl	$-1, %ecx
	orl	%ebp, %edx
	je	LBB0_3
# BB#2:                                 #   in Loop: Header=BB0_1 Depth=1
	movl	%eax, %edi
	orl	%ecx, %edi
	movl	%esi, %ebx
	movl	%ebp, %esi
	jne	LBB0_1
LBB0_3:                                 # %.critedge
	orl	%ecx, %eax
	orl	%eax, %edx
	sete	%al
	movzbl	%al, %eax
	popl	%esi
	popl	%edi
	popl	%ebx
	popl	%ebp
	ret

Ну или так (дисассемблер в intel формат, с ручной вставкой .align вместо nop)
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
	
        public  _f
DGROUP  group   _DATA,_BSS

_TEXT   segment
        assume  CS:_TEXT
                .align 16
_f:
                push    EBP
                push    EBX
                push    EDI
                push    ESI
                xor     ESI,ESI
                mov     EBX,1
                mov     ECX,020h[ESP]
                mov     EAX,01Ch[ESP]
                .align 16
L20:            mov     EDX,EBX
                and     EDX,1
                mov     EDI,0
                cmovnz  EDI,018h[ESP]
                mov     EBP,ESI
                sar     EBP,1
                xor     EBP,EDI
                test    DL,DL
                mov     EDX,0
                cmovnz  EDX,014h[ESP]
                shld    ESI,EBX,01Fh
                xor     ESI,EDX
                mov     EDX,ESI
                xor     EDX,1
                add     EAX,0FFFFFFFFh
                adc     ECX,0FFFFFFFFh
                or      EDX,EBP
                je      L60
                mov     EDI,EAX
                or      EDI,ECX
                mov     EBX,ESI
                mov     ESI,EBP
                jne     L20
L60:            or      EAX,ECX
                or      EDX,EAX
                setz    AL
                movzx   EAX,AL
                pop     ESI
                pop     EDI
                pop     EBX
                pop     EBP
                ret
_TEXT   ends
...
Рейтинг: 0 / 0
09.06.2018, 07:56
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658680
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
BarloneВы тут ассемблером балуетесь... А компилятор например не забывает перед началом цикла воткнуть .align 16
оно вроде как на современных процах не имеет значения
...
Рейтинг: 0 / 0
09.06.2018, 08:10
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658684
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
kealon(Ruslan)BarloneВы тут ассемблером балуетесь... А компилятор например не забывает перед началом цикла воткнуть .align 16
оно вроде как на современных процах не имеет значенияАвтору же надо на старых процессорах.
...
Рейтинг: 0 / 0
09.06.2018, 08:26
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658729
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
 
обещанный полный код f() от MS VC++ на аcсемблере
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
PUBLIC	?f@@YAH_K0@Z					; f
; Function compile flags: /Ogtp
;	COMDAT ?f@@YAH_K0@Z
_TEXT	SEGMENT
_c$ = -8						; size = 8
_a$ = 8							; size = 8
_b$ = 16						; size = 8
?f@@YAH_K0@Z PROC					; f, COMDAT

; 272  : {

	push	ebp
	mov	ebp, esp
	sub	esp, 8

; 273  : 	__int64 c = 0;

	xor	edx, edx
	push	esi
	push	edi
	mov	DWORD PTR _c$[ebp+4], edx

; 274  : 	__int64 d = 1;

	mov	eax, 1
	xor	ecx, ecx
$LN4@f:

; 275  : 
; 276  : 	do
; 277  : 	{
; 278  : 		__int64 e = -(d & 1);

	mov	esi, eax
	and	esi, 1
	xor	edi, edi

; 279  : 		d >>= 1;
; 280  : 		d ^= e & a;

	neg	esi
	adc	edi, edi
	and	esi, DWORD PTR _a$[ebp]
	shrd	eax, ecx, 1
	neg	edi
	and	edi, DWORD PTR _a$[ebp+4]
	sar	ecx, 1
	xor	eax, esi

; 281  : 		c++;

	mov	esi, DWORD PTR _c$[ebp+4]
	xor	ecx, edi
	add	edx, 1
	adc	esi, 0
	mov	DWORD PTR _c$[ebp+4], esi

; 282  : 	}
; 283  : 	while (d != 1 && c != b);

	cmp	eax, 1
	jne	SHORT $LN11@f
	test	ecx, ecx
	je	SHORT $LN10@f
$LN11@f:
	cmp	edx, DWORD PTR _b$[ebp]
	jne	SHORT $LN4@f
	cmp	esi, DWORD PTR _b$[ebp+4]
	jne	SHORT $LN4@f
$LN7@f:

; 284  :                                                         
; 285  : 	return (d == 1 && c == b) ? 1 : 0;	// если выполнились одновременно оба условия, достаточных для выхода из цикла, возвращаем 1, иначе 0

	xor	eax, eax

; 286  : }

	pop	edi
	pop	esi
	mov	esp, ebp
	pop	ebp
	ret	0
$LN10@f:

; 284  :                                                         
; 285  : 	return (d == 1 && c == b) ? 1 : 0;	// если выполнились одновременно оба условия, достаточных для выхода из цикла, возвращаем 1, иначе 0

	cmp	edx, DWORD PTR _b$[ebp]
	jne	SHORT $LN7@f
	cmp	esi, DWORD PTR _b$[ebp+4]
	jne	SHORT $LN7@f

; 286  : }

	pop	edi
	mov	eax, 1
	pop	esi
	mov	esp, ebp
	pop	ebp
	ret	0
?f@@YAH_K0@Z ENDP					; f


...
Рейтинг: 0 / 0
09.06.2018, 10:02
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658759
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Моя последняя ассемблерная версия. Увы, 44 секунды ((

[SPOILER версия с ассемблерной вставкой]
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
unsigned __int32 fa(unsigned __int64 _a, unsigned __int64 _b)
{
	unsigned __int32 a_H	= _a >> 32;
	unsigned __int32 a_L	= _a & 0xFFFFFFFF;
	unsigned __int32 b_H	= _b >> 32;
	unsigned __int32 b_L	= _b & 0xFFFFFFFF;

	unsigned __int32 _ret	= 0;
	unsigned __int32 d_H, d_L, c_H, c_L;
	
	__asm
	{	
		mov		edx, 0		// <edx:ecx> = d, начальное состояние = 000..01
		mov		ecx, 1
		xor		ebx, ebx	// <ebx:eax> = c, начальное состояние = 000..00
		xor		eax, eax

loopstart:
		xor		esi, esi	// <esi:edi> - будет заполняться в ходе работы либо 000..00, либо a
		xor		edi, edi

		shrd	ecx, edx, 1	// сдвиг младшей половины d
		cmovc	esi, a_H	// если был перенос в shrd, кладём a_H
		cmovc	edi, a_L	// если был перенос в shrd, кладём a_L
		shr		edx, 1		// сдвиг старшей половины d
		xor		edx, esi	// xor d либо с 000..00, либо с a
		xor		ecx, edi

		add		eax, 1		// инкремент c
		adc		ebx, 0

test_d:						// метка не используется
		cmp		edx, 0		// проверка d == 1
		jne	test_c
		cmp		ecx, 1
		jne	test_c
		jmp	loopout

test_c:						// проверка c == b
		cmp		ebx, b_H
		jne	loopstart
		cmp		eax, b_L
		jne	loopstart

loopout:
		cmp		edx, 0
		jne asmout
		cmp		ecx, 1
		jne asmout
		cmp		ebx, b_H
		jne asmout
		cmp		eax, b_L
		jne asmout
		mov		_ret, 1		// если прошли все 4 проверки выше, заполняем _ret = 1 (при объявлении _ret = 0)

asmout:					
		mov		d_H,	edx	// сохраняем d для вывода в printf()...
		mov		d_L,	ecx
		mov		c_H,	ebx	// сохраняем c для вывода в printf()...
		mov		c_L,	eax
	}
	
	printf("\nasmout:	d_H = %u		d_L = %u			c_H = %u		c_L = %u	\n",	d_H, d_L, c_H, c_L);

	return _ret;
}


[/SPOILER ]
...
Рейтинг: 0 / 0
09.06.2018, 10:53
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658770
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Barlone, AR®,

спасибо за код.

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

Дальше можно пойти по пути использования свойств алгоритма,
например, учитывать четность параметра и/или 33-битность,
если, конечно, автор не заинтересован в реализации тупого перебора )
Кода уже понаписано немало, самое время прояснить цель.
...
Рейтинг: 0 / 0
09.06.2018, 11:00
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658771
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Самое интересное: если убрать в моей версии блок проверки d == 1, работает 13-14 секунд.
Именно эти проверки ломают intel'овский конвейер.
...
Рейтинг: 0 / 0
09.06.2018, 11:02
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658828
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Все ручные оптимизации - бесполезная трата времени.
Один исходник на чистом С, разные компиляторы:
msvc, 32bit - 41 sec
clang, 32bit - 18 sec
gcc, 64bit - 9.5 sec
...
Рейтинг: 0 / 0
09.06.2018, 13:08
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658835
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
еще
msvc 64bit - 18sec
gcc 32bit -27sec
...
Рейтинг: 0 / 0
09.06.2018, 13:15
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658844
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
КМК этот алгоритм балансирует на грани алгоритмизации и практики использования железа.
Алгоритмически например первый шаг расчета e=-(d & 1) определяет битовую маску. Которая
влияет на ход вычисления всего кода дальше. В некоторых высокоуровневых ЯП можно было-бы поставить if
который при прочих генерализовнных условиях мог-бы повлиять на сложность алгоритма.
Типа раньше выйти из цикла. Или что-то в этом роде. Но помня о штрафных санкциях за неверный
переход тут надо подумать. Для ассемблера возможно оно и лучше оперировать флажками
но сохранять непрерывный поток команд без веток. Тоесть это тот случай когда алгоритмист-теоретик
проиграет практикующему ассебмлерщику.

Тот-же 33й бит как-то связывает руки. Так можно было-бы попробовать развернуть 2 раунда
вычислений в 1 спаренный на ММХ 2 по 32. Вобщем злая постановка. Напоминает язык Malbolge,
который создан чтобы поиздеваться над мозгом. Или потренировать смекалку. Впрочем без особой
практической пользы для отрасли.

Чисто организационно я-бы развернул для себя do{}while в for{}. Просто так привычнее. Только надо учеть
1 безусловную итерацию перед входом в цикл. Но возможно для ассемблера с его пост-условными переходами назад
этот подход чуть-чуть отдаляет оригинальный код С++ от результирующего.
...
Рейтинг: 0 / 0
09.06.2018, 13:21
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658863
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
maytonАлгоритмически например первый шаг расчета e=-(d & 1) определяет битовую маску.
Заметьте, в моей последней асм-версии я от него избавился.

maytonТот-же 33й бит как-то связывает руки.
Увы. Для 32 бит всё уже успешно проделано. И 33-й - это только начало и почва для отладки.

Нет ли идей, что у меня ломает конвейер?
...
Рейтинг: 0 / 0
09.06.2018, 13:40
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658884
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Barlone,

clang понравился:
-без фрейма,
-догадался насчет декремента,
-заменил работу с маской -1 на условную пересылку,
-все сравнения or-ами.
...
Рейтинг: 0 / 0
09.06.2018, 14:14
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658888
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®...И 33-й - это только начало и почва для отладки...

Т.е. процедура должна работать и на 34 бита?
...
Рейтинг: 0 / 0
09.06.2018, 14:17
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658916
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®,

как то жёстко 21481207 , на i7 42 секунды по сравнению с 14.8 на плюсах
...
Рейтинг: 0 / 0
09.06.2018, 14:43
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658934
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovТ.е. процедура должна работать и на 34 бита?
И на 34, и на 35..64.
32-битная версия удовлетворительно работала на C#. Переход к 64-битной арифметике вынудил вспомнить про C и написание dll.
...
Рейтинг: 0 / 0
09.06.2018, 14:58
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658936
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
kealon(Ruslan)AR®, как то жёстко 21481207 , на i7 42 секунды по сравнению с 14.8 на плюсах

Закомментируйте часть с метки test_d: до метки test_c:, на Вашем i7 будет секунд 10-12.
...
Рейтинг: 0 / 0
09.06.2018, 15:00
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659057
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®,

попробуй вот этот вариант как

 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
__int32 fa(unsigned __int64 _a, unsigned __int64 _b)
{
	_b += 0xFFFFFFFF;
	unsigned __int32 a_H = _a >> 32;
	unsigned __int32 a_L = _a & 0xFFFFFFFF;
	unsigned __int32 b_H = _b >> 32;
	unsigned __int32 b_L = _b & 0xFFFFFFFF;

	unsigned __int32 _ret = 0;
	unsigned __int32 d_H, d_L, c_H, c_L;

	__asm
	{
		mov		ecx, 0		// <edx:ecx> = d, начальное состояние = 000..01
		mov		edx, 0
		mov		eax, b_L	// <ebx:eax> = c, начальное состояние = 000..00
		mov		ebx, b_H
.align 16
		loopstart :
			inc		ecx
			xor		esi, esi	// <esi:edi> - будет заполняться в ходе работы либо 000..00, либо a
			xor		edi, edi

			shrd	ecx, edx, 1	// сдвиг младшей половины d
			cmovc	esi, a_H	// если был перенос в shrd, кладём a_H
			cmovc	edi, a_L	// если был перенос в shrd, кладём a_L
			shr		edx, 1		// сдвиг старшей половины d
			xor		edx, esi	// xor d либо с 000..00, либо с a
			xor		ecx, edi

			sub		eax, 1  		// декремент c
			sbb 	ebx, 0
			jz		loopout      
		test_d :						// метка не используется // проверка d == 1
			dec		ecx
			jnz		loopstart
			test	edx, edx
			jnz		loopstart
			inc		ecx
			jmp		asmout

		loopout :
			test	edx, edx
			jne		asmout
			cmp		ecx, 1
			jne		asmout
			mov		_ret, 1		// если прошли все 4 проверки выше, заполняем _ret = 1 (при объявлении _ret = 0)

		asmout:
			mov		d_H, edx	// сохраняем d для вывода в printf()...
			mov		d_L, ecx

			sub		eax, 0xFFFFFFFF
			sbb 	ebx, 0
			mov		c_H, ebx	// сохраняем c для вывода в printf()...
			mov		c_L, eax
	}
	_b -= 0xFFFFFFFF;
	printf("\nasmout:	d_H = %u		d_L = %u			c_H = %u		c_L = %u	\n", d_H, d_L, c_H, c_L);

	return _ret;
}

...
Рейтинг: 0 / 0
09.06.2018, 18:40
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659085
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
kealon(Ruslan)AR®, попробуй вот этот вариант

Попробовал, но только, к сожалению, на другом компе: С++ - 30 сек., мой асм - 80 сек., Ваш - 53 сек.
...
Рейтинг: 0 / 0
09.06.2018, 19:51
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659155
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®,

нет в мире таких крепостей, которые не взять за 529 секунд на i7-7700, используя Delphi+BASM
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
//Aleksandr Sharahov 2018
function IsMaxLFSR(Feedback, MaxPeriod: pint64): boolean;
asm
  push ebp
  push ebx
  push esi

  mov ebx, dword ptr [edx]     //period
  mov ebp, dword ptr [edx+4]   //period

  mov ecx, dword ptr [eax]     //reverse feedback bits
  rol ecx, 16
  mov edx, ecx
  and edx, $FF00FF00
  xor ecx, edx
  shl ecx, 8
  shr edx, 8
  or  ecx, edx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  mov ecx, dword ptr [eax+4]   //reverse feedback bits
  rol ecx, 16
  mov edx, ecx
  and edx, $FF00FF00
  xor ecx, edx
  shl ecx, 8
  shr edx, 8
  or  ecx, edx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  xor esi, esi                 //initial state
  mov eax, $80000000           //initial state

@loop:
  sub ebx, 1                   //decrement period
  sbb ebp, 0                   //decrement period
  cdq                          //output bit to mask
  mov ecx, edx                 //output bit to mask
  add esi, esi                 //shift
  adc eax, eax                 //shift
  and ecx, dword ptr[esp]      //feedback
  and edx, dword ptr[esp+4]    //feedback
  xor esi, ecx                 //new state
  xor eax, edx                 //new state
  mov edx, eax                 //is equal
  xor edx, $80000000           //to
  or  edx, esi                 //initial state?
  jnz @loop
  or  ebx, ebp                 //is period maximal?
  setz al
  movzx eax, al
  add esp, 8
  pop esi
  pop ebx
  pop ebp
  end;

...
Рейтинг: 0 / 0
10.06.2018, 00:43
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659168
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
чего то пока далековато до моих 160-180с, которые достигаются одной строчкой =)
...
Рейтинг: 0 / 0
10.06.2018, 02:31
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659176
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
то ли еще будет )
...
Рейтинг: 0 / 0
10.06.2018, 07:26
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659197
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Сравнение состояния по частям дает 470.5 sec на i7-7700
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
//Aleksandr Sharahov 2018
function IsMaxLFSR3(Feedback, MaxPeriod: pint64): boolean;
asm
  push ebp
  push ebx
  push esi

  mov ebx, dword ptr [edx]     //period
  mov ebp, dword ptr [edx+4]   //period

  mov ecx, dword ptr [eax]     //reverse feedback bits
  rol ecx, 16
  mov edx, ecx
  and edx, $FF00FF00
  xor ecx, edx
  shl ecx, 8
  shr edx, 8
  or  ecx, edx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  mov ecx, dword ptr [eax+4]   //reverse feedback bits
  rol ecx, 16
  mov edx, ecx
  and edx, $FF00FF00
  xor ecx, edx
  shl ecx, 8
  shr edx, 8
  or  ecx, edx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  xor esi, esi                 //initial state
  mov eax, $80000000           //initial state

@loop:
  sub ebx, 1                   //decrement period
  sbb ebp, 0                   //decrement period
  cdq                          //output bit to mask
  mov ecx, edx                 //output bit to mask
  add esi, esi                 //shift
  adc eax, eax                 //shift
  and ecx, dword ptr[esp]      //feedback
  and edx, dword ptr[esp+4]    //feedback
  xor esi, ecx                 //new state
  xor eax, edx                 //new state
  cmp eax, $80000000           //is equal to
  jne @loop
  test esi, esi                //initial state?
  jnz @loop
  or  ebx, ebp                 //is period maximal?
  setz al
  movzx eax, al
  add esp, 8

  pop esi
  pop ebx
  pop ebp
  end;

...
Рейтинг: 0 / 0
10.06.2018, 10:42
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659199
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
529 с, 160-180 с - в обоих случаях речь идёт про тест, где 254 числа и из них 20 f()==1 ?
...
Рейтинг: 0 / 0
10.06.2018, 10:49
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659214
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr Sharahovто ли еще будет )
А Делфи позволяют посмотреть, во что ассемблерное превратил компилятор ассемблер в исходнике? В MS VC бывают незначительные отличия типа je вместо jz и т.п.
...
Рейтинг: 0 / 0
10.06.2018, 11:49
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659222
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
AR®je вместо jz
Это разные мнемоники одной и той же машиной команды
...
Рейтинг: 0 / 0
10.06.2018, 12:06
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659227
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®529 с, 160-180 с - в обоих случаях речь идёт про тест, где 254 числа и из них 20 f()==1 ?

У меня все по-честному, без параллелей.

Кстати простыню можно немного сократить.
И второй цикл лучше выравнивать, если компилятор позволяет, - будет еще быстрее (477 сек).
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
//Aleksandr Sharahov 2018
function IsMaxLFSR4(Feedback, MaxPeriod: pint64): boolean;
asm
  push ebp
  push ebx
  push esi

  mov ebx, dword ptr [edx]     //period
  mov ebp, dword ptr [edx+4]   //period

  xor esi, esi
@reverse:
  mov ecx, dword ptr [eax+esi] //reverse feedback bits
  bswap ecx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  test esi, esi
  lea esi, [esi+4]
  jz @reverse

  xor esi, esi                 //initial state
  mov eax, $80000000           //initial state
  cdq                          //output bit to mask
  mov ecx, edx                 //output bit to mask

@loop:
  add esi, esi                 //shift
  adc eax, eax                 //shift
  and edx, dword ptr[esp+4]    //feedback
  and ecx, dword ptr[esp]      //feedback
  add ebx, -1                  //decrement period
  adc ebp, -1                  //decrement period
  xor eax, edx                 //new state
  xor esi, ecx                 //new state
  cdq                          //output bit to mask
  mov ecx, edx                 //output bit to mask
  cmp eax, $80000000           //is equal to
  jne @loop
  test esi, esi                //initial state?
  jnz @loop

  or  ebx, ebp                 //is period maximal?
  setz al
  movzx eax, al
  add esp, 8
  pop esi
  pop ebx
  pop ebp
  end;

...
Рейтинг: 0 / 0
10.06.2018, 12:38
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659229
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov,

опечатка: не 477, а 447 сек
...
Рейтинг: 0 / 0
10.06.2018, 12:46
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659318
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr Sharahov

Хотел потестить Ваши примеры, но, похоже, в C++ нельзя использовать ebp для собственных нужд. Компилируется с warning'ами, а при запуске падает на первом mov ebp.

Есть более фундаментальный вопрос: откуда уверенность, что initial state обязательно повторится? У Вас его повторение является единственным условием выхода из цикла, а в исходном алгоритме ещё и достижение предела счётчиком цикла.
Возможно, повторение initial state неизбежно, но я не знаю, так ли это. Вы, возможно знаете теорию.
...
Рейтинг: 0 / 0
10.06.2018, 19:45
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659324
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Хотел потестить Ваши примеры, но, похоже, в C++ нельзя использовать ebp для собственных нужд. Компилируется с warning'ами, а при запуске падает на первом mov ebp.

В последних функциях регистр edi не используется. Замените.

AR®Есть более фундаментальный вопрос: откуда уверенность, что initial state обязательно повторится? У Вас его повторение является единственным условием выхода из цикла, а в исходном алгоритме ещё и достижение предела счётчиком цикла.
Возможно, повторение initial state неизбежно, но я не знаю, так ли это. Вы, возможно знаете теорию.
Вы бы не задавали этот вопрос, если бы грызли гранит до основания, а не чисто периодически )
Но, как мы помним, эту "Задачу должен решить я" (с).
...
Рейтинг: 0 / 0
10.06.2018, 20:42
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659325
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®Увы. Для 32 бит всё уже успешно проделано. И 33-й - это только начало и почва для отладки.

Нет ли идей, что у меня ломает конвейер?
Идей нет. Конвейер команд ломают условные переходы. Но в нашем случае 99% переходов - назад.
Как определить состояние конвейера в нашем случае - ХЗ. У меня нет мыслей. Самое правильное - это
воспользоваться утилитой тонкого тюнинга Intel Vtune и посмотреть ее отчоты.

Я по ссылкам от этого топика пошёл читать про PAPI. Не думаю что выйду с предложением. Тут Шарахов
тебе хорошо помогает. А я уже свои мысли сказал. Если-б я делал эту функцию - то использовал-бы
мемоизацию.
...
Рейтинг: 0 / 0
10.06.2018, 20:52
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659331
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovВы бы не задавали этот вопрос, если бы грызли гранит до основания, а не чисто периодически )
Э-э, я-то делаю это скорее даже а периодически. ))

Aleksandr SharahovНо, как мы помним, эту "Задачу должен решить я" (с).
И решу, не сумневайтесь. )
...
Рейтинг: 0 / 0
10.06.2018, 21:14
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659344
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Aleksandr SharahovВы бы не задавали этот вопрос, если бы грызли гранит до основания, а не чисто периодически )
Э-э, я-то делаю это скорее даже а периодически. ))

Главное, все читать внимательно, чтоб случайно не пропустить идею какую или подсказку )


AR®Aleksandr SharahovНо, как мы помним, эту "Задачу должен решить я" (с).
И решу, не сумневайтесь. )
Подкину еще дровишек (191 сек на i7-7700). Решать - не перерешать )
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
type
  i64= array[0..1] of cardinal;
  ca= ^i64;
const
  RunCount= 8*1024; // = 2^N, N>=3
var
  XorTable: array[0..255] of int64;
  RunTable: array[0..RunCount-1] of int64;
  RunOver: array[0..RunCount-1] of integer;

procedure FillXorTable(Feedback: pint64);
var
  i, Run: integer;
  x: int64;
  IsOdd: boolean;
begin;
  for i:=0 to 255 do begin;
    x:=i;
    for Run:=1 to 8 do begin;
      IsOdd:=x and 1<>0;
      x:=x shr 1;
      if IsOdd then x:=x xor Feedback^;
      end;
    XorTable[i]:=x;
    end;
  end;

procedure FillRunTable(Feedback: pint64);
var
  Run: integer;
  x: int64;
  IsOdd: boolean;
begin;
  x:=1;
  RunTable[0]:=x;
  RunOver[0]:=0;
  for Run:=1 to RunCount-1 do begin;
    IsOdd:=x and 1<>0;
    x:=x shr 1;
    if IsOdd then x:=x xor Feedback^;
    RunTable[Run]:=x;
    RunOver[Run]:=Run;
    end;
  end;

procedure SortRunTable;
var
  i, j, t: integer;
  x: int64;
begin;
  i:=0;
  j:=RunCount-1;
  while j>0 do begin;
    if ca(@RunTable[j])[0]<ca(@RunTable[i])[0] then i:=j;
    dec(j);
    end;
  if i>0 then begin;
    x:=RunTable[0]; RunTable[0]:=RunTable[i]; RunTable[i]:=x;
    t:=RunOver[0]; RunOver[0]:=RunOver[i]; RunOver[i]:=t;
    end;

  j:=1;
  while true do begin;
    if j>=RunCount-1 then break;
    inc(j);
    if ca(@RunTable[j])[0]<ca(@RunTable[j-1])[0] then begin;
      x:=RunTable[j];
      t:=RunOver[j];
      i:=j;
      repeat;
        RunTable[i]:=RunTable[i-1];
        RunOver[i]:=RunOver[i-1];
        dec(i);
        until not (ca(@x)[0]<ca(@RunTable[i-1])[0]);
      RunTable[i]:=x;
      RunOver[i]:=t;
      end;
    end;
  end;

function FindRunOver(p: pint64): integer;
var
  Left, Right: integer;
begin;
  Left:=0;
  Right:=RunCount;              //index of the element greater than p^
  while Left<Right do begin;
    Result:=(Left+Right) shr 1; //round to left
    if ca(p)[0]<ca(@RunTable[Result])[0] then Right:=Result else Left:=Result+1;
    end;
  dec(Right);
  while (Right>=0)
  and (ca(p)[0]=ca(@RunTable[Right])[0]) do begin;
    if ca(p)[1]=ca(@RunTable[Right])[1] then begin;
      Result:=RunOver[Right];
      exit;
      end;
    dec(Right);
    end;
  Result:=-1;
  end;

procedure RunLFSR(var x: int64);
var
  i, j: integer;
begin;
  j:=RunCount;
  repeat;
    i:=x and 255;
    x:=x shr 8 xor XorTable[i];
    j:=j-8;
    until j<=0;
  end;

//Aleksandr Sharahov 2018
function IsMaxLFSR5(Feedback, MaxPeriod: pint64): boolean;
var
  Count, State: int64;
  Over: integer;
begin;
  if (MaxPeriod^<MaxInt)
  or (MaxPeriod^ and (MaxPeriod^+1)<>0) then begin;
    Result:=false;
    exit;
    end;
  FillXorTable(Feedback);
  FillRunTable(Feedback);
  SortRunTable;
  Count:=0;
  State:=1;
  repeat;
    RunLFSR(State);
    Count:=Count+RunCount;
    Over:=FindRunOver(@State);
    until Over>=0;
  Result:=Count=MaxPeriod^+Over;
  end;



Написано неоптимально, просто демонстрация идеи.
Алгоритм каждой из процедур можно улучшить + использовать ассемблер.

Еще больше оптимизаций можно подсмотреть здесь:
http://guildalfa.ru/alsha/node/2
http://guildalfa.ru/alsha/node/4
http://guildalfa.ru/alsha/node/10
...
Рейтинг: 0 / 0
10.06.2018, 22:37
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659350
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®Aleksandr Sharahov

Хотел потестить Ваши примеры, но, похоже, в C++ нельзя использовать ebp для собственных нужд. Компилируется с warning'ами, а при запуске падает на первом mov ebp.

Есть более фундаментальный вопрос: откуда уверенность, что initial state обязательно повторится? У Вас его повторение является единственным условием выхода из цикла, а в исходном алгоритме ещё и достижение предела счётчиком цикла.
Возможно, повторение initial state неизбежно, но я не знаю, так ли это. Вы, возможно знаете теорию.
если грубо перевести
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
__int32 fSharahov(unsigned __int64 _a, unsigned __int64 _b)
{
	unsigned __int32 _ret = 0;
	_asm {
		push ebp
		push ebx
		push esi
		push edi

		lea eax, _a
		lea edx, _b

		//
		mov ebx, dword ptr[edx]     //period
		mov ebp, dword ptr[edx + 4]   //period

		xor esi, esi
	reverse:
		mov ecx, dword ptr[eax + esi] //reverse feedback bits
		bswap ecx
		mov edx, ecx
		and edx, 0xF0F0F0F0
		xor ecx, edx
		shl ecx, 4
		shr edx, 4
		or ecx, edx
		mov edx, ecx
		and edx, 0xCCCCCCCC
		xor ecx, edx
		shl ecx, 2
		shr edx, 2
		or ecx, edx
		mov edx, ecx
		and edx, 0xAAAAAAAA
		xor ecx, edx
		shl ecx, 1
		shr edx, 1
		or ecx, edx
		push ecx

		test esi, esi
		lea esi, [esi + 4]
		jz reverse

		xor esi, esi                 //initial state
		mov eax, 0x80000000           //initial state
		cdq                          //output bit to mask
		mov ecx, edx                 //output bit to mask
	loop_cicle:
		add esi, esi                 //shift
		adc eax, eax                 //shift
		and edx, dword ptr[esp+4]    //feedback
		and ecx, dword ptr[esp]      //feedback
		add ebx, -1                  //decrement period
		adc ebp, -1                  //decrement period
		xor eax, edx                 //new state
		xor esi, ecx                 //new state
		cdq                          //output bit to mask
		mov ecx, edx                 //output bit to mask
		cmp eax, 0x80000000           //is equal to
		jne loop_cicle
		test esi, esi                //initial state?
		jnz loop_cicle

		or ebx, ebp                 //is period maximal?
		setz al
		
		add esp, 8
		///
		pop edi
		pop esi
		pop ebx
		pop ebp
		movzx eax, al
		mov _ret, eax
	}
	return _ret;
}

...
Рейтинг: 0 / 0
10.06.2018, 23:34
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659355
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®,

вот только я что-то не вижу где у него счётчик проверяется, вижу что меняется, а что каждый раз проверяется - нет
...
Рейтинг: 0 / 0
11.06.2018, 00:03
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659358
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
kealon(Ruslan)AR®,

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

Именно. Не проверяется вовсе. Только 1 раз в конце при принятии решения о возвращаемом значении.
Выше было по этому поводу:

Aleksandr SharahovAR®Есть более фундаментальный вопрос: откуда уверенность, что initial state обязательно повторится? У Вас его повторение является единственным условием выхода из цикла, а в исходном алгоритме ещё и достижение предела счётчиком цикла.
Возможно, повторение initial state неизбежно, но я не знаю, так ли это. Вы, возможно знаете теорию.
Вы бы не задавали этот вопрос, если бы грызли гранит до основания, а не чисто периодически )
Но, как мы помним, эту "Задачу должен решить я" (с).
...
Рейтинг: 0 / 0
11.06.2018, 00:16
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659567
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®, как движется изучение?

Сейчас проверил, таблица на 2K значений, как в статье по CRC32,
позволяет прогнать длинный тест менее, чем за 66 сек.
Чистый паскаль, без других оптимизаций.
...
Рейтинг: 0 / 0
12.06.2018, 01:20
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659570
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovAR®, как движется изучение?

Без Вашей магии - никуда. ))
Подтверждаю пока лишь, что Ваши асм-версии (все) переиграли компилятор C++ на довольно старом компе с VS2008. Примерно 20 сек вместо 30 у C++ . Самые последние - 18-19 сек.
Откройте тайну: это достигнуто с использованием хвалёного интеловского тьюнера?
...
Рейтинг: 0 / 0
12.06.2018, 01:45
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659573
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Aleksandr SharahovAR®, как движется изучение?

Без Вашей магии - никуда. ))
Подтверждаю пока лишь, что Ваши асм-версии (все) переиграли компилятор C++ на довольно старом компе с VS2008. Примерно 20 сек вместо 30 у C++ . Самые последние - 18-19 сек.
Откройте тайну: это достигнуто с использованием хвалёного интеловского тьюнера?

Без. Хотя этим и заниматься не стоило, не знаю даже, почему задело.

Считая биты, очень трудно заметно ускорить функцию.
Нужны, как минимум, байты и более широкие типы.
Успехов.
...
Рейтинг: 0 / 0
12.06.2018, 02:04
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659609
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovБез.
Значит, интуиция и немалый опыт.

Aleksandr Sharahov Хотя этим и заниматься не стоило,
В моём случае стоило. К масштабной переделке всего и вся я пока не готов морально. ) Прирост в 30-40% меня бы устроил.

Aleksandr Sharahov не знаю даже, почему задело.

Потому что мой вариант 21481207 , например, с моей точки зрения безупречен (а с Вашей в нём есть лишняя проверка - счётчика цикла, не нужная в теории), но работает почему-то долго. ))
Косметика типа замены инкремента на декремент ничего не меняет. Отказаться от использования CMOV ? От SHRD ?
В общем, гадание на процессорной гуще, да и только. Ваши же примеры - чёрная асм-магия! )
...
Рейтинг: 0 / 0
12.06.2018, 10:17
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659613
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Прирост в 30-40% меня бы устроил.

Только до тех пор, пока вы ограничиваетесь 33 битами. Хотя, думаю, конкретно 33 бита можно ускорить чуть изменив 32-битную функцию. А пойдете дальше - и прирост уже не устроит. В то время как хорошая теория легко дает ускорение на 1.5 порядка. С ассемблером, наверно, можно и чуть больше отжать. А очень хорошая теория может вообще сделать все эти пляски ненужными. В зависимости от решаемой задачи.

Так выпьем же за кибернетике!
...
Рейтинг: 0 / 0
12.06.2018, 10:33
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659813
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovТак выпьем же за кибернетику!
И за математику!

CMOV - это красивый, но ложный след. ))
...
Рейтинг: 0 / 0
12.06.2018, 18:31
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39662539
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr Sharahov 21484030
Подкину еще дровишек (191 сек на i7-7700). Решать - не перерешать )


Честно говоря, не понял идею.
Ещё не понял в Вашем примере, что означает ca(...) - приведение к типу ca?
...
Рейтинг: 0 / 0
19.06.2018, 15:48
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39662633
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Aleksandr Sharahov 21484030 Подкину еще дровишек (191 сек на i7-7700). Решать - не перерешать )
Честно говоря, не понял идею.
Идея простая:
1. Вы запрограммировали работу регистра сдвига с линейной обратной связью (LFSR) в конфигурации Галуа.
2. Последовательность состояний LFSR - чисто периодическая с максимальным периодом 2^N-1.
Длина периода зависит от значения обратной связи.
3. Ваша функция определяет, дает ли указанная обратная связь максимальный период.
4. Обратная связь на K следующих тактах работы LFSR (у меня K=8) полностью определяется
последними К битами текущего состояния LFSR и может быть сохранена в XOR-таблице размером 2^K.
Т.о. вместо прогона K тактов LFSR достаточно выполнить XOR элемента таблицы со сдвинутым состоянием.
Понятно, что хотелось бы прогонять достаточно большое количество тактов за один вызов процедуры.
Понятно также, что в любом случае мы проскочим за повтор начального состояния.
4. Т.к. начальное состояние и непосредственно следующие за ним состояния в точности повторятся
после прогона полного периода LFSR, то их можно хранить в RUN-таблице и использовать для определения повтора.



AR®Ещё не понял в Вашем примере, что означает ca(...) - приведение к типу ca?
ca - это массив переменных типа DWORD, расположенных по указанному адресу (у меня по адресу переменной типа int64).

Т.о. ca(@x)[0] - это младшие 32 бита переменной x,
а ca(@x)[1] - старшие 32 бита переменной x.
...
Рейтинг: 0 / 0
19.06.2018, 18:33
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39662718
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovВы запрограммировали работу...

Честно говоря, чувствую себя немного О.Бендером в роли шахматного гроссмейстера (который не знал, что играет вполне известные специалистам партии, и что они даже имеют названия).

Независимо от этого, благодарю. Предлагаю участнику mayton отправить ранее обещанный мне коньяк Вам. ) При случае могу быть третьим, но совсем не фанат этого дела. )
Жаль, времени особо нет на эксперименты.
...
Рейтинг: 0 / 0
19.06.2018, 22:03
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39662721
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
P.S. Ваша асм-версия с "зеркальным" отражением и сдвигом влево через сложение (вместо сдвига вправо) работает.
...
Рейтинг: 0 / 0
19.06.2018, 22:06
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39662722
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®Независимо от этого, благодарю. Предлагаю участнику mayton отправить ранее обещанный мне коньяк Вам. ) При случае могу быть третьим, но совсем не фанат этого дела. )
Жаль, времени особо нет на эксперименты.
Шарахов - молодец. Но коньяк я ему не отправлю. У меня договорённость была только с вами.
А я - чту договорённости. Могу выслать вам а вы уж сами решайте с кем пить и где.
...
Рейтинг: 0 / 0
19.06.2018, 22:06
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39662738
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®, mayton,

да ладно вам, забудьте )
...
Рейтинг: 0 / 0
19.06.2018, 23:55
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39662855
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Aleksandr Sharahov1. Вы запрограммировали работу регистра сдвига с линейной обратной связью (LFSR) в конфигурации Галуа. А, ну вот, мне не зря показалось, что где-то я это уже видел.
Там же есть известные необходимые условия для максимального периода. Для теста "все числа от ... до ..." можно будет как минимум половину сразу выкинуть (с нечетным числом единичных битов).
...
Рейтинг: 0 / 0
20.06.2018, 09:35
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39662925
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Barloneвыкинуть (с нечетным числом единичных битов).

Это сделано у меня в основной программе.
LFSR, Галуа, Фибоначчи - лишь терминология.
...
Рейтинг: 0 / 0
20.06.2018, 11:34
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39663126
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
теория
...
Рейтинг: 0 / 0
20.06.2018, 15:35
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39663643
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Barlone теория
Ой, как много там теории... ) И автор употребляет какую-то специфичную символику, портящую зрение.
Раз уж с подачи Шарахова мы ввели в оборот понятие LFSR, можно для начала прочесть: https://web.archive.org/web/20060315203220/http://www.yikes.com/~ptolemy/lfsr_web/index.htm

От себя добавлю лишь, что "Type 1 or External LFSRs" - это конфигурация Фибоначчи, а "Type 2 or Internal LFSRs" - это конфигурация Галуа.
...
Рейтинг: 0 / 0
21.06.2018, 14:04
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39663680
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
AR®Barlone теория
Ой, как много там теории... ) И автор употребляет какую-то специфичную символику, портящую зрение.
Раз уж с подачи Шарахова мы ввели в оборот понятие LFSR, можно для начала прочесть: https://web.archive.org/web/20060315203220/http://www.yikes.com/~ptolemy/lfsr_web/index.htm

От себя добавлю лишь, что "Type 1 or External LFSRs" - это конфигурация Фибоначчи, а "Type 2 or Internal LFSRs" - это конфигурация Галуа.Ну да, много. Только там помимо теории есть еще программка с исходниками, которая находит неприводимые полиномы за меньше чем одну секунду (и не для 33, а для 62 степени). Aleksandr Sharahov А очень хорошая теория может вообще сделать все эти пляски ненужными.
...
Рейтинг: 0 / 0
21.06.2018, 15:44
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39663809
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
BarloneТолько там помимо теории есть еще программка с исходниками, которая находит неприводимые полиномы за меньше чем одну секунду (и не для 33, а для 62 степени).

Видел. Только она решает немного не мою задачу. Насколько я понял, она ищет "какой-нибудь", т.е. первый подходящий многочлен для заданных степени и модуля. Мне же интересно быстро проверить любую в пределах заданной степени конфигурацию на предмет того, порождает ли такой LFSR m-последовательность.
Хотя стоит, безусловно, посмотреть, что и как там сделано.
...
Рейтинг: 0 / 0
21.06.2018, 20:30
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39663810
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Хотя там и сказано You can also test a given polynomial for primitivity and find all primitive polynomials. , но про время выполнения этой задачи там ничего нет.
...
Рейтинг: 0 / 0
21.06.2018, 20:35
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39664136
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
AR®Хотя там и сказано You can also test a given polynomial for primitivity and find all primitive polynomials. , но про время выполнения этой задачи там ничего нет.Такое же время - миллисекунды. Там еще можно получить все примитивные полиномы, но вот это уже будет дольше - их же много.
...
Рейтинг: 0 / 0
22.06.2018, 12:28
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39664162
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
BarloneТакое же время - миллисекунды.
Проверяли сами?

BarloneТам еще можно получить все примитивные полиномы, но вот это уже будет дольше - их же много.
Для 33 бит, по моим скромным познаниям, 211016256.

Смущает, что автор программы использует некие готовые таблицы, полученные от кого-то.
Я тоже могу взять таблицы всех LFSR'ов (их есть у меня от 3 до 32 бит включительно), и вся работа сведётся к работе с БД. :)
Но будет ли это решением задачи?
...
Рейтинг: 0 / 0
22.06.2018, 12:53
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39664207
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Уточнение: 211016256 - это по модулю 2.
...
Рейтинг: 0 / 0
22.06.2018, 13:35
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39664219
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
AR®BarloneТакое же время - миллисекунды.
Проверяли сами?

BarloneТам еще можно получить все примитивные полиномы, но вот это уже будет дольше - их же много.
Для 33 бит, по моим скромным познаниям, 211016256.

Смущает, что автор программы использует некие готовые таблицы, полученные от кого-то.
Я тоже могу взять таблицы всех LFSR'ов (их есть у меня от 3 до 32 бит включительно), и вся работа сведётся к работе с БД. :)
Но будет ли это решением задачи?Проверял. И там алгоритм так построен - генерируем полином, проверяем его на примитивность.
...
Рейтинг: 0 / 0
22.06.2018, 13:54
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39664231
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
А из "готовых таблиц" там только таблицы разложения на множители чисел p^n-1. Для вашего случая p=2 и n<=64 таблица будет совсем маленькой.
...
Рейтинг: 0 / 0
22.06.2018, 14:04
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39664295
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Barlone там только таблицы разложения на множители чисел p^n-1

Факторизация - не проблема. См. тему Простые числа простыми средствами
...
Рейтинг: 0 / 0
22.06.2018, 15:14
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39666734
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."

John von Neumann, 1951.
...
Рейтинг: 0 / 0
27.06.2018, 17:27
| Ответить | Цитировать | Написать  
225 сообщений из 225, показаны все 9 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ассемблер - регистры MMX - команды условного перехода.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]