Hmm.. this optimization is exactly what the DD.selfX methods were supposed
to allow. I can see that a selfSqr method would be useful.
The DD API was trying to strike a balance between efficiency, ease of use
and simplicity. It certainly could be extended to provide more of the
first, at the expense of the latter two.
Feel free to post your enhancements for others to share.
On Wed, Apr 30, 2014 at 6:33 AM, Gary Lucas <[email protected]> wrote:
> I have a suggestion about modifications to the JTS DD class to yield
> higher performance for certain applications.
>
>
>
> The JTS DD class provides routines for extending the precision of
> floating-point arithmetic operations by representing numbers using
> two-doubles instead of one (attaining approximately 30 digits of decimal
> precision). Recently, I have been experimenting with using DD in a Java
> application I have for creating Triangulated Irregular Networks (TINs), or
> “triangular meshes”, from lidar data. One of the key operations in all
> triangular mesh building operations is the “in-circle” method which
> determines if an arrangement of neighboring points is triangulated in an
> optimal manner. This method gets called quite frequently. For a 1.02
> million points sample, my application performs about 18.7 in-circle
> tests. But because in-circle depends on the evaluation of a determinant
> that can often be very close to zero (but still significant), precision is
> an important consideration. Thus the motivation for using DD. In fact, the
> DD class actually includes an implementation of a method called
> DD.inCircleDDNormalized().
>
>
>
> The problem is that DD is substantially more expensive than straight
> floating-point operations. In my testing, I developed two routines, one
> that would use DD only when “absolutely necessary” and one that used it all
> the time. The runtimes for the application variations were:
>
>
>
> a) Standard floating point: 0.769 seconds
>
> b) Using DD: 8.078 seconds
>
>
>
> Part of that difference is unavoidable. Extended precision operations
> simply cost more than hardware-based calculations. But looking at the code
> I noticed that one of the features of DD is that in using it, you have to
> create a very large number of short-lived objects. For example, to add
> a+b, you need to create at least two DD objects (one for a, one for b, and
> then you can either store the result in a or produce a third object
> depending on whether or not you use one of what DD calls “self” methods).
> Once you create an object, there is no way to set their value so that they
> may be While Java has made great strides over the years in terms of
> handling the creation and garbage collection of large numbers of objects,
> it would be far more efficient if the DD objects could be reused.
>
>
>
> For example, I hacked a version of DD to add a couple of “set” methods
> that let me set the values of DD objects. I created all the DD objects I
> needed at application start up and used the set method to recycle them
> every time the in-circle method was called. The results:
>
>
>
> a) Using DD: 8.078 seconds
>
> b) Recycling Objects: 4.404 seconds
>
>
>
>
>
> The nearly 50 percent reduction in run time was due to just the savings in
> not creating and garbage collecting objects. The cost of the real work
> done by DD did not change.
>
>
>
> These changes are only worthwhile in applications that perform a large
> number of the same calculation over-and-over again. Of course, that’s just
> the kind of thing that shows up in computational geometry applications.
> Although it could be argued that “non-mutable” objects are “safer” than
> mutable objects I believe that any developer with basic experience in
> handling data would understand how to use mutable objects without mishap.
> And, after all, the authors of DD already found it necessary to implement
> “self” objects that mutate the content of DD objects, so there is a
> precedent.
>
>
>
> Basically I suggest the introduction methods such as set(),
> setSubtract(a,b), setMultiply(a,b), etc. to DD. Developers could then
> allow apply them to their code where appropriate.
>
>
>
> The code snippet below gives the guts of my in-circle implementation. The
> algebra is the same as that used in DD.inCircleDDNormalized(). All DD
> objects are instantiated in the constructor (not shown).
>
>
>
> // inCircle for coordinates a, b, c, d (DD used p instead of
> d)
>
> // “q” variables are pre-allocated DD objects. Set methods
> are
>
> // used to set values of the object.
>
>
>
> q11.setSubtract(a.x, d.x);
>
> q21.setSubtract(b.x, d.x);
>
> q31.setSubtract(c.x, d.x);
>
>
>
> q12.setSubtract(a.y, d.y);
>
> q22.setSubtract(b.y, d.y);
>
> q32.setSubtract(c.y, d.y);
>
>
>
> q11s.setSqr(q11);
>
> q12s.setSqr(q12);
>
> q21s.setSqr(q21);
>
> q22s.setSqr(q22);
>
> q31s.setSqr(q31);
>
> q32s.setSqr(q32);
>
>
>
> q11_22.set(q11);
>
> q11_32.set(q11);
>
> q21_12.set(q21);
>
> q21_32.set(q21);
>
> q31_22.set(q31);
>
> q31_12.set(q31);
>
>
>
> q21_32.selfMultiply(q32);
>
> q31_22.selfMultiply(q22);
>
> q31_12.selfMultiply(q12);
>
> q11_32.selfMultiply(q32);
>
> q11_22.selfMultiply(q22);
>
> q21_12.selfMultiply(q12);
>
>
>
> // the following lines use s1,s2,s3, etc. as a convenience
>
> // naturally, you have to be careful about what you overwrite…
>
> DD s1 = q11s.selfAdd(q12s);
>
> DD s2 = q21s.selfAdd(q22s);
>
> DD s3 = q31s.selfAdd(q32s);
>
>
>
> DD t1 = q21_32.selfSubtract(q31_22);
>
> DD t2 = q31_12.selfSubtract(q11_32);
>
> DD t3 = q11_22.selfSubtract(q21_12);
>
>
>
> s1.selfMultiply(t1);
>
> s2.selfMultiply(t2);
>
> s3.selfMultiply(t3);
>
> s1.selfAdd(s2).selfAdd(s3);
>
>
>
> return s1.doubleValue();
>
>
>
>
>
>
>
>
>
>
>
>
> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos. Get
> unparalleled scalability from the best Selenium testing platform available.
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs
> _______________________________________________
> Jts-topo-suite-user mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
------------------------------------------------------------------------------
"Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
Instantly run your Selenium tests across 300+ browser/OS combos. Get
unparalleled scalability from the best Selenium testing platform available.
Simple to use. Nothing to install. Get started now for free."
http://p.sf.net/sfu/SauceLabs
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
