kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #35773
Some speed up patches
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 <hillbrand@xxxxxxxxxxx>
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 <thread>
#include <mutex>
-
+#define PROFILE
#ifdef PROFILE
#include <profile.h>
#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<ZONE_CONTAINER*> ( 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 <class T>
void CN_LIST::FindNearby( BOX2I aBBox, T aFunc, bool aDirtyOnly )
{
- for( auto p : m_anchors )
+ sort();
+
+ CN_ANCHOR_PTR lower_ptr = std::make_shared<CN_ANCHOR>
+ ( 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 linear search is made because the number of candidates
- * having the right X position is usually small
- */
- // search next candidates in list
- VECTOR2I diff;
-
- for( int ii = idx; ii <= idxmax; ii++ )
- {
- auto& p = m_anchors[ii];
- diff = p->Pos() - aPosition;;
-
- if( std::abs( diff.x ) > aDistMax )
- break; // Exit: the distance is to long, we cannot find other candidates
+ CN_ANCHOR_PTR lower = std::make_shared<CN_ANCHOR>
+ ( aPosition - VECTOR2I( aDistMax + 1, 0 ), m_anchors[0]->Item() );
- if( std::abs( diff.y ) > aDistMax )
- continue; // the y distance is to long, but we can find other candidates
-
- // We have here a good candidate: add it
- if( p->Valid() )
- if( !aDirtyOnly || p->IsDirty() )
- aFunc( p );
- }
+ auto lower_it = std::lower_bound( m_anchors.begin(), m_anchors.end(), lower,
+ []( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) -> bool
+ { return a->Pos().x < b->Pos().x; } );
- // search previous candidates in list
- for( int ii = idx - 1; ii >=0; ii-- )
+ for( auto it = lower_it; it != m_anchors.end(); it++ )
{
- auto& p = m_anchors[ii];
- diff = p->Pos() - aPosition;
-
- if( abs( diff.x ) > aDistMax )
+ if( (*it)->Pos().x > aDistMax + aPosition.x )
break;
- if( abs( diff.y ) > aDistMax )
- continue;
-
- // We have here a good candidate:add it
- if( p->Valid() )
- {
- if( !aDirtyOnly || p->IsDirty() )
- aFunc( p );
- }
+ if( (*it)->Valid() && std::abs( (*it)->Pos().y - aPosition.y ) < aDistMax
+ && ( !aDirtyOnly || (*it)->IsDirty() ) )
+ aFunc( *it );
}
}
--
2.11.0
From bcee561e5aac64086b6ded72676f41ffab726ce6 Mon Sep 17 00:00:00 2001
From: Seth Hillbrand <hillbrand@xxxxxxxxxxx>
Date: Fri, 11 May 2018 12:47:12 -0700
Subject: [PATCH 3/5] Adjust connectivity search
To increase the responsiveness of the connectivity search on large
boards, we add additional segmentation of the search space, omitting
non-dirty elements from the recalculation.
---
pcbnew/connectivity_algo.cpp | 108 +++++++++++++++++++++++++------------------
pcbnew/connectivity_algo.h | 61 ++++++++++++++++++------
2 files changed, 111 insertions(+), 58 deletions(-)
diff --git a/pcbnew/connectivity_algo.cpp b/pcbnew/connectivity_algo.cpp
index 29e650acd..2a649cec8 100644
--- a/pcbnew/connectivity_algo.cpp
+++ b/pcbnew/connectivity_algo.cpp
@@ -27,7 +27,7 @@
#include <thread>
#include <mutex>
-#define PROFILE
+
#ifdef PROFILE
#include <profile.h>
#endif
@@ -302,15 +302,9 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
{
std::mutex cnListLock;
- int totalDirtyCount = 0;
-
- if( m_lastSearchWithZones != aIncludeZones )
- {
- m_padList.MarkAllAsDirty();
- m_viaList.MarkAllAsDirty();
- m_trackList.MarkAllAsDirty();
- m_zoneList.MarkAllAsDirty();
- }
+#ifdef PROFILE
+ PROF_COUNTER search_conns( "full-search-connections" );
+#endif
m_lastSearchWithZones = aIncludeZones;
@@ -454,8 +448,6 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
for( auto item : garbage )
delete item;
- //auto all = allItemsInBoard();
-
#ifdef CONNECTIVITY_DEBUG
for( auto item : m_padList )
if( all.find( item->Parent() ) == all.end() ) { printf("Failing pad : %p\n", item->Parent() ); assert ( false ); }
@@ -470,57 +462,81 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
if( all.find( item->Parent() ) == all.end() ) { printf("Failing zome : %p\n", item->Parent() ); assert ( false ); }
#endif
+
+ // The search functions below assume a sorted list, so ensure that is true for all lists
+ m_padList.Sort();
+ m_trackList.Sort();
+ m_viaList.Sort();
+
#ifdef PROFILE
- PROF_COUNTER search_cnt( "search-connections" );
- PROF_COUNTER search_basic( "search-basic" );
PROF_COUNTER search_pads( "search-pads" );
- PROF_COUNTER search_tracks( "search-tracks" );
#endif
- if( m_padList.IsDirty() || m_trackList.IsDirty() || m_viaList.IsDirty() )
+ if( m_padList.IsDirty() )
{
- totalDirtyCount++;
-
for( auto padItem : m_padList )
{
- auto pad = static_cast<D_PAD*> ( padItem->Parent() );
- auto searchPads = std::bind( checkForConnection, _1, padItem );
+ if( padItem->Dirty() )
+ {
+ auto pad = static_cast<D_PAD*> ( padItem->Parent() );
+ auto layers = pad->GetLayerSet() & LSET::AllCuMask();
+ auto searchPads = std::bind( checkForConnection, _1, padItem );
- m_padList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, pad->GetLayerSet() );
- m_trackList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, pad->GetLayerSet() );
- m_viaList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, pad->GetLayerSet() );
+ m_padList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, layers );
+ m_viaList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, layers );
+ m_trackList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, layers );
+ }
}
+ }
+
#ifdef PROFILE
- search_pads.Show();
+ search_pads.Show();
+ PROF_COUNTER search_tracks( "search-tracks" );
#endif
-
+ if( m_trackList.IsDirty() )
+ {
for( auto& trackItem : m_trackList )
{
- auto track = static_cast<TRACK*> ( trackItem->Parent() );
- int dist_max = track->GetWidth() / 2;
- auto searchTracks = std::bind( checkForConnection, _1, trackItem, dist_max );
-
- m_trackList.FindNearby( track->GetStart(), dist_max, searchTracks, track->GetLayerSet() );
- m_trackList.FindNearby( track->GetEnd(), dist_max, searchTracks, track->GetLayerSet() );
+ if( trackItem->Dirty() )
+ {
+ auto track = static_cast<TRACK*> ( trackItem->Parent() );
+ auto layers = track->GetLayerSet() & LSET::AllCuMask();
+ int dist_max = track->GetWidth() / 2;
+ auto searchTracks = std::bind( checkForConnection, _1, trackItem, dist_max );
+
+ m_trackList.FindNearby( track->GetStart(), dist_max, searchTracks, layers);
+ m_viaList.FindNearby( track->GetStart(), dist_max, searchTracks );
+ m_padList.FindNearby( track->GetStart(), dist_max, searchTracks, layers);
+ m_trackList.FindNearby( track->GetEnd(), dist_max, searchTracks, layers );
+ m_viaList.FindNearby( track->GetEnd(), dist_max, searchTracks );
+ m_padList.FindNearby( track->GetEnd(), dist_max, searchTracks, layers );
+ }
}
+ }
#ifdef PROFILE
- search_tracks.Show();
+ search_tracks.Show();
+ PROF_COUNTER search_vias( "search-vias" );
#endif
+ if( m_viaList.IsDirty() )
+ {
for( auto& viaItem : m_viaList )
{
- auto via = static_cast<VIA*> ( viaItem->Parent() );
- int dist_max = via->GetWidth() / 2;
- auto searchVias = std::bind( checkForConnection, _1, viaItem, dist_max );
+ if( viaItem->Dirty() )
+ {
+ auto via = static_cast<VIA*> ( viaItem->Parent() );
+ int dist_max = via->GetWidth() / 2;
+ auto searchVias = std::bind( checkForConnection, _1, viaItem, dist_max );
- totalDirtyCount++;
- m_viaList.FindNearby( via->GetStart(), dist_max, searchVias );
- m_trackList.FindNearby( via->GetStart(), dist_max, searchVias );
+ m_viaList.FindNearby( via->GetStart(), dist_max, searchVias );
+ m_trackList.FindNearby( via->GetStart(), dist_max, searchVias );
+ m_padList.FindNearby( via->GetStart(), dist_max, searchVias );
+ }
}
}
-
#ifdef PROFILE
- search_basic.Show();
+ search_vias.Show();
+ PROF_COUNTER search_cnt( "search-zones" );
#endif
if( aIncludeZones )
@@ -552,14 +568,14 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
{
auto item = m_zoneList[i];
auto zoneItem = static_cast<CN_ZONE *> (item);
+ auto layers = zoneItem->Parent()->GetLayerSet() & LSET::AllCuMask();
auto searchZones = std::bind( checkForConnection, _1, zoneItem );
if( zoneItem->Dirty() || m_padList.IsDirty() || m_trackList.IsDirty() || m_viaList.IsDirty() )
{
- totalDirtyCount++;
- m_viaList.FindNearby( zoneItem->BBox(), searchZones );
- m_trackList.FindNearby( zoneItem->BBox(), searchZones );
- m_padList.FindNearby( zoneItem->BBox(), searchZones );
+ m_viaList.FindNearby( zoneItem->BBox(), searchZones, layers );
+ m_trackList.FindNearby( zoneItem->BBox(), searchZones, layers );
+ m_padList.FindNearby( zoneItem->BBox(), searchZones, layers );
m_zoneList.FindNearbyZones( zoneItem->BBox(), std::bind( checkInterZoneConnection, _1, zoneItem ) );
}
@@ -588,6 +604,8 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
#ifdef PROFILE
search_cnt.Show();
+ search_conns.Show();
+ printf("\n");
#endif
}
@@ -663,7 +681,7 @@ const CN_CONNECTIVITY_ALGO::CLUSTERS CN_CONNECTIVITY_ALGO::SearchClusters( CLUST
CLUSTERS clusters;
if( isDirty() )
- searchConnections( includeZones );
+ searchConnections( true );
auto addToSearchList = [&head, withinAnyNet, aSingleNet, aTypes] ( CN_ITEM *aItem )
{
diff --git a/pcbnew/connectivity_algo.h b/pcbnew/connectivity_algo.h
index a36af5fbf..d92bd8f7d 100644
--- a/pcbnew/connectivity_algo.h
+++ b/pcbnew/connectivity_algo.h
@@ -407,6 +407,9 @@ class CN_LIST
{
private:
bool m_dirty;
+ bool m_unsorted;
+ bool m_sorted_once;
+
std::vector<CN_ANCHOR_PTR> m_anchors;
CN_ANCHORS m_layer_anchors[PCB_LAYER_ID_COUNT];
@@ -427,25 +430,60 @@ protected:
private:
- void sort()
+ inline void anchorInsertionSort( CN_ANCHORS::iterator aBegin, CN_ANCHORS::iterator aEnd )
{
- if( m_dirty )
- {
- std::sort( m_anchors.begin(), m_anchors.end() );
+ if( aBegin == aEnd)
+ return;
- for( auto i = 0; i < PCB_LAYER_ID_COUNT; i++ )
+ for( auto it = aBegin + 1; it != aEnd; it++ )
+ {
+ if( *( it - 1 ) > *it )
{
- std::sort( m_layer_anchors[i].begin(), m_layer_anchors[i].end() );
+ auto const insertion = std::upper_bound( aBegin, it, *it );
+ std::rotate( insertion, it, it + 1 );
}
-
- m_dirty = false;
}
- }
+ };
public:
CN_LIST()
{
m_dirty = false;
+ m_unsorted = false;
+ m_sorted_once = false;
+ }
+
+ void Sort()
+ {
+ /**
+ * STD library sort is efficient only for unsorted lists.
+ * After sorting once, we switch to an insertion for for mostly-sorted lists
+ */
+ if( m_unsorted )
+ {
+ if( !m_sorted_once )
+ {
+ std::sort( m_anchors.begin(), m_anchors.end() );
+
+ for( auto i = 0; i < PCB_LAYER_ID_COUNT; i++ )
+ {
+ std::sort( m_layer_anchors[i].begin(), m_layer_anchors[i].end() );
+ }
+
+ m_sorted_once = true;
+ }
+ else
+ {
+ anchorInsertionSort( m_anchors.begin(), m_anchors.end() );
+
+ for( auto i = 0; i < PCB_LAYER_ID_COUNT; i++ )
+ {
+ anchorInsertionSort( m_layer_anchors[i].begin(), m_layer_anchors[i].end() );
+ }
+ }
+
+ m_unsorted = false;
+ }
}
void Clear()
@@ -474,6 +512,7 @@ public:
void SetDirty( bool aDirty = true )
{
m_dirty = aDirty;
+ m_unsorted = aDirty;
}
bool IsDirty() const
@@ -642,8 +681,6 @@ public:
template <class T>
void CN_LIST::FindNearby( BOX2I aBBox, T aFunc, LSET aLayers, bool aDirtyOnly )
{
- sort();
-
CN_ANCHORS *anchor_set = &m_anchors;
PCB_LAYER_ID layer = aLayers.ExtractLayer();
@@ -700,8 +737,6 @@ void CN_LIST::FindNearby( VECTOR2I aPosition, int aDistMax, T aFunc, LSET aLayer
* in the correct y range.
*/
- sort();
-
CN_ANCHORS *anchor_set = &m_anchors;
PCB_LAYER_ID layer = aLayers.ExtractLayer();
--
2.11.0
From 4e412ce2d9188e7248548f5a20fee982de1af977 Mon Sep 17 00:00:00 2001
From: Seth Hillbrand <hillbrand@xxxxxxxxxxx>
Date: Thu, 10 May 2018 18:01:38 -0700
Subject: [PATCH 2/5] Split anchor vectors by layer
This is a speed commit for large boards. Tracks and pads cannot connect
to elements that are not on the same layer. Rather than checking for
this at the last step, this commit splits the anchor vectors by layer,
limiting the initial search space.
---
pcbnew/connectivity_algo.cpp | 27 +++++++++++++++++-----
pcbnew/connectivity_algo.h | 53 +++++++++++++++++++++++++++++++++++---------
2 files changed, 64 insertions(+), 16 deletions(-)
diff --git a/pcbnew/connectivity_algo.cpp b/pcbnew/connectivity_algo.cpp
index 299740995..29e650acd 100644
--- a/pcbnew/connectivity_algo.cpp
+++ b/pcbnew/connectivity_algo.cpp
@@ -473,6 +473,8 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
#ifdef PROFILE
PROF_COUNTER search_cnt( "search-connections" );
PROF_COUNTER search_basic( "search-basic" );
+ PROF_COUNTER search_pads( "search-pads" );
+ PROF_COUNTER search_tracks( "search-tracks" );
#endif
if( m_padList.IsDirty() || m_trackList.IsDirty() || m_viaList.IsDirty() )
@@ -484,10 +486,13 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
auto pad = static_cast<D_PAD*> ( padItem->Parent() );
auto searchPads = std::bind( checkForConnection, _1, padItem );
- m_padList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads );
- m_trackList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads );
- m_viaList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads );
+ m_padList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, pad->GetLayerSet() );
+ m_trackList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, pad->GetLayerSet() );
+ m_viaList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, pad->GetLayerSet() );
}
+#ifdef PROFILE
+ search_pads.Show();
+#endif
for( auto& trackItem : m_trackList )
{
@@ -495,9 +500,12 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
int dist_max = track->GetWidth() / 2;
auto searchTracks = std::bind( checkForConnection, _1, trackItem, dist_max );
- m_trackList.FindNearby( track->GetStart(), dist_max, searchTracks );
- m_trackList.FindNearby( track->GetEnd(), dist_max, searchTracks );
+ m_trackList.FindNearby( track->GetStart(), dist_max, searchTracks, track->GetLayerSet() );
+ m_trackList.FindNearby( track->GetEnd(), dist_max, searchTracks, track->GetLayerSet() );
}
+#ifdef PROFILE
+ search_tracks.Show();
+#endif
for( auto& viaItem : m_viaList )
{
@@ -602,6 +610,15 @@ void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
} );
m_anchors.resize( lastAnchor - m_anchors.begin() );
+ for( auto i = 0; i < PCB_LAYER_ID_COUNT; i++ )
+ {
+ lastAnchor = std::remove_if(m_layer_anchors[i].begin(), m_layer_anchors[i].end(),
+ [] ( const CN_ANCHOR_PTR anchor ) {
+ return !anchor->Valid();
+ } );
+
+ m_layer_anchors[i].resize( lastAnchor - m_layer_anchors[i].begin() );
+ }
auto lastItem = std::remove_if(m_items.begin(), m_items.end(), [&aGarbage] ( CN_ITEM* item ) {
if( !item->Valid() )
diff --git a/pcbnew/connectivity_algo.h b/pcbnew/connectivity_algo.h
index fd7996a78..a36af5fbf 100644
--- a/pcbnew/connectivity_algo.h
+++ b/pcbnew/connectivity_algo.h
@@ -408,13 +408,21 @@ class CN_LIST
private:
bool m_dirty;
std::vector<CN_ANCHOR_PTR> m_anchors;
+ CN_ANCHORS m_layer_anchors[PCB_LAYER_ID_COUNT];
protected:
std::vector<CN_ITEM*> m_items;
void addAnchor( VECTOR2I pos, CN_ITEM* item )
{
- m_anchors.push_back( item->AddAnchor( pos ) );
+ CN_ANCHOR_PTR new_anchor = item->AddAnchor( pos );
+ m_anchors.push_back( new_anchor );
+
+ for( int i = 0; i < PCB_LAYER_ID_COUNT; i++ )
+ {
+ if( ( item->Parent()->GetLayerSet() & LSET( 1, i ) ).any() )
+ m_layer_anchors[i].push_back( new_anchor );
+ }
}
private:
@@ -425,6 +433,11 @@ private:
{
std::sort( m_anchors.begin(), m_anchors.end() );
+ for( auto i = 0; i < PCB_LAYER_ID_COUNT; i++ )
+ {
+ std::sort( m_layer_anchors[i].begin(), m_layer_anchors[i].end() );
+ }
+
m_dirty = false;
}
}
@@ -453,10 +466,10 @@ public:
std::vector<CN_ANCHOR_PTR>& Anchors() { return m_anchors; }
template <class T>
- void FindNearby( VECTOR2I aPosition, int aDistMax, T aFunc, bool aDirtyOnly = false );
+ void FindNearby( VECTOR2I aPosition, int aDistMax, T aFunc, LSET aLayers = LSET::AllLayersMask(), bool aDirtyOnly = false );
template <class T>
- void FindNearby( BOX2I aBBox, T aFunc, bool aDirtyOnly = false );
+ void FindNearby( BOX2I aBBox, T aFunc, LSET aLayers = LSET::AllLayersMask(), bool aDirtyOnly = false );
void SetDirty( bool aDirty = true )
{
@@ -627,18 +640,27 @@ public:
template <class T>
-void CN_LIST::FindNearby( BOX2I aBBox, T aFunc, bool aDirtyOnly )
+void CN_LIST::FindNearby( BOX2I aBBox, T aFunc, LSET aLayers, bool aDirtyOnly )
{
sort();
+ CN_ANCHORS *anchor_set = &m_anchors;
+ PCB_LAYER_ID layer = aLayers.ExtractLayer();
+
+ if( layer > 0 )
+ anchor_set = &(m_layer_anchors[ layer ]);
+
+ if( (*anchor_set).size() == 0 )
+ return;
+
CN_ANCHOR_PTR lower_ptr = std::make_shared<CN_ANCHOR>
- ( aBBox.GetPosition(), m_anchors[0]->Item() );
+ ( aBBox.GetPosition(), (*anchor_set)[0]->Item() );
- auto lower_it = std::lower_bound( m_anchors.begin(), m_anchors.end(), lower_ptr,
+ auto lower_it = std::lower_bound( anchor_set->begin(), anchor_set->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++)
+ for( auto it = lower_it; it != anchor_set->end(); it++)
{
if( (*it)->Pos().x > aBBox.GetRight() )
break;
@@ -669,7 +691,7 @@ void CN_ZONE_LIST::FindNearbyZones( BOX2I aBBox, T aFunc, bool aDirtyOnly )
template <class T>
-void CN_LIST::FindNearby( VECTOR2I aPosition, int aDistMax, T aFunc, bool aDirtyOnly )
+void CN_LIST::FindNearby( VECTOR2I aPosition, int aDistMax, T aFunc, LSET aLayers, bool aDirtyOnly )
{
/* Search items in m_Candidates that position is <= aDistMax from aPosition
* (Rectilinear distance)
@@ -680,14 +702,23 @@ void CN_LIST::FindNearby( VECTOR2I aPosition, int aDistMax, T aFunc, bool aDirty
sort();
+ CN_ANCHORS *anchor_set = &m_anchors;
+ PCB_LAYER_ID layer = aLayers.ExtractLayer();
+
+ if( layer > 0 )
+ anchor_set = &(m_layer_anchors[ layer ]);
+
+ if( (*anchor_set).size() == 0 )
+ return;
+
CN_ANCHOR_PTR lower = std::make_shared<CN_ANCHOR>
- ( aPosition - VECTOR2I( aDistMax + 1, 0 ), m_anchors[0]->Item() );
+ ( aPosition - VECTOR2I( aDistMax, 0 ), (*anchor_set)[0]->Item() );
- auto lower_it = std::lower_bound( m_anchors.begin(), m_anchors.end(), lower,
+ auto lower_it = std::lower_bound( anchor_set->begin(), anchor_set->end(), lower,
[]( 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++ )
+ for( auto it = lower_it; it != anchor_set->end(); it++ )
{
if( (*it)->Pos().x > aDistMax + aPosition.x )
break;
--
2.11.0
From 8cc6ac577da2d231921d9ca82b977fda56d8a374 Mon Sep 17 00:00:00 2001
From: Seth Hillbrand <hillbrand@xxxxxxxxxxx>
Date: Tue, 15 May 2018 14:22:29 -0700
Subject: [PATCH 4/5] Optimize zone connection search
When searching for zone connections we need only consider two cases:
1) The individual zone has changed
2) Some element that connects to the zone has changed
In case 1, we search all possible connections to the zone -- this is
slower. In case 2, which is the case when routing, we need only search
the connection lists that are dirty for their connections to the zone.
---
pcbnew/connectivity_algo.cpp | 24 ++++++++++++++----------
1 file changed, 14 insertions(+), 10 deletions(-)
diff --git a/pcbnew/connectivity_algo.cpp b/pcbnew/connectivity_algo.cpp
index 2a649cec8..8a946b06b 100644
--- a/pcbnew/connectivity_algo.cpp
+++ b/pcbnew/connectivity_algo.cpp
@@ -541,8 +541,6 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
if( aIncludeZones )
{
- int cnt = 0;
-
if( m_progressReporter )
{
m_progressReporter->SetMaxProgress( m_zoneList.Size() );
@@ -571,22 +569,28 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
auto layers = zoneItem->Parent()->GetLayerSet() & LSET::AllCuMask();
auto searchZones = std::bind( checkForConnection, _1, zoneItem );
- if( zoneItem->Dirty() || m_padList.IsDirty() || m_trackList.IsDirty() || m_viaList.IsDirty() )
+ if( zoneItem->Dirty() )
{
m_viaList.FindNearby( zoneItem->BBox(), searchZones, layers );
m_trackList.FindNearby( zoneItem->BBox(), searchZones, layers );
m_padList.FindNearby( zoneItem->BBox(), searchZones, layers );
m_zoneList.FindNearbyZones( zoneItem->BBox(), std::bind( checkInterZoneConnection, _1, zoneItem ) );
}
-
+ else
{
- std::lock_guard<std::mutex> lock( cnListLock );
- cnt++;
+ if( m_viaList.IsDirty() )
+ m_viaList.FindNearby( zoneItem->BBox(), searchZones, layers );
- if (m_progressReporter)
- {
- m_progressReporter->AdvanceProgress();
- }
+ if( m_trackList.IsDirty() )
+ m_trackList.FindNearby( zoneItem->BBox(), searchZones, layers );
+
+ if( m_padList.IsDirty() )
+ m_padList.FindNearby( zoneItem->BBox(), searchZones, layers );
+ }
+
+ if (m_progressReporter)
+ {
+ m_progressReporter->AdvanceProgress();
}
}
}
--
2.11.0
From 807fad041789fcd496126a332b76dc52c2f5517a Mon Sep 17 00:00:00 2001
From: Seth Hillbrand <hillbrand@xxxxxxxxxxx>
Date: Tue, 15 May 2018 15:50:59 -0700
Subject: [PATCH 5/5] Garbage collection optimization
We only need to iterate over the anchors when there are items that are
marked invalid. We check once in the item list and only if there are
invalid items to remove do we trim the anchor lists.
However, the connected items might still need to be trimmed, so we leave
this final step outside of the conditional.
---
pcbnew/connectivity_algo.cpp | 43 +++++++++++++++++++++++++------------------
1 file changed, 25 insertions(+), 18 deletions(-)
diff --git a/pcbnew/connectivity_algo.cpp b/pcbnew/connectivity_algo.cpp
index 8a946b06b..a77f56d8b 100644
--- a/pcbnew/connectivity_algo.cpp
+++ b/pcbnew/connectivity_algo.cpp
@@ -437,6 +437,9 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
printf("Search start\n");
#endif
+#ifdef PROFILE
+ PROF_COUNTER garbage_collection( "garbage-collection" );
+#endif
std::vector<CN_ITEM*> garbage;
garbage.reserve( 1024 );
@@ -469,6 +472,7 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
m_viaList.Sort();
#ifdef PROFILE
+ garbage_collection.Show();
PROF_COUNTER search_pads( "search-pads" );
#endif
@@ -626,23 +630,8 @@ void CN_ITEM::RemoveInvalidRefs()
void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
{
- auto lastAnchor = std::remove_if(m_anchors.begin(), m_anchors.end(),
- [] ( const CN_ANCHOR_PTR anchor ) {
- return !anchor->Valid();
- } );
-
- m_anchors.resize( lastAnchor - m_anchors.begin() );
- for( auto i = 0; i < PCB_LAYER_ID_COUNT; i++ )
+ auto lastItem = std::remove_if(m_items.begin(), m_items.end(), [&aGarbage] ( CN_ITEM* item )
{
- lastAnchor = std::remove_if(m_layer_anchors[i].begin(), m_layer_anchors[i].end(),
- [] ( const CN_ANCHOR_PTR anchor ) {
- return !anchor->Valid();
- } );
-
- m_layer_anchors[i].resize( lastAnchor - m_layer_anchors[i].begin() );
- }
-
- auto lastItem = std::remove_if(m_items.begin(), m_items.end(), [&aGarbage] ( CN_ITEM* item ) {
if( !item->Valid() )
{
aGarbage.push_back ( item );
@@ -652,10 +641,28 @@ void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
return false;
} );
- m_items.resize( lastItem - m_items.begin() );
+ if( lastItem != m_items.end())
+ {
+ auto lastAnchor = std::remove_if(m_anchors.begin(), m_anchors.end(),
+ [] ( const CN_ANCHOR_PTR anchor ) {
+ return !anchor->Valid();
+ } );
+
+ m_anchors.resize( lastAnchor - m_anchors.begin() );
+ for( auto i = 0; i < PCB_LAYER_ID_COUNT; i++ )
+ {
+ lastAnchor = std::remove_if(m_layer_anchors[i].begin(), m_layer_anchors[i].end(),
+ [] ( const CN_ANCHOR_PTR anchor ) {
+ return !anchor->Valid();
+ } );
- // fixme: mem leaks
+ m_layer_anchors[i].resize( lastAnchor - m_layer_anchors[i].begin() );
+ }
+ m_items.resize( lastItem - m_items.begin() );
+ }
+
+ // fixme: mem leaks
for( auto item : m_items )
item->RemoveInvalidRefs();
}
--
2.11.0
Follow ups
