Сложение очень-очень длинных чисел

Asterix

IA-32 Intel® Architecture Optimization Reference Manual (Issued in U.S.A. Order Number: 248966-011)

"Another way to remove branches on Pentium II and subsequent processors is to use the cmov and fcmov instructions." (page 2-15)

"The cmov and fcmov instructions are available on the Pentium II and subsequent processors, but not on Pentium processors and earlier 32-bit Intel architecture processors" (page 2-16)



TheSvin

Очередное "послание президента" ? Я думал у нас тут форум, а тут нравоучения и навешивание ярлыков, а я видимо в роли Ходорковского...



А если по делу, то вот, примногоуважаемый, "великий и ужасный" TheSVin, результаты дополнительных тестов на P3 и P4. Речь идет о последнем варианте с jc @@carry и cmovc.



P3-650 (6.8.1) и P3-800 (6.8.6) дают одинаковые результаты:

Код (Text):

1. Gray____[b]TheSvin[/b]______cmovNoJumps____сmovAllJumps____
2. 1198____1157 ([b]3.5%[/b])___752 ([b]59%[/b])_____710 ([b]68%!!![/b])___

Две модели P4-1800 1) 15.2.4 и 2) 15.2.7:

Код (Text):

1. ___Gray________[b]TheSvin[/b]______cmovNoJmps____movAllJumps____
2. 1)_1396,1444___1444,1452_____1112 ([b]25%[/b])____1240 ([b]12%[/b])
3. 2)_1361,1384___1380,1375_____1120 ([b]21%[/b])____1327 ([b]2.5%[/b])

Special notes for TheSvin:

Для P4 Gray и TheSvin приведены две цифры для блюстителей "ОБЯЗАТЕЛЬНОГО" выравнивания и любителей логического мышления: первая соответствует смещению цикла xFh (вроде бы должен быть худший случай), а вторая х0h (супервыравнивание согласно учению TheSvin). Для тестированных моделей P3 разницы в выравнивании нет вообще, а для P4 - сами видите - непредсказуемое поведение в пределах нескольких процентов (закономерностью это назвать сложно, если для xF лучше чем для x0).



Вывод 1: из протестированных процев P4 15.2.7 (приверженцем которого я оказывается являюсь просто потому, что он уменя дома стоит и мне прще на нем проверить) для рассматриваемого варианта дает худшие результаты.

Поскольку у нас форум, а не отчетно-выборная конференция, надеюсь кто-нибудь заинтересуется и проверит на атлонах (а может еще на чем - спросите у TheSvin, что сейчас актуально, но думаю с EC 1033 и "Наири-K" могут быть проблемы - щутка, ес-но).



Вывод 2 (риторический): легко выдавать наброски идей, и не очень просто ... (чего-то не нашел подходящего выражения, опять приставка "квази" в пустой башке крутится)



PS: Заранее приношу глубочайшие извенения, если посмел кого обидеть - вольно или невольно, ведь не корысти ради, а токмо познания истины и т.д. и т.п. А все-таки лучше обсуждать конкретные вопросы, чем "ставить диагнозы"...

 

)

Да наплюй ты извинятся

Было бы перед кем ))

У тебя всё одно извинялка не функционирует.

Мы ж оба знаем, что извинятся ты и не собирался и считаешь что не за что.

От тебя одно требуется переварить информацию которую тебе дают и в которой ты ничего кроме наездов не видишь.

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



Не супервыравнивание а выравнивание на 16, и не моему учению, а строению кеша и стуктуре предвыборки.

Я из жалости к твоему травмированному местным аменингитом мозгу сообщил что фраза "выравнять хотя бы на 4е" говорит о том, что ты не понимаешь почему выравнивание на 16 должно быть. Вместо того, чтобы разобраться в вопросе ты ставишь мне свои "а по существу !!! ???" хотя уже указано слабое место. Оно же (это слабое место) не делось никуда. Ты опять пишешь

Т.е. как ни понимал так и не понимаешь. Что x1 будет лучше что ли xF? Что будет лучше\хуже при невыравненном коде уже будет зависить от самого кода и размера.

