2017-02-22 FizzBuzz 2

by Vasil Kolev

Понеже идеята ми се мотае в главата от месец-два и тая нощ ми хрумна финалната оптимизация, ето продължението на post-а за fizzbuzz:

int i=0,p;
static void *pos[4]= {&&digit, &&fizz, &&buzz, &&fizzbuzz};
static void *loop[2] = { &&loopst, &&loopend};
int s3[3]={1,0,0},s5[5]={2,0,0,0,0};
char buff[2048];
char dgts[16]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
int buffpos=0;

loopst:
	i++;
	p= s3[i%3] | s5[i%5]; 
	goto *pos[p];

fizz:
	memcpy(&buff[buffpos],"Fizz", 4);
	buffpos+=4;
	goto end;
buzz:
	memcpy(&buff[buffpos],"Buzz", 4);
	buffpos+=4;
	goto end;
fizzbuzz:
	memcpy(&buff[buffpos],"FizzBuzz", 8);
	buffpos+=8;
	goto end;
digit:
	buff[buffpos++]=dgts[i/16];
	buff[buffpos++]=dgts[i%16];
end:
	buff[buffpos++]='\n';
	goto *loop[i/100];
loopend:
write(1, buff, buffpos);

Известно време се чудех как може цялото нещо да стане без никакъв branch, т.е. и без проверката за край на цикъла. Първоначалната ми идея беше да я карам на асемблер и да използвам като в exploit-ите NOP sled, нещо от типа (извинете ме за калпавия асемблер):

	JMP loopst
	JMP loopend
loopst:
	NOP
	NOP
...
	NOP
	; fizzbuzz implementation
	; i is in RAX
...
	MOV RBX, 0
	SUB RBX, RAX
	SUB RBX, $LENGTH
	SUB EIP, RBX
loopend:

Или, накратко, колкото повече се увеличава i, толкова повече скачам назад с релативния JMP (който съм написал като вадене на нещо от EIP, което най-вероятно изобщо не е валидно), докато не ударя JMP, който ме изхвърля. Като оптимизация бях решил, че мога да shift-вам стойността с 4, така че sled-а да е само 25 броя.

В един момент ми хрумна, че мога да мина и без sled-а, като правя деление (което е отвратителна операция, но спестява кофа nop-ове). Така се получи по-горния вариант на C, който не е съвсем C, а просто някаква странна асемблероподобна гняс.

Иначе, важно е да се отбележи, че на какъвто и да е модерен процесор по-горния код е далеч по-неефективен от простото решение с if-ове, най-вече защото branch prediction и всички други екстри се справят много добре с всякаквите if-ове, но доста по-трудно могат да се сетят тия jmp-ове към таблици базирани на някакви стойности къде точно ще идат, за да се прави спекулативното изпълнение. Не съм си играл да benchmark-вам (въпреки, че имам желание), но като цяло горния код има шанс да се справя по-добре само на неща като 8086 и компания.

И като идея за следващата подобна мизерия, може би може да се оптимизира истински чрез ползване на някое от разширенията за работа с вектори/големи стойности и се unroll-не цикъла, например да се прави на стъпки от по 4 с някаква инструкция, която смята делители (кой-знае какви странни неща има вкарани вече в x86 instruction set-а).

Tags: , ,

2 Responses to “2017-02-22 FizzBuzz 2”

  1. Иван Says:

    Аз направих benchmark. Новата ти подобрена версия е два пъти по-бавна от същата стара която ползва цикъл. Нямам идея защо.
    По принцип `for` цикъла има една проверка която е в началото му, branch-ът след нея рядко успява, а всички разклонения на програмния блок свършват с jmp към проверката в началото на цикъла. С `goto` в края на цикъла кодът изпълнява един jmp към края, който изпълнява втори jmp според масива. Може би два последователни jmp му идват в повече, може би на по-нов процесор това няма да му пречи…

    Бенчмарка е лесен, просто изпълнявам 10 милиона пъти частта която съставя текста. Това почти гарантира че всеки достъп ще е от кеша. Предсказването на преходи вероятно също събира добра статистика. Ползвам gcc-5.4.0 -O3 -m64 .

    Пробвах някои мои варианти и промени.

    Избягването на библиотечни функции оказва най-голямо влияние. Тоест, след printf(), извикването на memcpy() е най-скъпата операция. Трикът тук е, че ако memcpy() се извиква с константна големина, gcc inline-ва собствен вариант.
    (Вариантът където нямаше никакви разклонения, но се ползваха таблици за стринговете и големината им, се оказа два пъти по-бавен от еталонния с goto).

    Следваща по тежест е операцията деление/модул. Бърз поглед на асемблера подсказва, че се генерира код който използва умножение и константа с реципрочна стойност. Умножението е добре оптимизирано, което прави някои от другите трикове неефективни. Не всички…

    Използването на `switch case` е с почти същата скорост като сложния вариант с масива от етикети. Използването на `if()` е сравнително евтино. Още повече, ако се използва вариант който позволява използването на `cmov`.

    Ползвайки горните наблюдения, успях да направя версия която е с 30% по-бърза от “оптималната”. Много е вероятно моята версия да е оптимизирана специално за моя компилатор, затова няма да я публикувам тук.
    Просто ползвайте switch и memcpy за всеки случай и ще имате разбираема и бърза програма.

  2. Иван Says:

    Сетих се, че двете таблици с етикети могат да се обединят в една, резултатът е значително по-добър, но все още е по-бавен с 10% от предишната версия с for().

Leave a Reply