2012-03-16 15 views
8

Quiero crear y manipular grandes matrices de enteros (de 4 bytes) en memoria. En general, me refiero al orden de cientos de millones. Cada celda en la matriz actuará como un contador para una posición en un cromosoma. Todo lo que necesito es que encaje en la memoria y tenga acceso rápido (O (1)) a los elementos. Lo que estoy contando no es una característica escasa, así que no puedo usar una matriz dispersa.Arrays tipo C en perl

No puedo hacer esto con una lista perl normal, porque perl (al menos en mi máquina) usa 64 bytes por elemento, por lo que los genomas de la mayoría de los organismos con los que trabajo son demasiado grandes. Intenté almacenar los datos en el disco a través de SQLite y hash atar, y aunque funcionan, son muy lentos, especialmente en las unidades comunes. (Funciona razonablemente bien cuando corro en incursiones de 4 unidades).

pensé que podría utilizar matrices PDL, b/c PDL almacena sus arrays tal como lo hace C, utilizando sólo 4 bytes por elemento. Sin embargo, he encontrado que la velocidad de actualización para que sea muy lento en comparación con las listas de Perl:

use PDL; 
use Benchmark qw/cmpthese/; 

my $N = 1_000_000; 
my @perl = (0 .. $N - 1); 
my $pdl = zeroes $N; 

cmpthese(-1,{ 
    perl => sub{ 
     $perl[int(rand($N))]++; 
    }, 
    pdl => sub{ 
     # note that I'm not even incrementing here just setting to 1 
     $pdl->set(int(rand($N)), 1); 
    } 
}); 

devuelve:

  Rate pdl perl 
pdl 481208/s -- -87% 
perl 3640889/s 657% --  

¿alguien sabe cómo aumentar conjunto PDL() el rendimiento, o sabe de un módulo diferente que puede lograr esto?

+1

¿Ha estudiado los módulos perl bioinformáticos? – AlfredoVR

Respuesta

8

no puedo decir qué tipo de rendimiento que obtendrá, pero recomiendo el uso de la función vec, documentó here, para dividir una cadena en campos de bits. He experimentado y he descubierto que Perl tolerará una cadena de hasta 500_000_000 caracteres de longitud. que corresponde a 125,000,000 de valores de 32 bits.

my $data = "\0" x 500_000_000; 
vec($data, 0, 32)++;   # Increment data[0] 
vec($data, 100_000_000, 32)++; # Increment data[100_000_000] 

Si esto no es suficiente, puede haber algo en la construcción de Perl que controle el límite. Alternativamente, si usted cree que puede conseguir campos más pequeños - dice el recuento de 16 bits - vec aceptará ancho de los campos de cualquier potencia de 2 hasta 32.

Editar: creo que el límite de tamaño de la cadena está relacionado con el máximo de 2 GB trabajo privado configurado en procesos de Windows de 32 bits. Si está ejecutando Linux o tiene un Perl de 64 bits, puede ser más afortunado que yo.


He añadido a su programa de referencia como éste

my $vec = "\0" x ($N * 4); 

cmpthese(-3,{ 
    perl => sub{ 
     $perl[int(rand($N))]++; 
    }, 
    pdl => sub{ 
     # note that I'm not even incrementing here just setting to 1 
     $pdl->set(int(rand($N)), 1); 
    }, 
    vec => sub { 
     vec($vec, int(rand($N)), 32)++; 
    }, 
}); 

dando estos resultados

  Rate pdl vec perl 
pdl 472429/s -- -76% -85% 
vec 1993101/s 322% -- -37% 
perl 3157570/s 568% 58% -- 

por lo que usar vec es dos tercios de la velocidad de una matriz nativa. Presumiblemente eso es aceptable.

2

PDL gana cuando las operaciones se pueden enhebrar, al parecer no está optimizado para el acceso aleatorio y la asignación. Tal vez alguien con más conocimiento PDL podría ayudar.

+0

