Du bon usage de const et des typedef...

Marc Boyer wrote:

J'ai des interrogations de style sur les signatures de fonctions
associées aux types utilisateurs, surtout question de style, pas
vitales, mais bon...

Prenons un type Pile, pile d'entiers.

Je vois 4 familles de définition de ce type

aucune ne me plait :-)

A) struct avec taille+tableau dynamique
typedef struct {
int* tab;
size_t capacite, taille;
} Pile;
B) Ptr sur 1ere element d'une liste chainee
struct cel {
struct cel* next;
int i;
};
typedef struct cel * Pile;
C) TAD pur
typedef Pile; // dans le .h

attention, tu peux avoir des surprises avec ca. Pile n'est pas un ADT
mais in int (avec un joli warning du compilo)!

typdedef struct Pile Pile;

serait mieux.

// version A ou B dans le .c
D) Tableau de taille fixe (pile bornée + délimiteur de fin)
typedef int Pile[CAPA+1];

pas beau.

si tu veux minimiser les malloc, je suggere

struct Pile {
size_t size, capacity;
int stack[1];
};

dans le .c mais ca a le deavantage de devoir avoir des signatures du type:

Pile* pile_push(Pile* pile, int elem);

et de ne pas oublier de reassigner le pointeur sur pile.

Ou d'integrer le type pointeur dans le typedef et avoir

typedef struct Pile *Pile;

Pile* pile_push(Pile* pile, int elem);

mais ca implique une indirection de plus dans le .c.

Donc supposons que minimiser les malloc n'est pas ta principale
preoccupation, j'utiliserais.

typdedef struct Pile Pile;

dans le .h

et

struct Pile {
size_t size, capacity;
int *stack;
};

dans le .c.

L'utilisation d'un tableau de taille fixe me parait pas une bonne idee.

Quelles signatures donner aux fonctions qui la manipulent ? Pour
alimenter la discution, prenons simplement initialisation et taille.

Moi, ma tendance serait:

A+B+D: // struct, pointeur et tableau
bool initPile(Pile* p);
size_t sizePile(const Pile p);

C: // TAD
Pile* newPile(void);
size_t sizePile(const Pile *p);

Je prefere ca de loin C. Avec cependant un nommage different

Pile* pile_new(size_t initSize);
size_t pile_size(const Pile *p);

Mais (et c'est là que commencent mes interrogations):

Dans A et B (struct et pointeur), le const de size est superflux: de
toute façon on a une copie, c'est pas plus pertinent que
foo(const int);

yep

En plus, pour A, j'entends déjà les critiques de perfs parce que
je passe une structure en paramètre, et que ça va pénaliser les perfs
là où
sizePile(const Pile* p)
aurait été bien meilleur (mais plus mauvais pour B puisqu'on
rajouterais une indirection supplémentaire)

Passer des structures par valeur signifie adopter une semantique par
valeur partout, ce qu'il faut eviter, pas seulement pour des raisons de
perfs.

Sauf si les compilateurs savent remplacer les appels du genre
foo(const T) en foo(const T*) s'ils pensent que ce sera plus
rapide (inline ou cout indirection negligeable par rapport au
gain en copie).

Il ne peut pas s'il ne connait pas au minimum la definition de la
fonction (ex: appel recursif). Je ne crois pas qu'aucun compilateur ne
se risquerait a changer une semantique par valeur par une semantique par
reference.

Dans D (tableau), c'est initPile qui rajoute une indirection inutile.

Il n'y a que pour le TAD que c'est simple: comme on a décidé par
design de payer une indirection à chaque fois, tout est simple
ensuite.

Cette indirection ne coute rien. Pourquoi se compliquer la vie?

Des idées, des commentaires, vos pratiques ?

Voila.

Mais comme tu le sais, j'utilise OOC (pas du tout la version que tu as,
on a beaucoup simplifie depuis) ou je ne pratique l'ADT que pour les
classes "final" a cause de la derivation (on ne peut pas deriver d'un
ADT :-). Pour les methodes, elles sont de toutes facon encapsulees dans
la classe et les signatures sont plutot du type

