• úvod
  • témata
  • události
  • tržiště
  • diskuze
  • nástěnka
  • přihlásit
    registrace
    ztracené heslo?
    XCHAOSANSI C/C99 (specifikace), GNU C (gcc, glibc), Tiny C (tcc) a POSIX - ne nutně C++,g++,libstdc++ nebo Win32 API
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    REDGUY:
    http://en.wikipedia.org/wiki/Carry-lookahead_adder (je logN misto N)
    http://en.wikipedia.org/wiki/Carry_bypass_adder
    Carry-select adder - Wikipedia, the free encyclopedia
    http://en.wikipedia.org/wiki/Carry-select_adder

    Ale priznam, musel sem zkonzultovat spoluzaka, protoze uz to je 5 let co sem se to ucil, 4 roky od posledniho pouziti.
    REDGUY
    REDGUY --- ---
    DAVIDOWITCH: Neznam terminus technicus, ale takovou tu uplne obycejnou. I kdyz nepochybuju ze zaimavy budou i ty chytrejsi 8)
    Zkusim najit kde jsem o tom cetl...
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    REDGUY: Myslis Carry-lookahead, nebo nejakou z tech chytrejsich, nebo obecne proste tyhle bordely?
    REDGUY
    REDGUY --- ---
    REDGUY: A btw, navrh hw scitacek co pracujou v konstatnim case, aniz bys musel nejak postupne v nekolika krocich propagovat carry zleva doprava je docela zajimavej a elegantni. Doporucuju si o tom neco najit,
    REDGUY
    REDGUY --- ---
    XCHAOS: sčítání čísel obsahujíích různý počet nastavených bitů prostě trvá různě dlouho - ale kdeze. Delka scitani integeru je konstantni, na poslednich intelech trva tusim dokonce efektivne 0.5 taktu. Navic ty cisla co scitas jsou stejna, jen v jinem poradi. A konecne tuhle teorii lze snadno vyvratit tak, ze si to vyzkousis scitanim jinejch cisel.

    nebo trváte na compile-time optimalizacích - netrvame, protoze compile-time optimalizace s tim nemaji nic spolecneho (*) a nikdo tady nic takoveho nerikal. Naopak, tohle je nasledkem v podstate run-time optimalizace, ktera probiha primo v procesoru. Podrobne vysvetleni i s obrazkama: http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

    (*) tedy, c-t-o s tim maji spolecneho to, ze maji vliv na to jak vyrazny je ten efekt a pokud mas fakt hodne chytrej prekladac, dokazou ho eliminovat. Ale na ten rozdil v casech vliv nemaji.
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    XCHAOS: Cim se lisej tyhle dva behy?
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    XCHAOS: scitani cisel obsahujicich ruzny pocet bitu trva uplne stejne, jeden takt.
    XCHAOS
    XCHAOS --- ---
    xchaos@tartarus:~$ ./test WTF
    Sum: 403504454559365000
    Time: 0.444335
    xchaos@tartarus:~$ ./test
    Sum: 403504454559365000
    Time: 2.32974

    ....a tohle je nejlepší:

    xchaos@tartarus:~$ ./test WTF
    Sum: 403504454559365000
    Time: 0.658788
    xchaos@tartarus:~$ ./test
    Sum: 403504454559365000
    Time: 0.687157

    ok, přiznávám se - dostali jste mě :-)

    (jen podotýkám, že můj mini-toolkit zahnrnuje i dávkový soubor "bake", který se má používat místo "make" a Makefile - a že budu používat při volání gcc ty optimalizace, který mě nejlíp dopadnou s mými typy zasmyčkování, která chystám... ale to je offtopic, tohle byl hezký vtípek, uznávám ...)
    XCHAOS
    XCHAOS --- ---
    xchaos@tartarus:~$ gcc -O1 test.c -otest
    xchaos@tartarus:~$ ./test WTF
    Sum: 403504454559365000
    Time: 0.43624
    xchaos@tartarus:~$ ./test
    Sum: 403504454559365000
    Time: 2.3264
    XCHAOS
    XCHAOS --- ---
    huh


    xchaos@tartarus:~$ gcc -O0 test.c -otest
    xchaos@tartarus:~$ ./test
    Sum: 403504454559365000
    Time: 3.60948
    xchaos@tartarus:~$ ./test
    Sum: 403504454559365000
    Time: 4.5604
    xchaos@tartarus:~$
    XCHAOS
    XCHAOS --- ---
    dobře... tohle už vypadá jako signál mimozemské civilizace "WTF" (zachycen po velkém úspěchu předchozího signálu "WOW")

    xchaos@tartarus:~$ ./test WTF
    Sum: 403504454559365000
    Time: 1.53202
    xchaos@tartarus:~$ ./test
    Sum: 403504454559365000
    Time: 3.59716

    můj návrh interpretace: sčítání čísel obsahujíích různý počet nastavených bitů prostě trvá různě dlouho - prostě CPU nějak ví, kolik je max. platných bitů v registru a pak i mikrokód sčítačící různý počet bitů trvá různě dlouho, to je celé.... prostě se mi to jeví, že asm instrukce ADD už není "atomická" (či jak to nazvat) - prostě už na soudobých architekturách netrvá vždy stejný počet taktů CPU (resp. možná trvá na úrovni jednoho vlákna, ale ten čas se může využívat např. pro NEVÍM způsobem NEVÍM JAK)

    je možné, že je to tímhle? (testováno zatím jen na 64bit platformě), nebo trváte na compile-time optimalizacích?
    XCHAOS
    XCHAOS --- ---
    REDGUY: ok :-)
    REDGUY
    REDGUY --- ---
    XCHAOS: Aaaaaaaaaaaargh. To proste neni mozny. Ty proste nejsi skutecnej. Ty jsi ve skutecnosti sdruzeni nekolika spickovejch komiku s extremne bizanim smyslem pro humor.

    Co jsem napsal v puvodni zprave?
    - "pokud mu na prikazove radce reknete "WTF"
    Co se pise v kodu?
    - "if (argc == 2 && !strcmp(argv[1], "WTF")) {"

    Co potom napsal xchaos?

    - "xchaos@tartarus:~$ ./test wtf"

    Najdi tri rozdily...

    Jak si z tebe potom nemam delat srandu?
    XCHAOS
    XCHAOS --- ---
    DAVIDOWITCH: myslím, že vidět v hlavním cíli mých pokusů "mikrooptimalizace" je trochu nepochopení mojí motivace k tomu, o co se snažím...
    XCHAOS
    XCHAOS --- ---
    REDGUY: dvě setinky sekundy. hmm, zajímavý.

    xchaos@tartarus:~$ ./test
    Sum: 403504454559365000
    Time: 3.50986
    xchaos@tartarus:~$ ./test wtf
    Sum: 403504454559365000
    Time: 3.52524
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    XCHAOS: Protoze to vede ke (spatnemu) zaveru, ze mikrooptimalizace (ala ty ktery delas ty) jsou dobrej napad.
    XCHAOS
    XCHAOS --- ---
    REDGUY: mě to přijde jako zajímavý zadání... nevím proč se do mě musíš obouvat i v případě, že to je zajímavý téma který nijak nesouvisí s mýma ujetýma nápadama.

    až budu mít chvilku, vyzkouším to.
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    Ostatne, funguje to i ve skalarnim kodu, zkus to samy na tohle (kdyz je v #if 1, je to maskovani, kdyz 0 je to starej kod):

    for(j = 0; j < ITERS; j++) {
    for(i = 0; i < ASIZE; i++) {
    #if 1
    unsigned mask = (prdel[i] >= RAND_MAX/2);
    mask = unsigned(-mask);
    sum += (mask & prdel[i]);
    #else
    if (prdel[i] >= RAND_MAX/2) {
    sum += prdel[i];
    }
    #endif
    }
    }
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    REDGUY: Jak ktery. Ale vetsinou mas instrukci ktera ti nastavi masky podle nejaky podminky a pak instrukci co je resetne do nejakyho stavu.

    v SIMD by to bylo cca takhle (kdyby se tohle odehravalo v jedny lane, takze de facto SIMT prave ala CUDA).

    const __m128 treshold = _mm_set_ss(RND_MAX/2);
    __m128 acc = _mm_set_ss(0);

    for(int i=0; i < ASIZE; i++)
    {
    // hezky
    __m128 datai = _mm_set_ss(data[i]);
    __m128 mask = _mm_cmp_ge(datai, treshold);
    datai = _mm_and_ps(datai, mask);
    acc = _mm_add_ps(acc, datai);
    }
    REDGUY
    REDGUY --- ---
    DAVIDOWITCH: To maskovani funguje jak? Na pristi instrukci, pristi store, dokud ho nevypnu, nebo jinak?
    Kliknutím sem můžete změnit nastavení reklam