[C] Xor of aftrekken

[Gehakt]

Ik wil in C 2 CRC waarden met elkaar vergelijken. Als ze aan elkaar gelijk zijn is de bitstroom correct. Zo niet dan is deze incorrect. Vrij simpel dus.

Nou zat ik me alleen af te vragen wat hiervoor handiger / sneller is. Een bitwise XOR gebruiken, of simpelweg de 2 waarden van elkaar aftrekken.

In het geval van een XOR zijn er maar 2 uitkomsten. 0 en 1. In het geval dat je van elkaar aftrekt hangt het van de datatypen af wat je mogelijke terugkomsten zijn (denk ik zo).

Dus mijn vraag. Wat is beter? Of zie ik zelfs nog opties over het hoofd.

[Flard]

Als het om een embedded omgeving gaat: kijk eens in de handleiding van de processor, daar staat meestal precies omschreven hoe lang iedere instructie duurt.

Ik denk echter dat je mag aannemen dat een XOR sneller gaat dan aftrekken: bij een XOR hoeven alleen maar de bits vergeleken te worden, en zodra hij een ongelijk paar bits aantreft, weet hij dus al dat ze niet gelijk zijn. Bij aftrekken (negatief optellen) moet hij dus altijd álle bits gaan gebruiken, en misschien zelfs het carry-bit.
Maar goed, dat hangt een beetje af van de processor.

[Gehakt]

Het gaat hier om een embedded omgeving met een ARM processor. Mijn eerste gedachte was ook om gebruik te maken van de XOR optie.

[RobIII]

Flard schreef op dinsdag 16 januari 2007 @ 10:13:
Als het om een embedded omgeving gaat: kijk eens in de handleiding van de processor, daar staat meestal precies omschreven hoe lang iedere instructie duurt.

Ik denk echter dat je mag aannemen dat een XOR sneller gaat dan aftrekken: bij een XOR hoeven alleen maar de bits vergeleken te worden, en zodra hij een ongelijk paar bits aantreft, weet hij dus al dat ze niet gelijk zijn. Bij aftrekken (negatief optellen) moet hij dus altijd álle bits gaan gebruiken, en misschien zelfs het carry-bit.

Bij mijn weten werken instructies (en processors) altijd op hele bytes/words etc en niet op bits. Het is dus (volgens mij) niet zo dat bij een XOR na de 2e bit "gestopt" zal worden als er een verschil zou zijn; sterker: dat is niet eens interessant omdat alle bits "tegelijkertijd" worden gedaan.
Daarnaast vraag ik me af waarom je uberhaupt op 1 instructie wou willen optimaliseren; zit je zo krap in je tijd dat het daar op aan komt? Dan moet je eens gaan kijken naar het geheel en niet naar dit soort micro-optimalisaties.

[Gehakt]

Het gaat mij helemaal niet om de tijd uiteraard. Dat controleren zal die natuurlijk in een zucht en een scheet doen. Ik vind het echter gewoon interessant voor mezelf welke methode netter / makkelijker / sneller zou zijn. Om welke reden dan ook.

[RobIII]

Gehakt schreef op dinsdag 16 januari 2007 @ 10:48:
Het gaat mij helemaal niet om de tijd uiteraard. Dat controleren zal die natuurlijk in een zucht en een scheet doen. Ik vind het echter gewoon interessant voor mezelf welke methode netter / makkelijker / sneller zou zijn. Om welke reden dan ook.

Netter is nog altijd gewoon de meest leesbare code natuurlijk, makkelijker ... makkelijker voor wie? Voor jou of die processor? Sneller... Joh, je bespaart 1 clockcycle...

[Flard]

RobIII schreef op dinsdag 16 januari 2007 @ 10:45:
[...]

Bij mijn weten werken instructies (en processors) altijd op hele bytes/words etc en niet op bits. Het is dus (volgens mij) niet zo dat bij een XOR na de 2e bit "gestopt" zal worden als er een verschil zou zijn; sterker: dat is niet eens interessant omdat alle bits "tegelijkertijd" worden gedaan.
Daarnaast vraag ik me af waarom je uberhaupt op 1 instructie wou willen optimaliseren; zit je zo krap in je tijd dat het daar op aan komt? Dan moet je eens gaan kijken naar het geheel en niet naar dit soort micro-optimalisaties.

Je hebt helemaal gelijk...

[Soultaker]

Waar héb je het over? Wat is er mis met:

C:

if( crc1 == crc2 ) {
    // ...
}

Natuurlijk, je kunt ook crc1 - crc2 == 0 of crc1 ^ crc2 == 0 schrijven, maar waarom zou je?

