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

Вы кончайте мне тут упаднические настроения создавать

Ишь на пару с Quantum заголосили - "не уменьшить"

Пока не вечер тут бабушка надвое сказала.

Наша задача рассмотреть математику с точки зрения низкоуровневого представления в дополнительном коде. Пока мы ищем путь сократить сам алгоритм математически но с точки зрения этого представления - у нас все связи проясняются, а это и есть главная цель, а не кусок кода.

Мне вот замечание про cdq твоё понравилось не только и не столько как сокращение байта определённой инструкцией, но прежде всего как отметка что на то что a оказалось меньше b указывает также sf, поскольку как ты справедливо отметил - начально числа положительные, и этот факт можно использовать например с cdq. Хотя моё замечание про cmc тоже сокращает на байт, оно мне менее интересно так как просто указывает на другую реализацию загрузки 1...1 или 0..0 в зависимости от той же CF, а твоё привлекает новое небольшое но свежее направление SF. Тем более уже несколько примеров как можно изменить алгоритм получения максимума математически, правда они не короче, но и не длинее, а значит есть альтернативы принципиально отличающиеся и никто ещё не доказал, что все они представлены, а если не все - говорить о невозможности найти такую которая короче по шагам - рано. Не найдём короче - зато найдём альтернативы, они в другом окружении могут привести и к укорачиванию, раскорячиванию.

 

С лёту не понял. Это после sbb cx,cx?

sub bx,cx ;bx+1 или bx

or cx,ax ;cx = -1 или ax

а дальше что?

 

Дык push -100 pop edx экономят 2а байта, а последовательно xor edx,edx mov dl,100 не приведут к partial stall разве?

Там (Ppro+)особый случай для верхних 24 bit у eax, а для edx IMHO будет stall.

 

The Svin

Прошу прощения - с размером push+pop прокольчик получился

pop edx конечно одним байтом кодируется, а я как-то с подачи Black_mirror'a на двух зациклился



А вот насчет скорости не совсем так. В данном случае конечно по сравнению с imul+idiv прочая мелочь особой роли не играет. Но все же, во-первых, на всех процессорах push и pop это сложные инструкции (Vector Path на языке AMD), в частности в AMD и P6 простые инструкции декодируются по 3 шт.за такт, а сложные только по одной. Во-вторых, в пентиумах push\pop достаточно быстрые (по 1-1.5 такта), а вот в атлонах латентность push составляет 3 такта (esp - готов через 2), pop - 4 такта. В итоге получается, что выполнение независимой операции imul на атлонах растянется за счет push+pop на много тактов: X+T_push+T_pop+T_imul, где X = 0-2 такта задержки декодирования в зависимости от положения push. А если использовать комбинацию

Код (Text):

1.  
2.   sub eax,ebx
3.   mov edx,-100
4.   sbb ecx,ecx
5.   imul edx

то mov выполнится одновременно с sub и общее время получения imul составит 1+T_imul и вся цепочка зависимых операций по получению ebx выполнится параллельно с imul.



Насчет partial stall.

Во-первых, по настоящему эта проблема существует только в P6 family и то в последних Pentium M, начиная с 13 модели Intel'ы ее устранили. Во-вторых, вставка xor всего регистра перед операцией с частичным регистром устраняет эту проблему на P6 - процессор запоминает, что регистр EDX очищен и не пытается комбинировать отображения регистров EDX и DL, а просто берет в качестве EDX образ DL с очищенными старшими битами.

 

AFAIK только для EAX. Т.е. там выбрали только один регистр для "запоминания".

 

The Svin

Да.

Дальше - add bx,cx и т.д. Я поменял только те 2 инструкции. Выйгрыша нет, к сожалению.

 

Ага. Дык это клёво Инструкция распараллеливается.

По байтам правда будет тоже что и у Бездонного Тёмного Зекрала, но код его это улучшает явно.

 

The Svin

