Petit problème d'optimisation...

Pascal Bourguignon

25/05/2007 à 03:34

"Patrick 'Zener' Brunet" writes:

Bonsoir.

Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Un sous-problème peut être d'éliminer les 1 de la partie gauche...

Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?

Le plus rapide, ce serait d'utiliser les instructions assembleur de
ton processeur. Par exemple, sur x86, il y a BSR et BSF.

Sinon, c'est plus simple de les enlever que de les compter:

int remove_ones_on_right(int bitfield){
/*
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(bitfield>0);
return(bitfield-((bitfield^(bitfield+1))>>1));
}

Pour compter, on peut les extraire et utilise un algo bitcount
quelconque (il y en a des dizaines):

int bitcount(int x)
{
assert(__WORDSIZE=2);
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333) - (((x)>>3)&0x11111111))
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) & 0xff)
return(BITCOUNT(x));
#undef BITCOUNT
#undef BX_
}//bitcount;

int index_first_zero(int bitfield){
return(bitcount((bitfield^(bitfield+1))>>1));
}

--
__Pascal Bourguignon__ http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.

"Patrick 'Zener' Brunet" <use.link.in.signature@ddress.invalid> writes:

Bonsoir.

Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Un sous-problème peut être d'éliminer les 1 de la partie gauche...

Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?

Le plus rapide, ce serait d'utiliser les instructions assembleur de
ton processeur. Par exemple, sur x86, il y a BSR et BSF.

Sinon, c'est plus simple de les enlever que de les compter:

int remove_ones_on_right(int bitfield){
/*
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(bitfield>0);
return(bitfield-((bitfield^(bitfield+1))>>1));
}

Pour compter, on peut les extraire et utilise un algo bitcount
quelconque (il y en a des dizaines):

int bitcount(int x)
{
assert(__WORDSIZE=2);
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333) - (((x)>>3)&0x11111111))
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) & 0xff)
return(BITCOUNT(x));
#undef BITCOUNT
#undef BX_
}//bitcount;

int index_first_zero(int bitfield){
return(bitcount((bitfield^(bitfield+1))>>1));
}

--
__Pascal Bourguignon__ http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.

Vous avez filtré cet utilisateur ! Consultez son message

Antoine Leca

25/05/2007 à 10:45

En news:f34nr2$oi5$,
Patrick 'Zener' Brunet va escriure:

Je cherche à optimiser une (pas si) bête opération de recherche de
bit dans un nombre entier.

Si tu veux optimiser quelque chose qui s'exprime logiquement par une boucle,
une idée c'est de découper le problème en un arbre balancé.

Par exemple, si le nombre de bits plus fréquent est de 8 :

if( trame & 0x100 ) {
if( trame & 0xFF == 0xFF )
/* il y a au moins 9 bits à droite */
else
/* il y a au plus 7 bits à droite */
} else {
if( trame & 0xFF == 0xFF )
/* on a trouvé, il y a exactement 8 bits */
else
/* il y a au plus 7 bits à droite */
}

ce qui se réduit à

switch( trame & 0x1FF ) {
case 0x0FF:
/* on a trouvé, il y a exactement 8 bits */
return ...;
case 0x1FF:
/* il y a au moins 9 bits à droite */
...
break;
default:
/* il y a au plus 7 bits à droite */
...
break;
}

Ensuite il faut refaire d'autre tests imbriqués (par exemple 4 et 16) et on
récurre...
En choisissant bien les valeurs pivots, tu vas diminuer le nombre de tests
donc le nombre total d'instructions exécutées.

Avec peu de valeurs (8 bits donc 512 valeurs me semblent une borne
supérieure ; en fait je crois que la norme ne garantit que 256) tu peux tout
mettre dans un seul switch, en fait tu programmes un tableau de résultats :

