[geos-devel] Benchmark between various geometry libraries

[Martin Davis]

Thanks for clarifying this, Hartmut.  This makes good sense to me.  In 
my (admittedly limited and dated) experience, the C/C++ heap allocator 
(good ol' malloc still, right?) is pretty slow.  From what you're saying 
stack allocation is substantially faster.

The kind of change you indicated should be fairly simple to make in the 
GEOS codebase.

I'd be interested to see how widespread this actually is.  Many of the 
structures that JTS/GEOS creates during processing are shared across 
multiple methods and classes.  I suppose this doesn't preclude using 
stack-based allocation, but mightn't it require passing more references 
down into function calls?

Hartmut Kaiser wrote:
>> Further to this, I did look at the GGL source to see if there were some
>> obvious algorithmic ideas that could be used in JTS/GEOS.  But I got
>> lost in all the template code...  8^(
>>
>> I am curious to know how much of the speed improvement is due to more
>> efficient compilation due to templating, VS pure algorithm design.  The
>> latter can inform other libraries - the former, not so much.
>>     
>
> I strongly believe the performance gain does not come from templates per se. As already said, but that's only an educated guess - I did not measure, GEOS loses a lot performance from allocating everything from the heap. These allocations/deallocations are done even in cases where no allocation is necessary. From the top of my head I remember GEOS often using constructs like:
>
>     {
>         vector<bla>* v = new vector<bla>();
>         // use v
>         delete v;
>     }
>
> instead of a simpler and faster (and, BTW, additionally exception safe):
>
>     {
>         vector<bla> v;
>         // use v
>     }
>
> The GEOS code base is full of those...
>
> The template vs. non-template issues are much less significant, as the major differences result from GEOS using runtime polymorphism (virtual functions) vs. GGL using static polymorphism (templates). Surely this has an impact as virtual functions not only add some overhead to the function calls, but additionally act as an optimization barrier for the compiler (no inlining and no global optimization possible). But this alone shouldn't result in magnitudes of performance differences.
>
> Regards Hartmut
>
> -------------------
> Meet me at BoostCon
> http://boostcon.com
>
>   
>> Martin Davis wrote:
>>     
>>> Maxime van Noppen wrote:
>>>       
>>>> It's quite interesting to have some numbers though, as sometimes
>>>>         
>> they
>>     
>>>> can lead to significant performance boost (CascadedPolygonUnion is a
>>>> good example). It might be interesting to analyze why geos is 23x
>>>>         
>> slower
>>     
>>>> than other geometry libraries in some cases whereas it competes with
>>>> them elsewhere.
>>>>
>>>>
>>>>         
>>> Yes, definitely it's nice to have examples of how things can be
>>>       
>> improved.
>>     
>>> Personally I intend to stay well away from any C++ template hacking,
>>> though!
>>>
>>>       
>> --
>> Martin Davis
>> Senior Technical Architect
>> Refractions Research, Inc.
>> (250) 383-3022
>>
>> _______________________________________________
>> geos-devel mailing list
>> geos-devel at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/geos-devel
>>     
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>
>   

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022