Tableaux multidimensionnels et déréférencement

Lucas Levrel

15/06/2009 à 14:18

Le 15 juin 2009, Marc Boyer a écrit :

J'ai raté un truc ? Ton argument ne tient pas: à tout type
de base, on peut associer un n, ok, mais on reste dénombrable.
Rajoute encore un n, et ça reste dénombrable. Ainsi de suite.

Certes, j'ai parlé un peu vite, mais le « ainsi de suite » me paraît un
peu rapide aussi. C'est sûr que N^p est dénombrable, mais {N^p / p entier}
me paraît moins évident !

--
LL

espie

15/06/2009 à 14:43

In article ,
Lucas Levrel wrote:

Le 15 juin 2009, Marc Boyer a Ã©crit :

J'ai ratÃ© un truc ? Ton argument ne tient pas: Ã tout type
de base, on peut associer un n, ok, mais on reste dÃ©nombrable.
Rajoute encore un n, et Ã§a reste dÃ©nombrable. Ainsi de suite.

Certes, j'ai parlÃ© un peu vite, mais le Â«Â ainsi de suiteÂ Â» me paraÃ®t un
peu rapide aussi. C'est sÃ»r que N^p est dÃ©nombrable, mais {N^p / p entier}
me paraÃ®t moins Ã©vident !

Tu as donc les p-uplets de nombres, eventuellement identiques. Tu peux assez
facilement montrer qu'il y en a moins que de parties finies de N.
Par exemple,
(a, b, c, d) => (a, a+b+1, a+b+c+2, a+b+c+d+3)
est une bijection.

et l'ensemble des parties finies de N est denombrable, c'est un exo classique:
tu prends la somme des 2^k, pour k appartenant a la partie consideree.
En vertu des proprietes classiques de l'enumeration en base 2, c'est
trivialement une bijection.

pour sortir du denombrable, il faut une suite *infinie* d'entiers. Tant que
tu restes dans l'arbitrairement long, mais finie, ca ne marche pas.

Et on prouve classiquement que ca n'est pas denombrable avec le procede
d'enumeration diagonale de Cantor: on construit une suite infinie qui n'est
egale a aucun n...

En general, on finit en disant que R n'est pas denombrable. Suffit d'utiliser
la numeration decimale, d'appliquer le procede precedent, et de verifier que
les artefacts de type 0,9999999999 = 1 sont negligeables (puisque
denombrables).

Antoine Leca

15/06/2009 à 15:01

Le 15/06/2009 12:43, Marc Espie écrivit :

pour sortir du denombrable, il faut une suite *infinie* d'entiers. Tant que
tu restes dans l'arbitrairement long, mais finie, ca ne marche pas.

OK, c'est clair pour moi.
On peut revenir au sujet ?

Et désolé pour le message précédent qui s'est échappé en Unicode,
j'espère que c'est corrigé ici.

Antoine

Marc Boyer

15/06/2009 à 15:04

On 2009-06-15, Lucas Levrel wrote:

Le 15 juin 2009, Marc Boyer a écrit :

J'ai raté un truc ? Ton argument ne tient pas: à tout type
de base, on peut associer un n, ok, mais on reste dénombrable.
Rajoute encore un n, et ça reste dénombrable. Ainsi de suite.

Certes, j'ai parlé un peu vite, mais le « ainsi de suite » me paraît un
peu rapide aussi. C'est sûr que N^p est dénombrable, mais {N^p / p entier}
me paraît moins évident !

Mais, {N^p | p entier}, c'est N^*, l'ensemble des vecteurs finis,
à ne pas confondre avec N^oo, l'ensemble des vacteurs infinis, et
N^omega, l'union des deux précédents.
Et N^*, il est dénombrable à ma connaissance.

Marc Boyer
--
Au XXIème siècle, notre projet de société s'est réduit
à un projet économique...

Marc Boyer

15/06/2009 à 15:12

On 2009-06-15, Marc Espie wrote:

In article <h0qqis$tcl$,
Antoine Leca wrote:
Que veut dire Â« tous Â» ? Les types du C dÃ©crivent un ensemble infini
(peut-Ãªtre mÃªme non dÃ©nombrable, mais cela fait trop longtemps que ce
sujet ne me prÃ©occupe plus pour que je ne sois pas 100% sÃ»r).

N'importe quoi.

Le C est un langage, les types du C ont une expression, sous forme de chaine
de caracteres explicitant le type. Ils sont donc forcement denombrables...

Disons qu'il faut arriver à exprimer un infini non dénombrable avec
un nombre fini de symbole, et c'est pas évident à faire avec
une sémantique raisonnable.