switch( trame & 0x1FF ) {
case 0x0FF:
/* on a trouvé, il y a exactement 8 bits */
return ...;
case 0x1FF:
/* il y a au moins 9 bits à droite */
...
break;
case 0x07F:
case 0x17F:
/* on a trouvé, il y a exactement 7 bits */
return ...;
case 0x03F: case 0x13F:
case 0x0BF: case 0x1BF:
/* on a trouvé, il y a exactement 6 bits */
return ...;

. . .

case 0: case 2: ... /* et tous les nombres pairs */
/* on a trouvé, il y a exactement 0 bit */
return ...;

default:
botch();
break;
}

Antoine

Antoine Leca

25/05/2007 à 10:59

En news:,
Pascal Bourguignon va escriure:

Sinon, c'est plus simple de les enlever que de les compter:

int remove_ones_on_right(int bitfield){
/*
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(bitfield>0);
return(bitfield-((bitfield^(bitfield+1))>>1));
}

Une fois que tu es arrivé là, on peut compter facilement, non ?

int compter_les_uns_à_droite(int trame){
/*

0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(trame>0);

switch((trame^(trame+1))>>1){
case 0: return 0;
case 1: return 1;
case 3: return 2;
case 7: return 3;
case 017: return 4;
case 037: return 5;
case 077: return 6;
case 0177: return 7;
case 0377: return 8;
case 0777: return 9;
... etc. je fatigue !
default: assert(!"possible"); return -1;
}
}

Antoine

Laurent Deniau

25/05/2007 à 11:30

Patrick 'Zener' Brunet wrote:

Bonsoir.

Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Un sous-problème peut être d'éliminer les 1 de la partie gauche...

Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?

Dans OOC-2.0 j'utilise la fonction ci-dessous pour trouver le rang du
premier bit a 1 dans un size_t. Donc pour toi ca revient a utiliser:

ooc_size_LSBlog2(~val)

pour trouver le premier 0 de val en partant de la droite. Le principe
est le meme que celui de Antoine (arbre balance = dichotomie) avec en 32
bits seulement 5 tests (+1 pour 0). Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite des
labels ce qui risque de se traduire par autant de tests que de cases, et
donc sous optimal par rapport a la dichotomie explicite.

a+, ld.

int
ooc_size_LSBlog2(size_t s)
{
int p;

if (s == 0)
return -1;

p = 0;

#if ULONG_MAX >= 4294967296
#if ULONG_MAX >= 18446744073709551616
if ((s & 0xfffffffffffffffful) == 0) {
s >>= 64;
p += 64;
}
#endif

if ((s & 0xfffffffful) == 0) {
s >>= 32;
p += 32;
}
#endif

if ((s & 0xfffful) == 0) {
s >>= 16;
p += 16;
}

if ((s & 0xfful) == 0) {
s >>= 8;
p += 8;
}

if ((s & 0x0ful) == 0) {
s >>= 4;
p += 4;
}

if ((s & 0x03ul) == 0) {
s >>= 2;
p += 2;
}

if ((s & 0x01ul) == 0)
p += 1;

return p;
}

Patrick 'Zener' Brunet wrote:

Bonsoir.

Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Un sous-problème peut être d'éliminer les 1 de la partie gauche...

Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?

Dans OOC-2.0 j'utilise la fonction ci-dessous pour trouver le rang du
premier bit a 1 dans un size_t. Donc pour toi ca revient a utiliser:

ooc_size_LSBlog2(~val)

pour trouver le premier 0 de val en partant de la droite. Le principe
est le meme que celui de Antoine (arbre balance = dichotomie) avec en 32
bits seulement 5 tests (+1 pour 0). Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite des
labels ce qui risque de se traduire par autant de tests que de cases, et
donc sous optimal par rapport a la dichotomie explicite.

a+, ld.

int
ooc_size_LSBlog2(size_t s)
{
int p;

if (s == 0)
return -1;

p = 0;

#if ULONG_MAX >= 4294967296
#if ULONG_MAX >= 18446744073709551616
if ((s & 0xfffffffffffffffful) == 0) {
s >>= 64;
p += 64;
}
#endif

if ((s & 0xfffffffful) == 0) {
s >>= 32;
p += 32;
}
#endif

if ((s & 0xfffful) == 0) {
s >>= 16;
p += 16;
}

if ((s & 0xfful) == 0) {
s >>= 8;
p += 8;
}

if ((s & 0x0ful) == 0) {
s >>= 4;
p += 4;
}

if ((s & 0x03ul) == 0) {
s >>= 2;
p += 2;
}

if ((s & 0x01ul) == 0)
p += 1;

return p;
}

Antoine Leca

25/05/2007 à 17:59

En news:f36acg$tkk$, Laurent Deniau écrivit:

Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.

Mon idée (mais je n'ai pas testé) c'est que ce switch est plein, donc le
compilateur va le remplacer par un goto calculé, en principe plus rapide
qu'une cascade de 3 tests.

Après, c'est une optimisation temps contre espace, cache localité etc. et
pour savoir à quel niveau il faut mettre la barre je ne suis pas partant
pour rentrer dans le détail... (et en plus j'ai vaguement l'idée que les
résultats dépendent des données et de la babasse).

Antoine

Patrick 'Zener' Brunet

25/05/2007 à 21:51

Bonsoir.

"Patrick 'Zener' Brunet" a écrit dans
le message news: f34nr2$oi5$

Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans

un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce

que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche

(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Enchanté que cela vous ait intéressé, et merci pour toutes ces idées.

Je crois que c'est Pascal Bourguignon qui a donné le déclic, par rapport à
mon besoin spécifique bien sûr, avec le +1 (dire que j'avais essayé avec la
négation et le Xor !).

En fait, par rapport à mon besoin, je pense pouvoir me passer ainsi du
comptage, et atteindre directement le résultat voulu.

Voilà à quoi ça sert:
______________________

Je développe une classe C++ d'arbres combinant de multiples possibilités, et
que je vais utiliser dans un projet de compilateur (donc gros volume de
données + impératif de performances + divers trucs à moi...).

Cet arbre doit être navigable de toutes les manières possibles, et la
solution naïve implique 5 pointeurs de chaînage par noeud, donc déjà 20
octets sans la charge utile, ce qui est prohibitif.

D'où l'idée de représenter l'arbre comme binaire, afin d'utiliser une
représentation en tableau, sans aucun pointeur. Evidemment l'arbre est non
balancé, et donc le tableau sera creux, mais j'ai une solution en vue pour
çà.

Donc ça donne (passer en fonte à pas fixe):

|
A-
|
|
B--C--D--E-
| | | |
| |
| J--K--L-
| | | |
|
F--G--H--I-
| | | |

A = 1
Down(i) = 2.i
Right(i) = 2.i + 1

Et le pattern binaire du problème est la forme générale d'une valeur
Right(i).

Si on lui applique la formule suivante:
Up(i) = i / ((i ^ (i + 1)) + 1) ^ est le Xor et / la division entière

On atteint directement son parent, sans aucune itération.
La formule est valide aussi pour les premiers descendants.

Et pour atteindre le Nème descendant, on a:
Child(i,n) = (i << n) | ((1 << (n - 1)) - 1) | est le Or inclusif

Finalement, le comptage de bits pourrait permettre à un noeud descendant de
connaître son rang, mais je ne pense pas en avoir besoin.
Toutefois je salue le BITCOUNT(x) que je ne connaissais pas (je suis très
autodidacte en informatique).

Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)

Merci pour tout.

--
Cordialement.
--
/**************************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************/

Bonsoir.

"Patrick 'Zener' Brunet" <use.link.in.signature@ddress.invalid> a écrit dans
le message news: f34nr2$oi5$1@shakotay.alphanet.ch...

Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans

un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce

que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche

(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Enchanté que cela vous ait intéressé, et merci pour toutes ces idées.

Je crois que c'est Pascal Bourguignon qui a donné le déclic, par rapport à
mon besoin spécifique bien sûr, avec le +1 (dire que j'avais essayé avec la
négation et le Xor !).

En fait, par rapport à mon besoin, je pense pouvoir me passer ainsi du
comptage, et atteindre directement le résultat voulu.

Voilà à quoi ça sert:
______________________

Je développe une classe C++ d'arbres combinant de multiples possibilités, et
que je vais utiliser dans un projet de compilateur (donc gros volume de
données + impératif de performances + divers trucs à moi...).

Cet arbre doit être navigable de toutes les manières possibles, et la
solution naïve implique 5 pointeurs de chaînage par noeud, donc déjà 20
octets sans la charge utile, ce qui est prohibitif.

D'où l'idée de représenter l'arbre comme binaire, afin d'utiliser une
représentation en tableau, sans aucun pointeur. Evidemment l'arbre est non
balancé, et donc le tableau sera creux, mais j'ai une solution en vue pour
çà.

Donc ça donne (passer en fonte à pas fixe):

|
A-
|
|
B--C--D--E-
| | | |
| |
| J--K--L-
| | | |
|
F--G--H--I-
| | | |

A = 1
Down(i) = 2.i
Right(i) = 2.i + 1

Et le pattern binaire du problème est la forme générale d'une valeur
Right(i).

Si on lui applique la formule suivante:
Up(i) = i / ((i ^ (i + 1)) + 1) ^ est le Xor et / la division entière

On atteint directement son parent, sans aucune itération.
La formule est valide aussi pour les premiers descendants.

Et pour atteindre le Nème descendant, on a:
Child(i,n) = (i << n) | ((1 << (n - 1)) - 1) | est le Or inclusif

Finalement, le comptage de bits pourrait permettre à un noeud descendant de
connaître son rang, mais je ne pense pas en avoir besoin.
Toutefois je salue le BITCOUNT(x) que je ne connaissais pas (je suis très
autodidacte en informatique).

Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)

Merci pour tout.

--
Cordialement.
--
/**************************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************/

Vous avez filtré cet utilisateur ! Consultez son message

Bonsoir.

"Patrick 'Zener' Brunet" a écrit dans
le message news: f34nr2$oi5$

Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans

un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce

que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche

(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Enchanté que cela vous ait intéressé, et merci pour toutes ces idées.

Je crois que c'est Pascal Bourguignon qui a donné le déclic, par rapport à
mon besoin spécifique bien sûr, avec le +1 (dire que j'avais essayé avec la
négation et le Xor !).

En fait, par rapport à mon besoin, je pense pouvoir me passer ainsi du
comptage, et atteindre directement le résultat voulu.

Voilà à quoi ça sert:
______________________

Je développe une classe C++ d'arbres combinant de multiples possibilités, et
que je vais utiliser dans un projet de compilateur (donc gros volume de
données + impératif de performances + divers trucs à moi...).

Cet arbre doit être navigable de toutes les manières possibles, et la
solution naïve implique 5 pointeurs de chaînage par noeud, donc déjà 20
octets sans la charge utile, ce qui est prohibitif.

D'où l'idée de représenter l'arbre comme binaire, afin d'utiliser une
représentation en tableau, sans aucun pointeur. Evidemment l'arbre est non
balancé, et donc le tableau sera creux, mais j'ai une solution en vue pour
çà.

Donc ça donne (passer en fonte à pas fixe):

|
A-
|
|
B--C--D--E-
| | | |
| |
| J--K--L-
| | | |
|
F--G--H--I-
| | | |

A = 1
Down(i) = 2.i
Right(i) = 2.i + 1

Et le pattern binaire du problème est la forme générale d'une valeur
Right(i).

Si on lui applique la formule suivante:
Up(i) = i / ((i ^ (i + 1)) + 1) ^ est le Xor et / la division entière

On atteint directement son parent, sans aucune itération.
La formule est valide aussi pour les premiers descendants.

Et pour atteindre le Nème descendant, on a:
Child(i,n) = (i << n) | ((1 << (n - 1)) - 1) | est le Or inclusif

Finalement, le comptage de bits pourrait permettre à un noeud descendant de
connaître son rang, mais je ne pense pas en avoir besoin.
Toutefois je salue le BITCOUNT(x) que je ne connaissais pas (je suis très
autodidacte en informatique).

Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)

Merci pour tout.

--
Cordialement.
--
/**************************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************/

Charlie Gordon

29/05/2007 à 02:12

"Antoine Leca" a écrit dans le message de news:
f3714j$afd$

En news:f36acg$tkk$, Laurent Deniau écrivit:
Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.

Mon idée (mais je n'ai pas testé) c'est que ce switch est plein, donc le
compilateur va le remplacer par un goto calculé, en principe plus rapide
qu'une cascade de 3 tests.

Ton switch est tout sauf plein : les case values ne sont pas contiguës, loin
s'en faut, il a de fortes chances d'être compilé comme une suite de tests
(quand meme dichotomiques avec un bon compilo).

Après, c'est une optimisation temps contre espace, cache localité etc. et
pour savoir à quel niveau il faut mettre la barre je ne suis pas partant
pour rentrer dans le détail... (et en plus j'ai vaguement l'idée que les
résultats dépendent des données et de la babasse).

Le code de Pascal Bourguignon est très instructif en la matière : il fait
une expression arithmétique très simple pour ne garder que les bits de poids
faible et utilise une implémentation certes cryptique mais hyper efficace de
bitcount qui ne fait aucun test. On a le résultat en temps constant avec
très peu de code, aucune donnée statique annexe, et un nombre total
d'instructions tout à fait raisonnable, que le compilo pourra sans doute
efficacement entrelacer pour tirer parti des capacités du processeur, si
cela est encore utile.

bitcount et atoi sont mes tests favoris lors d'un entretien d'embauche pour
un programmeur, j'ai un musée des horreurs où la collection se renouvelle
régulièrement, il est rare que j'aie l'opportunité de faire analyser le
bitcount par addition parallèle qu'utilise PB (ce serait sadique), et
jusqu'à présent personne ne l'a proposé d'emblée (ce serait génial).

Pour les curieux, en voici deux variantes lisibles :

int bitcount1(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
return x;
}
int bitcount2(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0x70707070) >> 4) + (x & 0x07070707);
x = ((x & 0x0F000F00) >> 8) + (x & 0x000F000F);
x = (x >> 16) + (x & 0x0000001F);
return x;
}

