date:20180515

[Kicad-developers] Some speed up patches

2018-05-15 Thread Seth Hillbrand

Hi Tomasz (and others if interested)-

I'm attaching some patches to the connectivity search.  I know you are
looking at moving some of this to a background thread (
https://bugs.launchpad.net/kicad/+bug/1769408) so I wanted to make sure
that I don't conflict with your work.

Let me know if you see any issues with these patches.

If anyone would like to see the effect of these patches, you can find a
relatively complex board at
https://github.com/ciaa/Hardware/tree/master/PCB/ACC/CIAA_ACC (60k
segments).  The speedup becomes more noticeable as users insert additional
tuned tracks as these create many small segments for connection.

Thanks-
Seth
From fe2b4d222a80c9096de41d7707dbaaf6c4f0546c Mon Sep 17 00:00:00 2001
From: Seth Hillbrand 
Date: Thu, 10 May 2018 13:11:53 -0700
Subject: [PATCH 1/5] Move some connectivity search to std::algs

Previously, binary search was hand-coded.  This moves the search to a
std::algorithm variant.  Also searches bbox by limits rather than
directly iterating.
---
 pcbnew/connectivity_algo.cpp |   2 +-
 pcbnew/connectivity_algo.h   | 119 +++
 2 files changed, 31 insertions(+), 90 deletions(-)

diff --git a/pcbnew/connectivity_algo.cpp b/pcbnew/connectivity_algo.cpp
index bacdc40ef..299740995 100644
--- a/pcbnew/connectivity_algo.cpp
+++ b/pcbnew/connectivity_algo.cpp
@@ -27,7 +27,7 @@
 
 #include 
 #include 
-
+#define PROFILE
 #ifdef PROFILE
 #include 
 #endif
diff --git a/pcbnew/connectivity_algo.h b/pcbnew/connectivity_algo.h
index 2c89d0fed..fd7996a78 100644
--- a/pcbnew/connectivity_algo.h
+++ b/pcbnew/connectivity_algo.h
@@ -570,8 +570,7 @@ public:
 
 bool ContainsAnchor( const CN_ANCHOR_PTR anchor ) const
 {
-auto zone = static_cast ( Parent() );
-return m_cachedPoly->ContainsPoint( anchor->Pos(), zone->GetMinThickness() );
+return ContainsPoint( anchor->Pos() );
 }
 
 bool ContainsPoint( const VECTOR2I p ) const
@@ -630,13 +629,23 @@ public:
 template 
 void CN_LIST::FindNearby( BOX2I aBBox, T aFunc, bool aDirtyOnly )
 {
-for( auto p : m_anchors )
+sort();
+
+CN_ANCHOR_PTR lower_ptr = std::make_shared
+( aBBox.GetPosition(), m_anchors[0]->Item() );
+
+auto lower_it = std::lower_bound( m_anchors.begin(), m_anchors.end(), lower_ptr,
+[](  const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) -> bool
+{ return a->Pos().x < b->Pos().x; } );
+
+for( auto it = lower_it; it != m_anchors.end(); it++)
 {
-if( p->Valid() && aBBox.Contains( p->Pos() ) )
-{
-if( !aDirtyOnly || p->IsDirty() )
-aFunc( p );
-}
+if( (*it)->Pos().x > aBBox.GetRight() )
+break;
+
+if( (*it)->Valid() && ( !aDirtyOnly || (*it)->IsDirty() )
+   && aBBox.Contains( (*it)->Pos() ) )
+aFunc( *it );
 }
 }
 
