C : un "gros" malloc me donne la mémoire au fur et à mesure

Bonjour à tous.

[Edit] J’utilise le nouvel éditeur, des retours à la ligne sont supprimés[/Edit][Edit 2]Je n’ai pas lu la doc, oubliez ça[/Edit 2]

Merci pour vos tutos, je les découvre tard mais ils aident beaucoup et sont très agréables à lire. Si ce post contrevient aux règles du forum, merci de me le dire. Et, naturellement, il y a eu recherche préalable de solutions mais rien n’a été trouvé

(Développement sous Code::Blocks / Windows 10) En allouant une grosse quantité de RAM (1’000’000 de tableaux de 1’000 char) on constate (via le Gestionnaire de Tâches) que la RAM n’est pas allouée au moment du malloc mais au fur et à mesure du "remplissage" des chaînes. Pourquoi ? Comment ? Est-il possible de tout avoir d’un coup ?

• Est-ce parce qu’il est jugé inutile de dépenser 1Go là ou l’utilisateur ne prendra peut-être que beaucoup moins ?
• Est-ce décidé par l’OS ? Par le mode de compilation du programme ?
• Si, comme supposé, la RAM est "donnée" au fur et à mesure, est-ce que cela se passe par des réallocations (qui doivent donc consommer du temps) ?
• Enfin, est-il possible d’éviter cela ?

Merci !

Le code qui suit met cela en évidence (sous Windows 10), à exécuter avec le Gestionnaire de Tâche affiché à côté de la fenêtre. Bien entendu il s’agit d’un "résumé" pour mise en évidence, le besoin réel est plus complexe.

#include <stdio.h>

#define PAUSE_TAILLE 100000
#define CHAINE_TAILLE 1000
#define CHAINE_NBRE 1000000
#define pause(texte) printf("%s (press <Enter>) : ", texte); getchar()
int main(){

    char ***x;
    pause("Avant malloc");
    x = (char*) malloc( CHAINE_TAILLE * CHAINE_NBRE);
    if( !x ){
        printf("Erreur d'allocation x\n");
        exit(3);
    }
    pause("Apres malloc\nAvant le remplissage");
sprintf(x[9000000],"%d",9000000); // Au cas où, voir si remplir un élément "haut placé" réglait le problème
pause("9000000");
    for(int i=0; i<CHAINE_NBRE; i++){
        sprintf(x[i],"%d",i);
        if( ( (i+1) % PAUSE_TAILLE ) == 0 ){
            printf("%9d remplissages faits", i);
            pause("");
        }
    }
    pause("Fin des remplissages\nAvant free");
    free(x);
    pause("Apres free\nProgramme fini");
    return(0);
}

Merci pour ta réponse ! Je me doutais d’un fonctionnement de ce genre, c’est logique. La question maintenant est de savoir si cette distribution de pages virtuelles prend du "temps", ce qui me gênerait. En effet, mon programme fait un très grand nombre de malloc/realloc/free de structures, et comme je tente de le rendre plus rapide, je cherche à pré-créer ces structures pour pouvoir les prendre/rendre par de simples copies d’adresses dans des tableaux (bien entendu, je crée ces tableaux au gré des besoins). Si je tente de réduire le nombre de mes malloc en pré-créant des piles de structures mais qu’en échange l’OS m’alloue (et je suppose désalloue) de la RAM au fur et à mesure des besoins, j’ai l’air malin ! N’y aurait-il pas moyen de dire à Windows "donne-moi ma RAM un point c’est tout" ?

Merci encore adri1.

D’accord otini.

Je me passerai d’utilisation d’outils pointus (pour moi), l’apprentissage du C accapare déjà beaucoup et vous avez je pense tous deux parfaitement répondu à ma question.

C’était de plus du découpage de cheveux en quatre (et de la curiosité) dans la mesure où pour chaque structure allouée il y a :

• tri/concaténation de _{14 chaines de} 5 caractères
• recherche par dichotomie dans un (grand) tableau de pointeurs sur ces structure, par comparaisons de chaines d’~200 caractères,
• insertion éventuelle du pointeur dans ce tableau (pour cette partie là peut-être qu’une arborescence serait intéressante, et encore) Bref, beaucoup de strcpy, strcat et strcmp, qui doivent certainement consommer bien plus qu’une allocation par petits morceaux. En plus, je réalise que cette tentative de récupérer des secondes ne serait utile que pour de gros traitements, qui donneront de gros tableaux, qui dépasseront la taille de la RAM ce qui donnera du swap…

Merci encore à tous les deux.

Je ne connais pas de cas où le programme alloue tellement vite que ça peut être un réel problème

Le cas classique où ça peut être gênant est avec une collection qu’on fait grandir dans une hot loop bien optimisée par ailleurs. Parfois c’est plus rapide d’allouer et initialiser toute les pages d’un coup (même si c’est avec un truc invalide pour le type en question, genre avec des 0) que de prendre de la mémoire non-initialisée et se cogner ensuite les pages faults dans la hot loop. C’est assez rare en pratique, et c’est encore plus rare que ce soit le bottleneck.

mon programme fait un très grand nombre de malloc/realloc/free de structures, et comme je tente de le rendre plus rapide, je cherche à pré-créer ces structures pour pouvoir les prendre/rendre par de simples copies d’adresses dans des tableaux (bien entendu, je crée ces tableaux au gré des besoins)

