Toon posts:

[C] Kleine structs efficiënt vergelijken

Pagina: 1
Acties:

Onderwerpen


  • Soultaker
  • Registratie: september 2000
  • Laatst online: 22-07 23:43
Stel, ik heb een struct zoals deze:
C:
1
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:
1
2
3
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:
1
2
3
4
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:
1
2
3
4
5
6
7
    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:
1
2
3
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:
1
2
3
4
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:
1
2
3
4
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:
1
2
    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
  • Registratie: januari 2007
  • Laatst online: 20-09 18:38

Matis

Rubber Rocket

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".

If money talks then I'm a mime
If time is money then I'm out of time


  • EddoH
  • Registratie: maart 2009
  • Niet online

EddoH

Backpfeifengesicht

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
  • Registratie: juli 2004
  • Laatst online: 19-01-2018

MLM

aka Zolo

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 ;)

-niks-


  • Mijzelf
  • Registratie: september 2004
  • Niet online
In dit specifieke geval zou je gebruik kunnen maken van bitfields:
C:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
  • Registratie: april 2000
  • Niet online

Woy

Moderator Devschuur®
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.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


  • leuk_he
  • Registratie: augustus 2000
  • Laatst online: 15-09 12:43

leuk_he

1. Controleer de kabel!

MLM schreef op dinsdag 12 oktober 2010 @ 10:10:
Premature optimization en root of all evils etc ;)
QFT _/-\o_ d:)b 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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
....
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:
1
2
3
4
    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)

Need more data. We want your specs. Ik ben ook maar dom. anders: forum, ff reggen, ff topic maken
En als je een oplossing hebt gevonden laat het ook ujb ff in dit topic horen.


  • .oisyn
  • Registratie: september 2000
  • Laatst online: 00:56

.oisyn

Moderator Devschuur® / Cryptocurrencies

Demotivational Speaker

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]

You see, killbots have a preset kill limit. Knowing their weakness, I sent wave after wave of my own men at them until they reached their limit and shut down. Kif, show them the medal I won.


  • H!GHGuY
  • Registratie: december 2002
  • Niet online

H!GHGuY

Try and take over the world...

Wat doet
C:
1
2
3
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 && ?

ASSUME makes an ASS out of U and ME


  • .oisyn
  • Registratie: september 2000
  • Laatst online: 00:56

.oisyn

Moderator Devschuur® / Cryptocurrencies

Demotivational Speaker

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:
1
2
3
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]

You see, killbots have a preset kill limit. Knowing their weakness, I sent wave after wave of my own men at them until they reached their limit and shut down. Kif, show them the medal I won.


  • MSalters
  • Registratie: juni 2001
  • Laatst online: 14-09 11:08
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:
1
struct s
niet aligned hoeft te worden (alleen chars) waardoor je niet zomaar een integer comparison kunt doen - dat is misaligned.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


  • pedorus
  • Registratie: januari 2008
  • Niet online
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
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. :p

Vitamine D tekorten in Nederland | Middelen tegen corona


  • Orwell
  • Registratie: december 2009
  • Laatst online: 14-09 08:33
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++:
1
2
3
4
5
struct COMPLETE {
    float px, py, pz;
    float nx, ny, nz;
    float tx, ty;
};


Met als epic vergelijking:

C++:
1
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++:
1
2
3
4
5
6
7
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++:
1
2
3
4
5
struct COMPLETE {
    D3DXVECTOR3 pos;
    D3DXVECTOR3 nor;
    D3DXVECTOR2 tex;
};


Met een wat minder lelijke compare:

C++:
1
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
  • Registratie: september 2000
  • Laatst online: 00:56

.oisyn

Moderator Devschuur® / Cryptocurrencies

Demotivational Speaker

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]

You see, killbots have a preset kill limit. Knowing their weakness, I sent wave after wave of my own men at them until they reached their limit and shut down. Kif, show them the medal I won.


  • igmar
  • Registratie: april 2000
  • Laatst online: 23:29

igmar

ISO20022

Soultaker schreef op dinsdag 12 oktober 2010 @ 02:28:
Stel, ik heb een struct zoals deze:
C:
1
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
  • Registratie: augustus 2000
  • Laatst online: 15-09 12:43

leuk_he

1. Controleer de kabel!

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.

Need more data. We want your specs. Ik ben ook maar dom. anders: forum, ff reggen, ff topic maken
En als je een oplossing hebt gevonden laat het ook ujb ff in dit topic horen.


  • .oisyn
  • Registratie: september 2000
  • Laatst online: 00:56

.oisyn

Moderator Devschuur® / Cryptocurrencies

Demotivational Speaker

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.

You see, killbots have a preset kill limit. Knowing their weakness, I sent wave after wave of my own men at them until they reached their limit and shut down. Kif, show them the medal I won.


  • Darkstone
  • Registratie: mei 2009
  • Laatst online: 26-04-2014

Darkstone

Het kan altijd sneller.

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

'de sheet' -- Dell Latitude E6520, 1080p, i7-2820QM, X25-M 80GB, 16GB, 97Wh
Gezocht: Baan software development, C++, gave software, omgeving Delft.


  • Robtimus
  • Registratie: november 2002
  • Laatst online: 20-09 14:45

Robtimus

me Robtimus no like you

Soultaker schreef op dinsdag 12 oktober 2010 @ 02:28:
Stel, ik heb een struct zoals deze:
C:
1
struct s { char a, b, c, d; };

...
C:
1
2
3
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:
1
2
3
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:
1
equal(&x, &y);

More than meets the eye
There is no I in TEAM... but there is ME
Vroeger IceManX | system specs


  • Soultaker
  • Registratie: september 2000
  • Laatst online: 22-07 23:43
* 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:
1
2
3
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:
1
2
3
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]

Pagina: 1


Nintendo Switch (OLED model) Apple iPhone 13 LG G1 Google Pixel 6 Call of Duty: Vanguard Samsung Galaxy S21 5G Apple iPad Pro (2021) 11" Wi-Fi, 8GB ram Nintendo Switch Lite

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2021 Hosting door True

Tweakers maakt gebruik van cookies

Bij het bezoeken van het forum plaatst Tweakers alleen functionele en analytische cookies voor optimalisatie en analyse om de website-ervaring te verbeteren. Op het forum worden geen trackingcookies geplaatst. Voor het bekijken van video's en grafieken van derden vragen we je toestemming, we gebruiken daarvoor externe tooling die mogelijk cookies kunnen plaatsen.

Meer informatie vind je in ons cookiebeleid.

Sluiten

Forum cookie-instellingen

Bekijk de onderstaande instellingen en maak je keuze. Meer informatie vind je in ons cookiebeleid.

Functionele en analytische cookies

Deze cookies helpen de website zijn functies uit te voeren en zijn verplicht. Meer details

janee

    Cookies van derden

    Deze cookies kunnen geplaatst worden door derde partijen via ingesloten content en om de gebruikerservaring van de website te verbeteren. Meer details

    janee