Compter les bits non nuls: banal !!!

Soyez le premier à donner votre avis sur cette source.

Vue 4 872 fois - Téléchargée 187 fois

Description

Pourquoi trouve-t-on des codes 100 fois plus rapides que d'autres ?
Est-ce un problème "trop simple" pour y découvrir quelques astuces ?

Voici 35 méthodes qui comptent les bits (BitCount, Population) et qui vous donneront des éléments de réponse.

Dans cet exposé, il faut remplacer le caractère # par 8, 16, 32 ou 64 selon la taille des mots à traiter.
L'ensemble de tous les sources se trouve dans le fichier Pop.cpp .
 
 

PopA#: comptage


L'idée est de parcourir tous les bits avec un 1 "shifté" à gauche et de compter tous les produits binaires non nuls:
int PopA#(uint#_t k) {
  int n=0;
  for (int i=0; i<#; i++) if (k&(1<<i)) ++n;
  return n;
}

 
 

PopB#: autre comptage


On peut aussi compter l'imparité du nombre à tester k en le décalant successivement une position à droite:
Dans ce cas, on peut s'arrêter dès que k=0.
int PopB#(uint#_t k) {
  int n=0;
  do n+=k&1; while (k>>=1);
  return n;
}

 
 

PopC#: comptage pour population éparse


L'instruction k = k&(k-1) est intéressante car elle permet d'éliminer le dernier bit non nul.
Utilisons-la pour ce comptage, efficace lorsque les "1" sont éparses (rares):
int PopC#(uint#_t k) {
  int n=0;
  while (k) {++n; k&=k-1;}
  return n;
}

 
 

PopD#: additions par groupes


On subdivise d'abord le mot en groupes de 2 bits.
On sélectionne tous les premiers bits de chaque groupe, puis les seconds en les décalant à droite.
Une seule addition suffit alors pour faire les sommes de tous les groupes, qui ne peuvent pas se chevaucher, puisque les sommes sont <= 2.
On répète une méthode similaire basée cette fois sur des groupes de 4 bits, et ainsi de suite.
int PopD8(uint32_t k) {
  k=(k&0X55)+((k>>1)&0X55);
  k=(k&0X33)+((k>>2)&0X33);
  return (k&0X0F)+(k>>4);
}
int PopD16(uint32_t k) {
  k=(k&0X5555)+((k>>1)&0X5555);
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k&0X0F0F)+((k>>4)&0X0F0F);
  return (k&0X00FF)+(k>>8);
}
int PopD32(uint32_t k) {
  k=(k&0X55555555)+((k>>1)&0X55555555);
  k=(k&0X33333333)+((k>>2)&0X33333333);
  k=(k&0X0F0F0F0F)+((k>>4)&0X0F0F0F0F);
  k=(k&0X00FF00FF)+((k>>8)&0X00FF00FF);
  return (k&0X0000FFFF)+(k>>16);
}
int PopD64(uint64_t k) {
  k=(k&0X5555555555555555)+((k>> 1)&0X5555555555555555);
  k=(k&0X3333333333333333)+((k>> 2)&0X3333333333333333);
  k=(k&0X0F0F0F0F0F0F0F0F)+((k>> 4)&0X0F0F0F0F0F0F0F0F);
  k=(k&0X00FF00FF00FF00FF)+((k>> 8)&0X00FF00FF00FF00FF);
  k=(k&0X0000FFFF0000FFFF)+((k>>16)&0X0000FFFF0000FFFF);
  return (k&0X00000000FFFFFFFF)+(k>>32);
}

 
 

PopE#: Additions par groupes bis


Avant d'optimiser les codes PopD#, constatons que les deux basés sur 8 ou 16 bits sont nettement plus lents que celui de 32.
Remède: transformer le type uint8_t ou uint16_t du paramètre en uint32_t au début du code.
L'amélioration est surprenante.
int PopE8(uint8_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X55;
  k=(k&0X33)+((k>>2)&0X33);
  return (k+(k>>4))&0x0F0F;
}
int PopE16(uint16_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X5555;
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k+(k>>4))&0x0F0F;
  return (k+(k>>8))&0x0000001F;
}

 
 