Chqrlie.

"Antoine Leca" <root@localhost.invalid> a écrit dans le message de news:
f3714j$afd$1@shakotay.alphanet.ch...

En news:f36acg$tkk$1@cernne03.cern.ch, Laurent Deniau écrivit:

Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.

Mon idée (mais je n'ai pas testé) c'est que ce switch est plein, donc le
compilateur va le remplacer par un goto calculé, en principe plus rapide
qu'une cascade de 3 tests.

Ton switch est tout sauf plein : les case values ne sont pas contiguës, loin
s'en faut, il a de fortes chances d'être compilé comme une suite de tests
(quand meme dichotomiques avec un bon compilo).

Après, c'est une optimisation temps contre espace, cache localité etc. et
pour savoir à quel niveau il faut mettre la barre je ne suis pas partant
pour rentrer dans le détail... (et en plus j'ai vaguement l'idée que les
résultats dépendent des données et de la babasse).

Le code de Pascal Bourguignon est très instructif en la matière : il fait
une expression arithmétique très simple pour ne garder que les bits de poids
faible et utilise une implémentation certes cryptique mais hyper efficace de
bitcount qui ne fait aucun test. On a le résultat en temps constant avec
très peu de code, aucune donnée statique annexe, et un nombre total
d'instructions tout à fait raisonnable, que le compilo pourra sans doute
efficacement entrelacer pour tirer parti des capacités du processeur, si
cela est encore utile.

bitcount et atoi sont mes tests favoris lors d'un entretien d'embauche pour
un programmeur, j'ai un musée des horreurs où la collection se renouvelle
régulièrement, il est rare que j'aie l'opportunité de faire analyser le
bitcount par addition parallèle qu'utilise PB (ce serait sadique), et
jusqu'à présent personne ne l'a proposé d'emblée (ce serait génial).

Pour les curieux, en voici deux variantes lisibles :

int bitcount1(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
return x;
}
int bitcount2(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0x70707070) >> 4) + (x & 0x07070707);
x = ((x & 0x0F000F00) >> 8) + (x & 0x000F000F);
x = (x >> 16) + (x & 0x0000001F);
return x;
}