Pile_t* new(struct Pile*, size_t initSize);
size_t size(Pile_t*);

ou Pile_t est le type des instances, struct Pile le type de la classe et
struct Pile_ le type de la metaclasse, mais normalement l'utilisateur
n'utilise jamais les deux derniers types. A noter que new est une
methode de classe, tandis que size est une methode d'instance.

a+, ld.

Dans A et B (struct et pointeur), le const de size est superflux: de
toute façon on a une copie, c'est pas plus pertinent que
foo(const int);
En plus, pour A, j'entends déjà les critiques de perfs parce que
je passe une structure en paramètre, et que ça va pénaliser les perfs
là où
sizePile(const Pile* p)
aurait été bien meilleur (mais plus mauvais pour B puisqu'on
rajouterais une indirection supplémentaire)

je m'étais également interrogé par ce const inutile et que je ne
savais où placer, donc je n'en ai pas dit. Ceci dit, je n'ai toujours
pas la réponse.

Sauf si les compilateurs savent remplacer les appels du genre
foo(const T) en foo(const T*) s'ils pensent que ce sera plus
rapide (inline ou cout indirection negligeable par rapport au
gain en copie).

oulà ! malheureux ! et le respect de l'ABI ?!? on en a pendu pour moins
que ça.

Des idées, des commentaires, vos pratiques ?

pour l'instant, dans le cas que tu décris (structure de donnée complexe
différente de char *), je ne mets rien, en attendant de voir la suite du
thread et ce que disent les vrais experts qui nous montreront leur
virilité.

--
DINH V. Hoa,

"Quel dieu cet homme !" -- FiLH

Laurent Deniau wrote:

Mais comme tu le sais, j'utilise OOC (pas du tout la version que tu as,
on a beaucoup simplifie depuis) ou je ne pratique l'ADT que pour les
classes "final" a cause de la derivation (on ne peut pas deriver d'un
ADT :-). Pour les methodes, elles sont de toutes facon encapsulees dans
la classe et les signatures sont plutot du type

Pile_t* new(struct Pile*, size_t initSize);
size_t size(Pile_t*);

Vu que la discussion est sur les const, je rectifie mon oubli (les
methodes ne sont pas declaree comme cela d'ou mon etourderie):

Pile_t* new(const struct Pile*, size_t initSize);
size_t size(const Pile_t*);

voila ce que j'utiliserais.

a+, ld.

In article <c6anl2$gt8$1@sunnews.cern.ch>, Laurent Deniau wrote:

C) TAD pur
typedef Pile; // dans le .h

attention, tu peux avoir des surprises avec ca. Pile n'est pas un ADT
mais in int (avec un joli warning du compilo)!

typdedef struct Pile Pile;

Oui, c'est bien sur ce a quoi je pensais...
Merci d'avoir corrigé l'erreur.

serait mieux.

// version A ou B dans le .c
D) Tableau de taille fixe (pile bornée + délimiteur de fin)
typedef int Pile[CAPA+1];

pas beau.

Dans ce cas là, c'est clairement une mauvaise idée, mais
comme le passage des tableaux est different des autres types,
je voulais inclure le cas (quitte a faire pas trop realiste).
Ceci dit, assez bas dans l'archi, on m'a parlé de petites
piles de taille fixe.

si tu veux minimiser les malloc, je suggere
struct Pile {
size_t size, capacity;
int stack[1];
};

dans le .c mais ca a le deavantage de devoir avoir des signatures du type:

Pile* pile_push(Pile* pile, int elem);

et de ne pas oublier de reassigner le pointeur sur pile.

Ca me semble un bon moyen de se facher avec les utilisateurs,
non ?

Ou d'integrer le type pointeur dans le typedef et avoir

typedef struct Pile *Pile;

Pile* pile_push(Pile* pile, int elem);

mais ca implique une indirection de plus dans le .c.

Donc supposons que minimiser les malloc n'est pas ta principale
preoccupation, j'utiliserais.

