Update to 3.9?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Update to 3.9?

Paul Ramsey
Hey all, just truing up what's underway and nearly there...

- Am I right that Z coordinates are nearly done? What's the status there?

I've been trying to address some performance issues, with some success and some ... other things.

The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.

While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.

I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). https://github.com/pramsey/geos/tree/monotone-chain-builder

I've put that work to the side for now.

All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS.  It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.

I think we're close, looking forward to release :)

P
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Regina Obe

> All the performance talk is mostly because JTS still runs a lot faster
than GEOS
> for some bulk processing. My current test is a big union of watershed
> boundaries, about 6MB of data, which takes about 20s under GEOS and
> about 25% of that under JTS.  It's a big gap, and in theory the two code
bases
> are pretty aligned right now. Same overlayNG engine, etc. So I figure
there

> has to be a big implementation ball of performance hiding under the covers
> somewhere. No luck thus far.
>
> I think we're close, looking forward to release :)
>
> P
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

You have your sample watershed data set.  Would like to test it out myself.

Thanks,
Regina

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Sandro Santilli-4
In reply to this post by Paul Ramsey
On Tue, Nov 24, 2020 at 03:44:20PM -0800, Paul Ramsey wrote:
> Hey all, just truing up what's underway and nearly there...
>
> - Am I right that Z coordinates are nearly done? What's the status there?

I plan to port the last bit of this eary next week.

--strk;
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Sandro Santilli-4
On Wed, Nov 25, 2020 at 01:35:31PM +0100, Sandro Santilli wrote:
> On Tue, Nov 24, 2020 at 03:44:20PM -0800, Paul Ramsey wrote:
> > Hey all, just truing up what's underway and nearly there...
> >
> > - Am I right that Z coordinates are nearly done? What's the status there?
>
> I plan to port the last bit of this eary next week.

For the record: this is tracked by
https://trac.osgeo.org/geos/ticket/1070
which I marked as blocker for release

Is reported to be the only blocker for 3.9.0 (please mark any other
ticket as blocker for easier management):
https://trac.osgeo.org/geos/query?priority=blocker&status=assigned&status=new&status=reopened&milestone=3.9.0&col=id&col=summary&col=status&col=priority&col=owner&col=type&col=milestone&order=priority

--strk;
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Martin Davis-3
In reply to this post by Paul Ramsey


On Tue, Nov 24, 2020 at 3:44 PM Paul Ramsey <[hidden email]> wrote:

- Am I right that Z coordinates are nearly done? What's the status there?

I'm going to say that the JTS Z work is functionally complete.  It interpolates Z values where possible, and populates missing Z values from an ElevationModel patterned after the one currently in GEOS.  I think GEOS does interpolation along a line as well, but that seems questionable to me, so have not implemented that.  

So the final step is to finish porting the JTS code to GEOS, and then try out the code in PostGIS. No idea how that will match up to the Z unit tests in PostGIS - but I'm not sure they are based on any actual requirements anyway?

The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.

Nice work. 

All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS.  It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.

That's quite a difference.  Maybe the JVM JIT really is magic? 

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Paul Ramsey
In reply to this post by Regina Obe


> On Nov 24, 2020, at 5:01 PM, Regina Obe <[hidden email]> wrote:
>
>
>> All the performance talk is mostly because JTS still runs a lot faster
> than GEOS
>> for some bulk processing. My current test is a big union of watershed
>> boundaries, about 6MB of data, which takes about 20s under GEOS and
>> about 25% of that under JTS.  It's a big gap, and in theory the two code
> bases
>> are pretty aligned right now. Same overlayNG engine, etc. So I figure
> there
>> has to be a big implementation ball of performance hiding under the covers
>> somewhere. No luck thus far.
>>
>> I think we're close, looking forward to release :)
>>
>> P
>> _______________________________________________
>> geos-devel mailing list
>> [hidden email]
>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> You have your sample watershed data set.  Would like to test it out myself.

https://www.dropbox.com/s/9ruvs6gxe3yl93c/wsa_vi.sql.bz2?dl=0

I union all these. It takes about 20s on my Air.

p

>
> Thanks,
> Regina
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Daniel Baston
After collecting the inputs and writing to WKT:

\copy (select st_astext(st_collect(geom), 18) from wsa_vi) to ~/data/wsa.wkt;

I'm seeing 6 seconds in GEOS (not including WKT parsing)

bin/perf_unary ~/data/wsa.wkt union
# Reading geometries from /home/dan/data/wsa.wkt
# Read 1 geometries.
# 6,137,885 usec

vs 14s in JTS (including WKT parsing)

time bin/jtsop.sh -a ~/data/wsa.wkt -op Overlay.unaryUnion  
# 14.43s user 0.47s system 202% cpu 7.354 total

Dan



On Wed, Nov 25, 2020 at 8:21 PM Paul Ramsey <[hidden email]> wrote:


> On Nov 24, 2020, at 5:01 PM, Regina Obe <[hidden email]> wrote:
>
>
>> All the performance talk is mostly because JTS still runs a lot faster
> than GEOS
>> for some bulk processing. My current test is a big union of watershed
>> boundaries, about 6MB of data, which takes about 20s under GEOS and
>> about 25% of that under JTS.  It's a big gap, and in theory the two code
> bases
>> are pretty aligned right now. Same overlayNG engine, etc. So I figure
> there
>> has to be a big implementation ball of performance hiding under the covers
>> somewhere. No luck thus far.
>>
>> I think we're close, looking forward to release :)
>>
>> P
>> _______________________________________________
>> geos-devel mailing list
>> [hidden email]
>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> You have your sample watershed data set.  Would like to test it out myself.

https://www.dropbox.com/s/9ruvs6gxe3yl93c/wsa_vi.sql.bz2?dl=0

I union all these. It takes about 20s on my Air.

p

>
> Thanks,
> Regina
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Martin Davis-3
Actually OverlayNGRobust.unaryUnion will compare the current OverlayNG code to GEOS. However, OverlayNG is likely to be slower, in any case.

So:
GEOS - 6.1 s
JTS 14.4 s

That's an impressive difference in favour of GEOS.  I wonder why Paul's timings are so different?

On Wed, Nov 25, 2020 at 6:00 PM Daniel Baston <[hidden email]> wrote:
After collecting the inputs and writing to WKT:

\copy (select st_astext(st_collect(geom), 18) from wsa_vi) to ~/data/wsa.wkt;

I'm seeing 6 seconds in GEOS (not including WKT parsing)

bin/perf_unary ~/data/wsa.wkt union
# Reading geometries from /home/dan/data/wsa.wkt
# Read 1 geometries.
# 6,137,885 usec

vs 14s in JTS (including WKT parsing)

time bin/jtsop.sh -a ~/data/wsa.wkt -op Overlay.unaryUnion  
# 14.43s user 0.47s system 202% cpu 7.354 total

Dan



On Wed, Nov 25, 2020 at 8:21 PM Paul Ramsey <[hidden email]> wrote:


> On Nov 24, 2020, at 5:01 PM, Regina Obe <[hidden email]> wrote:
>
>
>> All the performance talk is mostly because JTS still runs a lot faster
> than GEOS
>> for some bulk processing. My current test is a big union of watershed
>> boundaries, about 6MB of data, which takes about 20s under GEOS and
>> about 25% of that under JTS.  It's a big gap, and in theory the two code
> bases
>> are pretty aligned right now. Same overlayNG engine, etc. So I figure
> there
>> has to be a big implementation ball of performance hiding under the covers
>> somewhere. No luck thus far.
>>
>> I think we're close, looking forward to release :)
>>
>> P
>> _______________________________________________
>> geos-devel mailing list
>> [hidden email]
>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> You have your sample watershed data set.  Would like to test it out myself.

https://www.dropbox.com/s/9ruvs6gxe3yl93c/wsa_vi.sql.bz2?dl=0

I union all these. It takes about 20s on my Air.

p

>
> Thanks,
> Regina
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Paul Ramsey


> On Nov 25, 2020, at 6:41 PM, Martin Davis <[hidden email]> wrote:
>
> Actually OverlayNGRobust.unaryUnion will compare the current OverlayNG code to GEOS. However, OverlayNG is likely to be slower, in any case.
>
> So:
> GEOS - 6.1 s
> JTS 14.4 s
>
> That's an impressive difference in favour of GEOS.  I wonder why Paul's timings are so different?

OMG, I wonder... I have a debug build of GEOS (because, you know, debugging). Is that it? Otherwise, are both tests (JTS and GEOS side) running through the OverlayNGRobust? I suppose I should ask: how do I run the JTS test? Then I can cut out the middleman and run them all myself?

P

