On Mon, Jun 18, 2012 at 12:30 PM, Tim Haines
<[email protected]> wrote:
> Hi, Chris.
>
>
>>> I'm assuming that pnpoly_pp is actually pnpolyfill_pp?
>
> pnpoly_pp is just a pure PP version of the C code from
> http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html. I
> did this so that it would allow users to have access to a very fast pnpoly
> routine if they are just looking for the mask and do not need the
> pnpolyfill[v] functionality. pnpolyfill_pp was implemented separately, but
> using essentially the copy/paste of pnpoly_pp.
Ok, although it is usually better to write some perl
code to call pp_def() to generated both routines
from the same code---avoids the case where one
routine is modified but not the other.
>>> It would be better to have the pnpolyfill/pnpolyfillv accept an
>>> option to use the PP version or the plain perl/PDL level code.
>
> My apologies- I did not explain myself well enough. My thinking was that the
> pnpolyfill[v] functions would only be using the pnpoly_pp functionality
> since it has significant advantages over the PDL::pnpoly version. Aside from
> simplifying the testing syntax, I struggle to understand why a user would
> willfully use PDL::pnpoly instead of pnpoly_pp. Perhaps I am too myopic.
This was more a matter of how to stage the development.
The proposed route is usually good to allow for things to
be fully tested and incrementally developed. In the case
where one has a "developer on fire" (TM) then a lot of the
stages can be skipped. :-)
> Here is a quick overview of what I was envisioning for the
> PDL::Image2D::poly* namespace:
>
> # Leave these alone for backwards compatibility (but update the docs to let
> people know of the pnpoly* versions)
> PDL::pnpoly
Since the PP and non-PP implementations do the
same thing---just better, the pnpoly routine should
be migrated to use pnpoly_pp under the hood.
> polyfill
> PDL::polyfillv
Yes
> # Add these
> PDL::pnpolyfill
> PDL::pnpolyfillv
Yes
> pnpolyfill_pp
> pnpoly_pp
I recommend these be internal routines only
since all the functionality should be exposed
in pnpolyfill and pnpolyfillv.
> with
>
>
> 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;
> pnpolyfill_pp($im,$ps,$col);
> return $im;
> }
>
> and
>
>
> sub PDL::pnpolyfillv :lvalue {
> my ($im, $ps) = @_;
> barf("ps must contain pairwise points.\n") unless $ps->getdim(0) == 2;
>
> # Here, we have the choice of creating the mask
> # in the current space and calling pnpolyfill_pp like
> # what is done in PDL::polyfillv, or we can just have
> # pnpoly_pp create the intermediate mask for us
> # chose the latter to keep this as small as possible.
> return $im->where(pnpoly_pp($im, $ps));
> }
>
> still being Perl/PDL functions so that high-level checks on the inputs can
> be made and still have access to a fast pnpoly implementation.
>
> I have written some tests to validate that the results of these pnpoly*
> routines provide the same results as using PDL::pnpoly and masking
> techniques, and have found complete agreement with much improved speed. I
> will include these tests in the t/image2d.t test suite.
>
> I apologize for the protracted discussion on these enhancements. This being
> my first true interlude into PP, I tried to proceed with trepidation, but
> inevitably blundered along the way. I have learned a quite a bit about the
> PP architecture from this exercise, and it has greatly increased my
> enthusiasm for using PDL.
>
> I shall await approval on these proposed changes before proceeding.
Look good to me. Once we have some more user experience
with the new routine, we could prepare to make polyfill and
polyfillv call the pnpoly routines under the hood with a flag
to control the option. Followed by deprecation of the old
implementation.... Yes, a bit tedious but we're trying not
to break PDL out from under users.
Thanks for the hard work and coding,
Chris
> Thank you much for your patience.
>
> - Tim
> On Mon, Jun 18, 2012 at 8:18 AM, Chris Marshall <[email protected]>
> wrote:
>>
>> 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
