Re^3: Very Large Arrays

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
[download]

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
[download]

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.)

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

The start of some sanity?

Comment on Re^3: Very Large Arrays Select or Download Code

Replies are listed 'Best First'.
Re^4: Very Large Arrays by dave_the_m (Monsignor) on Feb 14, 2012 at 20:13 UTC
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 $$";` [download] Dave.	[reply] [d/l]

Replies are listed 'Best First'.

Re^4: Very Large Arrays
by dave_the_m (Monsignor) on Feb 14, 2012 at 20:13 UTC

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?

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 $$";
[download]

[reply]
[d/l]