¿Cómo debo lidiar con una matriz muy grande en Java?

Tengo un algoritmo que actualmente asigna una gran variedad de dobles, que actualiza y busca con frecuencia. El tamaño de la matriz es N^2/2, donde N es el número de filas en las que opera el algoritmo. También tengo que guardar una copia de todo el contenido para fines relacionados con la aplicación que rodea el algoritmo.¿Cómo debo lidiar con una matriz muy grande en Java?

Por supuesto, esto impone un límite en el número de filas que mi algoritmo puede manejar ya que tengo que lidiar con la limitación del montón. Hasta este punto me he salido con la tarea de pedirle a las personas que usan el algoritmo que actualicen la configuración -Xmx para asignar más espacio, y eso ha funcionado bien. Sin embargo, ahora tengo un problema real en el que necesito que esta matriz sea más grande de lo que puedo guardar en la memoria.

Ya tengo planes para cambiar mi algoritmo para mitigar la necesidad de este gran conjunto y tener algunos resultados prometedores en ese dominio. Sin embargo, es una alteración fundamental del proceso y requerirá mucho más trabajo antes de que llegue a la condición muy pulida de mi código actual, que está funcionando en la producción con mucho éxito y lo ha sido durante varios años.

Por lo tanto, mientras estoy perfeccionando mi nuevo algoritmo, quería extender la vida del existente y eso significa abordar la limitación de montón asociada con la asignación de mi enorme variedad de dobles.

Mi pregunta es ¿cuál es la mejor manera de manejarlo? ¿Debo usar un nio FileChannel y un MappedByteBuffer, o hay un mejor enfoque? Si uso el enfoque nio, ¿qué tipo de impacto de rendimiento debo esperar en comparación con un arreglo en memoria del mismo tamaño?

Gracias

Fuente

2009-12-16 Simon

Supongo que no podría procesar los datos en trozos? – Seth

Desafortunadamente no con esta implementación. Eso es lo que hace mi nueva implementación, pero hay toda una serie de problemas adicionales asociados con la combinación de los resultados del fragmento de nuevo. – Simon

¿ha considerado utilizar una base de datos? – pstanton

Si está ejecutando en PC, es probable que los tamaños de página para los archivos asignados sean de 4 kilobytes.

Así que la pregunta realmente comienza si empiezo a intercambiar los datos en el disco, "¿qué tan aleatorio es mi acceso aleatorio a la RAM-que-es-ahora-un-archivo"?

Y (... puedo y si es así ...) cómo puedo ordenar los dobles para maximizar los casos donde se accede a los dobles dentro de una página de 4K juntos en lugar de unos pocos en cada página antes de los próximos 4K búsqueda de disco?

Si usa la E/S estándar, probablemente aún desee leer y escribir en trozos, pero los trozos podrían ser más pequeños. Los sectores tendrán al menos 512 bytes, los clústeres de discos serán más grandes, pero ¿qué tamaño de lectura es mejor dado que hay una sobrecarga de ida y vuelta del kernel para cada IO?

Lo siento, pero me temo que sus mejores pasos dependen en gran medida del algoritmo y de los datos que está utilizando.

Fuente

2009-12-16 23:02:07 martinr

+1 Este es un buey muy bueno, gracias. Me doy cuenta de que hay mucho más en mi pregunta y dependerá de cómo funciona mi algoritmo, pero esto me da algunos parámetros para juzgarlos, que es lo que estaba esperando. – Simon

Admito que teniendo en cuenta los problemas de tamaño de caché L2 en el diseño también es importante. – martinr

Citando a ChrisW: "Estoy sorprendido: la figura 3 en el medio de http://queue.acm.org/detail.cfm?id=1563874 dice que la memoria es solo aproximadamente 6 veces más rápida cuando se hace acceso secuencial (350 Mvalues / seg para la memoria en comparación con 58 Mvalues / seg para el disco), pero es aproximadamente 100.000 veces más rápido cuando haces acceso aleatorio ". http://stackoverflow.com/questions/1371400/how-much-faster-is-the-memory-usually-than-the-disk – martinr