>
> On Wed, Nov 25, 2020 at 6:00 PM Daniel Baston <[hidden email]> wrote:
> After collecting the inputs and writing to WKT:
>
> \copy (select st_astext(st_collect(geom), 18) from wsa_vi) to ~/data/wsa.wkt;
>
> I'm seeing 6 seconds in GEOS (not including WKT parsing)
>
> bin/perf_unary ~/data/wsa.wkt union
> # Reading geometries from /home/dan/data/wsa.wkt
> # Read 1 geometries.
> # 6,137,885 usec
>
> vs 14s in JTS (including WKT parsing)
>
> time bin/jtsop.sh -a ~/data/wsa.wkt -op Overlay.unaryUnion  
> # 14.43s user 0.47s system 202% cpu 7.354 total
>
> Dan
>
>
>
> On Wed, Nov 25, 2020 at 8:21 PM Paul Ramsey <[hidden email]> wrote:
>
>
> > On Nov 24, 2020, at 5:01 PM, Regina Obe <[hidden email]> wrote:
> >
> >
> >> All the performance talk is mostly because JTS still runs a lot faster
> > than GEOS
> >> for some bulk processing. My current test is a big union of watershed
> >> boundaries, about 6MB of data, which takes about 20s under GEOS and
> >> about 25% of that under JTS.  It's a big gap, and in theory the two code
> > bases
> >> are pretty aligned right now. Same overlayNG engine, etc. So I figure
> > there
> >> has to be a big implementation ball of performance hiding under the covers
> >> somewhere. No luck thus far.
> >>
> >> I think we're close, looking forward to release :)
> >>
> >> P
> >> _______________________________________________
> >> geos-devel mailing list
> >> [hidden email]
> >> https://lists.osgeo.org/mailman/listinfo/geos-devel
> >
> > You have your sample watershed data set.  Would like to test it out myself.
>
> https://www.dropbox.com/s/9ruvs6gxe3yl93c/wsa_vi.sql.bz2?dl=0
>
> I union all these. It takes about 20s on my Air.
>
> p
>
> >
> > Thanks,
> > Regina
> >
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Martin Davis-3
Seems best to try a non-debug build...

To run in JTS you can use:

time bin/jtsop.sh -a ~/data/wsa.wkt -op OverlayNGRobust.unaryUnion 

You should run off master for this (or a very recent pull)

Actually it's better to use 

bin/jtsop.sh -time -a ~/data/wsa.wkt -op OverlayNGRobust.unaryUnion 

That will time only the operation, excluding the I/O.


On Wed, Nov 25, 2020 at 7:30 PM Paul Ramsey <[hidden email]> wrote:


> On Nov 25, 2020, at 6:41 PM, Martin Davis <[hidden email]> wrote:
>
> Actually OverlayNGRobust.unaryUnion will compare the current OverlayNG code to GEOS. However, OverlayNG is likely to be slower, in any case.
>
> So:
> GEOS - 6.1 s
> JTS 14.4 s
>
> That's an impressive difference in favour of GEOS.  I wonder why Paul's timings are so different?

OMG, I wonder... I have a debug build of GEOS (because, you know, debugging). Is that it? Otherwise, are both tests (JTS and GEOS side) running through the OverlayNGRobust? I suppose I should ask: how do I run the JTS test? Then I can cut out the middleman and run them all myself?

P

>
> On Wed, Nov 25, 2020 at 6:00 PM Daniel Baston <[hidden email]> wrote:
> After collecting the inputs and writing to WKT:
>
> \copy (select st_astext(st_collect(geom), 18) from wsa_vi) to ~/data/wsa.wkt;
>
> I'm seeing 6 seconds in GEOS (not including WKT parsing)
>
> bin/perf_unary ~/data/wsa.wkt union
> # Reading geometries from /home/dan/data/wsa.wkt
> # Read 1 geometries.
> # 6,137,885 usec
>
> vs 14s in JTS (including WKT parsing)
>
> time bin/jtsop.sh -a ~/data/wsa.wkt -op Overlay.unaryUnion   
> # 14.43s user 0.47s system 202% cpu 7.354 total
>
> Dan
>
>
>
> On Wed, Nov 25, 2020 at 8:21 PM Paul Ramsey <[hidden email]> wrote:
>
>
> > On Nov 24, 2020, at 5:01 PM, Regina Obe <[hidden email]> wrote:
> >
> >
> >> All the performance talk is mostly because JTS still runs a lot faster
> > than GEOS
> >> for some bulk processing. My current test is a big union of watershed
> >> boundaries, about 6MB of data, which takes about 20s under GEOS and
> >> about 25% of that under JTS.  It's a big gap, and in theory the two code
> > bases
> >> are pretty aligned right now. Same overlayNG engine, etc. So I figure
> > there
> >> has to be a big implementation ball of performance hiding under the covers
> >> somewhere. No luck thus far.
> >>
> >> I think we're close, looking forward to release :)
> >>
> >> P
> >> _______________________________________________
> >> geos-devel mailing list
> >> [hidden email]
> >> https://lists.osgeo.org/mailman/listinfo/geos-devel
> >
> > You have your sample watershed data set.  Would like to test it out myself.
>
> https://www.dropbox.com/s/9ruvs6gxe3yl93c/wsa_vi.sql.bz2?dl=0
>
> I union all these. It takes about 20s on my Air.
>
> p
>
> >
> > Thanks,
> > Regina
> >
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Paul Ramsey
Well then, good news from me, since with a Release build, I can run that union in 4.7s in GEOS and 6.6s in JTS.
w00T!
Now I'm wondering if my other performance work, that yielded relatively little in Debug might be bigger winners in Release...
P.

> On Nov 25, 2020, at 7:37 PM, Martin Davis <[hidden email]> wrote:
>
> Seems best to try a non-debug build...
>
> To run in JTS you can use:
>
> time bin/jtsop.sh -a ~/data/wsa.wkt -op OverlayNGRobust.unaryUnion
>
> You should run off master for this (or a very recent pull)
>
> Actually it's better to use
>
> bin/jtsop.sh -time -a ~/data/wsa.wkt -op OverlayNGRobust.unaryUnion
>
> That will time only the operation, excluding the I/O.
>
>
> On Wed, Nov 25, 2020 at 7:30 PM Paul Ramsey <[hidden email]> wrote:
>
>
> > On Nov 25, 2020, at 6:41 PM, Martin Davis <[hidden email]> wrote:
> >
> > Actually OverlayNGRobust.unaryUnion will compare the current OverlayNG code to GEOS. However, OverlayNG is likely to be slower, in any case.
> >
> > So:
> > GEOS - 6.1 s
> > JTS 14.4 s
> >
> > That's an impressive difference in favour of GEOS.  I wonder why Paul's timings are so different?
>
> OMG, I wonder... I have a debug build of GEOS (because, you know, debugging). Is that it? Otherwise, are both tests (JTS and GEOS side) running through the OverlayNGRobust? I suppose I should ask: how do I run the JTS test? Then I can cut out the middleman and run them all myself?
>
> P
>
> >
> > On Wed, Nov 25, 2020 at 6:00 PM Daniel Baston <[hidden email]> wrote:
> > After collecting the inputs and writing to WKT:
> >
> > \copy (select st_astext(st_collect(geom), 18) from wsa_vi) to ~/data/wsa.wkt;
> >
> > I'm seeing 6 seconds in GEOS (not including WKT parsing)
> >
> > bin/perf_unary ~/data/wsa.wkt union
> > # Reading geometries from /home/dan/data/wsa.wkt
> > # Read 1 geometries.
> > # 6,137,885 usec
> >
> > vs 14s in JTS (including WKT parsing)
> >
> > time bin/jtsop.sh -a ~/data/wsa.wkt -op Overlay.unaryUnion  
> > # 14.43s user 0.47s system 202% cpu 7.354 total
> >
> > Dan
> >
> >
> >
> > On Wed, Nov 25, 2020 at 8:21 PM Paul Ramsey <[hidden email]> wrote:
> >
> >
> > > On Nov 24, 2020, at 5:01 PM, Regina Obe <[hidden email]> wrote:
> > >
> > >
> > >> All the performance talk is mostly because JTS still runs a lot faster
> > > than GEOS
> > >> for some bulk processing. My current test is a big union of watershed
> > >> boundaries, about 6MB of data, which takes about 20s under GEOS and
> > >> about 25% of that under JTS.  It's a big gap, and in theory the two code
> > > bases
> > >> are pretty aligned right now. Same overlayNG engine, etc. So I figure
> > > there
> > >> has to be a big implementation ball of performance hiding under the covers
> > >> somewhere. No luck thus far.
> > >>
> > >> I think we're close, looking forward to release :)
> > >>
> > >> P
> > >> _______________________________________________
> > >> geos-devel mailing list
> > >> [hidden email]
> > >> https://lists.osgeo.org/mailman/listinfo/geos-devel
> > >
> > > You have your sample watershed data set.  Would like to test it out myself.
> >
> > https://www.dropbox.com/s/9ruvs6gxe3yl93c/wsa_vi.sql.bz2?dl=0
> >
> > I union all these. It takes about 20s on my Air.
> >
> > p
> >
> > >
> > > Thanks,
> > > Regina
> > >
> > > _______________________________________________
> > > geos-devel mailing list
> > > [hidden email]
> > > https://lists.osgeo.org/mailman/listinfo/geos-devel
> >
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Martin Davis-3
Excellent news for GEOS... but I'm a little sad for JTS.  

Release FTW!

On Wed, Nov 25, 2020 at 7:49 PM Paul Ramsey <[hidden email]> wrote:
Well then, good news from me, since with a Release build, I can run that union in 4.7s in GEOS and 6.6s in JTS.
w00T!
Now I'm wondering if my other performance work, that yielded relatively little in Debug might be bigger winners in Release...
P.

