[débutant objet] tableau de pointeur de fonction

Fabien LE LEZ

28/09/2005 à 06:37

On 27 Sep 2005 06:45:38 -0700, "kanze" :

Sur une machine moderne ?

Qu'entends-tu par "machine moderne" ? Une machine incapable de
travailler en 8 ou 16 bits, ou une machine trop rapide pour que ça ait
de l'importance ?

Soit une image en couleurs, que tu veux passer en valeurs de gris.

Pour chaque pixel, tu fais la moyenne de trois entiers non signés de 8
bits (les composantes rouge, bleue et verte du pixel). Faire ça en C++
(du style (pixel[0]+pixel[1]+pixel[2])/3 ) n'est pas possible -- trop
long, du moins quand tu veux afficher 24 images de taille respectable
toutes les secondes.

kanze

28/09/2005 à 09:27

Fabien LE LEZ wrote:

On 27 Sep 2005 06:45:38 -0700, "kanze" :

Sur une machine moderne ?

Qu'entends-tu par "machine moderne" ? Une machine incapable de
travailler en 8 ou 16 bits, ou une machine trop rapide pour
que ça ait de l'importance ?

À peu près n'importe quoi. Je n'ai pas voulu faire l'analyse
pour vérifier que ça ne fait aucune différence dans le cas des
compléments à un ou des bytes à neuf bits. Si la machine est à
adressage mot avec des mots de 36 bits, j'imagine que ça
pourrait faire une différence.

En somme : une « machine moderne » ici, c'est une machine aux
bytes de 8 bits qui peut accéder directement à des bytes et des
démi-mots (de 16 bits) sans penalité de temps, et qui travaille
en complément à deux.

Soit une image en couleurs, que tu veux passer en valeurs de gris.

Pour chaque pixel, tu fais la moyenne de trois entiers non signés de 8
bits (les composantes rouge, bleue et verte du pixel). Faire ça en C++
(du style (pixel[0]+pixel[1]+pixel[2])/3 ) n'est pas possible -- trop
long, du moins quand tu veux afficher 24 images de taille respectable
toutes les secondes.

