JTS Topology Suite

I'm processing a large volume of records, in which I perform IntersectionMatrix calculations between geometry pairs via RelateOp.relate(geo1, geo2).matches(...).


Some of these geometries are relatively large/complex (multipolygons with several thousand points), but we keep processing them repeatedly.

Poking (a little) into the code, it looks the relate() method builds up GeometryGraph's for both geo's, then passes them off to a RelateComputer, which computes nodes and so forth.

I'm wondering whether there's some trick for pre-processing (compiling?) a geometry's graph/nodes to expedite this processing (i.e. avoid having to re-compute these graphs/nodes repeatedly and just do the minimal work of computing edge intersections)?

Thanks!

This is certainly theoretically possible, but it requires a
substantial rework of the current relate algorithm.  I've recently
been thinking about this exact problem, and have a conceptual design
for how to address this issue (and some other ones as well, such a
small robustness problem that cropped up in the last few months).

However, this work will take a significant effort, so it probably
won't get done until there's some funding to support it.

In the meantime, you can use the PreparedGeometry API to improve the
performance of some of the more common predicates, such as intersects,
contains, and covers.

On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@...> wrote:
> I'm processing a large volume of records, in which I perform
> IntersectionMatrix calculations between geometry pairs via
> RelateOp.relate(geo1, geo2).matches(...).
>
> Some of these geometries are relatively large/complex (multipolygons with
> several thousand points), but we keep processing them repeatedly.
>
> Poking (a little) into the code, it looks the relate() method builds up
> GeometryGraph's for both geo's, then passes them off to a RelateComputer,
> which computes nodes and so forth.
>
> I'm wondering whether there's some trick for pre-processing (compiling?) a
> geometry's graph/nodes to expedite this processing (i.e. avoid having to
> re-compute these graphs/nodes repeatedly and just do the minimal work of
> computing edge intersections)?
>
> Thanks!
>
> ------------------------------------------------------------------------------
> Don't let slow site performance ruin your business. Deploy New Relic APM
> Deploy New Relic app performance management and know exactly
> what is happening inside your Ruby, Python, PHP, Java, and .NET app
> Try New Relic at no cost today and get our sweet Data Nerd shirt too!
> http://p.sf.net/sfu/newrelic-dev2dev
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>

Martin,

Fair enough--and thanks for the quick response.

I'm looking to apply the "inner intersects" test (i.e. intersects only if the interiors overlap, in other words T********).  So, I could use PreparedGeometry.intersects() and then exclude if touches(), but the latter delegates down to the Geometry, which does the heavy lifting of computing the IntersectionMatrix (and hence wouldn't save me any processing).  Is there some other trick I'm overlooking?

Also, on a related note, are PreparedGeometries thread-safe?

Thanks again. 




________________________________
 From: Martin Davis <mtnclimb@...>
To: 
Cc: "jts-topo-suite-user@..." <jts-topo-suite-user@...> 
Sent: Wednesday, October 10, 2012 4:40 PM
Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
 
This is certainly theoretically possible, but it requires a
substantial rework of the current relate algorithm.  I've recently
been thinking about this exact problem, and have a conceptual design
for how to address this issue (and some other ones as well, such a
small robustness problem that cropped up in the last few months).

However, this work will take a significant effort, so it probably
won't get done until there's some funding to support it.

In the meantime, you can use the PreparedGeometry API to improve the
performance of some of the more common predicates, such as intersects,
contains, and covers.

On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@...> wrote:
> I'm processing a large volume of records, in which I perform
> IntersectionMatrix calculations between geometry pairs via
> RelateOp.relate(geo1, geo2).matches(...).
>
> Some of these geometries are relatively large/complex (multipolygons with
> several thousand points), but we keep processing them repeatedly.
>
> Poking (a little) into the code, it looks the relate() method builds up
> GeometryGraph's for both geo's, then passes them off to a RelateComputer,
> which computes nodes and so forth.
>
> I'm wondering whether there's some trick for pre-processing (compiling?) a
> geometry's graph/nodes to expedite this processing (i.e. avoid having to
> re-compute these graphs/nodes repeatedly and just do the minimal work of
> computing edge intersections)?
>
> Thanks!
>
> ------------------------------------------------------------------------------
> Don't let slow site performance ruin your business. Deploy New Relic APM
> Deploy New Relic app performance management and know exactly
> what is happening inside your Ruby, Python, PHP, Java, and .NET app
> Try New Relic at no cost today and get our sweet Data Nerd shirt too!
> http://p.sf.net/sfu/newrelic-dev2dev
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>

------------------------------------------------------------------------------
Don't let slow site performance ruin your business. Deploy New Relic APM
Deploy New Relic app performance management and know exactly
what is happening inside your Ruby, Python, PHP, Java, and .NET app
Try New Relic at no cost today and get our sweet Data Nerd shirt too!
http://p.sf.net/sfu/newrelic-dev2dev
_______________________________________________
Jts-topo-suite-user mailing list
Jts-topo-suite-user@...
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

Checking for interior intersection requires computing topology at
intersecting nodes, in the general case.  The sequence of tests that
need to be made are:

- check for a proper intersection of segments
- check for an intersection at a node where the two boundaries cross,
rather than being tangent
- check one polygon wholly contained in the other, via point-in-polygon

There's nothing in JTS that will allow short-cutting the
implementation of this algorithm, especially if optimal performance
and topology caching are required

PreparedGeometry is not threa-safe in JTS 1.12.   But thanks to a
recent issue report by Tomas, I fixed the PreparedGeometry code in
trunk so that they are now thread-safe.

On Mon, Oct 15, 2012 at 1:30 PM, Shahak Nagiel <snagiel@...> wrote:
> Martin,
>
> Fair enough--and thanks for the quick response.
>
> I'm looking to apply the "inner intersects" test (i.e. intersects only if
> the interiors overlap, in other words T********).  So, I could use
> PreparedGeometry.intersects() and then exclude if touches(), but the latter
> delegates down to the Geometry, which does the heavy lifting of computing
> the IntersectionMatrix (and hence wouldn't save me any processing).  Is
> there some other trick I'm overlooking?
>
> Also, on a related note, are PreparedGeometries thread-safe?
>
> Thanks again.
>
>
> ________________________________
> From: Martin Davis <mtnclimb@...>
> To:
> Cc: "jts-topo-suite-user@..."
> <jts-topo-suite-user@...>
> Sent: Wednesday, October 10, 2012 4:40 PM
> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>
> This is certainly theoretically possible, but it requires a
> substantial rework of the current relate algorithm.  I've recently
> been thinking about this exact problem, and have a conceptual design
> for how to address this issue (and some other ones as well, such a
> small robustness problem that cropped up in the last few months).
>
> However, this work will take a significant effort, so it probably
> won't get done until there's some funding to support it.
>
> In the meantime, you can use the PreparedGeometry API to improve the
> performance of some of the more common predicates, such as intersects,
> contains, and covers.
>
> On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@...> wrote:
>> I'm processing a large volume of records, in which I perform
>> IntersectionMatrix calculations between geometry pairs via
>> RelateOp.relate(geo1, geo2).matches(...).
>>
>> Some of these geometries are relatively large/complex (multipolygons with
>> several thousand points), but we keep processing them repeatedly.
>>
>> Poking (a little) into the code, it looks the relate() method builds up
>> GeometryGraph's for both geo's, then passes them off to a RelateComputer,
>> which computes nodes and so forth.
>>
>> I'm wondering whether there's some trick for pre-processing (compiling?) a
>> geometry's graph/nodes to expedite this processing (i.e. avoid having to
>> re-compute these graphs/nodes repeatedly and just do the minimal work of
>> computing edge intersections)?

FYI: I tried using the latest from trunk (probably ~Oct 16-17), and am seeing occasional concurrency problems with PreparedGeometries:

java.util.ConcurrentModificationException
    at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
    at java.util.AbstractList$ListItr.set(AbstractList.java:409)
    at java.util.Collections.sort(Collections.java:163)
    at com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.buildTree(SortedPackedIntervalRTree.java:91)

    at com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.init(SortedPackedIntervalRTree.java:85)
    at com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.query(SortedPackedIntervalRTree.java:147)