Si usted está comenzando a quedarse sin memoria disponible, entonces es probable que también pronto comenzará a funcionar fuera de los índices de matriz disponibles, una matriz está limitada en tamaño a Integer.MAX_VALUE, y que cuando se utiliza dobles, los elementos de la matriz son "solo" de 32 GB de tamaño.

Obtener una máquina con 32 GB de memoria es costoso, pero probablemente no tan caro como su tiempo para modificar el algoritmo, y todas las pruebas asociadas.

Sin embargo, si el cliente se está ejecutando en los bordes de la memoria, y sus conjuntos de datos siguen creciendo, entonces tiene sentido que muerda la viñeta ahora y realice los cambios para poder utilizar menos memoria en cualquier momento tiempo, ya que es probable que pronto superen una matriz de todos modos.

La otra opción que tiene, suponiendo que la matriz está un tanto escasamente ocupada, es usar una de las diversas estructuras de datos de matriz dispersa, aunque estas solo son beneficiosas si su matriz está llena menos del 20%.

Editar: Dado que parece que ya ha investigado las alternativas, entonces el MappedByteBuffer bien podría ser el camino a seguir. Obviamente, esto tendrá un impacto en el rendimiento, sin embargo, si realiza principalmente lecturas y escrituras secuenciales desde la matriz, entonces esto no debería ser tan malo. Si está haciendo lecturas y escrituras aleatorias, esto va a ser muy lento muy rápido. O muy lento muy lentamente ... dependiendo de cómo veas estas cosas ;-)

Fuente

2009-12-16 22:52:57

+1 para resaltar los costos de hardware versus desarrollo –

Probablemente sea cierto que sería más económico obtener una caja más grande, sin embargo, esta no es una respuesta muy apetecible para el cliente. La conversación hasta ahora se ha ido Cliente: "se ha bloqueado de nuevo" Yo: "aumentar la memoria asignada a la JVM". Si mi próxima respuesta es "comprar una computadora nueva con 32 Gb de RAM", retrocederán. De hecho, el código está suficientemente abstraído que creo que puedo inyectar una clase de matriz diferente en tiempo de ejecución. Entonces mi riesgo se limita a la calidad de mi implementación de una matriz basada en nio. – Simon

parece que la respuesta a la recuperación de memoria más es "espere hasta que se complete el nuevo algoritmo". ¿Es mejor dedicar tu tiempo a trabajar en el nuevo algoritmo o cuidar al anterior? ¿Tiene alguna métrica de rendimiento para el nuevo algoritmo que puede presentar para persuadir al cliente? – basszero

Te mueves en el dominio de cómo escribir software que utiliza mejor un caché (como en la memoria caché en la CPU). Esto es difícil de hacer bien, y la forma "correcta" de hacerlo depende de cómo esté diseñado su algoritmo.

Entonces, ¿qué hace su programa realmente de forma algorítmica?

Fuente

2009-12-16 22:58:38

Si respondo, ¿prometes no decirme que implemente mi algoritmo de otra manera? El problema que creo que tendré al responder su pregunta es que tengo un algoritmo ineficiente para empezar. Lo sé y estoy bien en arreglarlo. Lo que estoy buscando es una forma de extender su vida para darme tiempo de completar esa reimplementación. Lamento ser un poco corto, pero lo que necesito ahora es una respuesta a mi pregunta sobre los pros y los contras de nio para mi problema inmediato. – Simon

@Simon, no podemos contarte sobre eso a menos que sepamos las características del algoritmo. Por ejemplo, si realiza muchas búsquedas binarias en la matriz de elementos dispares, probablemente tenga problemas. Sin embargo, si pasa mucho tiempo en un área más pequeña y luego se mueve a otra área, entonces su almacenamiento en caché y disco IO podrían tener éxito. – tster

@Simon, no estoy interesado en su elección de algoritmo, pero estoy interesado en el comportamiento del que ha elegido.A menudo, la elección de qué orden iterar las dimensiones de una matriz multidimensional es importante, p. –

