Assembly zliczanie jedynek w liczbie binarnej

Kordoba

2020-03-22T16:56:45+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 154

0

Witam,
Piszę program w assemblerze w którym podaję liczbę w postaci dziesiętnej, a program wypisuje liczbę jedynek znajdujących się w postaci binarnej tej liczby.
napisałem poniższy kod:

Kopiuj

convert:
    mov eax, ebx
    mov ecx, 2
    xor edx, edx
    div ecx
    cmp edx, 0
    je resume
    inc [result]
 
resume:
    mov ebx, eax
    cmp eax, 0
    jne convert

W rejestrze ebx znajduje się liczba w której trzeba zliczyć jedynki.
Dla liczb z przedziału <0,999> program działa poprawnie, lecz dla liczb >999 występuje anomalia.
Do wyniku(ilości jedynek) jest dodawana jakby "liczba dziesięć". Pokażę to na przykładzie:

dla 512 wynikiem jest 1 -->prawidłowo
dla 999 wynikiem jest 8 -->prawidłowo
dla 1024 wynikiem jest 11 (czyli jakby odjąć 10, wynik byłby prawidłowy)
dla 1021 wynikiem jest 19 (czyli jakby odjąć 10, wynik byłby prawidłowy)
dla 2047 wynikiem jest 21(czyli jakby odjąć 10, wynik byłby prawidłowy)

Mógłby ktoś pomóc z tym problemem?

rajszym

2020-03-22T17:08:44+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 62

1

Dzielenie jest w tym przypadku najmniej potrzebną instrukcją.
Zainteresuj się raczej instrukcją shr i flagą C.

Wibowit

2020-03-22T17:11:11+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

2

Instrukcja POPCNT z SSE 4.2 robi wprost całą robotę, więc może zacznij najpierw od kodu opartego o POPCNT i dopiero jak będzie działał to zmień na coś swojego jeśli bardzo chcesz.

stivens

2020-03-22T17:11:18+01:00

Rejestracja: dni
Ostatnio: dni

2

rajszym napisał(a):

Dzielenie jest w tym przypadku najmniej potrzebną instrukcją.
Zainteresuj się raczej instrukcją shr i flagą C.

Nope. Tutaj potrzebne jest podejscie divide and conquer. Dosyc klasyczne zadanie. Ewentualnie gotowa instrukcja - nie wiem co dokladnie ma zrobic.

Kordoba

2020-03-22T17:47:18+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 154

0

POPCNT robi robotę, lecz nie mogę używać żadnych instrukcji z rozszerzeń ani wywoływać funkcji z C. Jedynie podstawowe komendy z assemblera

Wibowit

2020-03-22T17:48:59+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

1

A z POPCNT działa dobrze dla każdej liczby?

yarel

2020-03-22T17:51:34+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 2384

2

Klasyczny problem, klasyczne rozwiązania -> https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Kordoba

2020-03-22T18:20:18+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 154

0

ostatecznie użyłem shr
dzięki wszystkim za pomoc :)

stivens

2020-03-22T18:25:56+01:00

Rejestracja: dni
Ostatnio: dni

0

Kordoba napisał(a):

ostatecznie użyłem shr
dzięki wszystkim za pomoc :)

U mnie by takie rozwiazanie nie przeszlo no ale okey

@Wibowit:

Jak tu niby zrobić efektywne "dziel i rządź"?

Jakos tak:

Zakladajac, ze

Architektura procesora pozwala na wykonywanie kilku instrukcji rownolegle
Dodawanie trwa 1 cykl

to jeden krok bedzie trwac 2 cykle a krokow bedzie log(#bitow)
Moglem cos pomieszac.

Algorytmy z https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive wydaja sie bardziej wyrafinowane to pewnie lepsze beda ;)

Wibowit

2020-03-22T19:32:38+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

0

@stivens:
Ilość pracy jest ta sama co w naiwnym algorytmie, więc w tej kwestii zysk jest zerowy, a nawet ujemny bo zwiększasz narzut wywołaniami rekurencyjnymi. Zrównoleglenie jest jedną z zalet strategii "dziel i rządź" ale wątpię by po zaimplementowaniu chociaż zbliżyło się wydajnością do zwykłego liczenia po bajtach (za pomocą LUTów = look-up table) zamiast po bitach: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable Zysk wydajnościowy z "dziel i zwyciężaj" mógłby być co najwyżej na jakieś czysto teoretycznej nigdy nie zaimplementowanej maszynie, a w zadaniu chodzi przecież o realną implementację na zwykłym pececie. Gdyby mi ktoś dał do zakodowania coś na procki x86 to myślałbym w kategoriach wydajności na prockach x86.