> AFAIK только для EAX. Т.е. там выбрали только один регистр для "запоминания".

Это ты наверное у А.Фога такую байку вычитал

Официальные мануалы Intel по оптимизации P6 family (24281603.pdf и 24512701.pdf) утверждают, что специальные случаи реализованы для XOR и SUB для всех 8-ми регистров общего назначения включая EBP, ESP, EDI и ESI.

Это элементарно проверяется и подтверждается на практике (по крайней мере для PIII, т.к. более древних моделей у меня под рукой нет, как впрочем и нет оснований не доверять интеловским докам

 

Понятно.

От темы отвлеклись.

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

Итог пока такой.

1.Есть способы на 1 байт уменьшить либо с cdq либо с cmc.

2.ECX Black_mirror в торопях использовал. Вобщем можно его алгоритмом ECX не трогать.

3.Есть варианты чуть улучшить скорость не портя размер.

Улучшения незначительны, IMHO потому как мы "заперли" себя в предложенном алгоритме. А Black_mirror кодёр внимательный он постарался, кроме мелочей, всё использовать.

 

Ещё одна фантазия для общего многообразия.

Как 5 инструкций заменить

И никого не застрелить,

от скуки...

(читатель ждёт уж рифмы "Хрюки",

так на же, чёрт тебя возьми)

(с)Александр Сергеевич Хрюшкин.

Код (Text):

1.  
2.  neg eax
3.  add eax,ebx
4.  cdq
5.  and edx,eax
6.  sub ebx,edx
7.  

 

The Svin

> "заперли" себя в предложенном алгоритме

IMHO "запор" вытекает сам собой из условий задачи и доступного набора инструкций x86

Сам алгоритм простой и однозначный: 1) получить разность a-b; 2) по знаку разности выбрать в качестве делителя d большее из чисел a или b. CMOVcc по условию использовать нельзя, поэтому нужно ручками сформировать d из доступных чисел a, b и a-b. Одной неразрывной функцией этого (видимо сделать нельзя - нужна ступенчатя функция типа sign. С учетом ограниченного набора инструкций x86 c регистровыми операндами выбрать наибольшее число менее чем 3-мя инструкциями вообще никак нельзя, а реально получается не менее 4-х, т.к.при sbb,cdq = -1 нужно использовать значение a, пропадающее при sub => возможно много однотипных вариаций, но предложить что-то кардинально другое врядли возможно.

Например есть команда XADD, а вот XSUB к сожалению нет - опять нужна доп.инструкция:

Код (Text):

1.   neg ebx      
2.   xadd eax,ebx ;теперь ebx = [a]
3.   sbb ecx,ecx
4.   and ecx,eax
5.   sub ecx,ebx  ;ecx=-a или -b

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

Код (Text):

1. XXX proc a:dword,b:dword  ;stdcall ес-но
2. option prologue : none
3. option epilogue : none
4.   mov eax,[esp+8] ;b
5.   mov edx,100
6.   sub eax,[esp+4] ;b-a
7.   sbb ecx,ecx     ;b > a -> 0; a > b -> -1
8.   imul edx
9.   idiv [esp+ecx*4+8]
10.   retn 8
11. option prologue : prologuedef
12. option epilogue : epiloguedef
13. XXX endp

 

Ага, интересно.

b >= a -> 0

 

Кстати, Black_mirror видимо не только качественный код пишет, но и мануалы внимательно читает - его вариант с точностью до not ecx совпадает с вариантом выбора минимального из двух чисел, рекомендуемым и А.Фогом и мануалами по оптимизации от AMD



Вот ради прикола еще вариант с самомодификацией кода - о размере и скорости конечно речи нет - просто шутка

Код (Text):

1.  
2.   sub eax,ebx
3.   cdq
4.   and edx,20h
5.   or [@F+2],dl
6. @@:
7.   lea ebx,[ebx+eax] ;)))))))))))))

 

Ой да это фигня. Кирпичик.

