Re: fonction c++
Finalement, voici le code assembleur de la fonction suivante généré pour un
processeur Itanium. Note : j'ai pris un tableu assez grand pour éviter les
loop unrolling et poub=voir tester les performances (pas fait pour finir)
uint BitCount(uint *w)
{
uint r = 0;
uint i;
for (i = 0; i 65536; i++)
{
r += *w 0x2;
*w = 1;
}
return(r);
}
Ce code doit être interprêté après avoir lu les documents mentionnés dans un
de mes mails d'hier. Sinon, toute conclusion relève du folklore... Pour
mémoire, Itanium a quadruplé chacune de ses unité fonctionnelle, il engendre
(dans ce cas) du code en modulo scheduled loop et il peut effectuer jusqu'à
4 opération en // par unité fonctionelle...
..L2:
BitCounter::
//file/line/col vm_app.c/45/1
// ***EntryOp*** CMid911, r32 = // A [vm_app.c: 45/1]
alloc r31 = ar.pfs, 1, 9, 0, 8 // M [vm_app.c: 45/1] [UVU: ]
mov ar.ec = 2 // I
brp.loop.few.imp ..L3, ..LB918 // B
ld4 r33 = [r32]// M [vm_app.c: 54/9] [UVuse]
add r8 = 0x, r0 ;; // I
mov r40 = ar.lc// I [vm_app.c: 45/1]
add r9 = 0, r32 ;; // M
nop.m 0 // M
mov r41 = pr // I [vm_app.c: 45/1]
// ***PseudoFenceOp***// A [vm_app.c: 45/1] [UVU: ]
cmp.ne.or.andcm p16, p17 = 42, r0 ;; // M
nop.m 0 // M
mov ar.lc = r8 // I
//file/line/col vm_app.c/50/6,52/5,54/9
add r8 = 0, r0 // M [vm_app.c: 50/6] [UVU: ]
nop.i 0 // I
nop.b 0 ;; // B
..L3:
nop.m 0 // M
(p16) extr.u r32 = r33, 16, 16 // I [vm_app.c: 55/9]
(p16) and r34 = 2, r33 // I [vm_app.c: 54/9]
(p17) add r8 = r8, r35 // M [vm_app.c: 54/9]
nop.f 0 // F
[..LB918:] br.ctop.dptk.few ..L3;; // B [vm_app.c: 52/16]
..L4:
//file/line/col vm_app.c/58/5
add r33 = 0, r34 // M
mov ar.lc = r40// I
add r32 = 0, r9 ;; // I
st4 [r32] = r33// M [vm_app.c: 55/9] [UVuse]
mov pr = r41, 0x1fffe // I [vm_app.c: 58/5]
br.ret.sptk.few rp ;; // B [vm_app.c: 58/5]
..L1:
// ***EndOp*** ;; // A
.endp BitCounter
Un mec d'HP m'a signalé qu'il existe une isnstruction beaucoup plus efficace
pour compter les bits. Voici donc le code :
#include machine/inline.h
uint BitCount(uint *w)
{
uint r = 0;
uint i;
for (i = 0; i 65536; i++)
{
r += _Asm_popcnt(*w);
w++;
}
}
A mon avis, il faut aussi réduire le nombre de boucle car l'opération
s'effectue sans doute sur 32 bits à la fois. DOnc pour un tableau de 128K
bits (131072), on n'effectue plus que 4096 boucles, au lieu de 65536 avec la
méthode précédente. De plus, l'instruction popcnt n'utilise qu'un seul cycle
machine au lieu de plusieurs isntructions avec ' '. Notez aussi que
l'incrémentation de w et i peut se faire dans le même cycle machine.
Un nouveau mêtier se dessine : programmeur assembleur sur Itanium :-)
Daniel
--
http://www-internal.alphanet.ch/linux-leman/ avant de poser
une question. Ouais, pour se désabonner aussi.
Investir dans le ``savoir faire'' (Was: Re: fonction c++)
On Tue, 3 Sep 2002, Daniel Cordey wrote: On Tuesday 03 September 2002 16:58, Marc SCHAEFER wrote: Sauf s'ils ont déjà renvoyé les personnes qui savaient. Ou que ceux-ci ont trouvé un meilleur boulot. Oui, c'est déjà arrivé par le passé (Apollo). Mais en général, les sociétés font un (petit) effort pour garder certains. Entre autre, losr de la fusion HP/Compaq, la connaissance était chez HP en ce qui concerne Itanium. D'après ce que je sais, l'équipe est toujours en place. (une entreprise n'a pas de savoir faire, elle a des employés). Aïe! Si ce que tu dis est vrai alors comment convaincre une entreprise d'investir dans la formation? C'est sans doute vrai dans le soft, nettement moins dans la mécanique :-) Intéressant! Comment l'entreprise conserve son savoir faire en changeant son personnel? -- Félix Hauri - [EMAIL PROTECTED] - http://www.f-hauri.ch -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: Investir dans le ``savoir faire'' (Was: Re: fonction c++)
On Wed, 4 Sep 2002, Félix Hauri wrote: (une entreprise n'a pas de savoir faire, elle a des employés). Aïe! Si ce que tu dis est vrai alors comment convaincre une entreprise d'investir dans la formation? Non, justement, et on refait la formation à chaque départ d'employé :) Comment l'entreprise conserve son savoir faire en changeant son personnel? En général quand tu quittes, tu es censé transmettre ton savoir. Sinon, on peut aussi s'arranger pour que tout le savoir d'une personne soit connu en partie par d'autres personnes. Ou, documenter tous les processus dans une démarche qualité. Bien sûr, dans certains domaines, ou si le savoir change très vite, une démarche qualité n'est même pas envisageable. Et l'expérience est très difficilement transférable. Finalement c'est à l'entreprise de s'organiser pour ce genre de cas: du point de vue de l'employeur, aucun employé ne devrait être indispensable: les impératifs pratiques font qu'en règle générale les employés qui partent en premier (ceux qui peuvent partir) sont ceux qui causent le plus de problèmes pour la perte du savoir. -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Monday 02 September 2002 21:52, Marc Mongenet wrote: Avec le ADDIB ça devient franchement du CISC (comme DBcc sur MC68000). Sauf que ADDIB prend 2 cycles avec le branchement ! Je ne sais plus. Je me souviens d'articles à propos des prévisions de performances que les fabricants font avant le premier prototype. Je suppose que chaque fabricant utilise cela pour optimiser le dimensionnement des caches, prédictions ou autre, non ? Maîtriser une architecture EPIC ne s'improvise pas du jours au lendemain. HP a aujourd'hui plusieurs longueurs d'avances dans cette technologie, car ils ont commencés à travailler la-dessus vers 1985-86. Ils ont surtout la gigantesque base d'instrumentation collectée avec les architectures HP-PA, dont Itanium est issu. Comme Intel/HP l'ont fait dans ce projet : http://www.intel.com/technology/itj/q32001/articles/art_4.htm Les gens d'HP sont des petits malins... Ils ont apportés l'architecture EPIC et la technologie des compilateurs dans le panier de la mariée; Intel ayant apporté la technologie de fabrication/production. Je suis sûr qu'ils n'ont pas tout donné et qu'ils conserve des technologies dans le domaine de l'optimisation avancée. Ils viennent d'ailleurs de le démontrer avec la fourniture du chipset ZX1 dont le développement ne se conçoit que si l'on maîtrise parfaitement les interactions entre la cache, la mémoire et les I/O pour une architecture Itanium. En conservant une légère avance, HP poura proposer des systèmes moins chers pour la même performance face à la concurrence. certainement sous HP-UX, mais l'inconnue concerne ce qu'il feront sous Linux... Daniel -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Monday 02 September 2002 21:52, Marc Mongenet wrote: Comme Intel/HP l'ont fait dans ce projet : http://www.intel.com/technology/itj/q32001/articles/art_4.htm Je suis en train de lire l'article, et avant d'avoir fini, je lis ce qui suit : There was no runtime environment available on UNIX. We had written a minimal set of runtime functions to interface with SoftSDV for our testing purposes. Each OS vendor had a different runtime environment. Our UNIX tool chain did not include a full-feature linker. Again OSVs were using their linker, which often behaved differently from what we were using. Not having a UNIX-based SoftSDV forced us to change our testing tools to work across platforms. A aucun moment, dans l'article, il n'est fait mention d'HP-UX... c'est hyper-mega suspet... Donc HP a bien laissé Intel se débroiller tout seul en fournissant de temps en temps un petit goodie quand Intel avait de la peine à avancer. C'est donc un projet uniquement Intel et les performances sont nettement en-dessous de ce qu'HP arrive à obtenir. Je vais partir à la chasse aux infos chez HP...:-) Daniel -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Tue, 3 Sep 2002, Daniel Cordey wrote: Maîtriser une architecture EPIC ne s'improvise pas du jours au lendemain. HP a aujourd'hui plusieurs longueurs d'avances dans cette technologie, car ils ont commencés à travailler la-dessus vers 1985-86. Sauf s'ils ont déjà renvoyé les personnes qui savaient. Ou que ceux-ci ont trouvé un meilleur boulot. (une entreprise n'a pas de savoir faire, elle a des employés). -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Tuesday 03 September 2002 16:58, Marc SCHAEFER wrote: Sauf s'ils ont déjà renvoyé les personnes qui savaient. Ou que ceux-ci ont trouvé un meilleur boulot. Oui, c'est déjà arrivé par le passé (Apollo). Mais en général, les sociétés font un (petit) effort pour garder certains. Entre autre, losr de la fusion HP/Compaq, la connaissance était chez HP en ce qui concerne Itanium. D'après ce que je sais, l'équipe est toujours en place. (une entreprise n'a pas de savoir faire, elle a des employés). C'est sans doute vrai dans le soft, nettement moins dans la mécanique :-) Daniel -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Monday 02 September 2002 01:05, Marc Mongenet wrote:
Sur un microprocesseur moderne je ne suis pas sûr que ce soit
possible. Avec le pipelining, la multi-scalarité, les prédictions
de branchement, les caches miss (L1/L2, instructions/données, TLB),
les problèmes d'alignement, les chargements spéculatifs, les dépendances
d'accès aux registres, les 100 autres instructions qui était in-fly
avant...
Je voulais sim[lement parler du nombre de cycle théorique de chacune de ces
instructions. Ce nombre de cycles varie fortement suivant les instructions et
chacun des modes d'adressages sur les processeurs CISC. Alors, qu'avec des
processeurs RISC, le nombre de cycle pour exécuter une instruction est fixe;
mis à part les instructions FP (+-* /). Cette comparaison est quand même
utile puisque, dans le cas qui nous a préoccupé ces derniers jours, on compte
le nombre d'instruction à l'intérieur de chaque boucle. Comm il est
nécessaire de ne manipuler que des valeurs dans des registres, afin de
bénéficier des meilleures performances, tout le monde est logé à la même
enseigne. De plus, on examine uniquement l'exécution des instructions sans
tenir compte des caches, TLB et autres technologies; qui ne sont quasi pas
¨prédictibles au niveau des temps d'exécution.
En ce qui concerne les processeurs RISC, il existe certainement beaucoup de
différences entre les différents CPUs et version de compilateurs. je ne peux
donner que des infos concernant les pocesseurs HP-PA 2.0. L'analyse di code
assembleur est particulièrement difficile car l'optimisation se fait déjà au
niveau des expressions C et ensuite au niveau de l'architecture du CPU. Comme
sur HP-PA 2.0, toutes les unités fonctionnelles sont doublées, le
compilateurs va essayer de // le code quand cela est possible (ou rentable).
J'ai du tricher un peu dans le nombre de boucles à effectuer car sans cela le
compilateur me déeroulait le code afin d'utiliser un maximum d'unités
fonctionnelles. De plus HP-PA dispose d'opération compound qui font quatre
choses en même temps; par exemple ADDIB effectue une adition, une
assignation, un test et un branchement. Cette instruction est massivement
utilisée dans les boucles for mais son placement et sa combinaison avec les
autres instructions est moins évidente que pour le code d'un processeurs
CISC. Pour exemple, je vous libre le code assembleur générer pour un HP-PA
2.0 sous HP-UX 11.0, à partir du code :
for(i = 0; i 2048; i++)
{
r += w 0xff;
w = 16;
}
Notez que j'ai du définir le nombre de boucles à 2048 (32 ou 64 aurait sans
doute suffit), car sans cela, j'aurais eu, non plus une boucle, mais un
paquet de lignes avec EXTRW et ADD. La dernière instruction EXTRW %31, 15...
est effectuée en même temps que le test de ADDIB et est nullifiée au cas ou
le branchement vers $0003 ne s'effectue pas (fin de boucle). Donc les
deux EXTRW sont effectués l'un dérrière l'autre, puis l'addition (r + w...)
et enfin l'assignation (r = ) avec l'incrémentattion ete le test de fin de
boucle (i++, i 2048).
$0003
EXTRW,U %r31,31,8,%r24 ;offset 0x10
ADD,L %r28,%r24,%r28 ;offset 0x14
$0001
ADDIB,1,%r23,$0003;offset 0x18
EXTRW,U %r31,15,16,%r31 ;offset 0x1c
Il est difficile de penser plus compact :-) Par contre il est certain que la
forme du code pour Itanium serait totalemnt différente. Pourquoi ? Pour
pouvoir // encore plus le contenu de la boucle à l'aide de la focntionalité
qui permet de décaler tous les registres à chaque itératon de la boucle.
Itanium serait alors capable d'effectuer le calcul pour 4 itérations d'une
boucle à la fois !!!
D'après ce que j'ai cru comprendre (notemment des mauvaises surprises avec
l'Itanium) même les simulateurs des fabriquants ne donnent pas des
résultats fiables.
Quel fabricants ? Il n'y a qu'un seil fabricant (Intel) et une société qui
possède des simulateurs depuis bientôt 10 ans (HP), qui se trouve être celle
qui maîtrise le mieux les compilateurs de cette architecture... et le
concepteur du jeux d'instructions... Je ne doute pas que les gens qui sont au
coeur des optimiseurs de gcc se mettront rapidement à niveau, mais il faudra
du temps car c'est une technologie hyper pointue et pas facile à maitriser.
Je RE-encourage tous le monde à lire les articles mentionnés en juin dans
l'un de mes mails; afin de comprendre la complexité de ce qu'est l'assembleur
sur Itanium. Ça fait un moment que je ne fais plus d'assembleur, mais là je
laisse complètement tomber :-)
http://www.hp.com/products1/itanium/infolibrary/whitepapers/ia64_overview_wp.html
http://www.hp.com/products1/itanium/infolibrary/whitepapers/os_compiler.pdf
http://www.hp.com/products1/itanium/chipset/analyst_report.pdf
Daniel
--
http://www-internal.alphanet.ch/linux-leman/ avant de poser
une question. Ouais, pour se désabonner aussi.
Re: fonction c++
Daniel Cordey wrote: On Monday 02 September 2002 01:05, Marc Mongenet wrote: $0003 EXTRW,U %r31,31,8,%r24 ;offset 0x10 ADD,L %r28,%r24,%r28 ;offset 0x14 $0001 ADDIB,1,%r23,$0003;offset 0x18 EXTRW,U %r31,15,16,%r31 ;offset 0x1c J'avais lu que l'architecture avait des instructions assez 'spéciales', mais utilisées très efficacement par HP, d'où les bons benchmarks. Ce EXTRW m'a effectivement l'air particulier(ement efficace). Avec le ADDIB ça devient franchement du CISC (comme DBcc sur MC68000). D'après ce que j'ai cru comprendre (notemment des mauvaises surprises avec l'Itanium) même les simulateurs des fabriquants ne donnent pas des résultats fiables. Quel fabricants ? Il n'y a qu'un seil fabricant (Intel) et une société qui possède des simulateurs depuis bientôt 10 ans (HP), qui se trouve être celle qui maîtrise le mieux les compilateurs de cette architecture... et le concepteur du jeux d'instructions... Je ne sais plus. Je me souviens d'articles à propos des prévisions de performances que les fabricants font avant le premier prototype. Je suppose que chaque fabricant utilise cela pour optimiser le dimensionnement des caches, prédictions ou autre, non ? Comme Intel/HP l'ont fait dans ce projet : http://www.intel.com/technology/itj/q32001/articles/art_4.htm Marc Mongenet -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Sat, 31 Aug 2002, Marc Mongenet wrote: Sur Motorola 68000 (désolé, je ne connais pas assez le 386, déjà le 68000 j'oublie), une boucle de 3 instructions : Le dernier processeur à assembleur confortable ? :) -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Friday 30 August 2002 20:08, Roman Merz wrote: Bien d'accord que des autres principes peuvent etre plus efficaces. btw une multiplication par deux est souvent traduit par add eax, eax. Et maintenant, il reste à faire la somme des cycles machines pour chaque boucle. J'imagine que sur ix6 une multiplication s'ffectue sur plisueieurs cycles... De plus, qule prix à payer pour les 'test', 'lea' et 'jnz' ? Daniel -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Sunday 01 September 2002 18:25, Marc SCHAEFER wrote: On Sat, 31 Aug 2002, Marc Mongenet wrote: Sur Motorola 68000 (désolé, je ne connais pas assez le 386, déjà le 68000 j'oublie), une boucle de 3 instructions : Le dernier processeur à assembleur confortable ? Ouai, parcequ'avec Itanium c'est carément du masochisme :-) Daniel -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
Daniel Cordey wrote: Bien d'accord que des autres principes peuvent etre plus efficaces. btw une multiplication par deux est souvent traduit par add eax, eax. Et maintenant, il reste à faire la somme des cycles machines pour chaque boucle. J'imagine que sur ix6 une multiplication s'ffectue sur plisueieurs cycles... De plus, qule prix à payer pour les 'test', 'lea' et 'jnz' ? Sur un microprocesseur moderne je ne suis pas sûr que ce soit possible. Avec le pipelining, la multi-scalarité, les prédictions de branchement, les caches miss (L1/L2, instructions/données, TLB), les problèmes d'alignement, les chargements spéculatifs, les dépendances d'accès aux registres, les 100 autres instructions qui était in-fly avant... D'après ce que j'ai cru comprendre (notemment des mauvaises surprises avec l'Itanium) même les simulateurs des fabriquants ne donnent pas des résultats fiables. Marc Mongenet -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Thursday 29 August 2002 19:32, Ivo Bloechliger wrote:
for (i = 0; i 16; ++i) {
r += w % 2 ; // on accumule le reste de la division entiere par deux
w = w / 2; // division entiere */
Sauf erreur, le compilateur est capable de détecter une
division/multiplication par une constante puissance de 2, et de transformer
cette opération en bit-shift équivalent. Ce qui fait que :
w = w / 2;
est en fait transformer en équivalent :
w =1;
C'est donc particulièrement rapide. Par contre je pense qu'écrire :
r += w 1;
devrait être plus rapide q'une opération de modulo :
r += w % 2 ;
Seul le résultat du bench nous dira si la téorie se confirme :-)
Ce genre de code devrait être optimisé de manière impressionnante sur un
processeur Itanium (sous Linux avec gcc ou HP-UX, pas W* !)
Daniel
--
http://www-internal.alphanet.ch/linux-leman/ avant de poser
une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Fri, 30 Aug 2002, Félix Hauri wrote: [ dans le cas présent, sauf problèmes de mémoire, je passerais probablement par le tableau de 64k, en particulier vu qu'avec un seul déréférencement on y arrive et que le nombre de bits à 1 est au max 16) ] Si on tourne dans l'autre sens ( x2 au lieu de /2 ) alors on doit pouvoir se contenter d'additionner le bit de retenue (si tant est que cette notion existe en C, vieux souvenir d'assembleur;) Non, pas à ma connaissance, il faudra passer par l'assembleur (d'ailleurs pas toutes les variantes des bit shifts assembleur font de la retenue). D'ailleurs il me semble qu'il y a deux retenues, une pour overflow, et une pour underflow, parfois jointes, et que une est utilisée dans le shift left, l'autre dans le shift right. PS: pour revenir à l'idée de division entière et de modulo, il ne faut pas oublier que beaucoup de processeurs ont une opération de division qui fait les deux à la fois. Je l'ai utilisé une fois pour gagner un temps précieux pour du RAID0 à multiple de 3 disques dans un contrôleur hard, avec distribution par secteur (chunk_size = 1 secteur). (la division pour connaître le numéro physique du secteur, le modulo pour connaître le numéro du disque physique). -- http://www-internal.alphanet.ch/linux-leman/ avant de poser une question. Ouais, pour se désabonner aussi.
Re: fonction c++
On Thu, Aug 29, 2002 at 06:34:28PM +0200, Francois Ryser wrote:
Bonjours,
Je recherche une methode en c++ de compter le nombre de bits a 1 dans des
mots de 16 bits, mais avec un imperatif de vitesse car nous devons faire sur
1 million de mots de 16 bits
utilise la division modulo avec 2, qui donne le reste de la division :
r = 0;
w = ;
for (i = 0; i 16; ++i) {
r += w % 2 ; // on accumule le reste de la division entiere par deux
w = w / 2; // division entiere */
}
avec un processeur actuelle, ca devrait prendre dans les 10ms pour
ton million de mot de 16 bits
y doit y avoir plus rapide, mais ca vaut probablement pas
la peine de se creuser plus les meninges je crois.
--
Philippe Strauss
http://philou.ch/
L'indifférence est le plus grand risque de notre temps,
la forme civilisée de la cruauté. -- Zenta Maurina
.
--
http://www-internal.alphanet.ch/linux-leman/ avant de poser
une question. Ouais, pour se désabonner aussi.
Re: fonction c++
Philippe Strauss wrote:
[EMAIL PROTECTED]">
On Thu, Aug 29, 2002 at 06:34:28PM +0200, Francois Ryser wrote:
Bonjours,Je recherche une methode en c++ de compter le nombre de bits a 1 dans desmots de 16 bits, mais avec un imperatif de vitesse car nous devons faire sur1 million de mots de 16 bits
Je pense que l'utilisation d'oprations sur bits devrait tre plus rapide
du style (pour l'intrieur de la boucle).
r += w 1; // bit-wise logical AND
w =1;// bit-shift
Sinon faire un tableau 65536 (=2^16) entres et stocker les rsultat peut
valoir la peine dans ton cas galement.
Mais bon il y a encore mieux :-( http://www.devx.com/free/tips/tipview.asp?content_id=3839
[EMAIL PROTECTED]">
utilise la division modulo avec 2, qui donne le reste de la division :r = 0;w = ;for (i = 0; i 16; ++i) {r += w % 2 ; // on accumule le reste de la division entiere par deux w = w / 2; // division entiere */
--
Ivo BloechligerPrsident GNU Generation
EPFL-FSB-IMA-RO-SE Association d'tudiants pour
1015 Lausanne la promotion des logiciels libres
http://rose.epfl.chhttp://gnugeneration.epfl.ch
Re: fonction c++
Ivo Bloechliger wrote:
On Thu, Aug 29, 2002 at 06:34:28PM +0200, Francois Ryser wrote:
Bonjours,
Je recherche une methode en c++ de compter le nombre de bits a 1 dans des
mots de 16 bits, mais avec un imperatif de vitesse car nous devons faire sur
1 million de mots de 16 bits
Je pense que l'utilisation d'opérations sur bits devrait être plus
rapide du style (pour l'intérieur de la boucle).
r += w 1; // bit-wise logical AND
w =1; // bit-shift
unsigned int while_cnt (unsigned int mot)
{
unsigned int res = 0;
while (mot != 0) {
res += mot 1;
mot = 1;
}
return res;
}
Ou bien le plus simple, avec la bibliothèque standard :
unsigned int std_cnt (unsigned short mot)
{
return std::bitset16(mot).count();
}
Sinon faire un tableau à 65536 (=2^16) entrées et stocker les résultat
peut valoir la peine dans ton cas également.
unsigned int tab_cnt2 (unsigned short mot)
{
return lookup16[mot];
}
Ou bien avec un tableau de 256 entrées utilisé 2 fois.
unsigned int tab_cnt (unsigned short mot)
{
return lookup8[mot 0xFF] + lookup8[mot 8];
}
Mais bon il y a encore mieux :-(
http://www.devx.com/free/tips/tipview.asp?content_id=3839
Certainement la plus rapide pour des mots de 32 bits.
On pourrait sans doute l'optimiser pour du 16 bits
car j'obtiens de meilleures résultat avec double lookup
(sans doute meilleur que lookup2 car utilisant mieux la
cache de données).
Temps relatifs sur mon PC (K6)
0.162030 s par tab_cnt
0.200805 s par count_bits
0.239354 s par tab_cnt2
0.343694 s par std_cnt
0.445795 s par while_cnt
Marc Mongenet
--
http://www-internal.alphanet.ch/linux-leman/ avant de poser
une question. Ouais, pour se désabonner aussi.