.
.
.
    at com.vividsolutions.jts.geom.prep.PreparedPolygon.intersects(PreparedPolygon.java:95)

Thanks.





________________________________
 From: Martin Davis <mtnclimb@...>
To: 
Cc: "jts-topo-suite-user@..." <jts-topo-suite-user@...> 
Sent: Monday, October 15, 2012 11:11 PM
Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
 
Checking for interior intersection requires computing topology at
intersecting nodes, in the general case.  The sequence of tests that
need to be made are:

- check for a proper intersection of segments
- check for an intersection at a node where the two boundaries cross,
rather than being tangent
- check one polygon wholly contained in the other, via point-in-polygon

There's nothing in JTS that will allow short-cutting the
implementation of this algorithm, especially if optimal performance
and topology caching are required

PreparedGeometry is not threa-safe in JTS 1.12.   But thanks to a
recent issue report by Tomas, I fixed the PreparedGeometry code in
trunk so that they are now thread-safe.

On Mon, Oct 15, 2012 at 1:30 PM, Shahak Nagiel <snagiel@...> wrote:
> Martin,
>
> Fair enough--and thanks for the quick response.
>
> I'm looking to apply the "inner intersects" test (i.e. intersects only if
> the interiors overlap, in other words T********).  So, I could use
> PreparedGeometry.intersects() and then exclude if touches(), but the latter
> delegates down to the Geometry, which does the heavy lifting of computing
> the IntersectionMatrix (and hence wouldn't save me any processing).  Is
> there some other trick I'm overlooking?
>
> Also, on a related note, are PreparedGeometries thread-safe?
>
> Thanks again.
>
>
> ________________________________
> From: Martin Davis <mtnclimb@...>
> To:
> Cc: "jts-topo-suite-user@..."
> <jts-topo-suite-user@...>
> Sent: Wednesday, October 10, 2012 4:40 PM
> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>
> This is certainly theoretically possible, but it requires a
> substantial rework of the current relate algorithm.  I've recently
> been thinking about this exact problem, and have a conceptual design
> for how to address this issue (and some other ones as well, such a
> small robustness problem that cropped up in the last few months).
>
> However, this work will take a significant effort, so it probably
> won't get done until there's some funding to support it.
>
> In the meantime, you can use the PreparedGeometry API to improve the
> performance of some of the more common predicates, such as intersects,
> contains, and covers.
>
> On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@...> wrote:
>> I'm processing a large volume of records, in which I perform
>> IntersectionMatrix calculations between geometry pairs via
>> RelateOp.relate(geo1, geo2).matches(...).
>>
>> Some of these geometries are relatively large/complex (multipolygons with
>> several thousand points), but we keep processing them repeatedly.
>>
>> Poking (a little) into the code, it looks the relate() method builds up
>> GeometryGraph's for both geo's, then passes them off to a RelateComputer,
>> which computes nodes and so forth.
>>
>> I'm wondering whether there's some trick for pre-processing (compiling?) a
>> geometry's graph/nodes to expedite this processing (i.e. avoid having to
>> re-compute these graphs/nodes repeatedly and just do the minimal work of
>> computing edge intersections)?

------------------------------------------------------------------------------
Don't let slow site performance ruin your business. Deploy New Relic APM
Deploy New Relic app performance management and know exactly
what is happening inside your Ruby, Python, PHP, Java, and .NET app
Try New Relic at no cost today and get our sweet Data Nerd shirt too!
http://p.sf.net/sfu/newrelic-dev2dev
_______________________________________________
Jts-topo-suite-user mailing list
Jts-topo-suite-user@...
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

Thanks for the alert.  I'll try and have a look at this soon.

If you or anyone else can identify the cause and suggest a fix, please
post to the list.

On Tue, Oct 23, 2012 at 9:45 AM, Shahak Nagiel <snagiel@...> wrote:
> FYI: I tried using the latest from trunk (probably ~Oct 16-17), and am
> seeing occasional concurrency problems with PreparedGeometries:
>
> java.util.ConcurrentModificationException
>     at
> java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
>     at java.util.AbstractList$ListItr.set(AbstractList.java:409)
>     at java.util.Collections.sort(Collections.java:163)
>     at
> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.buildTree(SortedPackedIntervalRTree.java:91)
>     at
> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.init(SortedPackedIntervalRTree.java:85)
>     at
> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.query(SortedPackedIntervalRTree.java:147)
> .
> .
> .
>     at
> com.vividsolutions.jts.geom.prep.PreparedPolygon.intersects(PreparedPolygon.java:95)
>
> Thanks.
>
>
>
> ________________________________
> From: Martin Davis <mtnclimb@...>
> To:
> Cc: "jts-topo-suite-user@..."
> <jts-topo-suite-user@...>
> Sent: Monday, October 15, 2012 11:11 PM
> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>
> Checking for interior intersection requires computing topology at
> intersecting nodes, in the general case.  The sequence of tests that
> need to be made are:
>
> - check for a proper intersection of segments
> - check for an intersection at a node where the two boundaries cross,
> rather than being tangent
> - check one polygon wholly contained in the other, via point-in-polygon
>
> There's nothing in JTS that will allow short-cutting the
> implementation of this algorithm, especially if optimal performance
> and topology caching are required
>
> PreparedGeometry is not threa-safe in JTS 1.12.  But thanks to a
> recent issue report by Tomas, I fixed the PreparedGeometry code in
> trunk so that they are now thread-safe.
>
> On Mon, Oct 15, 2012 at 1:30 PM, Shahak Nagiel <snagiel@...> wrote:
>> Martin,
>>
>> Fair enough--and thanks for the quick response.
>>
>> I'm looking to apply the "inner intersects" test (i.e. intersects only if
>> the interiors overlap, in other words T********).  So, I could use
>> PreparedGeometry.intersects() and then exclude if touches(), but the
>> latter
>> delegates down to the Geometry, which does the heavy lifting of computing
>> the IntersectionMatrix (and hence wouldn't save me any processing).  Is
>> there some other trick I'm overlooking?
>>
>> Also, on a related note, are PreparedGeometries thread-safe?
>>
>> Thanks again.
>>
>>
>> ________________________________
>> From: Martin Davis <mtnclimb@...>
>> To:
>> Cc: "jts-topo-suite-user@..."
>> <jts-topo-suite-user@...>
>> Sent: Wednesday, October 10, 2012 4:40 PM
>> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>>
>> This is certainly theoretically possible, but it requires a
>> substantial rework of the current relate algorithm.  I've recently
>> been thinking about this exact problem, and have a conceptual design
>> for how to address this issue (and some other ones as well, such a
>> small robustness problem that cropped up in the last few months).
>>
>> However, this work will take a significant effort, so it probably
>> won't get done until there's some funding to support it.
>>
>> In the meantime, you can use the PreparedGeometry API to improve the
>> performance of some of the more common predicates, such as intersects,
>> contains, and covers.
>>
>> On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@...> wrote:
>>> I'm processing a large volume of records, in which I perform
>>> IntersectionMatrix calculations between geometry pairs via
>>> RelateOp.relate(geo1, geo2).matches(...).
>>>
>>> Some of these geometries are relatively large/complex (multipolygons with
>>> several thousand points), but we keep processing them repeatedly.
>>>
>>> Poking (a little) into the code, it looks the relate() method builds up
>>> GeometryGraph's for both geo's, then passes them off to a RelateComputer,
>>> which computes nodes and so forth.
>>>
>>> I'm wondering whether there's some trick for pre-processing (compiling?)
>>> a
>>> geometry's graph/nodes to expedite this processing (i.e. avoid having to
>>> re-compute these graphs/nodes repeatedly and just do the minimal work of
>>> computing edge intersections)?
>
> ------------------------------------------------------------------------------
> Don't let slow site performance ruin your business. Deploy New Relic APM
> Deploy New Relic app performance management and know exactly
> what is happening inside your Ruby, Python, PHP, Java, and .NET app
> Try New Relic at no cost today and get our sweet Data Nerd shirt too!
> http://p.sf.net/sfu/newrelic-dev2dev
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>

