Hi, Chris.
>> 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% --
Should we export the pnpoly_pp function so that people can use it directly?
I will write some tests in the morning, then submit a patch to the mailing
list.
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
