Depending on what you want to do, it might be faster to keep the data structure in C land and access it through a tied array or unpack from the Perl side. You can gain a tiny speedup by using av_make to create the array in the DIFF_MATCH case (see perlguts on working with arrays).

I would look at using "bind" variables and writing the data from e directly into these variables instead of (re)allocating new Perl data structures every time. DBI has this for the maximum speed at a cost of convenience.

Thx corion. I will try your ideas.But still shake my head about slowness of arrays.

Why not skip the AoAs and return a string with two delimiters? eg. "3:4 6:3 8:3";

It seems to be just as easy, and probably faster to do:

my $diffs = diff( .... );
for my $diff ( split ' ', $diffs ) {
    my( $start, $len ) = split ':', $diff;
    ## use start / len
}
[download]

As it is:

my $ref = diff( ... );

for my $pair ( @{ $ref } ) {
    my( $start, $len ) = @{ $pair };
    ## use start / len
}
[download]

This is magnitudes slower:

#!perl
use 5.006;

use strict;
use warnings;

use Benchmark qw(:all) ;
use Data::Dumper;

my $diffs = join(' ', (map { "$_:$_" } (0..49)));

    timethese( 50_000, {
       'split' => sub {
            my $LCS = [];
            for my $diff ( split ' ', $diffs ) {
                my( $x, $y ) = split ':', $diff;
                #push @$LCS, [$x,$y];
            }
        },
    });
############
~/github/LCS-XS/xt$ perl split.t 
Benchmark: timing 50000 iterations of split...
     split:  2 wallclock secs ( 2.04 usr +  0.00 sys =  2.04 CPU) @ 24
+509.80/s (n=50000)
[download]

24 kHz without push, with push 11 kHz.

The idea was to build the string in XS and give that to the caller; not build a string and then build the AoAs from the string; which of course will be slower as your still building the AoAs, but also building and the breaking down the string.

Ie. Build the string instead of the AoAs in XS; and give the caller the string instead of the AoAs; thus avoiding the building of the AoAs entirely.

Be sure to preallocate the string to (even much) bigger than will be required and then use set CUR to trim to the final size.

---

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.

I'm with torvalds on this Agile (and TDD) debunked I told'em LLVM was the way to go. But did they listen!

Other ideas to try.

Just push the pairs onto the stack and let the user assign that to a single level array:

my @diffs = diff( ... );
while( @diffs ) {
    my( $x, $y ) = ( pop @diffs, pop @diffs );
    ## use em.
}
[download]

Build a single level C array and return a SvPV that points to the head of that array:

U32 len = sizeof( U32 ) * some over estimate;
U32 *diffs =  malloc( len );
U32 i = 0;
SV *packed;

SvPV_Set( packed, diffs ); SvLEN_set( len )

for( ) {
    for( ) {
        diffs[ i++ ] = x;
        diffs[ i++ ] = y;
    {
}

SvCur_set( packed, ( i-1 ) * sizeof( U32 ) );

return packed; // sv_2mortal?
[download]

then use unpack to access the numbers:

my $diffs = diff( ... );

while( length( $diffs ) ) {
    my( $x, $y ) = unpack 'VV', substr( $diffs, 0, 8, '' );
    ## use em.
}
[download]

BrowserUK: Unpack in your above code also creates a list, which seems to be the same bottleneck. Benchmarks are in the same range.

Also tried List::Util::pairs(), which benchmarks a little faster. Maybe I can copy and inline this part of C code.

What I maybe will do now is providing different formats, AoA [2][L], AoA[L][2] and 2 bitstrings (match-index). Bitstrings should be very fast, but not so convenient to process. Perl5 does not have the functions lsb (index of lowest significant bit) and msb, which Perl6 has.

Unpack in your above code also creates a list,

Only a list of 2 elements? That why I showed using substr to nibble the packed array in pairs.

---

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.

I'm with torvalds on this Agile (and TDD) debunked I told'em LLVM was the way to go. But did they listen!