Newsgroup: it.comp.lang.c++
Titolo: array virtuali con piccola cache (roba da swappare su disco)

Premetto, che mi è venuto questo dubbio ma è di carattere 
generale, e non certo specifico del C++ .... Tuttavia, siccome 
alla fine lo scriverei in C++ immagino che eventuali consigli 
specifici tailored sulle caratteristiche specifiche del 
linguaggio mi sarebbero più utili di consigli generici di tipo 
astratto (per questo provo a postare qui).
Allora mi ponevo questo problema : fare un array virtuale di 
grandi dimensioni, ma che consumasse poca memoria.
La prima soluzione, funzionante, NON usava alcuna cache ma ad 
ogni accesso, con "tipo & operator [] (size_t indice)", leggeva 
eo scriveva ad OGNI singolo accesso su disco.
Certo, usa poca memoria e non è difficilissima da scrivere (ho 
usato la generazione di un tipo temporaneo tramite costruttore 
del medesimo chiamato dall'operatore [], e poi dal temporaneo 
distinguo se è a destra o sinistra in un'assegnazione.
Il casino è che le performance, assumendo di non avere nessuna 
bufferizzazione di sistema sul file, sarebbero penose.
Allora mi son detto, sarebbe più funzionale un compromesso. 
Usare un po' di memoria, tipo una cache, che non mappa certo 
l'intero array, ma neppure dovrebbe costringere l'I/O su disco 
ad ogni accesso.
Il mio problema è che non so pensare a nessuna soluzione 
risparmiosa di memoria per implementare un buffer SPARSO, nel 
senso che questa specie di cache, di dimensione fissa, 
conterrebbe elementi che sull'array nel disco non sarebbero 
necessariam. contigui, ma sparsi qua e la, secondo il criterio a 
rotazione, LRU (via via che referenzio nuovi elementi dal 
momento in cui la cache è tutta piena, scarto sempre il più 
anticamente referenziato, una specie di buffer circolare).
Sono sorti guai concettuali.
Ho pensato di affiancare alla cache un array super compatto, 
fatto di singoli BIT per ciascun elemento (meno spazio di così 
....), laddove posso leggere giusto se un certo indice 
corrisponde a un valore residente in ram oppure è da recuperare 
da disco, scartando il più datato indice presente.
Questo è ancora accettabile.
Ma poi mi sono accorto di non sapere come capire questo : a 
quale indice "vero" dell'array su disco corrisponde un certo 
indice "trasparente" nella cache, senza perdermi in terribili 
ricerche sequenziali nella mappa di bit.
E' ovvio che, in questo caso, l'ENNESIMO elemento della cache 
deve essere l'ennesimo bit TRUE nella mappa, che avrebbe un 
indice nella mappa uguale all'indice reale su disco ... ma se mi 
metto a contare tutti i bit della mappa sino a arrivare al 
quorum di bit veri, immagino che otterrei quasi di sicuro 
performance peggiori che non evitando del tutto ogni forma di cache.
Se invece della mappa binaria, creassi una cache che non 
contiene esattamente elementi del tipo di dato nativo ma un dato 
che lo wrappa e in più contiene un membro "indice" (per risalire 
al valore di indice che l'elemento ha su disco), perderei 
parecchio spazio extra (invece che un bit per elemento, 32 bit 
per elemento), velocizzerei si un po' le ricerche, ma sarebbero 
cmq lineari : se voglio leggere il dato con indice 15 non posso 
leggere l'elemento 15 della cache, ammesso che esista, ma 
consultarla per intero sino a trovare quello il cui campo indice 
è appunto 15.
So che i memory manager che gestiscono memoria virtuale e swap 
fanno un compito simile (anche se dal poco che so in maniera 
ancora più sofisticata di quantomi serve, e caricano paginate 
intere cercando di prevedere il futuro per ridurre l'I/O)
Per finire, come fareste voi ?
Mi consigliereste eventualm. con qualche reference di rete al 
problema ?
ciao e danke in advance
CCCP_Mario

 anticamente referenziato, una specie di buffer circolare).
Io manterrei una mappa che associa a ciascun indice nell'array virtuale
la posizione nel buffer circolare. Se non trovi l'elemento che cerchi
nella mappa vuol dire che devi caricarlo, nella prima posizione libera
se c'e' oppure al posto dell'elemento inserito meno recentemente, cosa
che ti viene automatica col buffer circolare. Per rimuovere il
corrispondente elemento nella mappa o lo cerchi linearmente o tieni nel
buffer circolare delle coppie indice virtuale - elemento
corrispondente. Considera l'eventualita' di mantenere un id al'interno
della tua classe, cosi' risolvi il problema.
Ciao,
Nicola

 
no ... aspetta un momento però, mi è venuto un dubbio.
QUANTO grande pensavi di fare l'array mappa ?
Ripensandoci, se l'array mappa, contenente solo indici, è 1:1 
con quello virtuale (con altrettanti elementi), è vero che mi 
posso scansare la ricerca lineare dato che la decodifica di 
qualsiasi indice è istantanea.
Però, se per caso ci fosse un alto rapporto tra numero di 
elementi totali virtuali e numero di elementi residenti mappati 
nella cache, allora lo spreco di spazio costerebbe salato (per 
classi non enormi).
Se invece l'array di decodifica contenesse lo stesso numero di 
elementi della cache, allora NON potrei scansarmi la ricerca 
lineare, vero ?
Uhm .... se quello che ho scritto è vero, mi sa che avevo preso 
un abbaglio e sono di nuovo nella bagna  :-(
Confermi la seconda ?
ciao
Soviet
CUT ALL

 dimensioni, ma che consumasse poca memoria.
Hai preso in considerazione i memory mapped files? fanno parte sia di 
Windows che di Linux, e offrono ottime prestazioni. Basti pensare che 
ogni volta che si lancia un eseguibile il file eseguibile viene aperto 
come un MMF.
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 come un MMF.
Anche io valuterei molto attentamente la soluzione basata su MMF. 
Sopratutto se gli elementi dell'array sono POD.
Se invece decidi di gestire tu il caching degli accessi, ti consiglio di 
non lavorare a singoli elementi ma a blocchi. Idealmente a blocchi 
corrispondenti alla dimensione di un settore logico del disco. O, in 
generale, a blocchi di dimensione 512*2^k con k intero (non negativo).

 assoluto di memoria.
Nota che devi definire "memoria".
Se leggi anche un solo byte, il sistema caricherà SEMPRE almeno un 
settore fisico. E quasi certamente caricherà un settore logico.
Questi dati verranno caricati in memoria cache del sistema (potrebbero 
persino esserci due livelli di cache). Poi verranno copiati nella 
memoria della tua applicazione. Come questo avviene dipende da quali 
funzioni usi (se usi l'I/O buffered esiste un ulteriore copia dei dati a 
livello di buffer allocati nel tuo spazio di indirizzamento).
Una cosa è la memoria mappata nel tuo spazio di indirizzamento (e 
riportata dai vari tool che indicano quanta memoria la tua applicazione 
usa). Un'altra è la memoria che la tua applicazione non vede ma che il 
sistema deve comunque allocare per soddisfare le tue richieste.
Il caricare un blocco utilizzando una funzione a bassissimo livello 
(quindi OS dependent) potrebbe rivelarsi meno dispendioso in termini di 
utilizzo di memoria che non caricare i singoli elementi.
L'uso dei MMF ha un ulteriore vantaggio: una parte dello spazio di 
indirizzamento del tuo applicativo viene mappato direttamente nella RAM 
usata dal sistema di caching dell'OS, con il file stesso come 
back-storage (quindi senza usare lo swap file come back-storage). 
Apparentemente il tuo applicativo usa più memoria. Di fatto sta usando 
memoria che sarebbe comunque usata dall'OS.

 lineare, vero ?
E chi ti impesisce di tenerlo ordinato, o di usare una mappa vera e
propria, as esempio std::map?
Ciao,
Nicola

 utilizzo di memoria che non caricare i singoli elementi.
vorrei accontentarmi dell'I/O binario non bufferizzato, ma pur 
sempre standard perchè basato su files (tipo le vecchie _fread, 
_fwrite etc). Quanta memoria usare lo deciderà l'OS dentro _fopen.
cmq, già che ci sei, sai se esistono funzioni standard (temo di 
no) per i MMF ?
ciao
Soviet


 i MMF ?
Direi proprio di no.
L'esistenza dei MMF implica l'esistenza di memoria virtuale gestita con 
un memory manager che possa usare il disco come back-storage.
Inoltre implica che il memory manager stesso possa usare un qualunque 
file e non solo una zona del disco predefinita.
Inoltre implica che il memory manager stesso esporti una serie di API 
per gestire il suo funzionamento e i suoi mappaggi.
Infine implica che esista un layer che esporti la necessaria interfaccia 
verso lo userspace.
Direi che sono un pochino troppe implicazioni non solo per lo standard 
C/C++ ma anche per il Posix (almeno credo).