J'essaye de trouver la facon la plus rapide de comparer l'*egalite*
entre plusieurs unsigned dont les 3 MSB sont a zero (important pour le
2eme cas). Le probleme c'est que je n'ai acces qu'a gcc sur x86 et je ne
sais pas ce qui serait le plus rapide "en general". Pour precision il
s'agit d'une evaluation critique ou le nombre de test d'egalite va de 2
(plus court) a 6 (plus long).
J'ai regarde:
if (a == b && c == d)
success
failure
if (!(a ^ b || c ^ d))
success
failure
Les deux ci-dessus sont equivalent et gcc donne:
cmpl a, b
jne failure
cmpl c, d
je success
failure:
...
success:
...
En revanche:
if (!((a ^ b) + (c ^ d)))
success
failure
xorl a, b (r1)
xorl c, d (r2)
addl r1, r2
jne failure
success:
...
failure:
...
Et la ou je ne comprend plus, c'est que ce deuxieme cas qui n'implique
qu'un seul branchement est plus lent (d'environ 10%). Je ne m'attendais
pas a ca. De plus, sur une architecture avec plus de registre le
deuxieme cas devrait largement l'emporter, non?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Jean-Marc Bourguet
Laurent Deniau writes:
Et la ou je ne comprend plus, c'est que ce deuxieme cas qui n'implique qu'un seul branchement est plus lent (d'environ 10%). Je ne m'attendais pas a ca. De plus, sur une architecture avec plus de registre le deuxieme cas devrait largement l'emporter, non?
Plus j'etudie l'architecture des processeurs, moins je suis capable de predire ce genre de chose. En ce qui concerne les sauts, tu vas sous-estimer leur influence si le predicteur a detecte une regularite dans ton jeu de test. Autre facteur, savoir a quel point l'execution dans le desordre et l'execution speculative font que ces sequences se combinent bien avec ce qu'il y a autour. Pour des sequences aussi courtes, c'est important.
Dans le premier cas, les deux comparaisons peuvent se faire en parallele (les x86 font aussi du renommage de registres sur les flags, la seconde comparaison est naturellement speculative).
Dans le deuxieme cas, les xorl se font en parralele, l'addition attend le resultat et le saut attend le resultat de l'addition.
Une idee pour faire mieux?
Pas essaye, mais
if (!(a ^ b | c ^ d))
est legerement different: il evite la propagation de la carry (par rapport a l'addition) mais je doute que ce soit significatif.
A+
-- Jean-Marc FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc Site de usenet-fr: http://www.usenet-fr.news.eu.org
Laurent Deniau <laurent.deniau@cern.ch> writes:
Et la ou je ne comprend plus, c'est que ce deuxieme cas qui
n'implique qu'un seul branchement est plus lent (d'environ 10%). Je
ne m'attendais pas a ca. De plus, sur une architecture avec plus de
registre le deuxieme cas devrait largement l'emporter, non?
Plus j'etudie l'architecture des processeurs, moins je suis capable de
predire ce genre de chose. En ce qui concerne les sauts, tu vas
sous-estimer leur influence si le predicteur a detecte une regularite
dans ton jeu de test. Autre facteur, savoir a quel point l'execution
dans le desordre et l'execution speculative font que ces sequences se
combinent bien avec ce qu'il y a autour. Pour des sequences aussi
courtes, c'est important.
Dans le premier cas, les deux comparaisons peuvent se faire en
parallele (les x86 font aussi du renommage de registres sur les flags,
la seconde comparaison est naturellement speculative).
Dans le deuxieme cas, les xorl se font en parralele, l'addition attend
le resultat et le saut attend le resultat de l'addition.
Une idee pour faire mieux?
Pas essaye, mais
if (!(a ^ b | c ^ d))
est legerement different: il evite la propagation de la carry (par
rapport a l'addition) mais je doute que ce soit significatif.
A+
--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Et la ou je ne comprend plus, c'est que ce deuxieme cas qui n'implique qu'un seul branchement est plus lent (d'environ 10%). Je ne m'attendais pas a ca. De plus, sur une architecture avec plus de registre le deuxieme cas devrait largement l'emporter, non?
Plus j'etudie l'architecture des processeurs, moins je suis capable de predire ce genre de chose. En ce qui concerne les sauts, tu vas sous-estimer leur influence si le predicteur a detecte une regularite dans ton jeu de test. Autre facteur, savoir a quel point l'execution dans le desordre et l'execution speculative font que ces sequences se combinent bien avec ce qu'il y a autour. Pour des sequences aussi courtes, c'est important.
Dans le premier cas, les deux comparaisons peuvent se faire en parallele (les x86 font aussi du renommage de registres sur les flags, la seconde comparaison est naturellement speculative).
Dans le deuxieme cas, les xorl se font en parralele, l'addition attend le resultat et le saut attend le resultat de l'addition.
Une idee pour faire mieux?
Pas essaye, mais
if (!(a ^ b | c ^ d))
est legerement different: il evite la propagation de la carry (par rapport a l'addition) mais je doute que ce soit significatif.
A+
-- Jean-Marc FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc Site de usenet-fr: http://www.usenet-fr.news.eu.org
Laurent Deniau
Jean-Marc Bourguet wrote:
Laurent Deniau writes:
Et la ou je ne comprend plus, c'est que ce deuxieme cas qui n'implique qu'un seul branchement est plus lent (d'environ 10%). Je ne m'attendais pas a ca. De plus, sur une architecture avec plus de registre le deuxieme cas devrait largement l'emporter, non?
Plus j'etudie l'architecture des processeurs, moins je suis capable de predire ce genre de chose. En ce qui concerne les sauts, tu vas
moi aussi ;-)
sous-estimer leur influence si le predicteur a detecte une regularite dans ton jeu de test. Autre facteur, savoir a quel point l'execution dans le desordre et l'execution speculative font que ces sequences se combinent bien avec ce qu'il y a autour. Pour des sequences aussi courtes, c'est important.
Oui. Mais dans ce cas, le code assembleur avant et apres le test est strictement le meme pour les deux fonction, ce que j'ai poste etait en fait le 'diff'. Pour ce qui est du branchement speculatif, c'est justement ce qui me faisait chercher une autre solution que des == parce qu'apres six comparaisons, il y a peu de chance que le predicteur soit sur la bonne branche. D'un autre cote, si le test echoue (il a peu pres 40% de chance de reussir et 60% de chance d'echouer), la version avec + (ou |) evalue tout, tandis que le == stoppe tout de suite et passe au suivant. Comme j'ai trois tests presque identique qui se suivent, cela donne un avantage au ==.
Dans le premier cas, les deux comparaisons peuvent se faire en parallele (les x86 font aussi du renommage de registres sur les flags, la seconde comparaison est naturellement speculative).
Dans le deuxieme cas, les xorl se font en parralele, l'addition attend le resultat et le saut attend le resultat de l'addition.
Une idee pour faire mieux?
Pas essaye, mais
if (!(a ^ b | c ^ d))
est legerement different: il evite la propagation de la carry (par rapport a l'addition) mais je doute que ce soit significatif.
Effectivement, c'est dans le bruit du bench, bench qui est lui-meme tres instable. Difficile de conclure donc. Mais ca a le merite de ne pas imposer les 3 MSB a zero.
a+, ld.
Jean-Marc Bourguet wrote:
Laurent Deniau <laurent.deniau@cern.ch> writes:
Et la ou je ne comprend plus, c'est que ce deuxieme cas qui
n'implique qu'un seul branchement est plus lent (d'environ 10%). Je
ne m'attendais pas a ca. De plus, sur une architecture avec plus de
registre le deuxieme cas devrait largement l'emporter, non?
Plus j'etudie l'architecture des processeurs, moins je suis capable de
predire ce genre de chose. En ce qui concerne les sauts, tu vas
moi aussi ;-)
sous-estimer leur influence si le predicteur a detecte une regularite
dans ton jeu de test. Autre facteur, savoir a quel point l'execution
dans le desordre et l'execution speculative font que ces sequences se
combinent bien avec ce qu'il y a autour. Pour des sequences aussi
courtes, c'est important.
Oui. Mais dans ce cas, le code assembleur avant et apres le test est
strictement le meme pour les deux fonction, ce que j'ai poste etait en
fait le 'diff'. Pour ce qui est du branchement speculatif, c'est
justement ce qui me faisait chercher une autre solution que des == parce
qu'apres six comparaisons, il y a peu de chance que le predicteur soit
sur la bonne branche. D'un autre cote, si le test echoue (il a peu pres
40% de chance de reussir et 60% de chance d'echouer), la version avec +
(ou |) evalue tout, tandis que le == stoppe tout de suite et passe au
suivant. Comme j'ai trois tests presque identique qui se suivent, cela
donne un avantage au ==.
Dans le premier cas, les deux comparaisons peuvent se faire en
parallele (les x86 font aussi du renommage de registres sur les flags,
la seconde comparaison est naturellement speculative).
Dans le deuxieme cas, les xorl se font en parralele, l'addition attend
le resultat et le saut attend le resultat de l'addition.
Une idee pour faire mieux?
Pas essaye, mais
if (!(a ^ b | c ^ d))
est legerement different: il evite la propagation de la carry (par
rapport a l'addition) mais je doute que ce soit significatif.
Effectivement, c'est dans le bruit du bench, bench qui est lui-meme tres
instable. Difficile de conclure donc. Mais ca a le merite de ne pas
imposer les 3 MSB a zero.
Et la ou je ne comprend plus, c'est que ce deuxieme cas qui n'implique qu'un seul branchement est plus lent (d'environ 10%). Je ne m'attendais pas a ca. De plus, sur une architecture avec plus de registre le deuxieme cas devrait largement l'emporter, non?
Plus j'etudie l'architecture des processeurs, moins je suis capable de predire ce genre de chose. En ce qui concerne les sauts, tu vas
moi aussi ;-)
sous-estimer leur influence si le predicteur a detecte une regularite dans ton jeu de test. Autre facteur, savoir a quel point l'execution dans le desordre et l'execution speculative font que ces sequences se combinent bien avec ce qu'il y a autour. Pour des sequences aussi courtes, c'est important.
Oui. Mais dans ce cas, le code assembleur avant et apres le test est strictement le meme pour les deux fonction, ce que j'ai poste etait en fait le 'diff'. Pour ce qui est du branchement speculatif, c'est justement ce qui me faisait chercher une autre solution que des == parce qu'apres six comparaisons, il y a peu de chance que le predicteur soit sur la bonne branche. D'un autre cote, si le test echoue (il a peu pres 40% de chance de reussir et 60% de chance d'echouer), la version avec + (ou |) evalue tout, tandis que le == stoppe tout de suite et passe au suivant. Comme j'ai trois tests presque identique qui se suivent, cela donne un avantage au ==.
Dans le premier cas, les deux comparaisons peuvent se faire en parallele (les x86 font aussi du renommage de registres sur les flags, la seconde comparaison est naturellement speculative).
Dans le deuxieme cas, les xorl se font en parralele, l'addition attend le resultat et le saut attend le resultat de l'addition.
Une idee pour faire mieux?
Pas essaye, mais
if (!(a ^ b | c ^ d))
est legerement different: il evite la propagation de la carry (par rapport a l'addition) mais je doute que ce soit significatif.
Effectivement, c'est dans le bruit du bench, bench qui est lui-meme tres instable. Difficile de conclure donc. Mais ca a le merite de ne pas imposer les 3 MSB a zero.