Je ne comprends pas le « trop long ». Qu'est-ce que le
compilateur va faire de plus que tu ne dois pas faire en
assembleur ? Pour éviter les débordements, il faut bien que tu
convertis tes octets du composant couleur en 16 bits -- les
convertir directement en 32 ne coûte pas plus cher, j'imagine
(et si oui, un bon compilateur pourrait faire le travail en 16
bits aussi -- la norme n'exige pas la stupidité complète de la
part du compilateur.

La seule chose où je vois qu'il peut y avoir une différence :
après la conversion en int, le type est signé. Et je peux
imaginer que certains compilateurs hésitent à convertir la
division en décalages et additions (en supposant que l'addition
soit une opération chère) si les valeurs sont signées.

--
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

Fabien LE LEZ wrote:

On 27 Sep 2005 06:45:38 -0700, "kanze" <kanze@gabi-soft.fr>:

Sur une machine moderne ?

Qu'entends-tu par "machine moderne" ? Une machine incapable de
travailler en 8 ou 16 bits, ou une machine trop rapide pour
que ça ait de l'importance ?

À peu près n'importe quoi. Je n'ai pas voulu faire l'analyse
pour vérifier que ça ne fait aucune différence dans le cas des
compléments à un ou des bytes à neuf bits. Si la machine est à
adressage mot avec des mots de 36 bits, j'imagine que ça
pourrait faire une différence.

En somme : une « machine moderne » ici, c'est une machine aux
bytes de 8 bits qui peut accéder directement à des bytes et des
démi-mots (de 16 bits) sans penalité de temps, et qui travaille
en complément à deux.

Soit une image en couleurs, que tu veux passer en valeurs de gris.

Pour chaque pixel, tu fais la moyenne de trois entiers non signés de 8
bits (les composantes rouge, bleue et verte du pixel). Faire ça en C++
(du style (pixel[0]+pixel[1]+pixel[2])/3 ) n'est pas possible -- trop
long, du moins quand tu veux afficher 24 images de taille respectable
toutes les secondes.

Je ne comprends pas le « trop long ». Qu'est-ce que le
compilateur va faire de plus que tu ne dois pas faire en
assembleur ? Pour éviter les débordements, il faut bien que tu
convertis tes octets du composant couleur en 16 bits -- les
convertir directement en 32 ne coûte pas plus cher, j'imagine
(et si oui, un bon compilateur pourrait faire le travail en 16
bits aussi -- la norme n'exige pas la stupidité complète de la
part du compilateur.

La seule chose où je vois qu'il peut y avoir une différence :
après la conversion en int, le type est signé. Et je peux
imaginer que certains compilateurs hésitent à convertir la
division en décalages et additions (en supposant que l'addition
soit une opération chère) si les valeurs sont signées.

--
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

Vous avez filtré cet utilisateur ! Consultez son message

Fabien LE LEZ wrote:

On 27 Sep 2005 06:45:38 -0700, "kanze" :

Sur une machine moderne ?

Qu'entends-tu par "machine moderne" ? Une machine incapable de
travailler en 8 ou 16 bits, ou une machine trop rapide pour
que ça ait de l'importance ?

À peu près n'importe quoi. Je n'ai pas voulu faire l'analyse
pour vérifier que ça ne fait aucune différence dans le cas des
compléments à un ou des bytes à neuf bits. Si la machine est à
adressage mot avec des mots de 36 bits, j'imagine que ça
pourrait faire une différence.

En somme : une « machine moderne » ici, c'est une machine aux
bytes de 8 bits qui peut accéder directement à des bytes et des
démi-mots (de 16 bits) sans penalité de temps, et qui travaille
en complément à deux.

Soit une image en couleurs, que tu veux passer en valeurs de gris.

Pour chaque pixel, tu fais la moyenne de trois entiers non signés de 8
bits (les composantes rouge, bleue et verte du pixel). Faire ça en C++
(du style (pixel[0]+pixel[1]+pixel[2])/3 ) n'est pas possible -- trop
long, du moins quand tu veux afficher 24 images de taille respectable
toutes les secondes.

Je ne comprends pas le « trop long ». Qu'est-ce que le
compilateur va faire de plus que tu ne dois pas faire en
assembleur ? Pour éviter les débordements, il faut bien que tu
convertis tes octets du composant couleur en 16 bits -- les
convertir directement en 32 ne coûte pas plus cher, j'imagine
(et si oui, un bon compilateur pourrait faire le travail en 16
bits aussi -- la norme n'exige pas la stupidité complète de la
part du compilateur.

La seule chose où je vois qu'il peut y avoir une différence :
après la conversion en int, le type est signé. Et je peux
imaginer que certains compilateurs hésitent à convertir la
division en décalages et additions (en supposant que l'addition
soit une opération chère) si les valeurs sont signées.

--
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

Fabien LE LEZ

02/10/2005 à 22:02

On 28 Sep 2005 00:27:24 -0700, "kanze" :

Je ne comprends pas le « trop long ». Qu'est-ce que le
compilateur va faire de plus que tu ne dois pas faire en
assembleur ?

J'avais choisi l'exemple un peu au hasard, et j'avoue qu'il était
mauvais.
Mais je viens de tomber sur un exemple typique et réel.

J'ai deux images en RVB (1 octet rouge, 1 octet vert, 1 octet bleu) --
en fait deux frames successives dans une vidéo.

Je dois appliquer l'algorithme suivant : aucune composante ne peut
varier plus de deux fois plus vite que les autres.
En d'autres termes, et en simplifiant :

si (nouvelle_valeur[rouge]-ancienne_valeur[rouge]

2 * nouvelle_valeur[vert]-ancienne_valeur[vert])
alors nouvelle_valeur[rouge]= (ce qu'il faut)

Le "alors" ne m'inquiète pas trop ici, car le cas est peu fréquent ;
je ne m'intéresse qu'à la condition.
Je peux la réécrire ainsi :

si ( (nouvelle_valeur[rouge]-ancienne_valeur[rouge]) / 2

nouvelle_valeur[vert]-ancienne_valeur[vert])

Tous les nombres restent sur 8 bits ; j'aimerais donc beaucoup faire
de l'arithmétique en 8 bits, et ne pas avoir à faire des conversions
entre les entiers sur 1 octet et les entiers sur 4 octets.

Le programme, tel que je l'ai écrit (en C++, sans assembleur et sans
chercher à optimiser) prend un temps fou (au bas mot, c'est 10 fois
plus lent que ce à quoi on pourrait s'attendre pour un tel filtre) ;
il va donc falloir que je trouve une autre solution.

kanze

04/10/2005 à 09:51

Fabien LE LEZ wrote:

On 28 Sep 2005 00:27:24 -0700, "kanze" :

Je ne comprends pas le « trop long ». Qu'est-ce que le
compilateur va faire de plus que tu ne dois pas faire en
assembleur ?

J'avais choisi l'exemple un peu au hasard, et j'avoue qu'il
était mauvais. Mais je viens de tomber sur un exemple typique
et réel.

C'est mieux. Moi aussi, quand je cherche à trouver des exemples
de tête, je finis toujours à en trouver un qui n'est pas ce que
je veux.

J'ai deux images en RVB (1 octet rouge, 1 octet vert, 1 octet
bleu) -- en fait deux frames successives dans une vidéo.

Je dois appliquer l'algorithme suivant : aucune composante ne
peut varier plus de deux fois plus vite que les autres. En
d'autres termes, et en simplifiant :

si (nouvelle_valeur[rouge]-ancienne_valeur[rouge]
2 * nouvelle_valeur[vert]-ancienne_valeur[vert])
alors nouvelle_valeur[rouge]= (ce qu'il faut)

Le "alors" ne m'inquiète pas trop ici, car le cas est peu
fréquent ; je ne m'intéresse qu'à la condition. Je peux la
réécrire ainsi :

si ( (nouvelle_valeur[rouge]-ancienne_valeur[rouge]) / 2
nouvelle_valeur[vert]-ancienne_valeur[vert])

Je ne suis pas trop sûr de comprendre. Normalement, j'aurais
imaginé que nouvelle_valeur et ancienne_valeur sont des unsigned
char. (En fait, j'imagine plutôt que ce sont les pointeurs à des
unsigned char. Et que rouge et vert sont des constantes, pendant
qu'on y est.) Seulement, si ce sont des unsigned, et que la
nouvelle_valeur est plus petit que l'ancienne_valeur, la
différence va être énorme.

De toute façon, on a un problème ici : si les types sont
unsigned, il faut bien ou faire la soustraction dans le bon
sens, ou convertir le résultat en signed et en prendre la valeur
absolue. Et s'ils sont signed, il y a le problème que la
différence entre deux signed ne tient pas forcément dans le même
type. Et évidemment, qu'il faut en prendre la valeur absolue.

Dans tous les cas, si je suppose qu'il s'agit de la
représentation « classique » avec des valeurs de 0...255, il me
faut au moins 9 bits dans les calculs intermédiaire pour que le
résultat soit juste.

Tous les nombres restent sur 8 bits ; j'aimerais donc beaucoup
faire de l'arithmétique en 8 bits, et ne pas avoir à faire des
conversions entre les entiers sur 1 octet et les entiers sur 4
octets.

Tes valeurs 8 bits sont bien en mémoire, n'est-ce pas ? Il faut
les charger dans des régistres pour faire les calculs. Et les
régistres ont quelle taille ?

Si le C a adopté la politique de la promotion integrale, ce
n'est pas pour des raisons théoriques ; c'est parce que c'est
comme ça que fonctionne le hardware. La seule exception que je
connais (ou plutôt connaissais), c'est les premiers 8086, où la
lecture d'un octet ne changeait qu'un démi-régister -- un coup
d'oeil rapide au manuel actuel me montre qu'il y a maintenant
des instructions MOVSX et MOVZX qui feraient parfaitement
l'affaire.

Maintenant, s'il s'agit de stocker le résultat immédiatement
dans un octet en mémoire, quelque chose du genre : x += y (ou x
et y ont le type unsigned char), je vois mal un compilateur qui
génère autre chose que :

MOV al,[byte ptr y]
ADD [byte ptr x],al

Après tous, le résultat serait exactement pareil que si
l'arithmétique se faisait sur 32 bits.

Le programme, tel que je l'ai écrit (en C++, sans assembleur
et sans chercher à optimiser) prend un temps fou (au bas mot,
c'est 10 fois plus lent que ce à quoi on pourrait s'attendre
pour un tel filtre) ; il va donc falloir que je trouve une
autre solution.

Si le profiler dit qu'il le faut, il le faut. Mais si le code
C++ est bien écrit, et l'optimisateur fait bien son boulot, ne
t'attends pas à pouvoir faire beaucoup mieux en assembleur. Pour
gagner une facteur dix, il va falloir faire des optimisations au
niveau de l'algorithme.

--
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

Fabien LE LEZ wrote:

On 28 Sep 2005 00:27:24 -0700, "kanze" <kanze@gabi-soft.fr>:

Je ne comprends pas le « trop long ». Qu'est-ce que le
compilateur va faire de plus que tu ne dois pas faire en
assembleur ?

J'avais choisi l'exemple un peu au hasard, et j'avoue qu'il
était mauvais. Mais je viens de tomber sur un exemple typique
et réel.

C'est mieux. Moi aussi, quand je cherche à trouver des exemples
de tête, je finis toujours à en trouver un qui n'est pas ce que
je veux.

J'ai deux images en RVB (1 octet rouge, 1 octet vert, 1 octet
bleu) -- en fait deux frames successives dans une vidéo.

Je dois appliquer l'algorithme suivant : aucune composante ne
peut varier plus de deux fois plus vite que les autres. En
d'autres termes, et en simplifiant :

si (nouvelle_valeur[rouge]-ancienne_valeur[rouge]

2 * nouvelle_valeur[vert]-ancienne_valeur[vert])
alors nouvelle_valeur[rouge]= (ce qu'il faut)

Le "alors" ne m'inquiète pas trop ici, car le cas est peu
fréquent ; je ne m'intéresse qu'à la condition. Je peux la
réécrire ainsi :

si ( (nouvelle_valeur[rouge]-ancienne_valeur[rouge]) / 2

nouvelle_valeur[vert]-ancienne_valeur[vert])

Je ne suis pas trop sûr de comprendre. Normalement, j'aurais
imaginé que nouvelle_valeur et ancienne_valeur sont des unsigned
char. (En fait, j'imagine plutôt que ce sont les pointeurs à des
unsigned char. Et que rouge et vert sont des constantes, pendant
qu'on y est.) Seulement, si ce sont des unsigned, et que la
nouvelle_valeur est plus petit que l'ancienne_valeur, la
différence va être énorme.

De toute façon, on a un problème ici : si les types sont
unsigned, il faut bien ou faire la soustraction dans le bon
sens, ou convertir le résultat en signed et en prendre la valeur
absolue. Et s'ils sont signed, il y a le problème que la
différence entre deux signed ne tient pas forcément dans le même
type. Et évidemment, qu'il faut en prendre la valeur absolue.

Dans tous les cas, si je suppose qu'il s'agit de la
représentation « classique » avec des valeurs de 0...255, il me
faut au moins 9 bits dans les calculs intermédiaire pour que le
résultat soit juste.

Tous les nombres restent sur 8 bits ; j'aimerais donc beaucoup
faire de l'arithmétique en 8 bits, et ne pas avoir à faire des
conversions entre les entiers sur 1 octet et les entiers sur 4
octets.

Tes valeurs 8 bits sont bien en mémoire, n'est-ce pas ? Il faut
les charger dans des régistres pour faire les calculs. Et les
régistres ont quelle taille ?

Si le C a adopté la politique de la promotion integrale, ce
n'est pas pour des raisons théoriques ; c'est parce que c'est
comme ça que fonctionne le hardware. La seule exception que je
connais (ou plutôt connaissais), c'est les premiers 8086, où la
lecture d'un octet ne changeait qu'un démi-régister -- un coup
d'oeil rapide au manuel actuel me montre qu'il y a maintenant
des instructions MOVSX et MOVZX qui feraient parfaitement
l'affaire.

Maintenant, s'il s'agit de stocker le résultat immédiatement
dans un octet en mémoire, quelque chose du genre : x += y (ou x
et y ont le type unsigned char), je vois mal un compilateur qui
génère autre chose que :

MOV al,[byte ptr y]
ADD [byte ptr x],al

Après tous, le résultat serait exactement pareil que si
l'arithmétique se faisait sur 32 bits.

Le programme, tel que je l'ai écrit (en C++, sans assembleur
et sans chercher à optimiser) prend un temps fou (au bas mot,
c'est 10 fois plus lent que ce à quoi on pourrait s'attendre
pour un tel filtre) ; il va donc falloir que je trouve une
autre solution.

Si le profiler dit qu'il le faut, il le faut. Mais si le code
C++ est bien écrit, et l'optimisateur fait bien son boulot, ne
t'attends pas à pouvoir faire beaucoup mieux en assembleur. Pour
gagner une facteur dix, il va falloir faire des optimisations au
niveau de l'algorithme.

--
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

Vous avez filtré cet utilisateur ! Consultez son message

Fabien LE LEZ wrote:

On 28 Sep 2005 00:27:24 -0700, "kanze" :

Je ne comprends pas le « trop long ». Qu'est-ce que le
compilateur va faire de plus que tu ne dois pas faire en
assembleur ?

J'avais choisi l'exemple un peu au hasard, et j'avoue qu'il
était mauvais. Mais je viens de tomber sur un exemple typique
et réel.

C'est mieux. Moi aussi, quand je cherche à trouver des exemples
de tête, je finis toujours à en trouver un qui n'est pas ce que
je veux.

J'ai deux images en RVB (1 octet rouge, 1 octet vert, 1 octet
bleu) -- en fait deux frames successives dans une vidéo.

Je dois appliquer l'algorithme suivant : aucune composante ne
peut varier plus de deux fois plus vite que les autres. En
d'autres termes, et en simplifiant :

si (nouvelle_valeur[rouge]-ancienne_valeur[rouge]
2 * nouvelle_valeur[vert]-ancienne_valeur[vert])
alors nouvelle_valeur[rouge]= (ce qu'il faut)

Le "alors" ne m'inquiète pas trop ici, car le cas est peu
fréquent ; je ne m'intéresse qu'à la condition. Je peux la
réécrire ainsi :

si ( (nouvelle_valeur[rouge]-ancienne_valeur[rouge]) / 2
nouvelle_valeur[vert]-ancienne_valeur[vert])

Je ne suis pas trop sûr de comprendre. Normalement, j'aurais
imaginé que nouvelle_valeur et ancienne_valeur sont des unsigned
char. (En fait, j'imagine plutôt que ce sont les pointeurs à des
unsigned char. Et que rouge et vert sont des constantes, pendant
qu'on y est.) Seulement, si ce sont des unsigned, et que la
nouvelle_valeur est plus petit que l'ancienne_valeur, la
différence va être énorme.

De toute façon, on a un problème ici : si les types sont
unsigned, il faut bien ou faire la soustraction dans le bon
sens, ou convertir le résultat en signed et en prendre la valeur
absolue. Et s'ils sont signed, il y a le problème que la
différence entre deux signed ne tient pas forcément dans le même
type. Et évidemment, qu'il faut en prendre la valeur absolue.

Dans tous les cas, si je suppose qu'il s'agit de la
représentation « classique » avec des valeurs de 0...255, il me
faut au moins 9 bits dans les calculs intermédiaire pour que le
résultat soit juste.

Tous les nombres restent sur 8 bits ; j'aimerais donc beaucoup
faire de l'arithmétique en 8 bits, et ne pas avoir à faire des
conversions entre les entiers sur 1 octet et les entiers sur 4
octets.

Tes valeurs 8 bits sont bien en mémoire, n'est-ce pas ? Il faut
les charger dans des régistres pour faire les calculs. Et les
régistres ont quelle taille ?

Si le C a adopté la politique de la promotion integrale, ce
n'est pas pour des raisons théoriques ; c'est parce que c'est
comme ça que fonctionne le hardware. La seule exception que je
connais (ou plutôt connaissais), c'est les premiers 8086, où la
lecture d'un octet ne changeait qu'un démi-régister -- un coup
d'oeil rapide au manuel actuel me montre qu'il y a maintenant
des instructions MOVSX et MOVZX qui feraient parfaitement
l'affaire.

Maintenant, s'il s'agit de stocker le résultat immédiatement
dans un octet en mémoire, quelque chose du genre : x += y (ou x
et y ont le type unsigned char), je vois mal un compilateur qui
génère autre chose que :

MOV al,[byte ptr y]
ADD [byte ptr x],al

Après tous, le résultat serait exactement pareil que si
l'arithmétique se faisait sur 32 bits.

Le programme, tel que je l'ai écrit (en C++, sans assembleur
et sans chercher à optimiser) prend un temps fou (au bas mot,
c'est 10 fois plus lent que ce à quoi on pourrait s'attendre
pour un tel filtre) ; il va donc falloir que je trouve une
autre solution.

Si le profiler dit qu'il le faut, il le faut. Mais si le code
C++ est bien écrit, et l'optimisateur fait bien son boulot, ne
t'attends pas à pouvoir faire beaucoup mieux en assembleur. Pour
gagner une facteur dix, il va falloir faire des optimisations au
niveau de l'algorithme.

--
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

Jean-Marc Bourguet

04/10/2005 à 10:11

Fabien LE LEZ writes:

Tous les nombres restent sur 8 bits ; j'aimerais donc beaucoup faire
de l'arithmétique en 8 bits, et ne pas avoir à faire des conversions
entre les entiers sur 1 octet et les entiers sur 4 octets.

Les seuls cas ou j'ai l'impression qu'il y a moyen de gagner avec des
processeurs "normaux" en travaillant en 8 bits, c'est quand il y a
moyen d'utiliser les instructions vectorielles (dites "multimedia", ce
n'est pas les instructions vectorielles des processeurs Cray et
autres). Dans les autres cas, les chemins de donnees et les unites
fonctionnelles etant en 32 bits, il y aura conversion.

Le programme, tel que je l'ai écrit (en C++, sans assembleur et sans
chercher à optimiser) prend un temps fou (au bas mot, c'est 10 fois
plus lent que ce à quoi on pourrait s'attendre pour un tel filtre) ;
il va donc falloir que je trouve une autre solution.

C'est le genre de probleme ou on est normalement plus limite par la
bande passante que par le calcul. C'est en tout cas la ou je
regarderais en premier.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

kanze

05/10/2005 à 09:21

Jean-Marc Bourguet wrote:

Fabien LE LEZ writes:

Tous les nombres restent sur 8 bits ; j'aimerais donc
beaucoup faire de l'arithmétique en 8 bits, et ne pas avoir
à faire des conversions entre les entiers sur 1 octet et les
entiers sur 4 octets.

Les seuls cas ou j'ai l'impression qu'il y a moyen de gagner
avec des processeurs "normaux" en travaillant en 8 bits, c'est
quand il y a moyen d'utiliser les instructions vectorielles
(dites "multimedia", ce n'est pas les instructions
vectorielles des processeurs Cray et autres). Dans les autres
cas, les chemins de donnees et les unites fonctionnelles etant
en 32 bits, il y aura conversion.

Je ne suis pas sûr. Si le compilateur déroule la boucle, pour en
faire quatre pas chaque fois, puis réordonne le code de façon à
ce que les lectures de chaque table se suivent, il y a de fortes
chances qu'à la lecture des octets après le premier, le
processeur trouve que les données sont déjà là, et n'accède pas
à la mémoire pour les autres. Quelque chose du genre :

MOV al,[byte ptr table1][0]
MOV bl,[byte ptr table1][1]
MOV cl,[byte ptr table1][2]
MOV dl,[byte ptr table1][3]
ADD al,[byte ptr table2][0]
ADD bl,[byte ptr table2][1]
ADD cl,[byte ptr table2][2]
ADD dl,[byte ptr table2][3]
...

L'accès à [byte ptr table1][0] va en fait lire tout le mot, et
le processeur trouvera les autres octets de table1 déjà dans son
pipeline de lecture.

Ceci dit, le fait de travailler sur 32 bits à la place de 8 n'y
change pas forcement grand chose. On remplace les MOV par des
MOVZX. Et dans le cas de Fabien, il faut bien travailler sur au
moins 9 bits pour avoir un résultat correct.

Le programme, tel que je l'ai écrit (en C++, sans assembleur
et sans chercher à optimiser) prend un temps fou (au bas
mot, c'est 10 fois plus lent que ce à quoi on pourrait
s'attendre pour un tel filtre) ; il va donc falloir que je
trouve une autre solution.

C'est le genre de probleme ou on est normalement plus limite
par la bande passante que par le calcul. C'est en tout cas la
ou je regarderais en premier.

Probablement.

D'après les données, j'imagine qu'il s'agit d'un image à
afficher sur un écran. La résolution « standard » d'un écran
d'un desktop est de 1280x1024 ; à trois octets par pixel, ça
fait bien 3932160 octets à lire. Ça, c'est incontournable. À peu
près tout sur lequel il pourrait jouer, c'est la localisation,
pour augmenter l'efficacité de la cache. (Je suppose qu'il a
déjà fait la nécessaire pour que les données soient réelement en
mémoire réele, et qu'il n'y a pas de page faults.)

Note que même s'il n'accède qu'à chaque donnée une fois, pour
faire la boucle dans une séconde, il faut un temps d'accès moyen
de l'ordre de 250 ns. Or, dans son exemple, il y avait déjà deux
tableau (les valeurs actuelles, et les valeurs précédantes), et
je suppose qu'il lui faut exécuter le code plus qu'une fois par
séconde -- si c'est pour un traitement temps réel, j'ai un taux
de raffraichissement ici de 72 fois par séconde, ce qui fait
qu'il lui faut un temps d'accès moyen inférieur à 1.8 ns. Sur ma
machine ici, même les accès aux régistres ne sont pas aussi
vite. (Mais ma machine ici est un veau -- sur la machine chez
moi à la maison, je crois l'accès au cache du premier niveau est
inférieur à la nanoséconde. Seulement, quatre Go ne tient pas
dans la cache du premier niveau.)

S'il déclare les données dans une struct de quatre octets,
genre :

struct { uint8_t red,green,blue,fill ; } ;

et que le compilateur est assez intelligent pour lire le struct
dans un seul coup, et le tenir dans un régistre, ça dévise le
nombre d'accès par quatre. (Seulement, sur un Intel, les deux
octets de poids fort d'un registre ne sont pas accessible
directement comme octets. Du coup, il faut des décalages et des
masquages, qui ne vont pas accélérer le traitement non plus.)

Il ne nous a pas donné la contexte, mais si le but est un
traitement d'image en temps réel sur une machine genre desktop,
je crois que c'est cuit d'avance. Et il ne faut pas blâmer le
langage parce que le compilateur n'arrive pas à faire
l'impossible.

--
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

Jean-Marc Bourguet wrote:

Fabien LE LEZ <gramster@gramster.com> writes:

Tous les nombres restent sur 8 bits ; j'aimerais donc
beaucoup faire de l'arithmétique en 8 bits, et ne pas avoir
à faire des conversions entre les entiers sur 1 octet et les
entiers sur 4 octets.

Les seuls cas ou j'ai l'impression qu'il y a moyen de gagner
avec des processeurs "normaux" en travaillant en 8 bits, c'est
quand il y a moyen d'utiliser les instructions vectorielles
(dites "multimedia", ce n'est pas les instructions
vectorielles des processeurs Cray et autres). Dans les autres
cas, les chemins de donnees et les unites fonctionnelles etant
en 32 bits, il y aura conversion.

Je ne suis pas sûr. Si le compilateur déroule la boucle, pour en
faire quatre pas chaque fois, puis réordonne le code de façon à
ce que les lectures de chaque table se suivent, il y a de fortes
chances qu'à la lecture des octets après le premier, le
processeur trouve que les données sont déjà là, et n'accède pas
à la mémoire pour les autres. Quelque chose du genre :

MOV al,[byte ptr table1][0]
MOV bl,[byte ptr table1][1]
MOV cl,[byte ptr table1][2]
MOV dl,[byte ptr table1][3]
ADD al,[byte ptr table2][0]
ADD bl,[byte ptr table2][1]
ADD cl,[byte ptr table2][2]
ADD dl,[byte ptr table2][3]
...

L'accès à [byte ptr table1][0] va en fait lire tout le mot, et
le processeur trouvera les autres octets de table1 déjà dans son
pipeline de lecture.

Ceci dit, le fait de travailler sur 32 bits à la place de 8 n'y
change pas forcement grand chose. On remplace les MOV par des
MOVZX. Et dans le cas de Fabien, il faut bien travailler sur au
moins 9 bits pour avoir un résultat correct.

Le programme, tel que je l'ai écrit (en C++, sans assembleur
et sans chercher à optimiser) prend un temps fou (au bas
mot, c'est 10 fois plus lent que ce à quoi on pourrait
s'attendre pour un tel filtre) ; il va donc falloir que je
trouve une autre solution.

C'est le genre de probleme ou on est normalement plus limite
par la bande passante que par le calcul. C'est en tout cas la
ou je regarderais en premier.

Probablement.

D'après les données, j'imagine qu'il s'agit d'un image à
afficher sur un écran. La résolution « standard » d'un écran
d'un desktop est de 1280x1024 ; à trois octets par pixel, ça
fait bien 3932160 octets à lire. Ça, c'est incontournable. À peu
près tout sur lequel il pourrait jouer, c'est la localisation,
pour augmenter l'efficacité de la cache. (Je suppose qu'il a
déjà fait la nécessaire pour que les données soient réelement en
mémoire réele, et qu'il n'y a pas de page faults.)

