[c] integer inverteren in 8bit

[Verwijderd]

Hallo,

ik wil in c het volgende

ik wil een waarde die ik als een integer binnenkrijg van de hardware binair spiegelen(er komt binnen 10101111 en ik wil er van maken: 11110101) heeft iemand een idee hoe ik dit kan doen...

ik heb de volgende code

code:

int input;

input = 25;
itoa(input binair, 2);
printf("voor: input: %i binair: %s", input, binair);

input = ~input;
itoa(input binair, 2);
printf("na: input: %i binair: %s", input, binair);

heeft iemand een idee hoe ik dit kan aanpakken ?

[ Voor 8% gewijzigd door Verwijderd op 18-03-2004 12:38 ]

[Emmeau]

edit: verkeerd gelezen, zal even opnieuw kijken (je topictitel spreekt over inverteren, maar je post over spiegelen)

[ Voor 114% gewijzigd door Emmeau op 18-03-2004 12:43 ]

[Verwijderd]

Emmeau schreef op 18 maart 2004 @ 12:38:
255 - jouw getal ?

jij zegt dit dus

code:

int input;

input = 25;
itoa(input binair, 2);
printf("voor: input: %i binair: %s", input, binair);

input = 255 - input;
itoa(input binair, 2);
printf("na: input: %i binair: %s", input, binair);

dan zet ik 1000000 om naar 111111 en niet 1000000 naar 0000001

[ Voor 12% gewijzigd door Verwijderd op 18-03-2004 12:42 ]

[Verwijderd]

Uitgaande van het feit dat je alleen de laatste acht bits wilt omdraaien zou je volgens mij het onderstaande kunnen doen. Maar misschien zijn er wel snellere mogelijkheden.

code:

int input;
unsigned char in, out=0x00;
unsigned char i;

in = (unsigned char)input & 0xFF;

for(i=0; i<8; i++)
{
  out << 1;
  out = out & 0xFE;
  out = out | ((in >> i) & 0x01);
}
input = out;

[miw]

Je kan dit uitrekenen met behulp van de shift operator. Een kort voorbeeldje ter illustratie. Je kan het natuurlijk veel netter opschrijven.

code:

int i, flip = 0;
for (i=1; i<=8; i++) {
  if ((input & (1<<i)) != 0)
      flip |= 0x10 >> i;
}

[Verwijderd]

Een beetje DSP heeft hier een speciale instructie voor. Of ben je niet de butterflies van een IDCT aan het uitrekenen?

Anywayzz dit is een heel bekend probleem met legio oplossingen. Het feit dat sommige DSPs dit zelfs in hardware kunnen zegt genoeg, volgens mij.


edit:
Indien je geen Butterflies voor Lee's algorithme aan het uitrekenen bent: Waarom zou je dit in 's hemels naam willen??

[ Voor 20% gewijzigd door Verwijderd op 18-03-2004 13:03 ]

[Verwijderd]

suntsu schreef op 18 maart 2004 @ 12:54:
Je kan dit uitrekenen met behulp van de shift operator. Een kort voorbeeldje ter illustratie. Je kan het natuurlijk veel netter opschrijven.

code:

int i, flip = 0;
for (i=1; i<=8; i++) {
  if ((input & (1<<i)) != 0)
      flip |= 0x10 >> i;
}

Probleempjes die hierbij ontstaan:
- het if-statement levert altijd true op (<< shift 1-en binnen en dit is dus altijd ongelijk aan 0)
- de eeste bit (bit 0) wordt niet meegenomen
- je shift vanaf bit 5 op de flip (moet bit 8 (= 0x80) zijn)

Dit werkt dan denk ik beter:

code:

int i, flip = 0;
for (i=0; i<8; i++) {
  if ((input & (0x80>>i)) != 0)
      flip |= 0x80 >> 7-i;
}

[Verwijderd]

Tjonge... die oplossing in C zien er wel vreselijk traag uit. Mag je niet gewoon 16 assembly instructies inlinen? Namelijk 8x een combinatie van
"shift left" waarbij het MSB de carry in schuift en "rol right" waarbij de carry het MSB in schuift

Lijkt mij een factortje 100 sneller of zo...

[Verwijderd]

Als ik het goed begrijp, wil je dat
bit 0 -> bit 31
[...]
bit n -> bit 31 - n
[...]
bit 31 -> bit 0

Volgens mij kun je hier wel een leuk algorithme voor bedenken, maar als het puur om 8 bit -> 8 bit gaat en snelheid, kun je het beste een lookuptable maken van 256 bytes, waarbij je de waarde als 8 bits unsigned gebruikt als index om de bit-reverse waarde te vinden of zo.

dus zoiets als:

C:

uint8_t rev_bits_table[256] = 
{
  0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xe0,
  0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xf0,
  ... /* enzovoort */
};

uint8_t reverse = rev_bits_table[(unsigned)input & 0xff];

[Verwijderd]

Een 256-bytes look-up table: Vreselijk wat een geheugen-verslindende oplossingen worden hier aangedragen.

't is toch wel te merken dat de programmeurs van tegenwoordig niet meer weten hoe het is om te programmeren wanneer iedere byte telt

"Vroeger, toen het gras nog groen was, en de vogeltjes nog floten, toen.... Toen geheugen mog per bit werd verkocht, toen..." Toen heb ik regelmatig routines geprogrammeerd die aangeroepen op adres N een bepaalde funktie uitvoerden, maar aangeroepen op adres N+1 een totaal andere funktie uitvoerden.
Microsoft bediende zich overigens zelf ook van die smerige programmeer truken. (Iemand de MSX ROM-BIOS een keer voor de lol gedisassembled?)
Dat waren nog eens tijden

[.oisyn]

Verwijderd schreef op 18 maart 2004 @ 13:05:
Lijkt mij een factortje 100 sneller of zo...

right, overdrijven is ook een vak

Bovendien is het echt onzin zo moeilijk te doen als hij maar slechts enkele getallen probeert te converteren

[Verwijderd]

suntsu schreef op 18 maart 2004 @ 12:54:
Je kan dit uitrekenen met behulp van de shift operator. Een kort voorbeeldje ter illustratie. Je kan het natuurlijk veel netter opschrijven.

C:

int i, flip = 0;
for (i=1; i<=8; i++) {
  if ((input & (1<<i)) != 0)
      flip |= 0x10 >> i;
}

Ik denk dat je bedoelde (twee wijzigingen):

C:

int i, flip = 0;
for (i=0; i < 8; i++) {
  if ((input & (1<<i)) != 0)
      flip |= 0x80 >> i;
}

offtopic:
Gebruik liever [code=c][/code] tags voor C code, dan heb je tenminste syntax-highlighting...

[ Voor 11% gewijzigd door Verwijderd op 18-03-2004 13:44 ]

[Verwijderd]

Verwijderd schreef op 18 maart 2004 @ 13:10:
Een 256-bytes look-up table: Vreselijk wat een geheugen-verslindende oplossingen worden hier aangedragen.

't is toch wel te merken dat de programmeurs van tegenwoordig niet meer weten hoe het is om te programmeren wanneer iedere byte telt

Sja, tegenwoordig is geheugenruimte een stuk goedkoper als snelheidsverlies.
Sjee, 256bytes, dat past zowat nog in mijn signature!!!

Het was mij dan ook zeker niet duidelijk, als dit om een embedded project gaat, waar elke bit telt...

[PiepPiep]

C:

int c;

c=((c&0x0F)<<4)+((c&0xF0)>>4);
c=((c&0x33)<<2)+((c&0xCC)>>2);
c=((c&0x55)<<1)+((c&0xAA)>>1);

Zoiets?