No es el acceso aleatorio, sino el tiempo de inicio para inicializar las estructuras de datos PDL. Dependiendo del cálculo involucrado, PDL requiere de 100-1000 elementos para ser procesados ​​antes de alcanzar el mismo rendimiento con operaciones perl nativas. Con su soporte para bucles implícitos, una línea de código PDL puede reemplazar múltiples bucles escalares o de listas anidados en perl simple. – chm

+0

Usted sería el mejor para saber, gracias por el comentario. Ciertamente hay mejores respuestas publicadas para esta pregunta ahora que la mía. :-) –

2

Packed::Array en CPAN podría ayudar.

Packed :: Array proporciona una clase de matriz de enteros con signo lleno. Las matrices creadas con Packed :: Array solo pueden contener enteros con signo que coincidan con los enteros nativos de la plataforma, pero solo toman la cantidad de memoria necesaria para contener esos enteros. Por lo tanto, para sistemas de 32 bits, en lugar de tomar aproximadamente 20 bytes por entrada de matriz, solo toman 4.

+2

Sí, he visto este módulo, así como 'Tie :: Array :: Pack',' Tie :: Array :: Packed', 'Tie :: VecArray' y' Tie :: Array :: PackedC '. Desafortunadamente, la API Perl 'tie' es muy lenta y la más rápida (' Tie :: Array :: Packed') sigue siendo diez veces más lenta que las matrices nativas. – Borodin

7

El comando PDL desea es indadd. (Gracias a Chris Marshall, PDL Pumpking, por señalarlo me elsewhere.)

PDL está diseñado para lo que llamo "operaciones vectorizadas". En comparación con las operaciones en C, las operaciones de Perl son bastante lentas, por lo que debe mantener el número de invocaciones al método PDL al mínimo y hacer que cada invocación haga mucho trabajo. Por ejemplo, este punto de referencia le permite especificar el número de actualizaciones para realizar de una sola vez (como un parámetro de línea de comandos). El lado Perl tiene que bucle, pero el lado PDL sólo realiza cinco o así llamadas a funciones:

use PDL; 
use Benchmark qw/cmpthese/; 

my $updates_per_round = shift || 1; 

my $N = 1_000_000; 
my @perl = (0 .. $N - 1); 
my $pdl = zeroes $N; 

cmpthese(-1,{ 
    perl => sub{ 
     $perl[int(rand($N))]++ for (1..$updates_per_round); 
    }, 
    pdl => sub{ 
     my $to_update = long(random($updates_per_round) * $N); 
     indadd(1,$to_update,$pdl); 
    } 
}); 

Cuando ejecuto esto con un argumento de 1, I empeorar aún más el rendimiento que cuando se utiliza set, que es lo que yo esperado:

$ perl script.pl 1 
      Rate pdl perl 
pdl 21354/s -- -98% 
perl 1061925/s 4873% -- 

¡Eso es mucho terreno para recuperar! Pero espera ahí. Si hacemos 100 iteraciones por ronda, se obtiene una mejora:

$ perl script.pl 100 
     Rate pdl perl 
pdl 16906/s -- -18% 
perl 20577/s 22% -- 

Y con 10.000 actualizaciones por ronda, PDL supera a Perl en un factor de cuatro:

$ perl script.pl 10000 
     Rate perl pdl 
perl 221/s -- -75% 
pdl 881/s 298% -- 

PDL sigue llevando a cabo más o menos 4 veces más rápido que Perl simple para valores aún mayores.

Tenga en cuenta que el rendimiento de PDL puede degradarse para operaciones más complejas. Esto se debe a que PDL asignará y destruirá espacios de trabajo grandes pero temporales para operaciones intermedias. En ese caso, es posible que desee considerar el uso de Inline::Pdlpp. Sin embargo, esa no es una herramienta para principiantes, así que no saltes hasta que hayas determinado que es lo mejor para ti.

Otra alternativa a todo esto es el uso de Inline::C así:

use PDL; 
use Benchmark qw/cmpthese/; 

my $updates_per_round = shift || 1; 

my $N = 1_000_000; 
my @perl = (0 .. $N - 1); 
my $pdl = zeroes $N; 
my $inline = pack "d*", @perl; 
my $max_PDL_per_round = 5_000; 

use Inline 'C'; 