> On Nov 25, 2020, at 7:37 PM, Martin Davis <[hidden email]> wrote:
>
> Seems best to try a non-debug build...
>
> To run in JTS you can use:
>
> time bin/jtsop.sh -a ~/data/wsa.wkt -op OverlayNGRobust.unaryUnion
>
> You should run off master for this (or a very recent pull)
>
> Actually it's better to use
>
> bin/jtsop.sh -time -a ~/data/wsa.wkt -op OverlayNGRobust.unaryUnion
>
> That will time only the operation, excluding the I/O.
>
>
> On Wed, Nov 25, 2020 at 7:30 PM Paul Ramsey <[hidden email]> wrote:
>
>
> > On Nov 25, 2020, at 6:41 PM, Martin Davis <[hidden email]> wrote:
> >
> > Actually OverlayNGRobust.unaryUnion will compare the current OverlayNG code to GEOS. However, OverlayNG is likely to be slower, in any case.
> >
> > So:
> > GEOS - 6.1 s
> > JTS 14.4 s
> >
> > That's an impressive difference in favour of GEOS.  I wonder why Paul's timings are so different?
>
> OMG, I wonder... I have a debug build of GEOS (because, you know, debugging). Is that it? Otherwise, are both tests (JTS and GEOS side) running through the OverlayNGRobust? I suppose I should ask: how do I run the JTS test? Then I can cut out the middleman and run them all myself?
>
> P
>
> >
> > On Wed, Nov 25, 2020 at 6:00 PM Daniel Baston <[hidden email]> wrote:
> > After collecting the inputs and writing to WKT:
> >
> > \copy (select st_astext(st_collect(geom), 18) from wsa_vi) to ~/data/wsa.wkt;
> >
> > I'm seeing 6 seconds in GEOS (not including WKT parsing)
> >
> > bin/perf_unary ~/data/wsa.wkt union
> > # Reading geometries from /home/dan/data/wsa.wkt
> > # Read 1 geometries.
> > # 6,137,885 usec
> >
> > vs 14s in JTS (including WKT parsing)
> >
> > time bin/jtsop.sh -a ~/data/wsa.wkt -op Overlay.unaryUnion   
> > # 14.43s user 0.47s system 202% cpu 7.354 total
> >
> > Dan
> >
> >
> >
> > On Wed, Nov 25, 2020 at 8:21 PM Paul Ramsey <[hidden email]> wrote:
> >
> >
> > > On Nov 24, 2020, at 5:01 PM, Regina Obe <[hidden email]> wrote:
> > >
> > >
> > >> All the performance talk is mostly because JTS still runs a lot faster
> > > than GEOS
> > >> for some bulk processing. My current test is a big union of watershed
> > >> boundaries, about 6MB of data, which takes about 20s under GEOS and
> > >> about 25% of that under JTS.  It's a big gap, and in theory the two code
> > > bases
> > >> are pretty aligned right now. Same overlayNG engine, etc. So I figure
> > > there
> > >> has to be a big implementation ball of performance hiding under the covers
> > >> somewhere. No luck thus far.
> > >>
> > >> I think we're close, looking forward to release :)
> > >>
> > >> P
> > >> _______________________________________________
> > >> geos-devel mailing list
> > >> [hidden email]
> > >> https://lists.osgeo.org/mailman/listinfo/geos-devel
> > >
> > > You have your sample watershed data set.  Would like to test it out myself.
> >
> > https://www.dropbox.com/s/9ruvs6gxe3yl93c/wsa_vi.sql.bz2?dl=0
> >
> > I union all these. It takes about 20s on my Air.
> >
> > p
> >
> > >
> > > Thanks,
> > > Regina
> > >
> > > _______________________________________________
> > > geos-devel mailing list
> > > [hidden email]
> > > https://lists.osgeo.org/mailman/listinfo/geos-devel
> >
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Joris Van den Bossche
In reply to this post by Paul Ramsey
Hi all,

