← Back to team overview

kicad-developers team mailing list archive

Re: RTree implementation


On 10/22/2018 3:38 AM, jp charras wrote:
> Le 22/10/2018 à 05:05, Seth Hillbrand a écrit :
>> Am Mo., 6. Aug. 2018 um 15:49 Uhr schrieb Seth Hillbrand
>> <seth@xxxxxxxxxxxxx <mailto:seth@xxxxxxxxxxxxx>>:
>>     Am Mo., 6. Aug. 2018 um 14:18 Uhr schrieb Tomasz Wlostowski
>>     <tomasz.wlostowski@xxxxxxx <mailto:tomasz.wlostowski@xxxxxxx>>:
>>         On 06/08/18 18:35, Seth Hillbrand wrote:
>>         >
>>         > There's another 32-bit RTree issue that is showing its face
>>         > (https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=905221). 
>>         The last
>>         > one (https://bugs.launchpad.net/kicad/+bug/1774316), we hacked
>>         around
>>         > for v5 but as this seems to be a recurring theme, I'd like to
>>         address it
>>         > with some finality.
>>         >
>>         > We could maintain the RTree implementation ourselves with
>>         updates to
>>         > correct these errors.
>>         > Or, we could use the Boost-based implementation
>>         >
>>         (https://www.boost.org/doc/libs/1_67_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree.html).
>>         >
>>         > I have a basic framework for shifting to the Boost-based
>>         > implementation.  In tests, I don't see a speed difference in
>>         running. 
>>         > Compiling might be modestly slower.
>>         Hi Seth,
>>         I would be careful with anything related to geometry in Boost. Good
>>         things from Boost sooner or later end up in the standard C++ library
>>         (e.g. unordered). We had a lot of trouble in the past with
>>         crashes in
>>         boost::polygon that nobody could debug or even understand
>>         because of the
>>         vast complexity of Boost code. We struggled for few months to
>>         replace it
>>         with Clipper, since then, we've seen no crashes in polygon
>>         boolean ops.
>>         If the solution to fix the current R-tree to work on 32-bit
>>         platforms is
>>         to use doubles instead of floats, why not try it out? By changing to
>>         boost::geometry, we'll likely have to report bugs there. I'm
>>         also quite
>>         surprised this bug surfaced on one particular OS (Debian) 5
>>         years after
>>         this R-tree implementation had been introduced to pcbnew. Does
>>         anyone
>>         here know why it crashes on Debian and not on other 32-bit systems?
>>         Tom
>>     Hi Tom-
>>     You make good points here.  I'm happy to wait on the boost:geometry
>>     revision until we see if the double-fix addresses the issue.  I
>>     can't recreate the currently reported issue, so I'm not certain
>>     whether the double-fix addresses it as well as the original bug but
>>     it definitely makes sense to try it out.  
>>     There may or may not have been a second report of this bug under
>>     Fedora (see comment 19 and below
>>     at https://bugs.launchpad.net/kicad/+bug/1774316) that may or may
>>     not have been 32-bit.  I'm vague on the details as the original
>>     reporter did not follow up.
>>     In the meantime, I'll push the double-fix to 5.0.1 and 5.1.
>>     -Seth
>> Hi All-
>> Heads up that we have another 32-bit Debian bug [1] that looks like the
>> same type of issue as before.  I've rebased and pushed my test
>> replacement of the RTree to [2] in case anyone would like to test it
>> out.  Currently, it only replaces the connectivity RTree but if there
>> are no objections, I'll continue to update the other RTree uses as well.
>> Also, Tom I checked with the boost dev team and the person who is
>> responsible for boost::polygon (1 guy) is not involved with the
>> boost::geometry team.
>> -Seth
>> [1] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=911559
>> [2] https://code.launchpad.net/~sethh/kicad/+git/kicad/+ref/boost_polytri <https://code.launchpad.net/%7Esethh/kicad/+git/kicad/+ref/boost_polytri>
> Hi Seth,
> To be honest, I am not especially thrilled by a new boost dependency, as
> we had so many issues with boost and the incompatibilities between versions.
> Note (as Tomasz said) sources are not understandable, and updating boost
>  if a bug is found is not usually possible.
> Note also, due to the complexity of boost include files, we already had
> an issue with optimization level (-O1 worked, -O2 does not), depending
> on gcc compil version.
> It can be an explanation to the Debian 32 bits build issue.
> However I tested your branch:
> - on Linux (using boost 1.54) Kubuntu 14.04 LTE (still maintained).
>   no problem.
> - on msys2 (using boost 1.63): does not compile. See attached report.
>  I am guessing this is a boost version issue.

I tend to side with JP on this.  Our luck with boost has not been the
best over the years.  We seem to have an issue every few boost releases
with something getting broken so I would tread cautiously and require
lots of testing with many different boost versions back to 1.54 which is
our current minimum version.

Follow ups