2010-07-14 7 views
14

Voy a almacenar 350M números dobles precalculados en un archivo binario, y los cargaré en la memoria cuando se inicie mi dll. ¿Existe alguna forma de cargarlo en paralelo, o debería dividir los datos en varios archivos y cuidar yo mismo varios hilos?Cargue rápidamente números 350M en una matriz doble [] en C#

Respondiendo a los comentarios: Voy a ejecutar este dll en cajas lo suficientemente poderosas, muy probablemente solo en las de 64 bits. Debido a que todo el acceso a mis números será a través de las propiedades de todos modos, puedo almacenar mis números en varias matrices.

[Actualización]

Todo el mundo, gracias por responder! Estoy esperando mucho benchmarking en diferentes cajas. Acerca de la necesidad: Quiero acelerar un cálculo muy lento, por lo que voy a calcular previamente una cuadrícula, cargarla en la memoria y luego interpolarla.

+6

+1 para wow factor – northpole

+0

No veo por qué tendrías que dividir en varios archivos. Usted sabe cuántas líneas hay (suponiendo 1 número/línea), por lo que puede hacer que diferentes hilos comiencen a leer el archivo en diferentes desplazamientos. – FrustratedWithFormsDesigner

+4

¿No es esto como 2.6 gigas de datos? –

Respuesta

7

La primera pregunta que presumiblemente ya ha respondido es "¿tiene que calcularse previamente?". ¿Hay algún algoritmo que pueda usar que permita calcular los valores requeridos según demanda para evitar este problema? Asumiendo que no ...

Eso es solo 2.6GB de datos - en un procesador de 64 bits no tendrá problemas con una cantidad tan pequeña de datos como esa. Pero si se está ejecutando en una computadora de 5 años con un sistema operativo de 10 años, entonces no es un iniciador, ya que esa cantidad de datos llenará inmediatamente el conjunto de trabajo disponible para una aplicación de 32 bits.

Un enfoque que sería obvio en C++ sería utilizar un archivo mapeado en memoria. Esto hace que los datos aparezcan en su aplicación como si estuvieran en la memoria RAM, pero el sistema operativo en realidad solo publica partes de ellos a medida que se accede, por lo que se usa muy poca RAM real. No estoy seguro de si podría hacer esto directamente desde C#, pero podría hacerlo fácilmente en C++/CLI y luego acceder desde C#.

Por otra parte, suponiendo que la pregunta "¿Qué se necesita toda ella en la memoria RAM de forma simultánea" se ha respondido con un "sí", entonces usted no puede ir para cualquier tipo de enfoque de virtualización, así que ...

Cargando en varios subprocesos no será de ayuda; usted va a tener E/S encuadernado, por lo que tendrá n hilos esperando datos (y pidiendo al disco duro que busque entre los fragmentos que están leyendo) en lugar de un subproceso waiitng para datos (que se lee de forma secuencial, sin búsquedas). Entonces, los hilos solo causarán más búsqueda y, por lo tanto, pueden hacerlo más lento. (El único caso en el que dividir los datos podría ayudar es si los divide en diferentes discos físicos para poder leer diferentes fragmentos en paralelo; no haga esto en el software; compre una matriz RAID)

El único El lugar donde puede ayudar el multihilo es hacer que la carga suceda en el fondo mientras se inicia el resto de la aplicación, y permitir que el usuario empiece a usar la parte de los datos que ya está cargada mientras el resto del búfer se llena, por lo que el usuario (con suerte) no tiene que esperar mucho mientras se cargan los datos.

Por lo tanto, has vuelto a cargar los datos en una matriz masiva en un solo hilo ...