Oui, il y a des trucs marrants en theorie des types. Mais il faut du typage
automatique pour sortir des trucs exprimables par le systeme de types... et
c'est bien le souci, en general.

Voui, avec des constructeurs universels et existentiels, et
un petit point fixe, on doit pouvoir jouer...
M'enfin, on doit être loi du C...

Marc Boyer
--
Au XXIème siècle, notre projet de société s'est réduit
à un projet économique...

Antoine Leca

15/06/2009 à 16:43

Le 15/06/2009 8:20, Lucas Levrel écrivit :

Le 11 juin 2009, Antoine Leca a écrit :
Le 11/06/2009 08:14Z, Lucas Levrel écrivit :
Ah, l'ambiguïté entre valeur et adresse d'un pointeur...

Personnellement je ne vois aucune ambiguïté.

Je parlais de l'ambiguïté du vocabulaire, pas de la notion bien sûr.
Car la valeur du pointeur est l'adresse de l'objet pointé.

Ah! Pardon, je n'avais pas vu que «d'un pointeur» qualifiait valeur.

Donc quand je demande si « table[i] existe en mémoire », je suis
trop succinct, car ça peut vouloir dire :
1) est-ce que la valeur de table[i] est une adresse qui existe
ou
2) est-ce que l'objet table[i] est stocké en mémoire

Voilà. Moi, je ne vois que la seconde forme ; la première ne me vient
pas à l'esprit. Entre autres parce qu'une expression qui a pour type
int[N] n'est pas pour moi un pointeur ou une adresse, mais un objet.

Le fait est que souvent, l'expression table[i] va devenir un pointeur ;
mais ce n'est pas systématique ; exemple, derrière sizeof, ou devant ou dans une initialisation.

Par ailleurs, le pointeur est lui-même un objet, et comme tout objet
possède son adresse propre.

C'est bien de ça que je parlais.

¿¿¿Bzzz??? Là tu m'as complètement perdu... Deux lignes plus haut tu dit
qu'il ne faut pas considérer l'adresse du pointeur (mais sa valeur, qui
est l'adresse de l'objet pointé), et quand j'en parle tu dis que c'est
bien de cela qu'il s'agit...

Serait-ce que ma formulation fut malheureuse et que je n'ai pas réussi à
bien différencier les deux adresses ? Car moi, dans la phrase ci-dessus
je voulais parler d'une *AUTRE* adresse que celle dont il est question,
l'hypothétique adresse où se trouve l'hypothétique pointeur (qui pour
moi n'existe pas, je l'appelerai virtuel).

Je crois que c'est assez clair à la
lumière de la deuxième question de mon post initial, où je parlais de
tableaux dynamiques pour lesquels on crée d'abord int *table[3], puis on
fait pointer chaque table[i] vers un int[4].

Euh... Je dois avoir loupé quelque chose...
Pour moi, un tableau dynamique ne désigne pas un tableau de pointeurs
vers des tableaux (éventuellement disjoints en mémoire, et de taille
allouées éventuellement distinctes), mais plutôt un tableau homogène
d'un seul bloc alloué dynamiquement (par malloc()).
Je me trompai, me trompé-je?

Par ailleurs, dans la formulation
int table[3][4];
il n'y a que 12 int, et pas de tableaux de pointeurs;
et il n'y a un pointeur QUE dans le contexte
int fonction_ancien_style(table)
int table[3][4];
{ /* */ }

(et je ne pense pas que tu parles de ce cas-là).

Je sais que table[i] est l'adresse d'une zone mémoire allouée,
c'est celle de la valeur table[i][0].

Pour la n-ième fois, je ne comprends pas ta notation.

table[i] == &(table[i][0])
Non ?

Oui, c'est la spécification de l'opérateur & appliqué à blabla[0] que de
pouvoir être remplacé par blabla tout court.
Mais pour moi, les deux sont des objets (tableaux de 4 int) ; qui en
plus d'une adresse ont un type, et dont la valeur sont des quadruplets.

Je dois dire que je ne pensai pas qu'il faille rajouter &.

Je suis désolé, je n'avais pas ma tête, je n'avais pas bien compris.
J'ai trop l'habitude de considérer la complexité potentielle des
expressions en C avec des pointeurs vers tableaux et les différents
niveaux d'indirection possible, je pense que je n'arrive pas à
simplifier suffisament mon propos.

Évidemment, avec ces conventions, tu ne dois pas comprendre la plupart
de mes remarques car je n'arrive pas à entrer dans ton formalisme.
Je m'en excuse.

le compilateur réserve-t-il trois zones de mémoire pour stocker table[0],
table[1] et table[2] ?