Une règle d’or en optimisation (surtout avec des langages systèmes où l’intuition se plante souvent) est de profiler pour savoir ce qui prend effectivement du temps. Une fois que c’est identifié, il faut déjà réfléchir à des changements possibles à l’algorithme utilisé. Et seulement ensuite, réfléchir aux questions de taille de cache, prédiction de branche, d’éviter les appels systèmes (dont les allocations), de page fault, etc qui peuvent se produire. C’est relativement rare en pratique d’avoir besoin de taper dans ces considérations bas niveau pour optimiser efficacement un programme (à moins de faire vraiment n’importe quoi évidemment, mais c’est un autre problème).

Salut,

Par ailleurs, je trouve que ce serait intéressant de savoir ce sur quoi tu travailles, notamment pour des raisons d’algos (voir le message de adri1).

Bonjour, Désolé mille fois, je ne recevais pas de notifications (un paramètre non vu sur le profil ?), aussi je n’ai pas été "sonné" pour les messages !!

Edit : Aille, erreur de quotation.

Bonjour, (Et désolé encore pour le retard)

Sur quoi je travaille… Pour cause de problèmes mentaux je n’arrive plus trop à refléchir, structurer, penser à l’avance, ma capacité d’apprentissage est réduite et, surtout, j’oublie vite le savoir acquis. Le tout dit sans vouloir me plaindre, c’est juste pour expliquer ma démarche et le fait que je ne veux pas m’enfoncer dans des notions trop complexes. Bref, je programme un peu pour m’amuser, sans allez trop loin, histoire de dégourdir le cerveau. Tout n’est qu’exercice relativement facile.

Le but est de résoudre le jeu des "tubes à essai".

J’avance par approches successives et aussi fais mumuse avec différentes possibilités du C.

• Les "tubes" sont stockés dans des fichiers texte, une lettre par couleur, on part du principe que le fichier est "propre". Ce principe permet de changer facilement la configuration à résoudre, il est préférable de faire des essais sur du facile.
• La méthode de départ est brutale (ça a un nom que j’ai oublié) : "pour tout tube de départ possible, pour tout tube d’arrivée, si le mouvement est possible, le faire, et itérer". Dès qu’une solution est trouvée, on arrête.
• Il y a eu divers gains de temps évidents.
• Il y a eu ensuite recherche de la solution la plus rapide : on n’itère plus dès que le nombre d’itérations dépasse la "taille" de la meilleure solution déjà trouvée, et on continue jusqu’à la fin.
• Un gain important : inutile (selon les cas) de chercher plus loin lorsqu’une étape a déjà été rencontrée (aux échanges de position des tubes près). Cela nécessite de stocker une "image" de l’étape en cours : on trie les tubes entre eux par ordre alphabétique (puisqu’ils sont des chaines de caractères), on concatène pour en faire une longue chaine qui en quelque sorte est une trace de l’étape en cours. Ce sont ces traces dont les adresses sont stockées dans un tableau et pour lesquelles je voulais tenter (toujours à titre d’exercice) une sorte de préallocation par paquets.
• Pour ces chaines, il y a recherche (dichotomique) dans le tableau qui est, par nature, trié. Si la chaine n’existe pas, on l’insère dans le tableau et ça, ça consomme un temps fou. En effet, mes tableaux sont montés jusqu’à 3’000’000 de chaines, faire décaler les pointeurs à (potentiellement) chaque itération consomme beaucoup. En ce moment, je travaille à remplacer ce tableau par une arbre binaire équilibré (AVL) dont j’ai trouvé les explications sur ce site \o/.
• A titre d’expérience j’ai tenté de paralelliser un peu (avec pthread), avec autant de threads que de tubes, mais malgré une grosse optimisation sur les durées d’activation des mutex, cela était plus lent. Il faut dire qu’un mutex actif couvrait recherche/insertion de chaque chaîne. Avec l’insertion dans un tableau AVL, il est probable que cette solution parallélisée redevienne envisageable.
• les données sont organisées en quelques structures, toutes dynamiques au début, histoire de me faire des noeuds aux neurones avec les pointeurs, mais il ne reste maintenant que peu d’allocations dynamiques, ce n’était pas rentable. Après l’implémentation de l’AVL il restera beaucoup de choses à faire comme établir un nommage strict des variables, implémenter une meilleure structuration des fonctions, puis des choses certaines peu utiles mais par amusement, comme l’enregistrement tous les x itérations de l’"état des lieux", ce qui sera consommateur de temps mais permettra de reprendre le traitement après interruption brutale. Ensuite, peut-être du C++ afin d’implémenter une interface graphique vec QT pour montrer les jolies petites billes qui se déplacent et construisent la solution.

Tout à été fait par mes blanches mains, avec beaucoup de recherches sur les sites (c’est ainsi que j’ai découvert ZesteDeSavoir !), tout sauf l’implémentation des BST, l’implémentation faite par Richou D. Degenne (https://github.com/Richard-Degenne/bst) était trop élégante pour que je m’en passe, je n’aurais jamais pu faire cela. Cette implémentation est en cours de modification pour passer de BST à AVL, le résultat sera bien moins élégant.

Bref, tu m’a compris, le but est surtout de musarder à droite et à gauche, toucher à tout sans toutefois approfondir réellement.

Je pense avoir été verbeux et touffu :-)

La méthode de départ est brutale

Bruteforce ?

Question: j’arrive un peu en retard pour la bataille, mais il n’est pas possible de faire du pooling de mémoire si le soucis réside dans l’allocation / la désallocation ?