4. Gesetzte Bits im Byte zählen

Gesetzte Bits im Byte zählen

  • V

    meinen bescheidenen Messungen nach braucht die Version ohne Schleife 19 Takte, die mit Schleife mindesten 32 Takte. Gemessen an Zahlen -1 bis -10000000. Als Inline-Funktion 18 und 31.
    Uih. Ist ein Funktionaufruf jeute echt so billig? Oder hab ich nur Mist gemessen?

    0
  • E

    wie misst man sowas? ich hätte jetzt im buch nachgeguckt, und von hand die takte ausgerechnet.

    kann es sein, dass der GCC inline assembler mist ist, oder bin ich nur so dumm?

    0
  • M

    ach ja:

    #include <stdio.h>

unsigned char bitcnt(unsigned char c) {
    unsigned char r = 0, x = c;
    while (c) {
        ++r;
        c &= c - 1;
    }
    return r;
}

int main(int argc, char **argv)
{
    unsigned char cnt[256];

    for (int i = 0; i < 256; i++)
        cnt[i] = bitcnt((unsigned char) i);

    FILE *f;

    if (argc < 2) f = stdout;
    else f = fopen(argv[1], "w");

    fprintf(f, "const int bitcount[256] = {\n");
    for (i = 0; i < 256; ++i) {
        fprintf(f, "\t0x%X%s%s", cnt[i], i < 255 ? "," : "", (i & 7) == 7 ? "\n" : " ");
    }
    fprintf(f, "};\n#define BITCOUNT(uc) (bitcount[(unsigned char) uc])\n");
    return 0;
}
    0
  • V

    Der hier ist 1 Takt bei mir schneller. Aber ich geh davon aus, daß auf moderneren Prozessoren als meinem Celeron400 IMUL schneller ist.

    17:   u32 countBitsTrue4(u32 x)
18:   {//http://www.df.lth.se/~john_e/gems/gem002d.html
00401000   mov         eax,ecx
00401002   shr         eax,1
00401004   and         eax,55555555h
00401009   sub         ecx,eax
19:       x = x - ((x >> 1) & 0x55555555);
20:       x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
0040100B   mov         eax,ecx
0040100D   shr         eax,2
00401010   and         ecx,33333333h
00401016   and         eax,33333333h
0040101B   add         eax,ecx
21:       x = (x + (x >> 4)) & 0x0F0F0F0F;
0040101D   mov         ecx,eax
0040101F   shr         ecx,4
00401022   add         ecx,eax
00401024   and         ecx,0F0F0F0Fh
22:       x = x + (x >> 8);
0040102A   mov         edx,ecx
0040102C   shr         edx,8
0040102F   add         ecx,edx
23:       x = x + (x >> 16);
00401031   mov         eax,ecx
00401033   shr         eax,10h
00401036   add         eax,ecx
24:       x = x & 0x3f;
00401038   and         eax,3Fh
25:       return x;
26:   }
0040103B   ret

    gemessen hab ich unter der Annahme, daß ich von vielen Messungen den mit der kürzesten Laufzeit nehmen muß, weil ich sonst cache-misses und das alles zu bezahlen hätte.
    Als Uhr nahm ich rdtsc.

    #include <iostream>
#include <ctime>
using namespace std;

typedef unsigned int u32;

u32 countBitsTrue1(u32 x) //17 takte
{//http://www.df.lth.se/~john_e/gems/gem002d.html
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x *= 0x001010101;
    x >>= 24;
    return x;
}

u32 countBitsTrue4(u32 x)//16 takte
{//http://www.df.lth.se/~john_e/gems/gem002d.html
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & 0x3f;
    return x;
}

u32 countBitsTrue2(u32 data) //30 Takte
{
    u32 result=0;
    while(data)
    {
        ++result;
        data&=data-1;
    }
    return result;
};

unsigned countBitsTrue3(unsigned v) //24 takte
{ 
    unsigned r; 
    __asm {
    mov eax, [v]
    mov edx, eax
    shr eax, 1
    and eax, 055555555h
    sub edx, eax
    mov eax, edx
    shr edx, 2
    and eax, 033333333h
    and edx, 033333333h
    add eax, edx
    mov edx, eax
    shr eax, 4
    add eax, edx
    and eax, 00F0F0F0Fh
   imul eax, 001010101h
    shr eax, 24
    mov r,   eax
   }
   return r;
}

u32 countBitsTrue5(u32 c) //30 takte
{
    u32 r = 0, x = c;
    while (x) {
        ++r;
        x &= x - 1;
    }
    return r;
}