Я ведь пишу это в третий раз! Для меня это по существу (в третий раз по существу) и что я должен сделать то? какие я тебе "уси-пуси - деточка - ягодка - смородинка" должен сказать что бы и для тебя это стало по существу?

В первых же обоих я писал дважды ещё и

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

2. Твои все проценты - вообще ни хрена ничего не стоят пока ты не показал код которым они были получены и этот код не признан участниками корректным. Тут мой ник присутсвует - а ведь я не давал законченной процедуры - пример кода как убрать изменение указателя и пример распаралеливания при развороте.

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

В твоей как ты сам пишешь "пустой башке" ничего другого крутится и не предпологалось по предыдущим твоим письмам.

Мне ни лень было хотя бы в математике ТВОЮ идею по CF записать, я уже повёлся (хотя мне очень не нравится когда мной пытаются манипулировать да так грубо, что это оскобрит интиллект и жабы, не на конфетку даже а на фантик ловишь) так тебе всё одно мало, сколь тебе не уступай.

Так где ж твои идеи то которые как ты "легко набрасывать"?

Это что идея "нужно ADC заменить"? - это не идея и не набросок идеи - это проблема которую ты не решил.



Дайте формат. Тест корректный. Укажите модель.

Тогда будет имлементация.



Не позорься ты своими умствованиями про выравнивание - дай мне формат (сколько аргументов в процедуре как передаются и какой пролог) я покажу тебе как выровнять без всяких 15и nop'ов и границу входа в процедуру и сам цикл по параграфу без потерь.



S_T_A_S.

По поводу "мутной документации" у меня тут такие субъективные соображения, из скромного личного опыта.



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

Ну это как бы когда высокоуровневому программисту поясняют что существует вообще то такой "машинный код" в который переводятся высокоуровневые инструкции. Ну и каждый в меру своей испорченности "додумывает" это.

Понимания никакого нет конечно. Так ни только высокоуровневый программёр а даже и ассемблерщик не знающий строения кода может получить глядя на мнемоники

mov eax,[eax*4]

mov eax,[eax*4][ecx][FFFFFFF]

не правильное представление какая из них длинее если только в дебагер не посмотрит. Тому кто знает строение же кода никакого дебагера не нужно понятно.

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

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

Для DX486 это решалось в основном с помощью документации в которой важные вопросы были описаны.

Для PMMX и последующих было сложнее.

Вкратце

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

Так как каждое из них может быть реализованно по разному.

Т.е. конкретный камень разваливается на такие основные вещи как

шинный интерефейс (в которое входят тоже несколько компонентов и каждый из компонентов может иметь у разных шинных интерфейсов разные характеристики)

Например у разных шинных интерфейсов разный буфер записи.

Что это такое? Запись в основном сквозная, т.е. если есть данные в кеше то и они при записи обновляются и память тоже. Вроде бы должна быть задержка, но существует буфер записи и пока он не переполнен в него помещаются данные с той же скоростью что и в кеш, поэтому если даже у нас в какой то момент идёт запись но мы знаем что буфер уже должен быть свободен мы спокойно не боясь задержки можем писать в память и расположить по возможности код так что когда буфер заполнится мы поделаем в нашем коде что - нить другое (посчитаем в регистрах, почитаем из кеша и т.п.) чтобы буфер освободился мы таким образом избегаем циклов ожидания. Это только одна из сторон использования знаний шинного интерфейса, просто для примера.

кеш память

Она может быть разная и по разному организованна внутри камня в сопряжении с другими устройствами в камне.

Мы просто сначала изучаем сами виды реализации кеш памяти в интересных нам камнях. Скольки она ассоциативная, размеры её строк, логику синхронизации и т.п.

то же самое касается

устройства предвыборки

дешифратора

АЛУ, сколько, как организованны и т.п.

Устройство предугадывания переходов

и ещё длинный список ...

Мы концентрируем внимание на структуре, логике и алгоритмах положенных в каждое из этих устройств и видов реализиций их.

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

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

Нужно учится считать это самому.

А сами данные вот к примеру для (реликтового) 486DX ещё можно было в единой доке найти 27302501 там и различное LRU и различные виды кеша более менее разобраны, а по теперяшним конкретно нужно смотреть у нужно камня составные части и само описание частей искать на доках (тоже Интеловских) для разработчиков встроенных систем, там уже и с временными диаграммами и более детально по кишкам и математику можно почитать о логических связях.