PopF#: Additions par groupes optimisé


Peut-on encore simplifier les codes PopD# (ou PopE#) ? Il semble que oui.

La première ligne de code, par exemple:
k = (k&0X55555555) + ((k>>1)&0X55555555); peut être remplacée par:  k = k - ((k>>1)&0X55555555);
Contrôlons cela pour les 4 combinaisons possibles dans un groupe à 2 bits:
  00: 0-0=0 ; 01: 1-0=1 ; 10: 2-1=1 ; 11: 3-1=2 .
Résultats qui représentent bien le nombre de bits à 1 dans les différents groupes de 2 bits.

La troisième ligne k = (k&0X0F0F0F0F) + ((k>>4)&0X0F0F0F0F);
peut aussi se simplifier en: k = (k + (k>>4))&0x0F0F0F0F;
En effet, à ce stade, k contient les sommes des groupes de 4 bits, comprises entre 0 et 4.
Comme chaque somme tient dans 4 bits, il suffit d'appliquer le masque 0X0F0F0F0F sur le résultat.

Dans les quatrième et cinquième lignes, on peut même éviter l'utilisation du masque en limitant simplement le résultat à ses 7 premiers bits.
Ce qui donne:
int PopF32(uint32_t k) {
  k-=(k>>1)&0X55555555;
  k=(k&0X33333333)+((k>>2)&0X33333333);
  k=(k+(k>>4))&0X0F0F0F0F;
  k+=(k>>8);
  k+=(k>>16);
  return k&0X0000003F;
}

Finalement, j'ai retenu dans le fichier 'Pop.cpp' les codes suivants:
int PopF8(uint8_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X55;
  k=(k&0X33)+((k>>2)&0X33);
  return (k+(k>>4))&0X0F;
}
int PopF16(uint16_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X5555;
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k+(k>>4))&0X0F0F;
  return (k+(k>>8))&0X001F;
}
int PopF32(uint32_t k) {
  k-=(k>>1)&0X55555555;
  k=(k&0X33333333)+((k>>2)&0X33333333);
  k=(k+(k>>4))&0X0F0F0F0F;
  k+=(k>>8);
  return (k+(k>>16))&0X0000003F;
}
int PopF64(uint64_t k) {
  k-=(k>>1)&0X5555555555555555;
  k=(k&0X3333333333333333)+((k>>2)&0X3333333333333333);
  k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
  k+=(k>>8);
  k+=(k>>16);
  return (k+(k>>32))&0X0000007F;
}

PopF32 correspond au code proposé dans le "Hacker's Delight".
 
 

PopG#: multiplication


Comme le montre ce tableau,
 0 1 2 3 4 5 6 7 8 9 A B C D E F = k
 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 = n = (k>>1)&0X7777777777777777
 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 = k = k-n
 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 = n = (n>>1)&0X7777777777777777
 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 = k = k-n
 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 = n = (n>>1)&0X7777777777777777
 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 = k = k-n,
les 6 premières lignes de chacun des 4 codes suivants permettent de compter la population par groupe de 4.
Puis, k=(k+(k>>4))&0X0F0F0F0F effectue la somme par byte (ou groupe de 8 bits).
Le produit par 0X0101, 0X01010101 ou 0X0101010101010101 permet de faire d'un coup la somme de tous ces bytes. Exemple:
//      0X0r0s0t0u * 0X01010101         (avec 0 <= r,s,t,u <= 8)
//    = 0X0r0s0t0u
//    + 0X0s0t0u
//    + 0X0t0u
//    + 0X0u
//    = 0Xzz??????                      (avec zz = r+s+t+u <= 32)