И не Фог его конечно придумал. Я встречал этот приём в древних книгах 50-60гг.

Мне понравилось как все кирпичики увязаны у него.

У меня очень большие сложности бывают с этим.

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

Это то, что я называю "carefull coding".

Причём этому в книжках нигде не учат.

 

А где вообще сказано про cdq насколько она тормозная и т.п.?



И вопрос ещё один меня гложет вот уже продолжительное время.

Ты постоянно ссылаешься на P4.

У тебя как-то работа связана с оптимизацией под P4?

 

CDQ однотактная операция на всех процах (P6,P4,K7,K8), а вот ADC\SBB - 1 такт на AMD, 1-2 в P6 и до 8 тактов (!) в NetBurst (P4, Pentium D и т.п.)

Для АМД латентности всех инструкций подробно расписаны в мануалах по оптимизации (K7 - 22007.pdf, K8 - 25112.pdf). А вот Intel как всегда ленится или что-то скрывает. Для P6 в "старых" мануалах только SSE расписаны, а для прочих приводится только латентность и throughput исполнительных блоков и отдельно дается табличка кол-ва микроопераций - как хочешь так и увязывай. Для P4 (и частично для Pentium M) неплохо расписаны SSE\MMX\FPU, а вот целочисленные - только выборочно. На помощь приходит pentopt.pdf А.Фога, правда с поправкой на ветер - его данные относятся к 1-й модели P4 (Willamette), у которой есть небольшие различия со 2й (Northwood) и существенные с 3й (Prescott) и выше. Поэтому тут нужен "творческий подход"



Ну а что касается "ссылок" на P4, то, во-первых, под P4 я подразумеваю всю линейку NetBurst, включая Pentium D, которые еще продолжают "раскручиваться". Разумеется все эти монстры обладают рядом "гнусных" особенностей по сравнению с классикой P6+ и K7\K8. Во-вторых, благодаря агрессивной рекламе они расплодились и еще продолжают плодиться в огромном количестве, и неизвестно когда уйдут со сцены. Поэтому если не заниматься сиюминутной оптимизацией под конкретный камень, а творить "для людей" и "на века", то приходится брать поправку на "монстров" и при наличии нескольких вариантов реализации выбирать приемлемый как для классики P6+ (в т.ч. и под будущий интеловский Conroe), так и для неповоротливых NetBurst. Например в рассматриваемом случае CDQ "устраивает всех", а вот SBB в цепочке зависимых операций - существенный тормоз в NetBurst, а уж в сочетании с CMC - вообще труба (по данным Фога в P4 латентность CLC\STC\CMC 10 тиков, хотя на самом деле они могут вести себя "хитро" в зависимости от окружения)

 

У меня просто свой маленький личный опыт. Постоянно приходится оптимизировать либо по скорости либо размеру и скорости по работе. Он никак не собразует с логикой творить "для людей" , к которой я периодически сталкиваюсь. Она обычно исходит из того, что надо оптимизировать (и актуально оптимизировать) под те камни, которые в данный момент покупает некий "средний" пользователь. Доходит до такого непонимания бывает в разговорах, что чуть ли на грани конфликтов всё получается . Помню некто Nexo был на старой борде у Hiro. Вобще хороший кодёр, и как к программисту к нему у меня притензий нет. Но вот начинаешь заявлять тему и указываешь код нужен для PMMX. А он лезет с оптимизацией под AMD. Объясняешь - AMD неинтересно и не актуально для меня. Он лезет в бутылку - мол у тебя неправильный взгляд, а AMD популярный и лучше Pentium, и надо оптимизировать под AMD. Объясняешь мне не надо. Вобще fury какой-то становится Брызгает виртуальной слюной, я и обидеть не хочу и всё одно вижу, что не поймём мы друг друга. Всё таки область деятельности когда не разделена какое-то непреодолимое препятсвие получается в понимании.