Il réserve une seule zone de 12 int. On peut ensuite voir cela comme
trois zones, mais il n'en reste pas moins que les zones sont contiguës.

Là encore, je ne parlais pas de ce sur quoi pointent les table[i], à
savoir des zones de 4 int, mais des table[i] eux-mêmes.

Ah! tu parlais des pointeurs virtuels vers les tableaux d'int!
Encore désolé de ne pas avoir compris plus tôt.

Non, le compilateur ne réserve pas de zones mémoire pour ces pointeurs,
ils restent virtuels.

(OK, dans les détails, il est possible que dans certaines expressions
complexes le compilateur soit obligé de créer des variables temporaires,
normalement en pile, pour stocker ces pointeurs lors du calcul d'une
expression plus large. Donc il y aura réservation d'espace "auto".
Mais c'est encore une fois la cuisine.)

Mais bon, cela c'est la salade interne des compilateurs, ce n'est pas
important.

C'est ce que je cherche à comprendre, par exemple quand je demande si ça
aurait un intérêt (en vitesse d'exécution) de déclarer int table[12] et de
gérer moi-même l'indexation (voir la Q2 de mon post initial).

Impossible de répondre à cette question en général.

Par exemple, imagines que tu as un algorithme sur une matrice
triangulaire avec plusieurs passes, que la matrice allouée par morceaux
(de taille croissante) tienne en mémoire centrale mais que la matrice
allouée d'un seul coup (qui est donc environ 50% plus grande) ne tienne
pas et oblige à utiliser la mémoire d'échange (swap) : dans ce cas
précis, il est facile de voir qu'une des méthode aura des performances
supérieures à l'autre.

Un autre exemple où l'allocation par morceau peut être moins efficace :
si l'allocateur mémoire fabrique des morceaux juste d'une taille
multiple d'une page, et si tu traverses la matrice dans l'autre sens : à
un instant donné tu vas donc manipuler des lignes mémoire qui ont toutes
par le même motif d'adresse xx234yy0 (par exemple), et tu peux (pouvais)
alors engorger une petite partie du TLB...
La manière habituelle d'optimiser ce genre de contrainte est d'allouer
une taille d'éléments légèrement supérieure qui ne soit pas multiple de
la taille de page, mais là cela ne va pas fonctionner à cause de
l'allocateur.

Mais bon, comme toutes les discussions sur l'optimisation, la bonne
réponse c'est qu'il ne faut pas se préoccuper des optimisations en C, et
surtout pas lors que l'on est encore à la phase de conception ou avant.
Il est généralement /beaucoup/ plus efficace et surtout rentable de
choisir de bons algorithmes (en amont) ou d'augmenter le rendement des
machines (en aval).

Par exemple, que verrait-on si on lisait le code assembleur
produit par le compilo ?

xycc -S > tes_yeux

~> xycc
bash: xycc: command not found

Pardon. En général les compilateurs C sont appelés par une commande qui
finit par cc ([machine truc] C Compiler en anglais), et ont toujours en
général une option -S qui génère un listage en assembleur.

Dans ton cas,
$ gcc -S ton_source.c | less
devrait le faire. Ce sera différent pour d'autres lecteurs de ce groupe.

Tous les types du C existent-ils ?

Où ?

Tu sépares les phrases... Dans le code assembleur produit !

La question n'est pas aussi stupide. Je voulais te demander, au niveau
du code (représentation du binaire), ou au niveau du flux assembleur
produit (dans ton environnement) par le compilateur à destination de
l'assembleur.

Les réponses étant respectivement non et oui.
La différence étant que les informations de type sont (normalement)
rangées dans le fichier objet produit sous forme d'informations
symboliques destinées à l'éventuel débogage.

Que veut dire « tous » ?
Les types du C décrivent un ensemble infini
(peut-être même non dénombrable, [...]

Y'a des chances, vu qu'on peut mettre autant de [n] qu'on veut avec n
entier strictement positif quelconque, ça fait un beau N^N !

... qui reste un nombre. OK bon, ce n'est pas le sujet.

En fait, je voulais savoir si tu voulais faire référence à l'ensemble de
tous les types possible du langage C, dont il devrait paraître assez
évident qu'ils ne sont pas /tous/ représentés dans le flux produit (d'où
ma stupide remarque),
ou bien si tu voulais faire référence à l'ensemble des types que le
compilateur a construit au cours de l'analyse (y compris ceux qui ne
servent pas effectivement, par exemple int(*)[3][4] dans ton exemple),
auquel cas la réponse est peut-être,
ou si tu faisais référence aux types explicitement utilisés, auquel cas
je pense que la réponse devrait être oui sous réserve de la qualité du
compilateur.

Antoine

Le 15/06/2009 8:20, Lucas Levrel écrivit :

Le 11 juin 2009, Antoine Leca a écrit :

Le 11/06/2009 08:14Z, Lucas Levrel écrivit :

Ah, l'ambiguïté entre valeur et adresse d'un pointeur...

Personnellement je ne vois aucune ambiguïté.

Je parlais de l'ambiguïté du vocabulaire, pas de la notion bien sûr.
Car la valeur du pointeur est l'adresse de l'objet pointé.

Ah! Pardon, je n'avais pas vu que «d'un pointeur» qualifiait valeur.

Donc quand je demande si « table[i] existe en mémoire », je suis
trop succinct, car ça peut vouloir dire :
1) est-ce que la valeur de table[i] est une adresse qui existe
ou
2) est-ce que l'objet table[i] est stocké en mémoire