Sin embargo, puede ser capaz de acelerar este proceso considerablemente mediante la compresión de los datos. Hay un par de enfoques generales valió la pena considerar:

  • Si usted sabe algo acerca de los datos, que puede ser capaz de inventar un esquema de codificación que hace que los datos más pequeño (y por lo tanto más rápido para cargar). p.ej. si los valores tienden a estar cerca el uno del otro (por ejemplo, imagina los puntos de datos que describen una onda sinusoidal (los valores van desde muy pequeños a muy grandes, pero cada valor es solo un pequeño incremento desde el último) es posible que puedas represente los 'deltas' en un flotador sin perder la precisión de los valores dobles originales, reduciendo a la mitad el tamaño de los datos. Si hay alguna simetría o repetición de los datos, es posible que pueda explotarla (por ejemplo, imagine almacenar todas las posiciones para describir un círculo completo, en lugar de almacenar un cuadrante y usar un poco de matemática trivial y rápida para reflejarlo 4 veces; forma fácil de reducir la cantidad de datos de E/S). Cualquier reducción en el tamaño de los datos daría una reducción correspondiente en el tiempo de carga. Además, muchos de estos esquemas permitirían que los datos permanezcan "codificados" en la memoria RAM, por lo que utilizaría mucha menos memoria RAM, pero aún así sería capaz de buscar rápidamente los datos cuando fueran necesarios.

  • Como alternativa, puede ajustar fácilmente su flujo con un algoritmo de compresión genérico como Desinflar. Puede que esto no funcione, pero generalmente el costo de descomprimir los datos en la CPU es menor que el tiempo de E/S que guardas al cargar menos datos de origen, por lo que el resultado neto es que se carga significativamente más rápido. Y por supuesto, ahorre una carga de espacio en disco también.

+1

¡La compresión aceleró drásticamente las cargas, gracias! –

+0

@AlexKuznetsov: Cool. Me alegro de que haya ayudado. :-) –

9

Parece extremadamente improbable que pueda encajar esto en una matriz contigua en la memoria, por lo que presumiblemente la forma en que paraleliza la carga depende de la estructura de datos real.

(Adición:.. LukeH señaló en los comentarios que en realidad hay un límite duro de 2 GB en el tamaño del objeto en el CLR Esto se detalla en this other SO question)

Suponiendo que usted está leyendo todo el asunto de un disco, paralelizar las lecturas del disco es probablemente una mala idea. Si hay algún procesamiento que necesite hacer a los números como o después de cargarlos, puede considerar ejecutarlos en paralelo al mismo tiempo que está leyendo desde el disco.

+1

I puedo escribir un programa que contenga esa cantidad de datos en una matriz contigua en la memoria de mi computadora portátil de 5 años. Esto no es tan improbable. – liori

+2

@lion: Es curioso ... ¿Cuánta memoria tienes y en qué punto obtienes la 'OutOfMemoryException'? El mío ni siquiera puede acercarse a crear la matriz doble de entrada de 350M. –

+1

Mi estación de trabajo Dell Precision de 8GB de RAM aquí no puede hacerlo. – mquander

2

Eso no suena como una buena idea para mí. 350,000,000 * 8 bytes = 2,800,000,000 bytes. Y si se logra evitar la OutOfMemoryException el proceso puede ser el canje de entrada/salida del archivo de página de todos modos. También podría dejar los datos en el archivo y cargar los mandriles más pequeños a medida que se necesiten. El punto es que sólo porque usted puede destinar esta cantidad de memoria no significa que usted debe .

+3

Aquí hacen muchas suposiciones sobre la máquina que el OP usará –

+2

@Martin: el OP tiene la responsabilidad de indicar cuáles son las restricciones de hardware; sin ninguna información sobre eso, entonces tiene sentido razonar de manera conservadora. Francamente, esto tampoco me parece una buena idea. Si tuviera 350 millones de flotadores en el disco, nunca trataría de leerlos todos en la memoria a la vez. Los habría leído en pedazos, según sea necesario. Esta es una idea perfectamente sensata. –

+1

@Martin: Ese es un buen punto especialmente a la luz de la edición de la pregunta. Edité mi respuesta en consecuencia. –

1

Con una configuración de disco adecuada, dividir en varios archivos en los discos tendría sentido, y la lectura de cada archivo en un subproceso independiente funcionaría bien (si tiene algo de strip-less RAID), entonces podría tener sentido para leer desde un solo archivo con múltiples hilos).

