"Да... оказывается мы придумываем сложение чисел с форматом которого не определились..."
Я все-таки понимаю задачу так, как она сформулирована в названии темы, т.е. в общем. И Gray в своих неоднократных пояснениях прямо или косвенно об этом говорил. Если мы хотим не просто быстренько "спихнуть" задачку, а поисследовать проблему, то мы разбиваем ее на этапы. Вполне естественно, что на первом этапе решалась задача сложения длинных чисел, записанных в обычном формате. Здесь, по крайней мере для меня, думаю и для других тоже, выяснилось очень много интересного, связанного с особенностями работы современных процессоров (к сожалению, об особенностях атлонов мы мало чего узнали...). Это и то, что ADC на P3-P4 довольно тормозная инструкция, и что самый компактный код, далеко не всегда оказывается самым быстрым, и что предсказумые переходы в циклах "не так страшны, как их малюют", и насколько важно выравнивание кода и т.д. и т.п. Что-то из этого было известно "теоретически", но тут оно было проверено на практике и подтверждено тестами. Разве можно говорить, что это был мартышкин труд ?
На втором этапе можно поговорить и о формате чисел. В частности разная длина операндов не протеворечит тому, что было сделано. Gray сразу говорил, что y < x. Поэтому под size мы можем понимать длину у и при выходе из цикла добавить перенос в старшие разряды x в дополнительном цикле с выходом по JNC. Что касается изменения формата (прямой код, динамическая длина и т.п.), то я согласен с Max - прежде чем изобретать велосипед, не мешало бы ознакомится с "мировыми достижениями" в этом деле и затем предложить какой-нить вариант для затравки. Иначе все зациклится на уровне беспочвенных рассуждений.

PS: Все-таки не удержусь от замечания насчет "интересной мысли" Gray по поводу ZF. Я ее считаю не особо интересной, поскольку если комбинация 0\0 вещь редкая, то JZ ничего не дает кроме дополнительного проигрыша, когда эта комбинация все-таки встречается. Некоторая польза от нее может быть именно в случае, когда операнды одинаковой длины и 0 < у < x, т.е. когда мы "тупо" складываем старшие дворды x с нулями. Тогда за счет динамического предсказания может удастся что-то сэкономить.

Max >"может быть имеет смысл не изобретать велосипед по новой, а взять готовую либу и попытаться прооптимизировать ее?"
Gray >"создавать всегда интереснее, чем переделывать :)"
Max >"нуу, если такими темпами делать сложение, то я представляю, что будет, когда пойдет умножение или деление :)))"

Кстати, алгоритм быстрого умножения Карацубы был создан именно в процессе "изобретения велосипеда" :)

The Svin >"Да... оказывается мы придумываем сложение чисел с форматом которого не определились..."

Смеюсь :) Классический RTFM. Я ведь не просто так постил в форум свой сишный исходник (См. первую страницу темы. Gray Дата: Окт 7, 2004 12:24:57) Из него мой рабочий формат чисел очевиден :)
И про свое отношение к формату писал (См. вторую страницу темы. Gray Дата: Окт 7, 2004 18:06:01 )
Формат - не догма! Если удастся придумать формат дающий большее быстродействие, с удовольствием буду его использовать. Как Вам мысль о хранении чисел блоками по 127 или 63 бит с перспективой использования возможностей SSE2?

S_T_A_S_ > "Корень зла - незнание истины. Из этого корня вырастает дерево сомнений со множеством полодов страданий.
Будда. "

Червь познания питается плодами сомнений...
Кто-тоМудрый

leo >"Все-таки не удержусь от замечания насчет "интересной мысли" Gray по поводу ZF. Я ее считаю не особо интересной, поскольку если комбинация 0\0 вещь редкая, то JZ ничего не дает кроме дополнительного проигрыша, когда эта комбинация все-таки встречается."

Похоже я плохо выразил мысль о ZF. Речь идет лишь о варианте, когда используется комбинация
add eax,edx
jc @@carry2

