[geos-devel] Updated timings/profiling.
strk at refractions.net
strk at refractions.net
Tue Feb 22 17:36:13 EST 2005
On Tue, Feb 22, 2005 at 01:32:45PM -0500, Ferdinando Villa wrote:
> Maybe the "easygeos" layer could be the place to integrate smart
> pointers, too? So we get to pass shapes and managers with value
> semantics and forget about it all :)
It could be a way to integrate smart pointers internally w/out
changing the interfaces (both binary and source-level).
--strk;
>
> ferdinando
>
> -----Original Message-----
> From: geos-devel-bounces at geos.refractions.net
> [mailto:geos-devel-bounces at geos.refractions.net] On Behalf Of
> strk at refractions.net
> Sent: Tuesday, February 22, 2005 1:32 PM
> To: geos-devel at geos.refractions.net
> Subject: Re: [geos-devel] Updated timings/profiling.
>
>
> On Tue, Feb 15, 2005 at 06:39:50PM +0100, strk at refractions.net wrote:
> > On Tue, Feb 01, 2005 at 04:55:46PM +0100, strk at refractions.net wrote:
> > > On Fri, Jan 28, 2005 at 01:19:55PM +0100, strk at refractions.net
> > > wrote:
> > > > Some time ago I've been researching about GEOS performance
> > > > problems as related to JTS. Attached is a shapefile and an .xml
> > > > test you can use to compare the two.
> > > >
> > > > JTS does not support buffers tests, so you'll need to use another
> > > > method for that. I used JUMP, which reports computation time.
> > > >
> > > > Well. The operation is a buffer(polygon, 2000).
> > > >
> > > > JTS: 18 seconds
> > > > GEOS: 574 seconds (9 minutes, 34 secs)
> > >
> > > I've found out I was using non-optimized builds (-O0).
> > > With -O2 GEOS timing reduces to 63 seconds.
> >
> > Timing is now 43 seconds (from 63). We are getting closer ...
>
> We hit 33 seconds.
> Some memory allocations reduction and some inlining.
>
> I'm sure we can get good performance improvement by providing
> a complete STRtree::query() functoin. Current one invokes
> the AbstractSTRtree:: version, which makes static binding
> impossible.
>
> Another thing to look at is the way SegmentNodeList manages
> SegmentNodes. Currently it always builds a new SegmentNode for every
> addition request, then checks to see if a SegmentNode is already present
> in the node sets (see geos::yComparator) and eventually deletes the
> newly created one.. We could use a small key object instead, storing
> only the values used in
> comparison...
>
> Finally I'd keep removing heap allocations from mass-allocated objects
> and add reserve() functions to some array-based ones.
>
> Since all this changes break ABI it would definitely be useful a
> compatibility layer with Abstract Data Types. Something like:
>
> libeasygeos.so/easygeos.h
> typedef struct EasyGeometry_t EasyGeometry;
> bool intersects(EasyGeometry *a, EasyGeoemtry *b);
> bool union(EasyGeometry *a, EasyGeoemtry *b);
> ...
>
> What do you think ?
>
> --strk(new head of Flat profile follows);
>
> Flat profile:
>
> Each sample counts as 0.01 seconds.
> % cumulative self self total
> time seconds seconds calls s/call s/call name
> 29.89 78.64 78.64 232042887 0.00 0.00
> geos::STRtree::STRIntersectsOp::intersects(void const*, void const*)
> 20.39 132.27 53.63 451654 0.00 0.00
> geos::AbstractSTRtree::query(void const*, geos::AbstractNode*,
> std::vector<void*, std::allocator<void*> >*)
> 4.63 144.46 12.19 194036421 0.00 0.00
> geos::ItemBoundable::getBounds()
> 4.47 156.22 11.76 14852093 0.00 0.00
> geos::yComparator(geos::Boundable*, geos::Boundable*)
> 4.28 167.47 11.25 19520052 0.00 0.00
> geos::Edge::equals(geos::Edge*)
> 2.61 174.33 6.86 2288324 0.00 0.00
> geos::RobustLineIntersector::computeIntersect(geos::Coordinate const&,
> geos::Coordinate const&, geos::Coordinate const&, geos::Coordinate
> const&)
> 2.55 181.05 6.72 68212774 0.00 0.00
> geos::AbstractNode::getBounds()
>
> >
> > I've done other optimizations of the code.
> > The bigger one is probably inlining of most Envelope methods, but I've
>
> > also added some preallocations for standard containers (mostly in
> > indexSTRtree).
> >
> > Our bottleneck now is STRtree::STRIntersectsOp::intersects(), with
> > 15.35% of time spent. This function basically calls the inlined
> > Envelope::intersects, so not much to optimize there, and no inlining
> > possible.
> >
> > I wonder if checking for intersection 45281976 times is really correct
>
> > or our indexes are broken...
> >
> > First line of flat profile:
> >
> > Flat profile:
> >
> > Each sample counts as 0.01 seconds.
> > % cumulative self self total
> > time seconds seconds calls s/call s/call name
> > 15.35 14.27 14.27 45281976 0.00 0.00
> geos::STRtree::STRIntersectsOp::intersects(void const*, void const*)
> > 7.73 21.46 7.19
> geos::AbstractSTRtree::query(void const*)
> > 4.28 25.44 3.98 28602 0.00 0.00
> geos::RobustLineIntersector::computeIntersect(geos::Coordinate const&,
> geos::Coordinate const&, geos::Coordinate const&, geos::Coordinate
> const&)
> > 3.72 28.90 3.46 40923120 0.00 0.00
> geos::DefaultCoordinateSequence::add(geos::Coordinate const&)
> >
> > --strk;
> >
> >
> > >
> > > Still worth profiling, but JTS/GEOS are much closer.
> > >
> > > Most of the time is spent in MCQuadtreeNoder::intersectChains().
> > >
> > > --strk;
> > >
> > > >
> > > > GEOS computation keeps the CPU pretty busy (98.2-99.8%) and takes
> > > > up to about 170 MB of ram
> > > >
> > > > JTS seems to use 3 threads, the bigger using at most 80%
> > > > of CPU, but most of the time far below that point.
> > > > JUMP reports 104MB committed, but I'm not sure about the meaning.
> > > >
> > > > For GEOS, valgrind reports (with buffer 500):
> > > > malloc/free: 2982697 allocs, 2982697 frees, 924407212 bytes
> > > > allocated.
> > > >
> > > > How much do you think this wild allocation negatively influence
> > > > the poor performance of GEOS ?
> > > >
> > > > --strk;
> > > > _______________________________________________
> > > > geos-devel mailing list
> > > > geos-devel at geos.refractions.net
> > > > http://geos.refractions.net/mailman/listinfo/geos-devel
> > > _______________________________________________
> > > geos-devel mailing list
> > > geos-devel at geos.refractions.net
> > > http://geos.refractions.net/mailman/listinfo/geos-devel
> > _______________________________________________
> > geos-devel mailing list
> > geos-devel at geos.refractions.net
> > http://geos.refractions.net/mailman/listinfo/geos-devel
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
More information about the geos-devel
mailing list