Tableaux multidimensionnels et déréférencement

Le 10/06/2009 10:26Z, Lucas Levrel écrivit :

1) Si je déclare
int table[3][4];
table est de type int(*)[4],

Non, cf. <news:h095mb$dsi$1@shakotay.alphanet.ch>.

et table[i] est de type int[4].

Oui.

Confirmez-vous que néanmoins table[i] n'existe pas en mémoire,

Oui si i==3; non dans tous les autres cas : l'objet existe pour i valant
0,1 et 2, et l'expression n'a pas de sens pour les autres valeurs de i.

et que le
compilateur ne crée qu'un genre de int *t qui pointe vers table[0][0],
puis remplacera table[i] par t+4*i ? (D'où l'obligation que toutes les
dimensions sauf la première soient connues à la compilation.)

C'est confus parce que tu mélanges pointeurs et tableaux, mais c'est à
peu près cela.
t est (d'après ta description) un pointeur, que le compilateur peut
effectivement synthétiser avec l'adresse de table (qui est aussi celle
de table[0][0], mais les deux expressions n'ont pas le même type);
s'il y a des opérations à faire sur table[i], tout particulièrement des
appels de fonctions, le compilateur peut utiliser t+4*i comme valeur de
pointeur pour le remplacer.
Et oui c'est bien cela qui justifie techniquement la nécessité de
déclarer les dimensions.

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

Euh, là c'est toi qui voit.


Antoine

Bonjour,

Merci pour la réponse.

Le 10 juin 2009, Antoine Leca a écrit :

> 1) Si je déclare
> int table[3][4];

> Confirmez-vous que néanmoins table[i] n'existe pas en mémoire,

Oui si i==3; non dans tous les autres cas : l'objet existe pour i valant
0,1 et 2, et l'expression n'a pas de sens pour les autres valeurs de i.

Ah, l'ambiguïté entre valeur et adresse d'un pointeur... Je sais que
table[i] est l'adresse d'une zone mémoire allouée, c'est celle de la
valeur table[i][0]. Ce que je demande, c'est si la valeur table[i] est
stockée quelque part en mémoire. Autrement dit, quand je déclare
int table[3][4];
le compilateur réserve-t-il trois zones de mémoire pour stocker table[0],
table[1] et table[2] ? Je crois que non, qu'il les calcule uniquement
lorsque je les utilise, à partir de table, i et 4, selon la formule
table+4*i. J'ai bon ?

> et que le
> compilateur ne crée qu'un genre de int *t qui pointe vers table[0][0],
> puis remplacera table[i] par t+4*i ? (D'où l'obligation que toutes les
> dimensions sauf la première soient connues à la compilation.)

C'est confus parce que tu mélanges pointeurs et tableaux, mais c'est à
peu près cela.

En fait, je cherche à savoir ce qui se passe au niveau machine, après
compilation. Par exemple, que verrait-on si on lisait le code assembleur
produit par le compilo ? Tous les types du C existent-ils ?

--
LL

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

Le 10 juin 2009, Antoine Leca a écrit :

1) Si je déclare
int table[3][4];
Confirmez-vous que néanmoins table[i] n'existe pas en mémoire,

Oui si i==3; non dans tous les autres cas : l'objet existe pour i valant
0,1 et 2, et l'expression n'a pas de sens pour les autres valeurs de i.

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

???
Personnellement je ne vois aucune ambiguïté.
Le propos d'un pointeur (quand il est valide) est de désigner un objet ;
on dit aussi (surtout en anglais) "to reference". Si un objet est décrit
par un type et une adresse d'instance, le pointeur doit donc posséder
ces informations.
En C, la valeur d'un pointeur --qui est par ailleurs accessible-- est
conventionnellement l'adresse de l'objet ; tandis que le type de l'objet
pointé est décrit à travers du type du pointeur, type qui est
pratiquement figé à la compilation.

Par ailleurs, le pointeur est lui-même un objet, et comme tout objet
possède son adresse propre.
Mais les deux choses n'ont absolument rien à voir entre elles.

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][j] est un entier (dans ton exemple), il a une valeur qui a sa
vie propre indépendamment des mécanismes de pointeurs.

L'adresse de la zone mémoire peut se récupérer grâce à l'opérateur &,
par exemple en écrivant &table[i][0] ou &table[i]; ces deux expresssions
sont de type pointeur (vers des types différents), les deux ont la même
valeur si on les convertit dans des types compatibles comme par exemple
void*:
if( (void*)&table[i][0] != (void*)&table[i] )
ceci n'est plus du C...;

Et dans la pratique, (la plupart) des compilateurs implémentent ceci en
utilisant la même valeur numérique pour les deux expressions.

Donc pour essayer de comprendre, je rajouterais des &