Creo que estás en un escondite a nada intentando esto con un solo disco físico, sin embargo.

5

En el caso típico, la velocidad de carga estará limitada por la velocidad de almacenamiento desde la que está cargando los datos, es decir. disco duro.

Si quiere que sea más rápido, necesitará usar un almacenamiento más rápido, es decir, múltiples discos duros unidos en un esquema RAID.

Si los datos se pueden comprimir razonable, hacer eso. Intenta encontrar un algoritmo que use exactamente la potencia de CPU que tengas, menos que eso y tu velocidad de almacenamiento externo será factor limitante; más que eso y la velocidad de tu CPU será un factor limitante. Si su algoritmo de compresión puede usar múltiples núcleos, entonces multihilo puede ser útil.

Si sus datos son de alguna manera predecibles, es posible que desee crear un esquema de compresión personalizado. F.e. si los números consecutivos están cerca el uno del otro, es posible que desee almacenar las diferencias entre los números --- esto podría ayudar a la eficiencia de la compresión.

¿Realmente necesita doble precisión? ¿Tal vez las carrozas harán el trabajo? ¿Tal vez no necesitas un rango completo de dobles? Por ejemplo, si necesita 53 bits completos de precisión de mantisa, pero solo necesita almacenar números entre -1.0 y 1.0, puede intentar cortar algunos bits por número al no almacenar exponentes en rango completo.

3

Hacer este paralelo sería una mala ideamenos que esté ejecutando en un SSD. El factor limitante será el disco IO, y si ejecuta dos hilos, la cabeza va a saltar hacia adelante y hacia atrás entre las dos áreas que se leen. Esto ralentizará mucho más que cualquier aceleración posible de la paralelización.

Recuerde que las unidades son dispositivos MECANICOS y son increíblemente lentos en comparación con el procesador. Si puedes hacer un millón de instrucciones para evitar una sola búsqueda de cabeza, seguirás adelante.

Además, una vez que el archivo está en el disco, asegúrese de desfragmentar el disco para asegurarse de que esté en un bloque contiguo.

12

Bueno, hice una pequeña prueba y definitivamente recomendaría usar archivos asignados de memoria. Creé un archivo que contiene 350M de valores dobles (2.6 GB como se mencionó anteriormente) y luego probé el tiempo que toma para asignar el archivo a la memoria y luego acceder a cualquiera de los elementos.

En todas mis pruebas en mi computadora portátil (Win7, .Net 4.0, Core2 Duo 2.0 GHz, 4GB de RAM) tardé menos de un segundo en mapear el archivo y en ese momento acceder a cualquiera de los elementos tomó prácticamente 0ms (todos el tiempo está en la validación del índice). Luego, decidí revisar todos los números de 350M y todo el proceso tomó aproximadamente 3 minutos (se incluyeron los mensajes de paginación), por lo que si en su caso tiene que iterar, puede ser otra opción.

Sin embargo, me envolvió el acceso, sólo para propósitos de ejemplo allí unas condiciones mucho que se debe comprobar antes de utilizar este código, y parece que este

 

public class Storage<T> : IDisposable, IEnumerable<T> where T : struct 
{ 
    MemoryMappedFile mappedFile; 
    MemoryMappedViewAccessor accesor; 
    long elementSize; 
    long numberOfElements; 

    public Storage(string filePath) 
    { 
     if (string.IsNullOrWhiteSpace(filePath)) 
     { 
      throw new ArgumentNullException(); 
     } 

     if (!File.Exists(filePath)) 
     { 
      throw new FileNotFoundException(); 
     } 

     FileInfo info = new FileInfo(filePath); 
     mappedFile = MemoryMappedFile.CreateFromFile(filePath); 
     accesor = mappedFile.CreateViewAccessor(0, info.Length); 
     elementSize = Marshal.SizeOf(typeof(T)); 
     numberOfElements = info.Length/elementSize; 
    } 