stivens

2020-03-22T19:33:17+01:00

Rejestracja: dni
Ostatnio: dni

0

Tutaj nie ma zadnych wywolan rekurencyjnych..

Wibowit

2020-03-22T19:39:04+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

0

Ja tam nie widzę żadnych wywołań tylko jakąś zeskanowaną kartkę :) Za Wikipedią https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm (pogrubienie ode mnie):

Divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

Teoretycznie ta rekurencja jest. Nie musi jej być widać wprost w kodzie docelowym, ale semantycznie to chyba każdy algorytm "dziel i zwyciężaj" tę rekurencję posiada. Są jakieś bez rekurencji? Jak by się to miało do definicji?

stivens

2020-03-22T19:43:05+01:00

Rejestracja: dni
Ostatnio: dni

1

https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685

Motywacja

goose_

2020-03-22T19:49:27+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 97

0

Nie wiem czy to pomoże, bo tak na szybko ale może coś takiego.

Kod w C.

Kopiuj

#include <stdio.h>

int main()
{
    int val = 2047;
    int i, c;
    #define BITSSIZE 32
    for (i = 0; i < BITSSIZE; ++i) {
        if (((1 << i) & val) > 0) {
            c++;
        }
    }
    printf("%d \n", c);
    return 0;
}

To co wygenerował kompilator

Kopiuj

000000000040052d <main>:
  40052d:	55                   	push   %rbp
  40052e:	48 89 e5             	mov    %rsp,%rbp
  400531:	48 83 ec 10          	sub    $0x10,%rsp
  400535:	c7 45 fc ff 07 00 00 	movl   $0x7ff,-0x4(%rbp)
  40053c:	c7 45 f4 00 00 00 00 	movl   $0x0,-0xc(%rbp)
  400543:	eb 1d                	jmp    400562 <main+0x35>
  400545:	8b 45 f4             	mov    -0xc(%rbp),%eax
  400548:	ba 01 00 00 00       	mov    $0x1,%edx
  40054d:	89 c1                	mov    %eax,%ecx
  40054f:	d3 e2                	shl    %cl,%edx
  400551:	89 d0                	mov    %edx,%eax
  400553:	23 45 fc             	and    -0x4(%rbp),%eax
  400556:	85 c0                	test   %eax,%eax
  400558:	7e 04                	jle    40055e <main+0x31>
  40055a:	83 45 f8 01          	addl   $0x1,-0x8(%rbp)
  40055e:	83 45 f4 01          	addl   $0x1,-0xc(%rbp)
  400562:	83 7d f4 1f          	cmpl   $0x1f,-0xc(%rbp)
  400566:	7e dd                	jle    400545 <main+0x18>
  400568:	8b 45 f8             	mov    -0x8(%rbp),%eax
  40056b:	89 c6                	mov    %eax,%esi
  40056d:	bf 14 06 40 00       	mov    $0x400614,%edi
  400572:	b8 00 00 00 00       	mov    $0x0,%eax
  400577:	e8 94 fe ff ff       	callq  400410 <printf@plt>
  40057c:	b8 00 00 00 00       	mov    $0x0,%eax
  400581:	c9                   	leaveq 
  400582:	c3                   	retq   
  400583:	66 2e 0f 1f 84 00 00 	nopw   %cs:0x0(%rax,%rax,1)
  40058a:	00 00 00 
  40058d:	0f 1f 00             	nopl   (%rax)

Ogólnie koncepcja taka że robisz przesunięcie i sprawdzasz jako maske liczbe, jeśli jest równe 0 wtedy wartośc jest true i liczysz ile jest tych jedynek. W pythonie jakoś tak to leci

Kopiuj

a = 1122
>>> bin(a)
'0b10001100010'
>>> ((1 << 9) & a)
0
>>> ((1 << 2) & a)
0
>>> ((1 << 1) & a)
2
>>> ((1 << 3) & a)
0
>>> ((1 << 4) & a)
0
>>> ((1 << 5) & a)
32
>>> ((1 << 6) & a)
64
>>> ((1 << 7) & a)
0
>>> ((1 << 7) & a) > 0
False
>>> ((1 << 6) & a) > 0
True

Wibowit

2020-03-22T19:52:20+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

0

