zliczanie bitów

[Fibik]

Algorytm zliczania bitów o wartości 1 w liczbie 32-bitowej:

int nbits(unsigned n)
{
int k = 0;
for( ; n != 0; n >>= 1) k += n & 1;
// n >>= 1; - przesuwa bity liczby n, w prawo o 1
// n & 1 - operacja bitowa 'and': n AND 1
return k;
}

Algorytm ten (funkcja) wymaga, najwyżej 32*(1 + 1 + 2) = 32*4 = 128 instrukcji.
Kto zna lepszy?
Język dowolny: paskal, assembler, c, albo nawet schemat blokowy.

[drunkard]

Może jest jakaś instrukcja assemblera??
Jeśli wydajność jest kluczowa, a operacja jest często powtarzana, to najprościej najpierw przygotować 256-elementową tablicę, zawierającą ilość bitów w kolejnych liczbach od 0 do 255.
Potem zostaje już tylko podzielić 32-bitową liczbę na 4 bajty i sprawdzić w tablicy te 4 bajty i zsumować.
Tak na oko to jakieś 10 operacji.

[Fibik]

Mówisz o czymś takim:

byte t8[256] = {0,1,1,2,1,2,2,3,1, ... };

int nbits(byte b4[])
{
return t8[b4[0]] + t8[b4[1]] + t8[b4[2]] + t8[b4[3]];
}

Nie wiem, czy to będzie szybsze - używanie tablicy pośredniej,
która leży w pamięci (do rejestrów jej nie załaduję) może znacznie spowolnić.
Sprawdzę to.
Może masz jakieś inne pomysły - bez tej tablicy.

[drunkard]

Dokładnie tak. No ale odwołania do pamięci będą jakieś 2 razy wolniejsze niż do rejestrów (a nie 12 razy). Tak więc można sądzić, że będzie to działać przynajmniej 6 razy szybciej.
Jak na razie nic innego nie przychodzi mi do głowy, ale pomyślę, bo ciekawy problem. Swoją drogą: do czego Ci potrzebne zliczanie bitów?

[Fibik]

Kiedyś potrzebowałem takiego zliczania przy obróbce obrazów - kombinowałem z wygładzaniem krawędzi (antialiasing).
Są też inne zastosowania np. w algorytmach do kompresji, sumy kontrolne (bit parzystości).

[arigo]

jesli zalezy Ci na wydajnosci dajnej funkcji i jest ona "niskopoziomowa" to zaimplementuj ja w asm i potem w progsie taka wstawke wkleisz

[Fibik]

Co to jest funkcja 'niskopoziomowa'?

Assemblerem można przyspieszyć - góra 50%,
a tu się walczy o grube sety - przynajmniej 500%

Mam pewien pomysł ze zbiorczym sumowaniem bitów:
dodajemy 16 + 16 bitów, teraz 8 + 8 par, ...
- pięć dodawań, ale jest dość sporo manewrów pomocniczych.
Łącznie może, to być gorsze od wariantu z tablicą.

[arigo]

Co to jest funkcja 'niskopoziomowa'?

to taka ktora mozna w prosty sposob wyrazic za pomoca assemblera tak jak w tym przypadku poniewaz jest tu duzo zabawy z bitami

Assemblerem mo\u017cna przyspieszy\u0107 - góra 50%

ten sam algorytm w porownaniu w asm w porownaniu do C imho bedzie szybszy bardziej niz o 50%

caly problem opiera sie na tym ze instrukcje C nie sa tlumaczone na asm 1:1 tak wiec Twoja funkcja w C ktorej jedno przejscie mialo zajmowac 4 instrukcje w rzeczywistosci jest przez mikroproca wykonywane jako

Kod: Zaznacz cały

int nbits(unsigned n)
{
int k = 0;
for( ; n != 0; n >>= 1) k += n & 1;
// n >>= 1; - przesuwa bity liczby n, w prawo o 1
// n & 1 - operacja bitowa 'and': n AND 1
return k;
} 

08048354 <nbits>:
 8048354:       55                      push   %ebp
 8048355:       89 e5                   mov    %esp,%ebp
 8048357:       83 ec 04                sub    $0x4,%esp
 804835a:       c7 45 fc 00 00 00 00    movl   $0x0,0xfffffffc(%ebp)
 8048361:       83 7d 08 00             cmpl   $0x0,0x8(%ebp)
 8048365:       75 02                   jne    8048369 <nbits+0x15>
 8048367:       eb 10                   jmp    8048379 <nbits+0x25>
 8048369:       8b 55 08                mov    0x8(%ebp),%edx
 804836c:       83 e2 01                and    $0x1,%edx
 804836f:       8d 45 fc                lea    0xfffffffc(%ebp),%eax
 8048372:       01 10                   add    %edx,(%eax)
 8048374:       d1 6d 08                shrl   0x8(%ebp)
 8048377:       eb e8                   jmp    8048361 <nbits+0xd>
 8048379:       8b 45 fc                mov    0xfffffffc(%ebp),%eax
 804837c:       c9                      leave  
 804837d:       c3                      ret    

tak wiec z tego powodu imho tablice odpadaja poniewaz kazde odwolanie do pamieci wymaga zaglowania rejestrami oraz jest czasochlonne.

co do tego zbiorczego sumowania bitow to nie za bardzo rozumiem co miales na mysli
natomiast imho najbardziej wydajny bedzie pierwszy algorytm zaimplementowany w asm

[Fibik]