On Tuesday 23 October 2012 09:59:41 Martin Davis wrote:
> Thanks for the alert.  I'll try and have a look at this soon.
> 
> If you or anyone else can identify the cause and suggest a fix, please
> post to the list.

might be fixed in the trunk when you solved the issues we discussed in "[Jts-
topo-suite-user] Is PreparedGeometry threadsafe?" couple of weeks ago?

I remember the issue was that a list was re-used rather than simply re-
created.

@Shahak you could try out the TRUNK and see if it works for you!

Cheers


Jan

There was a race condition in the intialization method for the 
SortedPackedIntervalRtree.  This is now fixed in SVN.

Can you try this out and see if it fixed the problem?

On 10/23/2012 9:45 AM, Shahak Nagiel wrote:
> FYI: I tried using the latest from trunk (probably ~Oct 16-17), and am 
> seeing occasional concurrency problems with PreparedGeometries:
>
> java.util.ConcurrentModificationException
> at 
> java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
> at java.util.AbstractList$ListItr.set(AbstractList.java:409)
>     at java.util.Collections.sort(Collections.java:163)
>     at 
> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.buildTree(SortedPackedIntervalRTree.java:91)
>     at 
> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.init(SortedPackedIntervalRTree.java:85)
>     at 
> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.query(SortedPackedIntervalRTree.java:147)
> .
> .
> .
>     at 
> com.vividsolutions.jts.geom.prep.PreparedPolygon.intersects(PreparedPolygon.java:95)
>
> Thanks.
>
>
>
> ------------------------------------------------------------------------
> *From:* Martin Davis <mtnclimb@...>
> *To:*
> *Cc:* "jts-topo-suite-user@..." 
> <jts-topo-suite-user@...>
> *Sent:* Monday, October 15, 2012 11:11 PM
> *Subject:* Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>
> Checking for interior intersection requires computing topology at
> intersecting nodes, in the general case.  The sequence of tests that
> need to be made are:
>
> - check for a proper intersection of segments
> - check for an intersection at a node where the two boundaries cross,
> rather than being tangent
> - check one polygon wholly contained in the other, via point-in-polygon
>
> There's nothing in JTS that will allow short-cutting the
> implementation of this algorithm, especially if optimal performance
> and topology caching are required
>
> PreparedGeometry is not threa-safe in JTS 1.12.  But thanks to a
> recent issue report by Tomas, I fixed the PreparedGeometry code in
> trunk so that they are now thread-safe.
>
> On Mon, Oct 15, 2012 at 1:30 PM, Shahak Nagiel <snagiel@... 
> <mailto:snagiel@...>> wrote:
> > Martin,
> >
> > Fair enough--and thanks for the quick response.
> >
> > I'm looking to apply the "inner intersects" test (i.e. intersects 
> only if
> > the interiors overlap, in other words T********).  So, I could use
> > PreparedGeometry.intersects() and then exclude if touches(), but the 
> latter
> > delegates down to the Geometry, which does the heavy lifting of 
> computing
> > the IntersectionMatrix (and hence wouldn't save me any processing).  Is
> > there some other trick I'm overlooking?
> >
> > Also, on a related note, are PreparedGeometries thread-safe?
> >
> > Thanks again.
> >
> >
> > ________________________________
> > From: Martin Davis <mtnclimb@... <mailto:mtnclimb@...>>
> > To:
> > Cc: "jts-topo-suite-user@... 
> <mailto:jts-topo-suite-user@...>"
> > <jts-topo-suite-user@... 
> <mailto:jts-topo-suite-user@...>>
> > Sent: Wednesday, October 10, 2012 4:40 PM
> > Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
> >
> > This is certainly theoretically possible, but it requires a
> > substantial rework of the current relate algorithm. I've recently
> > been thinking about this exact problem, and have a conceptual design
> > for how to address this issue (and some other ones as well, such a
> > small robustness problem that cropped up in the last few months).
> >
> > However, this work will take a significant effort, so it probably
> > won't get done until there's some funding to support it.
> >
> > In the meantime, you can use the PreparedGeometry API to improve the
> > performance of some of the more common predicates, such as intersects,
> > contains, and covers.
> >
> > On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@... 
> <mailto:snagiel@...>> wrote:
> >> I'm processing a large volume of records, in which I perform
> >> IntersectionMatrix calculations between geometry pairs via
> >> RelateOp.relate(geo1, geo2).matches(...).
> >>
> >> Some of these geometries are relatively large/complex 
> (multipolygons with
> >> several thousand points), but we keep processing them repeatedly.
> >>
> >> Poking (a little) into the code, it looks the relate() method builds up
> >> GeometryGraph's for both geo's, then passes them off to a 
> RelateComputer,
> >> which computes nodes and so forth.
> >>
> >> I'm wondering whether there's some trick for pre-processing 
> (compiling?) a
> >> geometry's graph/nodes to expedite this processing (i.e. avoid 
> having to
> >> re-compute these graphs/nodes repeatedly and just do the minimal 
> work of
> >> computing edge intersections)?
>
> ------------------------------------------------------------------------------
> Don't let slow site performance ruin your business. Deploy New Relic APM
> Deploy New Relic app performance management and know exactly
> what is happening inside your Ruby, Python, PHP, Java, and .NET app
> Try New Relic at no cost today and get our sweet Data Nerd shirt too!
> http://p.sf.net/sfu/newrelic-dev2dev
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@... 
> <mailto:Jts-topo-suite-user@...>
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
>
>
> ------------------------------------------------------------------------------
> Everyone hates slow websites. So do we.
> Make your web apps faster with AppDynamics
> Download AppDynamics Lite for free today:
> http://p.sf.net/sfu/appdyn_sfd2d_oct
>
>
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
> No virus found in this message.
> Checked by AVG - http://www.avg.com <http://www.avg.com>
> Version: 2012.0.2221 / Virus Database: 2441/5349 - Release Date: 10/23/12
>

I realized that the safest way to provide thread-safety for
PreparedGeometry is to ensure the initialization of the internal index
caches is made thread-safe.  I'll make this improvement ASAP.

(Technical note: My first thought was to use Double-Check Locking as
the pattern to provide thread-safety, and avoid a performance impact
incurred by synchronizing the getter methods doing the lazy
initialization.  But this discussion [1] convinces me that it's better
to simply synchronize the getters, and let the JVM handle the locking.
 Apparently in modern JVMs there is very little overhead from
synchronization anyway).

[1] http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