Note que même s'il n'accède qu'à chaque donnée une fois, pour
faire la boucle dans une séconde, il faut un temps d'accès moyen
de l'ordre de 250 ns. Or, dans son exemple, il y avait déjà deux
tableau (les valeurs actuelles, et les valeurs précédantes), et
je suppose qu'il lui faut exécuter le code plus qu'une fois par
séconde -- si c'est pour un traitement temps réel, j'ai un taux
de raffraichissement ici de 72 fois par séconde, ce qui fait
qu'il lui faut un temps d'accès moyen inférieur à 1.8 ns. Sur ma
machine ici, même les accès aux régistres ne sont pas aussi
vite. (Mais ma machine ici est un veau -- sur la machine chez
moi à la maison, je crois l'accès au cache du premier niveau est
inférieur à la nanoséconde. Seulement, quatre Go ne tient pas
dans la cache du premier niveau.)

S'il déclare les données dans une struct de quatre octets,
genre :

struct { uint8_t red,green,blue,fill ; } ;

et que le compilateur est assez intelligent pour lire le struct
dans un seul coup, et le tenir dans un régistre, ça dévise le
nombre d'accès par quatre. (Seulement, sur un Intel, les deux
octets de poids fort d'un registre ne sont pas accessible
directement comme octets. Du coup, il faut des décalages et des
masquages, qui ne vont pas accélérer le traitement non plus.)