В этом случае лучше писать
add eax,edx
jz @@carry2

Выигрываем мы на этом конечно очень мало, но все же выигрываем :)

1. Определение обычный формат субъективное, это опять случай, когда никакой сложности нет точно сказать какой формат, но почему то труда ты себе не даёшь и читателям приходится предпологать а что такое для leo обычный формат.
Для меня к примеру несколько форматов вполне обычны, и по данному топику высказался, что предпологал что это целые числа фиксированной длины в [b]дополнительном коде[b].
У Gray нет никакого формата, он его не придумал, поэтому к сложению его чисел данный топик имеет косвенное отношение.
Он может посмотреть как складываются числа в другом (не его формате) и при сочинении своего формата может учесть особенности. Но предположение, что находки сделанные в процедурах для целых чисел в дополнительном коде обязательно найдут своё место в процедурах для его формата - ни на чём не основано, всё что хорошо здесь может быть наоборот плохо или вообще неприменимо или по барабану для процедур его формата. Не зная формат мы и судить не можем поможет ли это ему. Данный топик имеет непосредственную ценность только для тех кто собирается складывать в дополнительном коде.

2. По поводу„ поскольку если комбинация 0\0 вещь редкая“

Предположим что речь идёт о целых числах в дополнительном коде. Тогда вспомним как мы раскладываем слогаемые в алгоритме у нас есть cf который складывается с a и их сумма складывается с b. (a+cf)+b.
Трудно понять из выражения „комбинация 0\0 “
что имелось ввиду (для меня она выглядит как ноль делённый на ноль) но что имелось ввиду Gray то это случай когда при a+cf a=0=cf
А случай которые я использовал это a=FFFFFFFh cf=1
Так вот таких случаев не больше не меньше а ровно столько же. Возьми все числа где на определённых участках a=FFFFFFFh cf=1, сделать not множества этих чисел, получишь равномощное множество чисел со случаями
a+cf a=0=cf.
3.
„ то JZ ничего не дает кроме дополнительного проигрыша,“
Ты видимо не понял вообще о чём речь, тут не может быть проигрыша никак, меняется просто условие в переходе.

Давай по полочкам
Есть два и только два случая когда a+cf=0
Первый случай это тот же что и когда (a+cf) вызывает cf
т.е. а=-1 и cf=1
Другой случай a+cf=0 это a=0 и cf = 0.
Всё! больше случаев быть не может!
Обрати внимание что в первом случае cf и до и после сложения равен будет 1 а во втором и до и после cf будет равен 0, иначе говоря cf не изменится.
Пусть у нас переменная cf ={1,0}
Определим функцию CF(a,cf) которая будет возвращать тоже
{1,0} если будет CF при сложении текущего cf и a,
тогда можно так записать идею про ZF
(a+cf=0)&(CF(0,0)=0)&(CF(-1,1)=1)->
->(a=-1 & cf=1)|(a=0&cf=0)->
->(CF(-1,cf)=1=cf)|(CF(a,cf)=0=cf)->
->CF(a,cf)=cf&(a+cf=0)
CF это carry после операции cf - до.
Если установился ZF - то ни cf ни надо проверять, ни 0 ни надо прибавлять.
Мы просто

jc @@carry2
	add [edi],eax
	setc dl
@@carry2:

меняем на

je @@carry2
	add [edi],eax
	setc dl
@@carry2:

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

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