Chqrlie.

Vous avez filtré cet utilisateur ! Consultez son message

"Antoine Leca" a écrit dans le message de news:
f3714j$afd$

En news:f36acg$tkk$, Laurent Deniau écrivit:
Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.

Mon idée (mais je n'ai pas testé) c'est que ce switch est plein, donc le
compilateur va le remplacer par un goto calculé, en principe plus rapide
qu'une cascade de 3 tests.

Ton switch est tout sauf plein : les case values ne sont pas contiguës, loin
s'en faut, il a de fortes chances d'être compilé comme une suite de tests
(quand meme dichotomiques avec un bon compilo).

Après, c'est une optimisation temps contre espace, cache localité etc. et
pour savoir à quel niveau il faut mettre la barre je ne suis pas partant
pour rentrer dans le détail... (et en plus j'ai vaguement l'idée que les
résultats dépendent des données et de la babasse).

Le code de Pascal Bourguignon est très instructif en la matière : il fait
une expression arithmétique très simple pour ne garder que les bits de poids
faible et utilise une implémentation certes cryptique mais hyper efficace de
bitcount qui ne fait aucun test. On a le résultat en temps constant avec
très peu de code, aucune donnée statique annexe, et un nombre total
d'instructions tout à fait raisonnable, que le compilo pourra sans doute
efficacement entrelacer pour tirer parti des capacités du processeur, si
cela est encore utile.

bitcount et atoi sont mes tests favoris lors d'un entretien d'embauche pour
un programmeur, j'ai un musée des horreurs où la collection se renouvelle
régulièrement, il est rare que j'aie l'opportunité de faire analyser le
bitcount par addition parallèle qu'utilise PB (ce serait sadique), et
jusqu'à présent personne ne l'a proposé d'emblée (ce serait génial).

Pour les curieux, en voici deux variantes lisibles :

int bitcount1(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
return x;
}
int bitcount2(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0x70707070) >> 4) + (x & 0x07070707);
x = ((x & 0x0F000F00) >> 8) + (x & 0x000F000F);
x = (x >> 16) + (x & 0x0000001F);
return x;
}