On Tue, Oct 23, 2012 at 9:35 PM, Martin Davis <mtnclimb@...> wrote:
> There was a race condition in the intialization method for the
> SortedPackedIntervalRtree.  This is now fixed in SVN.
>
> Can you try this out and see if it fixed the problem?
>
>
> On 10/23/2012 9:45 AM, Shahak Nagiel wrote:
>
> FYI: I tried using the latest from trunk (probably ~Oct 16-17), and am
> seeing occasional concurrency problems with PreparedGeometries:
>
> java.util.ConcurrentModificationException
>     at
> java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
>     at java.util.AbstractList$ListItr.set(AbstractList.java:409)
>     at java.util.Collections.sort(Collections.java:163)
>     at
> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.buildTree(SortedPackedIntervalRTree.java:91)
>     at
> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.init(SortedPackedIntervalRTree.java:85)
>     at
> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.query(SortedPackedIntervalRTree.java:147)
> .
> .
> .
>     at
> com.vividsolutions.jts.geom.prep.PreparedPolygon.intersects(PreparedPolygon.java:95)
>
> Thanks.
>
>
>
> ________________________________
> From: Martin Davis <mtnclimb@...>
> To:
> Cc: "jts-topo-suite-user@..."
> <jts-topo-suite-user@...>
> Sent: Monday, October 15, 2012 11:11 PM
> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>
> Checking for interior intersection requires computing topology at
> intersecting nodes, in the general case.  The sequence of tests that
> need to be made are:
>
> - check for a proper intersection of segments
> - check for an intersection at a node where the two boundaries cross,
> rather than being tangent
> - check one polygon wholly contained in the other, via point-in-polygon
>
> There's nothing in JTS that will allow short-cutting the
> implementation of this algorithm, especially if optimal performance
> and topology caching are required
>
> PreparedGeometry is not threa-safe in JTS 1.12.  But thanks to a
> recent issue report by Tomas, I fixed the PreparedGeometry code in
> trunk so that they are now thread-safe.
>
> On Mon, Oct 15, 2012 at 1:30 PM, Shahak Nagiel <snagiel@...> wrote:
>> Martin,
>>
>> Fair enough--and thanks for the quick response.
>>
>> I'm looking to apply the "inner intersects" test (i.e. intersects only if
>> the interiors overlap, in other words T********).  So, I could use
>> PreparedGeometry.intersects() and then exclude if touches(), but the
>> latter
>> delegates down to the Geometry, which does the heavy lifting of computing
>> the IntersectionMatrix (and hence wouldn't save me any processing).  Is
>> there some other trick I'm overlooking?
>>
>> Also, on a related note, are PreparedGeometries thread-safe?
>>
>> Thanks again.
>>
>>
>> ________________________________
>> From: Martin Davis <mtnclimb@...>
>> To:
>> Cc: "jts-topo-suite-user@..."
>> <jts-topo-suite-user@...>
>> Sent: Wednesday, October 10, 2012 4:40 PM
>> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>>
>> This is certainly theoretically possible, but it requires a
>> substantial rework of the current relate algorithm.  I've recently
>> been thinking about this exact problem, and have a conceptual design
>> for how to address this issue (and some other ones as well, such a
>> small robustness problem that cropped up in the last few months).
>>
>> However, this work will take a significant effort, so it probably
>> won't get done until there's some funding to support it.
>>
>> In the meantime, you can use the PreparedGeometry API to improve the
>> performance of some of the more common predicates, such as intersects,
>> contains, and covers.
>>
>> On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@...> wrote:
>>> I'm processing a large volume of records, in which I perform
>>> IntersectionMatrix calculations between geometry pairs via
>>> RelateOp.relate(geo1, geo2).matches(...).
>>>
>>> Some of these geometries are relatively large/complex (multipolygons with
>>> several thousand points), but we keep processing them repeatedly.
>>>
>>> Poking (a little) into the code, it looks the relate() method builds up
>>> GeometryGraph's for both geo's, then passes them off to a RelateComputer,
>>> which computes nodes and so forth.
>>>
>>> I'm wondering whether there's some trick for pre-processing (compiling?)
>>> a
>>> geometry's graph/nodes to expedite this processing (i.e. avoid having to
>>> re-compute these graphs/nodes repeatedly and just do the minimal work of
>>> computing edge intersections)?
>
> ------------------------------------------------------------------------------
> Don't let slow site performance ruin your business. Deploy New Relic APM
> Deploy New Relic app performance management and know exactly
> what is happening inside your Ruby, Python, PHP, Java, and .NET app
> Try New Relic at no cost today and get our sweet Data Nerd shirt too!
> http://p.sf.net/sfu/newrelic-dev2dev
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
>
>
> ------------------------------------------------------------------------------
> Everyone hates slow websites. So do we.
> Make your web apps faster with AppDynamics
> Download AppDynamics Lite for free today:
> http://p.sf.net/sfu/appdyn_sfd2d_oct
>
>
>
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
>
> No virus found in this message.
> Checked by AVG - http://www.avg.com
> Version: 2012.0.2221 / Virus Database: 2441/5349 - Release Date: 10/23/12
>
>
>
> ------------------------------------------------------------------------------
> Everyone hates slow websites. So do we.
> Make your web apps faster with AppDynamics
> Download AppDynamics Lite for free today:
> http://p.sf.net/sfu/appdyn_sfd2d_oct
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>

This fix is now in place.  It would be great if it can be tested in a
suitable environment.

On Wed, Oct 24, 2012 at 3:30 PM, Martin Davis <mtnclimb@...> wrote:
> I realized that the safest way to provide thread-safety for
> PreparedGeometry is to ensure the initialization of the internal index
> caches is made thread-safe.  I'll make this improvement ASAP.
>
> (Technical note: My first thought was to use Double-Check Locking as
> the pattern to provide thread-safety, and avoid a performance impact
> incurred by synchronizing the getter methods doing the lazy
> initialization.  But this discussion [1] convinces me that it's better
> to simply synchronize the getters, and let the JVM handle the locking.
>  Apparently in modern JVMs there is very little overhead from
> synchronization anyway).
>
> [1] http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
>
> On Tue, Oct 23, 2012 at 9:35 PM, Martin Davis <mtnclimb@...> wrote:
>> There was a race condition in the intialization method for the
>> SortedPackedIntervalRtree.  This is now fixed in SVN.
>>
>> Can you try this out and see if it fixed the problem?
>>
>>
>> On 10/23/2012 9:45 AM, Shahak Nagiel wrote:
>>
>> FYI: I tried using the latest from trunk (probably ~Oct 16-17), and am
>> seeing occasional concurrency problems with PreparedGeometries:
>>
>> java.util.ConcurrentModificationException
>>     at
>> java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
>>     at java.util.AbstractList$ListItr.set(AbstractList.java:409)
>>     at java.util.Collections.sort(Collections.java:163)
>>     at
>> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.buildTree(SortedPackedIntervalRTree.java:91)
>>     at
>> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.init(SortedPackedIntervalRTree.java:85)
>>     at
>> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.query(SortedPackedIntervalRTree.java:147)
>> .
>> .
>> .
>>     at
>> com.vividsolutions.jts.geom.prep.PreparedPolygon.intersects(PreparedPolygon.java:95)
>>
>> Thanks.
>>
>>
>>
>> ________________________________
>> From: Martin Davis <mtnclimb@...>
>> To:
>> Cc: "jts-topo-suite-user@..."
>> <jts-topo-suite-user@...>
>> Sent: Monday, October 15, 2012 11:11 PM
>> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>>
>> Checking for interior intersection requires computing topology at
>> intersecting nodes, in the general case.  The sequence of tests that
>> need to be made are:
>>
>> - check for a proper intersection of segments
>> - check for an intersection at a node where the two boundaries cross,
>> rather than being tangent
>> - check one polygon wholly contained in the other, via point-in-polygon
>>
>> There's nothing in JTS that will allow short-cutting the
>> implementation of this algorithm, especially if optimal performance
>> and topology caching are required
>>
>> PreparedGeometry is not threa-safe in JTS 1.12.  But thanks to a
>> recent issue report by Tomas, I fixed the PreparedGeometry code in
>> trunk so that they are now thread-safe.
>>
>> On Mon, Oct 15, 2012 at 1:30 PM, Shahak Nagiel <snagiel@...> wrote:
>>> Martin,
>>>
>>> Fair enough--and thanks for the quick response.
>>>
>>> I'm looking to apply the "inner intersects" test (i.e. intersects only if
>>> the interiors overlap, in other words T********).  So, I could use
>>> PreparedGeometry.intersects() and then exclude if touches(), but the
>>> latter
>>> delegates down to the Geometry, which does the heavy lifting of computing
>>> the IntersectionMatrix (and hence wouldn't save me any processing).  Is
>>> there some other trick I'm overlooking?
>>>
>>> Also, on a related note, are PreparedGeometries thread-safe?
>>>
>>> Thanks again.
>>>
>>>
>>> ________________________________
>>> From: Martin Davis <mtnclimb@...>
>>> To:
>>> Cc: "jts-topo-suite-user@..."
>>> <jts-topo-suite-user@...>
>>> Sent: Wednesday, October 10, 2012 4:40 PM
>>> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>>>
>>> This is certainly theoretically possible, but it requires a
>>> substantial rework of the current relate algorithm.  I've recently
>>> been thinking about this exact problem, and have a conceptual design
>>> for how to address this issue (and some other ones as well, such a
>>> small robustness problem that cropped up in the last few months).
>>>
>>> However, this work will take a significant effort, so it probably
>>> won't get done until there's some funding to support it.
>>>
>>> In the meantime, you can use the PreparedGeometry API to improve the
>>> performance of some of the more common predicates, such as intersects,
>>> contains, and covers.
>>>
>>> On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@...> wrote:
>>>> I'm processing a large volume of records, in which I perform
>>>> IntersectionMatrix calculations between geometry pairs via
>>>> RelateOp.relate(geo1, geo2).matches(...).
>>>>
>>>> Some of these geometries are relatively large/complex (multipolygons with
>>>> several thousand points), but we keep processing them repeatedly.
>>>>
>>>> Poking (a little) into the code, it looks the relate() method builds up
>>>> GeometryGraph's for both geo's, then passes them off to a RelateComputer,
>>>> which computes nodes and so forth.
>>>>
>>>> I'm wondering whether there's some trick for pre-processing (compiling?)
>>>> a
>>>> geometry's graph/nodes to expedite this processing (i.e. avoid having to
>>>> re-compute these graphs/nodes repeatedly and just do the minimal work of
>>>> computing edge intersections)?
>>
>> ------------------------------------------------------------------------------
>> Don't let slow site performance ruin your business. Deploy New Relic APM
>> Deploy New Relic app performance management and know exactly
>> what is happening inside your Ruby, Python, PHP, Java, and .NET app
>> Try New Relic at no cost today and get our sweet Data Nerd shirt too!
>> http://p.sf.net/sfu/newrelic-dev2dev
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts-topo-suite-user@...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Everyone hates slow websites. So do we.
>> Make your web apps faster with AppDynamics
>> Download AppDynamics Lite for free today:
>> http://p.sf.net/sfu/appdyn_sfd2d_oct
>>
>>
>>
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts-topo-suite-user@...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>
>>
>>
>> No virus found in this message.
>> Checked by AVG - http://www.avg.com
>> Version: 2012.0.2221 / Virus Database: 2441/5349 - Release Date: 10/23/12
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Everyone hates slow websites. So do we.
>> Make your web apps faster with AppDynamics
>> Download AppDynamics Lite for free today:
>> http://p.sf.net/sfu/appdyn_sfd2d_oct
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts-topo-suite-user@...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>

