On Sun, Jun 17, 2012 at 10:37 PM, Tim Haines
<[email protected]> wrote:
>
>>> 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.
>
> Ah, but of course! I don't know what I was thinking.
>
> The updated version is much better.
> Rate pnpoly polyfill pnpoly_pp
> pnpoly 6784/s -- -93% -93%
> polyfill 100000/s 1374% -- -4%
> pnpoly_pp 104167/s 1435% 4% --
Cool! I'm assuming that pnpoly_pp is actually pnpolyfill_pp?
> Should we export the pnpoly_pp function so that people can use it directly?
It would be better to have the pnpolyfill/pnpolyfillv accept an
option to use the PP version or the plain perl/PDL level code.
That will also make possible testing to verify that we get the
same answer with either implementation. E.g.,
pnpolyfill($im,$ps,$col,{use_pp=>1}) # fast!
pnpolyfill($im,$ps,$col,{use_perl=>1}) # slow
pnpolyfill($im,$ps,$col) # use default engine
> I will write some tests in the morning, then submit a patch to the mailing
> list.
The general idea of tests is to do some calculation and
then check that the answer you got is what was expected.
Our PDL standard test module is Test::More but not all
existing tests have been migrated to use that. All new
tests should start with that.
As for tests, I suggest adding some for pnpolyfill, pnpolyfillv,
polyfill, polyfillv, with and without options. The polyfill ones
would be useful to demonstrate the difference between the
two implementations.
--Chris
> Many thanks for all of your help.
>
> - Tim
>
>
>
>
>
> On Sun, Jun 17, 2012 at 7:41 PM, chm <[email protected]> wrote:
>>
>> 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