int PopG16(uint16_t kk) {
	uint32_t k=kk,n=(k>>1)&0X7777;
	k-=n;
	n=(n>>1)&0X7777;
	k-=n;
	n=(n>>1)&0X7777;
	k-=n;
	k=(k+(k>>4))&0X0F0F;
  return ((k*0X0101)>>8)&0X1F;
}
int PopG32(uint32_t k) {
	uint32_t n=(k>>1)&0X77777777;
	k-=n;
	n=(n>>1)&0X77777777;
	k-=n;
	n=(n>>1)&0X77777777;
	k-=n;
	k=(k+(k>>4))&0X0F0F0F0F;
	return (k*0X01010101)>>24;
}
int PopG64(uint64_t k) {
	uint64_t n=(k>>1)&0X7777777777777777;
	k-=n;
	n=(n>>1)&0X7777777777777777;
	k-=n;
	n=(n>>1)&0X7777777777777777;
	k-=n;
	k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
	return (k*0X0101010101010101)>>56;
}

 
 

PopH#: addition et multiplication


Ici, nous prenons le début de PopF# et la fin de PopG#:
int PopH16(uint16_t kk) {
	uint32_t k=kk;
	k-=(k>>1)&0X5555;
	k=(k&0X3333)+((k>>2)&0X3333);
	k=(k+(k>>4))&0X0F0F;
  return ((k*0X0101)>>8)&0X1F;
}
int PopH32(uint32_t k) {
	k-=(k>>1)&0X55555555;
	k=(k&0X33333333)+((k>>2)&0X33333333);
	k=(k+(k>>4))&0X0F0F0F0F;
	return (k*0X01010101)>>24;
}
int PopH64(uint64_t k) {
	k-=(k>>1)&0X5555555555555555;
	k=(k&0X3333333333333333)+((k>>2)&0X3333333333333333);
	k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
	return (k*0X0101010101010101)>>56;
}

 

PopI#: 256 bytes précomptés


La méthode est basée sur un array de 256 éléments contenant la somme des bits de l'index.
inline int PopI8(uint8_t k) {return T8[k];}
inline int PopI16(uint16_t k) {return (T8[k&255]+T8[k>>8]);}
inline int PopI32(uint32_t k) {
  return (T8[k&0XFF]+T8[(k>>8)&0XFF]+T8[(k>>16)&0XFF]+T8[k>>24]);
}
inline int PopI64(uint64_t k) {
  return T8[k&0XFF]+T8[(k>>8)&0XFF]+T8[(k>>16)&0XFF]+T8[(k>>24)&0XFF]
    +T8[(k>>32)&0XFF]+T8[(k>>40)&0XFF]+T8[(k>>48)&0XFF]+T8[k>>56];
}

 
 

PopJ#: 65536 shorts précomptés


Et la dernière méthode présentée est basée sur un array de 65536 éléments (T16) contenant la somme des bits de l'index.
inline int PopJ16(uint16_t k) {return T16[k];}
inline int PopJ32(uint32_t k) {return (T16[k&0XFFFF]+T16[k>>16]);}
inline int PopJ64(uint64_t k) {
  return (T16[k&0XFFFF]+T16[(k>>16)&0XFFFF]+T16[(k>>32)&0XFFFF]+T16[k>>48]);
}

 
 

Temps utilisé pour compter 1 miliard de bits


Dans main(), le vecteur V64 est rempli avec des valeurs aléatoires, et de leur compléments (on a donc exactement la moitié des bits à "1").
V64 est alors analysé en tant que array of uint8_t, uint16_t, uint32_t, uint64_t, selon le type de fonction.
Vous pouvez aussi compiler (en release) et exécuter le fichier Pop.cpp.

PopA: comptage
   8 Bits: s=500000000, t=2605 ms
  16 Bits: s=500000000, t=3759 ms
  32 Bits: s=500000000, t=3588 ms
  64 Bits: s=500000000, t=5835 ms
PopB: autre comptage
   8 Bits: s=500000000, t=1138 ms
  16 Bits: s=500000000, t=4243 ms
  32 Bits: s=500000000, t=920 ms
  64 Bits: s=500000000, t=1872 ms
