Hi Tim-
The signature of pnpoly_pp is not quite the same:
seems like it should be something like:
x(m); y(m); px(k); py(k); int [o] msk(m)
At any rate, direct PP implementation of pnpolyfill
and/or pnpolyfillv would show a greater improvement
since replacing the xvals and yvals allocation and
calculation by the loop index for the corresponding
dimension is expected to be much more efficient.
I suggest add the perl level versions with tests.
Then you'll have a reference for the implementation
of the corresponding PP versions.
--Chris
On 6/17/2012 7:21 PM, Tim Haines wrote:
I have updated the two pnpolyfill functions as you listed below and the
documentation of all of the poly* routines to reflect the difference
between the pnpoly and the polyfill approach to determining set membership.
Before I submitted that patch, I wanted to take a stab at implementing
pnpoly in PP. Below is my first attempt.
pp_def('pnpoly_pp',
HandleBad => 1,
Pars => 'x(m,n); y(m,n); px(k); py(k); int [o] msk(m,n)',
Code => '
int a, b, i, j, c, nvert;
nvert = $SIZE(k);
#define TESTX $x(m=>a,n=>b)
#define TESTY $y(m=>a,n=>b)
#define VERTX(q) $px(k=>q)
#define VERTY(q) $py(k=>q)
for(b=0;b<$SIZE(n);b++) {
for(a=0;a<$SIZE(m);a++) {
c = 0;
for(i=0,j=nvert-1;i<nvert;j=i++) {
if( ((VERTY(i)>TESTY) != (VERTY(j)>TESTY)) &&
(TESTX < (VERTX(j)-VERTX(i)) *
(TESTY-VERTY(i)) / (VERTY(j)-VERTY(i)) + VERTX(i)) )
c = !c;
}
$msk(n=>b,m=>a) = c;
}
}
#undef TESTX
#undef TESTY
#undef VERTX(q)
#undef VERTY(q)
'
);
I also did a quick benchmark:
my $px = pdl(3,15,9);
my $py = pdl(3,3,9);
my $im = zeroes(20, 11);
my $ps = $px->cat($py)->xchg(0,1);
cmpthese(5e4,{
'pnpoly' => sub{pnpoly($im->xvals,$im->yvals,$px,$py)},
'pnpoly_pp' => sub{PDL::pnpoly_pp($im->xvals,$im->yvals,$px,$py)},
'polyfill' => sub{polyfill($im,$ps,1)}
});
Rate pnpoly pnpoly_pp polyfill
pnpoly 5241/s -- -72% -95%
pnpoly_pp 19011/s 263% -- -82%
polyfill 106383/s 1930% 460% --
There is a drastic improvement (~2.5x) over the current pnpoly
implementation, but it still lags well behind the polyfill in both runtime
and memory consumption. I was thinking that it might be possible to get
better runtime by making a function which operates on a single row and
using a threadloop in pnpoly_pp to run it over the image. Do you think
there would be much utility in that? I have a feeling most of the execution
time is in the allocation of x/yvals on the Perl call to pnpoly_pp, but I
was curious about what others' experience has been with something like this.
I haven't ever created test cases before and I didn't see a guide on the
PDL website, what are the sorts of things that are usually tested for?
Many thanks.
- Tim
On Sun, Jun 17, 2012 at 12:55 PM, chm <[email protected]> wrote:
Hi Tim-
Here are some candidate versions for pnpolyfill
and pnpolyfillv with some minor cleanup and
fixes including lvalue subroutine declaration.
sub PDL::pnpolyfill {
my ($im, $ps, $col) = @_;
barf("ps must contain pairwise points.\n") unless $ps->getdim(0) == 2;
barf("color not specified.\n") unless $col;
$im->where(pnpoly($im->xvals, $im->yvals, $ps->using(0,1))) .= $col;
}
sub PDL::pnpolyfillv :lvalue {
my ($im, $ps) = @_;
barf("ps must contain pairwise points.\n") unless $ps->getdim(0) == 2;
return $im->where(pnpoly($im->xvals, $im->yvals, $ps->using(0,1)));
}
--Chris
On 6/17/2012 9:03 AM, chm wrote:
Hi Tim-
Thanks for the patch.
After further consideration, how about we implement
a pnpolyfill and pnpolyfillv per your original
approach rather than coupling the two versions?
Where I'm going with this is that, ideally, we would
have a PP implementation of the pnpoly stuff which
would have good performance and the better algorithm.
All that would be needed are the two new routines
and some pnpoly cases for t/image2d.t in the PDL
test suite.
--Chris
On 6/16/2012 3:25 PM, Tim Haines wrote:
Hi, Chris.
I updated the documentation for polyfill and polyfillv, added the Perl
subroutine PDL::polyfill, and added the pnpoly option to polyfill and
polyfillv. I have attached the git diff file generated against the latest
repository. It builds and tests without issue against Perl 5.14.2 on
Ubuntu
12.04 x86_64.
Many thanks.
- Tim
_______________________________________________
Perldl mailing list
[email protected]
http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