[ Voor 35% gewijzigd door Soultaker op 16-01-2007 16:31 ]

[.oisyn]

RobIII schreef op dinsdag 16 januari 2007 @ 10:45:
[...]

Bij mijn weten werken instructies (en processors) altijd op hele bytes/words etc en niet op bits.

Niet helemaal waar. Zo is de gespendeerde tijd van een deling op de meeste platforms bijvoorbeeld afhankelijk van de operanden. Maar een xor vs. een sub doet er doorgaans niet toe

[ Voor 3% gewijzigd door .oisyn op 16-01-2007 16:38 ]

[RobIII]

.oisyn schreef op dinsdag 16 januari 2007 @ 16:37:
[...]

Niet helemaal waar. Zo is de gespendeerde tijd van een deling op de meeste platforms bijvoorbeeld afhankelijk van de operanden. Maar een xor vs. een sub doet er doorgaans niet toe

Mierencopulator
Inderdaad, mijn reply was onvolledig. Het is echter in het geval van xor vs. sub vs. add etc dus niet interessant.

[Theuno]

RobIII schreef op dinsdag 16 januari 2007 @ 16:45:
[...]

Mierencopulator
Inderdaad, mijn reply was onvolledig. Het is echter in het geval van xor vs. sub vs. add etc dus niet interessant.

Helemaal niet inderdaad, waarschijnlijk heeft je processor een geoptimaliseert stuk voor rekenkundige functies, en daar valt sub ook onder. Mijn vermoeden is dan ook dat deze beide functies in 1 klokcycle uitgevoerd worden.

Wat eerder gezegd is, kies in dit geval voor makkelijk herbruik van je code. Over een jaar ben je kwijt waarom je ook alweer een XOR hebt gebruikt.

[ Voor 13% gewijzigd door Theuno op 16-01-2007 17:24 ]

[Woy]

Theuno schreef op dinsdag 16 januari 2007 @ 17:22:
[...]


Helemaal niet inderdaad, waarschijnlijk heeft je processor een geoptimaliseert stuk voor rekenkundige functies, en daar valt sub ook onder. Mijn vermoeden is dan ook dat deze beide functies in 1 klokcycle uitgevoerd worden.

Wat eerder gezegd is, kies in dit geval voor makkelijk herbruik van je code. Over een jaar ben je kwijt waarom je ook alweer een XOR hebt gebruikt.

Dat er een geoptimaliseerd stuk voor rekenkundige operaties ( zo veel meer doet een processor IMHO trouwens niet ) heeft wil nog niet zeggen dat alles wat dat stuk doet in een klokcycle gebeurd. Dingen als delingen en dergelijke gaan meestal echt niet in een klokcycle

[DigiK-oz]

rwb schreef op dinsdag 16 januari 2007 @ 19:23:
[...]

Dat er een geoptimaliseerd stuk voor rekenkundige operaties ( zo veel meer doet een processor IMHO trouwens niet ) heeft wil nog niet zeggen dat alles wat dat stuk doet in een klokcycle gebeurd. Dingen als delingen en dergelijke gaan meestal echt niet in een klokcycle

Klopt. Maar eerst CRCs berekenen (100-en clockcycles at least?) en dan willen optimaliseren op één XOR vs ==

Nieuwsgierigheid naar wat efficienter is, ok. Maar leesbare code is bij dit soort optimalisaties imho een zwaarwegender argument.

[Gehakt]

Eerlijk gezegd...Had ik uberhaupt nog niet aan een == gedacht. Ik zat even teveel met mijn hoofd in assembler denk ik. Dat krijg je als je een dag naar een scherm zit te staren.

[ Voor 19% gewijzigd door Gehakt op 16-01-2007 21:27 ]

[.oisyn]

De branch is idd duurder dan de vergelijking

[RobIII]

Theuno schreef op dinsdag 16 januari 2007 @ 17:22:
[...]


Helemaal niet inderdaad, waarschijnlijk heeft je processor een geoptimaliseert stuk voor rekenkundige functies, en daar valt sub ook onder. Mijn vermoeden is dan ook dat deze beide functies in 1 klokcycle uitgevoerd worden.

Je moet wel even goed de discussie volgen; mijn punt was dat een processor niet "in een lusje" die bits gaat zitten verwerken maar dat per byte/word/quadword etc. doet (en dat dus idd in 1 cycle; waarop .oisyn aantipte dat sommige instructies meer dan 1 cycle nodig hebben; wat ik op mijn beurt was vergeten te vermelden).

[ Voor 13% gewijzigd door RobIII op 17-01-2007 01:15 ]