PopC: comptage pour population éparse
   8 Bits: s=500000000, t=1482 ms
  16 Bits: s=500000000, t=858 ms
  32 Bits: s=500000000, t=561 ms
  64 Bits: s=500000000, t=1061 ms
PopD: addition par groupes
   8 Bits: s=500000000, t=405 ms
  16 Bits: s=500000000, t=249 ms
  32 Bits: s=500000000, t=31 ms
  64 Bits: s=500000000, t=171 ms
PopE: addition par groupes bis
   8 Bits: s=500000000, t=78 ms
  16 Bits: s=500000000, t=47 ms
PopF: addition par groupes optimisé
   8 Bits: s=500000000, t=78 ms
  16 Bits: s=500000000, t=60 ms
  32 Bits: s=500000000, t=31 ms
  64 Bits: s=500000000, t=156 ms
PopG: multiplication
  16 Bits: s=500000000, t=62 ms
  32 Bits: s=500000000, t=31 ms
  64 Bits: s=500000000, t=202 ms
PopH: addition et multiplication
  16 Bits: s=500000000, t=46 ms
  32 Bits: s=500000000, t=31 ms
  64 Bits: s=500000000, t=172 ms
PopI: 256 bytes précomptés
   8 Bits: s=500000000, t=78 ms
  16 Bits: s=500000000, t=78 ms
  32 Bits: s=500000000, t=109 ms
  64 Bits: s=500000000, t=94 ms
PopJ: 65536 shorts précomptés
  16 Bits: s=500000000, t=62 ms
  32 Bits: s=500000000, t=62 ms
  64 Bits: s=500000000, t=69 ms

J'espère que ces mesures vous aideront à formuler votre propre conclusion.

Remarque: il me semble que les méthodes basés sur 64 bits sont relativement lentes, alors que mon système fonctionne sur 64 bits.
J'ai remarqué que MS VS Express 2013 charge kernel32.dll.
Existe-t-il un équivalent 64 bits "kernel64.dll" ?
Merci d'avance à ceux qui voudraient bien éclairer ma lanterne.

Le zip comprend les fichiers "Pop.cpp" et "Description.txt"

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

Mon intention n'est pas de faire ici un "snippet".
Mais je n'arrive pas à insérer le zip (5 ko).
Après avoir désigné le fichier zip en question, et cliqué sur "Charger", les 5 points défilent "éternellement" et on me demande si je veux ouvrir ou enregistrer "save.json" !?!


Pour y remédier, je donne ici le contenu du fichier Pop.cpp:

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NB 1000000000
uint64_t V64[NB/64];
uint8_t T8[256],T16[65536];

