kicad-developers team mailing list archive

[Chris Pavlina <pavlina.chris@xxxxxxxxx>]

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 <pavlina.chris@xxxxxxxxx>
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 <tomasz.wlostowski@xxxxxxx>
  *
  * 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 <tomasz.wlostowski@xxxxxxx>
  *
  * 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