Мелкие задачки для крупных мозгов №24

Quantum

> "Фог считает иначе"

Это он тебе в приватной беседе сообщил ? ))

Насчет спариваемости на P\PMMX это да. Но насчет собственной латентности - в pentopt.pdf во всех табличках латентности rol r,1 и rol r,i и shr\shl совершенно одинаковые. В IA-32 Optimization тоже одинаковые (примечание стоит только в отношении rcl,rcr). А в мануалах AMD вообще особое примечание: "regardless of the number of shifts or rotates as determined by CL or imm8."

PS: вопрос конечно спорный, поэтому я не настаиваю, а лишь делаю примечание, что утверждение о преимуществе shl\shr перед ror\rol не вполне обоснованно

 

asd вариант не катит, без деления на 400 можно и обойтись (400, в отличие от 100 - без остатка делится на 16, т.е. достаточно проверить младшие 4 бита), а вот как обойтись без деления на 100 ...

 

leo

Да, за кружкой пива

Да, они просто не укзаны для PPro - P3. Зато у rol/ror на один uop в ALU больше. А в таблице для P4 тайминг тоже одинаковый, но для ror/rol указана зависимость от флагов. Поэтому в любом случае ror/rol тормознее shr/shl, хоть на самую малость.

Но и на AMD ror/rol не будет быстрее, т.к. это не логично. Я знаю только 2 способа организовать ror/rol в кремнии и оба сложнее обычного сдвига.

 

Quantum

Ну ты меня удивляешь, видимо тебе Фог за кружкой пива какой-то экслюзивный вариант своего труда подарил

У меня и в старом и в новом вариантах для PPro-P3 черным по белому в одну строчку (с переходом на вторую из-за нехватки места) написано "SHL SHR SAR ROR ROL r,i/C 1", т.е. для всех одна микрооперация в port0.

Рассуждения типа "тормознее .. хоть на самую малость" и "это не логично" еще более удивительны, т.к. речь идет о ТАКТАХ - да пусть хоть в 10 раз быстрее, все что укладывается в один такт иммеет латентность 1 такт - исполнение следующей зависимой инструкции раньше чем в начале следующего такта (в P4 полутакта) начаться все равно не может. Если измерять пикосекунды, а не такты, то и любой ADD\SUB "тормознее" любого AND\OR\XOR - от задержки распространения переноса никуда не денешься



PS: тебе не кажется, что пора завязывать с этим делом В докозательство твоей правоты могу привести пример, правда не вполне объяснимый, но все же: на P4 Northwood цепочка из 3-х зависимых shl ecx,i и одной независимой shl eax,i выполняется как положено 4*3=12 тактов, а аналогичная цепочка из rol - на 1 такт дольше как ни крути. Можно торжествовать ))

 

leo

Может и так, но места там вполне достаточно и разделению на 2 строчки можно найти другое обьяснение.

А кто сказал, что следующая инструкция должна иметь зависимость? А если зависимости нет, но она всё равно не может начаться из-за того что ror всё ещё держит ALU? Не вижу смысла пытаться упростить задачу. Так мы скоро придём к заключению, что все инструкции равны и выполняются за одинаковое количество абстрактных единиц времени. Фактически ror можно представить как shrd + or и этот or после сдвига вполне может задерживать выполнение следующей инструкции. В ALU я не могу заглянуть, чтобы подтвердить, что это действительно так, но из альтернативных решений мне не приходит в голову более рациональное.

 

Quantum

1) Другое объяснение разделению на 2 строчки найти трудно, т.к. ROR расположен в одной строке с SHR и т.п.

2) Если говорить о пикосекундах, то сами по себе логические операции AND\OR\XOR предельно быстрые и выполняются "мгновенно" - с задержкой распространения сигнала на одном вентиле. Но другие операции (включая пересылки данных и переключения множества управляющих сигналов), с такой скоростью работать не могут и поэтому величина такта берется существенно большей, чем задержка вентиля. В ALU я тоже не могу заглянуть, но думаю что при любой самой крутой реализации схемы переноса задержка сложения в несколько раз превышает задержку непосредственного побитового XOR. Ведь недаром интеловские извращенцы пошли на хитрость в P4 со своим double-speed ALU - побитовая логика действительно выполняется за полтакта, а вот сложение и вычитание реально за два полутакта - по 16 бит в каждом полутакте. Поэтому если даже ror и выполняется по схеме "shrd + or", то это супербыстрый внутренний (аппаратный нетактируемый) or, а не отдельная микрооперация, и поэтому "shrd + or" вполне могут укладываться в один такт. А то что схема сдвига достаточно крутая видно из того, что в первых моделях P4 ей вообще не нашлось места и все сдвиги были реализованы на MMX_SHIFT - отсюда и латентность 4 такта (2 на сдвиг и 2 на пересылку) вместо одного

 

Непоняттно на кой нужен еще OR после SHRD ? ROL/ROR легко эмулируются одной операцией SHLD/SHRD.

 

dermatolog

У Кванта спроси А я сказал - "если даже"

PS: речь ес-но идет о неких внутренних операциях shrd\shld, т.к. аналогичные инструкции ес-но более тормозные - сдвиг двух регистров => не менее 2-х мопов

 

dermatolog

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



leo

А вдруг ROL эмулируется через ROR? Однонаправленный латч всё-таки дешевле.



В конечно счёте, ror/rol не быстрее shr/shl. Думаю, что на этом можно остановиться.

 