//×× PopA: comptage ×××××××××××××××××××××××××××××××××××××××××××××
int PopA8(uint8_t k) {
int n=0;
for(int i=0; i<8; i++) if(k&(1<<i)) ++n;
return n;
}
int PopA16(uint16_t k) {
int n=0;
for(int i=0; i<16; i++) if(k&(1<<i)) ++n;
return n;
}
int PopA32(uint32_t k) {
int n=0;
for(int i=0; i<32; i++) if(k&(1<<i)) ++n;
return n;
}
int PopA64(uint64_t k) {
int n=0;
for(int i=0; i<64; i++) if(k&(1ll<<i)) ++n;
return n;
}
//×× PopB: autre comptage ×××××××××××××××××××××××××××××××××××××××
int PopB8(uint8_t k) {
int n=0;
do n+=k&1; while(k>>=1);
return n;
}
int PopB16(uint16_t k) {
int n=0;
do n+=k&1; while(k>>=1);
return n;
}
int PopB32(uint32_t k) {
int n=0;
do n+=k&1; while(k>>=1);
return n;
}
int PopB64(uint64_t k) {
int n=0;
do n+=k&1; while(k>>=1);
return n;
}
//×× PopC: comptage pour population éparse ××××××××××××××××××××××
int PopC8(uint8_t k) {
int n=0;
while(k) {++n; k&=k-1;}
return n;
}
int PopC16(uint16_t k) {
int n=0;
while(k) {++n; k&=k-1;}
return n;
}
int PopC32(uint32_t k) {
int n=0;
while(k) {++n; k&=k-1;}
return n;
}
int PopC64(uint64_t k) {
int n=0;
while(k) {++n; k&=k-1;}
return n;
}
//×× PopD: addition par groupes ×××××××××××××××××××××××××××××××××
int PopD8(uint8_t k) {
k=(k&0X55)+((k>>1)&0X55);
k=(k&0X33)+((k>>2)&0X33);
return (k&0X0F)+(k>>4);
}
int PopD16(uint16_t k) {
k-=(k>>1)&0X5555;
k=(k&0X3333)+((k>>2)&0X3333);
k=(k&0X0F0F)+((k>>4)&0X0F0F);
return (k&0X00FF)+(k>>8);
}
int PopD32(uint32_t k) {
k=(k&0X55555555)+((k>>1)&0X55555555);
k=(k&0X33333333)+((k>>2)&0X33333333);
k=(k&0X0F0F0F0F)+((k>>4)&0X0F0F0F0F);
k=(k&0X00FF00FF)+((k>>8)&0X00FF00FF);
return (k&0X0000FFFF)+(k>>16);
}
int PopD64(uint64_t k) {
k=(k&0X5555555555555555)+((k>> 1)&0X5555555555555555);
k=(k&0X3333333333333333)+((k>> 2)&0X3333333333333333);
k=(k&0X0F0F0F0F0F0F0F0F)+((k>> 4)&0X0F0F0F0F0F0F0F0F);
k=(k&0X00FF00FF00FF00FF)+((k>> 8)&0X00FF00FF00FF00FF);
k=(k&0X0000FFFF0000FFFF)+((k>>16)&0X0000FFFF0000FFFF);
return (k&0X00000000FFFFFFFF)+(k>>32);
}
//×× PopE: addition par groupes bis ×××××××××××××××××××××××××××××××××
int PopE8(uint8_t kk) {
uint32_t k=kk;
k-=(k>>1)&0X55;
k=(k&0X33)+((k>>2)&0X33);
return (k+(k>>4))&0X0F;
}
int PopE16(uint16_t kk) {
uint32_t k=kk;
k-=(k>>1)&0X5555;
k=(k&0X3333)+((k>>2)&0X3333);
k=(k+(k>>4))&0X0F0F;
return (k+(k>>8))&0X0000001F;
}
//×× PopF: addition par groupes optimisé ×××××××××××××××××××××××××××××××××
int PopF8(uint8_t kk) {
uint32_t k=kk;
k-=(k>>1)&0X55;
k=(k&0X33)+((k>>2)&0X33);
return (k+(k>>4))&0X0F;
}
int PopF16(uint16_t kk) {
uint32_t k=kk;
k-=(k>>1)&0X5555;
k=(k&0X3333)+((k>>2)&0X3333);
k=(k+(k>>4))&0X0F0F;
return (k+(k>>8))&0X001F;
}
int PopF32(uint32_t k) {
k-=(k>>1)&0X55555555;
k=(k&0X33333333)+((k>>2)&0X33333333);
k=(k+(k>>4))&0X0F0F0F0F;
k+=(k>>8);
return (k+(k>>16))&0X0000003F;
}
int PopF64(uint64_t k) {
k-=(k>>1)&0X5555555555555555;
k=(k&0X3333333333333333)+((k>>2)&0X3333333333333333);
k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
k+=(k>>8);
k+=(k>>16);
return (k+(k>>32))&0X0000007F;
}
//×× PopG: multiplication ×××××××××××××××××××××××××××××××××××××
int PopG16(uint16_t kk) {
uint32_t k=kk,n=(k>>1)&0X7777;
k-=n;
n=(n>>1)&0X7777;
k-=n;
n=(n>>1)&0X7777;
k-=n;
k=(k+(k>>4))&0X0F0F;
return ((k*0X0101)>>8)&0X1F;
}
int PopG32(uint32_t k) {
uint32_t n=(k>>1)&0X77777777;
k-=n;
n=(n>>1)&0X77777777;
k-=n;
n=(n>>1)&0X77777777;
k-=n;
k=(k+(k>>4))&0X0F0F0F0F;
return (k*0X01010101)>>24;
}
int PopG64(uint64_t k) {
uint64_t n=(k>>1)&0X7777777777777777;
k-=n;
n=(n>>1)&0X7777777777777777;
k-=n;
n=(n>>1)&0X7777777777777777;
k-=n;
k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
return (k*0X0101010101010101)>>56;
}
//×× PopH: addition et multiplication ×××××××××××××××××××××××××××××××××
int PopH16(uint16_t kk) {
uint32_t k=kk;
k-=(k>>1)&0X5555;
k=(k&0X3333)+((k>>2)&0X3333);
k=(k+(k>>4))&0X0F0F;
return ((k*0X0101)>>8)&0X1F;
}
int PopH32(uint32_t k) {
k-=(k>>1)&0X55555555;
k=(k&0X33333333)+((k>>2)&0X33333333);
k=(k+(k>>4))&0X0F0F0F0F;
return (k*0X01010101)>>24;
}
int PopH64(uint64_t k) {
k-=(k>>1)&0X5555555555555555;
k=(k&0X3333333333333333)+((k>>2)&0X3333333333333333);
k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
return (k*0X0101010101010101)>>56;
}
//×× PopI: 256 bytes précomptés ×××××××××××××××××××××××××××××××××××××
inline int PopI8(uint8_t k) { return T8[k]; }
inline int PopI16(uint16_t k) { return T8[k&0XFF]+T8[k>>8]; }
inline int PopI32(uint32_t k) {
return T8[k&0XFF]+T8[(k>>8)&0XFF]+T8[(k>>16)&0XFF]+T8[k>>24];
}
inline int PopI64(uint64_t k) {
return T8[k&0XFF]+T8[(k>>8)&0XFF]+T8[(k>>16)&0XFF]+T8[(k>>24)&0XFF]
+T8[(k>>32)&0XFF]+T8[(k>>40)&0XFF]+T8[(k>>48)&0XFF]+T8[k>>56];
}
//×× PopJ: 65536 shorts précomptés ××××××××××××××××××××××××××××××
inline int PopJ16(uint16_t k) {return T16[k];}
inline int PopJ32(uint32_t k) {return (T16[k&0XFFFF]+T16[k>>16]);}
inline int PopJ64(uint64_t k) {
return T16[k&0XFFFF]+T16[(k>>16)&0XFFFF]+T16[(k>>32)&0XFFFF]+T16[k>>48];
}
//×× Fonctions communes ××××××××××××××××××××××××××××××××××××××××××××××
void Count8(int(*F8)(uint8_t)) {
clock_t t=clock();
uint8_t *v8=(uint8_t*)&V64;
uint32_t s=0;
for(uint32_t n=0; n<NB/8; ++n) s+=F8(v8[n]);
printf(" 8 Bits: s=%u, t=%u ms\n",s,clock()-t);
}
void Count16(int(*F16)(uint16_t)) {
clock_t t=clock();
uint16_t *v16=(uint16_t*)&V64;
uint32_t s=0;
for(uint32_t n=0; n<NB/16; ++n) s+=F16(v16[n]);
printf(" 16 Bits: s=%u, t=%u ms\n",s,clock()-t);
}
void Count32(int(*F32)(uint32_t)) {
clock_t t=clock();
uint32_t *v32=(uint32_t*)&V64;
uint32_t s=0;
for(uint32_t n=0; n<NB/32; ++n) s+=F32(v32[n]);
printf(" 32 Bits: s=%u, t=%u ms\n",s,clock()-t);
}
void Count64(int(*F64)(uint64_t)) {
clock_t t=clock();
uint32_t s=0;
for(uint32_t n=0; n<NB/64; ++n) s+=F64(V64[n]);
printf(" 64 Bits: s=%u, t=%u ms\n",s,clock()-t);
}
//×× main ××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××
int main() {
uint64_t m=0XFFFF;
for(uint32_t i=0; i<NB/64; i+=2) { // "array" de 1 millard de bits
V64[i]=rand()&m|((rand()&m)<<16)|((rand()&m)<<32)|((rand()&m)<<48);
V64[i+1]=~V64[i];
}
for(uint32_t i=0; i<256; ++i) T8[i]=PopD8(i); // précomptage
for(uint32_t i=0; i<65536; ++i) T16[i]=PopD16(i); // précomptage

printf("Temps utilisé pour compter 1 miliard de bits\n\n");
printf("PopA: comptage\n");
Count8(PopA8); Count16(PopA16); Count32(PopA32); Count64(PopA64);
printf("PopB: autre comptage\n");
Count8(PopB8); Count16(PopB16); Count32(PopB32); Count64(PopB64);
printf("PopC: comptage pour population éparse\n");
Count8(PopC8); Count16(PopC16); Count32(PopC32); Count64(PopC64);
printf("PopD: addition par groupes\n");
Count8(PopD8); Count16(PopD16); Count32(PopD32); Count64(PopD64);
printf("PopE: addition par groupes bis\n");
Count8(PopE8); Count16(PopE16);
printf("PopF: addition par groupes optimisé\n");
Count8(PopF8); Count16(PopF16); Count32(PopF32); Count64(PopF64);
printf("PopG: multiplication\n");
Count16(PopG16); Count32(PopG32); Count64(PopG64);
printf("PopH: addition et multiplication\n");
Count16(PopH16); Count32(PopH32); Count64(PopH64);
printf("PopI: 256 bytes précomptés\n");
Count8(PopI8); Count16(PopI16); Count32(PopI32); Count64(PopI64);
printf("PopJ: 65536 shorts précomptés\n");
Count16(PopJ16); Count32(PopJ32); Count64(PopJ64);
getchar();
return 0;
}

