laziness, impatience, and hubris PerlMonks

### Re^2: Comparing two arrays

by oiskuu (Hermit)
 on Dec 16, 2013 at 10:49 UTC ( #1067307=note: print w/replies, xml ) Need Help??

in reply to Re: Comparing two arrays

I wrote a crude implementation of merge(sort) to estimate the matching speed. 30 buckets each with ~10k sorted, "l/l" packed numbers (representing y-vector ID's). Merge and scan takes about 5 ms (unless I've botched it somewhere). Full search is ten minutes at that rate. Hm.
```#! /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) };

Update. SSE4.1 version doubled the performance.

Create A New User
Node Status?
node history
Node Type: note [id://1067307]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (2)
As of 2017-08-21 22:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (325 votes). Check out past polls.

Notices?