Re^2: Very Large Arrays

[dave_the_m]

A 43 million element array of 20-ish character strings should come in well below 4GB.

On a 64-bit system with a modern perl, it uses about 3.5Gb, assuming that the strings and the array were created in the most efficient way possible. Based on the OPs comments, I would guess they aren't being generated in the most efficient way possible; and together with the overhead of whatever the rest of code does, that swap really is an issue.

In that case, it may be worth the OP's while to try an initial sequential read of the the array to get all the elements swapped backed in, before hitting random elements. Whether this will increase performance is pure speculation at this point.

Another possibility is to use a single large string, divided into blocks of 20 chars, to avoid the overhead of the array and SVs; then access individual elements using substr().

Dave.

[BrowserUk]

On a 64-bit system with a modern perl, it uses about 3.5Gb, assuming that the strings and the array were created in the most efficient way possible.

As much as that? I based my estimate upon this (running 5.10.1 64-bit):

c:\test>p1
[0] Perl> 
sub shuffle { 
    my $r = shift; 
    for ( 0 .. $#$r ) { 
        my $a = $_ + rand( @$r - $_ ); 
        my $t = $r->[ $a ]; 
        $r->[ $a ] = $r->[ $_ ]; 
        $r->[ $_ ] = $t; 
    }; 
};;

[0] Perl> @a = 1 .. 1e6;;
[0] Perl> push @a, @a;;
[0] Perl> push @a, @a;;
[0] Perl> push @a, @a;;
[0] Perl> push @a, @a;;

[0] Perl> $t = time; shuffle \@a; print time - $t;;
20.9429998397827

[0] Perl> print total_size \@a;;
518218064

That's 16 million integers occupying just under 500MB being shuffled in 20 seconds.

I reasoned that 3 times that gives 48M in 1.5GB. Then replace the ints with the pointers and add 48mx20 (rounded up to 24) = 1.01GB for the strings themselves. gives 2.5GB total; and around 60 seconds to shuffle. Did I miss something?

Another possibility is to use a single large string, divided into blocks of 20 chars, to avoid the overhead of the array and SVs; then access individual elements using substr().

I had similar thoughts. On the basis of the single pair of numbers the OP gave as an example, it looks like floats would be sufficient precision for his purposes. In which case, a packed string shuffled with substr seemed possible:

c:\test>p1
[0] Perl> sub shuffle { 
    my $r = shift; 
    my $n = length( $$r ) / 8; 
    for ( 0 .. $n ) { 
        my $a = $_ + rand( $n - $_ ); 
        my $t = substr $$r, $a, 8; 
        substr $$r, $a, 8, substr $$r, $_, 8; 
        substr $$r, $_, 8, $t; 
    }; 
};;

[0] Perl> $a = pack 'f*', map -1e5 + rand(1e9), 1 .. 1e6;;
[0] Perl> $a x= 96;;

[0] Perl> print length $a;;
384000000

[0] Perl> $t = time; shuffle \$a; print time - $t;;
59.6950001716614

It really rather surprised me that the shuffle time was so close to my estimate for the array of strings. (Despite needing 4 substrs per.)

[dave_the_m]

I reasoned that 3 times that gives 48M in 1.5GB. Then replace the ints with the pointers and add 48mx20 (rounded up to 24) = 1.01GB for the strings themselves. gives 2.5GB total; and around 60 seconds to shuffle. Did I miss something?

Yes: an int is stored entirely within an SV head, whereas a string needs an SV body too, as well as the string itself (which may also have some malloc overhead).

I used the following code to get my estimate:

my $max = 10_000_000;
my @a;
system "ps -flyp $$";
$a[$max] = 0; # pre-extend array
$a[$_] = '4.90032E-8,1.25327E-7' for 0..$max;
system "ps -flyp $$";

Dave.