CODEWITHSUNDEEP
perlstring
sigjuice
sigjuice

Reputation: 29757

How can I pre-allocate a string in Perl?

I have a Perl script that crunches a lot of data. There are a bunch of string variables that start small but grow really long due to the repeated use of the dot (concatentation) operator. Will growing the string in this manner result in repeated reallocations? If yes, is there a way to pre-allocate a string?

Upvotes: 13

Views: 3836

Answers (6)

chaos
chaos

Reputation: 124317

Alternate suggestion that will be much easier to cope with: push the strings onto an array and join it when you're done.

Upvotes: 8

Kent Fredric
Kent Fredric

Reputation: 57364

Perl's strings are mutable, so appending to a string does NOT incur a string duplication penalty.

You can try all you want to find a "faster" way, but this smells really bad of premature optimization.

For an example, I whipped up a class that abstracted away the hard work. It works perfectly, but it's, for all its goofy tricks, really slow.

Here's the result: 

         Rate  magic normal
magic  1.72/s     --   -93%
normal 23.9/s  1289%     --

Yes, that's right, Perl is 1200% faster than what I thought was a respectable implementation.

Profile your code and find what the real problems are, don't try optimising stuff that isn't even a known problem. 

#!/usr/bin/perl

use strict;
use warnings;

{

    package MagicString;
    use Moose;

    has _buffer => (
        isa => 'Str',
        is  => 'rw',
    );
    has _buffer_size => (
        isa     => 'Int',
        is      => 'rw',
        default => 0,
    );
    has step_size => (
        isa     => 'Int',
        is      => 'rw',
        default => 32768,
    );
    has _tail_pos => (
        isa     => 'Int',
        is      => 'rw',
        default => 0,
    );

    sub BUILD {
        my $self = shift;
        $self->_buffer( chr(0) x $self->step_size );
    }

    sub value {
        my $self = shift;
        return substr( $self->{buffer}, 0, $self->{_tail_pos} );
    }

    sub append {
        my $self  = shift;
        my $value = shift;
        my $L     = length($value);
        if ( ( $self->{_tail_pos} + $L ) > $self->{_buffer_size } ){
            $self->{buffer} .= (chr(0) x $self->{step_size} );
            $self->{_buffer_size} += $self->{step_size};
        }
        substr( $self->{buffer}, $self->{_tail_pos}, $L, $value );
        $self->{_tail_pos} += $L;
    }
    __PACKAGE__->meta->make_immutable;
}


use Benchmark qw( :all :hireswallclock );

cmpthese( -10 , {
        magic => sub{
            my $x = MagicString->new();
            for ( 1 .. 200001 ){
                $x->append( "hello");
            }
            my $y = $x->value();
        },
        normal =>sub{
            my $x = '';
            for ( 1 .. 200001 ){
                $x .= 'hello';
            }
            my $y = $x;
        }
    });
#use Data::Dumper;
#print Dumper( length( $x->value() ));

Upvotes: 7

hpavc
hpavc

Reputation:

I would go the array/join way:

push(@array, $crunched_bit)

And then $str = join('', @array), if nothing more, to have access to all the elements for debugging at some later time.

Upvotes: 0

Motti
Motti

Reputation: 114735

I don't know specifically how Perl strings are implemented but a pretty good guess is that it's constant amortized time. This means that even if you do find a way to pre-allocate your string chances are that the combined time it will save for all the script's users will be less than the time you spent asking this question on Stack Overflow.

Upvotes: 3

Schwern
Schwern

Reputation: 165004

Yes, Perl growing a string will result in repeated reallocations. Perl allocates a little bit of extra space to strings, but only a few bytes. You can see this using Devel::Peek. This reallocation is very fast and often does not actually copy the memory. Trust your memory manager, that's why you're programming in Perl and not C. Benchmark it first!

You can preallocate arrays with $#array = $num_entries and a hash with keys %hash = $num_keys but length $string = $strlen doesn't work. Here's a clever trick I dug up on Perlmonks.

my $str = "";
vec($str, $length, 8)=0;
$str = "";

Or if you want to get into XS you can call SvGROW().

chaos' suggestion to use an array and then join it all together will use more than double the memory. Memory for the array. Memory for each scalar allocated for each element in the array. Memory for the string held in each scalar element. Memory for the copy when joining. If it results in simpler code, do it, but don't think you're saving any memory.

Upvotes: 16

Kevin Beck
Kevin Beck

Reputation: 2390

Yes, pre-extending strings that you know will grow is a good idea.

You can use the 'x' operator to do this. For example, to preallocate 1000 spaces:

$s = " " x 1000:

Upvotes: -2

Related Questions