Schéma d'allocation mémoire pour une matrice

**Thierry Chappuis** · 30/04/2011, 16h46

Dans un autre fils, j'ai posé un code proposant un schéma d'allocation de mémoire pour un type abstrait de donnée Matrix qui a suscité le débat sur le plan du respect des contraintes d'alignement (Version 3 ci-dessous). Je crée ici une nouvelle discussion pour ne pas polluer le thread initial. Si la version 1 du code ci-dessous est celle généralement proposée, la version 2 est probablement plus facile à gérer par un débutant (moins d'allocation, gestion des erreurs allégée). Du point de vue de la performance, pour des grosse matrices, y a-t-il un avantage à allouer la mémoire pour chaque ligne de la matrice comme dans la version 1, par rapport à une allocation en masse comme dans la version 2 (p.ex. moins de swap)? Ou inversemment?

Les trois versions proposées sont:

Version 1: (nlines + 2) allocations de mémoire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
struct Matrix
{
    double **_data;
    size_t dim[2];
};
#define MATRIX_INIT {NULL, {0}}
 
struct Matrix *m_matrix_new(size_t nlines, size_t ncols)
{
    struct Matrix *self = NULL;
 
    if (nlines > 0 && ncols > 0)
    {
        /* Hop, on change les habitudes et on alloue tout en un bloc */
        self = malloc(sizeof *self);
        if (self != NULL)
        {
            static const struct Matrix tmp = MATRIX_INIT;
            /* Initialisation de tous les champs de la structure a une valeur
               nulle */
            *self = tmp;
 
            self->dim[0] = nlines;
            self->dim[1] = ncols;
 
            self->_data = malloc(nlines * sizeof *self->_data);
            if (self->_data != NULL)
            {
                size_t i;
                size_t j;
                int err = 0;
 
                for (i = 0; i < nlines && err == 0; i++)
                {
                    self->_data[i] = malloc(ncols *sizeof *self->_data[i]);
                    if (self->_data[i] == NULL)
                    {
                        /* Echec d'allocation: on fait le menage, on sort de
                           la boucle et on renvoit la valeur NULL */
                        do
                        {
                            i--;
                            free(self->_data[i]);
                        }
                        while (i > 0);
 
                        free(self->_data);
                        free(self), self = NULL;
 
                        err = 1;
                    }
                }
 
                if (err == 0)
                {
                    /* Initialisation */
                    for (i = 0; i < nlines; i++)
                    {
                        for (j = 0; j < ncols; j++)
                        {
                            self->_data[i][j] = 0.0;
                        }
                    }
                }
            }
            else
            {
                /* Echec de l'allocation: on fait le menage et on renvoit la
                   valeur NULL */
                free(self), self = NULL;
            }
        }
        else
        {
            /* Echec de l'allocation de memoire pour self: rien a faire, on
               renvoit la valeur NULL. */
        }
    }
 
    return self;
}
 
struct Matrix * m_matrix_delete(struct Matrix *self)
{
    if (self != NULL)
    {
        size_t i;
 
        for (i = 0; i < self->dim[0]; i++)
        {
            free(self->_data[i]);
        }
        free(self->_data);
        free(self), self = NULL;
    }
 
    return self;
}

Version 2: 3 allocations de mémoire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
struct Matrix
{
    double **_data;
    size_t dim[2];
};
#define MATRIX_INIT {NULL, {0}}
 
struct Matrix *m_matrix_new(size_t nlines, size_t ncols)
{
    struct Matrix *self = NULL;
 
    if (nlines > 0 && ncols > 0)
    {
        /* Hop, on change les habitudes et on alloue tout en un bloc */
        self = malloc(sizeof *self);
        if (self != NULL)
        {
            static const struct Matrix tmp = MATRIX_INIT;
            /* Initialisation de tous les champs de la structure a une valeur
               nulle */
            *self = tmp;
 
            self->dim[0] = nlines;
            self->dim[1] = ncols;
 
            self->_data = malloc(nlines * sizeof *self->_data);
            if (self->_data != NULL)
            {
                self->_data[0] = malloc(nlines * ncols * sizeof *self->_data[0]);
                if (self->_data[0] != NULL)
                {
                    int i;
 
                    for (i = 1; i < nlines; i++)
                    {
                        self->_data[i] = self->_data[0] + i * ncols;
                    }
 
                    /* Initialization */
                    for (i = 0; i < nlines * ncols; i++)
                    {
                        self->_data[0][i] = 0.0;
                    }
                }
                else
                {
                    /* Echec de l'allocation de memoire: on fait le menage et on
                       renvoit la valeur NULL */
                    free(self->_data);
                    free(self), self = NULL;
                }
            }
            else
            {
                /* Echec de l'allocation: on fait le menage et on renvoit la
                   valeur NULL */
                free(self), self = NULL;
            }
        }
        else
        {
            /* Echec de l'allocation de memoire pour self: rien a faire, on
               renvoit la valeur NULL. */
        }
    }
 