Я заметил что много хороших программистов тусуются в ассемблерных эхах у которых работа реально не связана с низким уровнем и они видят в ассемблерной "идее" какой-то выдуманный символ "спасения программного мира" в котором "оптимизированные на ассемблере" процедуры изменяют мир к лучшему и ориентироваться нужно (что вобщем то логичным кажется в этой надуманной идее) на машины которые стоят у большинства людей. Как будто на этих машинах вдруг волшебным образом появятся те же самые Word и Exel но уже с интегрированными в них ассемблерными процедурами, написанными спасителями умирающего ламеризированного программистого движения.

Согласно моему скромному опыту всё выглядит с оптимизацией немножко не так. Можно выделить две наиболее крупные группы программёров связанных с оптимизацией на низком уровне. Одна (к которой более менее можно и меня отнести) работает над "закрытым" программным обеспечением, над программами, которые вобще никто кроме служащих конторы знать не должен, и за разглашение можно получить от штрафа до срока. Сюда по характеру програмной работы можно отнести и в частности разработчиков разного рода промышленных контроллеров, работающих в областях повышенных требований надёжности. Систем управления производством (не документообротом - а производством, задвижки там к примеру на нефтепроводе открывать, или в шахтах ) Там смена железа происходит ооочень инертно. У нас например светофорами до сих пор в городе управляет СМ2 - это в качестве гротескного примера (т.е. какой может быть разговор в этой конкретной конторе про то что PMMX устарел или не устарел - там вообще стоит СМ2 а IA вообще никогда не было). Оптимизация для этой области диффиринцируется на несколько категорий целесообразности, которые в некоторых задачах могут объединяться.



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



Реал - таймовская, есть поступление данных в реальном времени, и местами эти данные нужно быстро обработать (обработка бывает очень сложная и многослойная что-ли) и вот надо вписаться в отрезок от A до B в определённых участках. На этих участках выжимаешь всё бывает на грани того что мозги начинают течь и такое ощущение что насочинял уже на докторскую материала. При этом на других участках от C до D у тебя может быть совсем маленькая обработка и ты там можешь поэкономить байт-кодов, которые не жалел в узком месте. Я привожу это потому что критерии оценки тут совсем иные согласись, чем в соревнованиях на сколь процентов мой код быстрее. Тут проценты роли не играют тут надо вписаться в отведённые микросекунды. Буферизация в какой-то мере помогает но полностью не спасает.



Ну и третий вид оптимизации, уже похожий более менее на то, что делается на любительский соревнованиях. Нужно как можно быстрее обработать данные. Т.е. будет результат через день или через месяц. Это обычно дешифровки, шифровки, различный анализ по нечёткой логике и т.п.



Если говорить о камнях в этой области, то

1. Для систем с высокими требованиями надёжности P4 вобще не годятся. Т.е. это камень для домашнего постоянно слетающего с катушек компа - игровой приставки. Который даже в тепличных домашних условиях не может выдержать долгой предельной нагрузки. Так - попыхтел\отдохнул\попыхтел\отдохнул - ещё туда-сюда. Но под медицинский прибор, управляемый P4, я бы ложится не советовал, как и доверять управление ядерным щитом не стал бы ему.

2.Меняется в таких местах оборудование очень инертно. Я знаю про некоторые Новые проекты только в обработке в которые заложены 386 и 486DX. А в других местах стоят годами PMMX и машины там не выключаются, и когда сменят их и перепишут ооочень большое программное обеспеченье - не знаю, но не в этом и не в следующем году.



Другая категория программистов - разработчики коммерческого ПО. По большей части с низким уровнем связаны разработчики BIOS, драйверов и геймов (так же хрякерских пограмм-ломалок).

Разработчики драйверов вроде что-то должны оптимизировать, но из знакомых никогда не слышал об напрягах с оптимизацией по скорости. Обычно - по размеру, чаще вообще ничего не оптимизируют.