Chqrlie.

Bruno Causse

29/05/2007 à 09:39

"Charlie Gordon" a écrit dans le message de news:
465b6fdc$0$3630$

Pour les curieux, en voici deux variantes lisibles :

int bitcount1(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
return x;
}
int bitcount2(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0x70707070) >> 4) + (x & 0x07070707);
x = ((x & 0x0F000F00) >> 8) + (x & 0x000F000F);
x = (x >> 16) + (x & 0x0000001F);
return x;
}

et une 3eme (en 64 bits, la plus rapide que je connaisse)

unsigned long long
result = legals
- ((legals >> 1) & 0x7777777777777777ULL)
- ((legals >> 2) & 0x3333333333333333ULL)
- ((legals >> 3) & 0x1111111111111111ULL);
result = ((result + (result >> 4)) & 0x0F0F0F0F0F0F0F0FULL) % 0xFF;

Laurent Deniau

29/05/2007 à 11:08

Patrick 'Zener' Brunet wrote:

Bonsoir.

"Patrick 'Zener' Brunet" a écrit dans
le message news: f34nr2$oi5$
Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans

un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce

que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche

(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Enchanté que cela vous ait intéressé, et merci pour toutes ces idées.

Je crois que c'est Pascal Bourguignon qui a donné le déclic, par rapport à
mon besoin spécifique bien sûr, avec le +1 (dire que j'avais essayé avec la
négation et le Xor !).

En fait, par rapport à mon besoin, je pense pouvoir me passer ainsi du
comptage, et atteindre directement le résultat voulu.

Voilà à quoi ça sert:
______________________

Je développe une classe C++ d'arbres combinant de multiples possibilités, et
que je vais utiliser dans un projet de compilateur (donc gros volume de
données + impératif de performances + divers trucs à moi...).

Cet arbre doit être navigable de toutes les manières possibles, et la
solution naïve implique 5 pointeurs de chaînage par noeud, donc déjà 20
octets sans la charge utile, ce qui est prohibitif.

D'où l'idée de représenter l'arbre comme binaire, afin d'utiliser une
représentation en tableau, sans aucun pointeur. Evidemment l'arbre est non
balancé, et donc le tableau sera creux, mais j'ai une solution en vue pour
çà.

Donc ça donne (passer en fonte à pas fixe):

|
A-
|
|
B--C--D--E-
| | | |
| |
| J--K--L-
| | | |
|
F--G--H--I-
| | | |

A = 1
Down(i) = 2.i
Right(i) = 2.i + 1

Et le pattern binaire du problème est la forme générale d'une valeur
Right(i).

Si on lui applique la formule suivante:
Up(i) = i / ((i ^ (i + 1)) + 1) ^ est le Xor et / la division entière

On atteint directement son parent, sans aucune itération.
La formule est valide aussi pour les premiers descendants.

Et pour atteindre le Nème descendant, on a:
Child(i,n) = (i << n) | ((1 << (n - 1)) - 1) | est le Or inclusif

Finalement, le comptage de bits pourrait permettre à un noeud descendant de
connaître son rang, mais je ne pense pas en avoir besoin.
Toutefois je salue le BITCOUNT(x) que je ne connaissais pas (je suis très
autodidacte en informatique).

Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)

