[C] Kleine structs efficiënt vergelijken

[Soultaker]

Stel, ik heb een struct zoals deze:

C:

struct s { char a, b, c, d; };

Op een typische 32-bits architectuur is dat ding natuurlijk precies zo groot als een int. Als ik twee variabelen heb van dit type, en de ene aan de andere toeken, dan zal de compiler ook gewoon netjes een enkele instructie genereren waarbij in één keer een 32-bits waarde wordt toegekend.

Helaas is voor structs geen gelijkheidsoperator gedefinieert. Ik vraag me dan dus af op welke manier ik twee structs op net zo'n efficiënte manier zou kunnen vergelijken. De meest voor de hand liggende optie is dit:

C:

int equal(struct s x, struct s y) {
    return x.a == y.a && x.b == y.b && x.c == y.c && x.d == y.d;
} 

Dit werkt, maar genereert ook echt code voor vier vergelijkingen, met allerlei bitshifts en conditionele jumps en andere toestanden. Veel te veel code voor wat feitelijk een word-sized comparison is, naar mijn idee. Blijkbaar heeft de compiler niet door dat ik álle velden aan het vergelijken ben en dat dat in één keer kan gebeuren.

Stel dat ik even gebruik maak van het feit dat ik weet dat de struct geen padding bevat (wat de compiler ook weet) en ik ze dus met memcmp() kan vergelijken:

C:

struct s { char a, b, c, d; };
int equal(struct s x, struct s y) {
    return memcmp(&x, &y, sizeof(struct s)) == 0;
} 

Als dit een function call zou worden zou het natuurlijk nog steeds niet efficiënt zijn, maar dit is een standard library functie die de compiler kent en speciaal optimaliseert. Er wordt code gegenereerd van de vorm:

code:

    cld
    movl    $4, %ecx
    leal    12(%ebp), %edi
    leal    8(%ebp), %esi
    repz cmpsb
    movl    (%esp), %esi
    movl    4(%esp), %edi

Met nog het nodige gedoe eromheen om een stackframe te bouwen en registers te saven/restoren. De compiler heeft de call naar memcmp() vervangen door een rep cmpsb constructie, wat waarschijnlijk beter is dan een reeks vergelijkingen, maar het is nog steeds belachelijk veel overhead en een impliciete loop. Waarschijnlijk komt dat doordat de memcmp() meer doet dan ik wil, want het is een comperator die een lexicografische vergelijking uitvoert. De compiler beseft niet dat ik het resultaat uiteindelijk alleen maar met 0 vergelijk.

Dus ik zoek nog even verder en er blijkt ook nog een (deprecated) functie bcmp() te bestaan, wat precies specificieert wat ik zoek: het werkt als memcmp() behalve dat de functie nul of niet-nul retourneert afhankelijk van of de buffers wel of niet gelijk zijn. Aan een niet-nul resultaat wordt verder geen enkele betekenis toegekend. Dat moet toch aanzienlijk beter te optimaliseren zijn, leek me! Helaas genereert de compiler hier precies dezelfde code, waarschijnlijk omdat het een deprecated functie is waarvoor dus niet specifiek geoptimaliseerd wordt.

Gelukkig heb ik ook wel wat methoden gevonden die wél naar wens werken, als ik ook gebruik dat ik toevallig weet dat de struct even groot is als een int. Ik kan ze dan via via naar een int casten:

C:

int equal(struct s x, struct s y) {
    return *(int*)&x == *(int*)&y;
} 

Dit werkt correct, hoewel het dubieus op me over kwam in combinatie met strict aliasing regels. (Is dit eigenlijk een overtreding of niet?)

Een variant die zeker veilig is, is het gebruik van een union:

C:

int equal(struct s x, struct s y) {
    union u { struct s s; int i; } ux = { x }, uy = { y };
    return ux.i == uy.i;
} 

Niet de meest mooie code. In C99 kan ik zelfs een union constructor gebruiken, wat misschien iets prettiger leest, maar dus niet echt compatible is met oudere C standaarden (wat natuurlijk jammer is):

C:

int equal(struct s x, struct s y) {
    union u { struct s s; int i; };
    return ((union u)x).i == ((union u)y).i;
} 

