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: , ,

3 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().

  3. Стоян Малинин Says:

    Здравейте,
    Аз разработих тази задача като обърнах внимание повече на идеята отколкото на реализацията. Моята идея се базира на това да се генерират числата като се развиват две редици – едната кратна на 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