Складываем два длинных-предлинных числа X и Y (Y<X).
Вычисляем X=X+Y.
Основной цикл сложения выглядит так:

cikl: mov eax,[esi]
lea esi,[esi+4]
adc [edi],eax
lea edi,[edi+4]
dec ecx
jnz cikl

Как бы сделать это еще быстрее?

А в какой системе счисления записаны числа? В 2³²-ричной? Изврат...
afaik add работает быстрее, чем lea - команда попроще, микроинструкций меньше

Исправлено
Начет системы - извините, лох. Двоичная. Только работать с такими "очень длинными" числами все равно изврат imho...

Arvensis, числа хранятся двойными словами, но можно формат хранения и поменять, если это позволит складывать быстрее. Как предлагаешь?
Может add и быстрее, но он влияет на флаг переполнения,
поэтому lea здесь придется заменять на pushf / add / popf,
что уже будет медленнее...

add повлияет на adc , и помойму 1 такт будет что lea , что add

А числа ооочень большие? Может юзать SSE/SSE2?

Gray > „Складываем два длинных-предлинных числа X и Y“

На сколько эти числа длинные и что с ними потом делать нужно?

По поводу цикла: IMHO тут особо не разгонишся, т.к. зависимости по результату из-за переноса..

Интереснго, если это складывать как-нибудь двумя потоками через DWORD, то как потом переносы учитывать?

Хотел предложить использовать lodsd, stosd, loop для уменьшения размера... хорошо, что не поленился проверить, прежде чем предлагать :)

Оказалось, что в случае с использованием lodsd и stosd скорость падает на 30-40%, а использование loop на скорость не влияет.

Правда, есть один нюанс. При размере чисел в 8 мегабайт все вычисление (Seleron 2,6) занимает порядка 100-150 миллисекунд. А при размере в 16 мегабайт винда начинает свопить массивы, и в результате ни о каких измерениях скорости речи быть не может - результат колеблется от 2 до 15 секунд.

Для желающих принять участие в тестировании привожу код:

#include <windows.h>

#define Size 0x800000

DWORD x1[Size];
DWORD x2[Size];
DWORD y[Size];

void add1()
{
	__asm
	{
		mov edi,offset x1
		mov esi,offset y
		mov ecx,Size
		cld
cikl1:	lodsd
		adc eax,[edi]
		stosd
		loop cikl1
	}
}

void add2()
{
	__asm
	{
		mov edi,offset x2
		mov esi,offset y
		mov ecx,Size
cikl2:	mov eax,[esi]
		lea esi,[esi+4]
		adc [edi],eax
		lea edi,[edi+4]
		dec ecx
		jnz cikl2
	}
}

DWORD my_rand()
{
	return rand()%0x100 + ((rand()%0x100)<<8) + ((rand()%0x100)<<16) + ((rand()%0x100)<<24);
}

#pragma comment(linker, "/entry:main")
void main()
{
//	srand(0);
	srand(GetTickCount());
	for (DWORD i=0;i<Size;i++)
	{
		DWORD tmp=my_rand();
		x1[i]=tmp;
		x2[i]=tmp;
		y[i]=my_rand();
	}
	DWORD t0=GetTickCount();
	add1();
	DWORD t1=GetTickCount();
	add2();
	DWORD t2=GetTickCount();
	
	char buf[128];
	wsprintf(buf,"add1:%i, add2:%i",t1-t0,t2-t1);
	MessageBox(0,buf,"Finished",0);
	ExitProcess(0);
}

1. Использовано ADC и в сложении первых (младших) 32 бит числа. Что если на входе будет CF? Будет неверный результат. Если хочется экономить размер кода - сбрось CF
если важнее скорость - перед входом в цикл сделай сложение первых двойных слов (счётчик понятно в цикле должен быть уменьшен на 1 (т.е. (колл_байт_в_числах/4)-1)
2. Далее - можно использовать ecx одновременно как счётчик и индекс. Для этого нужно указать в счётчике вместо x -x
а в указатели загрузить предельный (первый невходящий) адрес.
т.е. если адресс a, а колличество двойных слов x
то адресс а можно представить как a+4x-4x.
т.е. если ecx это x, а скажем edi это a
то [edi]= [edi+ecx*4][4*-ecx]
далее вместо уменьшения наоброт умеличиваем счётчик.
т.е. пусть ecx - счётчик


lea edi,[edi][ecx*4]
lea esi,[esi][ecx*4]
neg ecx
clc

@loop:
mov eax,[esi][ecx*4]
adc [edi][ecx*4],eax
inc ecx
jne @loop

„А числа ооочень большие? Может юзать SSE/SSE2?“

Их вообще нет смысла юзать - они работают с floating point, а не с целыми :)

А вот насчет MMX я пытался думать, и ничего хорошего из этого не вышло: если я все правильно понял, то PADDB/PADDW/PADDD/PADDQ суммируют массивы чисел, а перенос между элементами массивов не делают.

RobinFood
Их вообще нет смысла юзать - они работают с floating point, а не с целыми :)

PADDx могут работать и с XMM регистрами для SSE2

