kicad-developers team mailing list archive

[Maciej Sumiński <maciej.suminski@xxxxxxx>]

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
>

Attachment: signature.asc
Description: OpenPGP digital signature