Там кстати форум есть, я даже когда то учавствовал в нём когда практикующим программистом был а не балоболом

 

TheSvin

> "когда практикующим программистом был а не балоболом "

Во,во.. Ты не в первый раз указываешь на чью-то тупость, бестолковость и упрямство, а за собой видимо не замечаешь. Не в первый раз пишешь безсодержательные пространные послания и требуешь сформулировать задачу, которая уже давно сформулирована. Это что - не тупость ? Если ты забыл, то автором темы является Gray. Цитаты приводить не буду, но на сегодняшний день задача выглядит так:

1) Требуется оптимизировать цикл сложения x=x+y, где x и y целые числа длиной ~ 500-1000 бит. Для определенности в тестах используем 1024 бит = 128 байт.

2) За основу при сравнениях берется исходный вариант Gray. Варианты с разворачиванием цикла пока не рассматриваются, т.к. это известная методика и как правило работает всегда. (Gray включает в тесты простейший вариант разворачивания под условным названием leo для контроля результатов "снизу").

3) Требуется оптимизация не под конкретную модель процессора, а круг популярных на сегодняшний день моделей. Поэтому частные решения типа перестановки порядка операций или замена dec ecx на dec cx не возбраняются, но рассматриваются как экзотика и иллюстрация "хитрости" тех или иных процев. Задачка ес-но решается не строго научно ("не на просто модели а на составных устройствах модели"), а как обычно - методом "мозгового штурма" и "квазинаучного тыка". Берется идея (которая может на первый взгляд казаться и бредовой) и проверяется на том, что есть под рукой. Если получается, что-то интересное, то автор темы может положить эту фигню в свою копилку, чтобы проверить затем на других процах или развить идею дальше. Решать-то ему, мы здесь только так - развлекаемся и заодно помогаем чем можем. В частности, сам Gray против P4 не возражает (и тестирует на P4 и даже предложил вариант реализации на SSE2). У меня есть возможность проверки на P3 (6.8.х) и P4 (15.2.х), у S_T_A_S_ на AXP 1666 и т.д. Так общими усилиями может сложиться какая-то цельная картина. Если есть у кого другие модели - подключайтесь. Или что, покритиковал меня строгий TheSvin за "приверженность" к P4 и я должен ради реабилитации бегать и искать P2, PMMX или еще чего ?

4) Методика тестирования предложена bogrus (с подачи Агнера Фога) и "утверждена" Gray 11 октября 2004 г. (см.аттач test.asm на 3-й странице). Возможны несущественные модификации в "окружении" при условии, что они не искажают результатов тестирования. Последние тесты я провожу именно по этой методике (с идентичной основой, но с другим интерфейсом).



> "Т.е. как ни понимал так и не понимаешь. Что x1 будет лучше что ли xF?"

Насчет выравнивания не я тебя достал, а ты меня. Сколько можно повторять. Во-первых, протерев очки и посмотрев на цифры ответь на встречный вопрос: "что xF будет лучше что ли x0 ?" Во-вторых, перечитай мой пост от 12 окт.23:47 - я на P3 проверил все 16 вариантов смещения начала цикла от х0 до xF и магические числа x0,x4,x8 оказались ни чем не лучше других. Не веришь - возьми указанный test.asm, выкини оттуда align и добавляй по одному nop перед циклом - потом поговорим.



> "Это что идея "нужно ADC заменить"? - это не идея и не набросок идеи - это проблема которую ты не решил"

Когда я это писал, я уже проверил идею "статистической оптимизации" с setc и результат на P4 оказался заметно хуже. До cmovс тогда руки не дошли - вместо того, чтобы полезным делом заниматься, приходится перед тобой долго оправдываться.

 

Коллеги, говорю "брек" и напоминаю, что мы не на ринге. Не надо, как в детском саду, меряться "процессорами". Пусть каждый пользуется тем, что имеет.



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



leo, cпасибо за прекрасное изложение формулировки задачи.

leo, Ваш сmovAllJumps доставил эстетическое удовольствие. Хороший пример того, что много команд может быть быстрее чем мало.