@stivens:
Procesor superskalarny może wykonywać wiele instrukcji naraz, ale instrukcje wykonywane naraz muszą być od siebie niezależne (no chyba, że procesor wykonuje przewidywanie np skoków, ale wtedy jest ryzyko że predykcja była błędna i obliczenia trzeba powtórzyć). W tejn funkcji int pop(unsigned x) { ... } prawie nie ma miejsca na jednoczesne wykonywanie więcej niż jednej instrukcji.

stivens

2020-03-22T19:53:57+01:00

Rejestracja: dni
Ostatnio: dni

1

Wibowit napisał(a):

@stivens:
Procesor superskalarny może wykonywać wiele instrukcji naraz, ale instrukcje wykonywane naraz muszą być od siebie niezależne (no chyba, że procesor wykonuje przewidywanie np skoków, ale wtedy jest ryzyko że predykcja była błędna i obliczenia trzeba powtórzyć). W ten funkcji int pop(unsigned x) { ... } prawie nie ma miejsca na jednoczesne wykonywanie więcej niż jednej instrukcji.

Pewnie najlepiej by bylo zaimplementowac oba i zobaczyc w ile cykli sie wykonuja, ale mi sie nie chce ;s

Moze ustalmy uwage.

To:

Kopiuj

while (x > 0) {
    if (x & 1) cnt++;
    x >>= 1;
}

vs

Wibowit

2020-03-22T20:06:08+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

0

goose_ napisał(a):

Nie wiem czy to pomoże, bo tak na szybko ale może coś takiego.

Kod w C.

Kopiuj

#include <stdio.h>

int main()
{
    int val = 2047;
    int i, c;
    #define BITSSIZE 32
    for (i = 0; i < BITSSIZE; ++i) {
        if (((1 << i) & val) > 0) {
            c++;
        }
    }
    printf("%d \n", c);
    return 0;
}

Zapomniałeś c = 0 na początku i operujesz na niezainicjalizowanej pamięci.

stivens napisał(a):

Pewnie najlepiej by bylo zaimplementowac oba i zobaczyc w ile cykli sie wykonuja, ale mi sie nie chce ;s

Chyba nie czytałeś tego co podałeś ze zrozumieniem :] Masz:

figure 5-1, gdzie jest rozrysowany algorytm,
potem masz tłumaczenie wprost na kod w C: "the method illustrated in figure 5-1 can be commited to C code as"
potem masz rozpisane przemyślenia n.t. optymalizacji tego kodu i z nich powstaje funkcja int pop(unsigned x) { ... }

stivens

2020-03-22T20:06:47+01:00

Rejestracja: dni
Ostatnio: dni

1

Ale juz ta niezoptymalizowana wersja jest lepsza od naiwnego podejscia

I mowie o tej niezoptymalizowanej bo taka mialem na mysli dolaczajac do tematu :)

naive.c

Kopiuj

#include <stdio.h>
#include <limits.h>
#include <stdint.h>

uint64_t pop(uint64_t x);

int main() {
    uint64_t t[10000];

    for (int i = 0; i < 10000; i++) {
        t[i] = pop(i);
    }

    return 0;
}


uint64_t pop(uint64_t x) {
    uint64_t cnt = 0;
    while (x > 0) {
        if (x & 1) cnt++;
        x >>= 1;
    }

    return cnt;
}

opt.c

Kopiuj

#include <stdio.h>
#include <limits.h>
#include <stdint.h>

uint64_t pop(uint64_t x);

int main() {
    uint64_t t[10000];

    for (int i = 0; i < 10000; i++) {
        t[i] = pop(i);
    }

    return 0;
}

uint64_t pop(uint64_t x) {
    x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F);
    x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF);
    x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF);
    x = (x & 0x00000000FFFFFFFF) + ((x >> 32) & 0x00000000FFFFFFFF);

    return x;
}

perf

Kopiuj

stivens@S410UA ~/test $ gcc naive.c -o naive
stivens@S410UA ~/test $ gcc opt.c -o opt
stivens@S410UA ~/test $ sudo ./perf.sh ./opt

 Performance counter stats for './opt':

           454 394      cycles:u                                                    
                
             4 746      bus-cycles:u                                                
           773 099      instructions:u            #    1,70  insn per cycle         
            49 947      branches:u                                                  
             1 412      branch-misses:u           #    2,83% of all branches        
             8 666      cache-references:u                                                                              

       0,000816440 seconds time elapsed

       0,000882000 seconds user
       0,000000000 seconds sys


