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
|