Surtout que ca n'économise un malloc qu'a chaque creation de pile,
je sais pas si c'est le pire.

typdedef struct Pile Pile;

dans le .h

et

struct Pile {
size_t size, capacity;
int *stack;
};

dans le .c.

Oui, c'est le TAD avec implementation A.

Je prefere ca de loin C. Avec cependant un nommage different

Pile* pile_new(size_t initSize);
size_t pile_size(const Pile *p);

Oui, je note le prefixage contre le postfixage...
Des raisons ?

Passer des structures par valeur signifie adopter une semantique par
valeur partout, ce qu'il faut eviter, pas seulement pour des raisons de
perfs.

Tu penses que l'utilisateur sera trop destabilisé si autre chose
qu'un pointeur n'a pas de sémantique de valeur ?

Il ne peut pas s'il ne connait pas au minimum la definition de la
fonction (ex: appel recursif). Je ne crois pas qu'aucun compilateur ne
se risquerait a changer une semantique par valeur par une semantique par
reference.

Oui, avec le probleme de la compilation separee, ce ne serait
envisageable qu'avec un static inline.

Il n'y a que pour le TAD que c'est simple: comme on a décidé par
design de payer une indirection à chaque fois, tout est simple
ensuite.

Cette indirection ne coute rien. Pourquoi se compliquer la vie?

Comment ca elle coute rien ?

Marc Boyer
--
La contractualisation de la recherche, c'est me donner de l'argent pour
faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce
que je sais faire, je le fais sans moyens...

En etPan.4088e24d.312be56a.b94@homer, DINH Viêt Hoà va escriure:

Sauf si les compilateurs savent remplacer les appels du genre
foo(const T) en foo(const T*) s'ils pensent que ce sera plus
rapide (inline ou cout indirection negligeable par rapport au
gain en copie).

oulà ! malheureux ! et le respect de l'ABI ?!? on en a pendu pour
moins que ça.

Mmmmh. Cela peut justement *être* l'ABI: les structures ne sont pas passées
par valeur, mais toujours par référence. Si la structure est modifiée dans
la fonction appelée, celle-ci est priée d'en faire une copie locale.

Et bien sûr, si la fonction appelée modifie en direct, on pend !


Antoine

"Antoine Leca" <root@localhost.gov> writes:

En etPan.4088e24d.312be56a.b94@homer, DINH Viêt Hoà va escriure:

Sauf si les compilateurs savent remplacer les appels du genre
foo(const T) en foo(const T*) s'ils pensent que ce sera plus
rapide (inline ou cout indirection negligeable par rapport au
gain en copie).

oulà ! malheureux ! et le respect de l'ABI ?!? on en a pendu pour
moins que ça.

Mmmmh. Cela peut justement *être* l'ABI: les structures ne sont pas passées
par valeur, mais toujours par référence. Si la structure est modifiée dans
la fonction appelée, celle-ci est priée d'en faire une copie locale.

Pas uniquement si, toujours a cause de la possibilite d'alias.

A+

--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Marc Boyer wrote:

In article <c6anl2$gt8$1@sunnews.cern.ch>, Laurent Deniau wrote:

Ou d'integrer le type pointeur dans le typedef et avoir

typedef struct Pile *Pile;

Pile* pile_push(Pile* pile, int elem);

mais ca implique une indirection de plus dans le .c.

Donc supposons que minimiser les malloc n'est pas ta principale
preoccupation, j'utiliserais.

Surtout que ca n'économise un malloc qu'a chaque creation de pile,
je sais pas si c'est le pire.

c'est vrai, mais ca peut dans certain cas etre significatif (ex: les
strings).

typdedef struct Pile Pile;

dans le .h

et

struct Pile {
size_t size, capacity;
int *stack;
};

dans le .c.

Oui, c'est le TAD avec implementation A.

Je prefere ca de loin C. Avec cependant un nommage different

Pile* pile_new(size_t initSize);
size_t pile_size(const Pile *p);

