Skip to content
Васил Колев

 2017-02-22 FizzBuzz 2

   от Васил Колев


Понеже идеята ми се мотае в главата от месец-два и тая нощ ми хрумна финалната оптимизация, ето продължението на 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-а).