Разработчики BIOS любят это дело. Но у них как раз не аморфная оптимизация "вообще" а под конкретный круг камней, чипсеты и т.п. Надо сказать ещё, что есть определённый круг разработчиков BIOS, которые делают не то, что пользователи ПК понимают как некую базовую недооперационку которая помогает загрузить "настоящую" какую-нить Винду. А делается типа контроллера в котором этот BIOS расчитывается как первая и единственная операционка. Т.е. по сути они пишут замкнутую в BIOS систему которая так и должна самостоятельно работать выполняя какие-то (в реальности самые разные) задачи.

Вот там приходится очень постараться из-за ограниченности ресурсов.

У геймеров и коммерческих хрякеров из тех кого я знаю подход в оптимизации распределённый. Т.е. пишется сразу несколько разных участков кода каждый выполняя одну и ту же задачу. Каждый участок оптимизируется под какую-то группу процов. На входе по CPUID определяется какой проц и направляется на определённый для него участок.



Я просто хотел пояснить чем вызваны мои вопросы были.

Т.е. или это действительно по работе надо P4 или это что то типа "в настоящее время логичным кажется заниматься оптимизацией под то на чём сидит народ".

 

The Svin

> «видят в ассемблерной "идее" какой-то выдуманный символ "спасения программного мира"»

Полностью согласен. Если говорить об оптимизации по скорости, то низкоуровневая ассемблерная оптимизация это никакая не панацея, а скорее последнее звено цепи: верхний уровень - ес-но выбор\разработка алгоритма, средний уровень - "правильная" реализация как с учетом "прописных истин" программирования, так и некоторых тонкостей работы железа и винды. (Например, "народец" с одной стороны до смерти боится goto и условных переходов, хотя во многих случаях ничего страшного в них нет, а с другой стороны верит сказкам про чудесный файл-маппинг или наоборот наивно полагает, что читать с диска "заголовки" блоков и seek'ать на следующий блок всегда быстрее, чем читать все подряд Ну а низкий уровень ес-но остается на десерт и часто оказывыется не нужным - бесполезным или нецелесообразным на фоне общих тормозов, поданных на первое и второе.



> «Можно выделить две наиболее крупные группы программёров связанных с оптимизацией на низком уровне»

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

Во-вторых, к "закрытым" конторам или кругам можно отнести ПО для инженерных и научных расчетов, включая различные CAD, ГИС и доморощенные базы данных. В этой области быстродействие никогда не бывает излишним и соответсвенно народ стремится держать нос по ветру и регулярно обновлять железо. Причем замена ес-но идет частями и с учетом моды\рекламы\слухов, поэтому в одной конторе можно встретить и P6+ (как ветеранов труда - PIII, так и современных "шустряков" Pentium M), и полный спектр P4 и\или AMD (кому, что "насоветовали"

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



> «или это действительно по работе надо P4 или ...»

Нет, конкретно под P4 не надо, а по большому счету вообще не надо )))

Во-первых, в основном рулит "высокоуровневая" оптимизация. Во-вторых, я уже достаточно долго окучиваю и удобряю поле, с которого собираю свои скромные баксы , поэтому основные критичные кирпичики уже оптимизированы (причем это в основном не ALU, а FPU - тут различий в камнях меньше). В-третьих, задачек множество и плодятся они как кролики, время обработки и в старые времена было вполне приемлемым - в основном до единиц-десятка секунд (ес-но с алгоритмической оптимизацией, иначе тоскливо), а на нынешних камнях соответсвенно - доли-единицы секунд. Плюс "социальная инженерия" - развлечь юзверя во время обработки (протокольчик на экран, вместо одного прогресса - два-три, не успеешь ничего толком разобрать - результат готов, время пролетело - даже не интересно, слишком быстро Так что, у меня по текущей работе низкооуровневая оптимизация вообще мало востребована, это скорее хобби и тренировка мозгов, клич пионера - всегда будь готов ))

 

Насчет P4 - мне даже представить страшно сколько может стоить Pentium 4 Industrial Edition!