On Wednesday 24 October 2012 15:30:11 Martin Davis wrote:
> I realized that the safest way to provide thread-safety for
> PreparedGeometry is to ensure the initialization of the internal index
> caches is made thread-safe.  I'll make this improvement ASAP.

If your init work is in the constructor, only, and public methods (getters, 
etc.) don't modify the internal state of the PreparedGeometry you can even 
skip synchronization.

Cheers,

-- 
Jan

I tested the latest from trunk last night with a simple test harness (100-wide thread pool, each one iterating 100,000 times and testing PreparedGeometry.intersects()), and it performed well (very fast and, more importantly, no concurrency exceptions).

The test was conducted on a simple dual-core machine, so it didn't realistically simulate a more highly concurrent server platform.  And, I didn't get a chance to re-build and test with source code prior to the SortedPackedIntervalRTree revision (671), but I'll be sure to do so ASAP.  I can then then test with these latest changes (674) as well.

Thanks!





________________________________
 From: Martin Davis <mtnclimb@...>
To: 
Cc: jts-topo-suite-user@... 
Sent: Thursday, October 25, 2012 1:42 AM
Subject: Re: [Jts-topo-suite-user] PreparedGeometries thread safety
 
This fix is now in place.  It would be great if it can be tested in a
suitable environment.

On Wed, Oct 24, 2012 at 3:30 PM, Martin Davis <mtnclimb@...> wrote:
> I realized that the safest way to provide thread-safety for
> PreparedGeometry is to ensure the initialization of the internal index
> caches is made thread-safe.  I'll make this improvement ASAP.
>
> (Technical note: My first thought was to use Double-Check Locking as
> the pattern to provide thread-safety, and avoid a performance impact
> incurred by synchronizing the getter methods doing the lazy
> initialization.  But this discussion [1] convinces me that it's better
> to simply synchronize the getters, and let the JVM handle the locking.
>  Apparently in modern JVMs there is very little overhead from
> synchronization anyway).
>
> [1] http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
>
> On Tue, Oct 23, 2012 at 9:35 PM, Martin Davis <mtnclimb@...> wrote:
>> There was a race condition in the intialization method for the
>> SortedPackedIntervalRtree.  This is now fixed in SVN.
>>
>> Can you try this out and see if it fixed the problem?
>>
>>
>> On 10/23/2012 9:45 AM, Shahak Nagiel wrote:
>>
>> FYI: I tried using the latest from trunk (probably ~Oct 16-17), and am
>> seeing occasional concurrency problems with PreparedGeometries:
>>
>> java.util.ConcurrentModificationException
>>     at
>> java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
>>     at java.util.AbstractList$ListItr.set(AbstractList.java:409)
>>     at java.util.Collections.sort(Collections.java:163)
>>     at
>> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.buildTree(SortedPackedIntervalRTree.java:91)
>>     at
>> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.init(SortedPackedIntervalRTree.java:85)
>>     at
>> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.query(SortedPackedIntervalRTree.java:147)
>> .
>> .
>> .
>>     at
>> com.vividsolutions.jts.geom.prep.PreparedPolygon.intersects(PreparedPolygon.java:95)
>>
>> Thanks.
>>
>>
>>
>> ________________________________
>> From: Martin Davis <mtnclimb@...>
>> To:
>> Cc: "jts-topo-suite-user@..."
>> <jts-topo-suite-user@...>
>> Sent: Monday, October 15, 2012 11:11 PM
>> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>>
>> Checking for interior intersection requires computing topology at
>> intersecting nodes, in the general case.  The sequence of tests that
>> need to be made are:
>>
>> - check for a proper intersection of segments
>> - check for an intersection at a node where the two boundaries cross,
>> rather than being tangent
>> - check one polygon wholly contained in the other, via point-in-polygon
>>
>> There's nothing in JTS that will allow short-cutting the
>> implementation of this algorithm, especially if optimal performance
>> and topology caching are required
>>
>> PreparedGeometry is not threa-safe in JTS 1.12.  But thanks to a
>> recent issue report by Tomas, I fixed the PreparedGeometry code in
>> trunk so that they are now thread-safe.
>>
>> On Mon, Oct 15, 2012 at 1:30 PM, Shahak Nagiel <snagiel@...> wrote:
>>> Martin,
>>>
>>> Fair enough--and thanks for the quick response.
>>>
>>> I'm looking to apply the "inner intersects" test (i.e. intersects only if
>>> the interiors overlap, in other words T********).  So, I could use
>>> PreparedGeometry.intersects() and then exclude if touches(), but the
>>> latter
>>> delegates down to the Geometry, which does the heavy lifting of computing
>>> the IntersectionMatrix (and hence wouldn't save me any processing).  Is
>>> there some other trick I'm overlooking?
>>>
>>> Also, on a related note, are PreparedGeometries thread-safe?
>>>
>>> Thanks again.
>>>
>>>
>>> ________________________________
>>> From: Martin Davis <mtnclimb@...>
>>> To:
>>> Cc: "jts-topo-suite-user@..."
>>> <jts-topo-suite-user@...>
>>> Sent: Wednesday, October 10, 2012 4:40 PM
>>> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>>>
>>> This is certainly theoretically possible, but it requires a
>>> substantial rework of the current relate algorithm.  I've recently
>>> been thinking about this exact problem, and have a conceptual design
>>> for how to address this issue (and some other ones as well, such a
>>> small robustness problem that cropped up in the last few months).
>>>
>>> However, this work will take a significant effort, so it probably
>>> won't get done until there's some funding to support it.
>>>
>>> In the meantime, you can use the PreparedGeometry API to improve the
>>> performance of some of the more common predicates, such as intersects,
>>> contains, and covers.
>>>
>>> On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@...> wrote:
>>>> I'm processing a large volume of records, in which I perform
>>>> IntersectionMatrix calculations between geometry pairs via
>>>> RelateOp.relate(geo1, geo2).matches(...).
>>>>
>>>> Some of these geometries are relatively large/complex (multipolygons with
>>>> several thousand points), but we keep processing them repeatedly.
>>>>
>>>> Poking (a little) into the code, it looks the relate() method builds up
>>>> GeometryGraph's for both geo's, then passes them off to a RelateComputer,
>>>> which computes nodes and so forth.
>>>>
>>>> I'm wondering whether there's some trick for pre-processing (compiling?)
>>>> a
>>>> geometry's graph/nodes to expedite this processing (i.e. avoid having to
>>>> re-compute these graphs/nodes repeatedly and just do the minimal work of
>>>> computing edge intersections)?
>>
>> ------------------------------------------------------------------------------
>> Don't let slow site performance ruin your business. Deploy New Relic APM
>> Deploy New Relic app performance management and know exactly
>> what is happening inside your Ruby, Python, PHP, Java, and .NET app
>> Try New Relic at no cost today and get our sweet Data Nerd shirt too!
>> http://p.sf.net/sfu/newrelic-dev2dev
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts-topo-suite-user@...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Everyone hates slow websites. So do we.
>> Make your web apps faster with AppDynamics
>> Download AppDynamics Lite for free today:
>> http://p.sf.net/sfu/appdyn_sfd2d_oct
>>
>>
>>
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts-topo-suite-user@...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>
>>
>>
>> No virus found in this message.
>> Checked by AVG - http://www.avg.com
>> Version: 2012.0.2221 / Virus Database: 2441/5349 - Release Date: 10/23/12
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Everyone hates slow websites. So do we.
>> Make your web apps faster with AppDynamics
>> Download AppDynamics Lite for free today:
>> http://p.sf.net/sfu/appdyn_sfd2d_oct
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts-topo-suite-user@...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>