Alledrie de varianten compileren naar dezelfde, efficiënte code die ik graag in het begin gezien had:

C:

    movl    12(%ebp), %eax
    cmpl    %eax, 8(%ebp)

(De enige reden dat het nog twee in plaats van één instructie kost, is dat beide argumenten op de stack staan in plaats van in registers.)

Helaas generaliseert deze aanpak slecht naar meerdere platformen met wisselende groottes van datatypes, complexere structures, en dergelijke. Ik zou liever gezien hebben dat de compiler op de een of andere manier bedenkt op welke manier twee structures inhoudelijk het beste vergeleken kunnen worden en daar zélf de beste code bij genereert.

De vraag die ik hierbij wil stellen is de volgende: herkennen anderen dit probleem, en zo ja, hoe lossen jullie het op?

[Matis]

Ik weet niet precies wat je bedoelt met efficient. Kijk je daarmee naar het aantal regels assembly/code of de efficiëntie van de uitvoer ervan.
Omdat je in je eerste stukje code allemaal && gebruikt, zal (afaik) de code van links naar rechts evalueren. Wanneer de eerste conditie niet waar is, dan wordt er direct een false geretourneerd. Zonder dat de rechtse 3 ook geëvalueerd worden.
Als je zorgt dat de vergelijking met de meeste kans op ongelijkheden het meest links in de vergelijking komt, dan zit je volgens mij wel snor qua efficiëntie in uitvoering. Qua bytecode is het misschien niet optimaal.

We gebruiken dat ook veel voor het vergelijken van "struct tm".

[EddoH]

Ik herken het probleem en loop er ook meer dan eens tegenaan.
Ik dit geval wil je de complete struct vergelijken, en komt de data mooi uit op een int, maar in veel meer gevallen is de data natuurlijk niet zo ideaal geordend.
Ik vraag me dan ook af of er een veel efficientere methode is.

Wat ik probeer te doen is om te voorkomen dat ik alle velden moet gaan comparen, en te zorgen dat er in het datamodel van de struct een bepaalde unieke waarde aanwezig is die representatief voor de inhoud is. Je zou het een soort hash kunnen noemen. Nadeel is dat het vullen/behandelen hiervan ook weer extra tijd en geheugen kost.
Oftwel: ik probeer het by design op te lossen.

[MLM]

Bij structs met een specifieke size doe ik meestal pointer casten naar integral van dezelfde size, en een assert(sizeof(int) == sizeof(struct)) erbij (anders krijg je leuke bugs als je struct veranderd).

Je zou nog wat template magic kunnen gebruiken op sizeof(struct) en er een (a ^ b) & size_mask of iets dergelijks van kunnen maken, en dan kun je structs comparen van elke grootte tot je max integral value, en anders memcmp gebruiken, maar dan zit je vast aan C++ ipv C.

Tevens is memcmp typisch gezien afhankelijk van je geheugen snelheid, vergelijken gaat sneller dan dat data arriveert, dus die extra cycles voor een loop etc worden verstopt achter je geheugen latency, tenzij het om erg kleine structs gaat, en dan kost het sowieso niet erg lang Tenzij je op een embedded systeem zit met die compare in een veel uitgevoerde loop, zou ik me er niet te druk over maken. Premature optimization en root of all evils etc

[Mijzelf]

In dit specifieke geval zou je gebruik kunnen maken van bitfields:

C:

union s{
    struct{
        int a:8;
        int b:8;
        int c:8;
        int d:8;
    } delen;
    int totaal;
};

union s s1;
s1.delen.a = 5;

int equal(union s x, union s y) { 
    assert( sizeof( x.totaal ) == sizeof( x.delen ) );
    return x.totaal == y.totaal; 
}

Nadeel is wel dat de equal functie snel word, maar het benaderen van de afzonderlijke delen trager. (masken, bitshift,...)

[Woy]

Matis schreef op dinsdag 12 oktober 2010 @ 09:02:
Omdat je in je eerste stukje code allemaal && gebruikt, zal (afaik) de code van links naar rechts evalueren. Wanneer de eerste conditie niet waar is, dan wordt er direct een false geretourneerd. Zonder dat de rechtse 3 ook geëvalueerd worden.