Voilà. Moi, je ne vois que la seconde forme ; la première ne me vient
pas à l'esprit. Entre autres parce qu'une expression qui a pour type
int[N] n'est pas pour moi un pointeur ou une adresse, mais un objet.

Le fait est que souvent, l'expression table[i] va devenir un pointeur ;
mais ce n'est pas systématique ; exemple, derrière sizeof, ou devant ou dans une initialisation.

Par ailleurs, le pointeur est lui-même un objet, et comme tout objet
possède son adresse propre.

C'est bien de ça que je parlais.

¿¿¿Bzzz??? Là tu m'as complètement perdu... Deux lignes plus haut tu dit
qu'il ne faut pas considérer l'adresse du pointeur (mais sa valeur, qui
est l'adresse de l'objet pointé), et quand j'en parle tu dis que c'est
bien de cela qu'il s'agit...

Serait-ce que ma formulation fut malheureuse et que je n'ai pas réussi à
bien différencier les deux adresses ? Car moi, dans la phrase ci-dessus
je voulais parler d'une *AUTRE* adresse que celle dont il est question,
l'hypothétique adresse où se trouve l'hypothétique pointeur (qui pour
moi n'existe pas, je l'appelerai virtuel).

Je crois que c'est assez clair à la
lumière de la deuxième question de mon post initial, où je parlais de
tableaux dynamiques pour lesquels on crée d'abord int *table[3], puis on
fait pointer chaque table[i] vers un int[4].

Euh... Je dois avoir loupé quelque chose...
Pour moi, un tableau dynamique ne désigne pas un tableau de pointeurs
vers des tableaux (éventuellement disjoints en mémoire, et de taille
allouées éventuellement distinctes), mais plutôt un tableau homogène
d'un seul bloc alloué dynamiquement (par malloc()).
Je me trompai, me trompé-je?

Par ailleurs, dans la formulation
int table[3][4];
il n'y a que 12 int, et pas de tableaux de pointeurs;
et il n'y a un pointeur QUE dans le contexte
int fonction_ancien_style(table)
int table[3][4];
{ /* */ }

(et je ne pense pas que tu parles de ce cas-là).

Je sais que table[i] est l'adresse d'une zone mémoire allouée,
c'est celle de la valeur table[i][0].

Pour la n-ième fois, je ne comprends pas ta notation.

table[i] == &(table[i][0])
Non ?

Oui, c'est la spécification de l'opérateur & appliqué à blabla[0] que de
pouvoir être remplacé par blabla tout court.
Mais pour moi, les deux sont des objets (tableaux de 4 int) ; qui en
plus d'une adresse ont un type, et dont la valeur sont des quadruplets.

Je dois dire que je ne pensai pas qu'il faille rajouter &.

Je suis désolé, je n'avais pas ma tête, je n'avais pas bien compris.
J'ai trop l'habitude de considérer la complexité potentielle des
expressions en C avec des pointeurs vers tableaux et les différents
niveaux d'indirection possible, je pense que je n'arrive pas à
simplifier suffisament mon propos.

Évidemment, avec ces conventions, tu ne dois pas comprendre la plupart
de mes remarques car je n'arrive pas à entrer dans ton formalisme.
Je m'en excuse.

le compilateur réserve-t-il trois zones de mémoire pour stocker table[0],
table[1] et table[2] ?

Il réserve une seule zone de 12 int. On peut ensuite voir cela comme
trois zones, mais il n'en reste pas moins que les zones sont contiguës.

Là encore, je ne parlais pas de ce sur quoi pointent les table[i], à
savoir des zones de 4 int, mais des table[i] eux-mêmes.