Gray & TheSvin еще раз о JZ
Все что вы оба говорите я прекрасно понимаю, это вы меня понять не хотите.
Я тестировал на P3 и P4 несколько вариантов переходов: 1) нет переходов вообще, 2) в каждом цикле кроме первого есть переход, 3) переход в каждом нечетном цикле, 3) переходы в каждом 4, 8 и 16 цикле (дальше не было смысла т.к. тенденция стала ясна). При этом вариант 2) давал несколько лучшие результаты чем 1). Вариант 3) давал наихудшие и намного худшие результаты. Дальше с уменьшением числа переходов ситуация улучшается. Цифры для P4 приведены на стр.5, leo 16 окт 12:17, аналогичная тенденция наблюдается и для P3, поэтому в начале стр.6 я уже не приводил все варианты, а только 1 и 3 (если нужно могу привести все).
Какой из всего этого напрашивается вывод. Очень простой: и в P3 и в P4 рулит предсказание переходов (в первом цикле статическое, в последующих динамическое). В варианте 1) и статическое и динамическое предсказание совпадают и jc занимает максимум один такт, а если доверять интелам то 0. В варианте 2) один раз получается промах, но зато проц пропускает неисполняемые инструкции и в итоге получается несколько лучше. В остальных же случаях возникают НЕПРЕДСКАЗУЕМЫЕ переходы и связанные с этим penalty, т.к. проц должен выбросить из конвейера ненужные микроопы и\или отменить результат, если он уже успел его "сощелкать". На P4 ес-но результаты хуже за счет более длинного конвейера (см.IA-32 optimization).
Теперь что касается ZF. Если считать, что комбинации (у=1,cf=1) и (y=0,cf=0) появляются случайно и равновероятно, но не идут пачками, то мы при замене jc на jz будем иметь в среднем в два раза больше НЕПРЕДСКАЗАННЫХ длительных переходов. Вы считаете это хорошо и "интересно" ?
Все-таки переходы никогда не считались быстрыми операциями, и в доках по i486 приводились задержки jcc: 1 такт при отсутствии перехода и не менее 3 тактов при наличии. В P3 и P4 ситуация изменилась - здесь важно не то есть прыжок или нет, а то что проц правильно угадал куда пойдет выполнение. Если угадал, то задержки практически нет, если не угадал то говорить о задержке просто "not applicable", ребята из интел только говорят что она может быть большой, сравнимой с длиной конвейера и что ветвление следует избегать где только возможно.
В нашем случае jc - это необходимость (т.к. иначе нужен еще один setc, а это уже хуже, чем просто adc), а вот зачем сюда еще jz навешивать, я не очень понимаю. Вот если числа фиксированного формата и старшие дворды y[i]= 0 и мы продолжаем складывать х[i] с нулями, тогда за счет повторяемости ситуации jz не будет давать задержки на этих нулях.
Впрочем, я ничего не советую и тем более не навязываю, а просто поясняю ситуацию так как ее понимаю.

[flood]

„понимаю задачу так, как она сформулирована в названии темы, т.е. в общем“

Ох и не хочется мне снова возвращаться в этот топик, поскольку всё что я здесь пишу больше похоже на флуд =)
Но всёже напишу, повторюсь.

НЕЛЬЗЯ РЕШИТЬ ЗАДАЧУ "В ОБЩЕМ" !!!

Решать - можно, будет приобретён опыт, может ещё что..

Но универсального решения не существует. Нет такого алгоритма, который бы работал одинаково эффективно для
любых данных.

Что такое "очень-очень длинное число"? Может пара мегабайт? Тогда увеличения скорости нужно добиваться другими методами

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

И IMHO „Классический RTFM“ здесь не уместен. Ещё STFW напишите ;-) "Найди условия задачи в гугле" :).
Ну из того сишного исходника очевидно-то?
Да, можно сделать некоторые предположения, как делал я. Потом оказывается, что они не верны для задачи в целом, а являются лишь частным случаем (что и не удивительно).


Для сомневающихся в важности знания не только формата данных, но и контекста, в котором эти самые данные используются, простой вопрс на засыпку:
даны строки ascii символов, нужно производить их сравнение на равентсво. Как лучше эти строки представить, что бы получить максимально быстрое сравнение? (в формате asciiz или Pascal или..)

ЗЫ: учитывая вышесказанное и то, что у меня athlon, можно делать догадки, почему „об особенностях атлонов мы мало чего узнали“ :)

ЗЫЫ: Не принимайте всё это близко к сердцу, просто вспомнил, как пришел как-то на Θорум человек, тоже числа складывать быстро хотел. А потом оказалось, что большие числа нужны, что бы отображать счёт в игре %)