Et peut-etre regarder les "Judy Array" qui font exactement ca, non?

http://judy.sourceforge.net/

a+, ld.

Patrick 'Zener' Brunet wrote:

Bonsoir.

"Patrick 'Zener' Brunet" <use.link.in.signature@ddress.invalid> a écrit dans
le message news: f34nr2$oi5$1@shakotay.alphanet.ch...

Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans

un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce

que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche

(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Enchanté que cela vous ait intéressé, et merci pour toutes ces idées.

Je crois que c'est Pascal Bourguignon qui a donné le déclic, par rapport à
mon besoin spécifique bien sûr, avec le +1 (dire que j'avais essayé avec la
négation et le Xor !).

En fait, par rapport à mon besoin, je pense pouvoir me passer ainsi du
comptage, et atteindre directement le résultat voulu.

Voilà à quoi ça sert:
______________________

Je développe une classe C++ d'arbres combinant de multiples possibilités, et
que je vais utiliser dans un projet de compilateur (donc gros volume de
données + impératif de performances + divers trucs à moi...).

Cet arbre doit être navigable de toutes les manières possibles, et la
solution naïve implique 5 pointeurs de chaînage par noeud, donc déjà 20
octets sans la charge utile, ce qui est prohibitif.

D'où l'idée de représenter l'arbre comme binaire, afin d'utiliser une
représentation en tableau, sans aucun pointeur. Evidemment l'arbre est non
balancé, et donc le tableau sera creux, mais j'ai une solution en vue pour
çà.

Donc ça donne (passer en fonte à pas fixe):

|
A-
|
|
B--C--D--E-
| | | |
| |
| J--K--L-
| | | |
|
F--G--H--I-
| | | |

A = 1
Down(i) = 2.i
Right(i) = 2.i + 1

Et le pattern binaire du problème est la forme générale d'une valeur
Right(i).

Si on lui applique la formule suivante:
Up(i) = i / ((i ^ (i + 1)) + 1) ^ est le Xor et / la division entière

On atteint directement son parent, sans aucune itération.
La formule est valide aussi pour les premiers descendants.

Et pour atteindre le Nème descendant, on a:
Child(i,n) = (i << n) | ((1 << (n - 1)) - 1) | est le Or inclusif

Finalement, le comptage de bits pourrait permettre à un noeud descendant de
connaître son rang, mais je ne pense pas en avoir besoin.
Toutefois je salue le BITCOUNT(x) que je ne connaissais pas (je suis très
autodidacte en informatique).

Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)

