Pbl template / définition de statique

kanze wrote on 27/04/2006 18:22:

Mais alors... Il n'a jamais dit que son template ne servait que
pour les types entiers de base -- je suis d'accord qu'écrire un
template qui n'accepte que les types entiers de base comme
paramètre, c'est vraiement rarement utile.

corrollairement une classe template ne peux proposer que des services
"basiques" pour supporter aussi bien un type primitif que des références
d'objects, on voit donc souvent des template<type primitif> à coté de
template<class T[&|*]>.

(Sauf, peut-être,
pour rouler la mechanique. La mode est aux templates, après
tout, et si tu ne fais pas un template de tout, tu n'es pas in.)

c'est un peu le fond de ma question, une fois acté le fait évident qu'il
n'est pas utile de réinventer l'eau tiède pour un service standard, je
m'interrogais sur l'usage (fréquent) des templates comme soit lié à un
effet de mode, soit comme la conséquence d'une perte de maitrise de
l'algorithme.

algorithmie au sens large d'ailleurs: logique, sur la mise au point d'un
algo de tri, de gestion de listes, ..., comme globale sur la répartition
des taches dans un programme complet et les règles d'éxecution de ces
taches (mettre un save dans un destructeur parce que ça fait mode, tant
bien même celui-ci est incapable de gérer correctement l'opération).

Il y a des fois que d'autres types s'imposent -- j'ai aussi du
code avec les uint32_t, par exemple (dans l'implémentation de
SHA-1, par exemple). Mais ce sont des exceptions. (Il y a aussi
des décalages dans l'implémentation de SHA-1:-).)

ouais, c'est plus des rotations avec réinjection que des shifts ;)

Sylvain.

Sylvain wrote:

kanze wrote on 27/04/2006 18:22:

Il y a des fois que d'autres types s'imposent -- j'ai aussi
du code avec les uint32_t, par exemple (dans
l'implémentation de SHA-1, par exemple). Mais ce sont des
exceptions. (Il y a aussi des décalages dans
l'implémentation de SHA-1:-).)

ouais, c'est plus des rotations avec réinjection que des shifts ;)

Logiquement, en tout cas. Mais vue que le C++ n'a pas
d'opérateur de rotation, on fait semblant avec des décalages.
(Je ne me suis pas posé la question, mais est-ce qu'un
compilateur pour un processeur qui a des instructions de
rotation, comme IA-32, reconnaîtra l'idiome avec << n et >>
(32-n), et génèrera l'instruction machine voulue ? En principe,
c'est possible, et même pas trop difficile.)

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

kanze wrote:

Logiquement, en tout cas. Mais vue que le C++ n'a pas
d'opérateur de rotation, on fait semblant avec des décalages.
(Je ne me suis pas posé la question, mais est-ce qu'un
compilateur pour un processeur qui a des instructions de
rotation, comme IA-32, reconnaîtra l'idiome avec << n et >>
(32-n), et génèrera l'instruction machine voulue ? En principe,
c'est possible, et même pas trop difficile.)

Petit test avec gcc 3.4.4:
unsigned rotate(unsigned x, unsigned n)
{
return x << n | x >> (32-n);
}

même sans optimisation, donne
pushl %ebp
movl %esp, %ebp
movl 12(%ebp), %ecx
movl 8(%ebp), %eax
roll %cl, %eax
popl %ebp
ret

Avec -O2 ou -O3, le popl se fait avant le roll.

Falk

kanze wrote:

Logiquement, en tout cas. Mais vue que le C++ n'a pas
d'opérateur de rotation, on fait semblant avec des décalages.
(Je ne me suis pas posé la question, mais est-ce qu'un
compilateur pour un processeur qui a des instructions de
rotation, comme IA-32, reconnaîtra l'idiome avec << n et >>
(32-n), et génèrera l'instruction machine voulue ? En principe,
c'est possible, et même pas trop difficile.)

Petit test avec gcc 3.4.4:
unsigned rotate(unsigned x, unsigned n)
{
return x << n | x >> (32-n);
}

même sans optimisation, donne pushl %ebp
movl %esp, %ebp
movl 12(%ebp), %ecx
movl 8(%ebp), %eax
roll %cl, %eax
popl %ebp
ret

Avec -O2 ou -O3, le popl se fait avant le roll.

Pas mal ! VC6, même en optimisation max, ne reconnaît pas l'idiome :

mov edx,dword ptr [esp+4]
push esi
mov esi,dword ptr [esp+0Ch]
mov ecx,20h
sub ecx,esi
mov eax,edx
shr eax,cl
mov ecx,esi
pop esi
shl edx,cl
or eax,edx
ret

--
Sylvain Togni

Sylvain Togni wrote on 28/04/2006 11:03:

Pas mal ! VC6, même en optimisation max, ne reconnaît pas l'idiome :

je crains plutôt que, quoi qu'il reconnaisse, il ne peux utiliser que
des instructions valides du proc. target; et (sauf grave erreur de ma
part) Intel n'a pas cablé de rotl / rotr (ni roll).

Sylvain.

Sylvain wrote:

je crains plutôt que, quoi qu'il reconnaisse, il ne peux utiliser que
des instructions valides du proc. target; et (sauf grave erreur de ma
part) Intel n'a pas cablé de rotl / rotr (ni roll).

Les instructions rol et ror (ainsi que rcl / rcr) étaient déjà
présents dans le 8086 sorti il y a 28 ans, (voir par exemple
<http://www.cs.tut.fi/~siponen/upros/intel>) et depuis le 80386
vieux de 20 ans) ces instructions acceptent des opérandes de 32 bits.

Falk

Falk Tannhäuser wrote on 28/04/2006 23:22:

Sylvain wrote:

(sauf grave erreur de ma part)
Intel n'a pas cablé de rotl / rotr (ni roll).

Les instructions rol et ror (ainsi que rcl / rcr) étaient déjà
présents dans le 8086 sorti il y a 28 ans et depuis le 80386
vieux de 20 ans) ces instructions acceptent des opérandes de 32 bits.

c'était donc une grave erreur de ma part ;)

merci pour l'indication - je n'avais jamais cherché au bon endroit (rotl
au lieu de rcl).

un recodage rapide du SHA1 donne 46ms de gain pour 1 million de blocs de
64 octets traités (réf. 1,231 sec pour 1 million de blocs).

qu'est-ce qu'on va faire de tout ce temps gagné ? ;)

Sylvain.