Re: [Kicad-developers] [PATCH] Memoize SHAPE_LINE_CHAIN bounding box computation

2016-08-11 Thread Maciej Sumiński 
Just to let you know: I had asked Tom and he had had nothing against the
patch, so Chris has committed it.

Regards,
Orson

On 08/10/2016 04:19 PM, Wayne Stambaugh wrote:
> Orson & Tom,
> 
> Please look over this patch when you get a chance to see if it makes
> sense to commit it.
> 
> Thanks,
> 
> Wayne
> 
> On 8/6/2016 9:36 PM, Chris Pavlina wrote:
>> 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 :)
>>
>>
>>
>> ___
>> 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
> 




signature.asc
Description: OpenPGP digital signature
___
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] Memoize SHAPE_LINE_CHAIN bounding box computation

2016-08-10 Thread Wayne Stambaugh 
Orson & Tom,

Please look over this patch when you get a chance to see if it makes
sense to commit it.

Thanks,

Wayne

On 8/6/2016 9:36 PM, Chris Pavlina wrote:
> 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 :)
> 
> 
> 
> ___
> 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

[Kicad-developers] [PATCH] Memoize SHAPE_LINE_CHAIN bounding box computation

2016-08-06 Thread Chris Pavlina 
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 
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 
  *
  * 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 
  *
  * This program is free software; you can redistribute it and/or
@@ -49,6 +50,12 @@ private:
 typedef std::vector::iterator point_iter;
 typedef std::vector::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,