kicad-developers team mailing list archive

[Jon Evans <jon@xxxxxxxxxxxxx>]

Wayne, Orson's latest patch is basically Option 2 but implemented another
way.  Can you check it out and let us know if you are OK merging it as-is,
or if we should change the implementation to be more like what I described?

Thanks,
Jon

On Wed, Mar 1, 2017 at 8:43 AM, Wayne Stambaugh <stambaughw@xxxxxxxxx>
wrote:

> Option 2 seems fine.  It may be easier to just add an option argument to
> the existing GetBoundingBox() function to either return the cached
> bounding box or recalculate the bounding box on demand rather than
> create a different function for the cached vs. uncached version.
>
> On 3/1/2017 2:51 AM, Maciej Sumiński wrote:
> > Wayne, what do you think? If it is acceptable, then I would like to
> > merge the patches. I should not judge my code, as I might be tempted to
> > consider it a good solution.
> >
> > In case my proposal to cache the bounding box in autorouter code is not
> > approved, then I would say #2 would do the job.
> >
> > Cheers,
> > Orson
> >
> > On 03/01/2017 01:23 AM, Jon Evans wrote:
> >> 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
> >>>>
> >>>
> >>>
> >>
> >>
> >>
> >> _______________________________________________
> >> 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
>