cmpthese(-1,{ 
    perl => sub{ 
     $perl[int(rand($N))]++ for (1..$updates_per_round); 
    }, 
    pdl => sub{ 
     my $to_update = long(random($updates_per_round) * $N); 
     indadd(1,$to_update,$pdl); 
    }, 
    inline => sub{ 
     do_inline($inline, $updates_per_round, $N); 
    }, 
}); 


__END__ 

__C__ 

void do_inline(char * packed_data, int N_updates, int N_data) { 
    double * actual_data = (double *) packed_data; 
    int i; 
    for (i = 0; i < N_updates; i++) { 
     int index = rand() % N_data; 
     actual_data[index]++; 
    } 
} 

Para mí, la función en línea gana a ambos Perl y PDL. Para valores más grandes de $updates_per_round, digamos 1,000, obtengo la versión Inline::C aproximadamente 5 veces más rápido que Perl puro y entre 1.2x y 2x más rápido que PDL. Incluso cuando $updates_per_round es solo 1, donde Perl supera a PDL, el código en línea es 2.5 veces más rápido que el código Perl.

Si esto es todo lo que necesita para llevar a cabo, le recomiendo usar Inline::C.

Pero si necesita realizar muchas manipulaciones a sus datos, lo mejor es seguir con PDL por su potencia, flexibilidad y rendimiento. Vea a continuación cómo puede usar vec() con datos PDL.

4

PDL::set() y PDL::get() están destinados más como una ayuda para el aprendizaje que otra cosa. Constituyen la forma más simple de acceder a las variables PDL. Sería mucho mejor utilizar algunas de las rutinas integradas de acceso masivo. El constructor PDL acepta listas de Perl:

$pdl = pdl(@list) 

y es razonablemente rápido. También puede cargar sus datos directamente desde un archivo ASCII usando PDL::rcols, o desde un archivo binario usando una de muchas rutinas IO.Si usted tiene los datos como una cadena embalado con el fin de la máquina, incluso se puede acceder a la memoria PDL directamente:

$pdl = PDL->new_from_specification(long,$elements); 
$dr = $pdl->get_dataref; 
$$dr = get_my_packed_string(); 
$pdl->upd_data; 

También tenga en cuenta que puede "tener su pastel y comérselo también" mediante el uso de objetos PDL mantener sus matrices de números enteros, cálculos PDL (como indadd) para la manipulación a gran escala de los datos, sino también utilizar vec() directamente en los datos PDL como una cadena que se puede obtener a través de la get_dataref método:

vec($$dr,int(rand($N)),32); 

Necesitarás bswap4 los datos si estás en un sistema little-endian:

$pdl->bswap4; 
$dr = $pdl->get_dataref; 
vec($$dr,int(rand($N)),32)++; 
$pdl->upd_data; 
$pdl->bswap4; 

Et, voila!

2

ya estaban usando números enteros, lo que debería ser aceptable para su uso con los cromosomas probar esto

use PDL; 
use Benchmark qw/cmpthese/; 

my $N = 1_000_000; 
my @perl; 
@perl = (0 .. $N - 1); 
my $pdl; 
$pdl = (zeroes($N)); 

cmpthese(-1,{ 
perl => sub{ 
    $perl[int(rand($N))]++; 
}, 
pdl2 => sub{ 
    # note that I'm not even incrementing here just setting to 1 
    $pdl->set(int(rand($N)), 1); 
    $pdl2 = pack "w*", $pdl; 
} 
}); 

y hacia fuera puesto que obtuve de esta era ...

  Rate pdl2 perl 
pdl2 46993/s -- -97% 
perl 1641607/s 3393% -- 

que muestra una gran diferencia de rendimiento desde la primera vez que probé este código sin añadiendo en mis 2 centavos obtuve

  Rate pdl perl 
pdl 201972/s -- -86% 
perl 1472123/s 629% -- 
0

Mi respuesta anterior puede ser inútil ... aunque esto podría ayudar ..

use PDL; 
$x = sequence(45000,45000); 

ahora que no funcionará a menos que tenga 16 GB de RAM y utilizar

$PDL::BIGPDL=1;