Come devo gestire un array molto grande in Java?

Question

Ho un algoritmo che attualmente assegna una grande serie di doppie, che aggiorna e cerca di frequente. La dimensione dell'array è N^2/2, dove N è il numero di righe su cui opera l'algoritmo. Devo anche conservare una copia dell'intera cosa per scopi associati all'applicazione che circonda l'algoritmo.

Naturalmente questo impone un limite al numero di righe che il mio algoritmo può gestire come ho la limitazione mucchio da affrontare. Fino a questo punto sono riuscito a chiedere alle persone che usano l'algoritmo di aggiornare l'impostazione -Xmx per allocare più spazio e che ha funzionato bene. Tuttavia, ora ho un vero problema in cui ho bisogno di questo array per essere più grande di quello che posso inserire in memoria.

ho già intenzione di cambiare il mio algoritmo per mitigare la necessità di questa grande varietà e hanno alcuni risultati promettenti in quel dominio. Tuttavia si tratta di una modifica sostanziale al processo e richiederà molto più lavoro prima che arrivi alla condizione molto lucido del mio codice corrente che opera nella produzione di grande successo ed è stato per diversi anni.

Quindi, mentre sto perfezionando il mio nuovo algoritmo, ho voluto estendere la vita di quello esistente e ciò significa affrontare la limitazione dell'heap associata all'assegnazione della mia vasta gamma di doppi.

La mia domanda è che cosa è il modo migliore di trattare con esso? Dovrei usare un nio FileChannel e un MappedByteBuffer, o c'è un approccio migliore. Se utilizzo l'approccio nio, quale tipo di impatto sulle prestazioni dovrei aspettarmi di fare rispetto a un array in-memory della stessa dimensione?

Grazie

Answer 1

Se si esegue su PC, le dimensioni di pagina per i file mappati sono probabilmente di 4 kilobyte.

Quindi la domanda inizia davvero se inizio a scambiare i dati su disco, "quanto è casuale il mio accesso casuale alla RAM-che-è-ora-un-file"?

E (... posso e se è così ...) come posso ordinare il doppio per massimizzare i casi in cui si accede ai doppi in una pagina 4K insieme piuttosto che pochi alla volta in ogni pagina prima del prossimo 4K recupero del disco?

Se si utilizza l'IO standard, probabilmente si desidera ancora leggere e scrivere in blocchi, ma i blocchi potrebbero essere più piccoli. I settori saranno almeno 512 byte, i cluster di dischi più grandi, ma quale dimensione di lettura è migliore dato che c'è un overhead del kernel round trip per ogni IO?

Mi dispiace, ma temo che i tuoi migliori passi successivi dipendano in gran parte dall'algoritmo e dai dati che stai utilizzando.

Answer 2

Se si inizia a corto di memoria disponibile, allora si avrà probabilmente anche presto iniziare a corto di indici di matrice disponibili, una matrice è delimitata per dimensioni a Integer.MAX_VALUE, e che quando si utilizza doppie gli elementi dell'array sono "solo" da 32 GB.

Ottenere una macchina con 32GB di memoria è costoso, ma probabilmente non così costoso come il tempo di modificare l'algoritmo, e tutto il test associato.

Tuttavia, se il client è in esecuzione sui bordi della memoria e i relativi set di dati sono ancora in crescita, allora è logico che si morda il proiettile e apportare le modifiche per poter utilizzare meno memoria in qualsiasi dato tempo, dal momento che probabilmente supereranno presto un array comunque.

L'altra opzione che si ha, supponendo che l'array sia un po 'riempita scarsamente, è quella di utilizzare una delle varie strutture di dati di array sparse, sebbene queste tendano a essere utili solo se l'array è pieno meno del 20%.

Modifica: Poiché sembra che abbiate già studiato le alternative, il MappedByteBuffer potrebbe essere la strada da percorrere. Ovviamente questo avrà un impatto sulle prestazioni, tuttavia se si eseguono per lo più letture e scritture sequenziali dall'array, questo non dovrebbe essere un problema. Se stai facendo letture e scritture casuali, questo diventerà molto lento molto velocemente. O molto lentamente molto lentamente ... a seconda di come guardi queste cose ;-)

Answer 3

Ti stai muovendo nel regno di come scrivere software che utilizza una cache (come nella cache di memoria nella CPU) migliore. È difficile farlo correttamente e il modo "giusto" per farlo dipende da come è stato progettato il tuo algoritmo.

Quindi, che cosa fa il tuo programma in modo algoritmico?

Answer 4

Si può provare a memorizzare l'array come righe in una tabella di database e utilizzare proc memorizzati per eseguire aggiornamenti e ricerche su di esso.

Un'altra idea:

Utilizzare un B-Tree come l'array e tenere alcune foglie su disco. Assicurati di rendere i nodi di B-Tree le dimensioni di una pagina o le dimensioni di più pagine.

Answer 5

Se il problema è che si sta esaurendo la memoria, la soluzione semplice è aggiornare l'hardware con più memoria, aumentare le dimensioni dell'heap Java e/o passare a una JVM 64-bi5t.

D'altra parte, se si sta andando a scapito del limite di Java sulla dimensione degli array, è possibile scendere lungo la rotta ByteBuffer, oppure è possibile passare all'utilizzo di una matrice di array. La versione successiva è la soluzione alternativa suggerita da Sun.

Con l'approccio dell'array si può (in teoria) far fronte ai valori di N vicino a . In pratica il limite sarà determinato dalla quantità di memoria fisica disponibile e dall'ammontare che può essere risolto utilizzando la combinazione di OS/JVM.

Answer 6

Ho avuto generalmente buone esperienze con MappedByteBuffers di Java e vi incoraggio a dare un'occhiata più approfondita. Può benissimo permetterti di non affrontare nuovamente le modifiche -Xmx. Tenere presente che se sono necessari più di 2-4 GB di spazio indirizzabile, sono necessari una CPU a 64 bit, OS e JVM.

Per superare il problema degli indici Integer.MAX_VALUE è possibile scrivere un algoritmo di paging, come ho fatto qui in una risposta correlata a Binary search in a sorted (memory-mapped ?) file in Java.

Answer 7

Tenere presente che alcuni sistemi operativi supportano meglio la mappatura della memoria rispetto ad altri.

sarei tentato di fare questo:

1. mettere tutte le Array Ottiene/mette dietro un'interfaccia oggetto (se non lo sono già) liberando così fino a cambiare facilmente l'implementazione.
2. Utilizzare un array di SoftReference in cui ogni SoftReference punta alla matrice di doppi per quella riga. Utilizzare un ReferenceQueue per salvare gli array sul disco quando il GC li rilascia. Quando get() restituisce null, recupera dal disco.

Potresti scoprire che hai un maggiore controllo sulle prestazioni in questo modo: il -Xmx può essere modificato come desiderato.