@@ -664,96 +673,28 @@ void CN_LIST::FindNearby( VECTOR2I aPosition, int aDistMax, T aFunc, bool aDirty
 {
 /* Search items in m_Candidates that position is <= aDistMax from aPosition
  * (Rectilinear distance)
- * m_Candidates is sorted by X then Y values, so a fast binary search is used
- * to locate the "best" entry point in list
- * The best entry is a pad having its m_Pos.x == (or near) aPosition.x
- * All candidates are near this candidate in list
- * So from this entry point, a linear search is made to find all candidates
+ * m_Candidates is sorted by X then Y values, so binary search is made for the first
+ * element.  Then a linear iteration is made to identify all element that are also
+ * in the correct y range.
  */
 
 sort();
 
-int idxmax = m_anchors.size() - 1;
-
-int delta = idxmax + 1;
-int idx = 0;// Starting index is the beginning of list
-
-while( delta )
-{
-// Calculate half size of remaining interval to test.
-// Ensure the computed value is not truncated (too small)
-if( ( delta & 1 ) && ( delta > 1 ) )
-delta++;
-
-delta /= 2;
-
-auto p = m_anchors[idx];
-
-int dist = p->Pos().x - aPosition.x;
-
-if( std::abs( dist ) <= aDistMax )
-{
-break;  // A good entry point is found. The list can be scanned from this point.
-}
-else if( p->Pos().x < aPosition.x ) // We should search after this point
-{
-idx += delta;
-
-if( idx > idxmax )
-idx = idxmax;
-}
-else// We should search before this p
-{
-idx -= delta;
-
-if( idx < 0 )
-idx = 0;
-}
-}
-
-/* Now explore the candidate list from the "best" entry point found
- * (candidate "near" aPosition.x)
- * We exp the list until abs(candidate->m_Point.x - aPosition.x) > aDistMashar* Currently a

Re: [Kicad-developers] [PATCH] Allow OpenCASCADE standard edition

2018-05-15 Thread Seth Hillbrand

Sorry about the broke builds.  I've adjusted the FindOCE section to a
better override, restoring how it searched previously.  OpenCascade changes
should now only affect builds specifically requesting KICAD_USE_OCC.

-Seth



Am Di., 15. Mai 2018 um 05:42 Uhr schrieb Simon Richter <
simon.rich...@hogyros.de>:

> Hi,
>
> On 15.05.2018 10:40, Nick Østergaard wrote:
>
> > The occ patch makes the build fail on macos when enabling oce. I don't
> > understanf why the error message suggest the occ path instead of the occ
> > one. Also I don't understand why the defualt would not work as before.
>
> FWIW, it also makes MSVC builds fail as the script only looks at the
> registry to find OCE, not at -DOCE_DIR=...
>
> Even if OCE paths are stored in the registry, this seems to be lacking
> 32/64 bit distinction, so the upstream script needs to be improved as well.
>
>Simon
>
> ___
> Mailing list: https://launchpad.net/~kicad-developers
> Post to : kicad-developers@lists.launchpad.net
> Unsubscribe : https://launchpad.net/~kicad-developers
> More help   : https://help.launchpad.net/ListHelp
>
___
Mailing list: https://launchpad.net/~kicad-developers
Post to : kicad-developers@lists.launchpad.net
Unsubscribe : https://launchpad.net/~kicad-developers
More help   : https://help.launchpad.net/ListHelp

Re: [Kicad-developers] [PATCH] Allow OpenCASCADE standard edition

2018-05-15 Thread Simon Richter

Hi,

On 15.05.2018 10:40, Nick Østergaard wrote:

> The occ patch makes the build fail on macos when enabling oce. I don't
> understanf why the error message suggest the occ path instead of the occ
> one. Also I don't understand why the defualt would not work as before.

FWIW, it also makes MSVC builds fail as the script only looks at the
registry to find OCE, not at -DOCE_DIR=...

Even if OCE paths are stored in the registry, this seems to be lacking
32/64 bit distinction, so the upstream script needs to be improved as well.

   Simon

___
Mailing list: https://launchpad.net/~kicad-developers
Post to : kicad-developers@lists.launchpad.net
Unsubscribe : https://launchpad.net/~kicad-developers
More help   : https://help.launchpad.net/ListHelp

Re: [Kicad-developers] [PATCH] Allow OpenCASCADE standard edition

2018-05-15 Thread Nick Østergaard

The occ patch makes the build fail on macos when enabling oce. I don't
understanf why the error message suggest the occ path instead of the occ
one. Also I don't understand why the defualt would not work as before.

http://ci.kicad-pcb.org/job/osx-kicad-adam-head/659/console


tir. 20. mar. 2018 00.50 skrev Seth Hillbrand :

> Nick, as always, thanks for the detailed helpful comments.  To specify the
> installation, we will need to set -DOCC_LIBRARY_DIR and -DOCC_INCLUDE_DIR.
> That works on my machine and the docker file.
>
> I'll implement your suggestions and give people another few days to test
> if they're interested in this topic before merging.
>
> Best-
> Seth
>
> 2018-03-18 15:57 GMT-07:00 Nick Østergaard :
>
>> Hi Seth,
>>
>> I tried to test your patch. It bascially works. Some observations follows:
>>
>> I think the message printed from cmake
>> "from /opt/oce/lib/libTKernel.so I found /opt/oce/lib"
>> should be removed from the output, it looks liek a debug message to me. I
>> guess the same information is available in the CMakeCache.txt if needed
>> later on.
>>
>> It defaults to OCE as expected, builds, and runs.
>>
>> If I remove OCE it will find my normal opencascade installation, builds
>> and runs.
>>
>> I think it also did use OCC if I set KICAD_USE_OCC=ON, where it built and
>> ran fine. But when this happens I still see KICAD_USE_OCE=ON in the cache.
>> This might be ok, but could be confusing.
>>
>> I canẗ make it use an alterntive install location of OCC, I tried to set
>> OCC_INCLUDE_DIR=/opt/opencascade7/inc. This fails. What variable do I need
>> to set to select another version of opencascade?
>>
>> I tested this on archlinux. I think it could be improved to be less
>> errorprone, but could possibly be comitted as is if that debug log is
>> removed. It seems to work fine if you are not switching between OCE and OCC
>> in the same build dir, that is, a clean config.
>>
>> Nick
>>
>>
>> 2018-03-17 0:51 GMT+01:00 Nick Østergaard :
>>
>>> Thank you very much, I will try to remember it after the weekend.
>>>
>>> 2018-03-17 <20%2018%2003%2017> 0:46 GMT+01:00 Seth Hillbrand <
>>> seth.hillbr...@gmail.com>:
>>>
 Hi Nick-

 I finally found a moment to figure out Docker and get this up and
 running in your build configuration.

 Please take a look when you have a chance and let me know if you have
 any issues with this patch.

 Best-
 Seth

 2018-02-10 <20%2018%2002%2010> 7:12 GMT-08:00 Seth Hillbrand <
 seth.hillbr...@gmail.com>:

> Nick was having an unknown issue but I haven't heard back from him on
> whether the issue was resolved by doing a clean cmake.  If it isn't then
> I'll need to address that.
>
> Nick did you have a chance to test that?
>
> -S
>
> 2018-02-10 <20%2018%2002%2010> 6:18 GMT-08:00 Wayne Stambaugh <
> stambau...@gmail.com>:
>
>> Seth,
>>
>> What is the current status of this patch?  I would like to get it
>> merged
>> before rc1 so the package devs can test it.
>>
>> Cheers,
>>
>> Wayne
>>
>> On 01/30/2018 02:12 PM, Seth Hillbrand wrote:
>> > Nick-
>> >
>> > Thanks for the test.  I'm attaching revised patch that allows
>> multiple
>> > OpenCASCADE installations on a single machine.
>> >
>> > I've tested with a few different OpenCASCADE versions down to 6.8
>> with
>> > no issues installed alongside OCE 0.17.  You can choose which you
>> want
>> > to link by using either "-DKICAD_USE_OCE" or "-DKICAD_USE_OCC".  If
>> both
>> > are specified, "-DKICAD_USE_OCC" will override.
>> >
>> > I corrected the cmake message display to be less doubled and
>> correctly
>> > show the library location.
>> >
>> > I've also added the OCC version and type to the about window
>> version info.
>> >
>> > The "Based on" line was taken from
>> > (https://github.com/FreeCAD/FreeCAD/blob/master/src/FCConfig.h)
>> when
>> > trying to determine how FreeCAD likes to refer to themselves.  The
>> > actual FindOpenCascade.cmake file did not have a copyright header
>> > attached but falls under the license from
>> > (https://github.com/FreeCAD/FreeCAD/blob/master/COPYING).  I note
>> that I
>> > had it written as "FreeCAD CADx development system".  I've corrected
>> > this to read "FreeCAD CAx development system".
>> >
>> > I'm not sure to what the "CheckSymbolExists" line is referring.  I
>> don't
>> > see it on my machine.
>> >
>> > -Seth
>> >
>> > 2018-01-29 14:30 GMT-08:00 Nick Østergaard > > >:
>> >
>> > Hi Seth,
>> >
>> > I just took the patch for a testrun and will state some
>> comments below.
>> >
>> > This looks a bit strange:
>> >
>>

[Kicad-developers] Some speed up patches

Re: [Kicad-developers] [PATCH] Allow OpenCASCADE standard edition

Re: [Kicad-developers] [PATCH] Allow OpenCASCADE standard edition

Re: [Kicad-developers] [PATCH] Allow OpenCASCADE standard edition

4 matches

Site Navigation

Mail list logo

Footer information