Encore toutes mes excuses.
Messages postés
7569
Date d'inscription
jeudi 13 septembre 2007
Statut
Contributeur
Dernière intervention
21 octobre 2021
127 >
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

Bonjour,

J'ai eu le même problème pour enregistrer le zip. Voir ceci:

http://codes-sources.commentcamarche.net/forum/affich-10016759-deposer-une-source

Le problème n'a pas été résolu depuis!

Bonne journée
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
>
Messages postés
7569
Date d'inscription
jeudi 13 septembre 2007
Statut
Contributeur
Dernière intervention
21 octobre 2021

Bonjour
Merci pour votre information.
Que faire pour que le problème soit pris en considération ?

Bonne journée également
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30 >
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

J'ai remarqué que MS VS Express 2013 charge kernel32.dll.
Existe-t-il un équivalent 64 bits "kernel64.dll" ?

Je suppose que tu veux dire "à l'exécution".
'VS' est un "IDE", il ne "charge" donc rien du tout, quand l'exe est lancé il n'y a plus notion de VS. C'est le loader system qui charge kernel32 car tout prog en est dépendant, si exe est compilé x64 alors c'est bien entendu un kernel32 x64 qui est chargé. Un exe x64 ne chargera QUE des DLLs x64, idem pour les vieilleries 32 qui ne chargeront que des 32 bits.
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30 >
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019