On the CI of PyGEOS we have a build testing against GEOS master, and somewhere in the last 4 days, a lot of the STRtree tests started failing (see eg https://github.com/pygeos/pygeos/runs/1465460418#step:9:86). Looking at the commits of the last days, this might be related to the SimpleSTRtree work?

A small (python) example of a tree consisting of a single point, which no longer is returned when querying the tree with a big polygon that certainly contains the point:

Using released version of GEOS:

>>> import pygeos
>>> pygeos.geos_version
(3, 8, 1)
>>> point = pygeos.Geometry("POINT (2 3)")
>>> tree = pygeos.STRtree([point])
>>> tree.query(pygeos.box(0, 0, 10, 10))
array([0])

This is correctly returning the index of the single point. But when running with the latest GEOS master, the query doesn't find any point of the tree:

>>> import pygeos
>>> pygeos.geos_version
(3, 9, 0)
>>> point = pygeos.Geometry("POINT (2 3)")
>>> tree = pygeos.STRtree([point])
>>> tree.query(pygeos.box(0, 0, 10, 10))
array([], dtype=int64)

Are there changes expected in how the STRtree C API functions or required changes in user code? Or maybe we are using it in some incorrect/unexpected way? (code is at https://github.com/pygeos/pygeos/blob/master/src/strtree.c)

Best,
Joris


On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <[hidden email]> wrote:
Hey all, just truing up what's underway and nearly there...

- Am I right that Z coordinates are nearly done? What's the status there?

I've been trying to address some performance issues, with some success and some ... other things.

The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.

While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.

I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). https://github.com/pramsey/geos/tree/monotone-chain-builder

I've put that work to the side for now.

All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS.  It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.

I think we're close, looking forward to release :)

P
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Paul Ramsey


> On Nov 28, 2020, at 8:11 AM, Joris Van den Bossche <[hidden email]> wrote:
>
> Hi all,
>
> On the CI of PyGEOS we have a build testing against GEOS master, and somewhere in the last 4 days, a lot of the STRtree tests started failing (see eg https://github.com/pygeos/pygeos/runs/1465460418#step:9:86). Looking at the commits of the last days, this might be related to the SimpleSTRtree work?
>
> A small (python) example of a tree consisting of a single point, which no longer is returned when querying the tree with a big polygon that certainly contains the point:
>
> Using released version of GEOS:
>
> >>> import pygeos
> >>> pygeos.geos_version
> (3, 8, 1)
> >>> point = pygeos.Geometry("POINT (2 3)")
> >>> tree = pygeos.STRtree([point])
> >>> tree.query(pygeos.box(0, 0, 10, 10))
> array([0])
>
> This is correctly returning the index of the single point. But when running with the latest GEOS master, the query doesn't find any point of the tree:
>
> >>> import pygeos
> >>> pygeos.geos_version
> (3, 9, 0)
> >>> point = pygeos.Geometry("POINT (2 3)")
> >>> tree = pygeos.STRtree([point])
> >>> tree.query(pygeos.box(0, 0, 10, 10))
> array([], dtype=int64)
>
> Are there changes expected in how the STRtree C API functions or required changes in user code? Or maybe we are using it in some incorrect/unexpected way? (code is at https://github.com/pygeos/pygeos/blob/master/src/strtree.c)

There are changes, I don't think you're mis-using anything. I swapped the CAPI to use the SimpleSTRtree, figuring it would be good to share the performance win with downstream. However, I can swap it back to the original STRtree if this remains a problem.

One thing I noticed when trying to construct GEOS envelopes directly was that annoyingly they were xmin xmax, ymin ymax, but I doubt that would be a problem in your pre-existing working test.

I just reconstructed your test in the GEOS CAPI suite, and it works as one would expect. (Namely, it finds the one point.) So I'm not sure why your test is getting different results.


// querying tree with box
template<>
template<>
void object::test<8>
()
{
    GEOSSTRtree* tree = GEOSSTRtree_create(10);
    GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
    GEOSSTRtree_insert(tree, g, g);
    GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");

    typedef std::vector<GEOSGeometry*> GList;
    GList geoms;
    ensure_equals(geoms.size(), 0);
    GEOSSTRtree_query(
        tree,
        q,
        [](void* item, void* userdata) {
            GList* geoms = (GList*)userdata;
            geoms->push_back((GEOSGeometry*)item);
        },
        &geoms);

    ensure_equals(geoms.size(), 1);
    const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);

    double x = -1;
    double y = -1;
    GEOSCoordSeq_getXY(seq,  0, &x, &y);
    ensure_equals(x, 2.0);
    ensure_equals(y, 3.0);

    GEOSGeom_destroy(q);
    GEOSGeom_destroy(g);
    GEOSSTRtree_destroy(tree);
}





>
> Best,
> Joris
>
>
> On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <[hidden email]> wrote:
> Hey all, just truing up what's underway and nearly there...
>
> - Am I right that Z coordinates are nearly done? What's the status there?
>
> I've been trying to address some performance issues, with some success and some ... other things.
>
> The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.
>
> While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.
>
> I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). https://github.com/pramsey/geos/tree/monotone-chain-builder
>
> I've put that work to the side for now.
>
> All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS.  It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.
>
> I think we're close, looking forward to release :)
>
> P
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Joris Van den Bossche
Thanks for trying to reproduce it in C/C++. One obvious difference that I can spot is that we use an integer for the "item" that gets inserted, and not the geometry itself, but I wouldn't expect that to influence the result.
Although, trying to update your test case to do that, the test fails. But that might also be an issue on my side due to my limited C++ experience (it already fails on the "geoms.size()" check):

--- a/tests/unit/capi/GEOSSTRtreeTest.cpp
+++ b/tests/unit/capi/GEOSSTRtreeTest.cpp
@@ -268,10 +268,11 @@ void object::test<8>
 {
     GEOSSTRtree* tree = GEOSSTRtree_create(10);
     GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
-    GEOSSTRtree_insert(tree, g, g);
+    int idx = 0;
+    GEOSSTRtree_insert(tree, g, (void*)idx);
     GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
 
-    typedef std::vector<GEOSGeometry*> GList;
+    typedef std::vector<int> GList;
     GList geoms;
     ensure_equals(geoms.size(), 0);
     GEOSSTRtree_query(
@@ -279,23 +280,16 @@ void object::test<8>
         q,
         [](void* item, void* userdata) {
             GList* geoms = (GList*)userdata;
-            geoms->push_back((GEOSGeometry*)item);
+            geoms->push_back(*((int *)item));
         },
         &geoms);
 
     ensure_equals(geoms.size(), 1);
-    const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
-
-    double x = -1;
-    double y = -1;
-    GEOSCoordSeq_getXY(seq,  0, &x, &y);
-    ensure_equals(x, 2.0);
-    ensure_equals(y, 3.0);
+    ensure_equals(geoms.at(0), 0);
 

On Sat, 28 Nov 2020 at 20:55, Paul Ramsey <[hidden email]> wrote:


> On Nov 28, 2020, at 8:11 AM, Joris Van den Bossche <[hidden email]> wrote:
>
> Hi all,
>
> On the CI of PyGEOS we have a build testing against GEOS master, and somewhere in the last 4 days, a lot of the STRtree tests started failing (see eg https://github.com/pygeos/pygeos/runs/1465460418#step:9:86). Looking at the commits of the last days, this might be related to the SimpleSTRtree work?
>
> A small (python) example of a tree consisting of a single point, which no longer is returned when querying the tree with a big polygon that certainly contains the point:
>
> Using released version of GEOS:
>
> >>> import pygeos
> >>> pygeos.geos_version
> (3, 8, 1)
> >>> point = pygeos.Geometry("POINT (2 3)")
> >>> tree = pygeos.STRtree([point])
> >>> tree.query(pygeos.box(0, 0, 10, 10))
> array([0])
>
> This is correctly returning the index of the single point. But when running with the latest GEOS master, the query doesn't find any point of the tree:
>
> >>> import pygeos
> >>> pygeos.geos_version
> (3, 9, 0)
> >>> point = pygeos.Geometry("POINT (2 3)")
> >>> tree = pygeos.STRtree([point])
> >>> tree.query(pygeos.box(0, 0, 10, 10))
> array([], dtype=int64)
>
> Are there changes expected in how the STRtree C API functions or required changes in user code? Or maybe we are using it in some incorrect/unexpected way? (code is at https://github.com/pygeos/pygeos/blob/master/src/strtree.c)

There are changes, I don't think you're mis-using anything. I swapped the CAPI to use the SimpleSTRtree, figuring it would be good to share the performance win with downstream. However, I can swap it back to the original STRtree if this remains a problem.

One thing I noticed when trying to construct GEOS envelopes directly was that annoyingly they were xmin xmax, ymin ymax, but I doubt that would be a problem in your pre-existing working test.

I just reconstructed your test in the GEOS CAPI suite, and it works as one would expect. (Namely, it finds the one point.) So I'm not sure why your test is getting different results.


// querying tree with box
template<>
template<>
void object::test<8>
()
{
    GEOSSTRtree* tree = GEOSSTRtree_create(10);
    GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
    GEOSSTRtree_insert(tree, g, g);
    GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");

    typedef std::vector<GEOSGeometry*> GList;
    GList geoms;
    ensure_equals(geoms.size(), 0);
    GEOSSTRtree_query(
        tree,
        q,
        [](void* item, void* userdata) {
            GList* geoms = (GList*)userdata;
            geoms->push_back((GEOSGeometry*)item);
        },
        &geoms);

    ensure_equals(geoms.size(), 1);
    const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);

    double x = -1;
    double y = -1;
    GEOSCoordSeq_getXY(seq,  0, &x, &y);
    ensure_equals(x, 2.0);
    ensure_equals(y, 3.0);

    GEOSGeom_destroy(q);
    GEOSGeom_destroy(g);
    GEOSSTRtree_destroy(tree);
}





>
> Best,
> Joris
>
>
> On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <[hidden email]> wrote:
> Hey all, just truing up what's underway and nearly there...
>
> - Am I right that Z coordinates are nearly done? What's the status there?
>
> I've been trying to address some performance issues, with some success and some ... other things.
>
> The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.
>
> While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.
>
> I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). https://github.com/pramsey/geos/tree/monotone-chain-builder
>
> I've put that work to the side for now.
>
> All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS.  It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.
>
> I think we're close, looking forward to release :)
>
> P
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Paul Ramsey


> On Nov 28, 2020, at 12:44 PM, Joris Van den Bossche <[hidden email]> wrote:
>
> Thanks for trying to reproduce it in C/C++. One obvious difference that I can spot is that we use an integer for the "item" that gets inserted, and not the geometry itself, but I wouldn't expect that to influence the result.
> Although, trying to update your test case to do that, the test fails. But that might also be an issue on my side due to my limited C++ experience (it already fails on the "geoms.size()" check):

Nope still not seeing it... one small mistake in your query, trying to cast the int to a void, instead of passing in a the pointer to the address, here's one that works. Unfortunately that leaves us no closer to knowing why the SimpleSTRtree is unhappy in the python context. I fear I may just have to revert the CAPI to the old tree.


// querying tree with box
template<>
template<>
void object::test<9>
()
{
    GEOSSTRtree* tree = GEOSSTRtree_create(10);

    GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
    int payload = 876;
    GEOSSTRtree_insert(tree, g, &payload);

    GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");

    typedef std::vector<int*> IList;
    IList items;
    ensure_equals(items.size(), 0);
    GEOSSTRtree_query(
        tree,
        q,
        [](void* item, void* userdata) {
            IList* items = (IList*)userdata;
            items->push_back((int*)item);
        },
        &items);

    ensure_equals(items.size(), 1);

    ensure_equals(*(items[0]), payload);

    GEOSGeom_destroy(q);
    GEOSGeom_destroy(g);
    GEOSSTRtree_destroy(tree);
}




>
> --- a/tests/unit/capi/GEOSSTRtreeTest.cpp
> +++ b/tests/unit/capi/GEOSSTRtreeTest.cpp
> @@ -268,10 +268,11 @@ void object::test<8>
>  {
>      GEOSSTRtree* tree = GEOSSTRtree_create(10);
>      GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
> -    GEOSSTRtree_insert(tree, g, g);
> +    int idx = 0;
> +    GEOSSTRtree_insert(tree, g, (void*)idx);
>      GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>  
> -    typedef std::vector<GEOSGeometry*> GList;
> +    typedef std::vector<int> GList;
>      GList geoms;
>      ensure_equals(geoms.size(), 0);
>      GEOSSTRtree_query(
> @@ -279,23 +280,16 @@ void object::test<8>
>          q,
>          [](void* item, void* userdata) {
>              GList* geoms = (GList*)userdata;
> -            geoms->push_back((GEOSGeometry*)item);
> +            geoms->push_back(*((int *)item));
>          },
>          &geoms);
>  
>      ensure_equals(geoms.size(), 1);
> -    const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
> -
> -    double x = -1;
> -    double y = -1;
> -    GEOSCoordSeq_getXY(seq,  0, &x, &y);
> -    ensure_equals(x, 2.0);
> -    ensure_equals(y, 3.0);
> +    ensure_equals(geoms.at(0), 0);
>  
>
> On Sat, 28 Nov 2020 at 20:55, Paul Ramsey <[hidden email]> wrote:
>
>
> > On Nov 28, 2020, at 8:11 AM, Joris Van den Bossche <[hidden email]> wrote:
> >
> > Hi all,
> >
> > On the CI of PyGEOS we have a build testing against GEOS master, and somewhere in the last 4 days, a lot of the STRtree tests started failing (see eg https://github.com/pygeos/pygeos/runs/1465460418#step:9:86). Looking at the commits of the last days, this might be related to the SimpleSTRtree work?
> >
> > A small (python) example of a tree consisting of a single point, which no longer is returned when querying the tree with a big polygon that certainly contains the point:
> >
> > Using released version of GEOS:
> >
> > >>> import pygeos
> > >>> pygeos.geos_version
> > (3, 8, 1)
> > >>> point = pygeos.Geometry("POINT (2 3)")
> > >>> tree = pygeos.STRtree([point])
> > >>> tree.query(pygeos.box(0, 0, 10, 10))
> > array([0])
> >
> > This is correctly returning the index of the single point. But when running with the latest GEOS master, the query doesn't find any point of the tree:
> >
> > >>> import pygeos
> > >>> pygeos.geos_version
> > (3, 9, 0)
> > >>> point = pygeos.Geometry("POINT (2 3)")
> > >>> tree = pygeos.STRtree([point])
> > >>> tree.query(pygeos.box(0, 0, 10, 10))
> > array([], dtype=int64)
> >
> > Are there changes expected in how the STRtree C API functions or required changes in user code? Or maybe we are using it in some incorrect/unexpected way? (code is at https://github.com/pygeos/pygeos/blob/master/src/strtree.c)
>
> There are changes, I don't think you're mis-using anything. I swapped the CAPI to use the SimpleSTRtree, figuring it would be good to share the performance win with downstream. However, I can swap it back to the original STRtree if this remains a problem.
>
> One thing I noticed when trying to construct GEOS envelopes directly was that annoyingly they were xmin xmax, ymin ymax, but I doubt that would be a problem in your pre-existing working test.
>
> I just reconstructed your test in the GEOS CAPI suite, and it works as one would expect. (Namely, it finds the one point.) So I'm not sure why your test is getting different results.
>
>
> // querying tree with box
> template<>
> template<>
> void object::test<8>
> ()
> {
>     GEOSSTRtree* tree = GEOSSTRtree_create(10);
>     GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
>     GEOSSTRtree_insert(tree, g, g);
>     GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>
>     typedef std::vector<GEOSGeometry*> GList;
>     GList geoms;
>     ensure_equals(geoms.size(), 0);
>     GEOSSTRtree_query(
>         tree,
>         q,
>         [](void* item, void* userdata) {
>             GList* geoms = (GList*)userdata;
>             geoms->push_back((GEOSGeometry*)item);
>         },
>         &geoms);
>
>     ensure_equals(geoms.size(), 1);
>     const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
>
>     double x = -1;
>     double y = -1;
>     GEOSCoordSeq_getXY(seq,  0, &x, &y);
>     ensure_equals(x, 2.0);
>     ensure_equals(y, 3.0);
>
>     GEOSGeom_destroy(q);
>     GEOSGeom_destroy(g);
>     GEOSSTRtree_destroy(tree);
> }
>
>
>
>
>
> >
> > Best,
> > Joris
> >
> >
> > On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <[hidden email]> wrote:
> > Hey all, just truing up what's underway and nearly there...
> >
> > - Am I right that Z coordinates are nearly done? What's the status there?
> >
> > I've been trying to address some performance issues, with some success and some ... other things.
> >
> > The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.
> >
> > While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.
> >
> > I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). https://github.com/pramsey/geos/tree/monotone-chain-builder
> >
> > I've put that work to the side for now.
> >
> > All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS.  It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.
> >
> > I think we're close, looking forward to release :)
> >
> > P
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Joris Van den Bossche

On Sat, 28 Nov 2020 at 21:53, Paul Ramsey <[hidden email]> wrote:


> On Nov 28, 2020, at 12:44 PM, Joris Van den Bossche <[hidden email]> wrote:
>
> Thanks for trying to reproduce it in C/C++. One obvious difference that I can spot is that we use an integer for the "item" that gets inserted, and not the geometry itself, but I wouldn't expect that to influence the result.
> Although, trying to update your test case to do that, the test fails. But that might also be an issue on my side due to my limited C++ experience (it already fails on the "geoms.size()" check):

Nope still not seeing it... one small mistake in your query

Also not if you try my original code *with* the mistake?
Because your version indeed passes for me as well, but I *think* the version I wrote resembles more closely the PyGEOS code (so it might be an issue in our C code on how we use the tree).
 
, trying to cast the int to a void, instead of passing in a the pointer to the address, here's one that works. Unfortunately that leaves us no closer to knowing why the SimpleSTRtree is unhappy in the python context. I fear I may just have to revert the CAPI to the old tree.


// querying tree with box
template<>
template<>
void object::test<9>
()
{
    GEOSSTRtree* tree = GEOSSTRtree_create(10);

    GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
    int payload = 876;
    GEOSSTRtree_insert(tree, g, &payload);

    GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");

    typedef std::vector<int*> IList;
    IList items;
    ensure_equals(items.size(), 0);
    GEOSSTRtree_query(
        tree,
        q,
        [](void* item, void* userdata) {
            IList* items = (IList*)userdata;
            items->push_back((int*)item);
        },
        &items);

    ensure_equals(items.size(), 1);

    ensure_equals(*(items[0]), payload);

    GEOSGeom_destroy(q);
    GEOSGeom_destroy(g);
    GEOSSTRtree_destroy(tree);
}




>
> --- a/tests/unit/capi/GEOSSTRtreeTest.cpp
> +++ b/tests/unit/capi/GEOSSTRtreeTest.cpp
> @@ -268,10 +268,11 @@ void object::test<8>
>  {
>      GEOSSTRtree* tree = GEOSSTRtree_create(10);
>      GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
> -    GEOSSTRtree_insert(tree, g, g);
> +    int idx = 0;
> +    GEOSSTRtree_insert(tree, g, (void*)idx);
>      GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");

> -    typedef std::vector<GEOSGeometry*> GList;
> +    typedef std::vector<int> GList;
>      GList geoms;
>      ensure_equals(geoms.size(), 0);
>      GEOSSTRtree_query(
> @@ -279,23 +280,16 @@ void object::test<8>
>          q,
>          [](void* item, void* userdata) {
>              GList* geoms = (GList*)userdata;
> -            geoms->push_back((GEOSGeometry*)item);
> +            geoms->push_back(*((int *)item));
>          },
>          &geoms);

>      ensure_equals(geoms.size(), 1);
> -    const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
> -
> -    double x = -1;
> -    double y = -1;
> -    GEOSCoordSeq_getXY(seq,  0, &x, &y);
> -    ensure_equals(x, 2.0);
> -    ensure_equals(y, 3.0);
> +    ensure_equals(geoms.at(0), 0);

>
> On Sat, 28 Nov 2020 at 20:55, Paul Ramsey <[hidden email]> wrote:
>
>
> > On Nov 28, 2020, at 8:11 AM, Joris Van den Bossche <[hidden email]> wrote:
> >
> > Hi all,
> >
> > On the CI of PyGEOS we have a build testing against GEOS master, and somewhere in the last 4 days, a lot of the STRtree tests started failing (see eg https://github.com/pygeos/pygeos/runs/1465460418#step:9:86). Looking at the commits of the last days, this might be related to the SimpleSTRtree work?
> >
> > A small (python) example of a tree consisting of a single point, which no longer is returned when querying the tree with a big polygon that certainly contains the point:
> >
> > Using released version of GEOS:
> >
> > >>> import pygeos
> > >>> pygeos.geos_version
> > (3, 8, 1)
> > >>> point = pygeos.Geometry("POINT (2 3)")
> > >>> tree = pygeos.STRtree([point])
> > >>> tree.query(pygeos.box(0, 0, 10, 10))
> > array([0])
> >
> > This is correctly returning the index of the single point. But when running with the latest GEOS master, the query doesn't find any point of the tree:
> >
> > >>> import pygeos
> > >>> pygeos.geos_version
> > (3, 9, 0)
> > >>> point = pygeos.Geometry("POINT (2 3)")
> > >>> tree = pygeos.STRtree([point])
> > >>> tree.query(pygeos.box(0, 0, 10, 10))
> > array([], dtype=int64)
> >
> > Are there changes expected in how the STRtree C API functions or required changes in user code? Or maybe we are using it in some incorrect/unexpected way? (code is at https://github.com/pygeos/pygeos/blob/master/src/strtree.c)
>
> There are changes, I don't think you're mis-using anything. I swapped the CAPI to use the SimpleSTRtree, figuring it would be good to share the performance win with downstream. However, I can swap it back to the original STRtree if this remains a problem.
>
> One thing I noticed when trying to construct GEOS envelopes directly was that annoyingly they were xmin xmax, ymin ymax, but I doubt that would be a problem in your pre-existing working test.
>
> I just reconstructed your test in the GEOS CAPI suite, and it works as one would expect. (Namely, it finds the one point.) So I'm not sure why your test is getting different results.
>
>
> // querying tree with box
> template<>
> template<>
> void object::test<8>
> ()
> {
>     GEOSSTRtree* tree = GEOSSTRtree_create(10);
>     GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
>     GEOSSTRtree_insert(tree, g, g);
>     GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>
>     typedef std::vector<GEOSGeometry*> GList;
>     GList geoms;
>     ensure_equals(geoms.size(), 0);
>     GEOSSTRtree_query(
>         tree,
>         q,
>         [](void* item, void* userdata) {
>             GList* geoms = (GList*)userdata;
>             geoms->push_back((GEOSGeometry*)item);
>         },
>         &geoms);
>
>     ensure_equals(geoms.size(), 1);
>     const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
>
>     double x = -1;
>     double y = -1;
>     GEOSCoordSeq_getXY(seq,  0, &x, &y);
>     ensure_equals(x, 2.0);
>     ensure_equals(y, 3.0);
>
>     GEOSGeom_destroy(q);
>     GEOSGeom_destroy(g);
>     GEOSSTRtree_destroy(tree);
> }
>
>
>
>
>
> >
> > Best,
> > Joris
> >
> >
> > On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <[hidden email]> wrote:
> > Hey all, just truing up what's underway and nearly there...
> >
> > - Am I right that Z coordinates are nearly done? What's the status there?
> >
> > I've been trying to address some performance issues, with some success and some ... other things.
> >
> > The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.
> >
> > While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.
> >
> > I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). https://github.com/pramsey/geos/tree/monotone-chain-builder
> >
> > I've put that work to the side for now.
> >
> > All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS.  It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.
> >
> > I think we're close, looking forward to release :)
> >
> > P
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Paul Ramsey


> On Nov 28, 2020, at 1:05 PM, Joris Van den Bossche <[hidden email]> wrote:
>
>
> On Sat, 28 Nov 2020 at 21:53, Paul Ramsey <[hidden email]> wrote:
>
>
> > On Nov 28, 2020, at 12:44 PM, Joris Van den Bossche <[hidden email]> wrote:
> >
> > Thanks for trying to reproduce it in C/C++. One obvious difference that I can spot is that we use an integer for the "item" that gets inserted, and not the geometry itself, but I wouldn't expect that to influence the result.
> > Although, trying to update your test case to do that, the test fails. But that might also be an issue on my side due to my limited C++ experience (it already fails on the "geoms.size()" check):
>
> Nope still not seeing it... one small mistake in your query
>
> Also not if you try my original code *with* the mistake?

Well, with the mistake the code is saying "here's a null pointer" (since that's what casting 0 to a void* will get you) index this. I'll see! It shouldn't really matter from an index point-of-view, it should still index it and return a null pointer out the back end.

> Because your version indeed passes for me as well, but I *think* the version I wrote resembles more closely the PyGEOS code (so it might be an issue in our C code on how we use the tree).
>  
> , trying to cast the int to a void, instead of passing in a the pointer to the address, here's one that works. Unfortunately that leaves us no closer to knowing why the SimpleSTRtree is unhappy in the python context. I fear I may just have to revert the CAPI to the old tree.
>
>
> // querying tree with box
> template<>
> template<>
> void object::test<9>
> ()
> {
>     GEOSSTRtree* tree = GEOSSTRtree_create(10);
>
>     GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
>     int payload = 876;
>     GEOSSTRtree_insert(tree, g, &payload);
>
>     GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>
>     typedef std::vector<int*> IList;
>     IList items;
>     ensure_equals(items.size(), 0);
>     GEOSSTRtree_query(
>         tree,
>         q,
>         [](void* item, void* userdata) {
>             IList* items = (IList*)userdata;
>             items->push_back((int*)item);
>         },
>         &items);
>
>     ensure_equals(items.size(), 1);
>
>     ensure_equals(*(items[0]), payload);
>
>     GEOSGeom_destroy(q);
>     GEOSGeom_destroy(g);
>     GEOSSTRtree_destroy(tree);
> }
>
>
>
>
> >
> > --- a/tests/unit/capi/GEOSSTRtreeTest.cpp
> > +++ b/tests/unit/capi/GEOSSTRtreeTest.cpp
> > @@ -268,10 +268,11 @@ void object::test<8>
> >  {
> >      GEOSSTRtree* tree = GEOSSTRtree_create(10);
> >      GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
> > -    GEOSSTRtree_insert(tree, g, g);
> > +    int idx = 0;
> > +    GEOSSTRtree_insert(tree, g, (void*)idx);
> >      GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
> >  
> > -    typedef std::vector<GEOSGeometry*> GList;
> > +    typedef std::vector<int> GList;
> >      GList geoms;
> >      ensure_equals(geoms.size(), 0);
> >      GEOSSTRtree_query(
> > @@ -279,23 +280,16 @@ void object::test<8>
> >          q,
> >          [](void* item, void* userdata) {
> >              GList* geoms = (GList*)userdata;
> > -            geoms->push_back((GEOSGeometry*)item);
> > +            geoms->push_back(*((int *)item));
> >          },
> >          &geoms);
> >  
> >      ensure_equals(geoms.size(), 1);
> > -    const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
> > -
> > -    double x = -1;
> > -    double y = -1;
> > -    GEOSCoordSeq_getXY(seq,  0, &x, &y);
> > -    ensure_equals(x, 2.0);
> > -    ensure_equals(y, 3.0);
> > +    ensure_equals(geoms.at(0), 0);
> >  
> >
> > On Sat, 28 Nov 2020 at 20:55, Paul Ramsey <[hidden email]> wrote:
> >
> >
> > > On Nov 28, 2020, at 8:11 AM, Joris Van den Bossche <[hidden email]> wrote:
> > >
> > > Hi all,
> > >
> > > On the CI of PyGEOS we have a build testing against GEOS master, and somewhere in the last 4 days, a lot of the STRtree tests started failing (see eg https://github.com/pygeos/pygeos/runs/1465460418#step:9:86). Looking at the commits of the last days, this might be related to the SimpleSTRtree work?
> > >
> > > A small (python) example of a tree consisting of a single point, which no longer is returned when querying the tree with a big polygon that certainly contains the point:
> > >
> > > Using released version of GEOS:
> > >
> > > >>> import pygeos
> > > >>> pygeos.geos_version
> > > (3, 8, 1)
> > > >>> point = pygeos.Geometry("POINT (2 3)")
> > > >>> tree = pygeos.STRtree([point])
> > > >>> tree.query(pygeos.box(0, 0, 10, 10))
> > > array([0])
> > >
> > > This is correctly returning the index of the single point. But when running with the latest GEOS master, the query doesn't find any point of the tree:
> > >
> > > >>> import pygeos
> > > >>> pygeos.geos_version
> > > (3, 9, 0)
> > > >>> point = pygeos.Geometry("POINT (2 3)")
> > > >>> tree = pygeos.STRtree([point])
> > > >>> tree.query(pygeos.box(0, 0, 10, 10))
> > > array([], dtype=int64)
> > >
> > > Are there changes expected in how the STRtree C API functions or required changes in user code? Or maybe we are using it in some incorrect/unexpected way? (code is at https://github.com/pygeos/pygeos/blob/master/src/strtree.c)
> >
> > There are changes, I don't think you're mis-using anything. I swapped the CAPI to use the SimpleSTRtree, figuring it would be good to share the performance win with downstream. However, I can swap it back to the original STRtree if this remains a problem.
> >
> > One thing I noticed when trying to construct GEOS envelopes directly was that annoyingly they were xmin xmax, ymin ymax, but I doubt that would be a problem in your pre-existing working test.
> >
> > I just reconstructed your test in the GEOS CAPI suite, and it works as one would expect. (Namely, it finds the one point.) So I'm not sure why your test is getting different results.
> >
> >
> > // querying tree with box
> > template<>
> > template<>
> > void object::test<8>
> > ()
> > {
> >     GEOSSTRtree* tree = GEOSSTRtree_create(10);
> >     GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
> >     GEOSSTRtree_insert(tree, g, g);
> >     GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
> >
> >     typedef std::vector<GEOSGeometry*> GList;
> >     GList geoms;
> >     ensure_equals(geoms.size(), 0);
> >     GEOSSTRtree_query(
> >         tree,
> >         q,
> >         [](void* item, void* userdata) {
> >             GList* geoms = (GList*)userdata;
> >             geoms->push_back((GEOSGeometry*)item);
> >         },
> >         &geoms);
> >
> >     ensure_equals(geoms.size(), 1);
> >     const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
> >
> >     double x = -1;
> >     double y = -1;
> >     GEOSCoordSeq_getXY(seq,  0, &x, &y);
> >     ensure_equals(x, 2.0);
> >     ensure_equals(y, 3.0);
> >
> >     GEOSGeom_destroy(q);
> >     GEOSGeom_destroy(g);
> >     GEOSSTRtree_destroy(tree);
> > }
> >
> >
> >
> >
> >
> > >
> > > Best,
> > > Joris
> > >
> > >
> > > On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <[hidden email]> wrote:
> > > Hey all, just truing up what's underway and nearly there...
> > >
> > > - Am I right that Z coordinates are nearly done? What's the status there?
> > >
> > > I've been trying to address some performance issues, with some success and some ... other things.
> > >
> > > The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.
> > >
> > > While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.
> > >
> > > I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). https://github.com/pramsey/geos/tree/monotone-chain-builder
> > >
> > > I've put that work to the side for now.
> > >
> > > All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS.  It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.
> > >
> > > I think we're close, looking forward to release :)
> > >
> > > P
> > > _______________________________________________
> > > geos-devel mailing list
> > > [hidden email]
> > > https://lists.osgeo.org/mailman/listinfo/geos-devel
> > > _______________________________________________
> > > geos-devel mailing list
> > > [hidden email]
> > > https://lists.osgeo.org/mailman/listinfo/geos-devel
> >
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
> > _______________________________________________
> > geos-devel mailing list
> > [hidden email]
> > https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Paul Ramsey


> On Nov 28, 2020, at 1:11 PM, Paul Ramsey <[hidden email]> wrote:
>
>
>
>> On Nov 28, 2020, at 1:05 PM, Joris Van den Bossche <[hidden email]> wrote:
>>
>>
>> On Sat, 28 Nov 2020 at 21:53, Paul Ramsey <[hidden email]> wrote:
>>
>>
>>> On Nov 28, 2020, at 12:44 PM, Joris Van den Bossche <[hidden email]> wrote:
>>>
>>> Thanks for trying to reproduce it in C/C++. One obvious difference that I can spot is that we use an integer for the "item" that gets inserted, and not the geometry itself, but I wouldn't expect that to influence the result.
>>> Although, trying to update your test case to do that, the test fails. But that might also be an issue on my side due to my limited C++ experience (it already fails on the "geoms.size()" check):
>>
>> Nope still not seeing it... one small mistake in your query
>>
>> Also not if you try my original code *with* the mistake?
>
> Well, with the mistake the code is saying "here's a null pointer" (since that's what casting 0 to a void* will get you) index this. I'll see! It shouldn't really matter from an index point-of-view, it should still index it and return a null pointer out the back end.

And indeed it does not work. So, something to examine... why can we not index with a null item?

P

>
>> Because your version indeed passes for me as well, but I *think* the version I wrote resembles more closely the PyGEOS code (so it might be an issue in our C code on how we use the tree).
>>
>> , trying to cast the int to a void, instead of passing in a the pointer to the address, here's one that works. Unfortunately that leaves us no closer to knowing why the SimpleSTRtree is unhappy in the python context. I fear I may just have to revert the CAPI to the old tree.
>>
>>
>> // querying tree with box
>> template<>
>> template<>
>> void object::test<9>
>> ()
>> {
>>    GEOSSTRtree* tree = GEOSSTRtree_create(10);
>>
>>    GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
>>    int payload = 876;
>>    GEOSSTRtree_insert(tree, g, &payload);
>>
>>    GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>>
>>    typedef std::vector<int*> IList;
>>    IList items;
>>    ensure_equals(items.size(), 0);
>>    GEOSSTRtree_query(
>>        tree,
>>        q,
>>        [](void* item, void* userdata) {
>>            IList* items = (IList*)userdata;
>>            items->push_back((int*)item);
>>        },
>>        &items);
>>
>>    ensure_equals(items.size(), 1);
>>
>>    ensure_equals(*(items[0]), payload);
>>
>>    GEOSGeom_destroy(q);
>>    GEOSGeom_destroy(g);
>>    GEOSSTRtree_destroy(tree);
>> }
>>
>>
>>
>>
>>>
>>> --- a/tests/unit/capi/GEOSSTRtreeTest.cpp
>>> +++ b/tests/unit/capi/GEOSSTRtreeTest.cpp
>>> @@ -268,10 +268,11 @@ void object::test<8>
>>> {
>>>     GEOSSTRtree* tree = GEOSSTRtree_create(10);
>>>     GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
>>> -    GEOSSTRtree_insert(tree, g, g);
>>> +    int idx = 0;
>>> +    GEOSSTRtree_insert(tree, g, (void*)idx);
>>>     GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>>>
>>> -    typedef std::vector<GEOSGeometry*> GList;
>>> +    typedef std::vector<int> GList;
>>>     GList geoms;
>>>     ensure_equals(geoms.size(), 0);
>>>     GEOSSTRtree_query(
>>> @@ -279,23 +280,16 @@ void object::test<8>
>>>         q,
>>>         [](void* item, void* userdata) {
>>>             GList* geoms = (GList*)userdata;
>>> -            geoms->push_back((GEOSGeometry*)item);
>>> +            geoms->push_back(*((int *)item));
>>>         },
>>>         &geoms);
>>>
>>>     ensure_equals(geoms.size(), 1);
>>> -    const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
>>> -
>>> -    double x = -1;
>>> -    double y = -1;
>>> -    GEOSCoordSeq_getXY(seq,  0, &x, &y);
>>> -    ensure_equals(x, 2.0);
>>> -    ensure_equals(y, 3.0);
>>> +    ensure_equals(geoms.at(0), 0);
>>>
>>>
>>> On Sat, 28 Nov 2020 at 20:55, Paul Ramsey <[hidden email]> wrote:
>>>
>>>
>>>> On Nov 28, 2020, at 8:11 AM, Joris Van den Bossche <[hidden email]> wrote:
>>>>
>>>> Hi all,
>>>>
>>>> On the CI of PyGEOS we have a build testing against GEOS master, and somewhere in the last 4 days, a lot of the STRtree tests started failing (see eg https://github.com/pygeos/pygeos/runs/1465460418#step:9:86). Looking at the commits of the last days, this might be related to the SimpleSTRtree work?
>>>>
>>>> A small (python) example of a tree consisting of a single point, which no longer is returned when querying the tree with a big polygon that certainly contains the point:
>>>>
>>>> Using released version of GEOS:
>>>>
>>>>>>> import pygeos
>>>>>>> pygeos.geos_version
>>>> (3, 8, 1)
>>>>>>> point = pygeos.Geometry("POINT (2 3)")
>>>>>>> tree = pygeos.STRtree([point])
>>>>>>> tree.query(pygeos.box(0, 0, 10, 10))
>>>> array([0])
>>>>
>>>> This is correctly returning the index of the single point. But when running with the latest GEOS master, the query doesn't find any point of the tree:
>>>>
>>>>>>> import pygeos
>>>>>>> pygeos.geos_version
>>>> (3, 9, 0)
>>>>>>> point = pygeos.Geometry("POINT (2 3)")
>>>>>>> tree = pygeos.STRtree([point])
>>>>>>> tree.query(pygeos.box(0, 0, 10, 10))
>>>> array([], dtype=int64)
>>>>
>>>> Are there changes expected in how the STRtree C API functions or required changes in user code? Or maybe we are using it in some incorrect/unexpected way? (code is at https://github.com/pygeos/pygeos/blob/master/src/strtree.c)
>>>
>>> There are changes, I don't think you're mis-using anything. I swapped the CAPI to use the SimpleSTRtree, figuring it would be good to share the performance win with downstream. However, I can swap it back to the original STRtree if this remains a problem.
>>>
>>> One thing I noticed when trying to construct GEOS envelopes directly was that annoyingly they were xmin xmax, ymin ymax, but I doubt that would be a problem in your pre-existing working test.
>>>
>>> I just reconstructed your test in the GEOS CAPI suite, and it works as one would expect. (Namely, it finds the one point.) So I'm not sure why your test is getting different results.
>>>
>>>
>>> // querying tree with box
>>> template<>
>>> template<>
>>> void object::test<8>
>>> ()
>>> {
>>>    GEOSSTRtree* tree = GEOSSTRtree_create(10);
>>>    GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
>>>    GEOSSTRtree_insert(tree, g, g);
>>>    GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>>>
>>>    typedef std::vector<GEOSGeometry*> GList;
>>>    GList geoms;
>>>    ensure_equals(geoms.size(), 0);
>>>    GEOSSTRtree_query(
>>>        tree,
>>>        q,
>>>        [](void* item, void* userdata) {
>>>            GList* geoms = (GList*)userdata;
>>>            geoms->push_back((GEOSGeometry*)item);
>>>        },
>>>        &geoms);
>>>
>>>    ensure_equals(geoms.size(), 1);
>>>    const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
>>>
>>>    double x = -1;
>>>    double y = -1;
>>>    GEOSCoordSeq_getXY(seq,  0, &x, &y);
>>>    ensure_equals(x, 2.0);
>>>    ensure_equals(y, 3.0);
>>>
>>>    GEOSGeom_destroy(q);
>>>    GEOSGeom_destroy(g);
>>>    GEOSSTRtree_destroy(tree);
>>> }
>>>
>>>
>>>
>>>
>>>
>>>>
>>>> Best,
>>>> Joris
>>>>
>>>>
>>>> On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <[hidden email]> wrote:
>>>> Hey all, just truing up what's underway and nearly there...
>>>>
>>>> - Am I right that Z coordinates are nearly done? What's the status there?
>>>>
>>>> I've been trying to address some performance issues, with some success and some ... other things.
>>>>
>>>> The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.
>>>>
>>>> While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.
>>>>
>>>> I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). https://github.com/pramsey/geos/tree/monotone-chain-builder
>>>>
>>>> I've put that work to the side for now.
>>>>
>>>> All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS. It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.
>>>>
>>>> I think we're close, looking forward to release :)
>>>>
>>>> P
>>>> _______________________________________________
>>>> geos-devel mailing list
>>>> [hidden email]
>>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>>> _______________________________________________
>>>> geos-devel mailing list
>>>> [hidden email]
>>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>>
>>> _______________________________________________
>>> geos-devel mailing list
>>> [hidden email]
>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>> _______________________________________________
>>> geos-devel mailing list
>>> [hidden email]
>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>
>> _______________________________________________
>> geos-devel mailing list
>> [hidden email]
>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>> _______________________________________________
>> geos-devel mailing list
>> [hidden email]
>> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Update to 3.9?

Paul Ramsey


> On Nov 28, 2020, at 1:13 PM, Paul Ramsey <[hidden email]> wrote:
>
>
>
>> On Nov 28, 2020, at 1:11 PM, Paul Ramsey <[hidden email]> wrote:
>>
>>
>>
>>> On Nov 28, 2020, at 1:05 PM, Joris Van den Bossche <[hidden email]> wrote:
>>>
>>>
>>> On Sat, 28 Nov 2020 at 21:53, Paul Ramsey <[hidden email]> wrote:
>>>
>>>
>>>> On Nov 28, 2020, at 12:44 PM, Joris Van den Bossche <[hidden email]> wrote:
>>>>
>>>> Thanks for trying to reproduce it in C/C++. One obvious difference that I can spot is that we use an integer for the "item" that gets inserted, and not the geometry itself, but I wouldn't expect that to influence the result.
>>>> Although, trying to update your test case to do that, the test fails. But that might also be an issue on my side due to my limited C++ experience (it already fails on the "geoms.size()" check):
>>>
>>> Nope still not seeing it... one small mistake in your query
>>>
>>> Also not if you try my original code *with* the mistake?
>>
>> Well, with the mistake the code is saying "here's a null pointer" (since that's what casting 0 to a void* will get you) index this. I'll see! It shouldn't really matter from an index point-of-view, it should still index it and return a null pointer out the back end.
>
> And indeed it does not work. So, something to examine... why can we not index with a null item?

Because I was using a non-null item pointer as a cue that the node was a leaf node, so it wasn't picking up null items as leaves.
So, I've pushed that fix, does that change your test suite all that much?

P


>
> P
>
>>
>>> Because your version indeed passes for me as well, but I *think* the version I wrote resembles more closely the PyGEOS code (so it might be an issue in our C code on how we use the tree).
>>>
>>> , trying to cast the int to a void, instead of passing in a the pointer to the address, here's one that works. Unfortunately that leaves us no closer to knowing why the SimpleSTRtree is unhappy in the python context. I fear I may just have to revert the CAPI to the old tree.
>>>
>>>
>>> // querying tree with box
>>> template<>
>>> template<>
>>> void object::test<9>
>>> ()
>>> {
>>>   GEOSSTRtree* tree = GEOSSTRtree_create(10);
>>>
>>>   GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
>>>   int payload = 876;
>>>   GEOSSTRtree_insert(tree, g, &payload);
>>>
>>>   GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>>>
>>>   typedef std::vector<int*> IList;
>>>   IList items;
>>>   ensure_equals(items.size(), 0);
>>>   GEOSSTRtree_query(
>>>       tree,
>>>       q,
>>>       [](void* item, void* userdata) {
>>>           IList* items = (IList*)userdata;
>>>           items->push_back((int*)item);
>>>       },
>>>       &items);
>>>
>>>   ensure_equals(items.size(), 1);
>>>
>>>   ensure_equals(*(items[0]), payload);
>>>
>>>   GEOSGeom_destroy(q);
>>>   GEOSGeom_destroy(g);
>>>   GEOSSTRtree_destroy(tree);
>>> }
>>>
>>>
>>>
>>>
>>>>
>>>> --- a/tests/unit/capi/GEOSSTRtreeTest.cpp
>>>> +++ b/tests/unit/capi/GEOSSTRtreeTest.cpp
>>>> @@ -268,10 +268,11 @@ void object::test<8>
>>>> {
>>>>    GEOSSTRtree* tree = GEOSSTRtree_create(10);
>>>>    GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
>>>> -    GEOSSTRtree_insert(tree, g, g);
>>>> +    int idx = 0;
>>>> +    GEOSSTRtree_insert(tree, g, (void*)idx);
>>>>    GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>>>>
>>>> -    typedef std::vector<GEOSGeometry*> GList;
>>>> +    typedef std::vector<int> GList;
>>>>    GList geoms;
>>>>    ensure_equals(geoms.size(), 0);
>>>>    GEOSSTRtree_query(
>>>> @@ -279,23 +280,16 @@ void object::test<8>
>>>>        q,
>>>>        [](void* item, void* userdata) {
>>>>            GList* geoms = (GList*)userdata;
>>>> -            geoms->push_back((GEOSGeometry*)item);
>>>> +            geoms->push_back(*((int *)item));
>>>>        },
>>>>        &geoms);
>>>>
>>>>    ensure_equals(geoms.size(), 1);
>>>> -    const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
>>>> -
>>>> -    double x = -1;
>>>> -    double y = -1;
>>>> -    GEOSCoordSeq_getXY(seq,  0, &x, &y);
>>>> -    ensure_equals(x, 2.0);
>>>> -    ensure_equals(y, 3.0);
>>>> +    ensure_equals(geoms.at(0), 0);
>>>>
>>>>
>>>> On Sat, 28 Nov 2020 at 20:55, Paul Ramsey <[hidden email]> wrote:
>>>>
>>>>
>>>>> On Nov 28, 2020, at 8:11 AM, Joris Van den Bossche <[hidden email]> wrote:
>>>>>
>>>>> Hi all,
>>>>>
>>>>> On the CI of PyGEOS we have a build testing against GEOS master, and somewhere in the last 4 days, a lot of the STRtree tests started failing (see eg https://github.com/pygeos/pygeos/runs/1465460418#step:9:86). Looking at the commits of the last days, this might be related to the SimpleSTRtree work?
>>>>>
>>>>> A small (python) example of a tree consisting of a single point, which no longer is returned when querying the tree with a big polygon that certainly contains the point:
>>>>>
>>>>> Using released version of GEOS:
>>>>>
>>>>>>>> import pygeos
>>>>>>>> pygeos.geos_version
>>>>> (3, 8, 1)
>>>>>>>> point = pygeos.Geometry("POINT (2 3)")
>>>>>>>> tree = pygeos.STRtree([point])
>>>>>>>> tree.query(pygeos.box(0, 0, 10, 10))
>>>>> array([0])
>>>>>
>>>>> This is correctly returning the index of the single point. But when running with the latest GEOS master, the query doesn't find any point of the tree:
>>>>>
>>>>>>>> import pygeos
>>>>>>>> pygeos.geos_version
>>>>> (3, 9, 0)
>>>>>>>> point = pygeos.Geometry("POINT (2 3)")
>>>>>>>> tree = pygeos.STRtree([point])
>>>>>>>> tree.query(pygeos.box(0, 0, 10, 10))
>>>>> array([], dtype=int64)
>>>>>
>>>>> Are there changes expected in how the STRtree C API functions or required changes in user code? Or maybe we are using it in some incorrect/unexpected way? (code is at https://github.com/pygeos/pygeos/blob/master/src/strtree.c)
>>>>
>>>> There are changes, I don't think you're mis-using anything. I swapped the CAPI to use the SimpleSTRtree, figuring it would be good to share the performance win with downstream. However, I can swap it back to the original STRtree if this remains a problem.
>>>>
>>>> One thing I noticed when trying to construct GEOS envelopes directly was that annoyingly they were xmin xmax, ymin ymax, but I doubt that would be a problem in your pre-existing working test.
>>>>
>>>> I just reconstructed your test in the GEOS CAPI suite, and it works as one would expect. (Namely, it finds the one point.) So I'm not sure why your test is getting different results.
>>>>
>>>>
>>>> // querying tree with box
>>>> template<>
>>>> template<>
>>>> void object::test<8>
>>>> ()
>>>> {
>>>>   GEOSSTRtree* tree = GEOSSTRtree_create(10);
>>>>   GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
>>>>   GEOSSTRtree_insert(tree, g, g);
>>>>   GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
>>>>
>>>>   typedef std::vector<GEOSGeometry*> GList;
>>>>   GList geoms;
>>>>   ensure_equals(geoms.size(), 0);
>>>>   GEOSSTRtree_query(
>>>>       tree,
>>>>       q,
>>>>       [](void* item, void* userdata) {
>>>>           GList* geoms = (GList*)userdata;
>>>>           geoms->push_back((GEOSGeometry*)item);
>>>>       },
>>>>       &geoms);
>>>>
>>>>   ensure_equals(geoms.size(), 1);
>>>>   const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
>>>>
>>>>   double x = -1;
>>>>   double y = -1;
>>>>   GEOSCoordSeq_getXY(seq,  0, &x, &y);
>>>>   ensure_equals(x, 2.0);
>>>>   ensure_equals(y, 3.0);
>>>>
>>>>   GEOSGeom_destroy(q);
>>>>   GEOSGeom_destroy(g);
>>>>   GEOSSTRtree_destroy(tree);
>>>> }
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>>
>>>>> Best,
>>>>> Joris
>>>>>
>>>>>
>>>>> On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <[hidden email]> wrote:
>>>>> Hey all, just truing up what's underway and nearly there...
>>>>>
>>>>> - Am I right that Z coordinates are nearly done? What's the status there?
>>>>>
>>>>> I've been trying to address some performance issues, with some success and some ... other things.
>>>>>
>>>>> The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.
>>>>>
>>>>> While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.
>>>>>
>>>>> I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). https://github.com/pramsey/geos/tree/monotone-chain-builder
>>>>>
>>>>> I've put that work to the side for now.
>>>>>
>>>>> All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS. It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.
>>>>>
>>>>> I think we're close, looking forward to release :)
>>>>>
>>>>> P
>>>>> _______________________________________________
>>>>> geos-devel mailing list
>>>>> [hidden email]
>>>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>>>> _______________________________________________
>>>>> geos-devel mailing list
>>>>> [hidden email]
>>>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>>>
>>>> _______________________________________________
>>>> geos-devel mailing list
>>>> [hidden email]
>>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>>> _______________________________________________
>>>> geos-devel mailing list
>>>> [hidden email]
>>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>>
>>> _______________________________________________
>>> geos-devel mailing list
>>> [hidden email]
>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>> _______________________________________________
>>> geos-devel mailing list
>>> [hidden email]
>>> https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
12