[geos-devel] Updated timings/profiling.

strk at refractions.net strk at refractions.net
Tue Feb 22 13:32:27 EST 2005


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



More information about the geos-devel mailing list