stivens@S410UA ~/test $ sudo ./perf.sh ./naive

 Performance counter stats for './naive':

           437 509      cycles:u                                                      (13,49%)                                  
            25 305      bus-cycles:u                                                
         1 233 026      instructions:u            #    2,82  insn per cycle         
           317 181      branches:u                                                  
            54 966      branch-misses:u           #   17,33% of all branches        
             8 711      cache-references:u                                          
                                   

       0,001668939 seconds time elapsed

       0,001748000 seconds user
       0,000000000 seconds sys


stivens@S410UA ~/test $

Jak zniszczyc naive.c?

Kopiuj

    for (int i = 0; i < 10000; i++) {
        t[i] = pop( UINT64_MAX - i);
    }

Kopiuj

stivens@S410UA ~/test $ sudo ./perf.sh ./opt

 Performance counter stats for './opt':

           458 326      cycles:u                                                                                    
             4 788      bus-cycles:u                                                
           783 098      instructions:u            #    1,71  insn per cycle         
            49 946      branches:u                                                  
             1 376      branch-misses:u           #    2,75% of all branches        
             8 468      cache-references:u                                          
                                

       0,000866206 seconds time elapsed

       0,000926000 seconds user
       0,000000000 seconds sys


stivens@S410UA ~/test $ sudo ./perf.sh ./naive

 Performance counter stats for './naive':

         6 024 886      cycles:u                                                      (47,35%)                               
            65 459      bus-cycles:u                                                
         5 368 493      instructions:u            #    0,89  insn per cycle         
         1 349 949      branches:u                                                  
            66 960      branch-misses:u           #    4,96% of all branches        
             8 971      cache-references:u                                          
     
       0,003396542 seconds time elapsed

       0,003393000 seconds user
       0,000000000 seconds sys

Wibowit

2020-03-22T21:12:41+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

0

Wykombinowałem kod dla zliczania bitów w 32-bitowych rejestrach https://godbolt.org/z/_C_xYo :

Kopiuj

#include <stdio.h>

int main()
{
    unsigned val = 2047;
    unsigned result;
    asm("\n"
        // mov reg, reg is resolved during register renaming
        // so 0 cycles spent in ALUs
        "mov r8d, %[val]\n"
        "mov r9d, %[val]\n"
        "mov r10d, %[val]\n"
        "mov r11d, %[val]\n"
        // some zeroing idioms are recognized by decoder
        // so 0 cycles spent in ALUs
        "xor r12, r12\n"
        "xor r13, r13\n"
        "xor r14, r14\n"
        "xor r15, r15\n"
        // ryzen can do 4 [shr/adc r,i] in a cycle
        // skylake only 1 adc or 2 shr
        // "shr r8, 0\n"
        "shr r9, 8\n"
        "shr r10, 16\n"
        "shr r11, 24\n"
        "mov rcx, 8\n"
        // four independent pairs of instructions
        "loop:\n"
        "shr r8, 1\n"
        "adc r12, 0\n"
        "shr r9, 1\n"
        "adc r13, 0\n"
        "shr r10, 1\n"
        "adc r14, 0\n"
        "shr r11, 1\n"
        "adc r15, 0\n"
        "dec rcx\n"
        "jnz loop\n"
        "add r12, r13\n"
        "add r14, r15\n"
        "add r12, r14\n"
        "mov %[result], r12d\n"
        : [result] "=r" (result)
        : [val] "r" (val)
        : "rcx","r8","r9","r10","r11","r12","r13","r14","r15"
    );
    printf("%u\n", result);
    return 0;
}

ale to raczej pod Ryzena, bo ten ma znacznie większą przepustowość dla kluczowych instrukcji w tym algorytmie (shr r,i i adc r,i) niż Skylake.

stivens

2020-03-22T21:15:59+01:00

Rejestracja: dni
Ostatnio: dni

0

No i pamietaj, ze nie mowie ze D&C jest najlepszy a jedynie, ze lepszy od podejscia naiwnego. I w sumie moim zdaniem ciekawy ;)

Azarien

2020-03-23T09:26:51+01:00

Rejestracja: dni
Ostatnio: dni

2

OK, tylko jaki sens to optymalizować pod Haswelle i Ryzeny, skoro tam jest POPCNT. Chyba że ten POPCNT jednak słaby się okaże...
Raczej wydajnością bym się przejmował na prockach które nie mają tej instrukcji.