    return self;
}
 
struct Matrix * m_matrix_delete(struct Matrix *self)
{
    if (self != NULL)
    {
        free(self->_data[0]);
        free(self->_data);
        free(self), self = NULL;
    }
 
    return self;
}

Version 3: 1 allocation de mémoire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct Matrix
{
    double **_data;
    size_t dim[2];
};
#define MATRIX_INIT {NULL, {0}}
 
struct Matrix *m_matrix_new(size_t nlines, size_t ncols)
{
    struct Matrix *self = NULL;
 
    if (nlines > 0 && ncols > 0)
    {
        /* Hop, on change les habitudes et on alloue tout en un bloc */
        self = malloc(sizeof *self + nlines * sizeof *self->_data +
                      nlines * ncols * sizeof **self->_data);
        if (self != NULL)
        {
            size_t i, j;
            static const struct Matrix tmp = MATRIX_INIT;
            /* Initialisation de tous les champs de la structure a une valeur
               nulle */
            *self = tmp;
 
            self->dim[0] = nlines;
            self->dim[1] = ncols;
 
            /* Mise en forme de l'objet pour que tout pointe ou il faut */
            self->_data = (double **) (self + 1);
            self->_data[0] = (double *) (self->_data + nlines);
 
 
            for (i = (size_t) 1; i < nlines; i++)
            {
                self->_data[i] = self->_data[0] + i * ncols;
 
            }
 
            /* Initialisation des elements de la matrice */
            for (i = (size_t) 0; i < nlines; i++)
            {
                for (j = (size_t) 0; j < ncols; j++)
                {
                    self->_data[i][j] = 0.0;
                }
            }
 
        }
    }
 
    return self;
}
 
void m_matrix_delete(struct Matrix *self)
{
    if (self != NULL)
    {
        free(self);
    }
}

Avec mes meilleures salutations

Thierry

**Sve@r** · 01/05/2011, 00h30

Envoyé par Thierry Chappuis

Dans un autre fils, j'ai posé un code proposant un schéma d'allocation de mémoire pour un type abstrait de donnée Matrix qui a suscité le débat sur le plan du respect des contraintes d'alignement (Version 3 ci-dessous). Je crée ici une nouvelle discussion pour ne pas polluer le thread initial. Si la version 1 du code ci-dessous est celle généralement proposée, la version 2 est probablement plus facile à gérer par un débutant (moins d'allocation, gestion des erreurs allégée). Du point de vue de la performance, pour des grosse matrices, y a-t-il un avantage à allouer la mémoire pour chaque ligne de la matrice comme dans la version 1, par rapport à une allocation en masse comme dans la version 2 (p.ex. moins de swap)? Ou inversemment?

Salut

