Discussion :

[plxpy]

Bonjour,

Ces derniers jours, il y a eu plusieurs messages concernant des listes triées/à trier quelquefois "monstrueuses" (plusieurs millions d'éléments). Souvent, l'utilisation de tableaux a aussi été évoquée comme palliatif.

En y réfléchissant, je me suis posé la question suivante à laquelle je n'ai pas de réponse.

Peut-on se retrouver dans la situation où une allocation dynamique de (n x m) octets échouera tandis que, dans le même contexte, n allocations de m octets réussiront ? (pour une histoire de place, pas de syntaxe ou un truc dans le genre).

(n x m) octets contigus sont plus rares et difficiles à trouver que n blocs de m octets contigus, non ?

Est-ce que le système (l'OS) peut alors être amené à faire une espèce de "défragmentation" de la mémoire ou pas ? (en respectant, bien évidemment, les autres allocations faites et les adresses retournées précédemment).

Merci d'avance pour vos éclaircissements

ps : 1 allocation impose de mémoriser 1 adresse. N allocations imposent d'en mémoriser N mais ce n'est pas sur cela que ça porte, bien évidemment.

[Neckara]

L'avantage d'utiliser plusieurs malloc permet de faciliter les realloc futurs.

Après, quand on a beaucoup de données on utilisera surtout des Listes pour faciliter l'insertion, la suppression d'éléments.

Ensuite, un OS est très bien capable d'écrire sur la ROM quand la RAM ne suffit pas, donc pour "défragmenter" la RAM, c'est peut être possible en effet.

Mais en général, trouver un espace contigu est plus difficile de trouver n petits espaces.
Si il y a de la place pour le grand espace contigu, c'est qu'il y a en a pour les petits espaces, mais la réciproque n'est pas vraie.

[anacharsis]

un OS est très bien capable d'écrire sur la ROM

fais attention! pour les gens de ma génération ça craint un max ;=)

A+

[Neckara]

Le fait que l'OS soit capable d'écrire sur la ROM suggère bien que l'OS peut déplacer des segment de RAM en fonction de l'utilisation de la RAM.

Donc si un OS est capable de gérer cela, il est probable qu'il puisse aussi "arranger" la RAM pour avoir plus d'espace contigu.

Mais je n'ai jamais dit qu'utiliser de la ROM en tant que RAM était bien.
La ROM est beaucoup trop lente et n'est pas faite pour se substituer à la RAM.

Sinon, il me semble que les OS ont une technique bien particulière pour gérer la RAM, il faudrait se renseigner là-dessus.

[Derek Corgan]

Comme l'indique anacharsis écrire sur la ROM cela risque d'être difficile.

malloc reserve un espace vu comme contigüe dans le "tas".

Le tas peu être de la RAM (c'est préférable) ou de la mémoire de masse s'il n'y plus de place.
n allocation de (m) octets peut être intéressant si :
- risque d'avoir une allocation qui échoue (c'est rare) car n*m est très très élevé.
- si l'on souhaite faire des tris sur ces blocs.
Dans le cas de liste chainée l'on modifie uniquement les liens sans déplacer les valeurs.

[plxpy]

Merci pour vos réponses, même si j'avoue avoir un peu de mal à suivre quand ça descend trop bas, coté hard.

Sinon - j'aurais pu y penser avant ! - il suffit d'essayer :

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
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
 
#define MEGA        (1024*1024)
#define MEGA_500    (500*MEGA)
#define MEGA_10     (10*MEGA)
 
int main(int argc,char *argv[])
{
    char    *m500[8];   // 4 Go de mémoire
    int      i,j;
 
    for (i=0;;i++)
    {
        if ((m500[i] = malloc(MEGA_500)) == NULL)
            break;       
        // Sans remplissage, la mémoire utilisée qui est affichée dans le
        // moniteur système ne bouge pas (même si je sors de la boucle
        // au bout du meme nombre d'iterations). Avec remplissage, j'assure
        memset(m500[i],i,MEGA_500);
    }
 
    fprintf(stderr,"%d x 500 Moctets alloues\n",i);
    fprintf(stderr,"echec pour les 500 Mo suivants\n");
 
    for (i=0;;i++) 
    {
        char *m10 = malloc(MEGA_10);
        if (m10 == NULL) break;
        memset(m10,'X',MEGA_10);
    }
 
    fprintf(stderr,"%d x 10 Mo alloués en plus\n",i);
 
    // les blocs de 500Mo sont ils toujours dans le même état ?
    for (i=0;i<8;i++)
        if (m500[i])
        {
            fprintf(stderr,"verif bloc 500 Mo no %d\n",i);
            for (j=0;j<MEGA_500;j++)
                assert(m500[i][j] == i);
        }
 
}

Sous Linux (Ubuntu 11.04, 32 bits), l'exécution donne ça (avant le lancement, environ 600Mo sont déjà utilisés) :

Code :

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

1
2
3
4
5
6
7
8
9
plx@sony:~$ ./memory
5 x 500 Moctets alloues
echec pour les 500 Mo suivants
54 x 10 Mo alloués en plus
verif bloc 500 Mo no 0
verif bloc 500 Mo no 1
verif bloc 500 Mo no 2
verif bloc 500 Mo no 3
verif bloc 500 Mo no 4

500 Mo, ça plante mais, par paquets de 10Mo, on en passe 540.

Ca peut parfois, selon le contexte, la taille des données qu'on manipule et la façon dont on s'y prend, être important.

[mala92]

un OS est très bien capable d'écrire sur la ROM

fais attention! pour les gens de ma génération ça craint un max ;=)

A+

Ca fait un bail que je ne fais pas du très bas niveau, mais ROM ne veut plus dire ReadOnly Memory ?

[Bktero]

Pour moi cela veut bien dire Read Only Memory

Plxpy, la question originale est intéressante. Je pense d'ailleurs que ton code exemple répond à la question.

[plxpy]

Je pense d'ailleurs que ton code exemple répond à la question

C'est ce que je pense aussi d'où le passage en "Résolu" dans la foulée de mon dernier message.

Sinon, pendant que j'y suis ...

(n x m) octets contigus sont plus rares et difficiles à trouver que n blocs de m octets contigus, non ?

n'était pas vraiment une question que je me posais. C'est au niveau du hard que j'atteins très vite mes limites, mais pour ça, pas de problème !