Puede intentar almacenar la matriz como filas en una tabla de base de datos y usar procesos almacenados para realizar actualizaciones y búsquedas en ella.

Otra idea:

Uso de un árbol B que incluía la matriz y tener algunas hojas en el disco. Asegúrese de hacer que los nodos del B-Tree tengan el tamaño de una página o el tamaño de varias páginas.

Fuente

2009-12-16 23:03:31 tster

Lo he considerado y tengo mucha experiencia con las bases de datos. En este caso, lo que me detiene es que explota enormemente la complejidad de la solución que pongo frente a mi cliente. En algún momento puedo avanzar hacia el uso de una base de datos para cierta persistencia, pero en este momento juzgo que es un exceso de sobrecarga para mi problema actual, que se trata simplemente de extender la vida útil del algoritmo existente. – Simon

Si el problema es que se está quedando sin memoria, la solución simple es actualizar su hardware con más memoria, aumentar el tamaño del almacenamiento dinámico de Java y/o cambiar a una JVM 64-bi5t.

Por otro lado, si se está ejecutando contra el límite de Java en el tamaño de las matrices, puede ir por la ruta de ByteBuffer, o puede cambiar a utilizar una matriz de matrices. La última es la solución sugerida por Sun.

Con el arreglo array of arrays, podría (en teoría) hacer frente a los valores de N cerca de 2**31. En la práctica, su límite estará determinado por la cantidad de memoria física que tenga y la cantidad que se puede abordar con su combinación de OS/JVM.

Fuente

2009-12-17 03:52:04

En general, he tenido buenas experiencias con MappedByteBuffers de Java, y lo aliento a que lo analice más detenidamente. Muy bien, puede permitirle no tratar los cambios -Xmx nuevamente. Tenga en cuenta que si necesita más de 2-4 GB de espacio direccionable, entonces se requieren una CPU, sistema operativo y JVM de 64 bits.

Para ir más allá de la cuestión de los índices Integer.MAX_VALUE puede escribir un algoritmo de paginación, como he hecho aquí en una respuesta relacionada al Binary search in a sorted (memory-mapped ?) file in Java.

Fuente

2009-12-17 11:38:25

¡Ja! Acababa de escribir una lista de buscapersonas de MappedByteBuffers, es agradable ver la solución de otra persona. En mi caso, no tengo un archivo preexistente para mapear, así que voy a tener un archivo de página separado para cada bloque de Integer.MAX_INT dobla. Esto tiene una ventaja adicional para mí en el sentido de que puedo engendrar un hilo para hacer una gran parte de la búsqueda y así aprovechar los otros procesadores que sé que están cayendo y sin usar. Tengo la sospecha de que puedo ampliar el tamaño de mi algoritmo y hacerlo más rápido al mismo tiempo. Ya veremos. Gracias por la publicación +1 – Simon

Me alegra oír eso :) Siempre estuve muy satisfecho con esa respuesta. * En cuanto a sus ideas de rendimiento, * asegúrese de comprobar si la CPU es el cuello de la botella y no el disco. Si los últimos procesos/subprocesos múltiples que acceden a diferentes partes del disco a la vez pueden impedir su rendimiento general. Incluso si es el primero, un enfoque mesurado para agregar hilos es una buena idea. (Lección aprendida de la manera más dura para mí;) –

Tenga en cuenta que algunos sistemas operativos tienen mejor soporte para la asignación de memoria que otros.

estaría tentado de hacer esto:

poner todo su matriz es/pone detrás de una interfaz de objeto (si no lo son ya) liberando así que hasta cambiar fácilmente la aplicación.
Usa una matriz de referencias suaves donde cada referencia suave señala la matriz de dobles para esa fila. Use una ReferenceQueue para guardar las matrices en el disco cuando el GC las expulsa. Cuando get() devuelve null, recupera desde el disco.

Es posible que tenga más control sobre el rendimiento de esa manera: el -Xmx se puede ajustar según lo desee.

Fuente

2009-12-17 14:24:21

¿Cómo debo lidiar con una matriz muy grande en Java?

Respuesta

Cuestiones relacionadas