Oui, je note le prefixage contre le postfixage...
Des raisons ?

Question de gout. J'utilise name_ pour creer un espace de nom (une
classe, un module) quand je n'utilise pas OOC. Et j'utilise la
concatenation pour les mots. Par ex:

bool pile_estVide(const Pile*);

me parait simple et lisible.

Passer des structures par valeur signifie adopter une semantique par
valeur partout, ce qu'il faut eviter, pas seulement pour des raisons de
perfs.

Tu penses que l'utilisateur sera trop destabilisé si autre chose
qu'un pointeur n'a pas de sémantique de valeur ?

Je pense que c'est adapte dans certain cas, mais rare. Pour ma part elle
est souvent dictee plutot par une semantique de retour par valeur
combinee avec la volonte de pouvoir cascader les appels. Ex:

complex z = cpx_add(cpx_mul(z1,z2),z3);

dans ce cas, le passage doit etre par valeur.

Il n'y a que pour le TAD que c'est simple: comme on a décidé par
design de payer une indirection à chaque fois, tout est simple
ensuite.

Yep. Un TAD n'est pas seulement une protection/encapsulation, ca
simplifie aussi le design et les interfaces (plus d'inline, ouf).

Cette indirection ne coute rien. Pourquoi se compliquer la vie?

Comment ca elle coute rien ?

p->stack[n] a la meme rapidite que stack soit un tableau ou un pointeur
sur la pluspart des architectures modernes. Surtout depuis que les
languages objets se sont repandus. J'ai mesure des variations de +-5%
suivant les archis et les compilos. Completement negligeable en
comparaison de tes structures passees par valeur!

a+, ld.

Laurent Deniau wrote:

Marc Boyer wrote:

Surtout que ca n'économise un malloc qu'a chaque creation de pile,
je sais pas si c'est le pire.

c'est vrai, mais ca peut dans certain cas etre significatif (ex: les
strings).

Tout a fait.

Oui, je note le prefixage contre le postfixage...
Des raisons ?

Question de gout. J'utilise name_ pour creer un espace de nom (une
classe, un module) quand je n'utilise pas OOC. Et j'utilise la
concatenation pour les mots. Par ex:

bool pile_estVide(const Pile*);

me parait simple et lisible.

En y regardant a nouveau, oui, pourquoi pas...
En fait, ca m'interesse car j'ai le choix a faire dans
la BPL, et je sens que c'est le genre de détail qui peut
contribuer au succes ou à l'échec.

Je pense que c'est adapte dans certain cas, mais rare. Pour ma part elle
est souvent dictee plutot par une semantique de retour par valeur
combinee avec la volonte de pouvoir cascader les appels. Ex:

complex z = cpx_add(cpx_mul(z1,z2),z3);

Pas super genant dans ton cas en fait si on imagine que tes
fonctions ne modifient pas leurs parametres.
Mais je prends bonne note de la liaison "semantique par
valeur <-> appels en cascade" a etudier de pret.

Il n'y a que pour le TAD que c'est simple: comme on a décidé par
design de payer une indirection à chaque fois, tout est simple
ensuite.

