[prog] подсчитать биты?

sergey_m

Есть у кого готовая реализация функции которая посчитает сколько битов равно 1 в параметре? Типа BIT_COUNT в MySQL.

abrek

а в чём сложность?

sergey_m

Не уверен, что мой велосипед делает это оптимально. Необходима масимально быстрая реализация.

static __inline u_char

bit_count(u_long x)

{

        int i, c = 0;

        for (i=0; i < sizeof(x) * 8; i++)

                if (x & (1 << i

                        c++;

 

        return c;

}

---

кроме того хочется универсальности. Не писать же отдельную функцию, где параметр u_char. Можно все это вместо функции сделать макросом, с передавать по ссылке. Получится универсально, но мне кажется не красиво.

abrek

ну так возьми несколько реализаций, и померь производительность (на разных процессорах)
и не отдельно, а в составе своего приложения
в зависимости от типичных исходных данных, процессора, компилятора и приложения результат будет разный скорее всего

abrek

лови, например:

static int u4_bc(int a) {

    return !(a&1) + !(a&2) + !(a&4) + !(a&8);

}

static int u8_bc(__u8 a) {

    return u4_bc(a&15) + u4_bc(a>>4);

}

int u32_bc(__u32 a) {

    int s = 0;

    while(a) {

        s += u8_bc__u8)a);

        a >>= 8;

    }

    return s;

}

---

, что соответствует

        .p2align 415

.globl u32_bc

        .type   u32_bc,@function

u32_bc:

        pushl   %edi

        xorl    %edi, %edi

        pushl   %esi

        pushl   %ebx

        movl    16(%esp %esi

        testl   %esi, %esi

        je      .L14

        .p2align 47

.L12:

        movl    %esi, %ecx

        movl    %ecx, %edx

        shrb    $4, %cl

        andl    $15, %edx

        movzbl  %cl, %ecx

        movl    %edx, %eax

        movl    %edx, %ebx

        shrl    $2, %edx

        shrl    $1, %eax

        andl    $1, %ebx

        andl    $1, %eax

        addl    %eax, %ebx

        movl    %edx, %eax

        shrl    $1, %edx

        andl    $1, %eax

        addl    %eax, %ebx

        movl    %ecx, %eax

        addl    %edx, %ebx

        shrl    $1, %eax

        movl    %ecx, %edx

        andl    $1, %eax

        andl    $1, %edx

        shrl    $2, %ecx

        addl    %eax, %edx

        movl    %ecx, %eax

        shrl    $1, %ecx

        andl    $1, %eax

        addl    %eax, %edx

        addl    %ecx, %edx

        addl    %edx, %ebx

        addl    %ebx, %edi

        shrl    $8, %esi

        jne     .L12

.L14:

        popl    %ebx

        popl    %esi

        movl    %edi, %eax

        popl    %edi

        ret

.Lfe1:

        .size   u32_bc,.Lfe1-u32_bc

        .ident  "GCC: (GNU) 3.2.3 20030316 (Debian prerelease)"

---

sergey_m

Из моей получается вот так. Как теперь оценить что лучше?

        .p2align 2,0x90

.globl bit_count

                .type            bit_count,@function

bit_count:

        pushl %ebp      # 72    movsi-2

        movl %esp,%ebp  # 74    movsi+2/1

        pushl %esi      # 75    movsi-2

        pushl %ebx      # 76    movsi-2

        movl 8(%ebp%esi       # 4     movsi+2/2

        xorl %edx,%edx  # 10    movsi+2/1

        xorl %ecx,%ecx  # 13    movsi+2/1

        movl $1,%ebx    # 62    movsi+2/1

        .p2align 2,0x90

.L6:

        movl %ebx,%eax  # 71    movsi+2/1

        sall %cl,%eax   # 24    ashlqi3+2

        testl %esi,%eax # 26    cmpsf_ccfpeq+1

        je .L5  # 27    bleu+1

        incl %edx       # 30    addsi3+1/1

.L5:

        incl %ecx       # 36    addsi3+1/1

        cmpl $31,%ecx   # 16    cmpsi_1/1

        jbe .L6 # 17    bleu+1

        movzbl %dl,%eax # 45    zero_extendqisi2+2/2

        popl %ebx       # 79    pop

        popl %esi       # 80    pop

        leave   # 81    leave

        ret     # 82    return_internal

.Lfe1:

                .size            bit_count,.Lfe1-bit_count

        .ident  "GCC: (GNU) c 2.95.4 20020320 [FreeBSD]"

---

abrek

Я уже написал, как сравнить.
Только вот мне кажется, что в реальной программе разницы не заметишь, если только задача не совсем уж странная.
Запустил бы профайлер и посмотрел, где действительно тормозит.

Dasar

http://www.rsdn.ru/Forum/Message.aspx?mid=269194

        #define g21 0x55555555ul // = 0101_0101_0101_0101_0101_0101_0101_0101

        #define g22 0x33333333ul // = 0011_0011_0011_0011_0011_0011_0011_0011

        #define g23 0x0f0f0f0ful // = 0000_1111_0000_1111_0000_1111_0000_1111

        v = (v & g21) + v >> 1) & g21);

        v = (v & g22) + v >> 2) & g22);

        v = (v + (v >> 4 & g23;

        return (v + (v >> 8) + (v >> 16) + (v >> 24 & 0x3f;

---

sergey_m

Ого. И чо самая быстрая?

Dasar

По крайней мере шагов меньше, чем при цикле. jump-ы опять же отсутствуют.

Ivan8209

Да.
На существующих машинах.
---
"А я обучался азбуке с вывесок,
листая страницы железа и жести."