Salut,
j'ai fait un test (mode GUI Windows), une dialog avec bouton A et B.

CODE C complet (à part ASM):

#include <windows.h>

#define ALIGN16   __declspec(align(16))
#define MEMDISPO  (MEM_COMMIT | MEM_RESERVE)
#define ONEPAGE   4096
#define mcVirtualAlloc(N) VirtualAlloc(0, N, MEMDISPO, PAGE_READWRITE);
#define mcVirtualFree(Addr) VirtualFree(Addr, 0, MEM_RELEASE);

#include "resource.h"
//#include "bnSSE.h"

#define NB      15625000    // 1000000000 / 64
#define NBSIZE  (NB * 8)    // 125000000 OCTETS !!!

typedef struct _BNDT {
  DWORD (*pfunc) (UINT64);
  HWND hstT;
  HWND hstR;
} BNDT, *PBNDT;

////    DEPUIS  bnCRT.asm     ////////////////////
char* bnultoa(DWORD dwnum, char* szdst);
void bnFillRndNbsize(void *pdst);
////      bnCRT.asm     ////////////////////

ALIGN16 DWORD DWRNDMUL[4] = {214013,214013,214013,214013};
ALIGN16 DWORD DWRNDADD[4] = {2531011,2531011,2531011,2531011};