[Verwijderd]

factortje 100 sneller

right, overdrijven is ook een vak

Totally off-topic, natuurlijk. Maar ik denk dat die factor 100 toch aardig in de buurt komt. Op een moderne processor zoals een Pentium, zijn die 16 schuif instructies gewoon in volgorde zonder sprongen of lussen te schedulen. Waarschijnlijk is er zelfs nog wel een integer ALUtje vrij tussen de andere berekingen en bewerkuingen die het programma moet uitvoeren waar deze 16 instructies nog bij kunnen worden gescheduled. Verder zijn ook geen variabelen nodig (voor tellers e.d.) dus cache en geheugen access spelen geen rol. Maximaal kost het dus 16 klokslagen, maar effectief zal het (afhankelijk van de rest van het programma) 8 clock cycles kosten (ongeveer)

Het voorbeeldje waarbij een for-next lus wordt gebruikt, en twee schuif operaties plaats vinden binnen de lus en waarbij die schuifoperaties ook nog een variabel argument hebben (namelijk i) [O ramp!] en verder ook nog een if-then-else constructie. En natuurlijk nog in totaal 3 C-variabelen worden gebruikt... tja... da's gewoonweg een ramp...
Een lus en een if-then, dat zijn dus 2 branches die een pijplijn flush forceren. Schuifoperaties met variabel argumnet zijn ook niet fijn.
En dan nog 3 C-variabelen waarvan het maar de vraag is of ze door de compiler inderdaad op een register worden gemapt.
Dat gaat echt honderden of duizenden clock-cycles kosten!

En dan gaan jullie dit stukje code nog in een sub-routine zetten ook natuurlijk, waardoor ook nog de hele C-subroutine-caal overhead wordt toegvoegd

[Verwijderd]

Jaaaa... de oplossing van Pieppiep! Die is mooi!!! Prachtig!!! Ik had het zelf niet beter kunnen doen!


[Overigens heeft de Topic Starter nog steeds niet verteld, waarom hij/zij dit nu eigenlijk wil. Ik kan namelijk maar erg weinig redenen bedenken...]

[ Voor 44% gewijzigd door Verwijderd op 18-03-2004 13:28 ]

[Juicy]

Verwijderd schreef op 18 maart 2004 @ 13:10:
Toen heb ik regelmatig routines geprogrammeerd die aangeroepen op adres N een bepaalde funktie uitvoerden, maar aangeroepen op adres N+1 een totaal andere funktie uitvoerden.

Dat heeft niet met geheugenbesparing te maken, eerder met "niet onderhoudbare software" in elkaar te draaien ...

Microsoft bediende zich overigens zelf ook van die smerige programmeer truken. (Iemand de MSX ROM-BIOS een keer voor de lol gedisassembled?)
Dat waren nog eens tijden

Wat heeft Microsoft met MSX te maken ?

[MSalters]

offtopic:
MicroSoft eXtended basic

[Verwijderd]

Dat heeft niet met geheugenbesparing te maken, eerder met "niet onderhoudbare software" in elkaar te draaien ...

