Discussion :

[Moine]

Bonjour tous le monde,

Je dois traiter un fichier qui fait fait à peu près 1Go. Je le chargeais entièrement en mémoire avant de le traiter mais il se trouve que le programme ne peut s'exécuter que sur des machines qui ont au moins 1Go de mémoire et là encore c'est très lent. On m'a conseillé de diviser mon fichier en bloc de page de 512 octets et d'implémenter un algorithme de pagination(MRU ou LRU). les deux derniers octet de chaque page sont réservés pour des informations sur la page(numéro,modifier ou pas, le nombre d'enregistrement,etc). On doit pouvoir se déplacer dans chaque page pour aller récupérer l'information que l'on veut.

J'ai compris tous ça mais je voudrais savoir qu'elle structure de donnée utilisée pour declarer mes pages. Je songe à un truc de ce genre:

Code :

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

1
2
3
4
5
 
typedef Page{
   unsigned char* data[512];
   Page *next_page; //pour chainer les pages
}

Est ce que c'est la bonne manière de faire?

merci de me donner des exemples de structure de donnée qu'on peut utiliser pour déclarer une page de tel sorte qu'on puisse se déplacer dedans la lire, la modifier et l'enregistrer dans mon fichier.

[Mac LAK]

Ta structure est fausse : soit tu mets "unsigned char data[512]", soit "unsigned char* data", mais pas le pointeur + la taille en tout cas.

Personnellement, je prendrais une taille un peu plus grande que 512 octets (disons 4096 au moins, voire 32.768), et j'utiliserais un index / cache permettant de savoir si oui ou non un bloc est chargé en mémoire ou pas. L'index en question est bêtement un vecteur de structures de contrôle.

Reste le problème de l'invalidation : pour ça, je pense que des deadlines(*) pourraient être intéressantes à utiliser afin d'avoir un minimum de temps CPU consommé pour ce point.

Pour initialiser tout ça, tu prends la taille du fichier, tu la divise par la taille du bloc unitaire (ça peut se régler avec de simples décalages binaires très rapides), et tu alloue ton index. Bien entendu, aucune donné n'existe dedans, et cela correspond à la fonction d'ouverture de fichier.

Pour lire, un décalage binaire te donne immédiatement l'entrée d'index souhaitée. Si le bloc est présent, tant mieux, sinon tu le charges depuis le disque. Un petit accesseur sur un "pointeur courant" fera merveille pour rendre ça transparent et gérer au passage le pointeur réel sur le fichier.
Ensuite, tu renvoie autant de données que requis, en t'inspirant de la fonction de lecture fichier standard.

Pour l'écriture, c'est la même chose que la lecture bien entendu, sauf que là, autant flusher l'écriture directement sur le disque, par sécurité. Là aussi, les accesseurs "pointeur logique"/"pointeur d'index" t'aideront à grandement simplifier le problème.

Reste enfin la fermeture de fichier, qui détruira les blocs alloués et l'index, en plus de fermer réellement le fichier sur le disque.

Reste ensuite le problème d'invalidation des blocs : tu peux rajouter une deadline à chaque entrée valide de ton index, deadline réarmée à chaque accès à ce bloc. Une durée de 30 secondes me parait amplement suffisante. Chaque deadline active doit être stockée dans une file, l'idéal étant de ne stocker que l'indice du bloc dans la table d'index. Un petit thread léger s'occupera alors de vérifier régulièrement les deadlines : un réveil chaque seconde, il parcourt alors les deadlines de sa liste chaînée.
Si la deadline est expirée, elle est retirée et le bloc de cache libéré, l'entrée d'index est alors invalide. Si elle est valide, la deadline est réinsérée en fin de file pour une prochaine vérification.
On peut optimiser un peu le réveil du thread en calculant à la volée la plus proche durée d'expiration, et s'endormir d'autant. On peut également surcharger les méthodes de la classe, et leur faire traiter une entrée de file à chaque fois.

On peut aussi "compter" le nombre de blocs chargés en mémoire actuellement, et forcer des libérations si la taille totale excède une limite donnée (libération des plus anciens blocs en premier). On peut également faire ce nettoyage si l'allocation d'un bloc échoue : dans ce cas, il n'y a que si la DEUXIÈME allocation échoue qu'il y a réellement un problème (et une erreur).


Cela devrait être efficace, simple à faire et avoir une consommation mémoire raisonnable et/ou paramétrable... Ce qui devrait alors t'autoriser à le faire tourner même sur des machines avec peu de RAM.


(*) Deadline : entité logicielle permettant de calculer une date d'expiration / validité d'une donnée par ajout d'une certaine durée à un compteur interne "fiable" et surtout, rapide à obtenir. La précision dépend du système, on peut utiliser GetTickCount() sur Windows et gettimeofday() sur Linux.
Le principe moteur de la deadline, c'est qu'elle est PASSIVE : elle ne consomme du temps CPU qu'en étant utilisée, et ne requiert ni système de synchronisation, ni signaux, ni threads, uniquement un compteur temporel système.
Elle peut être réarmée (on prolonge la validité courante d'une durée donnée), annulée (elle expire immédiatement) ou consultée (elle renvoie alors un booléen indiquant si elle est expirée ou pas).
Le calcul d'expiration se résume à comparer le compteur système courant à la valeur prévue pour l'expiration, donc une inégalité entre entiers, très rapide. Le réarmement se résume à une addition, l'annulation à un positionnement à zéro.

[Moine]

Je vois un peu plus clair. Merci Lak pour l'astuce.

Si j'ai 512 octets comment me positionner sur la dernière octet c'est à dire lire la dernière octet?

si j'arrive à avoir cette information je pense que mon problème serait résolut.

[Mac LAK]

Tout dépend si tu veux le dernier octet du bloc de 512 (= le 511ème, donc), ou l'octet situé 512 plus loin (= le premier du PROCHAIN bloc)...

Sinon, ton octet est accessible par "data[511]" depuis ta structure de contrôle, le 511 étant obtenu par masque binaire depuis la position "réelle" dans le fichier.

[nicroman]

Code :

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

1
2
3
4
5
 
static const size_t page_size = 512;
 
size_t   page_number =  position / page_size;
size_t   pos_in_page = position % page_size;

Mais charger toutes les pages chainées en mémoire, revient à charger le fichier complet (c'est même pire).
Donc implémenter un LRU/MRU est absoluement indispensable.

Du coup, c'est plus certainement un unsigned char* (sans le tableau)

[Mac LAK]

Mais charger toutes les pages chainées en mémoire, revient à charger le fichier complet (c'est même pire).

Ce que j'ai expliqué au post #2 est un LRU+MRU, si tu regardes bien... Cela ne charge pas toutes les pages, juste celles demandées, et la consommation mémoire maximale est paramétrable si nécessaire, tout comme la durée d'expiration des blocs.

[white_tentacle]

Je plussoie sur le fait que 512 soit trop peu comme valeur, et que 4096 soit beaucoup mieux adaptée (il me semble bien qu'une page mémoire fait 4k sur un x86 standard).

[Mac LAK]

Je plussoie sur le fait que 512 soit trop peu comme valeur, et que 4096 soit beaucoup mieux adaptée (il me semble bien qu'une page mémoire fait 4k sur un x86 standard).

16k sous DOS, ça m'étonnerait que ça soit plus petit actuellement qu'à l'époque...
Il faut aussi compter avec la taille d'un cluster sur le disque (4k minimum), et prendre en gros le PPCM de la taille des clusters et des pages mémoire.

Normalement, 32k ou 64k devraient être idéaux.

[Jean-Marc.Bourguet]

La taille des pages des 80386 et successeurs est de 4 Kb; les processeurs plus recent (enfin, depuis le Pentium si j'ai bonne memoire) permettent aussi des pages de 4 Mb. D'autres processeurs ont des tailles de pages differentes (ou permettent plusieurs tailles).

Je pense que tu te souviens de la memoire "expanded" (alias LIM) qui etait une technique de pagination a partie d'une carte separee pour les 8086 et qui utilisait bien des pages de 16K. Les dernieres implementations etaient logicielles et utilisaient la memoire paginees de 80386 (donc une page LIM correspondait a 4 pages du processeur).

[Mac LAK]

Arf, oui, c'est vrai, 16k c'était la taille des pages EMS, pas des pages CPU... Ça ne nous rajeunit pas, tiens...

[Moine]

Je dispose de tous les éléments maintenant pour accélérer l'exécution de mon programme. Je vous remercie tous!