татко Крокодил

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);

	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:

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

1. Иван Says:
   March 1st, 2017 at 00:42

   Аз направих 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:
   March 1st, 2017 at 14:42

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

3. Стоян Малинин Says:
   June 5th, 2017 at 21:00

   Здравейте,
   Аз разработих тази задача като обърнах внимание повече на идеята отколкото на реализацията. Моята идея се базира на това да се генерират числата като се развиват две редици – едната кратна на 3, а другата на 5. Но тук се появяват 2 проблема: може да има дублиране на числа и не знаем как да ги сортираме.

   Първия проблем се решава лесно, понеже просто не вземаме fissBuzz числата по единия начин в моя случай чрез прибавянето на 5-тици.

   По-сложният проблем се явява вторият. За да го реша използвах едно от основополагащите неща при алгоритъмът за бързо сортиране merge-sort. То гласи следното: може да направим сортирана редица като използваме всички числа от 2 сортирани редици за N операции където N е броят на всички числа.

   Как става това? Нека имаме редиците:
   А: 1 2 6 7
   B: 0 3 8
   Винаги вземаме по-малкото число от двете начала(затова в реализацията използвам опашка)

   Сравняваме 1 и 0. Вземаме 0. Получава се:
   А: 1 2 6 7
   B: 3 8

   Сравняваме 1 и 3. Вземаме 1. Получава се:
   А: 2 6 7
   B: 3 8

   Сравняваме 2 и 3. Вземаме 2. Получава се:
   А: 6 7
   B: 3 8

   Сравняваме 6 и 3. Вземаме 3. Получава се:
   А: 6 7
   B: 8

   И така нататък…

   Така тази моя програма прави около N/3 + N/5 операции без да броим извеждането. Както забелязвате, не съм правил low-level оптимизации, понеже съм още неопитен и не разбирам много от компилатори.
   Мисля, че това решение има потенциал!

   Ето го и кодът:
   #include
   #include

   using namespace std;

   queue buzzFound;

   int main()
   {
   ios::sync_with_stdio(false);
   cin.tie(NULL);

   int n;
   int fizzNumber = 3, buzzNumber = 5;

   //cin >> n;
   n = 100;

   while(buzzNumber<=n)
   {
   if(buzzNumber%3!=0)
   buzzFound.push(buzzNumber);

   buzzNumber += 5;
   }

   while(fizzNumber<=n)
   {
   if(fizzNumber<=buzzFound.front())
   {
   if(fizzNumber%5==0)
   cout << fizzNumber << " – fizzBuzz" << '\n';
   else
   cout << fizzNumber << " – fizz" << '\n';

   fizzNumber += 3;
   }
   else
   {
   cout << buzzFound.front() << " – buzz" << '\n';
   buzzFound.pop();
   }
   }

   while(buzzFound.empty()==false)
   {
   cout << buzzFound.front() << " – buzz" << '\n';
   buzzFound.pop();
   }
   }

   В момента на моят компютър това решение работи малко по-бавно от оригиналното, но мисля, че след малко пипване тук-там може да го задмине и то доста.

Leave a Reply