Il ne nous a pas donné la contexte, mais si le but est un
traitement d'image en temps réel sur une machine genre desktop,
je crois que c'est cuit d'avance. Et il ne faut pas blâmer le
langage parce que le compilateur n'arrive pas à faire
l'impossible.

--
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

Vous avez filtré cet utilisateur ! Consultez son message

Jean-Marc Bourguet wrote:

Fabien LE LEZ writes:

Tous les nombres restent sur 8 bits ; j'aimerais donc
beaucoup faire de l'arithmétique en 8 bits, et ne pas avoir
à faire des conversions entre les entiers sur 1 octet et les
entiers sur 4 octets.

Les seuls cas ou j'ai l'impression qu'il y a moyen de gagner
avec des processeurs "normaux" en travaillant en 8 bits, c'est
quand il y a moyen d'utiliser les instructions vectorielles
(dites "multimedia", ce n'est pas les instructions
vectorielles des processeurs Cray et autres). Dans les autres
cas, les chemins de donnees et les unites fonctionnelles etant
en 32 bits, il y aura conversion.

Je ne suis pas sûr. Si le compilateur déroule la boucle, pour en
faire quatre pas chaque fois, puis réordonne le code de façon à
ce que les lectures de chaque table se suivent, il y a de fortes
chances qu'à la lecture des octets après le premier, le
processeur trouve que les données sont déjà là, et n'accède pas
à la mémoire pour les autres. Quelque chose du genre :

