The board I'm working on is quite complex and makes KiCad _very_ slow, so I'm working on a bit of profiling and optimizing. The attached patch memoizes SHAPE_LINE_CHAIN bounding box computation, which is a hot spot during netlist sync (presumably when trace/net connections are calculated). For my specific case, it results in a 38% speedup, from 21 seconds down to 13 seconds.
Next hotspot to tackle is NETLIST_OBJECT_LIST::BuildNetListInfo :) -- Chris
>From 7393dc6bca8cb0a748e790d6607b1ce7fe295fbe Mon Sep 17 00:00:00 2001 From: Chris Pavlina <[email protected]> Date: Sat, 6 Aug 2016 21:32:37 -0400 Subject: [PATCH] Memoize SHAPE_LINE_CHAIN bounding box computation For a specific project+system combination, this gives a 38% speedup on the pcbnew side of netlist sync. --- common/geometry/shape_line_chain.cpp | 8 +++++ include/geometry/shape_line_chain.h | 61 +++++++++++++++++++++++++++++------- 2 files changed, 58 insertions(+), 11 deletions(-) diff --git a/common/geometry/shape_line_chain.cpp b/common/geometry/shape_line_chain.cpp index 9b2118d..55500e7 100644 --- a/common/geometry/shape_line_chain.cpp +++ b/common/geometry/shape_line_chain.cpp @@ -2,6 +2,7 @@ * This program source code file is part of KiCad, a free EDA CAD application. * * Copyright (C) 2013 CERN + * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors. * @author Tomasz Wlostowski <[email protected]> * * This program is free software; you can redistribute it and/or @@ -95,6 +96,8 @@ void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& m_points.erase( m_points.begin() + aStartIndex + 1, m_points.begin() + aEndIndex + 1 ); m_points[aStartIndex] = aP; } + + m_bbox_memo_valid = false; } @@ -108,6 +111,8 @@ void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 ); m_points.insert( m_points.begin() + aStartIndex, aLine.m_points.begin(), aLine.m_points.end() ); + + m_bbox_memo_valid = false; } @@ -120,6 +125,7 @@ void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex ) aStartIndex += PointCount(); m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 ); + m_bbox_memo_valid = false; } @@ -139,6 +145,8 @@ int SHAPE_LINE_CHAIN::Distance( const VECTOR2I& aP ) const int SHAPE_LINE_CHAIN::Split( const VECTOR2I& aP ) { + m_bbox_memo_valid = false; + int ii = -1; int min_dist = 2; diff --git a/include/geometry/shape_line_chain.h b/include/geometry/shape_line_chain.h index ae2bf5e..8f4654c 100644 --- a/include/geometry/shape_line_chain.h +++ b/include/geometry/shape_line_chain.h @@ -2,6 +2,7 @@ * This program source code file is part of KiCad, a free EDA CAD application. * * Copyright (C) 2013 CERN + * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors. * @author Tomasz Wlostowski <[email protected]> * * This program is free software; you can redistribute it and/or @@ -49,6 +50,12 @@ private: typedef std::vector<VECTOR2I>::iterator point_iter; typedef std::vector<VECTOR2I>::const_iterator point_citer; + // SHAPE_LINE_CHAIN::BBox is a hotspot for loading data. + // Here we memoize it to avoid having to recompute the bounding box too many times + BOX2I m_bbox_memo; + int m_bbox_clearance_memo; + bool m_bbox_memo_valid; + public: /** * Struct INTERSECTION @@ -72,14 +79,17 @@ public: * Initializes an empty line chain. */ SHAPE_LINE_CHAIN() : - SHAPE( SH_LINE_CHAIN ), m_closed( false ) + SHAPE( SH_LINE_CHAIN ), m_bbox_memo_valid( false ), m_closed( false ) {} /** * Copy Constructor */ SHAPE_LINE_CHAIN( const SHAPE_LINE_CHAIN& aShape ) : - SHAPE( SH_LINE_CHAIN ), m_points( aShape.m_points ), m_closed( aShape.m_closed ) + SHAPE( SH_LINE_CHAIN ), + m_bbox_memo( aShape.m_bbox_memo ), m_bbox_clearance_memo( aShape.m_bbox_clearance_memo ), + m_bbox_memo_valid( aShape.m_bbox_memo_valid ), m_points( aShape.m_points ), + m_closed( false ) {} /** @@ -87,7 +97,8 @@ public: * Initializes a 2-point line chain (a single segment) */ SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB ) : - SHAPE( SH_LINE_CHAIN ), m_closed( false ) + SHAPE( SH_LINE_CHAIN ), + m_bbox_memo_valid( false ), m_closed( false ) { m_points.resize( 2 ); m_points[0] = aA; @@ -95,7 +106,7 @@ public: } SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) : - SHAPE( SH_LINE_CHAIN ), m_closed( false ) + SHAPE( SH_LINE_CHAIN ), m_bbox_memo_valid( false ), m_closed( false ) { m_points.resize( 3 ); m_points[0] = aA; @@ -104,7 +115,7 @@ public: } SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC, const VECTOR2I& aD ) : - SHAPE( SH_LINE_CHAIN ), m_closed( false ) + SHAPE( SH_LINE_CHAIN ), m_bbox_memo_valid( false ), m_closed( false ) { m_points.resize( 4 ); m_points[0] = aA; @@ -116,7 +127,7 @@ public: SHAPE_LINE_CHAIN( const VECTOR2I* aV, int aCount ) : SHAPE( SH_LINE_CHAIN ), - m_closed( false ) + m_bbox_memo_valid( false ), m_closed( false ) { m_points.resize( aCount ); @@ -137,6 +148,7 @@ public: { m_points.clear(); m_closed = false; + m_bbox_memo_valid = false; } /** @@ -263,13 +275,34 @@ public: /// @copydoc SHAPE::BBox() const BOX2I BBox( int aClearance = 0 ) const { - BOX2I bbox; - bbox.Compute( m_points ); + // Sorry for const-stripping, if you have a prettier way to memoize this + // feel free. + return const_cast<SHAPE_LINE_CHAIN *>( this )->BBoxMemoized( aClearance ); + } + + /** + * Compute the bounding box if necessary, or return a memoized copy if not. + */ + const BOX2I BBoxMemoized( int aClearance = 0 ) + { + if( m_bbox_memo_valid && m_bbox_clearance_memo == aClearance ) + { + return m_bbox_memo; + } + else + { + BOX2I bbox; + bbox.Compute( m_points ); - if( aClearance != 0 ) - bbox.Inflate( aClearance ); + if( aClearance != 0 ) + bbox.Inflate( aClearance ); - return bbox; + m_bbox_memo = bbox; + m_bbox_clearance_memo = aClearance; + m_bbox_memo_valid = true; + + return bbox; + } } /** @@ -328,6 +361,7 @@ public: { VECTOR2I v( aX, aY ); Append( v, aAllowDuplication ); + m_bbox_memo_valid = false; } /** @@ -372,11 +406,14 @@ public: m_points.push_back( p ); m_bbox.Merge( p ); } + + m_bbox_memo_valid = false; } void Insert( int aVertex, const VECTOR2I& aP ) { m_points.insert( m_points.begin() + aVertex, aP ); + m_bbox_memo_valid = false; } /** @@ -577,6 +614,8 @@ public: { for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i ) (*i) += aVector; + + m_bbox_memo_valid = false; } bool IsSolid() const -- 2.9.2
_______________________________________________ Mailing list: https://launchpad.net/~kicad-developers Post to : [email protected] Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