Ce que je demande, c'est si la valeur table[i] est

Ce que je demande, c'est si la valeur &table[i] est

stockée quelque part en mémoire.

Non.
Si le compilateur optimise comme un malade et arrive à déduire en
fonction du contexte la valeur de i, par exemple s'il déroule une
boucle, il peut éventuellement utiliser la valeur devenue constante et
alors, en fonction des circonstances, cette valeur pourrait apparaître
en mémoire. Mais ce sont des cas très particuliers.

int table[3][4];
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.

Je crois que non, qu'il les calcule uniquement

lorsque je les utilise, à partir de table, i et 4, selon la formule
table+4*i. J'ai bon ?

Pas tout-à-fait (dans le cas général) : quand le compilateur est au
niveau des adresses, il n'a que faire des limites des int et s'intéresse
normalement aux adresses des objets, qui sont d'habitude celles des bytes.
Donc la formule devient table+sizeof(int)*4*i

Et le plus souvent, le calcul sizeof(int)*4 est déjà rangé quelque part
(dans un type int[4] anonyme qui sert en interne au compilateur), donc
la formule utilisée est plutôt table+sizeof(table[0])*i
qui a le bon goût d'être la formule générale pour tous les tableaux,
c'est-à-dire que le « 4 » a disparu.
Mais bon, cela c'est la salade interne des compilateurs, ce n'est pas
important.

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

xycc -S > tes_yeux

Tous les types du C existent-ils ?

Où ?
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).

Relis aussi ce que j'ai écrit au début : en C les types sont
essentiellement un truc du compilateur, il n'y en quasiment plus de
trace dans le binaire produit.


Antoine

Lucas Levrel a écrit :

Confirmez-vous que néanmoins table[i] n'existe pas en mémoire, et que le
compilateur ne crée qu'un genre de int *t qui pointe vers table[0][0],
puis remplacera table[i] par t+4*i ?

C'est grosso modo ce que dit la Norme dans un exemple :


EXAMPLE Consider the array object defined by the declaration int x[3][5]; Here x
is a 3 × 5 array of ints; more precisely, x is an array of three element
objects, each of which is an array of five ints. In the expression x[i], which is
equivalent to (*((x)+(i))), x is first converted to a pointer to the initial
array of five ints. Then i is adjusted according to the type of x, which
conceptually entails multiplying i by the size of the object to which the
pointer points, namely an array of five int objects. The results are added and
indirection is applied to yield an array of five ints. When used in the
expression x[i][j], that array is in turn converted to a pointer to the first of
the ints, so x[i][j] yields an int.

(D'où l'obligation que toutes les
dimensions sauf la première soient connues à la compilation.)
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. Donc dans ton exemple ci-dessus, une telle fonction pourrait avoir le
prototype suivant :


void f(int tab[][4], int nbEl_tab)

alors qu'il n'est pas rare qu'on ait besoin d'un code plus souple (qui puisse
traiter de tableau de taille quelconque mais bornée à la compilation, imaginer
par exemple un code de Sudoku 3x3, 4x4 ou 5x5) auquel cas on déclare une
fonction prenant en paramètres
*) un tableau unidimensionnel qui va simuler un tableau 2D
*) les deux dimensons du tableau simulé,

donc quelque chose du genre

void g(int t[], int n, int p).

l'accès à un élément (i,j) du tableau se faisant par le genre de formule que tu
as indiquée.

En même temps, j'ai bien conscience que ce que je dis là n'est pas exactement ta
préoccupation, tu sembles visiblement vouloir comparer les coûts respectifs
effectués par différents type d'allocation de tableaux

Antoine Leca a écrit :

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

xycc -S > tes_yeux

Tous les types du C existent-ils ?

Où ?
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).

Je pense que ce qu'il veut dire c'est de savoir comment les types du C (de base,
ou pas) sont interprétés dans le code assembleur (qui lui ne reconnait pas
forcément les même types). En tous cas, je sais que je me suis posé ce genre de
question ou approchant, par exemple comment une bibliothèque qui n'a pas été
écrite en C peut dialoguer avec du code C, en particulier au moment de l'édition
de liens, plus précisément comment du code C peut appeler une fonction (donc
avec une syntaxe C) "externe" dans une bibliothèque par exemple qui elle a été
écrite dans un tout autre langage.

Relis aussi ce que j'ai écrit au début : en C les types sont
essentiellement un truc du compilateur, il n'y en quasiment plus de
trace dans le binaire produit.

Ah, OK. Ce qui répond donc en partie à la question précédente.

Le 11/06/2009 13:11, candide écrivit :

comment les types du C (de base,
ou pas) sont interprétés dans le code assembleur (qui lui ne reconnait pas
forcément les même types).