Et peut-etre regarder les "Judy Array" qui font exactement ca, non?

http://judy.sourceforge.net/

a+, ld.

Vous avez filtré cet utilisateur ! Consultez son message

Patrick 'Zener' Brunet wrote:

Bonsoir.

"Patrick 'Zener' Brunet" a écrit dans
le message news: f34nr2$oi5$
Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans

un nombre entier.

C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce

que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).

La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche

(MSbit):

- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.

Exemple:

...001101001111111

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Enchanté que cela vous ait intéressé, et merci pour toutes ces idées.

Je crois que c'est Pascal Bourguignon qui a donné le déclic, par rapport à
mon besoin spécifique bien sûr, avec le +1 (dire que j'avais essayé avec la
négation et le Xor !).

En fait, par rapport à mon besoin, je pense pouvoir me passer ainsi du
comptage, et atteindre directement le résultat voulu.

Voilà à quoi ça sert:
______________________

Je développe une classe C++ d'arbres combinant de multiples possibilités, et
que je vais utiliser dans un projet de compilateur (donc gros volume de
données + impératif de performances + divers trucs à moi...).

Cet arbre doit être navigable de toutes les manières possibles, et la
solution naïve implique 5 pointeurs de chaînage par noeud, donc déjà 20
octets sans la charge utile, ce qui est prohibitif.