MOV al,[byte ptr table1][0]
MOV bl,[byte ptr table1][1]
MOV cl,[byte ptr table1][2]
MOV dl,[byte ptr table1][3]
ADD al,[byte ptr table2][0]
ADD bl,[byte ptr table2][1]
ADD cl,[byte ptr table2][2]
ADD dl,[byte ptr table2][3]
...

L'accès à [byte ptr table1][0] va en fait lire tout le mot, et
le processeur trouvera les autres octets de table1 déjà dans son
pipeline de lecture.

Ceci dit, le fait de travailler sur 32 bits à la place de 8 n'y
change pas forcement grand chose. On remplace les MOV par des
MOVZX. Et dans le cas de Fabien, il faut bien travailler sur au
moins 9 bits pour avoir un résultat correct.

Le programme, tel que je l'ai écrit (en C++, sans assembleur
et sans chercher à optimiser) prend un temps fou (au bas
mot, c'est 10 fois plus lent que ce à quoi on pourrait
s'attendre pour un tel filtre) ; il va donc falloir que je
trouve une autre solution.

C'est le genre de probleme ou on est normalement plus limite
par la bande passante que par le calcul. C'est en tout cas la
ou je regarderais en premier.

Probablement.

D'après les données, j'imagine qu'il s'agit d'un image à
afficher sur un écran. La résolution « standard » d'un écran
d'un desktop est de 1280x1024 ; à trois octets par pixel, ça
fait bien 3932160 octets à lire. Ça, c'est incontournable. À peu
près tout sur lequel il pourrait jouer, c'est la localisation,
pour augmenter l'efficacité de la cache. (Je suppose qu'il a
déjà fait la nécessaire pour que les données soient réelement en
mémoire réele, et qu'il n'y a pas de page faults.)

