Come ottimizzare l'hash bidimensionale che attraversa in Perl?

Question

Ho un hash di hash %signal_db. Un elemento tipico è: $signal_db{$cycle}{$key}. Ci sono 10.000 di segnali e 10.000 di chiavi.

C'è un modo per ottimizzare (timewise) questo pezzo di codice:

foreach my $cycle (sort numerically keys %signal_db) { 
    foreach my $key (sort keys %{$signal_db{$cycle}}) { 
     print $signal_db{$cycle}{$key}.$key."\n"; 
    } 
} 

Gli elementi devono essere stampati nello stesso ordine come nel mio codice.

Answer 1

Due micro ottimizzazioni: mappa hash interno invece di costante dereferenziazione e buffer invece di stampa costante. È possibile eliminare l'ordinamento utilizzando formati di archiviazione alternativi, testate due varianti. Risultati:

   Rate  original   try3 alternative alternative2 
original  46.1/s   --   -12%   -21%   -32% 
try3   52.6/s   14%   --   -10%   -22% 
alternative 58.6/s   27%   11%   --   -13% 
alternative2 67.5/s   46%   28%   15%   -- 

Conclusione:

E 'meglio utilizzare il formato di archiviazione preselezionate ma senza C vittoria sarebbe probabilmente entro 100% (sul mio set di dati di test). Le informazioni fornite sui dati suggeriscono che le chiavi nell'hash esterno sono numeri quasi sequenziali, quindi questo piange per l'array.

Script:

#!/usr/bin/env perl 

use strict; use warnings; 
use Benchmark qw/timethese cmpthese/; 

my %signal_db = map { $_ => {} } 1..1000; 
%$_ = map { $_ => $_ } 'a'..'z' foreach values %signal_db; 

my @signal_db = map { { cycle => $_ } } 1..1000; 
$_->{'samples'} = { map { $_ => $_ } 'a'..'z' } foreach @signal_db; 

my @signal_db1 = map { $_ => [] } 1..1000; 
@$_ = map { $_ => $_ } 'a'..'z' foreach grep ref $_, @signal_db1; 

use Sort::Key qw(nsort); 

sub numerically { $a <=> $b } 

my $result = cmpthese(-2, { 
    'original' => sub { 
     open my $out, '>', 'tmp.out'; 
     foreach my $cycle (sort numerically keys %signal_db) { 
      foreach my $key (sort keys %{$signal_db{$cycle}}) { 
       print $out $signal_db{$cycle}{$key}.$key."\n"; 
      } 
     } 
    }, 
    'try3' => sub { 
     open my $out, '>', 'tmp.out'; 
     foreach my $cycle (map $signal_db{$_}, sort numerically keys %signal_db) { 
      my $tmp = ''; 
      foreach my $key (sort keys %$cycle) { 
       $tmp .= $cycle->{$key}.$key."\n"; 
      } 
      print $out $tmp; 
     } 
    }, 
    'alternative' => sub { 
     open my $out, '>', 'tmp.out'; 
     foreach my $cycle (map $_->{'samples'}, @signal_db) { 
      my $tmp = ''; 
      foreach my $key (sort keys %$cycle) { 
       $tmp .= $cycle->{$key}.$key."\n"; 
      } 
      print $out $tmp; 
     } 
    }, 
    'alternative2' => sub { 
     open my $out, '>', 'tmp.out'; 
     foreach my $cycle (grep ref $_, @signal_db1) { 
      my $tmp = ''; 
      foreach (my $i = 0; $i < @$cycle; $i+=2) { 
       $tmp .= $cycle->[$i+1].$cycle->[$i]."\n"; 
      } 
      print $out $tmp; 
     } 
    }, 
}); 

Answer 2

Proverei per la prima volta con lo Sort::Key module perché l'ordinamento richiede più tempo del semplice ciclo e della stampa. Inoltre, se le chiavi di hash interne sono (per lo più) identiche, allora dovresti semplicemente preselezionarle, ma suppongo che non sia così, altrimenti lo faresti già.

