[geos-devel] Updated timings/profiling.
Ferdinando Villa
ferdinando.villa at uvm.edu
Tue Feb 22 13:32:45 EST 2005
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 :)
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
More information about the geos-devel
mailing list