Maar het zijn nog steeds meer vergelijkingen dan nodig. Een 32 bits int vergelijken zal op een PC doorgaans minstens net zo snel ( of sneller ) gaan dan een byte vergelijken. Het is dus sowieso sneller om gewoon de int vergelijking te doen. Ik zou inderdaad wel zoals MLM voorstelt een assert aan de code toevoegen, anders is de kans natuurlijk groot dat het later een keer een vreemde bug oplevert.

[leuk_he]

MLM schreef op dinsdag 12 oktober 2010 @ 10:10:
Premature optimization en root of all evils etc

QFT L2 cache optimalisatie is op een multi ops/tick platform wellicht belangrijker.


In de zeldzame gevallen dat het van belang is definieer ik de struct al in een union.

code:

....
struct s { char a, b, c, d; };

typedef union  { s s1;
          int i;
} u;


main()
{
    u u1;
    u u2; 
    
    u1.s1.a=1;
    u1.s1.b=2;

    u2.s1.a=1;
    
    if (u1.i == u2.i) 
         printf("waar");
    else
          printf("niet waar" );
..

code:

    if (u1.i == u2.i) 
004113CA  mov         eax,dword ptr [u1] 
004113CD  cmp         eax,dword ptr [u2] 
004113D0  jne         wmain+4Bh (4113EBh)

(En dit gaat dus fout omdat c &d niet geinitilaiseerd zijn.. maar dat is dus niet het punt, we zijn immers hardcore aan het bitfucken)

Je zult dit dus ook specifiek voor je compiler+platform moeten testen. net als jouw union .Jouw cast naar pointer en dan de int cast daarvan vergelijken (wat je eigenlijk ook nog eens als inline procdeure dan wilt denk ik) werkt op bepaalde platformen. echter op AMD64 code de pointer 64 bit en de int 32 bit (en de long is cross platform 32 bit gedefineerd .... ) dus vergeet maar of het voor dat platform geldig is(ik ben te lui om het uit te testen). Let op je platform! Let op je compiler settings (stuct padding)

[.oisyn]

leuk_he schreef op dinsdag 12 oktober 2010 @ 12:05:
Jouw cast naar pointer en dan de int cast daarvan vergelijken (wat je eigenlijk ook nog eens als inline procdeure dan wilt denk ik) werkt op bepaalde platformen.

Hij cast niet eerst naar een pointer en dan naar een int. Hij cast een struct pointer naar een int pointer, en dereferencet hij, zodat hij de int representatie van het geheugen van de struct gebruikt. Dat wat jij denkt dat ie doet zorgt niet eens voor een valide compare (de adressen zullen immers altijd verschillend zijn voor de twee argumenten van de functie). 't Is feitelijk hetzelfde als de union oplossing.

En dan de hele tijd dat gezever over premature optimization... Als Soultaker het niet had teruggezien in z'n profiles had ie ook geen topic geopend .

De asserts gaan je overigens niet beschermen tegen mogelijke struct padding. Alle voorgestelde oplossingen falen zodra je een struct { short a; char b; } hebt.

[ Voor 10% gewijzigd door .oisyn op 12-10-2010 12:24 ]

[H!GHGuY]

Wat doet

C:

int equal(struct s x, struct s y) {
    return x.a == y.a & x.b == y.b & x.c == y.c & x.d == y.d;
}

met & ipv && ?

[.oisyn]

Dan is er nog steeds een compare nodig (en conditional branch of andere functionaliteit om de 0 danwel 1 te genereren). Dit is dan iets handiger:

C:

int equal(struct s x, struct s y) { 
    return !((x.a ^ y.a) | (x.b ^ y.b) | (x.c ^ y.c) | (x.d ^ y.d));
}

[ Voor 12% gewijzigd door .oisyn op 12-10-2010 13:20 ]

[MSalters]

Klinkt als een slecht optimaliserende compiler. Dit soort problemen los je al op met een triviale peephole optimizer.

Een peephole optimizer is een simpele optimizer specifiek voor een code generator, en werkt door bekend slechte output van de code generator te vervangen door betere code.

In dit geval zou die de slechte output (x.a == y.a && x.b == y.b) moeten vervangen door een enkele 16 bits compare. Doe dat nog eens voor de derde en vierde vergelijking, en daarna nog eens om de twee 16 bits vergelijkingen samen te voegen tot een enkele 32 bits vergelijking.

Het grootste probleem overigens is dat

code:

struct s

niet aligned hoeft te worden (alleen chars) waardoor je niet zomaar een integer comparison kunt doen - dat is misaligned.

[pedorus]

Soultaker schreef op dinsdag 12 oktober 2010 @ 02:28:
Helaas generaliseert deze aanpak slecht naar meerdere platformen met wisselende groottes van datatypes, complexere structures, en dergelijke.

Tsja, als dit er wel was, dan had == en != ook wel gedefinieerd kunnen worden voor structs. Ook

quote: http://c-faq.com/struct/compare.html

Question 2.8

Q: Is there a way to compare structures automatically?

A: No. There is not a good way for a compiler to implement structure comparison (i.e. to support the == operator for structures) which is consistent with C's low-level flavor. A simple byte-by-byte comparison could founder on random bits present in unused ``holes'' in the structure (such padding is used to keep the alignment of later fields correct; see question 2.12). A field-by-field comparison might require unacceptable amounts of repetitive code for large structures. Any compiler-generated comparison could not be expected to compare pointer fields appropriately in all cases: for example, it's often appropriate to compare char * fields with strcmp rather than == (see also question 8.2).

If you need to compare two structures, you'll have to write your own function to do so, field by field.

References: K&R2 Sec. 6.2 p. 129
Rationale Sec. 3.3.9
H&S Sec. 5.6.2 p. 133

En verder optimaliseert je compiler gewoon slecht.

[Orwell]

Probeer de variabeles eens in een type te gooien dat wel compareopdrachten heeft, zoals D3DXVECTOR#. Dat is namelijk veel sneller dan apart maken. Een voorbeeld. De oude situatie:

C++:

struct COMPLETE {
    float px, py, pz;
    float nx, ny, nz;
    float tx, ty;
};

Met als epic vergelijking:

C++:

if(objasm[a].px == objasm[b].px && objasm[a].py == objasm[b].py && objasm[a].pz == objasm[b].pz && objasm[a].nx == objasm[b].nx && objasm[a].ny == objasm[b].ny && objasm[a].nz == objasm[b].nz && objasm[a].tu == objasm[b].tu && objasm[a].tv == objasm[b].tv) {

En dat dan in een megaforloop om op die manier een vertexbuffer op dubbeles te controleren.

Dat duurde dus zo fucking lang dat ik maar is wat ben gaan veranderen. En ja hoor, het kon beter. Met het typedef D3DXVECTOR1/2/3, die een ==-operator heeft:

C++:

typedef struct D3DXVECTOR3 : public D3DVECTOR {
    (...)

    BOOL operator == ( CONST D3DXVECTOR3& ) const;
    BOOL operator != ( CONST D3DXVECTOR3& ) const;

} D3DXVECTOR3, *LPD3DXVECTOR3;

En hij is ook nog eens flink snel. Even voor de duidelijkheid, het ziet er nu zo uit:

C++:

struct COMPLETE {
    D3DXVECTOR3 pos;
    D3DXVECTOR3 nor;
    D3DXVECTOR2 tex;
};

Met een wat minder lelijke compare:

C++:

if(objasm[a].pos == objasm[b].pos && objasm[a].nor == objasm[b].nor && objasm[a].tex == objasm[b].tex) {

Wat dus wel een aanbeveling is als je toevallig met floats werkt. Enig probleem misschien is dat je misschien wat extra prut moet includen, maar die typedef doet mooi al het werk van geheugen indelen.

[.oisyn]

Ten eerste programmeert ie C, geen C++ (in C kun je geen operators overloaden). Ten tweede, de reden waarom D3DVECTOR snel is is omdat hij gebruik maakt van SSE operaties. Oftewel, vergelijkbaar met wat Soultaker al deed door 4 chars als enkele int te vergelijken.

[ Voor 21% gewijzigd door .oisyn op 12-10-2010 16:03 ]

[igmar]

Soultaker schreef op dinsdag 12 oktober 2010 @ 02:28:
Stel, ik heb een struct zoals deze:

C:

struct s { char a, b, c, d; };

Op een typische 32-bits architectuur is dat ding natuurlijk precies zo groot als een int. Als ik twee variabelen heb van dit type, en de ene aan de andere toeken, dan zal de compiler ook gewoon netjes een enkele instructie genereren waarbij in één keer een 32-bits waarde wordt toegekend.

In theorie : Ja. De compiler is echter vrij om naar eigen inzicht daar padding in te zetten, als als dat gebeurd ben je dus de sjaak. Theoretisch zou het inderdaad goed moeten werken.

[leuk_he]

igmar schreef op dinsdag 12 oktober 2010 @ 17:03:
[...]


In theorie : Ja. De compiler is echter vrij om naar eigen inzicht daar padding in te zetten, als als dat gebeurd ben je dus de sjaak. Theoretisch zou het inderdaad goed moeten werken.

Compilers hebben daar opties voor. dat heb je helemaal onder controle daarmee. We hebben het toch over een truuk die niet portable is.

Maar sommige processors vinden het niet prettig als dat niet goed op word/dword grenzen ligt en geeft je dan voor straf een paar clockcycles op de bank.

Of je hier nou essentiële performance mee wint of niet, je bewust zijn ven de gegeneerde assembly code kan zeker geen kwaad.

[.oisyn]

igmar schreef op dinsdag 12 oktober 2010 @ 17:03:
[...]


In theorie : Ja. De compiler is echter vrij om naar eigen inzicht daar padding in te zetten, als als dat gebeurd ben je dus de sjaak.

Nee hoor, de padding mag best meegekopiëerd worden. Het gaat pas fout als je die padding bytes meeneemt in de vergelijking.

[Verwijderd]

kan je dan niet simpel controleren OF er padding word gegenereerd, en aan de hand daarvan het juiste stukje code uitvoeren/compilen?

[Robtimus]

Soultaker schreef op dinsdag 12 oktober 2010 @ 02:28:
Stel, ik heb een struct zoals deze:

C:

struct s { char a, b, c, d; };

...

C:

int equal(struct s x, struct s y) {
    return x.a == y.a && x.b == y.b && x.c == y.c && x.d == y.d;
} 

Ik ben niet zo heel erg bedreven in C, maar maak je zo geen kopieën van je structs? Zou dit niet efficienter zijn op dat gebied:

C:

int equal(struct s *x, struct s *y) {
    return x->a == y->a && x->b == y->b && x->c == y->c && x->d == y->d;
}

C:

equal(&x, &y);

[Soultaker]

* Soultaker gaat voor het record op meeste mensen reageren in één post:

EddoH schreef op dinsdag 12 oktober 2010 @ 09:31:
Wat ik probeer te doen is om te voorkomen dat ik alle velden moet gaan comparen, en te zorgen dat er in het datamodel van de struct een bepaalde unieke waarde aanwezig is die representatief voor de inhoud is. Je zou het een soort hash kunnen noemen.

Daar kan ik me wat bij voorstellen, maar dat geeft natuurlijk juist bij kleine structs zoals deze relatief veel overhead. (Sowieso moet je dan zorgen dat de data consistent blijft, dus je unieke identifier updaten elke keer als je naar een veld schrijft. Je vergroot dan de complexiteit van de code ten behoeve van de efficiëntie, wat soms zeker te verdedigen is, maar niet direct mijn voorkeur heeft.)

MLM schreef op dinsdag 12 oktober 2010 @ 10:10:
Tevens is memcmp typisch gezien afhankelijk van je geheugen snelheid, vergelijken gaat sneller dan dat data arriveert, dus die extra cycles voor een loop etc worden verstopt achter je geheugen latency, tenzij het om erg kleine structs gaat, en dan kost het sowieso niet erg lang

Mja, het gaat specifiek om kleine structs die op veel plaatsen gebruikt worden. Voor grotere stukken data is memcmp() inderdaad prima, maar voor word-sized structs is het toch wat overdreven.

H!GHGuY schreef op dinsdag 12 oktober 2010 @ 12:58:
Wat doet

C:

int equal(struct s x, struct s y) {
    return x.a == y.a & x.b == y.b & x.c == y.c & x.d == y.d;
}

met & ipv && ?

Ah, je wilt de sequence points weg werken? Helaas genereert dat nog steeds een gigantische berg code (wel branchvrij). Zie: http://paste.pocoo.org/show/274639/

.oisyn schreef op dinsdag 12 oktober 2010 @ 13:05:
Dan is er nog steeds een compare nodig (en conditional branch of andere functionaliteit om de 0 danwel 1 te genereren). Dit is dan iets handiger:

C:

int equal(struct s x, struct s y) { 
    return !((x.a ^ y.a) | (x.b ^ y.b) | (x.c ^ y.c) | (x.d ^ y.d));
}

Dit wordt inderdaad significant minder code, maar nog steeds veel: http://paste.pocoo.org/show/274641/

pedorus schreef op dinsdag 12 oktober 2010 @ 15:29:
Tsja, als dit er wel was, dan had == en != ook wel gedefinieerd kunnen worden voor structs. Ook

A field-by-field comparison might require unacceptable amounts of repetitive code for large structures. Any compiler-generated comparison could not be expected to compare pointer fields appropriately in all cases: for example, it's often appropriate to compare char * fields with strcmp rather than ==

Ik ben er niet op uit om de taal te veranderen (ik probeer oplossingen te vinden binnen de geldende taaldefinitie) maar het laatstgenoemde argument vind ik flauwekul.

Als ik twee char* variabelen heb, dan kan ik die prima toekennen met = of vergelijken met ==. Dan krijg je ook gewoon een bitwise assignment of comparison in plaats van een inhoudelijke kopie met strdup() vergelijking met strcmp(), maar dat risico is voor de programmeur (en meestal wil je dat gewoon). Het slaat natuurlijk nergens op dat dat niet meer zou kunnen zodra een pointer in een field zit. Het enige lastige onderdeel lijkt me vergelijking van unions.

MSalters schreef op dinsdag 12 oktober 2010 @ 13:37:
Klinkt als een slecht optimaliserende compiler. Dit soort problemen los je al op met een triviale peephole optimizer.

Het gaat om gcc 4.4.4 met -O2 -march=i386; lijkt me toch niet de minste compiler.

In dit geval zou die de slechte output (x.a == y.a && x.b == y.b) moeten vervangen door een enkele 16 bits compare. Doe dat nog eens voor de derde en vierde vergelijking, en daarna nog eens om de twee 16 bits vergelijkingen samen te voegen tot een enkele 32 bits vergelijking.

Klinkt zinnig, hoewel het me een relatief complexe operatie lijkt voor een peephole optimizer. In ieder geval lijkt het niet te gebeuren.

Het grootste probleem overigens is dat struct s niet aligned hoeft te worden (alleen chars) waardoor je niet zomaar een integer comparison kunt doen - dat is misaligned.

Goed punt, maar de compiler begint juist steeds met die structs in registers te laden, dus blijkbaar is mogelijke alignment geen bezwaar. (Overigens garandeert de x86 ABI dat de stack word aligned is, dacht ik?) Dit is natuurlijk wel x86 specifiek, maar dat weet de compiler ook.

igmar schreef op dinsdag 12 oktober 2010 @ 17:03:
De compiler is echter vrij om naar eigen inzicht daar padding in te zetten, als als dat gebeurd ben je dus de sjaak.

Klopt natuurlijk, maar het is de compiler zelf die die keuze maakt en vervolgens code genereert. Dus als de compiler heeft besloten om vier chars in een 32-bits word te packen zonder verdere padding, dan staat het 'm daarna vrij om die integer comparison te genereren. Die optimalisatie voert 'ie ook gewoon uit bij een assignment. Alleen is het probleem natuurlijk dat er geen gelijkheidsoperator is die op structs werkt.

IceManX schreef op dinsdag 12 oktober 2010 @ 20:45:
Ik ben niet zo heel erg bedreven in C, maar maak je zo geen kopieën van je structs?

Ja, maar dat vind ik prima als ze zo klein zijn; een pointer is net zo groot als de struct. Sowieso is dit voorbeeld ernstig versimpeld. De gegenereerde code voor de vergelijking wordt er sowieso niet echt veel anders op.

[ Voor 3% gewijzigd door Soultaker op 12-10-2010 22:15 ]