Comme tu le sais (mais d'autres ne le savent pas forcément), j'étais dans l'autre fil dont tu parles et j'ai été surpris de ta façon innovante (pour moi) d'allouer ta matrice (qui correspond à la version 3 ici).
Innovante mais une fois qu'on l'a vue et comprise, on se dit "ben oui, c'est effectivement tout con". Un peu comme l'oeuf de Colomb quoi.

Donc maintenant mon avis. La version 3 (allocation complète d'un coup) présente l'avantage de tout stocker au même endroit. Eventuellement tu peux dupliquer ensuite toute ta matrice avec un simple memcpy().
L'inconvénient c'est que toute ta matrice étant vue comme une grosse chaine, tu auras des difficultés à l'agrandir (va donc essayer de rajouter une colonne sans te vautrer dans les colonnes déjà remplies juste pour rire...

)
La version 1 est plus typique du cas d'école. On alloue le conteneur puis on alloue les éléments individuels qui deviennent, dès lors, plus facilement manipulables/maintenables.

Ensuite le reste dépend bien entendu de l'usage qu'on doit en faire. Et questions performances, je ne sais pas trop. J'aurais tendance à penser que la mémoire c'est un peu comme un disque => vaut mieux qu'elle ne soit pas trop fragmentée => vaut mieux éviter de démultiplier les malloc() individuels mais c'est purement subjectif...

**Thierry Chappuis** · 01/05/2011, 01h39

Une matrice, au sens mathématique du terme, possède en général une taille fixe qui n'évolue pas au cours de sa vie. Ainsi, la possibilité de redimensionner n'est pas aussi importante que si on avait voulu faire un tableau à deux dimensions flexible. Je suis d'accord avec toi, la version 3 n'est pas propice au redimensionnement.

Si on désires redimensionner tout en garantissant un minimum de fragmentation de la mémoire, la version 2 a certains avantages.

Aux trois versions précédentes, je peux ajouter une quatrième version qui n'utilise que 2 allocations, garantit le respect des contraintes d'alignement, limite la fragmentation de la mémoire et autorise un redimensionnement pas trop prise de tête de la matrice:

Version 4: deux allocations

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct Matrix
{
    size_t dim[2];
    double **data;
    double _t[1]; /* HACK: l'espace memoire necessaire pour stoquer nlines * ncols doubles sera alloue dynamiquement */
};
#define MATRIX_INIT {{0}, NULL, {0.0}}
 
struct Matrix *m_matrix_new(size_t nlines, size_t ncols)
{
    struct Matrix *self = NULL;
 
    if (nlines > 0 && ncols > 0)
    {
        self = malloc(sizeof *self + nlines * ncols * sizeof *self->_t);
        if (self != NULL)
        {
            self->data = malloc(nlines * sizeof *self->data);
            if (self->data)
            {
                size_t i;
 
                for (i = 0; i < nlines; i++)
                {
                    self->data[i] = self->_t + i * ncols;
                }
 
                /* initialisation */
                self->dim[0] = nlines;
                self->dim[1] = ncols;
 
                for (i = 0; i < nlines * ncols; i++)
                {
                    self->data[0][i] = 0.0;
                }
            }
            else
            {
                /* Echec d'allocation: on fait le menage et on retourne NULL */
                free(self), self = NULL;
            }
        }
    }
 
    return self;
}
 
struct Matrix * m_matrix_delete(struct Matrix *self)
{
    if (self != NULL)
    {
        free(self->data);
        free(self), self = NULL;
    }
 
    return self;
}

Thierry

**diogene** · 01/05/2011, 10h18

J'ai déjà exprimé dans le fil que tu évoques mes réticences à mélanger dans une même allocation des données de types différents à cause des questions d'alignement. Donc à priori, je n'adopterai pas le modèle 3.
Les versions 1 et 2 sont classiques avec leurs avantages et leurs inconvénients.
- La version 1, plus lourde à mettre en place, à l'avantage de faciliter le redimensionnement des tableaux 2D, peut être de faciliter l'allocation de gros tableaux en permettant de fractionner la mémoire en morceaux plus petits.
- La version 2, outre l'avantage de la simplicité de mise en oeuvre, a l'avantage de stocker les données de la même façon que le fait un véritable tableau, ce qui peut être un avantage si on doit utiliser des fonctions de bibliothèque demandant un tel tableau en argument.

- Pour la version 4, la déclaration devrait être

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
struct Matrix
{
    size_t dim[2];
    double **data;
    double _t[]; 
};

pour exploiter un véritable "flexible array" dans la structure.

**Thierry Chappuis** · 01/05/2011, 12h41

Envoyé par diogene

J'ai déjà exprimé dans le fil que tu évoques mes réticences à mélanger dans une même allocation des données de types différents à cause des questions d'alignement. Donc à priori, je n'adopterai pas le modèle 3.
Les versions 1 et 2 sont classiques avec leurs avantages et leurs inconvénients.
- La version 1, plus lourde à mettre en place, à l'avantage de faciliter le redimensionnement des tableaux 2D, peut être de faciliter l'allocation de gros tableaux en permettant de fractionner la mémoire en morceaux plus petits.
- La version 2, outre l'avantage de la simplicité de mise en oeuvre, a l'avantage de stocker les données de la même façon que le fait un véritable tableau, ce qui peut être un avantage si on doit utiliser des fonctions de bibliothèque demandant un tel tableau en argument.

- Pour la version 4, la déclaration devrait être

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
struct Matrix
{
    size_t dim[2];
    double **data;
    double _t[]; 
};

pour exploiter un véritable "flexible array" dans la structure.

Je ne désire pas un tableau à longueur variable au sens C99 du terme, mais bien un tableau de 1 élément. Comme le C ne fait pas de vérification qu'un tableau est appelé avec un indice inférieur à sa longueur, la version 4 fonctionne et l'alignement est garantit.

Cela reste toutefois un hack pas très recommandable et la version 2 a ma préférence.

Thierry

**diogene** · 01/05/2011, 14h12

Ma remarque ne concerne pas les VLA (qu'on ne peut utiliser comme membre d'une structure), mais la possibilité d'avoir un "flexible array member" des structures ce qui correspond à ton idée et à ton code.

cf n1256 6.7.2.1 article 16

**Thierry Chappuis** · 01/05/2011, 14h21

Envoyé par diogene

Ma remarque ne concerne pas les VLA (qu'on ne peut utiliser comme membre d'une structure), mais la possibilité d'avoir un "flexible array member" des structures ce qui correspond à ton idée et à ton code.

cf n1256 6.7.2.1 article 16

Là, je découvre cet article de la norme. Merci pour la référence.

Thierry

Schéma d'allocation mémoire pour une matrice

C

Discussions similaires

Partager

Partager