Ah! tu parlais des pointeurs virtuels vers les tableaux d'int!
Encore désolé de ne pas avoir compris plus tôt.

Non, le compilateur ne réserve pas de zones mémoire pour ces pointeurs,
ils restent virtuels.

(OK, dans les détails, il est possible que dans certaines expressions
complexes le compilateur soit obligé de créer des variables temporaires,
normalement en pile, pour stocker ces pointeurs lors du calcul d'une
expression plus large. Donc il y aura réservation d'espace "auto".
Mais c'est encore une fois la cuisine.)

Mais bon, cela c'est la salade interne des compilateurs, ce n'est pas
important.

C'est ce que je cherche à comprendre, par exemple quand je demande si ça
aurait un intérêt (en vitesse d'exécution) de déclarer int table[12] et de
gérer moi-même l'indexation (voir la Q2 de mon post initial).

Impossible de répondre à cette question en général.

Par exemple, imagines que tu as un algorithme sur une matrice
triangulaire avec plusieurs passes, que la matrice allouée par morceaux
(de taille croissante) tienne en mémoire centrale mais que la matrice
allouée d'un seul coup (qui est donc environ 50% plus grande) ne tienne
pas et oblige à utiliser la mémoire d'échange (swap) : dans ce cas
précis, il est facile de voir qu'une des méthode aura des performances
supérieures à l'autre.

Un autre exemple où l'allocation par morceau peut être moins efficace :
si l'allocateur mémoire fabrique des morceaux juste d'une taille
multiple d'une page, et si tu traverses la matrice dans l'autre sens : à
un instant donné tu vas donc manipuler des lignes mémoire qui ont toutes
par le même motif d'adresse xx234yy0 (par exemple), et tu peux (pouvais)
alors engorger une petite partie du TLB...
La manière habituelle d'optimiser ce genre de contrainte est d'allouer
une taille d'éléments légèrement supérieure qui ne soit pas multiple de
la taille de page, mais là cela ne va pas fonctionner à cause de
l'allocateur.

Mais bon, comme toutes les discussions sur l'optimisation, la bonne
réponse c'est qu'il ne faut pas se préoccuper des optimisations en C, et
surtout pas lors que l'on est encore à la phase de conception ou avant.
Il est généralement /beaucoup/ plus efficace et surtout rentable de
choisir de bons algorithmes (en amont) ou d'augmenter le rendement des
machines (en aval).

Par exemple, que verrait-on si on lisait le code assembleur
produit par le compilo ?

xycc -S > tes_yeux

~> xycc
bash: xycc: command not found

Pardon. En général les compilateurs C sont appelés par une commande qui
finit par cc ([machine truc] C Compiler en anglais), et ont toujours en
général une option -S qui génère un listage en assembleur.

Dans ton cas,
$ gcc -S ton_source.c | less
devrait le faire. Ce sera différent pour d'autres lecteurs de ce groupe.

Tous les types du C existent-ils ?

Où ?

Tu sépares les phrases... Dans le code assembleur produit !

La question n'est pas aussi stupide. Je voulais te demander, au niveau
du code (représentation du binaire), ou au niveau du flux assembleur
produit (dans ton environnement) par le compilateur à destination de
l'assembleur.

Les réponses étant respectivement non et oui.
La différence étant que les informations de type sont (normalement)
rangées dans le fichier objet produit sous forme d'informations
symboliques destinées à l'éventuel débogage.

Que veut dire « tous » ?
Les types du C décrivent un ensemble infini
(peut-être même non dénombrable, [...]

Y'a des chances, vu qu'on peut mettre autant de [n] qu'on veut avec n
entier strictement positif quelconque, ça fait un beau N^N !

... qui reste un nombre. OK bon, ce n'est pas le sujet.

En fait, je voulais savoir si tu voulais faire référence à l'ensemble de
tous les types possible du langage C, dont il devrait paraître assez
évident qu'ils ne sont pas /tous/ représentés dans le flux produit (d'où
ma stupide remarque),
ou bien si tu voulais faire référence à l'ensemble des types que le
compilateur a construit au cours de l'analyse (y compris ceux qui ne
servent pas effectivement, par exemple int(*)[3][4] dans ton exemple),
auquel cas la réponse est peut-être,
ou si tu faisais référence aux types explicitement utilisés, auquel cas
je pense que la réponse devrait être oui sous réserve de la qualité du
compilateur.

Antoine

Vous avez filtré cet utilisateur ! Consultez son message

Le 15/06/2009 8:20, Lucas Levrel écrivit :

Le 11 juin 2009, Antoine Leca a écrit :
Le 11/06/2009 08:14Z, Lucas Levrel écrivit :
Ah, l'ambiguïté entre valeur et adresse d'un pointeur...

Personnellement je ne vois aucune ambiguïté.

Je parlais de l'ambiguïté du vocabulaire, pas de la notion bien sûr.
Car la valeur du pointeur est l'adresse de l'objet pointé.

Ah! Pardon, je n'avais pas vu que «d'un pointeur» qualifiait valeur.

Donc quand je demande si « table[i] existe en mémoire », je suis
trop succinct, car ça peut vouloir dire :
1) est-ce que la valeur de table[i] est une adresse qui existe
ou
2) est-ce que l'objet table[i] est stocké en mémoire