Note que même s'il n'accède qu'à chaque donnée une fois, pour
faire la boucle dans une séconde, il faut un temps d'accès moyen
de l'ordre de 250 ns. Or, dans son exemple, il y avait déjà deux
tableau (les valeurs actuelles, et les valeurs précédantes), et
je suppose qu'il lui faut exécuter le code plus qu'une fois par
séconde -- si c'est pour un traitement temps réel, j'ai un taux
de raffraichissement ici de 72 fois par séconde, ce qui fait
qu'il lui faut un temps d'accès moyen inférieur à 1.8 ns. Sur ma
machine ici, même les accès aux régistres ne sont pas aussi
vite. (Mais ma machine ici est un veau -- sur la machine chez
moi à la maison, je crois l'accès au cache du premier niveau est
inférieur à la nanoséconde. Seulement, quatre Go ne tient pas
dans la cache du premier niveau.)

S'il déclare les données dans une struct de quatre octets,
genre :

struct { uint8_t red,green,blue,fill ; } ;

et que le compilateur est assez intelligent pour lire le struct
dans un seul coup, et le tenir dans un régistre, ça dévise le
nombre d'accès par quatre. (Seulement, sur un Intel, les deux
octets de poids fort d'un registre ne sont pas accessible
directement comme octets. Du coup, il faut des décalages et des
masquages, qui ne vont pas accélérer le traitement non plus.)

