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. >> 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. 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 polyfill PDL::polyfillv # Add these PDL::pnpolyfill PDL::pnpolyfillv pnpolyfill_pp pnpoly_pp 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. I 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. 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