BNDT bdt[2] = {0};
UINT64 *pUQW = 0;

DWORD PopA64(UINT64 k)
{
  int i;
  DWORD n = 0;
  for(i = 0; i < 64; i++) if(k & (1ll << i)) n++;
  return n;
}

DWORD PopA64bn(UINT64 k)
{
  return (DWORD) __popcnt64(k);
}

DWORD Count64(DWORD (*pfunc64) (UINT64))
{
  DWORD s, n;
  s = 0;
  for(n = 0; n < NB; ++n) s += pfunc64(pUQW[n]);
  return s;
}

void tstCount64(DWORD idx)
{
  char buf[24];
  UINT64 deb, fin;
  DWORD n;
  PBNDT pbn = &bdt[idx];
  deb = __rdtsc();
  n = Count64(pbn->pfunc);
  fin = __rdtsc();
  fin -= deb;
  *bnultoa((DWORD) fin, buf) = 0;
  SetWindowText(pbn->hstT, buf);
  *bnultoa(n, buf) = 0;
  SetWindowText(pbn->hstR, buf);
}

INT_PTR AppDlgProc(HWND hdlg, UINT mssg, WPARAM wParam, LPARAM lParam)
{
  switch(mssg) {
    case WM_INITDIALOG:
      SetClassLongPtr(hdlg, GCLP_HICON, (LONG_PTR) LoadIcon(0, IDI_APPLICATION));
      bdt[0].hstT = GetDlgItem(hdlg, IDST_TA);
      bdt[0].hstR = GetDlgItem(hdlg, IDST_A);
      bdt[1].hstT = GetDlgItem(hdlg, IDST_TB);
      bdt[1].hstR = GetDlgItem(hdlg, IDST_B);
      bdt[0].pfunc = PopA64;
      bdt[1].pfunc = PopA64bn;
      return 1;
    case WM_COMMAND:
      switch(LOWORD(wParam)) {
        case IDBT_A:
        case IDBT_B:
          tstCount64((DWORD) (LOWORD(wParam) - IDBT_A));
          return 0;
        case IDCANCEL: EndDialog(hdlg, 0);
      }
  }
  return 0;
}

void __fastcall myWinMain()
{
  pUQW = mcVirtualAlloc(NBSIZE);
  if(pUQW == 0) goto progEND;
  bnFillRndNbsize(pUQW);
  DialogBoxParam(GetModuleHandle(0), MAKEINTRESOURCE(IDD_APP), 0, AppDlgProc, 0);
  mcVirtualFree(pUQW);
progEND:
  ExitProcess(0);
}

-----------------
EXE x64 fait 2688 octets (2.62 Ko).

RESULTAT:
Retour n identique pour les 2 fonctions, IMPEC.
Les temps:
Bouton A (TON code) : 570240399 ticks.
BOUTON B (CPU code) : 77899931 ticks.

Conclusion:
Tant que faire se peut, toujours utiliser ce que fournit un CPU.
Tout autre code est quasi toujours une nuisance comparé au CPU.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.