P.S. Эпикур говорил: "В дискуссиях выигрывает побежденный, ибо осознавая ошибку приобретает новую мудрость".

 

Мне на самом деле у leo понравилось одно место - представление адреса источника как базы для приемника - просто но эффективно

 

Тогда я повторю вопрос:

Тогда непонятно, зачем делается prefetchnta [ebx+128] ?





S_T_A_S_ >>

Gray >

Исходник я вижу.

Для меня проблема - что делать с этими значениями:



---------------------------

14 bytes , 8 passes

---------------------------

0000002039

0000000453

0000000410

0000000393

0000000393

0000000393

0000000393

0000000393



Как из них получается одно число?

Если просто среднее арифметическое - то подход IHMO неверный.





The Svin >

Гм, я даже не подумал, где такие вещи можно искать.. Как хорошо было у зилога - весь проц на 97 страниц.

 

Я брал 393

 

Думаю мне, старому хрюку, нужно признать что было заранее глупостью с моей стороны реагировать на посты leo

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

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



А потому несколько конструктивных мыслей, и набросок кода и теста на примере кода того же leo.



1. У меня субъективное недоверие к приведённой тестовой программе. Это строится пока на поверхностых наблюдениях нестабильных результатов при разных входных данных, странного поведения при выравнивании и т.п.

Главное - определённые результаты тестов не сходятся с показателями проверянных временем профайлеров, на которых детально можно рассмотреть результаты связанные с доступом к кешу. Если будет время проанализировать точнее - я сообщу результаты что и почему.

Я предлогаю простой но признаный в своё время на Win32asmcommunity профайлер Меверика.

У него есть свои недостатки, но они в очень ограниченных пределах. Анализ действия кеша кода при выравнивании по крайней мере очень чётко виден.



2. Я выбрал для анализ наиболее понравившийся код из того, что постил leo и на его примере показать некоторые зависимости. Код следующий:

Код (Text):

1.  
2.     sub esi,edi
3.     xor edx,edx
4.     mov ebx,1
5. @@loop:
6.     mov eax,[edi+esi]
7.     add eax,edx
8. jc @@carry
9.     xor edx,edx
10. @@carry:
11.     add [edi],eax
12.     cmovc edx,ebx
13.     add edi,4
14.     dec ecx
15.     jnz @@loop
16.     ret
17.  

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



Я поставил задачу изменить его так чтобы

a) Он был несколько (неоптимально но видимо) быстрее чему у leo чтобы снять п%;дёж про "общие замечания" которые понятно по моим постам мне "пустыми" не казались, но видимо пока не запишешь в коде они не доходят.

Но её можно будет ускорить ещё, даже будут намёки как.

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

с) В нём выбрано только то о чём говорилось, но было непонято, в данном топике. Изменения составлены так, чтобы можно было легко заменить пару строчек кода и посмотреть результат. А именно:

с.1) Показано как "освободить" регистр с помощью использования стека для одного из чисел.

с.2) Можно увидеть разницу между dec ecx и sub ecx,1

с.3) Показано как leo недодумал (скорее всего непросчитал) свою же собственную мысль про setcc.

с.4) Показано как "разредить" инструкции влияющие на EFLAGS.

с.5) Можно комментированием строчек посмотреть будет или нет влиять выравнивания и входа в процедуру и цикл.

с.6) Простая мат. логика + арифметика для одного из выводов реализованных в коде.

д) Для сложения я использовал два числа длинной в 2^17 бит. Т.е. занимающие по странице байт (1024*4)

Числа созданы так чтобы чередовать (но не последовательно) переносы и непереносы при сложении.

Для профилирования PROFILER Меверика.

Для показа результатов VKDBUG нашего друга VKima, бывшего участника HI-TECH, нашего самого любимого казахского корейца и корейского казаха По которому все скучаем.



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

Вся работа сводится -

вставить процедуру (например my_proc).

Добавить строчку после start:

PROFILE my_proc

И после неё

PrintDec PROFILECYCLES,"мой крутейший код"

После перекомпиляции программа будет показывать вместе с другими данными например:



PROFILECYCLES = 5663, leo proc (addlong.asm, 7)

PROFILECYCLES = 4880, The Svin proc (addlong.asm, 10)

