#! /usr/bin/perl -w

use strict;
use Inline C => Config => CC => 'clang', OPTIMIZE => '-O3';
use Inline C => <<'__CUT__', NAME => 'm300k';

#define elt I32

static void
results(elt n, elt *v[])
{
    Inline_Stack_Vars;
    Inline_Stack_Reset;
    if (n == 1) {
        elt *p = v[0], c, i = -1 + *p++;
        for (;;) {
            for (c = 1; i > 0 && p[0] != p[1]; p++, i--) {}
            if (i <= 0) break;
            for (c = 1; i > 0 && p[0] == p[1]; p++, i--) { c++; }
            if (c < 4) continue;
            Inline_Stack_Push(sv_2mortal(newSViv(*p)));
            Inline_Stack_Push(sv_2mortal(newSViv(c)));
        }
    }
    Inline_Stack_Done;
}

static void
merge2(elt *d, elt *a, elt *b)
{
    elt i, *ae = a + *a + 1, *be = b + *b + 1;
    *d++ = *a++ + *b++;
    while (i = (ae-a < be-b ? ae-a : be-b)) {
        for (; i; i--) *d++ = *a < *b ? *a++ : *b++;
    }
    if (!(ae-a)) 
        a = b, ae = be;
    memcpy(d, a, (ae-a) * sizeof(*a));
}

// increase stack size if this segfaults (or use malloc)
static void
nmerge(elt n, elt *v[])
{
    elt i, j;
    if (n < 2)
        return results(n, v);
    for (j = 0, i = n&1; i < n; i++) { j += *v[i] + 1; }
    elt tmp[j];
    for (j = 0, i = n&1; i < n; i++) {
        elt *a = v[i], *b = v[--n];
        merge2((v[i] = &tmp[j]), a, b);
        j += *v[i] + 1;
    }
    nmerge(n, v);
}
void vmatch(AV *vv)
{
    elt i, n = 1 + av_len(vv);
    elt *v[n];
    for (i = 0; i < n; i++) {
        v[i] = (elt*)SvPV_nolen(*av_fetch(vv, i, 0));
    }
    nmerge(n, v);
}
__CUT__

my @A;
sub uniq { keys %{{map {$_ => 1} @_}} }
push @A, pack "l/l", sort {$a <=> $b}
        uniq map int rand(5e6), 1..10000+rand(100) for 1..30;

use Benchmark qw(timethis);
timethis -5, sub { my @r = vmatch(\@A) };
[download]