Pour les types composés (structure, tableaux etc.), le langage donne
suffisamment de contraintes pour que, pour une architecture cible
donnée, il n'y a pas beaucoup de degrés de liberté. Et quand il y en a,
l'on entre souvent dans le domaine des choses « définies par
l'implémentation », donc qu'il faut éviter lorsqu'on souhaite écrire du
code portable et réutilisable : c'est en particulier le cas pour les
alignements au sein des structures, ou pour les champs de bits.

Pour les types de base, la première partie « dépendante de
l'architecture » du compilateur consiste justement à réaliser une
projection de l'ensemble des types tels que décrits par le langage, vers
un autre ensemble qui tient compte des contraintes de la machine et qui
inclut de plus d'autres informations comme les dimensions des objets (y
compris précision et étendue pour les flottants), ou les UAL, réelles ou
émulées, qui devront être mises en œuvre.

Exemple le plus évident, la plupart des machines n'ont pas les
opérations sur les nombres complexes déjà cablées, donc le compilateur
doit émuler ces opérations et inventer une structure pour stocker les
nombres (l'effort n'est pas grand, mais c'est quand même pas une bijection).

Autre exemple, bien peu de machines ont des jeux d'opérations
complètement différenciés pour les nombres signés et les non signés, et
en général au niveau de l'assembleur il y a confusion des deux types, et
une opération d'affectation pour des signed sera exactement identique à
une opération d'affectation pour des unsigned.

En tous cas, je sais que je me suis posé ce genre de
question ou approchant, par exemple comment une bibliothèque qui n'a pas été
écrite en C peut dialoguer avec du code C, en particulier au moment de l'édition
de liens, plus précisément comment du code C peut appeler une fonction (donc
avec une syntaxe C) "externe" dans une bibliothèque par exemple qui elle a été
écrite dans un tout autre langage.

C'est tout le propos de ce que l'on appelle « l'interface binaire
applicative » (ABI).
Qui n'est pas particulièrement lié au langage C, et a tout à voir avec
les caractéristiques de l'architecture cible. Ainsi, bien que beaucoup
de choses soient similaires voire identiques entre x86-32 et x86-64, les
ABI sont très différentes et non miscibles, tandis que les sources C,
même (ou surtout) pour les aspects très liés au matériel, sont souvent
identiques.


Antoine

Hello,

Bon, je crois que l'essentiel a été tiré au clair par candide, qui a su
interpréter les approximations de mon vocabulaire d'utilisateur formé sur
le tas avec le K&R... Ci-dessous je vais reformuler mes interrogations
pour voir si j'ai bien compris :-) Merci à Antoine pour ses lumières.

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

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

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

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

> Je crois que non, qu'il les calcule uniquement
> lorsque je les utilise, à partir de table, i et 4, selon la formule
> table+4*i. J'ai bon ?

Pas tout-à-fait (dans le cas général) : quand le compilateur est au
niveau des adresses, il n'a que faire des limites des int et s'intéresse
normalement aux adresses des objets, qui sont d'habitude celles des bytes.
Donc la formule devient table+sizeof(int)*4*i

OK, c'est ce à quoi je pensais mais je ne l'ai écrit qu'en arithmétique de
pointeur.

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

> 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

:-p

> Tous les types du C existent-ils ?

Où ?

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

Que veut dire « tous » ?

http://atilf.atilf.fr/dendien/scripts/tlfiv4/showps.exe?p=combi.htm;java=no;

Re- :-p

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

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 !

Merci encore.

--
LL

Le 11 juin 2009, candide a écrit :

EXAMPLE Consider the array object defined by the declaration int
x[3][5]; Here x is a 3 × 5 array of ints; more precisely, x is an array
of three element objects, each of which is an array of five ints. In the
expression x[i], which is equivalent to (*((x)+(i))), x is first
converted to a pointer to the initial array of five ints.

Cool, je n'avais pas tout faux !

> 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];}

En même temps, j'ai bien conscience que ce que je dis là n'est pas
exactement ta préoccupation, tu sembles visiblement vouloir comparer les
coûts respectifs effectués par différents type d'allocation de tableaux

Oui. Ta réponse est néanmoins intéressante, car je n'ai pas forcément vu
tous les inconvénients de chaque approche !

--
LL

On 2009-06-15, Lucas Levrel <lucas.levrel@univ-paris12.fr> wrote:

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

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 !

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.
Et il va être difficile d'écrire le code qui décrit un tableau
avec une infinité de dimensions.

Alors après, si on commence à regarder les types décris par
des termes infinis, pourquoi pas, mais ça me semble un peu
exagéré.

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

In article <h0qqis$tcl$1@shakotay.alphanet.ch>,
Antoine Leca <root@localhost.invalid> 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...

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.