This is what I mean by an end-to-end benchmark:

#! perl -slw
use strict; use Config;
use Inline C => Config => BUILD_NOISY => 1;
use Inline C => <<'END_C',  NAME => 'diffBench', CLEAN_AFTER_BUILD =>0
+;

SV *diffAoA( U32 n ) {
    AV *av = newAV();
    U32 i;

    for( i = 0; i < n/2; ++i ) {
        AV *av2 = newAV();
        av_push( av2, newSViv( i*2   ) );
        av_push( av2, newSViv( i*2+1 ) );
        av_push( av, (SV*)av2 );
    }
    return newRV_noinc( (SV*)av );
}

SV *diffPacked( U32 n ) {
    U32 *diffs = malloc( sizeof( U32 ) * n );
    SV *packed;
    U32 i;

    for( i = 0; i < n; ++i ) {
        diffs[ i ] = i;
    }
    packed = newSVpv( (char *)diffs, sizeof( U32 ) * n );
    free( diffs );
    return packed;
}

SV *diff2dString( U32 n ) {
    SV *diffs = newSVpv( "", 0 );
    U32 i;

    for( i = 0; i < n/2; ++i ) {
        sv_catpvf( diffs, "%u:%u ", i*2, i*2+1 );
    }
    return diffs;
}

void diffList( U32 n ) {
    inline_stack_vars;
    U32 i;

    inline_stack_reset;
    for( i = 0; i < n; ++i ) {
        inline_stack_push( sv_2mortal( newSViv( i ) ) );
    }
    inline_stack_done;
    inline_stack_return( n );
    return;
}

END_C
use Data::Dump qw[ pp ];
use Benchmark qw[ cmpthese ];

our $N //= 10;

cmpthese -1, {
    AoA => q[
        my $AoA = diffAoA( $N ); # pp $AoA;
        for my $pair ( @{ $AoA } ) {
            my( $x, $y ) = @{ $pair };
        }
    ],
    packed => q[
        my $packed = diffPacked( $N ); # pp $packed;
        while( length( $packed ) ) {
            my( $x, $y ) = unpack 'VV', substr( $packed, 0, 8, '' );
        }
    ],
    twoDel => q[
        my $string2d = diff2dString( $N ); # pp $string2d;
        for my $pair ( split ' ', $string2d ) {
            my( $x, $y ) = split ':', $pair;
        }
    ],
    list => q[
        my @array = diffList( $N ); # pp \@array;
        while( @array ) {
            my( $x, $y ) = ( shift @array, shift @array );
        }
    ],
};

__END__
C:\test>diffBench.pl -N=10
           Rate twoDel    AoA packed   list
twoDel  66743/s     --   -41%   -52%   -62%
AoA    113285/s    70%     --   -19%   -36%
packed 139015/s   108%    23%     --   -21%
list   175732/s   163%    55%    26%     --

C:\test>diffBench.pl -N=100
          Rate twoDel    AoA packed   list
twoDel  7440/s     --   -57%   -59%   -66%
AoA    17343/s   133%     --    -4%   -21%
packed 18033/s   142%     4%     --   -17%
list   21849/s   194%    26%    21%     --

C:\test>diffBench.pl -N=1000
         Rate twoDel    AoA packed   list
twoDel  704/s     --   -58%   -64%   -67%
AoA    1678/s   139%     --   -15%   -22%
packed 1965/s   179%    17%     --    -8%
list   2143/s   205%    28%     9%     --

C:\test>diffBench.pl -N=10000
         Rate twoDel    AoA packed   list
twoDel 67.0/s     --   -61%   -67%   -68%
AoA     173/s   158%     --   -16%   -18%
packed  205/s   205%    19%     --    -3%
list    212/s   216%    23%     3%     --

C:\test>diffBench.pl -N=100000
         Rate twoDel    AoA packed   list
twoDel 6.14/s     --   -63%   -69%   -70%
AoA    16.4/s   167%     --   -18%   -21%
packed 20.1/s   227%    22%     --    -3%
list   20.8/s   238%    26%     4%     --

C:\test>diffBench.pl -N=1000000
          Rate twoDel    AoA packed   list
twoDel 0.121/s     --   -93%   -94%   -94%
AoA     1.64/s  1251%     --   -17%   -22%
packed  1.97/s  1523%    20%     --    -7%
list    2.11/s  1636%    28%     7%     --
[download]

It surprised me how badly the two delimiters idea worked out; and how fast simply returning a list was.