D'où l'idée de représenter l'arbre comme binaire, afin d'utiliser une
représentation en tableau, sans aucun pointeur. Evidemment l'arbre est non
balancé, et donc le tableau sera creux, mais j'ai une solution en vue pour
çà.

Donc ça donne (passer en fonte à pas fixe):

|
A-
|
|
B--C--D--E-
| | | |
| |
| J--K--L-
| | | |
|
F--G--H--I-
| | | |

A = 1
Down(i) = 2.i
Right(i) = 2.i + 1

Et le pattern binaire du problème est la forme générale d'une valeur
Right(i).

Si on lui applique la formule suivante:
Up(i) = i / ((i ^ (i + 1)) + 1) ^ est le Xor et / la division entière

On atteint directement son parent, sans aucune itération.
La formule est valide aussi pour les premiers descendants.

Et pour atteindre le Nème descendant, on a:
Child(i,n) = (i << n) | ((1 << (n - 1)) - 1) | est le Or inclusif

Finalement, le comptage de bits pourrait permettre à un noeud descendant de
connaître son rang, mais je ne pense pas en avoir besoin.
Toutefois je salue le BITCOUNT(x) que je ne connaissais pas (je suis très
autodidacte en informatique).

Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)

Et peut-etre regarder les "Judy Array" qui font exactement ca, non?

http://judy.sourceforge.net/

a+, ld.

Patrick 'Zener' Brunet

29/05/2007 à 21:57

Bonsoir.

"Laurent Deniau" a écrit dans le message news:
f3gqiv$f3j$

Patrick 'Zener' Brunet wrote:
"Patrick 'Zener' Brunet" a écrit
dans

le message news: f34nr2$oi5$
[...]
Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester

virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)

Et peut-etre regarder les "Judy Array" qui font exactement ca, non?

http://judy.sourceforge.net/

Bien entendu, merci+++

Même s'il s'avère que l'implémentation ne colle pas au besoin spécifique,
les principes de conception m'intéresseront sûrement.

--
Cordialement.
--
/**************************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************/

Petit problème d'optimisation...

10 réponses

Veuillez sélectionner un problème