Il ne nous a pas donné la contexte, mais si le but est un
traitement d'image en temps réel sur une machine genre desktop,
je crois que c'est cuit d'avance. Et il ne faut pas blâmer le
langage parce que le compilateur n'arrive pas à faire
l'impossible.

--
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

Jean-Marc Bourguet

05/10/2005 à 10:16

"kanze" writes:

Jean-Marc Bourguet wrote:
Fabien LE LEZ writes:

Tous les nombres restent sur 8 bits ; j'aimerais donc
beaucoup faire de l'arithmétique en 8 bits, et ne pas avoir
à faire des conversions entre les entiers sur 1 octet et les
entiers sur 4 octets.

Les seuls cas ou j'ai l'impression qu'il y a moyen de gagner
avec des processeurs "normaux" en travaillant en 8 bits, c'est
quand il y a moyen d'utiliser les instructions vectorielles
(dites "multimedia", ce n'est pas les instructions
vectorielles des processeurs Cray et autres). Dans les autres
cas, les chemins de donnees et les unites fonctionnelles etant
en 32 bits, il y aura conversion.

Je ne suis pas sûr. Si le compilateur déroule la boucle, pour en
faire quatre pas chaque fois, puis réordonne le code de façon à
ce que les lectures de chaque table se suivent, il y a de fortes
chances qu'à la lecture des octets après le premier, le
processeur trouve que les données sont déjà là, et n'accède pas
à la mémoire pour les autres.

J'ai du mal a voir en quoi aider.

Les acces a la memoire se font de toute maniere a travers le cache et
se font par ligne de cache complete (ce qui fait plus de 4 octets).

Si on veut eviter l'attente des lectures, il faut jouer avec les
instructions de prefetch pour que le remplissage des caches (il y a
souvent plus d'un niveau) se fasse autant que possible en parallele
avec les calculs et ne pas causer des attentes.

Ceci dit, le fait de travailler sur 32 bits à la place de 8 n'y
change pas forcement grand chose.

Je serais surpris que ca change beaucoup. Et je ne serais pas surpris
que si ca change, ce soit en faveur de l'utilisation des registres sur
32 bits.

S'il déclare les données dans une struct de quatre octets,
genre :

struct { uint8_t red,green,blue,fill ; } ;

et que le compilateur est assez intelligent pour lire le struct
dans un seul coup, et le tenir dans un régistre, ça dévise le
nombre d'accès par quatre. (Seulement, sur un Intel, les deux
octets de poids fort d'un registre ne sont pas accessible
directement comme octets. Du coup, il faut des décalages et des
masquages, qui ne vont pas accélérer le traitement non plus.)