PROFILECYCLES = 100, мой крутейший код (addlong.asm, 12)



Теперь к самому коду.

Начнём с поверхностных изменений в коде leo.

В программе этот код выглядит как:

Код (Text):

1.  
2. align 16
3. leo_test:
4.     mov esi,offset data1
5.     mov edi,offset data2
6.     sub esi,edi
7.     xor edx,edx
8.     mov ebx,1
9.     mov ecx,1024
10. @@loop:
11.     mov eax,[edi+esi]
12.     add eax,edx
13. jc @@carry
14.     xor edx,edx
15. @@carry:
16.     add [edi],eax
17.     cmovc edx,ebx
18.     add edi,4
19.     dec ecx
20.     jnz @@loop
21.     ret
22.  

Результат:

PROFILECYCLES = 5663, leo proc (addlong.asm, 7)

Убираем ALIGN 16 со входа получаем:

PROFILECYCLES = 6159, leo proc (addlong.asm, 7)

(Справедливости ради отметим, что align 16 не простое полезное средство, оно может быть и вредным в определённых сочетаниях. Но для того чтобы описать точно как нужно что выравнивать, как это считается нужно писать методичку, пока мы просто отмечаем что выравнивание влияет. Например при данном расположение кода, выравнивание метки цикла приведёт наоборот к потерям.)

Востанавливаем align получаем опять 5663.

Второе простое изменение

заменяем dec ecx на sub ecx,1

PROFILECYCLES = 5649, leo proc (addlong.asm, 7)

Выигрыш небольшой но очевидный. Он сохраняется (подтверждается профайлером) и при других вариантах кода, другом колличестве циклов и т.п. Коль скоро уж leo избавился от необходимости adc то грех не воспользоваться sub.



Дальнейшие изменения уже не продемонстрировать так очевидно просто меняя код leo. Т.к. будет затрагиватся учёт изменения EFLAGS, распараллеливание инструкций и особенности отложенной записи.



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

Напрямую оно не ускорит код, но здесь есть одно но:

мы получаем регистр и тот кто захочет в дальнейшем оптимизировать мои идеи, может сделать разворот цикла (в целях корректности сравнений я также как leo оставил одно сложение на цикл, но реализовал так, что остаются два свободных регистра, учитывая, что к тому же источник загружается в любой регистр простым POP это даёт большое пространство для вариантов разворачивания цикла, даже на более чем два сложения)

На самом деле вы можете изменить мой код с вариантом загрузки операнда источника как у leo, и на PIII это даст даже лучшие результаты (правда о ловком разворачивании цикла забудьте тогда). Я сделал это просто чтобы проиллюстрировать идею.

Делается это просто (для наглядности я использовал обычную логику создания фрейма у MASM)

Для реализации последовательной загрузки операндов источника нам достаточно установить ESP на младший дворд источника, и далее POP будет делать две простые вещи - и операнд загружать и прибавлять 4 к ESP переводя ESP как указатель к следующему операнду (т.е. аналогия lodsd с теми лишь приятными разницами что

1. Загрузка в Любой регистр

2. Скорость резко выше

3. Используется как указатель ESP что освобождает EDI для других операций.

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

Код (Text):

1.  
2.     push ebp
3.     mov ebp,esp ;сохр. ebp esp
4.     mov esp,offset data1 ;ставим esp указателем на данные
5. ...
6.     leave ;восстанавливаем ebp,esp
7.  

Далее наша задача "разредить" максимально инструкции влияющие на EFLAGS и дать ещё одну возможность для освобождения регистра, для этого мы используем setcc,

а что леттенси не повлияло - максимально отдаляем использование того регистра в котором происходит установка по setcc. Для разрежения мы также меняем add edi,4 на

lea edi,[edi][-4] опять же отдаляя эту операцию от места где используется edi.

Другое наблюдение логико арифметическое.

На логическом языке я записал бы его так

(a + cf => cf) => (a+ cf)=0 => b+(a+cf)=b

Иначе говоря если мы прибавили к операнду CF и у нас carry

то в (a+ cf)=0 и смысла его прибавлять нет так как

b+0=b поэтому сложение тут можно скипнуть



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

Конечный код (давший ~ 17 % прибавки скорости на PIII):

Код (Text):

1.  
2. align 16
3. svin_test:
4.     push ebp
5.     mov ebp,esp
6.     mov esp,offset data1
7.     mov edi,offset data2
8.     xor edx,edx
9.     mov ecx,1024
10. align 16
11. @@loop2:
12.     pop eax
13.     add eax,edx
14. jc @@carry2
15.     add [edi],eax
16.     setc dl
17. @@carry2:
18.     lea edi,[edi][4]
19.     sub ecx,1
20.     jnz @@loop2
21.     leave
22.     ret    
23.  

Тестовая программа и исходники в формате проекта RadAsm

в архиве. Если нужен PROFILER Меверика - вышлю.

VKDEBUG должен быть на сайте.

Удачи всем в улучшении начального варианта.

Улучшения касаются только PIII (SB133mz) и за другие процы я не отвечаю.









1119913206__addlong.rar

 

Видимо тупость Для меня тупого задача до сих пор сформулирована не чётко. У меня беда такая - проффессиональный опыт требует чёткого тех. задания иначе недопонимание и переделки.

И дружок, если я тупой - игнорируй меня, пожалуйста.

Я по крайней мере, так и собираюсь поступать )

 

