25 de febrero de 2011

Rendimiento de estructuras de datos en Perl

Buenas,
recientemente, tratando de resolver las dudas de un principiante en Perl, he podido volver a constatar la dificultad que suponen para los novatos los vectores (@arrays) y las tablas asociativas (%hashes). Sin embargo, estas estructuras de datos son muy empleadas por usuarios experimentados, puesto que permiten guardar y modelar datos complejos de manera relativamente sencilla. No obstante, después de tanto tiempo usando estas estructuras, creo que nunca me he puesto a medir el coste de un vector y de un hash para guardar los mismos datos en un programita Perl. Este coste es especialmente relevante para manejar volúmenes de datos grandes, como averiguaremos con ayuda de los módulos Benchmark y Devel::Size.

Si además invocamos el módulo GraphViz::Data::Grapher, podremos dibujar ambos tipos de estructuras de datos, lo cual puede ayudar a los más principiantes:




 #!/usr/bin/perl -w  
   
 use strict;  
 use Benchmark;    
 use Devel::Size;   
 use Scalar::Util;  
 #use GraphViz::Data::Grapher;   
   
   
 my $MUESTRAS = 100;   
   
 # 1) mide tiempo de creacion de estructura de datos  
 print "# construyendo estructuras de datos:\n";  
 print "> hash :\n";  
 timethis( $MUESTRAS, "crea_estructura_datos('hash')" );  
 print "> array:\n";  
 timethis( $MUESTRAS, "crea_estructura_datos('array')" );  
   
 # 2) mide memoria que necesita cada estructura  
 print "\n# memoria RAM usada (KB):\n";  
 my $ref_hash = crea_estructura_datos('hash');  
 printf("\n> hash: %1.1f\n",  
    Devel::Size::total_size($ref_hash)/1024);  
   
 my $ref_array = crea_estructura_datos('array');  
 printf("> array: %1.1f\n",  
    Devel::Size::total_size($ref_array)/1024);  
      
 # 3) mide tiempo de consulta de estructura de datos  
 print "\n# consultando estructuras de datos:\n";  
 print "> hash:\n";  
 timethis( $MUESTRAS, sub{ consulta_estructura_datos($ref_hash) } );  
 print "> array:\n";  
 timethis( $MUESTRAS, sub{ consulta_estructura_datos($ref_array) } );     
   
 ############################################  
   
 sub crea_estructura_datos  
 {  
    my ($hash_o_array) = @_;   
   
     my $referencia;  
      
    if($hash_o_array eq 'hash')  
    {  
        foreach my $n (1..100_000)   
        {  
          # las llaves ocupan menos como cadenas de caracteres  
          # http://codenode.com/perl-memory-usage  
          $referencia->{"$n"} = $n * 10;         #7165.6KB en CPU 64bits  
         #$referencia->{sprintf("%01.3f",$n)} = $n * 10; #7556.2KB "  
          #$referencia->{$n/0.3} = $n * 10;        #7914.3KB "  
        }  
         
       #descomenta para generar grafo de estructura como el del blog  
       # OJO: mejor que sea una estructura no muy grande  
       #my $grafo = GraphViz::Data::Grapher->new($referencia);  
       #print $grafo->as_png("hash.png");  
     }  
    else  
    {  
       foreach my $n (1..100_000)   
        {  
         push(@{$referencia}, $n * 10);  # 3367.9KB           
          #$referencia->[$n-1] = $n * 10; # lo mismo  
        }  
         
       #my $grafo = GraphViz::Data::Grapher->new($referencia);  
       #print $grafo->as_png("array.png");  
    }  
   
    return $referencia;  
 }   
      
 sub consulta_estructura_datos  
 {  
    my ($referencia) = @_;   
      
    my $index;  
      
    if(Scalar::Util::reftype($referencia) eq "HASH")  
    {  
        foreach my $n (1..100_000)   
        {  
          $index = int(rand(100_000));  
          $referencia->{$index} += 1;   
        }  
     }  
    else  
    {  
       foreach my $n (1..100_000)   
        {  
         $index = int(rand(100_000));  
          $referencia->[$index] += 1;   
        }  
    }  
   
    return $referencia;  
 }   
   

Mediante este código, ejecutado en mi máquina de 64 bits, podemos ver que un hash sencillo ocupa un poco más del doble que un array para guardar una lista de enteros, y que su tamaño varía según el tipo de llave que usemos. Además, tardamos el triple de tiempo en llenar el hash que el array equivalente. Finalmente, este pequeño experimento muestra que el acceso y modificación de datos dentro un hash es al menos dos veces más lento que en un array:

# construyendo estructuras de datos:
> hash :
timethis 100: 10 wallclock secs (10.45 usr +  0.01 sys = 10.46 CPU) @  9.56/s (n=100)
> array:
timethis 100:  3 wallclock secs ( 2.17 usr +  0.00 sys =  2.17 CPU) @ 46.08/s (n=100)

# memoria RAM usada (KB):

> hash: 7165.6
> array: 3367.9

# consultando estructuras de datos:
> hash:
timethis 100:  6 wallclock secs ( 6.08 usr +  0.01 sys =  6.09 CPU) @ 16.42/s (n=100)
> array:
timethis 100:  3 wallclock secs ( 2.61 usr +  0.00 sys =  2.61 CPU) @ 38.31/s (n=100)

Un saludo,
Bruno

1 comentario:

  1. Aunque en el código se ve, sería recomendable indicar que también depende del sistema operativo utilizado.

    En los sistemas operativos Windows podríamos estar hablando, en algunos casos de pasar a un factor de tres (de décimas de segundos a decenas de minutos)

    Ejemplo:

    my $x;
    for (1 .. 100_000) { $x .= 'x' x 1_000 }

    Este ejemplo (descubierto en 2007), ejecutado en un XP, tardó 40 minutos en terminar, mientras que en un Linux (con el mismo hardware) solo tardó 0,40 segundos.

    (Parece ser que se trata de un problema de la gestión de memoria por parte del sistema operativo)

    ResponderEliminar