Nie oszukuj - ten kod assemblera wygenerowałeś właśnie kopmilatorem C.
Jak widać - niewiele da się tam poprawić (zoptymalizować).


Trzeci wariant wygląda tak:

int nbits(uint s)
{
s = (s & 0x55555555) + ((s >> 1) & 0x55555555); // 16 sum po 2
s = (s & 0x33333333) + ((s >> 2) & 0x33333333); // 8 sum po 4 = LHLHLHLH
s = (s & 0x0F0F0F0F) + ((s >> 4) & 0x0F0F0F0F); // 4 sum po 8 =
s = (s & 0x00FF00FF) + ((s >> 8) & 0x00FF00FF); // 2 po 16

return (s & 0xFF) + (s >> 16);
}

Przetestowałem te trzy warianty i wyniki są takie:
Czasy obliczania w milisekundach (dla kilku milionów wywołań):
1400 : 230 : 340

Po przeliczeniu na szybkość i wyrażeniu w stosunku do najwolniejszej w %:
100 : 610 : 410

Zatem:
- algorytm z tablicą jest 6 razy szybszy od pierwszego,
- wersja z binarnym połowieniem i sumowaniem bitów - 4 razy szybsza.

[arigo]

Nie oszukuj - ten kod assemblera wygenerowałeś właśnie kopmilatorem C.

pisalem wlasnie ze to jest kod asm tej funkcji w C....

[drunkard]

Do arigo: poruszasz złożone zagadnienia, warto zauważyć przynajmniej parę rzeczy:
- kompilatory posiadają opcje optymalizacyjne: najmniejszy rozmiar kodu LUB najszybsze wykonanie,
- często użycie asemblera jest zbędne (standardowe operacje na łańcuchach znaków czy np. kopiowanie obszarów pamięci - memmov lub memcpy),
- najlepiej po prostu efektywnie zakodować efektywny algorytm (ale zazwyczaj lepszy rezultat da zakodowanie w C efektywnego algorytmu, niż dłubanie w asm algorytmu nieefektywnego),
- w funkcji z ciałem "return t8[b4[0]] + t8[b4[1]] + t8[b4[2]] + t8[b4[3]]" kompilator będzie chyba skłonny skorzystać ze stosu (wyniki pośrednie operacji arytmetycznych), więc samodzielne zakodowanie tego może przynieść pewne oszczędności (-20%?).

[arigo]

do drunkard
zdaje sobie sprawe z tego co napisalem. mi chodzilo jedynie o to ze nie mozna wprost porowywac wydajnosci w jezykach wysokiego poziomu mowiac ze ten ma tyle dodawan i tyle mnozen a ten tyle i tyle wiec ten jest lepszy. sam powiedziales ze kompilator czesto stosuje optymalizacje - moze np pewne mozenia zamieniac na przesuniecia bitowe ktore sa duzo szybsze. tak samo np dodawanie liczb z rejestrow jest duzo szybsze niz dodawanie liczb ktore sa w komorkach pamieci gdyz najpierw trzeba wruzycic na stos zawartosc dwoch rejestrow, nastepnie wprowadzic do nich zawartosc powyzszych komorek wykonac operacje zapisac wynik do komorki pamieci i potem zdjac ze stosu rejestry. chodzi mi jedynie o to ze realne i w 100% dokladne porownania algorytmow mozna przeprowadzac tylko i wylacznie w ASM analizujac liczbe cykli rozkazowych

[Fibik]

Zły algorytm, przełożony na assembler, albo nawet na kod maszynowy, jest nadal złym algorytmem.

Weźmy przykładowo sortowanie.
Najprostszą metodą sortowania jest zwykłe wyszukiwanie największego elementu z
n elementów, później z n-1, dalej z n-2, i tak aż do 1.
Łączna liczba operacji: N = n + n-1 + ... + 1 = (n+1)n/2 = n^2 + ...
Zatem jest to metoda rzędu n^2.

Znany jest lepszy algorytm (quick sort)- rzędu n*log(n).

Czas wykonywania jednej operacji to t, zatem możemy obliczyć czasy sortowania:
To = n^2 * t; Tq = nlog(n)*t (jest to log o podstawie 2)
Porównajmy te metody: r = To/Tq = n/log(n)
dla n = 1000, r = 1000/10 = 100 -> qsort 100 jest razy szybsza
dla n = 1000,000, r = 1000,000/20 = 50,000 -> qsort 50tyś razy szybsza!

Widać tu, że zamiast marnować czas na doskonalenie pierwszej metody,
trzeba było ją wyrzucić na śmietnik i poszukać innej (całkowicie nowego algorytmu),
no i dzięki takiemu podejściu znaleziono nieporównywalnie szybszą metodę.

[juzef]

Nie ufam quicksortowi. Jeśli dostanie ładne dane, szybko je posortuje. Jeśli dostanie trochę gorsze (qs ma pesymistyczną złożoność \(\displaystyle{ n^2}\)), będzie działał koszmarnie długo, albo wywali się z ambitnym komentarzem w stylu stack overflow.

[Fibik]

Chyba mówisz o metodzie quickjuzef.
Są na to metody, np.: wariant wyboru mediany z trzech elementów,
plus wersja iteracyjna i takie tam drobiazgi.
Sprawdzałem to kiedyś: dla około miliona elementów maksymalny 'stos' jest równy
log(mln)*4=80 bajty, dla miliarda będzie 30*4 = 120 bytes. Dużo?

Jest jeszcze metoda zwana sortowaniem stogowym, też rzędu nlog(n).