Voilà. Moi, je ne vois que la seconde forme ; la première ne me vient
pas à l'esprit. Entre autres parce qu'une expression qui a pour type
int[N] n'est pas pour moi un pointeur ou une adresse, mais un objet.

Le fait est que souvent, l'expression table[i] va devenir un pointeur ;
mais ce n'est pas systématique ; exemple, derrière sizeof, ou devant ou dans une initialisation.

Par ailleurs, le pointeur est lui-même un objet, et comme tout objet
possède son adresse propre.

C'est bien de ça que je parlais.

¿¿¿Bzzz??? Là tu m'as complètement perdu... Deux lignes plus haut tu dit
qu'il ne faut pas considérer l'adresse du pointeur (mais sa valeur, qui
est l'adresse de l'objet pointé), et quand j'en parle tu dis que c'est
bien de cela qu'il s'agit...

Serait-ce que ma formulation fut malheureuse et que je n'ai pas réussi à
bien différencier les deux adresses ? Car moi, dans la phrase ci-dessus
je voulais parler d'une *AUTRE* adresse que celle dont il est question,
l'hypothétique adresse où se trouve l'hypothétique pointeur (qui pour
moi n'existe pas, je l'appelerai virtuel).

Je crois que c'est assez clair à la
lumière de la deuxième question de mon post initial, où je parlais de
tableaux dynamiques pour lesquels on crée d'abord int *table[3], puis on
fait pointer chaque table[i] vers un int[4].

Euh... Je dois avoir loupé quelque chose...
Pour moi, un tableau dynamique ne désigne pas un tableau de pointeurs
vers des tableaux (éventuellement disjoints en mémoire, et de taille
allouées éventuellement distinctes), mais plutôt un tableau homogène
d'un seul bloc alloué dynamiquement (par malloc()).
Je me trompai, me trompé-je?

Par ailleurs, dans la formulation
int table[3][4];
il n'y a que 12 int, et pas de tableaux de pointeurs;
et il n'y a un pointeur QUE dans le contexte
int fonction_ancien_style(table)
int table[3][4];
{ /* */ }

(et je ne pense pas que tu parles de ce cas-là).

Je sais que table[i] est l'adresse d'une zone mémoire allouée,
c'est celle de la valeur table[i][0].

Pour la n-ième fois, je ne comprends pas ta notation.

table[i] == &(table[i][0])
Non ?

Oui, c'est la spécification de l'opérateur & appliqué à blabla[0] que de
pouvoir être remplacé par blabla tout court.
Mais pour moi, les deux sont des objets (tableaux de 4 int) ; qui en
plus d'une adresse ont un type, et dont la valeur sont des quadruplets.

Je dois dire que je ne pensai pas qu'il faille rajouter &.

Je suis désolé, je n'avais pas ma tête, je n'avais pas bien compris.
J'ai trop l'habitude de considérer la complexité potentielle des
expressions en C avec des pointeurs vers tableaux et les différents
niveaux d'indirection possible, je pense que je n'arrive pas à
simplifier suffisament mon propos.

Évidemment, avec ces conventions, tu ne dois pas comprendre la plupart
de mes remarques car je n'arrive pas à entrer dans ton formalisme.
Je m'en excuse.

le compilateur réserve-t-il trois zones de mémoire pour stocker table[0],
table[1] et table[2] ?

Il réserve une seule zone de 12 int. On peut ensuite voir cela comme
trois zones, mais il n'en reste pas moins que les zones sont contiguës.

Là encore, je ne parlais pas de ce sur quoi pointent les table[i], à
savoir des zones de 4 int, mais des table[i] eux-mêmes.

Ah! tu parlais des pointeurs virtuels vers les tableaux d'int!
Encore désolé de ne pas avoir compris plus tôt.

Non, le compilateur ne réserve pas de zones mémoire pour ces pointeurs,
ils restent virtuels.