Dovresti ovviamente provare ad assegnare $ signal_db {$ cycle} anche a un riferimento. È possibile che each sia più veloce di keys più il recupero, soprattutto se utilizzato con Sort::Key. Verificerei se la mappa fosse più veloce di foreach, probabilmente la stessa cosa, ma chi lo sa. È possibile trovare print più veloce se si passa un elenco o si chiama più volte.

Non ho provato questo codice, ma gettare insieme tutte queste idee, tranne each dà:

foreach my $cycle (nsort keys %signal_db) { 
    my $r = $signal_db{$cycle}; 
    map { print ($r->{$_},$_,"\n"); } (nsort keys %$r); 
} 

C'è un articolo su di smistamento in perl here, controlla la Trasformata di Schwartz, se si vuole vedere come una potrebbe utilizzare each.

Se il codice non deve essere attenti alla sicurezza, allora si potrebbe plausibilmente disattivare la protezione di Perl contro algorithmic complexity attacks impostando PERL_HASH_SEED o legati variabili e/o ricompilare Perl con regolazione alterata, così keys e values comandi che di Perl restituite le chiavi o valori in ordine già ordinato, risparmiando così tempo considerevole per ordinarli. Ma per favore guarda this 28C3 talk prima di farlo. Non credo nemmeno che funzionerà, dovresti leggere questa parte del codice sorgente di Perl, forse più semplicemente implementando il tuo loop in C.

Answer 3

my %signal_db = map {$_ => {1 .. 1000}} 1 .. 1000; 

sub numerically {$a <=> $b} 
sub orig { 
    my $x; 
    foreach my $cycle (sort numerically keys %signal_db) { 
     foreach my $key (sort keys %{$signal_db{$cycle}}) { 
      $x += length $signal_db{$cycle}{$key}.$key."\n"; 
     } 
    } 
} 

sub faster { 
    my $x; 
    our ($cycle, $key, %hash); # move allocation out of the loop 
    local *hash;  # and use package variables which are faster to alias into 

    foreach $cycle (sort {$a <=> $b} # the {$a <=> $b} literal is optimized 
        keys %signal_db) { 
     *hash = $signal_db{$cycle}; # alias into %hash 
     foreach $key (sort keys %hash) { 
      $x += length $hash{$key}.$key."\n"; # simplify the lookup 
     } 
    } 
} 

use Benchmark 'cmpthese'; 
cmpthese -5 => { 
    orig => \&orig, 
    faster => \&faster, 
}; 

che ottiene:

 
     Rate orig faster 
orig 2.56/s  -- -15% 
faster 3.03/s 18%  -- 

Non un guadagno enorme, ma è qualcosa. Non è possibile ottimizzare molto di più senza modificare la struttura dei dati per utilizzare matrici preordinate.(o scrivere il tutto in XS)

Il passaggio dei loop foreach per utilizzare variabili del pacchetto esterno consente di risparmiare un po 'di tempo poiché perl non è necessario creare lessicali nel ciclo. Anche le variabili del pacchetto sembrano essere un po 'più veloci in alias. Anche ridurre la ricerca interiore a un singolo livello.

Suppongo che stiate stampando su STDOUT e quindi reindirizzando l'output su un file? In tal caso, utilizzare Perl per aprire direttamente il file di output e quindi stampare su quell'handle potrebbe consentire miglioramenti nelle prestazioni IO del file. Un'altra micro-ottimizzazione potrebbe essere quella di sperimentare diverse dimensioni dei record. Ad esempio, fa risparmiare tempo per costruire un array nel loop interno, quindi unirlo/stamparlo nella parte inferiore del ciclo esterno? Ma è qualcosa che è abbastanza dipendente dal dispositivo (e probabilmente inutile a causa di altri livelli di memorizzazione nella cache di IO), quindi lascerò questo test a te.