[/flood]

S_T_A_S_
Чего-то тебя тоже на пространные изложения потянуло, а намек с атлономами ты понял правильно и, надеюсь, без обид :)
Ты бы высказал свое мнение по поводу условных переходов в цикле (см.предыдущий пост leo) - как по твоему, правильно я понимаю и интерпретирую результаты в том плане, что в P6 и NetBurst штраф за неверное предсказание ветвления может превышать "выигрыш", который можно было бы получить перескочив пару инструкций (для данного случая это add m32,r32 и setc r8 - довольно много микроопов).

PS:
S_T_A_S_ & TheSvin
А в этом топике я тоже чувствую себя неуютно - уж больно много любителей цепляться к словам. Похоже тут собрались юристы и дипломаты - одно невыверенное слово - и жди международного скандала. И зачем я написал "в общем", когда нужно было "в частном". Посмотрите самый первый вопрос Gray - приведен код с инструкцией ADC и вопрос "Как бы сделать это еще быстрее?" Но тут появляется "невыспавшийся" Arvensis и задает вопрос о формате, за который тут же сам и извиняется. Gray ему конкретно отвечает "числа хранятся двойными словами, но можно формат хранения и поменять, если это позволит складывать быстрее". Я конечно не дипломат и понял это так, что числа хранятся в обычном виде, т.е. в дополнительном коде (иначе причем здесь ADC) и от того, что мы увеличиваем разрядность чисел ничего принципиально не изменяется, кроме того что нужно производить сложение по частям с учетом переноса (ага, вот вам еще возможность прицепиться, считая собеседника идиотом, и в сотый раз доказывать, что может быть лучше изменить формат, а что если мегабайты, гигабайты, террабайты и т.д. и т.п.)
Не первый раз повторяю, мне эта тема была интересна именно в такой "обычной" постановке и я извлек из этого много полезного. Хотите складывать мегабайты - складывайте (помнится как-то предлагалась тема сортировки гагабайтных текстовых файлов, но почему-то дальше слов дело не пошло - видимо никому особо и не нужно было).

leo >"при замене jc на jz будем иметь в среднем в два раза больше НЕПРЕДСКАЗАННЫХ длительных переходов."

Вот теперь то до меня дошло :) Интересная мысль. Появилось желание написать что-то совсем без переходов.
Пойду обмысливать сей вариант :)

„Похоже тут собрались юристы и дипломаты“

Объясняю свою позицию: я чайник.
Сижу, читаю этот топ, и до сих пор не пойму, что же нужно складывать :((

S_T_A_S_„Объясняю свою позицию: я чайник. “

Во-во, а я так точно такой, ну незнаю я С, чтоб условие понять, и не знаю какими регистрами складывать числа, если их длина может быть и 1000 и 2000 бит

„ т.е. в дополнительном коде (иначе причем здесь ADC)“
Так и в прямом коде можно ADC использовать.
Вобщем ладно оставляю топик в покое :)
Нездоровая атмосфера так и витает как doom над ним.

The Svin
Прочитал наконец!

Да нормальная атмосфера. Чего ж вы хотите?
Атмосфера амбиций - это так естественно :)

Спасибо за идеи!

Давайте попытаемся разобраться, чтобы небыло наполовину, как Владимир Семёнович завещал, как сделать из декларативного утверждения "je увеличит количество непредсказанных переходов" утверждение логически и математически обоснованное.
Я с удовольствием послушаю, как полный чайник, тем кому есть что сказать.
Вначале вспомогательный вопрос о вычислении.
Допустим у нас число занимает 256 двойных слов.
При сложении всех возможных пар чисел A и B, которые в свою очередь состоят из частей-двойных слов (a_0,a_1 ...a_255) сколько раз возникнет ситуация когда
1. a_?+cf даст CF
2. a_?+cf даст ZF
С удовольствием почитаю результат и обязательное к нему обоснование.

Ешё раз подчёркиваю - во всех возможных парах A и B.
Т.е в 2^2048 возможных парах.