Ну можно считать что я выступаю вне конкурса

Медальки не нужны Больше интересны всякие открытия, особенно с пояснениями.

Просто в голову пришла функция определения "if 31 day" от номера, показалась интересной - поделился:

Неравенсто старшего и младшего бита номера месяца (младшей тетрады) означает что дней 31. Ну и показал на базовых инструкциях.

Можно и предложеной мной арифм. зависимостью уложится в 8 байт:

D4 08 ;aam 8

and al,ah

xor al,ah

or al,30

 

The Svin

Это был не наезд, а особенность выражения мыслей.



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

 

Йееех...

Ты больные нервы мне задеваешь

Я начну сейчас филосовствовать и плакаться )

Если коротко - мне в местах подобных WASM,asm32community и т.п. были интересны ужасно люди, которых я там встречал, интересно общаться с ними, учится. Но как правило - совершенно неинтересны их задачи (предметная область, для которой они писали программы).

Мне всегда было странно - почему эти люди, которых я считал зачастую намного талантливей меня, занимаются такими убогими задачами, и постоянно плачутся, что их умения низкоуровневых программистов нигде толком не нужны,

и кроме хакерства\крякерства с одной стороны и пользовательских приложений (которые большинство из них считают удобнее писать на HLL) никаких приложений их умениям не найти.

У меня было всё всегда наоборот - нехватало умений, а вот амбициозных и достойных (с моей колокольни принципов и морали) - было всегда больше, чем я мог решить.

Другими словами - все задачи, которые я приводил из реальности (моей реальности). Суперских задач. Задач, решение которых, реально меняет действительность. Беда в том, что "реальность" задач у нас не совпадает зачастую.



По поводу "безбранчевости" - хочется ещё помимо практического кода изменить (повлиять на) взгляд чисто математический. Бранчевость - это в логике либо интенсиональный подход, либо имликационный.

По русски интенсиональный этого когда правило задаётся простым перечислением (конъюнкцией)

Т.е. когда, наприме вместо того чтобы сказать про можество всех х таких, что

x E N and x < 100 and x mod 2 = 1

мы пишем

x=1 or x=3 or x=5 or x=7 or ... x=99

Оправдание интесиональности может быть только тогда, когда не выдерживается эквивалентость.

(т.е. пример 2*2=4 и 2*2 и 4 во многих случаях эквивалентны, а значит могут быть заменены друг другом. Но возьмём случай фразы "Вовочка не знал что 2*2=4".

Попробуем заменить 4 на 2*2. Получаем "Вовочка не знал, что дважды два равно дважды два". Т.е. получили чепуху, которая смысл первой фразы уже не несёт. Может показаться что это относится только к филологии или логике, однако возьмём пример из ассемблера: алгебраически a+128=a-(-128) но из-за формата x86 add eax,128 на три байта будет кодироваться длинее чем sub eax,-128 и мы можем заменить для укорачивания кода, но будут ли они эквивалентны? в части состояния флагов после выполнения - нет)



Имликация - это типа если ... то ...

Замена импликции приведена как раз в моём примере в этом топике.

Допустим мы пишем функцию If31day. Область определения - номера месяца от 1го до 12го

область значения булева: - 0,1

Мы могли бы выразить импликационно + интенсионально

If (x < 8 & x mod 2 = 1) | (x > 8 & x mod 2 = 0)

if31day=1

else

if31day=0

А могли бы просто избежать и того и другого

if31day= NOT(Equal(младший бит, старший бит)

или просто

if31day= младший бит XOR старший бит



Избегание того и другого, где возможно, может резко сократить дорогу (что является вобщем целью дискретной математики - в изначальном значении - понятии эквивалентном программированию)

Ну человеку, знакомому с элементарной математикой, не приходит ведь в голову считать сумму чисел от 1 до 100

способом 1+2+3+..+100

он же сделает (1+100)*100/2

А если посмотреть на схожие с этой задачей в кодах программ - там это происходит сплошь и рядом.

Так вот, часто просто от незнания, или недостатка анализа (попросту лени) именно в современном практическом программировании (что на самом деле не что иное как область математики) идёт злостное злоупотребление IF ELSE и CASE на голом месте, где в этом нет необходимости.

Но привычка искать "короткие" пути в области отказа от ветвления (иногда ветвление бывает короче иногда - нет) не прийдёт сама собой. Поэтому я взял на себя наглость принудительно привлечь к этому внимание в своих задачках. И на примерах, где нельзя подсмотреть ответь в каком-нить справочнике, и где кажется, по первому взгляду, что без ветления не обойтись.

Вот такое простое объяснение.

 

[offtop]The Svin, ты почту читаешь или где? Отпиши мне, плз [/offtop]

 

masquer

Отписался, Дима. Проверь почту.

 

Quantum

Ты такую траву больше не кури )

ROL EAX,5 = SHLD EAX,EAX,5

ROR EAX,5 = SHRD EAX,EAX,5

 

dermatolog

Эврика! Срочно беги патентовать эту формулу, пока в Intel не проснулись.

 

29 байт на основе кода _BC_:

(eax - месяц, ecx - год)

Код (Text):

1.     or al,2
2.     cmp al,2
3.     jnz .exit
4.     mov al,100
5.     xchg eax,ecx
6.     cdq
7.     div ecx
8.     test edx,edx
9.     cmovnz eax,edx
10.     and al,3
11.     setz al
12.     .exit:
13.     imul edx,eax,32
14.     xor al,dh
15.     or al,28