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