Ach ja... maar 20 jaar geleden (het MSX tijdperk) was geheugen nog ERG duur in vergelijking met de prijs van een stelltje programmeurs. Zeker voor producten als een home-computer waar er miljoenen van werden verkocht. Verder was "onderhoud" van de code toen helemaal niet van belang, omdat er toch geen nieuwe versie kwam. Versie 1 was gewoon het eindproduct. (Hoewel er natuurlijk wel een MSX2 is gekomen. Echter, de eerste 32KB ROM van een MSX2 is precies gelijk aan de 32KB ROM van een MSX1. Dus van versie beheer was nog steeds geen sprake.

Ik geef onmiddellijk toe dat de wereld nu geheel anders in elkaar zit! Maar dat wil niet zeggen dat je dan maar meteen 'dom' moet gaan programeren Een beetje nadenken mag nog steeds

Wat heeft Microsoft met MSX te maken ?

MSX betekent "Micro Soft eXtended". ASCII (de hardware ontwerpers en systeem-archtecten (voor zover je daar in die tijd over kon spreken)) had Bill's Microsoft gevraagd de software voor hun nieuwe computer te programeren. Bill stemde in, onder de voorwaarde dat het product Bill's naam zou dragen: Vandaar de naam MSX...

(De X van eXtented komt overigens voort uit het feit dat de Basic taal van MSX een uitbreiding was op de mogelijkheden en functionaliteit van eerdere versies van Bill's basic. (Zoals bijvoorbeeld GWbasic bekend van de 8086))


[Tot zover deze bloemlezing computer geschiedenis...]

[ Voor 5% gewijzigd door Verwijderd op 18-03-2004 13:37 ]

[MSalters]

Verwijderd schreef op 18 maart 2004 @ 13:22:
[...]

Totally off-topic, natuurlijk. Maar ik denk dat die factor 100 toch aardig in de buurt komt. ...
Het voorbeeldje waarbij een for-next lus wordt gebruikt, en twee schuif operaties plaats vinden binnen de lus en waarbij die schuifoperaties ook nog een variabel argument hebben (namelijk i) [O ramp!] en verder ook nog een if-then-else constructie. En natuurlijk nog in totaal 3 C-variabelen worden gebruikt... tja... da's gewoonweg een ramp...

Benchmarkje? Disassembly? Ok gewoon jouw idee hoe een compiler werkt?

De loop is van beperkte fixed lengte; een optimizer kan uitrekenen of het slimmer is die loop te unrollen. Na de unroll zijn de shifts vervolgens over een fixed lengte. 3 C integers kunnen zelfs op een x86 nog in registers. Kortom, er is geen enkele reden waarom een beetje optimizer langzame code zou moeten opleveren.

[EXX]

Verwijderd schreef op 18 maart 2004 @ 13:10:
"Vroeger, toen het gras nog groen was, en de vogeltjes nog floten, toen.... Toen geheugen mog per bit werd verkocht, toen..." Toen heb ik regelmatig routines geprogrammeerd die aangeroepen op adres N een bepaalde funktie uitvoerden, maar aangeroepen op adres N+1 een totaal andere funktie uitvoerden.
Microsoft bediende zich overigens zelf ook van die smerige programmeer truken. (Iemand de MSX ROM-BIOS een keer voor de lol gedisassembled?)
Dat waren nog eens tijden

U vraagt, wij draaien
Dit is dan wel niet van een MSX computer, maar van een TRS-80 kloon. Das ook een Microsoft Basic dialect:

code:

; SUB for SMUL, SDIV, DMUL and DDIV
; Process exponents and signs

; Entry for DDIV

  00907 3EFF            LD      A,0FFH          ;Flag = FFH
* 00909 2EAF            LD      L,AFH           ;--

; Entry for DMUL

  0090A   AF            XOR     A               ;Flag = 00H
  0090B 212D41          LD      HL,412DH        ;HL -> MSB (Y)
  0090E 4E              LD      C,(HL)          ;C = MSB (Y)
  0090F 23              INC     HL              ;HL -> Exp (Y)
  00910 AE              XOR     (HL)            ;DMUL: A = Exp (Y)
                                                ;DDIV: A = -Exp (Y) - 1
  00911 47              LD      B,A             ;B = Exp
  00912 2E00            LD      L,00H           ;Continue as with SMUL

Het byte op 090AH wordt als het ware dubbel gebruikt.

hier nog zo iets:

code:

; TEST2: SNG function for X
; Test single or double precision number in X if smaller,
; equal or greater then zero
; ?TM Error when X contains a STR
;
; I: X = single or double precision number to be tested
; O: if X < 0: A = FFH, C-flag = 1, Z-flag = 0, S-flag = 1
; O: if X = 0: A = 00H, C-flag = 0, Z-flag = 1, S-flag = 0, P/V-flag = 1
; O: if X > 0: A = 01H, C-flag = 0, Z-flag = 0, S-flag = 0


  00955 3A2441          LD      A,(4124H)       ;A = Exp (X)
  00958 B7              OR      A               ;X = 0 ?
  00959 C8              RET     Z               :Yes: return

  0095A 3A2341          LD      A,(4123H)       ;A,7 = sign
  0095D FE2F            CP      2FH             ;--

; Entry from compare routines

* 0095D   2F            CPL
  0095F 17              RLA                     ;C-flag = sign
  00960 9F              SBC     A,A             ;A = FFH if X<0 else A = 00H
                                                ;X < 0 ?
  00961 C0              RET     NZ              ;Yes: return

  00962 3C              INC     A               ;X > 0: A = 01H
  00963 C9              RET

[Verwijderd]

De loop is van beperkte fixed lengte; een optimizer kan uitrekenen of het slimmer is die loop te unrollen. Na de unroll zijn de shifts vervolgens over een fixed lengte. 3 C integers kunnen zelfs op een x86 nog in registers. Kortom, er is geen enkele reden waarom een beetje optimizer langzame code zou moeten opleveren.

Ik weet dat compilers en optimizers tegenwoordig zeer geavanceerd zijn. Ik heb ook wel eens naar de binnenkant van een compiler gekeken. Maar ik weet ook dat compilers soms erg veel moeite hebben met schijnbaar simpele programmeer en optimalisatie truukjes.

De 3 variablen op registers mappen zou geen enkel probleem moeten opleveren overigens

[.oisyn]

Verwijderd schreef op 18 maart 2004 @ 13:22:
En dan gaan jullie dit stukje code nog in een sub-routine zetten ook natuurlijk, waardoor ook nog de hele C-subroutine-caal overhead wordt toegvoegd

Ten eerste kan dat in beide gevallen, dus dat verschil zou je niet mee moeten rekenen, ten tweede is er ook nog zoiets als inline.

En verder: die variabelen kunnen in registers, dus dat is niet per definitie geheugenaccess (bovendien is het op de stack die zo goed als zeker in de cache staat), en een branch betekent niet per definitie een hele pipeline flush, daar hebben ze branch prediction voor uitgevonden.

Tot slot

C++:

#include <iostream>

inline __int64 __declspec (naked) getTSC () 
{
    __asm
    {
        rdtsc
        ret
    }
}


inline int swap1 (int c)
{
    c=((c&0x0F)<<4)+((c&0xF0)>>4); 
    c=((c&0x33)<<2)+((c&0xCC)>>2); 
    c=((c&0x55)<<1)+((c&0xAA)>>1);
    return c;
}

inline int swap2 (int c)
{
    register int flip = 0; 
    for (register int i=0; i<=8; i++)
        if ((c & (1<<i))) 
            flip |= 0x100 >> i; 
}


int main () 
{
    int i;
    std::cin >> i;
    i &= 0xff;

    __int64 t1 = getTSC (), t2;
    int j = swap1 (i);
    t2 = getTSC ();
    std::cout << j << ": " << (t2 - t1) << " cycles" << std::endl;

    t1 = getTSC ();
    j = swap2 (i);
    t2 = getTSC ();
    std::cout << j << ": " << (t2 - t1) << " cycles" << std::endl;
}

swap1: 25 cycles
swap2: 37 cycles

.edit: foutje in mijn code, ik moet natuurlijk niet 2x swap1 aanroepen

Als ik de call echter wijzig naar swap2 dan is het resultaat een beetje vaagjes:

222: 205 cycles
444: 34 cycles

[ Voor 9% gewijzigd door .oisyn op 18-03-2004 14:00 ]

[Verwijderd]

swap1: 25 cycles
swap2: 37 cycles

Ik sta verbaasd van het kleine verschil!

En nu ben ik eigenlijk ook wel nieuwsgierig wat een pure assembly oplossing kost. Lukt dat ook? Of is dan het importeren en exporteren van C-variabelen een groot probleem? [En jouw tijd natuurlijk!]

Verder ben ik nieuwsgierig: Klopt die meting van het aantal klokslagen? Zit er inderdaad op een processor een tellertje dat het aantal clock-cycles telt???? Of is dit een of ander timertje van een peripherie-chip ergens?

[.oisyn]

Zie mijn vorige post, ik had een foutje gemaakt Ik krijg echter problemen met de code, zie jij toevallig nog een fout die ik over het hoofd zie? Of bugt de optimizer gewoon? (VC++ 7.1)

[Verwijderd]

De "sneller" oplossing is langzamer??? Dan eerst, en de "langzame" oplossing is sneller dan de "snelle" oplossing?

Hier klopt iets niet...

ik vertrouw eigenlijk de telling van de clock-cycles niet. Wat doet getTSC() precies?

[.oisyn]

Damnit, de optimizer goot mijn statements door de war
Hij doet eerst 2x getTSC (), en daarna pas de swap2. Bij swap1 doet ie het wel goed

Zoals je ziet voert die functie de rdtsc instructie uit, die geeft een cycle counter terug in edx:eax

Ik schrijf wel even met de hand de aanroepcode in assembly, want dit schiet niet op

[Wirf]

Verwijderd schreef op 18 maart 2004 @ 14:05:
ik vertrouw eigenlijk de telling van de clock-cycles niet. Wat doet getTSC() precies?

TSC staat voor TimeStamp Counter, dat is een functie van nieuwere processors waarmee je het aantal klokcycli van je processor kunt uitlezen.

RDTSC Read from Time Stamp Counter

Copies the contents of the Time Stamp Counter (TSC) into EDX EAX. (The
Pentium maintains a 64-bit Time Stamp Counter (TSC) that is incremented
every clock cycle.) When the Current Privilege Level is 0, the state of
the TSD bit in CR4 does not affect the operation of this instruction.
When the CPL is equal to 1, 2, or 3, the TSC may be read only if the TSD
bit in CR4 is 0. Only a supervisor level program may modify the value of
the TSC.

Flags: No flags affected.

Encoding: 00001111 00110001

Syntax Example Clock Cycles
------ ------- -----------
RDTSC rdtsc 6, 11

uit http://www.singlix.com/trdos/pentium.txt

[ Voor 56% gewijzigd door Wirf op 18-03-2004 14:17 ]

[.oisyn]

Zo, dit schiet meer op

C++:

#include <stdio.h>

inline __int64 __declspec (naked) getTSC () 
{
    __asm
    {
        rdtsc
        ret
    }
}


inline int swap1 (int c)
{
    c=((c&0x0F)<<4)+((c&0xF0)>>4); 
    c=((c&0x33)<<2)+((c&0xCC)>>2); 
    c=((c&0x55)<<1)+((c&0xAA)>>1);
    return c;
}

inline int swap2 (int c)
{
    register int flip = 0; 
    for (register int i=0; i<=8; i++)
        if ((c & (1<<i))) 
            flip |= 0x100 >> i;
    return flip;
}


int main () 
{
    int d;
    __asm
    {
        push 0
        call getTSC
        mov ebx, eax
        call swap1
        call getTSC
        sub eax, ebx
        mov d, eax
        add esp, 4
    }
    printf ("swap1: %d cycles\n", d);

    __asm
    {
        push 0
        call getTSC
        mov ebx, eax
        call swap2
        call getTSC
        sub eax, ebx
        mov d, eax
        add esp, 4
    }
    printf ("swap2: %d cycles\n", d);
}

Het schommelt natuurlijk een beetje, maar:

swap1: 53 cycles
swap2: 181 cycles

dat klopt meer

[Verwijderd]

[dat klopt meer

Deze getallen wil ik wel geloven. Hoewel ik 180 nog steeds erg weinig vind! Dat zijn maar 22 cycles per loop-iteratie!

Voor de volledigheid ook nog even die 16 assembly instructies? Of geloven we wel dat dat 16 cycles kost?

[edit: spellen in het Nederlands valt ook niet mee ]

[ Voor 12% gewijzigd door Verwijderd op 18-03-2004 14:26 ]

[.oisyn]

Hoe kom je aan die 150 en die 16? Dat zijn imho aannames die je niet kunt doen. Bovendien, zoals ik al zei schommelt het wat. Die 53 van swap1 wordt ook weleens 64 of wat hoger, net als bij de 181 van swap2. En 16 cycles betekent natuurlijk niet meteen 16 instructies, dat kunnen er ook wel 1 of 32 zijn

De bijbehorende assembly code:

code:

swap1:
00401010  mov         ecx,dword ptr [esp+4] 
00401014  mov         eax,ecx 
00401016  and         eax,0Fh 
00401019  sar         ecx,4 
0040101C  shl         eax,4 
0040101F  and         ecx,0Fh 
00401022  add         eax,ecx 
00401024  mov         ecx,eax 
00401026  sar         ecx,2 
00401029  and         eax,33h 
0040102C  and         ecx,33h 
0040102F  lea         eax,[ecx+eax*4] 
00401032  mov         edx,eax 
00401034  sar         edx,1 
00401036  and         edx,55h 
00401039  and         eax,55h 
0040103C  lea         eax,[edx+eax*2] 
0040103F  ret              
swap2:
00401040  mov         ecx,dword ptr [esp+4] 
00401044  xor         eax,eax 
00401046  test        cl,1 
00401049  je          swap2+10h (401050h) 
0040104B  mov         eax,100h 
00401050  test        cl,2 
00401053  je          swap2+1Ah (40105Ah) 
00401055  or          eax,80h 
0040105A  test        cl,4 
0040105D  je          swap2+22h (401062h) 
0040105F  or          eax,40h 
00401062  test        cl,8 
00401065  je          swap2+2Ah (40106Ah) 
00401067  or          eax,20h 
0040106A  test        cl,10h 
0040106D  je          swap2+32h (401072h) 
0040106F  or          eax,10h 
00401072  test        cl,20h 
00401075  je          swap2+3Ah (40107Ah) 
00401077  or          eax,8 
0040107A  test        cl,40h 
0040107D  je          swap2+42h (401082h) 
0040107F  or          eax,4 
00401082  test        cl,cl 
00401084  jns         swap2+49h (401089h) 
00401086  or          eax,2 
00401089  test        ch,1 
0040108C  je          swap2+51h (401091h) 
0040108E  or          eax,1 
00401091  ret

Hij unrollt de loop dus gewoon bij swap2
Overigens kun je de branch wel gemakkelijk wegwerken, DaZaffiro's code was niet echt bepaald slim in dat opzicht

Mijn versie:

C++:

inline int swap3 (int c)
{
    register int r = 0;
    for (register int i = 0; i < 8; i++)
        r |= ((c >> (7 - i)) & 1) << i;
    return r;
}

Bovendien was DaZaffiro's code fout, ik heb 'm even verbeterd:

C++:

inline int swap2 (int c)
{
    register int flip = 0; 
    for (register int i=0; i<8; i++)
        if ((c & (1<<i))) 
            flip |= 0x80 >> i;
    return flip;
}

Dit werkt wel in z'n voordeel aangezien er nu 1 iteratie minder wordt doorlopen

Resultaat:

swap1: 64 cycles
swap2: 160 cycles
swap3: 57 cycles

lol, mijn code is zelfs sneller dan die van PiepPiep In de huidige opstelling tenminste

assembly:

code:

swap3:
00401090  mov         ecx,dword ptr [esp+4] 
00401094  mov         eax,ecx 
00401096  sar         eax,2 
00401099  and         eax,20h 
0040109C  mov         edx,ecx 
0040109E  and         edx,40h 
004010A1  or          eax,edx 
004010A3  sar         eax,2 
004010A6  mov         edx,ecx 
004010A8  and         edx,20h 
004010AB  or          eax,edx 
004010AD  mov         edx,ecx 
004010AF  and         edx,10h 
004010B2  sar         eax,2 
004010B5  or          eax,edx 
004010B7  push        esi  
004010B8  mov         edx,ecx 
004010BA  and         edx,1 
004010BD  shl         edx,2 
004010C0  mov         esi,ecx 
004010C2  and         esi,2 
004010C5  or          edx,esi 
004010C7  shl         edx,2 
004010CA  mov         esi,ecx 
004010CC  and         esi,4 
004010CF  or          edx,esi 
004010D1  shl         edx,2 
004010D4  and         ecx,8 
004010D7  or          edx,ecx 
004010D9  sar         eax,1 
004010DB  shl         edx,1 
004010DD  or          eax,edx 
004010DF  pop         esi  
004010E0  ret

Leuk detail is dat als ik de volgorde verander naar swap1, swap3, swap2, de uitkomst ervan dit is:

code:

swap1: 64 cycles
swap3: 74 cycles
swap2: 160 cycles

Oftewel, het hangt volledig van de context af, mijn loopje en PiepPieps code zijn ongeveer even snel, hoewel mijn code kwa lengte 81 bytes is, die van PiepPiep slechts 48 bytes. Die van DaZaffiro is een factor 2 a 3 trager door de branches

[ Voor 36% gewijzigd door .oisyn op 18-03-2004 14:44 ]

[Verwijderd]

Hoe kom je aan die 180 en die 16? Dat zijn imho aannames die je niet kunt doen. En 16 cycles betekent natuurlijk niet meteen 16 instructies, dat kunnen er ook wel 1 of 32 zijn

Beide opmerkingen begrijp ik niet?

[.oisyn]

Oh daarnet zei je 150 (of las ik verkeerd?) Mijn resultaten waren resp. 53 en 181 cycles. Jij hebt het over 16 Waaruit trek je de conclusie dat iets 16 cycles is? En 16 cycles betekent ook niet 16 instructies, 1 instructie kan immers meerdere cycles beslaan, en bovendien kunnen meerdere instructies in dezelfde cycle worden uitgevoerd. Om nog maar te zwijgen over memory stalls en branch misprediction

Heb trouwens wat aan mijn vorige post toegevoegd

[Verwijderd]

En nu ben ik eigenlijk ook wel nieuwsgierig wat een pure assembly oplossing kost. Lukt dat ook?

lijkt mij sterk geoptimaliseerd iets als:

GAS:

_rev_bit:
 XOR   eax,eax
 MOVZX ebx, BYTE PTR [esp+4]
 RCR   bl,1
 RCL   al,1
 RCR   bl,1
 RCL   al,1
 RCR   bl,1
 RCL   al,1
 RCR   bl,1
 RCL   al,1
 RCR   bl,1
 RCL   al,1
 RCR   bl,1
 RCL   al,1
 RCR   bl,1
 RCL   al,1
 RCR   bl,1
 RCL   al,1
 RET

[Verwijderd]

.oisyn schreef op 18 maart 2004 @ 14:28:Overigens kun je de branch wel gemakkelijk wegwerken, DaZaffiro's code was niet echt bepaald slim in dat opzicht

was niet mijn code, maar een verbetering, alleen de verbeterde versie van mij verbetering had je niet meegenomen...

Mijn oplossing, de lookuptable blijft nog altijd de snelste... zo te zien he!

[Verwijderd]

Oh daarnet zei je 150 (of las ik verkeerd?)

150 was een typfout, heb ik 'snel' verbeterd...

Waaruit trek je de conclusie dat iets 16 cycles is?

De pure assembly oplossing is 16 instructies:

SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2

[Ik ben niet meer zo goed in 80x86 opcodes ]

En aangezien dit allemaal simpele schuifinstructies zijn, gok ik dat het ook 16 cycles kost. Dat zal toch wel, met zo'n dikke barrelshifter in een Pentium?

En 16 cycles betekent ook niet 16 instructies, 1 instructie kan immers meerdere cycles beslaan, en bovendien kunnen meerdere instructies in dezelfde cycle worden uitgevoerd. Om nog maar te zwijgen over memory stalls en branch misprediction

Klopt. Daarom ben ik ook nieuwsgierig hoe lang deze 16 assembly instructies duren. Ik vermoed namelijk dat het MINDER dan 16 cycles kost...


[edit: Ik ben veel te laat zie ik, DaZaffiro was mij al lang voor]

[ Voor 6% gewijzigd door Verwijderd op 18-03-2004 15:06 ]

[.oisyn]

Verwijderd schreef op 18 maart 2004 @ 14:54:
[...]
was niet mijn code, maar een verbetering, alleen de verbeterde versie van mij verbetering had je niet meegenomen...

ah ja ik zie het, mijn excuses

[Olaf van der Spek]

Waarom niet zo in C++?

C++:

int swap4(int c)
{
    int r = 0; 
    for (int i = 0; i < 8; i++) 
    {
        r = r << 1 | c & 1;
        c >>= 1;
    }
    return r; 
}

[Verwijderd]

Vooruit, dan toch maar helemaal:

C:

static const unsigned char swap5[] =
{
    0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 
    0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 
    0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 
    0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 
    0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 
    0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 
    0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 
    0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 
    0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 
    0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 
    0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 
    0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 
    0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 
    0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 
    0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 
    0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 
    0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 
    0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 
    0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 
    0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 
    0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 
    0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 
    0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 
    0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 
    0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 
    0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 
    0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 
    0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 
    0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 
    0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 
    0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 
    0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff 
};

Als de alternatieve functies meerdere keren ge-inline-d worden, dan kost dat ook steeds meer geheugenruimte... Deze tabel zou je natuurlijk kunnen genereren met een van de andere functies en fprintf

edit:
Overigens wordt dit meestal gebruikt bij Fast Fourier Transformaties waar het echt alleen maar om snelheid gaat, waar niemand echt wakker ligt van de 256 bytes die je kwijt bent aan de lookup table, gezien de nog relatief grote winst in snelheid.

Enneh... In hardware kost het ondersteunen van een dergelijke omzetting alleen maar draad en een opcode

[ Voor 9% gewijzigd door Verwijderd op 18-03-2004 16:16 ]

[igmar]

Bit shiften met rotate gaat het snelste op de volgende manier :

code:

#define rotr(x,n)   (((x) >> ((int) (n))) | ((x) << (32 - (int)(n))))
#define rotl(x,n)   (((x) << ((int) (n))) | ((x) >> (32 - (int)(n))))

Win32 heeft overigens _rotl() en _rotr() functies. D'r is alleen een probleem : Die dingen werken altijd op 32 bits waarden, hetgeen waarschijnlijk ook de reden is waarom de code van oisyn vreemde resultaten geeft.

[igmar]

Verwijderd schreef op 18 maart 2004 @ 14:54:
[...]
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2
SHIFTRIGHT reg1
ROLLLEFTCARRY reg2

Mijn compiler maakt d'r :

roll $16,%eax

van. Da's Rotate Left, maar dan 16 keer

[.oisyn]

igmar schreef op 18 maart 2004 @ 19:20:
Bit shiften met rotate gaat het snelste op de volgende manier :

code:

#define rotr(x,n)   (((x) >> ((int) (n))) | ((x) << (32 - (int)(n))))
#define rotl(x,n)   (((x) << ((int) (n))) | ((x) >> (32 - (int)(n))))

Win32 heeft overigens _rotl() en _rotr() functies. D'r is alleen een probleem : Die dingen werken altijd op 32 bits waarden, hetgeen waarschijnlijk ook de reden is waarom de code van oisyn vreemde resultaten geeft.

ik gebruik die functies niet, dus ik zie het verband niet

igmar schreef op 18 maart 2004 @ 19:25:
[...]


Mijn compiler maakt d'r :

roll $16,%eax

van. Da's Rotate Left, maar dan 16 keer

het moet ook ROLLRIGHTCARRY zijn ipv SHIFTLEFT

[ Voor 18% gewijzigd door .oisyn op 18-03-2004 19:29 ]

[igmar]

.oisyn schreef op 18 maart 2004 @ 19:28:
ik gebruik die functies niet, dus ik zie het verband niet

Dat de TS eigenlijk en roll wil, alleen dan met een 8 bits waarde.

het moet ook ROLLRIGHTCARRY zijn ipv SHIFTLEFT

Volgens mij maakt het niet uit of je een left of een right roll doet, zover ik het kan bedenken moet je gewoon een roll doet met de helft van het aantal bits om de gespiegelde waarde te krijgen. Zo even uit het hoofd Alleen een shit is onvoldoende, dan ben je ook meteen de helft van je bits kwijt

[ Voor 36% gewijzigd door igmar op 18-03-2004 19:41 ]

[Olaf van der Spek]

Dan zitten de laagste 16 bits in de hoogste 16 bits, maar dan zijn ze nog niet gemirrored.

[.oisyn]

igmar schreef op 18 maart 2004 @ 19:31:

Dat de TS eigenlijk en roll wil, alleen dan met een 8 bits waarde.

waarom geeft mijn code verkeerde resultaten door die functies als ik die functies niet gebruik Mijn code gaf verkeerde resultaten door verkeerde optimalisatie

Volgens mij maakt het niet uit of je een left of een right roll doet, zover ik het kan bedenken moet je gewoon een roll doet met de helft van het aantal bits om de gespiegelde waarde te krijgen. Zo even uit het hoofd Alleen een shit is onvoldoende, dan ben je ook meteen de helft van je bits kwijt

het gaat erom dat je de carry flag gebruikt om bits te transporteren van het ene naar het andere register. Een shift gebruikt de carry flag niet, daar zit de fout (als je dus steeds een shift op het ene register doet en dan een rotate met carry op het andere register is dat idd gewoon hetzelfde als 8x de rotate met carry (ik vraag me wel af waarom ie 16 doet en niet 8 ))

[igmar]

.oisyn schreef op 18 maart 2004 @ 20:40:
waarom geeft mijn code verkeerde resultaten door die functies als ik die functies niet gebruik Mijn code gaf verkeerde resultaten door verkeerde optimalisatie

Even voor de duidelijkheid : De TS wil met bytes werken toch ?

het gaat erom dat je de carry flag gebruikt om bits te transporteren van het ene naar het andere register. Een shift gebruikt de carry flag niet, daar zit de fout (als je dus steeds een shift op het ene register doet en dan een rotate met carry op het andere register is dat idd gewoon hetzelfde als 8x de rotate met carry (ik vraag me wel af waarom ie 16 doet en niet 8 ))

Inderdaad. Ik ga nog meer eens voor de lol morgen de zaken eens op papier zetten, ik heb net wat slechte voorbeelden genomen.

[igmar]

.oisyn schreef op 18 maart 2004 @ 20:40:
waarom geeft mijn code verkeerde resultaten door die functies als ik die functies niet gebruik

Mijn gedachten zaten bij 8 bits vs 32 bits, en operaties die alleen op 32 bits werken.

[Olaf van der Spek]

.oisyn schreef op 18 maart 2004 @ 20:40:
waarom geeft mijn code verkeerde resultaten door die functies als ik die functies niet gebruik Mijn code gaf verkeerde resultaten door verkeerde optimalisatie

Waar is return in (swap2 en) main gebleven in jouw code?

Edit: in swap2 staat die later wel.

[ Voor 6% gewijzigd door Olaf van der Spek op 18-03-2004 23:01 ]

[.oisyn]

ja ik zei al dat er een aantal foutjes in stonden. DaZaffiro had die al verbeterd, maar ik had uiteindelijk de verkeerde code gecopypaste naar m'n testprogramma

[Olaf van der Spek]

Hmm, zonder inline krijg ik dit:
52 122 119
51 122 119
51 122 119
51 122 119
51 122 119
51 122 119
51 122 119
51 122 119

En met inline krijg ik dit:
51 152 127
51 152 127
51 152 127
51 152 127
51 152 127
51 152 127
51 152 127
51 152 127

Swap 1, 2 en 4 in een loop met 8 iteraties.

Waarom is met inline langzamer?

[MSalters]

Cache boundary alignment? Het kan een verschil maken of je code precies in een cache line valt, of dat het de grens van twee cache lines overschrijdt. Met CISC code is dat laatste wat gangbaarder.

[Verwijderd]

Verwijderd schreef op 18 maart 2004 @ 14:51:
[...]


lijkt mij sterk geoptimaliseerd iets als:

GAS:

_rev_bit:
 XOR   eax,eax
 MOVZX ebx, BYTE PTR [esp+4]
 RCR   bl,1
 RCL   al,1
 [...]
 RET

Deze kost dus zo'n 67 cycles 4 cycles per rotate meet ik dus...
Foutje, volgens mij kom ik nu op 34 cycles

.oisyn: die benchmark van jou is niet helemaal representatief, je test alleen met '0', waardoor de bijvoorbeeld de branch van swap2 helemaal niet genomen wordt...

[ Voor 8% gewijzigd door Verwijderd op 19-03-2004 13:53 ]

[Olaf van der Spek]

Inderdaad, de executietijd is afhankelijk van de invoer. Van 0 tot 256:

code:

 0        61       133       137
 1        51       137       137
 2        51       180       137
 3        51       136       137
 4        51       169       137
 5        51       161       137
 6        51       180       137
 7        51       135       137
 8        51       158       137
 9        51       161       137
 a        51       203       137
 b        51       160       137
 c        51       168       137
 d        51       172       137
 e        51       166       137
 f        51       134       137
10        51       159       137
11        51       161       137
12        51       179       137
13        51       147       137
14        51       192       137
15        51       172       137
16        51       190       137
17        51       159       137
18        51       169       137
19        51       172       137
1a        51       191       137
1b        51       171       137
1c        51       154       137
1d        51       158       137
1e        51       177       137
1f        51       133       137
20        51       171       137
21        51       161       137
22        51       154       137
23        51       147       137
24        51       154       137
25        51       159       137
26        51       166       137
27        51       146       137
28        51       168       137
29        51       172       137
2a        51       165       137
2b        51       159       137
2c        51       165       137
2d        51       170       137
2e        51       189       137
2f        51       171       137
30        51       156       137
31        51       147       137
32        51       203       137
33        51       159       137
34        51       167       137
35        51       171       137
36        51       137       137
37        51       158       137
38        51       181       137
39        51       184       137
3a        51       190       137
3b        51       145       137
3c        51       166       137
3d        51       158       137
3e        51       161       137
3f        51       132       137
40        51       145       137
41        51       148       137
42        51       203       137
43        51       147       137
44        51       180       137
45        51       147       137
46        51       203       137
47        51       159       137
48        51       155       137
49        51       159       137
4a        51       202       137
4b        51       158       137
4c        51       179       137
4d        51       170       137
4e        51       165       137
4f        51       158       137
50        51       182       137
51        51       172       137
52        51       163       137
53        51       158       137
54        51       166       137
55        51       146       137
56        51       188       137
57        51       145       137
58        51       180       137
59        51       171       137
5a        51       176       137
5b        51       157       137
5c        51       203       137
5d        51       194       137
5e        51       162       137
5f        51       157       137
60        51       158       137
61        51       160       137
62        51       154       137
63        51       159       137
64        51       204       137
65        51       196       137
66        51       188       137
67        51       145       137
68        51       180       126
69        51       159       137
6a        51       177       137
6b        51       157       137
6c        51       164       137
6d        51       169       137
6e        51       176       137
6f        51       144       137
70        51       169       137
71        51       171       137
72        51       190       137
73        51       158       137
74        51       178       137
75        51       170       137
76        51       177       137
77        51       157       137
78        51       153       137
79        51       158       137
7a        51       176       137
7b        51       157       137
7c        51       150       137
7d        51       169       137
7e        51       148       137
7f        51       131       137
80        51       146       137
81        51       149       137
82        51       204       137
83        51       148       137
84        51       181       137
85        51       161       137
86        51       191       137
87        51       147       137
88        51       156       137
89        51       148       137
8a        51       178       137
8b        51       147       137
8c        51       192       137
8d        51       197       137
8e        51       190       137
8f        51       146       137
90        51       170       137
91        51       173       137
92        51       166       137
93        51       147       137
94        51       191       137
95        51       171       137
96        51       190       137
97        51       159       137
98        51       181       137
99        51       184       137
9a        51       177       137
9b        51       170       137
9c        51       191       137
9d        51       171       137
9e        51       162       137
9f        51       145       137
a0        51       158       137
a1        51       173       137
a2        51       179       137
a3        51       147       137
a4        51       179       137
a5        51       172       137
a6        51       189       137
a7        51       158       137
a8        51       154       137
a9        51       159       137
aa        51       164       137
ab        51       146       137
ac        51       203       137
ad        51       182       137
ae        51       176       137
af        51       158       137
b0        51       142       137
b1        51       147       137
b2        51       189       137
b3        51       158       137
b4        51       191       137
b5        51       170       137
b6        51       174       137
b7        51       157       137
b8        51       193       137
b9        51       171       137
ba        51       164       137
bb        51       170       137
bc        51       166       137
bd        51       158       137
be        51       148       137
bf        51       144       137
c0        51       145       137
c1        51       148       137
c2        51       179       137
c3        51       147       137
c4        51       168       137
c5        51       173       137
c6        51       178       137
c7        51       146       137
c8        51       193       137
c9        51       172       137
ca        51       177       137
cb        51       183       137
cc        51       203       137
cd        51       182       137
ce        51       175       137
cf        51       145       137
d0        51       181       137
d1        51       160       137
d2        51       177       137
d3        51       146       137
d4        51       166       137
d5        51       171       137
d6        51       174       137
d7        51       170       137
d8        51       192       137
d9        51       170       137
da        51       163       137
db        51       157       137
dc        51       190       126
dd        51       169       137
de        51       163       137
df        51       144       137
e0        51       143       137
e1        51       147       137
e2        51       190       137
e3        51       146       137
e4        51       167       137
e5        51       171       137
e6        51       189       137
e7        51       145       137
e8        51       192       137
e9        51       171       137
ea        51       189       137
eb        51       145       137
ec        51       178       137
ed        51       182       137
ee        51       176       137
ef        51       144       137
f0        51       142       137
f1        51       146       137
f2        51       176       137
f3        51       145       137
f4        61       202       137
f5        51       170       137
f6        51       151       137
f7        51       144       137
f8        51       140       137
f9        51       145       137
fa        51       150       137
fb        51       156       137
fc        51       149       137
fd        51       156       137
fe        51       159       137
ff        51       118       137

[ Voor 82% gewijzigd door Olaf van der Spek op 19-03-2004 13:45 ]

[Verwijderd]

De metingen met RDTSC lijken bij mij nog behoorlijk onbetrouwbaar. Dit alleen:

GAS:

    rdtsc
    mov esi, eax
    rdtsc

    sub eax, esi

Levert bij mij meestal 80 op in eax (dus 80 cycles)... (gcc/Linux/Pentium4)

Als ik meet hoeveel het kost om 256 keer de swap met een toenemende waarde uit te voeren en dat deel door 256, dan kom ik met "gcc-3.3.1 -O2 -fomit-frame-pointer -funroll-loops" op een gemiddelde van ongeveer:

swap1: 19 cycles (PiepPiep)
swap2: 129 cycles (suntsu)
swap3: 22 cycles (.oisyn)
swap4: 32 cycles (OlafvdSpek)
swap5: 10 cycles (DaZaffiro)
swap6: 34 cycles (victor8/DaZaffiro)

Deze metingen zijn beduidend lager dan de metingen die ik krijg als ik elke swap-aanroep individueel ga testen. Lijkt mij dat de rdtsc dus roet in het eten gooit bij de gebruikte metingen, en dat dit veel beter de werkelijke tijd benadert?!

(De metingen hebben overigens een kleine overhead door de loop iteraties en de optelling bij "test", die laatste is nodig om wegoptimalisatie te voorkomen (en de resultaten een klein beetje te controleren op juistheid ))

De swap5 en swap6 die ik trouwens gebruik zijn (gcc-3.3.1 -masm=intel -std=gnu99):

C:

inline unsigned int swap5 (unsigned int c)
{
    return (unsigned int)reverse_bit_lookup[c & 0xff];
}

inline unsigned int swap6(unsigned int c)
{
    unsigned int retval;

        asm(""
    "xor %0,%0\n"
    "rcr %1,1\n"
    "rcl %0,1\n"
    "rcr %1,1\n"
    "rcl %0,1\n"
    "rcr %1,1\n"
    "rcl %0,1\n"
    "rcr %1,1\n"
    "rcl %0,1\n"
    "rcr %1,1\n"
    "rcl %0,1\n"
    "rcr %1,1\n"
    "rcl %0,1\n"
    "rcr %1,1\n"
    "rcl %0,1\n"
    "rcr %1,1\n"
    "rcl %0,1\n" : "=Q" (retval), "=Q" (c) : "Q" (c));

    return retval;
}

en main.c:

C:

#include <stdio.h>
#include <inttypes.h>

unsigned int swap1(unsigned int c);
unsigned int swap2(unsigned int c);
unsigned int swap3(unsigned int c);
unsigned int swap4(unsigned int c);
unsigned int swap5(unsigned int c);
unsigned int swap6(unsigned int c);

int main () 
{
    unsigned long   timeA, timeB;
    unsigned int    test = 0;

    /* test swap1 */
    asm volatile("rdtsc" : "=A" (timeA) );

    for(unsigned int i = 0; i < 0x100; i++)
        test+= swap1(i);
    
    asm volatile("rdtsc" : "=A" (timeB) );

    printf ("swap1: %u cycles total\n", timeB - timeA);
    printf ("swap1: %u cycles average\n", (timeB - timeA + 128) >> 8);

    ASSERT(test == 0x7f80);

    test = 0;
    /* test swap2 */

[...]

De rest mag je d'r bij verzinnen

[ Voor 9% gewijzigd door Verwijderd op 19-03-2004 17:09 ]

[.oisyn]

Het vervelende van die rotate-series is dat elke instructie volledig afhankelijk is van de vorige; het pipelinet dus voor geen meter

[Grijze Vos]

Iemand stelde een lookup table van 256 bytes voor. Das een beetje gortig. Maar wat je wel zou kunnen overwegen (geen idee of het sneller is hoor, kben niet zo'n bit-neuker ), is de twee nibbles omdraaien via rotatie ofzo, en dan de twee nibbles afzonderlijk 'inverteren' middels een 16-byte lookup table.

[Verwijderd]

Grijze Vos schreef op 19 maart 2004 @ 17:37:
Iemand stelde een lookup table van 256 bytes voor. Das een beetje gortig. Maar wat je wel zou kunnen overwegen (geen idee of het sneller is hoor, kben niet zo'n bit-neuker ), is de twee nibbles omdraaien via rotatie ofzo, en dan de twee nibbles afzonderlijk 'inverteren' middels een 16-byte lookup table.

Ik was dat ja... En dat kost maar 2 klokcycles als je het zonder functiecall doet...
En waarom is dat gortig? Sterk optimaliseren met behulp van loop-unrolling en inlinen zal toch snel meer ruimte kosten hoor - en toch nog steeds langzamer zijn...

[ Voor 5% gewijzigd door Verwijderd op 19-03-2004 17:46 ]

[Verwijderd]

Wat is er mis met een look-up table? Ervanuitgaande dat dit voor DCT is, doet elke implementatie dat. Het is namelijk simpelweg het snelste. En die lookup-table genereer je natuurlijk niet met de hand, maar automatisch tijdens de init functie in een heerlijk trage maar duidelijke functie:

C:

uint8_t tab8[256];

static __init void
initialize_table (void)
{
  int i;

  for (i = 0; i < 256; i++) {
    /* doe hier iets met de methodiek die jullie hierboven
     * allemaal uitmelken */
    ..
  }
}

#define reverse(num) tab8[num]

..

En nogmaals uitgaande van DCT, een frame is uncompressed 768x576x2 byte (YUY2) en fatsoenlijke mensen gebruiken een buffer van tenminste 1 seconde (=* 25) en dan kom je op zoveel tig MB uit (22MB voor bovenstaande) dat die 256 byte echt geen reet uitmaken. .

Als je voor snelheid gaat, doe het dan goed.

[.oisyn]

LUTs zijn niet per definitie sneller, zeker niet de wat grotere. Zelf berekeningen doen kan in zo'n geval beter uitpakken dan de potentiele cache-misses die een LUT met zich meebrengt. (Ik noem bijvoorbeeld een sin/cos LUT van voldoende resolutie voor het gebruik bij 3D berekeningen)

[Verwijderd]

in de FOX toolkit hebben ze ook een soort getticks geimplementeerd:
die serializing call schijnt nogal belangrijk te zijn... Misschien geeft dat betere resultaten... of misschien heb ik maar de klok horen luiden....

C++:

/*
* Return clock ticks from x86 TSC register, if present.
* Execute cpuid, which is serializing, to complete uops first.
* It is strongly recommended that you know fxcpuid() to return
* CPU_HAS_TSC before calling this function!
* Save EBX because its used when generating position independent code;
* According to i386 ABI, EBP,  EBX, EDI, ESI, ESP need to be saved
* for caller, EAX, ECX, EDX are for callee to use; since we're only
* using EBX, that's the only one that needs saving.
*/
FXlong fxgetticks(){
  FXlong value;
  asm volatile ("pushl %%ebx            \n\t"
                "xor   %%eax,%%eax      \n\t"
                "cpuid                  \n\t"
                "rdtsc                  \n\t"
                "popl  %%ebx            \n\t"
                "movl  %%edx,%1         \n\t"
                "movl  %%eax,%0         \n\t"
                : "=m" (value), "=m" (*(((char *)&value) + 4))
                : /* no input */
                : "eax", "edx", "cc", "memory" );
  return value;
  }

edit: Ah jah...(ia-32 manual er bijpakkend) je wil graag een serializing call doen zodat je zeker weet dat alle instructies die daarvoor werden gedaan zijn afgehandeld...

[ Voor 14% gewijzigd door Verwijderd op 19-03-2004 20:39 ]

[Verwijderd]

.oisyn: zelfs een 2D sin()/cos() LUT (dus 256^2 byte) is tot wel 5x sneller dan het berekenen van de sin()/cos() waarde per frame (dus nog niet eens per pixel). Dat heb ik allemaal al lang uitgetest. . Misschien als ik wat beter in assembler zou zijn; maar vergeleken met alternatieve C implementaties is LUT zowat altijd de snelste. Ik zou zeggen: kom eens met een praktsich voorbeeld waarin een LUT trager is dan de per-case berekening. .

En voor de 256 byte case: . .

[.oisyn]

Verwijderd schreef op 19 maart 2004 @ 22:26:
.oisyn: zelfs een 2D sin()/cos() LUT table (dus 256^2 byte) is tot wel 5x sneller dan het berekenen van de sin()/cos() waarde per frame (dus nog niet eens per pixel). Dat heb ik allemaal al lang uitgetest. . Misschien als ik wat beter in assembler zou zijn; maar vergeleken met alternatieve C implementaties is LUT zowat altijd de snelste. Ik zou zeggen: kom eens met een praktsich voorbeeld waarin een LUT trager is dan de per-case berekening. .

Ten eerste: hoe lang was dat geleden?

Ten tweede:
ook zo lekker representatief, een klein demootje waarin je de LUT test. Ja, natuurlijk is het daar sneller, maar pas het nu eens toe in een echt grote applicatie, waar je sowieso al met floats werkt, en de LUT dus op een random manier geaccessed wordt. En met voldoende resolutie bovendien, een 65536 LUT is nou niet echt bepaald handig voor berekeningen waar je toch al te kampen hebt met vervelende afrondingsfouten.

En voor de 256 byte case: . .

duh, daar heb ik dan verder ook helemaal geen woord over gerept

[ Voor 6% gewijzigd door .oisyn op 19-03-2004 22:31 ]

[Zoijar]

Verwijderd schreef op 19 maart 2004 @ 22:26:
.oisyn: zelfs een 2D sin()/cos() LUT (dus 256^2 byte) is tot wel 5x sneller dan het

Hmmm het ligt er een beetje aan, een 64k tabel dat zal je cache niet fijn vinden. Een fsin kost zo'n 150 cycles, maar is wel overlapbaar door andere code. Dus met een beetje geluk kost het je maar een tik of 6. Als je in een iets grotere berekening dus een sinus nodig hebt, dan kan een fsin wel eens sneller zijn. Als je echter in een tight innerloop continu verschillende sinussen nodig hebt, dan zou de LUT sneller kunnen zijn. Ik vind het alleen wel een erg gespecialiseerde toepassing, en zou niet snel de precisie hiervoor inleveren.

(ik snap die opmerking over "per frame" en "per pixel" niet helemaal trouwens; het lijkt me erg sterk dat het berekenen van een paar sinussen op frame basis een factor 5 zou kunnen schelen. Ik neem aan dat je doelt op quaternion/matrix transformaties?)

[ Voor 18% gewijzigd door Zoijar op 20-03-2004 11:34 . Reden: niet fdiv maar fsin natuurlijk :P ]

[Verwijderd]

Sorry dot.oisyn, dat laatste stukje was dan verkeerd begrepen. .

Zoijar schreef op 19 maart 2004 @ 23:01:
(ik snap die opmerking over "per frame" en "per pixel" niet helemaal trouwens; het lijkt me erg sterk dat het berekenen van een paar sinussen op frame basis een factor 5 zou kunnen schelen. Ik neem aan dat je doelt op quaternion/matrix transformaties?)

Nee, streams. Een hue is een sinus-curve (niet lineair dus), en je wilt dus op m.b.v. de sinus van een constant nummer elke pixel opnieuw berekenen. Dus dit kun je zo doen:

C:

  int brightness = ..., contrast = ..., saturation = ...;
  int hue = sin (... iets met saturation ...), x, y;
..
  /* luminance */
  for (x = 0; x < width; x++) {
    for (y = 0; y < height; y++) {
      /* blabla, brightness, contrast */
    }
  }

  /* chroma */
  for (x = 0; x < (width / 2); x++) {
    for (y = 0; y < (height / 2); y++) {
      /* bereken hier de nieuwe chroma, based op chroma/luminance
       * combi's, en dus 2D! Depends on saturation, hue. */
    }
  }
..

Klopt niet, maar you get the point: zoiets dergelijks. Nu kun je dus voor bovenstaande een LUT maken die je verandert (on-the-fly) als de user brightness/contrast/saturation of hue verandert. Dit is 2D omdat het dus van de input pixel afhangt van zowel de luminance als de chroma, en je beiden nodig hebt om de nieuwe luminance en chroma's apart te berekenen. Dus 2D!

C:

static void
generate_tables (...)
{
  int a, b;
  .. brightness, hue, etc. ..

  for (a = 0; a < 256; a++) {
    this->luminance_table[a] = ...;
  }

  for (a = 0; a < 256; a++) {
    for (b = 0; b < 256; b++) {
      this->chroma_table[a][b] = ...;
    }
  }
}

..
  if (this->need_new_tables) {
    generate_tables ();
    this->need_new_tables = FALSE;
  }

  /* luminance */
  for (x = 0; x < width; x++) {
    for (y = 0; y < height; y++) {
      /* blabla, brightness, contrast */
    }
  }

  /* chroma */
  for (x = 0; x < (width / 2); x++) {
    for (y = 0; y < (height / 2); y++) {
      /* bereken hier de nieuwe chroma, based op chroma/luminance
       * combi's, en dus 2D! Depends on saturation, hue. */
    }
  }
..

Wat is nu het punt? Niks aan? Ha! Dat dachten d'r meer (ik werd voor gek verklaard toen ik dit herschreef). De unoptimized functie kost je op een P-3 1 GHz 80% CPU! De LUT versie kost je rond de 5% CPU. En dat allemaal vanwege wat simpele berekeningetjes als een deling, een vermenigvuldiging per kleurwaarde (dus 1,5*width*height keer per frame) en een sinus per frame. Ik heb dit allemaal uitgetest, en dit soort kleine dingetjes maken allemaal een gigantisch verschil. Zelfs de sinus, ja. Als je 't wilt uittesten en je hebt Linux, pak dan een random CVS versie rond januari van GStreamer, en de huidige 0.8.0, en doe op beiden in de pipeline editor videotestsrc -> colorbalance -> xvimagesink en ga met de properties spelen terwijl dit runt. .

Het genereren van de tables kost je in het geval van een 300x200 video ongeveer even lang als het genereren van 1 frame. Dus bij elke fatsoenlijke video (half-PAL, full-PAL) is het zelfs al sneller als je bij elke frame de tables opnieuw genereert.

edit:

MSalters: nooit van gehoord, ik ben programmeur-n00b zonder opleiding. .

[ Voor 7% gewijzigd door Verwijderd op 19-03-2004 23:33 ]

[MSalters]

Wie gebruikt er eigenlijk zo'n grote tabel? Wat moet je met 64K entries? Met 4K entries en Runga Kutta interpolatie moet je toch praktich net zo ver komen? Ik bedoel, de fout daarvan zou toch ergens in de buurt van de 10^-10 oid moeten liggen?

[Zoijar]

Verwijderd schreef op 19 maart 2004 @ 23:27:

Ah ok, ja dan zal het wel sneller zijn. Is een beetje het tweede geval waar ik het over had.