kicad-developers team mailing list archive

[Jon Evans <jon@xxxxxxxxxxxxx>]

Update: after some more testing, I think Orson's patch on top of mine is
the way to go.  It pulls the computation out of the loops for autorouter,
and that's the only place where the board's bounding box is used
repetitively.  Since the other call sites are only going to get the
bounding box intermittently, I don't think it's worth any effort doing
complicated things to track and recompute the bounding box when things are
changed.

So, I think my patch and Orson's should be merged.

-Jon

On Tue, Feb 28, 2017 at 6:51 PM, Jon Evans <jon@xxxxxxxxxxxxx> wrote:

> I'm finally back to this problem now that I have some other WIP committed.
>
> As far as I can tell, there two paths to go down for this problem:
>
> 1) Implement auto-caching of the bounding box.  This requires some
> mechanism to tell BOARD that it needs to update the cache, be it OBSERVABLE
> or some other update function added to BOARD_ITEM.  No matter how it's
> done, this method seems not great to me because it requires touching a ton
> of code to provide coverage for every possible entry point that could end
> up having an effect on the bounding box.
>
> 2) Have two different calls to get the bounding box for an EDA_ITEM, one
> that always re-generates the cache and one that just returns a cached
> value.  Update the call sites that hit the bounding box frequently
> (autorouter, etc) to make use of the cached value; keep the call sites that
> always re-generate the bounding box in today's code working that way.
> Performance shouldn't be any better or worse than it is now.
>
> 3) Track whether a board is clean/dirty in some other way besides looking
> at BOARD_ITEMs.  This might not be practical while we still support legacy,
> but once there is only GAL, I could see this maybe being possible through
> the tool framework.  For example, actions could be marked as possibly
> impacting the board or not (i.e. move item does, zoom does not)
>
> So, unless someone suggests otherwise, I'm going to try implementing #2,
> and suggest #3 as a future improvement that would improve performance for
> some edge case operations (i.e. "zoom to fit screen" would be instantaneous
> if nothing has modified the board since the last time the bbox was cached,
> even on large boards)
>
> -Jon
>
> On Fri, Feb 24, 2017 at 11:01 AM, Wayne Stambaugh <stambaughw@xxxxxxxxx>
> wrote:
>
>> On 2/24/2017 10:30 AM, Maciej Sumiński wrote:
>> > Most of the operations one can do on a BOARD_ITEM potentially affects
>> > the board bounding box. It means there might be many places where the
>> > notifications should be added.
>> >
>> > Some time ago, Michael Steinberg has put in place OBSERVABLE class
>> > (include/observable.h) that could facilitate the task.
>>
>> It could be useful but I'm not sure it would be a better design than the
>> child object informing it's parent that it's bounding box has changed.
>> I'm not sure the additional code would make the code any more readable.
>> The only benefit would be if other observers were required.
>>
>> >
>> > With the current approach, developers have to guess whether to update
>> > the bounding box with ComputeBoundingBox() or take the cached value.
>> > Update is called in very few places, so I really wonder what kind of
>> > magic makes it work, but I might have missed something here.
>>
>> This solution would require limiting the entry points in the BOARD
>> object that allow changes to the BOARD's child items.  Conceptually this
>> is probably easier to understand but requires developers to be diligent
>> when making changes to the BOARD object or not trying to bypass these
>> entry points.
>>
>> >
>> > Regards,
>> > Orson
>> >
>> > On 02/24/2017 04:06 PM, Wayne Stambaugh wrote:
>> >> Every BOARD_ITEM has a parent/child relationship or at least it did if
>> >> someone did not break it.  You can always find the parent BOARD object
>> >> by walking up the BOARD_ITEM parent list.  There is already a
>> >> BOARD_ITEM::GetBoard() call that should return the parent board.  You
>> >> could use that to notify the BOARD object when a child BOARD_ITEM
>> change
>> >> effects the bounding box.
>> >>
>> >> On 2/24/2017 9:27 AM, Jon Evans wrote:
>> >>> We need a solution that allows GetBoundingBox to be called blindly,
>> >>> without knowing if (or how) an EDA_ITEM subclass needs to have the
>> >>> bounding box updated.
>> >>>
>> >>> Does anyone have ideas about how complicated it would be to give the
>> >>> BOARD class knowledge of whether or not anything inside it has
>> changed?
>> >>> This is what I tried to implement at first, but Orson pointed out that
>> >>> the way I did it would miss some kinds of changes.
>> >>>
>> >>> Figuring out the above also seems useful for other reasons -- for
>> >>> example, autosave / backup features are easier to implement if there
>> is
>> >>> a global "dirty/clean" flag for things like BOARD.
>> >>>
>> >>> If there is no good way to implement caching, I guess another way
>> would
>> >>> be to implement caching at the sites that use the BOARD bounding box
>> >>> heavily (autorouter etc)
>> >>>
>> >>> -Jon
>> >>>
>> >>> On Fri, Feb 24, 2017 at 9:22 AM, Wayne Stambaugh <
>> stambaughw@xxxxxxxxx
>> >>> <mailto:stambaughw@xxxxxxxxx>> wrote:
>> >>>
>> >>>     On 2/24/2017 4:16 AM, Maciej Sumiński wrote:
>> >>>     > Hi Jon,
>> >>>     >
>> >>>     > The current version looks much better to me. From what I see
>> there is no
>> >>>     > actual bounding box caching, as GetBoundingBox() always calls
>> >>>     > ComputeBoundingBox(). I am fine with that, but before I push
>> the patch I
>> >>>     > need to ask: does anyone know why the board bounding box is
>> cached? I
>> >>>     > believe it must have been done to boost performance of certain
>> parts of
>> >>>     > the code, but I wonder if it is really necessary. Especially
>> that one
>> >>>     > needs to know that it has to be updated using
>> ComputeBoundingBox().
>> >>>
>> >>>     It was cached so it didn't need to be recalculated every time the
>> >>>     bounding box was required.  It should or at least it did
>> recalculate
>> >>>     only when the changes were made since the last call to fetch the
>> >>>     bounding box.  On very complex boards, this can take a while.
>> Getting
>> >>>     the bounding box is called fairly often so this can add up.  I
>> don't see
>> >>>     any reason to recalculate the bounding box on every get bounding
>> box
>> >>>     call.  If the current bounding box behavior is broken, then it
>> should be
>> >>>     fixed.  I don't see any reason to get rid of the caching method.
>> If you
>> >>>     are operating outside of the normal methods for adding and/or
>> editing
>> >>>     board objects that prevents the correct bounding box from being
>> >>>     calculated, that is your fault and you need to fix your code
>> >>>     accordingly.
>> >>>
>> >>>     >
>> >>>     > Just by looking at the code, I noticed that the autorouter calls
>> >>>     > BOARD::GetBoundingBox() frequently, but I could not see much
>> >>>     difference
>> >>>     > with caching disabled. Likely, the routing algorithm takes
>> >>>     significantly
>> >>>     > more time than the bounding box calculations.
>> >>>     >
>> >>>     > Personally I would completely remove m_BoundingBox field
>> instead of
>> >>>     > making it mutable. Also, I have noticed there are a few places
>> >>>     where the
>> >>>     > bounding box is overridden with SetBoundingBox(). It seems to
>> me a bit
>> >>>     > dubious, as bounding box should depend solely on the items
>> >>>     belonging to
>> >>>     > the board. I attach a patch to show what I would change. Any
>> comments,
>> >>>     > especially from Wayne & Jean-Pierre?
>> >>>     >
>> >>>     > Regards,
>> >>>     > Orson
>> >>>     >
>> >>>     > On 02/23/2017 01:49 PM, Jon Evans wrote:
>> >>>     >> Hi Orson,
>> >>>     >>
>> >>>     >> Here's an updated patch with the changes you requested.  The
>> only
>> >>>     issue is,
>> >>>     >> without some kind of caching, I had to change the call sites
>> that
>> >>>     were
>> >>>     >> interested in the board bounding box with edges only, so the
>> >>>     patch has
>> >>>     >> grown in scope.  Let me know if this looks better.
>> >>>     >>
>> >>>     >> Best,
>> >>>     >> Jon
>> >>>     >>
>> >>>     >> On Thu, Feb 23, 2017 at 4:17 AM, Maciej Sumiński
>> >>>     <maciej.suminski@xxxxxxx <mailto:maciej.suminski@xxxxxxx>>
>> >>>     >> wrote:
>> >>>     >>
>> >>>     >>> Hi Jon,
>> >>>     >>>
>> >>>     >>> I really like the generic approach in the zoom methods. This
>> part I
>> >>>     >>> would merge instantly, but there is an issue with caching the
>> board
>> >>>     >>> bounding box. It does not take into account that items already
>> >>>     added to
>> >>>     >>> board may change their position and affect the bounding box.
>> I would
>> >>>     >>> remove caching completely, what do you think?
>> >>>     >>>
>> >>>     >>> If you are going to modify the patch, would you rename
>> boardBBox in
>> >>>     >>> COMMON_TOOLS::ZoomFitScreen() to bbox or anything that is not
>> >>>     related to
>> >>>     >>> board? Thank you in advance.
>> >>>     >>>
>> >>>     >>> Regards,
>> >>>     >>> Orson
>> >>>     >>>
>> >>>     >>> On 02/23/2017 05:34 AM, Jon Evans wrote:
>> >>>     >>>> Hi all,
>> >>>     >>>>
>> >>>     >>>> This patch finishes off the refactor I did a few days ago, by
>> >>>     enabling
>> >>>     >>>> ZoomFitScreen to work without knowledge of the BOARD class.
>> >>>     >>>>
>> >>>     >>>> In order to make this work, I changed the way GetBoundingBox
>> and
>> >>>     >>>> ComputeBoundingBox work so that the call sites of
>> >>>     GetBoundingBox don't
>> >>>     >>> have
>> >>>     >>>> to also call ComputeBoundingBox if they don't need to use the
>> >>>     >>>> aBoardEdgesOnly flag.
>> >>>     >>>>
>> >>>     >>>> Those with good knowledge of BOARD should review this to make
>> >>>     sure I
>> >>>     >>> caught
>> >>>     >>>> all the instances where we should mark the bounding box as
>> >>>     needing to be
>> >>>     >>>> re-computed.
>> >>>     >>>>
>> >>>     >>>> Best,
>> >>>     >>>> Jon
>> >>>     >>>>
>> >>>     >>>>
>> >>>     >>>>
>> >>>     >>>> _______________________________________________
>> >>>     >>>> Mailing list: https://launchpad.net/~kicad-developers
>> >>>     <https://launchpad.net/~kicad-developers>
>> >>>     >>>> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
>> >>>     <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
>> >>>     >>>> Unsubscribe : https://launchpad.net/~kicad-developers
>> >>>     <https://launchpad.net/~kicad-developers>
>> >>>     >>>> More help   : https://help.launchpad.net/ListHelp
>> >>>     <https://help.launchpad.net/ListHelp>
>> >>>     >>>>
>> >>>     >>>
>> >>>     >>>
>> >>>     >>>
>> >>>     >>> _______________________________________________
>> >>>     >>> Mailing list: https://launchpad.net/~kicad-developers
>> >>>     <https://launchpad.net/~kicad-developers>
>> >>>     >>> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
>> >>>     <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
>> >>>     >>> Unsubscribe : https://launchpad.net/~kicad-developers
>> >>>     <https://launchpad.net/~kicad-developers>
>> >>>     >>> More help   : https://help.launchpad.net/ListHelp
>> >>>     <https://help.launchpad.net/ListHelp>
>> >>>     >>>
>> >>>     >>>
>> >>>     >>
>> >>>     >
>> >>>     >
>> >>>     >
>> >>>     > _______________________________________________
>> >>>     > Mailing list: https://launchpad.net/~kicad-developers
>> >>>     <https://launchpad.net/~kicad-developers>
>> >>>     > Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
>> >>>     <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
>> >>>     > Unsubscribe : https://launchpad.net/~kicad-developers
>> >>>     <https://launchpad.net/~kicad-developers>
>> >>>     > More help   : https://help.launchpad.net/ListHelp
>> >>>     <https://help.launchpad.net/ListHelp>
>> >>>     >
>> >>>
>> >>>
>> >>>     _______________________________________________
>> >>>     Mailing list: https://launchpad.net/~kicad-developers
>> >>>     <https://launchpad.net/~kicad-developers>
>> >>>     Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
>> >>>     <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
>> >>>     Unsubscribe : https://launchpad.net/~kicad-developers
>> >>>     <https://launchpad.net/~kicad-developers>
>> >>>     More help   : https://help.launchpad.net/ListHelp
>> >>>     <https://help.launchpad.net/ListHelp>
>> >>>
>> >>>
>> >>
>> >>
>> >> _______________________________________________
>> >> Mailing list: https://launchpad.net/~kicad-developers
>> >> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
>> >> Unsubscribe : https://launchpad.net/~kicad-developers
>> >> More help   : https://help.launchpad.net/ListHelp
>> >>
>> >
>> >
>> >
>> >
>> > _______________________________________________
>> > Mailing list: https://launchpad.net/~kicad-developers
>> > Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
>> > Unsubscribe : https://launchpad.net/~kicad-developers
>> > More help   : https://help.launchpad.net/ListHelp
>> >
>>
>>
>> _______________________________________________
>> Mailing list: https://launchpad.net/~kicad-developers
>> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
>> Unsubscribe : https://launchpad.net/~kicad-developers
>> More help   : https://help.launchpad.net/ListHelp
>>
>
>