------------------------------------------------------------------------------
Everyone hates slow websites. So do we.
Make your web apps faster with AppDynamics
Download AppDynamics Lite for free today:
http://p.sf.net/sfu/appdyn_sfd2d_oct
_______________________________________________
Jts-topo-suite-user mailing list
Jts-topo-suite-user@...
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

In the case of PreparedGeometry (and the Rtree indexes) the 
initialization is done lazily, so it is performed in a regular method, 
and can occur well after the object has been constructed.

I guess it might be possible to keep the initialized data in an internal 
object created when the lazy init is triggered, but it seemed simpler 
just to synchronize.

On 10/25/2012 12:48 AM, Jan Torben Heuer wrote:
> On Wednesday 24 October 2012 15:30:11 Martin Davis wrote:
>> I realized that the safest way to provide thread-safety for
>> PreparedGeometry is to ensure the initialization of the internal index
>> caches is made thread-safe.  I'll make this improvement ASAP.
> If your init work is in the constructor, only, and public methods (getters,
> etc.) don't modify the internal state of the PreparedGeometry you can even
> skip synchronization.
>
> Cheers,
>

I'm very familiar with thread-safety / concurrency issues, and I've read that link from Bill Pugh you referenced many times before.  It's a bit dated insofar as double-checked locking is safe now.  There are other approaches too.  Brian Goetz's book "Java Concurrency in Practice" is excellent.

I looked at your commit today, #674.  It's not clear to me why you are lazy-instantiating the FastSegmentSetIntersectionFinder and PointOnGeometryLocator.  Comments in your class say that these are "expensive".  Okay, I get that.  But it seems that these prepared geometry shape subclasses do nearly nothing else than provide access to these classes, so isn't it a given that these "expensive" class instances will need to be created *anyway*?  If so, then as Jan pointed out, you can simply initialize them in the constructor, make them final, and then not worry about thread-safety for those fields.

I took a closer look at FastSegmentSetIntersectionFinder.  This class does not appear thread-safe.
1.   For one it doesn't document itself as such, yet a shared instance is returned from PreparedPolygon which does declare to be thread-safe… which is suggestive of a problem, since it will be insufficient for PreparedPolygon to be thread-safe when multiple threads will also need to operate on the shared objects returned from PreparedPolygon's methods. 
2.  FastSegmentSetIntersectionFinder.intersects() will create a new SegmentIntersectionDetector which uses a LineIntersector static shared instance in its constructor.  Following the rabbit down the rabbit hole, LineIntersector, the shared instance here has state -- a warning sign for thread-safety.  LineIntersector does not document wether it's thread-safe.  And I see no signs of attempts to make it as such, so I don't think it is.
3.  FastSegmentSetIntersectionFinder.intersects() will take the SegmentIntersectionDetector it created and set it on SegmentSetMutualIntersector.  That right there is a warning flag for thread-safety since it's modifying state.  SegmentSetMutualIntersector does not declare itself to be thread-safe -- it isn't in fact, which is clear looking at this simple class.

In addition to pointing out these flaws I can try and fix them.

~ David

On Oct 24, 2012, at 6:30 PM, Martin Davis wrote:

> I realized that the safest way to provide thread-safety for
> PreparedGeometry is to ensure the initialization of the internal index
> caches is made thread-safe.  I'll make this improvement ASAP.
> 
> (Technical note: My first thought was to use Double-Check Locking as
> the pattern to provide thread-safety, and avoid a performance impact
> incurred by synchronizing the getter methods doing the lazy
> initialization.  But this discussion [1] convinces me that it's better
> to simply synchronize the getters, and let the JVM handle the locking.
> Apparently in modern JVMs there is very little overhead from
> synchronization anyway).
> 
> [1] http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
> 
> On Tue, Oct 23, 2012 at 9:35 PM, Martin Davis <mtnclimb@...> wrote:
>> There was a race condition in the intialization method for the
>> SortedPackedIntervalRtree.  This is now fixed in SVN.
>> 
>> Can you try this out and see if it fixed the problem?
>> 
>> 
>> On 10/23/2012 9:45 AM, Shahak Nagiel wrote:
>> 
>> FYI: I tried using the latest from trunk (probably ~Oct 16-17), and am
>> seeing occasional concurrency problems with PreparedGeometries:
>> 
>> java.util.ConcurrentModificationException
>>    at
>> java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
>>    at java.util.AbstractList$ListItr.set(AbstractList.java:409)
>>    at java.util.Collections.sort(Collections.java:163)
>>    at
>> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.buildTree(SortedPackedIntervalRTree.java:91)
>>    at
>> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.init(SortedPackedIntervalRTree.java:85)
>>    at
>> com.vividsolutions.jts.index.intervalrtree.SortedPackedIntervalRTree.query(SortedPackedIntervalRTree.java:147)
>> .
>> .
>> .
>>    at
>> com.vividsolutions.jts.geom.prep.PreparedPolygon.intersects(PreparedPolygon.java:95)
>> 
>> Thanks.
>> 
>> 
>> 
>> ________________________________
>> From: Martin Davis <mtnclimb@...>
>> To:
>> Cc: "jts-topo-suite-user@..."
>> <jts-topo-suite-user@...>
>> Sent: Monday, October 15, 2012 11:11 PM
>> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>> 
>> Checking for interior intersection requires computing topology at
>> intersecting nodes, in the general case.  The sequence of tests that
>> need to be made are:
>> 
>> - check for a proper intersection of segments
>> - check for an intersection at a node where the two boundaries cross,
>> rather than being tangent
>> - check one polygon wholly contained in the other, via point-in-polygon
>> 
>> There's nothing in JTS that will allow short-cutting the
>> implementation of this algorithm, especially if optimal performance
>> and topology caching are required
>> 
>> PreparedGeometry is not threa-safe in JTS 1.12.  But thanks to a
>> recent issue report by Tomas, I fixed the PreparedGeometry code in
>> trunk so that they are now thread-safe.
>> 
>> On Mon, Oct 15, 2012 at 1:30 PM, Shahak Nagiel <snagiel@...> wrote:
>>> Martin,
>>> 
>>> Fair enough--and thanks for the quick response.
>>> 
>>> I'm looking to apply the "inner intersects" test (i.e. intersects only if
>>> the interiors overlap, in other words T********).  So, I could use
>>> PreparedGeometry.intersects() and then exclude if touches(), but the
>>> latter
>>> delegates down to the Geometry, which does the heavy lifting of computing
>>> the IntersectionMatrix (and hence wouldn't save me any processing).  Is
>>> there some other trick I'm overlooking?
>>> 
>>> Also, on a related note, are PreparedGeometries thread-safe?
>>> 
>>> Thanks again.
>>> 
>>> 
>>> ________________________________
>>> From: Martin Davis <mtnclimb@...>
>>> To:
>>> Cc: "jts-topo-suite-user@..."
>>> <jts-topo-suite-user@...>
>>> Sent: Wednesday, October 10, 2012 4:40 PM
>>> Subject: Re: [Jts-topo-suite-user] Cache geometry graphs/nodes?
>>> 
>>> This is certainly theoretically possible, but it requires a
>>> substantial rework of the current relate algorithm.  I've recently
>>> been thinking about this exact problem, and have a conceptual design
>>> for how to address this issue (and some other ones as well, such a
>>> small robustness problem that cropped up in the last few months).
>>> 
>>> However, this work will take a significant effort, so it probably
>>> won't get done until there's some funding to support it.
>>> 
>>> In the meantime, you can use the PreparedGeometry API to improve the
>>> performance of some of the more common predicates, such as intersects,
>>> contains, and covers.
>>> 
>>> On Wed, Oct 10, 2012 at 12:46 PM, Shahak Nagiel <snagiel@...> wrote:
>>>> I'm processing a large volume of records, in which I perform
>>>> IntersectionMatrix calculations between geometry pairs via
>>>> RelateOp.relate(geo1, geo2).matches(...).
>>>> 
>>>> Some of these geometries are relatively large/complex (multipolygons with
>>>> several thousand points), but we keep processing them repeatedly.
>>>> 
>>>> Poking (a little) into the code, it looks the relate() method builds up
>>>> GeometryGraph's for both geo's, then passes them off to a RelateComputer,
>>>> which computes nodes and so forth.
>>>> 
>>>> I'm wondering whether there's some trick for pre-processing (compiling?)
>>>> a
>>>> geometry's graph/nodes to expedite this processing (i.e. avoid having to
>>>> re-compute these graphs/nodes repeatedly and just do the minimal work of
>>>> computing edge intersections)?
>> 
>> ------------------------------------------------------------------------------
>> Don't let slow site performance ruin your business. Deploy New Relic APM
>> Deploy New Relic app performance management and know exactly
>> what is happening inside your Ruby, Python, PHP, Java, and .NET app
>> Try New Relic at no cost today and get our sweet Data Nerd shirt too!
>> http://p.sf.net/sfu/newrelic-dev2dev
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts-topo-suite-user@...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>> 
>> 
>> 
>> 
>> ------------------------------------------------------------------------------
>> Everyone hates slow websites. So do we.
>> Make your web apps faster with AppDynamics
>> Download AppDynamics Lite for free today:
>> http://p.sf.net/sfu/appdyn_sfd2d_oct
>> 
>> 
>> 
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts-topo-suite-user@...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>> 
>> 
>> 
>> No virus found in this message.
>> Checked by AVG - http://www.avg.com
>> Version: 2012.0.2221 / Virus Database: 2441/5349 - Release Date: 10/23/12
>> 
>> 
>> 
>> ------------------------------------------------------------------------------
>> Everyone hates slow websites. So do we.
>> Make your web apps faster with AppDynamics
>> Download AppDynamics Lite for free today:
>> http://p.sf.net/sfu/appdyn_sfd2d_oct
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts-topo-suite-user@...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>> 
> 
> ------------------------------------------------------------------------------
> Everyone hates slow websites. So do we.
> Make your web apps faster with AppDynamics
> Download AppDynamics Lite for free today:
> http://p.sf.net/sfu/appdyn_sfd2d_oct
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