The Svin

> Если нужен PROFILER Меверика - вышлю.



Прицепил бы в топик. Дело в том что этот профайлер переделывали каждый на свой лад и я уже запутался в имеющихся у меня вариантах %) какой лучше точно уже не знаю.



Спасибо.

 

Вот

_573747113__profile.rar

 

TheSvin

Пропуск второго сложения при переносе - это гениально, восхищен, сэр !

Я столько крутился вокруг да около этого нуля, а тут все так просто и изящно.



Проверил на P4 1800 (15.2.7) без использования идеи с ESP и POP.

При отсутствии переходов выигрыш составляет 25% и ес-но снижается при их наличии.

Код (Text):

1. Gray____TheSvin skip setc (без esp)
2. 1385____1108 (25%) - нет ни одного jc
3. ________1240 (12%) - jc каждый 8-й цикл
4. ________1300-1350  - jc каждый 4-й цикл
5. ________1520-1640  - чередование jc через 1 цикл
6. ________626 (!)    - jc в каждом цикле

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



Пойду проверю на P3...



PS: Кстати, в посте о cmovc я привел результаты AllJumps с jc в каждом цикле, а надо бы приводить худший для P4 результат - с чередованием -> получается в районе 1650-1750.

 

The Svin



Тест не совсем корректный, как мне показалось, т.к. изменения в части svin_test влияют на скорость leo_test. Поясню:



В исходном варианте теста из аттача на Athlon 1800 имеется:

Код (Text):

1. PROFILECYCLES = 5153, leo proc (addlong.asm, 7)
2. PROFILECYCLES = 4114, he Svin proc (addlong.asm, 10)

Далее, закомментировал строку Align16 перед строкой leo_test: и VKDebug показывает:

Код (Text):

1. PROFILECYCLES = 4132, leo proc (addlong.asm, 7)
2. PROFILECYCLES = 4114, he Svin proc (addlong.asm, 10)

Далее: в части leo_test заменяю sub ecx,1 на dec ecx. Результат:

Код (Text):

1. PROFILECYCLES = 4108, leo proc (addlong.asm, 7)
2. PROFILECYCLES = 4114, he Svin proc (addlong.asm, 10)

Далее, пытаюсь тоже применить к svin_test: вместо sub ecx,1 - dec ecx. Результат:

Код (Text):

1. PROFILECYCLES = 4133, leo proc (addlong.asm, 7)
2. PROFILECYCLES = 4114, he Svin proc (addlong.asm, 10)

В заключение комментирую align16 перед строкой svin_test:

Код (Text):

1. PROFILECYCLES = 5153, leo proc (addlong.asm, 7)
2. PROFILECYCLES = 4114, he Svin proc (addlong.asm, 10)

 

Почему некорректный. Просто описанные мной результаты были на PIII, тобой на Athlon. Как раз корректный так как видим как по разному реагируют разные камни на выравнивание и прочее.

