kicad-developers team mailing list archive

[Carl Poirier <carl.poirier.2@xxxxxxxxx>]

I'm glad you like it. You did most of the work by eliminating the statics
in the triangulator.

I have not tested it under any other platform than Linux, but it's supposed
to work under MSVC++ as well.


On Fri, Jan 31, 2014 at 12:01 PM, Maciej Sumiński
<maciej.suminski@xxxxxxx>wrote:

> Hi Carl,
>
> Great job! I have just tested your patch and I confirm 2x boost on my
> machine as well. To tell the truth, I consider this a big speedup -
> particularly that you made it with just a few lines of code.
> RN_DATA::Recalculate() is run every time when there are changes on the
> board (e.g. items are moved/rotated/etc.) - it checks which nets where
> modified and updates the ratsnest for them.
> Speeding up the computation while parts are moved is obviously desired,
> but a bit harder to obtain, as GAL drawing functions are not thread-safe
> and it's not that easy to make them so. The main reason is that all items
> to be drawn are saved in a common buffer, so that has to be synchronized ->
> I expect a very little boost, if any. On the other hand, this type of
> ratsnest is not as demanding as the one you have accelerated in terms of
> CPU cycles.
> Thank you for the efforts. I will propose your changes for merging next
> week, together with some new features related to the ratsnest and tools.
>
> Regards,
> Orson
>
>
> On 01/31/2014 04:17 PM, Carl Poirier wrote:
>
>> Hi Maciej,
>>
>> Your last changes allow a complete independence of the loop iterations
>> in RN_DATA::Recalculate( int aNet ).
>>
>> I have almost a 2x speedup on a Core i7-4770 with the very simple
>> parallelization in the attached patch. I was expecting more, though.
>> There seems to be a bottleneck somewhere. I have a question, however.
>> Did you want to speedup the computation when you move the part? From
>> what I see, RN_DATA::Recalculate( int aNet ) is run only when the user
>> loads the board. Am I missing out on something?
>>
>> BTW, I've included in the patch some output to measure computation time,
>> which obviously is not meant to be committed. I have also added the
>> required build flag at the top of the CMakeLists.txt, because I don't
>> know exactly where it should go in it.
>>
>> Carl
>>
>>
>> On Tue, Jan 28, 2014 at 4:51 AM, Maciej Sumiński
>> <maciej.suminski@xxxxxxx <mailto:maciej.suminski@xxxxxxx>> wrote:
>>
>>     Hi Jean-Pierre,
>>
>>     I am done with the changes that would let me rely on the net codes
>>     in other parts of code. I did my best to perform tests and put
>>     comments to each commit, so they could be easier to understand and
>>     verify.
>>     Could you please have a look at the lp:~cern-kicad/kicad/netnames
>>     branch? If you think the proposed changes do not break anything, I
>>     would be grateful for merging the branch. Thank you in advance.
>>
>>     Regards,
>>     Orson
>>
>>     On 01/11/2014 05:31 PM, jp charras wrote:
>>
>>         Le 10/01/2014 18:35, Maciej Sumiński a écrit :
>>
>>
>>             On 01/09/2014 04:51 PM, jp charras wrote:
>>
>>                 Le 09/01/2014 11:22, Tomasz Wlostowski a écrit :
>>
>>                     On 01/08/2014 04:39 PM, jp charras wrote:
>>
>>                         Tracks do not store the net name but just the
>>                         net code, because they
>>
>>             are
>>
>>                         expected to be connected to pads which store
>>                         this info.
>>                         (this is the reason tracks and vias not
>>                         connected to a pad lose their
>>                         net after loading a board, or reading a netlist)
>>                         Therefore, after loading a board, or reading a
>>                         netlist, the track net
>>                         code should be initialized, but you have to
>>                         store this net name in
>>
>>             pads.
>>
>>                         (Of course, one can use an other way to store
>>                         net names, and an other
>>                         way to calculate net codes)
>>
>>
>>                     Hi Jean-Pierre,
>>
>>                     I see another point in modifying the net assignment
>>                     mechanism. If we
>>                     allow tracks/vias to retain net names and propagate
>>                     them from the pads
>>                     only when the schematic netlist has changed (not
>>                     every time the board is
>>                     loaded), it would also fix the infamous zone
>>                     stitching issue...
>>
>>                     Regards,
>>                     Tom
>>
>>
>>
>>                 Stitching vias and generally speaking not connected (to
>>                 a pad) items
>>                 (stitching vias, usual vias and tracks) create an other
>>                 problem than
>>                 retaining the net name.
>>
>>                 Retaining the net name of items not connected to a pad
>>                 (or a zone) items
>>                 is easy to fix (I already received a patch to do that).
>>
>>                 But the major issue is:
>>                 if the net names are retained in not connected (to a
>>                 pad) items, all
>>                 track ends and vias should be included in the ratsnest
>>                 generation.
>>                 Otherwise, we will have not connected vias and/or not
>>                 connected copper
>>                 zone areas (floating copper islands).
>>                 This is the only one reason stitching vias do not exist
>>                 in Pcbnew.
>>
>>                 Therefore fixing stitching vias issue is:
>>                 1 - finish and validate (this is the more important step
>>                 toward
>>                 stitching vias) the new ratsnest algorithm which takes
>>                 in account
>>                 pad+vias+track ends: mainly for very complex boards, see
>>                 if it is fast
>>                 enough.
>>
>>
>>             This is done by the ratsnest algorithm we added for the GAL
>>             (it is
>>             currently available in the testing branch). I have to admit
>>             that it
>>             probably is slower, but it is hard to keep the performance
>>             when amount
>>             of data for computation increases. The toughest test case I
>>             have by hand
>>             is the board that I recommended for testing the GAL
>>             (http://www.ohwr.org/__attachments/download/2187/wrs.
>> __kicad_pcb
>>             <http://www.ohwr.org/attachments/download/2187/wrs.kicad_pcb
>> >),
>>
>>             when you
>>
>>             drag the biggest IC in the middle, as it contains the
>>             greatest number of
>>             nets connected. After being dropped you may observe a freeze
>>             for a short
>>             time, it is the ratsnest algorithm going - we have to decide
>>             if it is
>>             acceptable.
>>
>>
>>         wrs.kicad_pcb is a decent board for tests.
>>
>>         The GAL ratsnest shown when moving a large footprint is very
>>         fast, no
>>         problem.
>>         (I tested also an other large board, and the ratsnest is also
>> fast)
>>
>>
>>                 The current ratsnest algorithm is very fast for 6000
>>                 pads (50 ms on my
>>                 computer).
>>                 What happen for 10x to 20x more (roughly 6000 pads +
>>                 30000 tracks (2
>>                 point) and 3000 vias for instance)
>>                 2 - after this, Retaining the net name of items not
>>                 connected.
>>                 And be sure the calculation time to know if 2 items are
>>                 connected by a
>>                 zone area is fast. Currently, this is 90% of calculation
>>                 time.
>>                 Because stitching vias will create a *lot* of items
>>                 connected by zones,
>>                 the calculation time in a very important criteria.
>>
>>
>>             We take it into account during the ratsnest calculation. I
>>             agree, it
>>             takes the biggest amount of time, but still on a decent
>>             hardware is
>>             acceptable (at least in my opinion, I would like to know
>>             other views).
>>
>>
>>         The current GAL ratsnest calculation is fast.
>>         Just keep in mind this is to find connections by copper areas
>>         which are
>>         time consuming.
>>
>>         I do not know if you are using my code for this, or a new code
>>         you wrote.
>>
>>         If it is my code, I am using an usual algorithm to determine if
>>         a via,
>>         pad or track end is inside a copper polygon.
>>         I am thinking it could be optimized to be faster (for instance
>>         considering the fact most of large copper polygon areas are
>>         built mainly
>>         from very small segments, and have very few long lines.)
>>
>>
>>                 3 - add tools to change items net names, when a net name
>>                 has changed in
>>                 schematic (for instance AGND changed to GND) (easy,
>>                 obviously, but
>>
>>             needed)
>>
>>             I think this could be handled easily if net names were kept in
>>             NETINFO_ITEM and D_PAD stored only net code or a pointer to
>> the
>>             appropriate data.
>>
>>
>>         This is certainly easy, but must be done...
>>
>>
>>                 I know the ratsnest need to be rebuild only for the
>>                 modified net (this
>>                 is also currently the case).
>>                 But the full ratsnet need to be fully rebuild, for
>>                 instance when
>>                 existing copper zones are modified (when creating/moving
>>                 a via, for
>>                 instance).
>>                 This is frequently the case, for complex boards.
>>
>>
>>             Until now, when I was not aware of the fact that net codes
>>             are a subject
>>             to change - I indexed all items by their net codes and if
>>             anything was
>>             modified, I checked its netcode and recalculated this. This
>>             also applies
>>             to zones, vias and tracks. This is one of reasons why I
>>             wanted to keep
>>             net codes constant during a single run time.
>>
>>
>>         Net codes are subject to change only after reading a netlist.
>>         Adding new net name is not allowed in pad edit dialog, and there
>>         is no
>>         reason to add a new net name in a board, outside the schematic.
>>
>>
>>                 In Altium, you need to deactivate (shelve) copper
>>                 polygons to be able to
>>                 work on you boards when the calculation time is too
>> long...
>>
>>
>>             I did not think of this, but actually it is a good hint to
>>             reduce
>>             computation time if user wants to do so.
>>
>>
>>         It is a good hint only for calculation time.
>>         When you deactivate a copper pour, (this is *exactly* like when
>> you
>>         remove the zone filling in Pcbnew) the corresponding ratnest is
>>         no more
>>         usable (you do not know anymore what is actually connected, and
>>         what do
>>         you connect), and this is very bad for the user.
>>         Power planes and split planes are other (poor) tricks to try to
>>         reduce
>>         the calculation time.
>>         But from my point of view, planes are poor features, because
>>         they are
>>         not (by far) as good as true polygons.
>>         The idea behind these planes is just to forbid tracks on these
>>         planes to
>>         avoid connection calculations (hard to call it "a good idea": in
>> the
>>         better case this is just an idea).
>>
>>             I already have the first changes proposal. As they are
>>             related to the
>>             KiCad's core, it is very important to me if you could assess
>>             if they are
>>             suitable to commit before I move on. If you have some spare
>>             time, please
>>             have a look at the lp:~cern-kicad/kicad/netnames branch.
>>             If in your opinion they do not break anything, the next step
>>             I wanted to
>>             do is to remove m_Netname/m_ShortNetname fields, move
>>             GetNetname()/GetShortNetname() to BOARD_CONNECTED_ITEM and
>>             make them use
>>             net names stored in NETINFO_ITEMs.
>>
>>
>>         I am thinking it should break nothing.
>>         But do not forget to keep a trace of the origin of net names:
>> those
>>         which are in netlist (in schematic) and those from existing
>>         items not
>>         connected to a pad (currently, only the zones, but could be also
>> not
>>         connected vias and track segments) which have net names not found
>> in
>>         netlist.
>>         We need to display a DRC error, and to be able to change the non
>>         existent net names, or to delete corresponding items.
>>
>>
>>             Regards,
>>             Orson
>>
>>
>>         Thanks for you work.
>>
>>
>>
>>     _________________________________________________
>>     Mailing list: https://launchpad.net/~kicad-__developers
>>     <https://launchpad.net/~kicad-developers>
>>     Post to     : kicad-developers@lists.__launchpad.net
>>     <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>
>>
>>
>>
>