    public long Length 
    { 
     get 
     { 
      return numberOfElements; 
     } 
    } 

    public T this[long index] 
    { 
     get 
     { 
      if (index < 0 || index > numberOfElements) 
      { 
       throw new ArgumentOutOfRangeException(); 
      } 

      T value = default(T); 
      accesor.Read<T>(index * elementSize, out value); 
      return value; 
     } 
    } 

    public void Dispose() 
    { 
     if (accesor != null) 
     { 
      accesor.Dispose(); 
      accesor = null; 
     } 

     if (mappedFile != null) 
     { 
      mappedFile.Dispose(); 
      mappedFile = null; 
     } 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     T value; 
     for (int index = 0; index < numberOfElements; index++) 
     { 
      value = default(T); 
      accesor.Read<T>(index * elementSize, out value); 
      yield return value; 
     } 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     T value; 
     for (int index = 0; index < numberOfElements; index++) 
     { 
      value = default(T); 
      accesor.Read<T>(index * elementSize, out value); 
      yield return value; 
     } 
    } 

    public static T[] GetArray(string filePath) 
    { 
     T[] elements; 
     int elementSize; 
     long numberOfElements; 

     if (string.IsNullOrWhiteSpace(filePath)) 
     { 
      throw new ArgumentNullException(); 
     } 

     if (!File.Exists(filePath)) 
     { 
      throw new FileNotFoundException(); 
     } 

     FileInfo info = new FileInfo(filePath); 
     using (MemoryMappedFile mappedFile = MemoryMappedFile.CreateFromFile(filePath)) 
     { 
      using(MemoryMappedViewAccessor accesor = mappedFile.CreateViewAccessor(0, info.Length)) 
      { 
       elementSize = Marshal.SizeOf(typeof(T)); 
       numberOfElements = info.Length/elementSize; 
       elements = new T[numberOfElements]; 

       if (numberOfElements > int.MaxValue) 
       { 
        //you will need to split the array 
       } 
       else 
       { 
        accesor.ReadArray<T>(0, elements, 0, (int)numberOfElements); 
       } 
      } 
     } 

     return elements; 
    } 
} 
 

Aquí está un ejemplo de cómo se puede utilizar la clase

 

Stopwatch watch = Stopwatch.StartNew(); 
using (Storage<double> helper = new Storage<double>("Storage.bin")) 
{ 
    Console.WriteLine("Initialization Time: {0}", watch.ElapsedMilliseconds); 

    string item; 
    long index; 

    Console.Write("Item to show: "); 
    while (!string.IsNullOrWhiteSpace((item = Console.ReadLine()))) 
    { 
     if (long.TryParse(item, out index) && index >= 0 && index < helper.Length) 
     { 
      watch.Reset(); 
      watch.Start(); 
      double value = helper[index]; 
      Console.WriteLine("Access Time: {0}", watch.ElapsedMilliseconds); 
      Console.WriteLine("Item: {0}", value); 
     } 
     else 
     { 
      Console.Write("Invalid index"); 
     } 

     Console.Write("Item to show: "); 
    } 
} 
 

ACTUALIZACIÓN I añadió un método estático para cargar todos los datos en un archivo a una matriz. Obviamente, este enfoque lleva más tiempo inicialmente (en mi computadora portátil tarda entre 1 y 2 minutos) pero después de eso, el rendimiento de acceso es lo que espera de .Net. Este método debería ser útil si tiene que acceder a los datos con frecuencia.

uso es bastante simple

double[] helper = Storage<double>.GetArray("Storage.bin");

HTH

+0

Agradezco la sugerencia, ¡gracias! No fui por eso porque solo leer desde un archivo comprimido era lo suficientemente rápido, y era más simple. –

+0

Realmente bueno saber y definitivamente es mejor "mantener es simple" – CriGoT

0

acabo de ver esto: .NET 4.0 tiene soporte para memory mapped files. Esa sería una forma muy rápida de hacerlo, y no se necesita soporte para la paralelización, etc.