Возвращаемся к простой мысли которая проходит лейтмотивом через весь топик: мы не можем корректно определить какой код лучше. Мы можем корректно определить какой код лучше для ОПРЕДЕЛЁННОЙ модели.

Конец моего поста говорит это открытым текстом:

оптимизировалось для PIII(SB133) за остальные камни не отвечаю.

Мой субъективный опыт, на котором и сформировались взляды на низкоуровневую оптимизацию был связан всегда с тем что такая оптимизация делается только для определённых камней. Например делались контроллеры на основе 486DX2.

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

Далее делалась оптимизации для системы управления, машины стояли PMMX и PIII на разных задачах, вместе связанные в систему. Управление базами этой системы должно было писаться максимально оптимизированным. Так только особенности внутренних устройств этих камней и учитывались.

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

К сожалению, по Athlon'ам я не специалист, они у нас сразу отметались как не прошедшие тесты по критериям соответсвия надёжности (я не против их, пойми правильно, они возможно самое то для твоих задач, но полевым условиям не соответсвуют, да и Пни с грехом пополам соответсвуют, последние более менее надёжные были 486DX, остальные делались подстать тому - за что платят "простые пользователи ПК").

Для того чтобы нормально писать низкоуровневую оптимизацию для Athlon нужно точно знать сопряжение внутренних устройств, таких как предвыборка, дешифратор, структура и сопряжения кеша, шинный интерфейс. У меня 0 знаний про Athlon.

Кроме того я уже писал что просто выравнивание на 16 - не панацея, там сложнее всё, завист от ассоциативности (по какому множеству) размера строк, и алгоритмов.

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

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

Чтобы не менялось общее расположение.

Можно было конечно разместить их в разных секциях.

Подробного объяснения ждать будет долго

 

Любуясь изящнейшим решением The Svin, вспомнил я один трюк... Результат перед Вами.



lea ebx,[4*ecx-4]

xchg esp,esi

xor edx,edx

@@loop2:

pop eax

add eax,edx

jc @@carry2

add eax,[esp+ebx]

mov [esp+ebx],eax

setc dl

@@carry2:

sub ecx,1

jnz @@loop2

xchg esp,esi



Дало это ~10% ускрорения



Для "тестилки" The Svin это выглядит так:



pop_plus:

mov esi,offset data1

mov edi,offset data2

mov ecx,1024

lea ebx,[4*ecx-4]

xchg esp,esi

xor edx,edx

@@loop3:

pop eax

add eax,edx

jc @@carry3

add eax,[esp+ebx]

mov [esp+ebx],eax

setc dl

@@carry3:

sub ecx,1

jnz @@loop3

xchg esp,esi

ret

 

Проверил метод TheSvin с setc и обходом второго add на P3 (6.8.1), но без esp\pop. (Методика пока прежняя, чтобы было с чем сравнивать). При отсутствии переходов имеем выдающееся ускорение до 78% по сравнению с исходным методом Gray (673 тика против 1196). Но тест с чередованием переходов через цикл дает как и на P4 ухудшение до 25% (1470-1500 тиков).



Тут меня заразила идея поискать код для P3, который бы давал меньшие потери при чередовании переходов через цикл. Сложилось впечатление (без претензии на всеобщность), что "длинный" переход через две инструкции в варианте TheSvin дает бОльшие потери, чем короткий через xor edx. Не буду приводить все промежуточные изыскания, но в итоге нашелся неплохой вариант, который проигрывает 5% методу TheSvin с обходом второго сложения, но гораздо менее чувствителен к ошибкам динамического предсказания при чередовании переходов. Здесь, кстати, использована первоначальная идея TheSvin c индексацией, но уже без масштабирования:

Код (Text):

1.     xor edx,edx
2.     xor ebx,ebx
3.     dec ecx
4.     shl ecx,2
5.     add esi,ecx
6.     add edi,ecx
7.     neg ecx
8.   @@loop:
9.     mov eax,[esi+ecx]
10.     add eax,edx
11.     jc @@carry
12.     xor edx,edx
13.   @@carry:
14.     add [edi+ecx],eax
15.     setc bl
16.     or dl,bl
17.     add ecx,4
18.     jle @@loop

Вот результаты для P3-600 (6.8.1)

Код (Text):