J'irais voir du cote des instructions multimedia qui sont justement
concues pour ce genre de situation. Mais je les connais mal.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

"kanze" <kanze@gabi-soft.fr> writes:

Jean-Marc Bourguet wrote:

Fabien LE LEZ <gramster@gramster.com> writes:

Tous les nombres restent sur 8 bits ; j'aimerais donc
beaucoup faire de l'arithmétique en 8 bits, et ne pas avoir
à faire des conversions entre les entiers sur 1 octet et les
entiers sur 4 octets.

Les seuls cas ou j'ai l'impression qu'il y a moyen de gagner
avec des processeurs "normaux" en travaillant en 8 bits, c'est
quand il y a moyen d'utiliser les instructions vectorielles
(dites "multimedia", ce n'est pas les instructions
vectorielles des processeurs Cray et autres). Dans les autres
cas, les chemins de donnees et les unites fonctionnelles etant
en 32 bits, il y aura conversion.

Je ne suis pas sûr. Si le compilateur déroule la boucle, pour en
faire quatre pas chaque fois, puis réordonne le code de façon à
ce que les lectures de chaque table se suivent, il y a de fortes
chances qu'à la lecture des octets après le premier, le
processeur trouve que les données sont déjà là, et n'accède pas
à la mémoire pour les autres.

J'ai du mal a voir en quoi aider.

Les acces a la memoire se font de toute maniere a travers le cache et
se font par ligne de cache complete (ce qui fait plus de 4 octets).

Si on veut eviter l'attente des lectures, il faut jouer avec les
instructions de prefetch pour que le remplissage des caches (il y a
souvent plus d'un niveau) se fasse autant que possible en parallele
avec les calculs et ne pas causer des attentes.

Ceci dit, le fait de travailler sur 32 bits à la place de 8 n'y
change pas forcement grand chose.

Je serais surpris que ca change beaucoup. Et je ne serais pas surpris
que si ca change, ce soit en faveur de l'utilisation des registres sur
32 bits.

S'il déclare les données dans une struct de quatre octets,
genre :

struct { uint8_t red,green,blue,fill ; } ;

et que le compilateur est assez intelligent pour lire le struct
dans un seul coup, et le tenir dans un régistre, ça dévise le
nombre d'accès par quatre. (Seulement, sur un Intel, les deux
octets de poids fort d'un registre ne sont pas accessible
directement comme octets. Du coup, il faut des décalages et des
masquages, qui ne vont pas accélérer le traitement non plus.)

J'irais voir du cote des instructions multimedia qui sont justement
concues pour ce genre de situation. Mais je les connais mal.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Vous avez filtré cet utilisateur ! Consultez son message

"kanze" writes:

Jean-Marc Bourguet wrote:
Fabien LE LEZ writes:

Tous les nombres restent sur 8 bits ; j'aimerais donc
beaucoup faire de l'arithmétique en 8 bits, et ne pas avoir
à faire des conversions entre les entiers sur 1 octet et les
entiers sur 4 octets.

Les seuls cas ou j'ai l'impression qu'il y a moyen de gagner
avec des processeurs "normaux" en travaillant en 8 bits, c'est
quand il y a moyen d'utiliser les instructions vectorielles
(dites "multimedia", ce n'est pas les instructions
vectorielles des processeurs Cray et autres). Dans les autres
cas, les chemins de donnees et les unites fonctionnelles etant
en 32 bits, il y aura conversion.

Je ne suis pas sûr. Si le compilateur déroule la boucle, pour en
faire quatre pas chaque fois, puis réordonne le code de façon à
ce que les lectures de chaque table se suivent, il y a de fortes
chances qu'à la lecture des octets après le premier, le
processeur trouve que les données sont déjà là, et n'accède pas
à la mémoire pour les autres.

J'ai du mal a voir en quoi aider.

Les acces a la memoire se font de toute maniere a travers le cache et
se font par ligne de cache complete (ce qui fait plus de 4 octets).

Si on veut eviter l'attente des lectures, il faut jouer avec les
instructions de prefetch pour que le remplissage des caches (il y a
souvent plus d'un niveau) se fasse autant que possible en parallele
avec les calculs et ne pas causer des attentes.

Ceci dit, le fait de travailler sur 32 bits à la place de 8 n'y
change pas forcement grand chose.

Je serais surpris que ca change beaucoup. Et je ne serais pas surpris
que si ca change, ce soit en faveur de l'utilisation des registres sur
32 bits.

S'il déclare les données dans une struct de quatre octets,
genre :

struct { uint8_t red,green,blue,fill ; } ;

et que le compilateur est assez intelligent pour lire le struct
dans un seul coup, et le tenir dans un régistre, ça dévise le
nombre d'accès par quatre. (Seulement, sur un Intel, les deux
octets de poids fort d'un registre ne sont pas accessible
directement comme octets. Du coup, il faut des décalages et des
masquages, qui ne vont pas accélérer le traitement non plus.)

J'irais voir du cote des instructions multimedia qui sont justement
concues pour ce genre de situation. Mais je les connais mal.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

[débutant objet] tableau de pointeur de fonction

7 réponses

Veuillez sélectionner un problème