А вот насчет MMX я пытался думать, и ничего хорошего из этого не вышло
я тоже думал :)
как вариант, можно распаковывать длинные числа не по 32 бита, а по 31 бит.
тогда 31-й бит (считая от 0) можно рассматривать как заем/перенос при сложении/вычитании.

RobinFood > „А при размере в 16 мегабайт винда начинает свопить массивы“

Что-то не то с виндой ;-)

AXP @1666:

---------------------------
Size 0x800000
---------------------------
add1:109, add2:110
---------------------------


---------------------------
Size (2*0x800000)
---------------------------
add1:219, add2:203
---------------------------


Способ The Svin'а даёт прирост до 16%

---------------------------
Size (2*0x800000)
---------------------------
add1:188, add2:218
---------------------------


ЗЫ
Как сюда MMX/SSE прикрутить? Что с переносом-то делать

RobinFood
Че? SSE2 работает с целыми данными, а вот что делать с переносами действительно не понятно... Может хранить не 64 бита, а 63 и последий юзать как детект переноса? Хотя действительно вряд-ли выигрыш даст - скорее наоборот.

Когда мы задаем мегабайтные числа, существенную роль играет скорость обмена с памятью (в этом случае не мешало бы prefetch использовать). Если же все данные лежат в кэше, то результаты получаются, мягко говоря, не столь однозначные. Например, такой эксперимент - берем size = 4096, а для увеличения статистики используем 10^4 - 10^5 повторений запуска процедуры. У меня на P4 1.8GHz получилось, что из приведенных методов исходный add2 самый быстрый, метод TheSwin на 27% хуже, а lodsd\stosd - ни в какие ворота не лезет (почти в 2 раза хуже).
Возможно для S_T_A_S_ это очередное подтвержение отстойности и тупиковости P4 NetBurst ?

А известным методом повышения быстродействия циклов является увеличение числа операций на цикл. Если в исходном методе в цикле складывать по 4 dword-а, то получим реальный выигрыш (по крайней мере хуже никогда не будет). Например, в приведенном выше тесте на P4 получился выигрыш на 20%.

    shr  ecx,2
    clc
  @@loop:
    mov eax,[esi]
    adc [edi],eax
    mov eax,[esi+4]
    adc [edi+4],eax
    mov eax,[esi+8]
    adc [edi+8],eax
    mov eax,[esi+12]
    adc [edi+12],eax
    lea esi,[esi+16]
    lea edi,[edi+16]
    dec ecx
    jnz @@loop

(Здесь, кстати, перестановки операций и задействование доп.регистров для уменьшения write-after-read delay ничего не дают - на P4)

TheSvin, очень изящное решение, сэр. Быстрее на 10-15%.

RobinFood, leo, S_T_A_S_ то что lods/stos вариант работает медленнее - проявление простой закономерности - чаще всего новые инструкции работают быстрее, чем старые,
и то, что было оптимальным для 8086 для Пентиумов уже таковым не является. Причина, IMHO, в том, что разработчики ленятся (и опасаются) переделывать то, что уже было сделано в кристалле предыдущих процессоров.

В реальной задаче цифры 1000-2000 бит длинной. Так, что кэш работает :)
При сложениии есть еще один трюк. При вычисленни b=b+a, если длинна а (обозначим ее A) меньше чем длинна b, то достаточно сделать А сложений, а затем если CF=1 cкладывать с 0. Код привожу ниже. (случай А>B пока не поддерживается)

void vadd(char* a,char* b) // b=b+a; a<b
{
_asm{
mov edi,b
mov esi,a
mov edx,edi // save pointer to b
movzx ecx, word ptr [esi]
movzx ebx, word ptr [edi]
sub ebx,ecx
lea edi,[edi+4*ecx+4]
lea esi,[esi+4*ecx+4]
neg ecx
clc
cikl3: mov eax,[esi+4*ecx] // основной цикл
adc [edi+4*ecx],eax
inc ecx
jne cikl3
jnc end_vadd
mov eax,ecx
cikl0: adc [edi+4*ecx],eax // eax=0
inc ecx
jc cikl0
end_vadd3: lea eax,[edi+4*ecx-4] // корректируем размер b
sub eax,edx
shr eax,2
mov [edx],ax
end_vadd:
}
}

leo > „Когда мы задаем мегабайтные числа, существенную роль играет скорость обмена с памятью“

IMHO это как раз не тот случай. Скорость чтения данных порядка 80Mb/sec. О кеше нужно думать, когда скорость напорядок больше.
И пока есть зависимость - учёт переноса, никуда от такой низкой скорости не деться.

> „на P4 1.8GHz получилось, что из приведенных методов исходный add2 самый быстрый, метод TheSwin на 27% хуже“

А это вроде бы (полу)документировано intel'ом - из-за умножения ecx на 4. Если вынести уножение за цикл, то должно быть лучше.. только вот inc на add так просто не поменяешь.


Gray

Поясню, зачем я спрашивал о том, как эти числа используются.
Если 80% времени происходит сложение, а потом числа преобразуются, например, в ASCII, то можно попробовать распараллелить сложение (см. пост Max), а переносы учитывать именно при преобразовании - оно и так медленное.