1. Gray    cmovc   "setc"  "setc2"
2. [b]1196[/b] 815 [b]673[/b]  [b]704[/b]  - без переходов (все y[j] > 0)
3.     1041    [b]1469[/b] [b]1038[/b] - чередование переходов (y[2j] = -1, y[2j+1] > 0)

(здесь "setc" с jc через add и setc, а "setc2" - приведенный выше код)

 

А чего никто цикл не разворачивает?

Так ведь написал пример чтобы зуд просто был

Можно так например:

Код (Text):

1.  
2. svin_test2:
3.     push ebp
4.     mov ebp,esp
5.     mov esp,offset data1
6.     mov edi,offset data2
7.     xor edx,edx
8.     mov ecx,512 ;128 if 1024 bytes long
9. align 16
10. @@loop3:
11.     pop eax
12.     add eax,edx
13.     pop ebx
14. jc @@carry3
15.     add [edi],eax
16.     setc dl
17. @@carry3:
18.     add ebx,edx
19. jc @@carry4
20.     add [edi][4],ebx   
21.     setc dl
22. @@carry4:
23.     sub ecx,1
24.     lea edi,[edi][8]
25.     jnz @@loop3
26.     leave
27.     ret    
28.  

Даёт ещё ~ 18 % ускорения. Можно ещё лучше сделать

и esi всё ещё свободен

 

Коллеги, примите во внимание следующие соображения:

1. При исполнении пары команд

add eax,edx

jc @@carry2

edx всегда либо 0 либо единица, следовательно переход по CF имеет место лишь в одном случае eax=FFFFFFFF & edx=1.

При этом остроумно пропускается одно сложение и запись результата. Однако, можно пропускать и при eax=0 & edx=0

Поэтому лучше будет проверять ZF (убивая сразу двух зайцев):

add eax,edx

jz @@carry2



2. В реальных вычислительных задачах с очень хорошим приближением можно считать двойные слова случайными величинами, тогда вероятность CF или ZF в вышеописанной ситуации крайне мала (~10^(-32)). Меньше одного события на терабайт обрабатываемых данных. Иль я не прав?

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

 

1. Интересная мысль по поводу ZF.

2. По поводу процитированного - не прав Если я правильно понял вопрос.

Если числа у тебя пусть длинные но знаковые (т.е. представлены в дополнительном коде) то ситуация когда CF будет прибавляться к FFFFFFFFh будет возникать всегда при сложении для одно число положительное а другое отрицательное т.е.

111...1xxx...

000...1xxx...

Мат. ожидание оставляю посчитать в виде упражнения.

Тоже можно сказать и про сложение двух положительных с большим количеством лидирующих 0.

000...1xx

000...xxx

leo, в целом правильный подход IMHO рассматривать разные ситуации с CF, но данные на вход лучше подавать более продуманными. Периодичность CF линейная очень редка кроме случая нет CF (лидирующие нули и все случаи когда числа без переноса) и все CF (сложение положительных и отрицательных слогаемых). Мысль по нет CF можно обдумать предлогая подход Gray выделив множество пар с большой мощностью - лидирующими нулями, а вот распределение переносов IMHO следует сделать более случайными, по натуральному ряду например, через 1, следующее через 2 и т.д. Мысль про пропуск то ли одной то ли двух инструкций приходила, но давала не равномерные результаты, найти закономерность и зависимость не смог, оставил более наглядный вариант, где видно что и почему пропускается.

 

The Svin, оба мы правы Просто у нас в голове разные модели чисел. Вы мыслите их в фиксированном формате (например 2048 бит, даже если все эти биты 0), а я говорю о "растяжимом" формате, т.е. число это заголовок+тело. Заголовок содержит информацию о длинне "тела" (количество двойных слов в теле) и знак числа. Само же "тело" всегда положительно. Такой формат представления данных позволяет заметно ускорить вычисления за счет того, что не надо складывать те самые лидирующие нули или FFFFFFFFh. Например сложение (в столбик на бумажке, забыв про шестнадцатеричную систему счисления) a+=b при a=123456789 и b=123 потребует трех сложений с переносом + 0.6 (в среднем) дополнительных сложений, а при фиксированном формате потребуются все десять сложений.