(OK, dans les détails, il est possible que dans certaines expressions
complexes le compilateur soit obligé de créer des variables temporaires,
normalement en pile, pour stocker ces pointeurs lors du calcul d'une
expression plus large. Donc il y aura réservation d'espace "auto".
Mais c'est encore une fois la cuisine.)

Mais bon, cela c'est la salade interne des compilateurs, ce n'est pas
important.

C'est ce que je cherche à comprendre, par exemple quand je demande si ça
aurait un intérêt (en vitesse d'exécution) de déclarer int table[12] et de
gérer moi-même l'indexation (voir la Q2 de mon post initial).

Impossible de répondre à cette question en général.

Par exemple, imagines que tu as un algorithme sur une matrice
triangulaire avec plusieurs passes, que la matrice allouée par morceaux
(de taille croissante) tienne en mémoire centrale mais que la matrice
allouée d'un seul coup (qui est donc environ 50% plus grande) ne tienne
pas et oblige à utiliser la mémoire d'échange (swap) : dans ce cas
précis, il est facile de voir qu'une des méthode aura des performances
supérieures à l'autre.

Un autre exemple où l'allocation par morceau peut être moins efficace :
si l'allocateur mémoire fabrique des morceaux juste d'une taille
multiple d'une page, et si tu traverses la matrice dans l'autre sens : à
un instant donné tu vas donc manipuler des lignes mémoire qui ont toutes
par le même motif d'adresse xx234yy0 (par exemple), et tu peux (pouvais)
alors engorger une petite partie du TLB...
La manière habituelle d'optimiser ce genre de contrainte est d'allouer
une taille d'éléments légèrement supérieure qui ne soit pas multiple de
la taille de page, mais là cela ne va pas fonctionner à cause de
l'allocateur.

Mais bon, comme toutes les discussions sur l'optimisation, la bonne
réponse c'est qu'il ne faut pas se préoccuper des optimisations en C, et
surtout pas lors que l'on est encore à la phase de conception ou avant.
Il est généralement /beaucoup/ plus efficace et surtout rentable de
choisir de bons algorithmes (en amont) ou d'augmenter le rendement des
machines (en aval).

Par exemple, que verrait-on si on lisait le code assembleur
produit par le compilo ?

xycc -S > tes_yeux

~> xycc
bash: xycc: command not found

Pardon. En général les compilateurs C sont appelés par une commande qui
finit par cc ([machine truc] C Compiler en anglais), et ont toujours en
général une option -S qui génère un listage en assembleur.

Dans ton cas,
$ gcc -S ton_source.c | less
devrait le faire. Ce sera différent pour d'autres lecteurs de ce groupe.

Tous les types du C existent-ils ?

Où ?

Tu sépares les phrases... Dans le code assembleur produit !

La question n'est pas aussi stupide. Je voulais te demander, au niveau
du code (représentation du binaire), ou au niveau du flux assembleur
produit (dans ton environnement) par le compilateur à destination de
l'assembleur.

Les réponses étant respectivement non et oui.
La différence étant que les informations de type sont (normalement)
rangées dans le fichier objet produit sous forme d'informations
symboliques destinées à l'éventuel débogage.

Que veut dire « tous » ?
Les types du C décrivent un ensemble infini
(peut-être même non dénombrable, [...]

Y'a des chances, vu qu'on peut mettre autant de [n] qu'on veut avec n
entier strictement positif quelconque, ça fait un beau N^N !

... qui reste un nombre. OK bon, ce n'est pas le sujet.

En fait, je voulais savoir si tu voulais faire référence à l'ensemble de
tous les types possible du langage C, dont il devrait paraître assez
évident qu'ils ne sont pas /tous/ représentés dans le flux produit (d'où
ma stupide remarque),
ou bien si tu voulais faire référence à l'ensemble des types que le
compilateur a construit au cours de l'analyse (y compris ceux qui ne
servent pas effectivement, par exemple int(*)[3][4] dans ton exemple),
auquel cas la réponse est peut-être,
ou si tu faisais référence aux types explicitement utilisés, auquel cas
je pense que la réponse devrait être oui sous réserve de la qualité du
compilateur.

Antoine

Antoine Leca

15/06/2009 à 16:49

Le 15/06/2009 8:34, Lucas Levrel écrivit :

Le 11 juin 2009, candide a écrit :
Du coup, je n'ai aucun intérêt à déclarer
int table[3*4];
puis à gérer moi-même l'accès à l'élément (i,j) avec table[4*i+j].

Intérêt ? ça dépend de ce que tu veux faire. Je trouve les tableaux
multidimensionnels (les vrais, par ceux qu'on alloue dynamiquement, cf.
ton point numéro2) peu souples puisqu'il faut indiquer toutes les
dimensions sauf la dimension principale lorsque le tableau est amené à
être argument d'une fonction.

OK. Cependant, dans le fil récent « Légallité d'un pointeur de tableau »
Jean-Claude Arbaut nous a appris qu'en C99 on pouvait faire
double get(int n, int p, double t[n][p], int i, int j){return t[i][j];}

Et c'est un VLA (tableau à longueur variable) de VLA, et rien ne dit que
les perfs des VLAs sont les mêmes que celles des tableaux à taille fixe.

On doit probablement trouver des implémentations où les VLAs sont
implémentés comme des objets C++ avec méthodes virtuelles etc., et un
ordre de grandeur de performance différent.

Antoine

ld

15/06/2009 à 16:59

On 15 juin, 15:01, Antoine Leca wrote:

Le 15/06/2009 12:43, Marc Espie écrivit :

> pour sortir du denombrable, il faut une suite *infinie* d'entiers. Tant que
> tu restes dans l'arbitrairement long, mais finie, ca ne marche pas.

OK, c'est clair pour moi.

Sauf que ce qui est dit ci-dessus est faux ;-)

