Bonjour a vous,
J'implemente en ce moment des algorithmes de programmation dynamique qui consomme une quantite de memoire impressionnante. Dans l'idee je cherche a evaluer une fonction positive recursive a 3 parametres. Je maintient a jour un tableau a 3 dimensions qui contient les valeurs de cette fonction. Si la valeure est negative, ca veut dire que je ne l'ai jamais evalue. Si j'en ai besoin, je l'evalue et met le resultat dans la table.

J'ai un nombre impressionant de coupe sur l'evaluation de ma fonction recursive qui fait que ma table est surtout compose de nombre negatif a la fin de mon evaluation. Les temps de calcul ne sont pas si gros que ca, mais la consommation memoire commence a etre le bottleneck. Pour resoudre le probleme j'ai deux pistes:
-utiliser une table de hash ou n'importe quelle technique de stockage de matrice creuse.
-ne mapper la memoire virtuelle vers de la memoire physique que lors de la premiere ecriture.

Je ne vais pas vous embeter avec la premiere qui releve juste de l'implementation, mais plutot avec la deuxieme.

Il est possible sous windows d'allouer de la memeoire virtuelle sans allouer la memoire physique qui va avec. Ca se fait avec virtualalloc ( http://msdn.microsoft.com/en-us/library/aa366887(VS.85).aspx ). Lorsque l'on acce a un de la memoire virtuelle non mappe sur la memoire physique, on reoit une exception STATUS_ACCESS_VIOLATION. On peut la traiter en allouant la memoire qui va bien qu'au moment ou on en a besoin.

Ma question pour vous est donc : Y a t'il un moyen de faire la meme chose sur mon linux 2.6.18 prefere ?

Pour autant que je sache, sous linux les demandes d'allocations sont déjà optimistes par nature. Ce qui signifie qu'un appel à malloc peut réussir même si physiquement la mémoire ne suit pas.

Dans ce contexte ça fait déjà un peu ce que tu demandes non?

Non, ça ne fait pas ce qu'il vaut, car l'allocation dans ce cas là est trop automatique et il ne peut pas différencier une cellule non initialisée d'une cellule déjà calculé.

Peut-être que tu peux jouer un peu entre les deux tableau en ayant une structure qui t'indique si une zone de la matrice (qui fait exatement la taille d'une page) a déjà été initialisé ou non. Ça te demande de la lire avant chaque accès, mais ce n'est pas un très gros problème.

Sinon, je ne connais pas d'appel sous linux qui serait équivalent à ce virtualalloc (c'est rare les fonctionnalité système qui existe sous windows mais pas linux, mais c'est vrai que la plupart de celles-ci ont à voir avec la gestion de la mémoire). Cependant est-ce que mmap avec le drapeau MAP_NORESERVE ne ferait pas ce que tu veux ?

je pourrais faire l'allocation manuellement, Ca serait probablement moins couteux que de devoir traiter une exception systeme de toute facon.

Je ne suis pas bien sur de ce que mmap avec MAP_NORESERVE fait. J'ai l'impression que mmap sert "seulement" a mapper des descripteurs de fichier en memoire ce qui n'est pas vraiment la meme chose.

Merci pour votre opinion.

non mmap est la primitive d'allocation de mémoire du système (ou était). Si tu ne veux pas mapper un fichier mais juste obtenir de l'espace, il faut lui passer le flag MAP_ANONYMOUS. Ensuite je suis d'accord que la description dans le man de ce drapeau NORESERVE n'est pas très clair. Il faudrait regarder dans les sources pour se faire une idée.

Bonjour encore a vous,

Je up mon topic un an apres pour poser une autre question. Je cherche a allouer un gros bout de memoire virtuelle (disons 1TB) et faire de l'allocation de blocs a (disons 1MB) l'interieur de ce morceau de memoire virtuelle ainsi que de la desallocation.

J'ai essaye d'abors de faire du mprotect(2) en me disnt que si un bloc de memoire avait pour protection "pas d'access" alors la memoire physique serait libere. Cependant l'execution du code suivant m'a fait obtenir un out of memory.

1. include <sys/mman.h>

int main ()
{
size_t sizetotal = 0x0100000000;
char* result = (char*)mmap(((void*)NULL), sizetotal, PROT_NONE, MAP_PRIVATE | MAP_ANON, -1, 0);

size_t sizeb = 0x100000;

for (size_t offset = 0; offset < sizetotal; offset += sizeb)
{
mprotect (result+offset, sizeb, PROT_READ|PROT_WRITE);
for (size_t inb = 0; inb < sizeb; inb++)
*(result + offset + inb) = 0;
mprotect (result+offset, sizeb, PROT_NONE);
}
return 0;
}

Une facon de forcer le noyau a liberer la memoire est d'appeller munmap. Une facon de faire pour regler mon probleme serait de faire un premier appel a mmap pour reserver 1TB de memoire virtuelle. Ensuite faire un appel a munmap pour liberer cette memoire virtuelle. Ensuite allouer tous les blocs de 1MB dans l'espace qui vient d'etre libere avec mmap et le flag MAP_FIXED. du fait, je peux allouer la memoire physique automatiquement quand j'ecris dessus et je peux la desalloue en appelant munmap et mmap sur le meme bloc de memoire virtuelle.

Ca devrait faire ce que je veux... a moins qu'un autre thread ne fasse joujou avec mmap lui aussi...

Un peu de contexte pour finir. J'ai des donnees tres grosses, mais je sais quelle ne seront pas utiliser toute d'un coup et j'ai un moyen de stockage (basiquement a travers le reseau) pour stocker toutes mes donnees. Je cherche a etablir un cache local de cette donnee qui conserve la contiguite de pointeur en memoire virtuelle. Les intentions d'access a la memoire me sont declarees et je suis averti quand la memoire n'est plus utile (ce qui me permet d'avoir du refcounting par bloc). Si je relaxe la propriete de contiguite alors c'est beaucoup plus simple pour moi mais les utilisateurs de la lib vont devoir gerer eux meme les problemes d'access d'un bloc a l'autre (ce qui pourrait etre abstrait, mais c'est fatiguant)

des idees? du petrole?

Je pensais même pas qu'on pouvait avoir un swap aussi gros (1TB). J'imagine que ça va pas t'aider mais tu ne devrais pas réfléchir à travailler sur disque directement vu cette quantité de données?

On ne travaille pas sur disque. Les donnees sont stockees dans la memoire d'un cluster. L'interface reseau est bien plus rapide qu'un access disque. Et les autres noeuds du cluster participent aux calculs.

PS: Quand je parle de memoire virtuelle, je ne parles pas de swap. Je parle de l'adressage de la memoire d'un processus qui est mappee en memoire physique par la TLB.