On Thu, Oct 25, 2012 at 7:27 AM, Smiley, David W. <dsmiley@...> wrote:
> I'm very familiar with thread-safety / concurrency issues, and I've read that link from Bill Pugh you referenced many times before.  It's a bit dated insofar as double-checked locking is safe now.  There are other approaches too.  Brian Goetz's book "Java Concurrency in Practice" is excellent.

Good info.  Does the Goetz book explain why DCL is now safe?

>
> I looked at your commit today, #674.  It's not clear to me why you are lazy-instantiating the FastSegmentSetIntersectionFinder and PointOnGeometryLocator.  Comments in your class say that these are "expensive".  Okay, I get that.  But it seems that these prepared geometry shape subclasses do nearly nothing else than provide access to these classes, so isn't it a given that these "expensive" class instances will need to be created *anyway*?  If so, then as Jan pointed out, you can simply initialize them in the constructor, make them final, and then not worry about thread-safety for those fields.

The reason for making the two indexes in PG lazily-created is that one
or other of them may not be needed, depending on which predicates are
called on the PG instance.  (E.g. contains(Point) doesn't need the
FastSegmentSetIntersectionFinder - and that is a common use case.

>
> I took a closer look at FastSegmentSetIntersectionFinder.  This class does not appear thread-safe.

Hoo, boy....   Yup, as you point out, the lack of thread-safety goes a
lot deeper than just the initialization.  (In my defence, JTS was
never designed to be thread-safe - but I agree that it's a good goal
to move towards).

Fixing this is going to cause a large number of changes to ripple
through the code.  Just one example: SegmentSetMutualIntersector holds
a SegmentIntersector, and this is set via a setter method. This
probably needs to be changed so that the process method takes all the
state it will be working with - which means changing the class
signature in quite a few classes, as well as fixing the code that
calls them. (And this will break a lot of client code, I suspect,
since I know people are using this API).

And yes, LineIntersector is not thread-safe, and should be created on
each call to FastSegmentSetIntersectionFinder.intersects()

Any ideas on how to mitigate the impact of changes made for thread-safety?


> 1.   For one it doesn't document itself as such, yet a shared instance is returned from PreparedPolygon which does declare to be thread-safe… which is suggestive of a problem, since it will be insufficient for PreparedPolygon to be thread-safe when multiple threads will also need to operate on the shared objects returned from PreparedPolygon's methods.
> 2.  FastSegmentSetIntersectionFinder.intersects() will create a new SegmentIntersectionDetector which uses a LineIntersector static shared instance in its constructor.  Following the rabbit down the rabbit hole, LineIntersector, the shared instance here has state -- a warning sign for thread-safety.  LineIntersector does not document wether it's thread-safe.  And I see no signs of attempts to make it as such, so I don't think it is.
> 3.  FastSegmentSetIntersectionFinder.intersects() will take the SegmentIntersectionDetector it created and set it on SegmentSetMutualIntersector.  That right there is a warning flag for thread-safety since it's modifying state.  SegmentSetMutualIntersector does not declare itself to be thread-safe -- it isn't in fact, which is clear looking at this simple class.
>
> In addition to pointing out these flaws I can try and fix them.
>

On Oct 25, 2012, at 12:47 PM, Martin Davis wrote:

> On Thu, Oct 25, 2012 at 7:27 AM, Smiley, David W. <dsmiley@...> wrote:
>> I'm very familiar with thread-safety / concurrency issues, and I've read that link from Bill Pugh you referenced many times before.  It's a bit dated insofar as double-checked locking is safe now.  There are other approaches too.  Brian Goetz's book "Java Concurrency in Practice" is excellent.

Come to think of it, I shouldn't have said it was dated; since it does say that JDK5 and later fixed DCL so long as the field is volatile.

> Good info.  Does the Goetz book explain why DCL is now safe?

Um, not really.  It says its safe for volatile, but doesn't explain why.  But there is plenty of information prior to this point in the book on the semantics of volatile RE "publication safety" so…
And I'll point out that Brian Goetz's writing in the book on DCL shows he's not a fan of DCL claiming that the net win is small in modern JVMs vs synchronized.  So your solution is not  only simple and effective but recommended.  I admit I use DCL any way; I'll take performance benefits even if small.

> 
>> 
>> I looked at your commit today, #674.  It's not clear to me why you are lazy-instantiating the FastSegmentSetIntersectionFinder and PointOnGeometryLocator.  Comments in your class say that these are "expensive".  Okay, I get that.  But it seems that these prepared geometry shape subclasses do nearly nothing else than provide access to these classes, so isn't it a given that these "expensive" class instances will need to be created *anyway*?  If so, then as Jan pointed out, you can simply initialize them in the constructor, make them final, and then not worry about thread-safety for those fields.
> 
> The reason for making the two indexes in PG lazily-created is that one
> or other of them may not be needed, depending on which predicates are
> called on the PG instance.  (E.g. contains(Point) doesn't need the
> FastSegmentSetIntersectionFinder - and that is a common use case.

Ah, ok.

>> 
>> I took a closer look at FastSegmentSetIntersectionFinder.  This class does not appear thread-safe.
> 
> Hoo, boy....   Yup, as you point out, the lack of thread-safety goes a
> lot deeper than just the initialization.  (In my defence, JTS was
> never designed to be thread-safe - but I agree that it's a good goal
> to move towards).
> 
> Fixing this is going to cause a large number of changes to ripple
> through the code.  Just one example: SegmentSetMutualIntersector holds
> a SegmentIntersector, and this is set via a setter method. This
> probably needs to be changed so that the process method takes all the
> state it will be working with - which means changing the class
> signature in quite a few classes, as well as fixing the code that
> calls them. (And this will break a lot of client code, I suspect,
> since I know people are using this API).
> 
> And yes, LineIntersector is not thread-safe, and should be created on
> each call to FastSegmentSetIntersectionFinder.intersects()
> 
> Any ideas on how to mitigate the impact of changes made for thread-safety?

What exactly needs to be retained for backwards compatibility?  The SegmentIntersector alone shouldn't bee too hard.  Or do you need to support custom subclasses -- that would be hard/messy, and might mean duplicating the classes to then make the duplicates thread-safe.

Assuming you need to only preserve the SegmentIntersector class's public API and not custom subclasses...
SegmentSetMutualntersector (and subclasses) needs to be made an immutable thread-safe object.  I'd start by marking the troubling parts @Deprecated, adding new methods where necessary to pass state.  So the segInt field becomes deprecated as well as the setter for it.  I also think that setBaseSegments(Collection segStrings) should be deprecated; instead the state should be initialized in the constructor of the implementing class, marking fields final if you can.  The one-arg process(Collection segStrings) becomes deprecated and you introduce one that takes an additional SegmentIntersector.  I could try a hack at it and show you a patch, if what I've said seems sensible so far.

~ David

Comments inline.

On Thu, Oct 25, 2012 at 2:54 PM, Smiley, David W. <dsmiley@...> wrote:
>
> On Oct 25, 2012, at 12:47 PM, Martin Davis wrote:
>
>> On Thu, Oct 25, 2012 at 7:27 AM, Smiley, David W. <dsmiley@...> wrote:
>>> I'm very familiar with thread-safety / concurrency issues, and I've read that link from Bill Pugh you referenced many times before.  It's a bit dated insofar as double-checked locking is safe now.  There are other approaches too.  Brian Goetz's book "Java Concurrency in Practice" is excellent.
>
> Come to think of it, I shouldn't have said it was dated; since it does say that JDK5 and later fixed DCL so long as the field is volatile.

Ah, right, I noticed that.  I guess that would work in this situation.
 Still, I prefer "synchronized" - no premature optimization and
simpler code win for me.



>>
>> Any ideas on how to mitigate the impact of changes made for thread-safety?
>
> What exactly needs to be retained for backwards compatibility?  The SegmentIntersector alone shouldn't bee too hard.  Or do you need to support custom subclasses -- that would be hard/messy, and might mean duplicating the classes to then make the duplicates thread-safe.

Who knows?  Any public method or class is fair game for clients.
Although generally for things that are so low-level I'm more willing
to change the API, since presumably anyone using them is able to
handle upgrading.

>
> Assuming you need to only preserve the SegmentIntersector class's public API and not custom subclasses...
> SegmentSetMutualntersector (and subclasses) needs to be made an immutable thread-safe object.  I'd start by marking the troubling parts @Deprecated, adding new methods where necessary to pass state.  So the segInt field becomes deprecated as well as the setter for it.  I also think that setBaseSegments(Collection segStrings) should be deprecated; instead the state should be initialized in the constructor of the implementing class, marking fields final if you can.  The one-arg process(Collection segStrings) becomes deprecated and you introduce one that takes an additional SegmentIntersector.  I could try a hack at it and show you a patch, if what I've said seems sensible so far.

Makes sense.  Sure, let's see a patch.

Do you have any ideas on how to test if the changes really do provide
thread-safety?

Thread-safety of PreparedGeometry<https://sourceforge.net/tracker/?func=detail&aid=3580383&group_id=128875&atid=713120>

On Oct 25, 2012, at 6:26 PM, Martin Davis wrote:
...

Any ideas on how to mitigate the impact of changes made for thread-safety?

What exactly needs to be retained for backwards compatibility?  The SegmentIntersector alone shouldn't bee too hard.  Or do you need to support custom subclasses -- that would be hard/messy, and might mean duplicating the classes to then make the duplicates thread-safe.

Who knows?  Any public method or class is fair game for clients.
Although generally for things that are so low-level I'm more willing
to change the API, since presumably anyone using them is able to
handle upgrading.

I like Lucene's approach to this.  It marks all internal or experimental classes or methods as such, so as a user you know.  And then there's the CHANGES.txt which details changes and how to upgrade.


Assuming you need to only preserve the SegmentIntersector class's public API and not custom subclasses...
SegmentSetMutualntersector (and subclasses) needs to be made an immutable thread-safe object.  I'd start by marking the troubling parts @Deprecated, adding new methods where necessary to pass state.  So the segInt field becomes deprecated as well as the setter for it.  I also think that setBaseSegments(Collection segStrings) should be deprecated; instead the state should be initialized in the constructor of the implementing class, marking fields final if you can.  The one-arg process(Collection segStrings) becomes deprecated and you introduce one that takes an additional SegmentIntersector.  I could try a hack at it and show you a patch, if what I've said seems sensible so far.

Makes sense.  Sure, let's see a patch.

Sourceforge issue: Thread-safety of PreparedGeometry<https://sourceforge.net/tracker/?func=detail&aid=3580383&group_id=128875&atid=713120>

Do you have any ideas on how to test if the changes really do provide
thread-safety?

Section 12.4 of Java Concurrency in Practice is relevant here.  The first technique mentioned is peer review, which I think is critical.  It's why I felt compelled to look at the supposedly thread-safe PreparedGeometry.  Then there are static analysis tools, such as FindBugs which to some extent can help if it sees you use synchronized or @Threadsafe and related annotations: http://jcip.net/annotations/doc/index.html  Another thing is to try and structure classes that claim to be thread-safe to more clearly be thread-safe.  For example, often times, a Thread-safe class should also be immutable, and JTS's PreparedGeometry (and related classes) fit this description.  So in my patch I made the members final, and where they weren't I added a TODO comment to make them so.  Due to @Deprecated method support, I couldn't always make them final.  And where the final field is itself potentially modifiable, it's important to at least add comments that the object, such as SpatialIndex, shouldn't be modified.

~ David

On Fri, Oct 26, 2012 at 6:35 AM, Smiley, David W. <dsmiley@...> wrote:

> Makes sense.  Sure, let's see a patch.
>
>
> Sourceforge issue: Thread-safety of PreparedGeometry

Thanks.  Due to timelines and compatibility I'll probably wait until
after the 1.13 release to look at applying this.

>
> Do you have any ideas on how to test if the changes really do provide
> thread-safety?
>
>
> Section 12.4 of Java Concurrency in Practice is relevant here.  The first
> technique mentioned is peer review, which I think is critical.  It's why I
> felt compelled to look at the supposedly thread-safe PreparedGeometry.  Then
> there are static analysis tools, such as FindBugs which to some extent can
> help if it sees you use synchronized or @Threadsafe and related annotations:
> http://jcip.net/annotations/doc/index.html  Another thing is to try and
> structure classes that claim to be thread-safe to more clearly be
> thread-safe.  For example, often times, a Thread-safe class should also be
> immutable, and JTS's PreparedGeometry (and related classes) fit this
> description.  So in my patch I made the members final, and where they
> weren't I added a TODO comment to make them so.  Due to @Deprecated method
> support, I couldn't always make them final.  And where the final field is
> itself potentially modifiable, it's important to at least add comments that
> the object, such as SpatialIndex, shouldn't be modified.

Good advice - thanks.

On Oct 29, 2012, at 2:10 PM, Martin Davis wrote:

Thanks.  Due to timelines and compatibility I'll probably wait until
after the 1.13 release to look at applying this.

Ok.  I suggest you at least start marking methods @Deprecated where appropriate, as a warning now before 1.13 is shipped.

~ David