dénombrable veut dire qu'on peut les compter ou autrement dit, trouver
le successeur d'un élément. Ca n'a rien à voir avec le nombre
d'éléments de l'ensemble, mais avec la possibilité de les énumére r
(discret vs continu).

une suite infinie d'entiers est donc dénombrable.
N, Z, D, Q sont dénombrables, R et C ne le sont pas.

On peut revenir au sujet ?

volontier ;-)

a+, ld.

ld

15/06/2009 à 17:35

On 15 juin, 15:12, Marc Boyer
wrote:

On 2009-06-15, Marc Espie wrote:

> In article <h0qqis$,
> Antoine Leca wrote:
>>Que veut dire Â« tous Â» ? Les types du C dÃ©crivent un ens emble infini
>>(peut-Ãªtre mÃªme non dÃ©nombrable, mais cela fait trop lon gtemps que ce
>>sujet ne me prÃ©occupe plus pour que je ne sois pas 100% sÃ»r).

> N'importe quoi.

> Le C est un langage, les types du C ont une expression, sous forme de c haine
> de caracteres explicitant le type. Ils sont donc forcement denombrables ...

yep

Disons qu'il faut arriver à exprimer un infini non dénombrable ave c
un nombre fini de symbole, et c'est pas évident à faire avec
une sémantique raisonnable.

Sans aller chercher bien, loin, le lambda calcul le permet parce
qu'une fonction peut se renvoyer elle-même. Par exemple x.xx ne peut
pas être type parce qu'il ne peut pas être réduit (expansion infinie) .

> Oui, il y a des trucs marrants en theorie des types. Mais il faut du ty page
> automatique pour sortir des trucs exprimables par le systeme de types.. . et
> c'est bien le souci, en general.

Voui, avec des constructeurs universels et existentiels, et
un petit point fixe, on doit pouvoir jouer...
M'enfin, on doit être loi du C...

Si c'est typé, ça devrait être dénombrable.

a+, ld.

espie

15/06/2009 à 17:50

In article ,
ld wrote:

On 15 juin, 15:01, Antoine Leca wrote:
Le 15/06/2009 12:43, Marc Espie écrivit :

> pour sortir du denombrable, il faut une suite *infinie* d'entiers. Tant que
> tu restes dans l'arbitrairement long, mais finie, ca ne marche pas.

OK, c'est clair pour moi.

Sauf que ce qui est dit ci-dessus est faux ;-)

dénombrable veut dire qu'on peut les compter ou autrement dit, trouver
le successeur d'un élément. Ca n'a rien à voir avec le nombre
d'éléments de l'ensemble, mais avec la possibilité de les énumérer
(discret vs continu).

Non, ce qui est dit est juste, tu l'as juste sorti de son contexte, et
forcement quand tu prends juste un fragment, ca ne veut plus rien dire.

La notion de denombrabilite n'a rien a voir avec l'idee de discret vs
continu. Je te fabrique quand je veux des ensembles non denombrables
en utilisant des nombres entiers (par exemple, l'ensemble des parties
de N, tiens...)

une suite infinie d'entiers est donc dénombrable.
N, Z, D, Q sont dénombrables, R et C ne le sont pas.

On peut revenir au sujet ?

volontier ;-)

Avec plaisir aussi, mais j'y reviendrai sans hesiter des que je verrais des
enormes conneries. ;-)

Tableaux multidimensionnels et déréférencement

10 réponses

Veuillez sélectionner un problème