Yep. Un TAD n'est pas seulement une protection/encapsulation, ca
simplifie aussi le design et les interfaces (plus d'inline, ouf).

Mais les programmeurs C ne vont-il pas etre reticents à
payer un appel de fonction pour des choses comme l'acces
à la taille ?

Cette indirection ne coute rien. Pourquoi se compliquer la vie?

Comment ca elle coute rien ?

p->stack[n] a la meme rapidite que stack soit un tableau ou un pointeur
sur la pluspart des architectures modernes. Surtout depuis que les
languages objets se sont repandus. J'ai mesure des variations de +-5%
suivant les archis et les compilos. Completement negligeable en
comparaison de tes structures passees par valeur!

Je suis positivement étonné. Je prends note.

Marc Boyer
--
La contractualisation de la recherche, c'est me donner de l'argent pour
faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce
que je sais faire, je le fais sans moyens...

Marc Boyer wrote:

Laurent Deniau wrote:

Il n'y a que pour le TAD que c'est simple: comme on a décidé par
design de payer une indirection à chaque fois, tout est simple
ensuite.

Yep. Un TAD n'est pas seulement une protection/encapsulation, ca
simplifie aussi le design et les interfaces (plus d'inline, ouf).

Mais les programmeurs C ne vont-il pas etre reticents à
payer un appel de fonction pour des choses comme l'acces
à la taille ?

Je ne connais pas de cas en C ou l'appel de fonction est trop couteux si
on programme correctement (ex: eviter les while(n++ < strlen(s)){} ).

Apres avoir ete dans l'exces avec les inline (la version de OOC que tu
as en est un bon exemple), j'ai tout vire.

Sur mon portable Pentium-M a 1.5 Ghz, je peux faire environs 175000000
d'appels de fonction par seconde avec deux pointeurs en argument, un
retour de pointeur plus une bete incrementation de conteur dedans (d'une
valeur pointee). Cette architecture n'est pas specialement rapide.

Alors de mon point de vue, la bonne question est quelle est l'algorithme
qui ne sera pas domine par les mouvements memoire (ex: cache) et qui
aurait besoin d'etre plus rapide? S'il existe (??), on peut le specialiser.

Pour moi les inlines on un sens dans tres tres peu de cas, sauf en C++
ou ils sont indispensable avec les templates.

Cette indirection ne coute rien. Pourquoi se compliquer la vie?

Comment ca elle coute rien ?

p->stack[n] a la meme rapidite que stack soit un tableau ou un pointeur
sur la pluspart des architectures modernes. Surtout depuis que les
languages objets se sont repandus. J'ai mesure des variations de +-5%
suivant les archis et les compilos. Completement negligeable en
comparaison de tes structures passees par valeur!

Je suis positivement étonné. Je prends note.

Real-ity is simple until you make it complex.

Je sais plus de qui s'est ni si c'est la phrase exacte, mais l'idee y
est :-)

a+, ld.

En pxbsmevgcqo.fsf@news.bourguet.org, Jean-Marc Bourguet va escriure:

"Antoine Leca" <root@localhost.gov> writes:

Mmmmh. Cela peut justement *être* l'ABI: les structures ne sont pas
passées par valeur, mais toujours par référence. Si la structure est
modifiée dans la fonction appelée, celle-ci est priée d'en faire une
copie locale.

Pas uniquement si, toujours a cause de la possibilite d'alias.

À quoi penses-tu ?


Soit
void f(struct bidule);
void g(struct bidule *);
void h(struct bidule const *);
void k(struct bidule, struct bidule);
struct bidule n(struct bidule);
struct bidule x;
struct bidule const y;

Côté appelant:

Écrit:
f(y);
g(&x); /* &y serait refusé ici */
h(&x);
k(x,y);
k(x,x);
f(n(y));

Transformé, sans que l'on sâche, en
void f@(struct bidule *);
void k@(struct bidule *, struct bidule *);
void n@(struct bidule * resultat, struct bidule * arg);

f@(&y); /* on passe ici un pointeur sur une constante,
mais elle ne sera pas modifiée */
g(&x);
h(&x);
k@(&x, &y);
k@(&x, &x); /* alias, on va voir ce que l'on va voir! */
struct bidule temp;
n@(&temp, &y);
f@(&temp);


Côté appelé; k() est le cas le plus intéressant:
void k(struct bidule a, struct bidule b) {

g(&a);
f(a);
h(&b);
a = n(a);
}

sera transformé en:
void k@(struct bidule *a, struct bidule *b) {

struct bidule temp_a = *a; /* copie locale */
g(&temp_a); /* peut être modifié par g() */
f(&temp_a);
h(b); /* ne peut être modifié par h(); même si c'est un alias,
pas de pépin, l'original n'a pas été modifié ci-dessus */
n(&temp_a, &temp_a);
}



En fait, c'est très similaire à ce que fait (faisait) la déclaration
register pour un paramètre.


Antoine