u32 countBitsTrue6(u32 c) //98 takte
{
    static char table[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
    u32 r = 0;
    while (c) 
    {
        r+=table[c%16];
        c/=16;
    }
    return r;
}

u32 tunix(u32 x)
{
    return x;
}

#pragma warning(disable:4035)
inline u32 rdtsc()
{
    __asm rdtsc;
}

int __cdecl main()
{
    u32 min=u32(-1);
    u32 r=0;
    for(int i=0;i<10000000;++i)
    {
        u32 start=rdtsc()+36;
        r+=countBitsTrue6(~i);
        u32 stop=rdtsc();
        if(stop-start<min)
        {
            min=stop-start;
            cout<<min<<endl;
        }
    }
    cout<<"fertig"<<endl;
    cout<<r<<endl;
    return 0;
}

    [ Dieser Beitrag wurde am 27.08.2002 um 20:58 Uhr von volkard editiert. ]

    0
  • -

    Also wenn es echt auf Speed ankommt würde ich sagen:
    nicht Rechnen,
    sondern Nachschaun!

    d.h. wir richten uns zunächst eine große Tabeller ein. Ich würde raten mit 256 Einträgen (für jedes byte einen).

    dann kann man die Ergebnisse über einfache lookups holen.
    Zur Generierung der Tabellen sollte man wohl einen der oben genannte Algorythmen benutzen.

    0
  • M

    Hi all ...

    ich habe -bg-'s Vorschlag mal umgesetzt ...

    #include <time.h>
#include <stdio.h>

typedef unsigned int u32;

u32 countBitsTrue4(u32 x)//16 takte
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & 0x3f;
    return x;
}

int tab[0xFFFF];

u32 count_bits(u32 x)
{
    x = tab[x & 0xFFFF] + tab[x>>16];

    return x;
}

#define TEST_PATTERN   0x12345678

int main(void)
{
    int i;
    clock_t before;
    double elapsed;

    for (i = 0; i < 0xFFFF; i++)
        tab[i] = countBitsTrue4(i);

    printf("x = %d\n", count_bits(TEST_PATTERN));

    before = clock();
    for (i = 0; i < 100000000; i++)
        count_bits(TEST_PATTERN);
        // countBitsTrue4(TEST_PATTERN);

    elapsed = clock() - before;
    printf("Funktion benötigte %.3lf Sekunden\n", elapsed/CLOCKS_PER_SEC);

    return 0;
}

    Die Tabellen-Variante ist um einiges schneller ... dafür muss man halt zuerst die Tabelle initialisieren ...

    0
  • M

    hihi, der is mein schnellster, den ich anzubieten habe (ohne inlining!):

    __declspec(naked) unsigned __stdcall bitcntC(unsigned v) { __asm {
     mov eax, [ESP+4]
     mov edx, eax
     shr eax, 1
     and eax, 055555555h
     sub edx, eax
     mov eax, edx
     shr edx, 2
     and eax, 033333333h
     and edx, 033333333h
     add eax, edx
     mov edx, eax
     shr eax, 4
     add eax, edx
     and eax, 00F0F0F0Fh
    imul eax, 001010101h
     shr eax, 24
     ret 4
}}

    auf meinem Athlon XP 2000+ hübsche 40 Mio. Aufrufe in einer halben sekunde. 50 ms schneller als die nicht naked version *g*

    0
  • M

    @mady: beim tabellenerstellen könntest du _viel_ *g* zeit sparen.

    0
  • E

    @-bg-: geniale idee! wie beim base64 encode!

    ich glaub dieses verfahren könnte man durchaus öfters benutzen!

    0
  • M

    ich dachte meine antwort zum table lookup (ein programm generator war das) wär lustig genug...
    (das mit "ach ja:" beginnt)

    [ Dieser Beitrag wurde am 04.09.2002 um 15:31 Uhr von Mr. n editiert. ]

    0
  • E

    damit ich auch mal mit reden kann... hat jemand eine tabelle über die takte, die bestimmte assembler anweisungen verbrauchen? hatte mal gesucht, aber nix gefunden 😞

    0
  • M

    das kommt auf deine cpu an. aber in meinem tollen link steht da auch was zu drin. textseite 259, acro-seite 279

    0
  • P

    Hast du auch schon im Forum gesucht?
    Clock-Tabelle

    lg, phreaking

    0
  • E

    nope, nur google. und bin nicht auf den begriff Clocks gekommen. Danke 🙂

    0
  • M

    Original erstellt von Mr. n:
    @mady: beim tabellenerstellen könntest du _viel_ *g* zeit sparen.

    Naja ... mir ging's erstmal darum, ein Beispiel der Tab.Variante zu zeigen.

    Normalerweise startet eine solche Initialisierung am Anfang eines Programms und damit ist das nicht so schlim, wenn's ein paar sek. länger dauert. Aber trotzdem bin ich auf Deinen Vorschlag gespannt, wie man das schneller machen kann!

    0
  • P

    Ich denke, er meint damit, einfach die Tabelle fix in den Source hinein kompilieren, ich würde es nämlich auch so machen 😉

    lg, phreaking

    0
  • E

    dito. wird aber ein eklig langer maskierter string *g+

    0
  • P

    Die Tabelle aus einer Datei in den Speicher zu holen, wäre auch möglich, aber ob das schneller ist... 😕

    lg, phreaking

    0
  • M

    beim hardcoding wirds doch auch aus ner datei in 'n speicher geladen *g* - meistens zumindest

    0
  • ?

    Ich dachte aber eher an eine schnellere Methode, als die oben vorgestellte.... mir ist auch schon was eingefallen, wie man das besser machen kann ...

    Aber dazu brauch' ich nen Compiler zum testen, den ich grad nicht hab....

    0
Anmelden zum Antworten