Re: [Kicad-developers] Ratsnest for the GAL

[Dick Hollenbeck]

On 10/16/2013 09:32 AM, Maciej Sumiński wrote:
> On 10/16/2013 02:59 PM, Dick Hollenbeck wrote:
>>
>> On Oct 16, 2013 7:53 AM, "Dick Hollenbeck" > > wrote:
>>  >
>>  > Looks promising, and super job on the presentation.
>>  >
>>  > Once you have it working, give some thought to using a special
>> purpose allocator for the elements of your container.   A memory pool
>> scheme, anchored on the container, might pay dividends if it removes the
>> size test for element allocations.  If you want the pool anchored on the
>> container, then overloading operator new is not best, but rather have a
>> container function do the allocations of its elements (from a pool it
>> owns.)
>>
>> Invariably
>> this means having an "in place" new operator for the element, not a
>> normal new operator overload.
>>
>> Such anchoring of pool in container is a separate decision from deciding
>> to use a fixed block allocator at all.  The fixed block allocator will
>> be worth it regardless of where the pool lives.  If you have to move
>> elements from one container to another, then anchoring the pool on the
>> container is not appropriate.  But you could then have a class that held
>> all your containers and a pool common to those containers.  I bring this
>> up because when instantiating hundreds of thousands of elements, memory
>> heap calls can be the bottleneck.
> 
> Thanks for the suggestion - I like the idea. I have briefly read the 
> boost::pool project page and initially it seems to be an easy solution 
> to the problem.


That is likely to be a *very* fast solution.  But keep in mind that if you are 
going to
delete the pool, since it is anchored in your ratsnest class, then you really 
don't need
element deletion, i.e. operator delete () on the container element.

This let's you trancend into *very very* fast, if you use it to your advantage. 
 The
problem with supporting pool::free( node ) is that it often requires that a 
pointer to the
big block from which the smaller fixed size block came be saved in the smaller 
block.
There may be other ways, look into this.  This additional pointer, if present,  
is
unnecessary if you don't worry about delete node, since the pool is going to be 
deleted
anyways.  The pointer is a way to figure out which big block to add the small 
fixed block
back into upon a free.  It is overhead you don't need.

Just saving that one pointer can be a big deal.  If the boost scheme is doing 
this, or if
its allocation function uses more than about 3 lines of code, then it may not 
be optimal.

Also, if your algorithm can work with pointers to the node, where moving nodes 
from one
container to another is really a matter of moving pointers, you will also pick 
up some speed.

What I envision is that when the pool would be inclined to return NULL, meaning 
the
current big block is exhausted, that it allocate another big block and then put 
that big
block onto a linked list of big blocks, singly linked is good enough.  After 
that, it puts
each small block within the big block onto another singly linked list, called a 
freelist.
 Each of the lists are held in the pool anchor.  The anchor destructor frees 
all the big
blocks.

operator delete () can be a dummy for the node element, I assume you will need 
one since
the container destructor may be calling it, and this happens before the pool 
destructor
hopefully.



 Especially that nodes are very likely going to be POD
> structures with fixed size.
> I guess it is already included in C++11 as the emplace() function that 
> is available for many std containers.
> 
> Regards,
> Orson
> 


___
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] Ratsnest for the GAL

[Dick Hollenbeck]

On 10/16/2013 09:24 AM, Maciej Sumiński wrote:
> On 10/16/2013 03:49 PM, Dick Hollenbeck wrote:
>> On 10/16/2013 04:09 AM, Maciej Sumiński wrote:
>>> It requires hashing function to be prepared (eg. using boost::hash), 
>>> possibly not very >
>> demanding on CPU cycles.
>>
>>
>> Sounds good.  A hashtable is probably the best bet.  Suggest adding it to 
>> hashtables.h
>> which is where we've put all the hashtables.
>>
>> Might this work?
>>
>> /// hash function for RATS_ELEM type
>> /// taken from: 
>> http://www.boost.org/doc/libs/1_53_0/libs/unordered/examples/fnv1.hpp
>> struct rats_hash
>> {
>>  std::size_t operator()( const RATS_ELEM& e ) const
>>  {
>>  std::size_t hash = 2166136261u;
>>
>>  hash ^= e.m_x;
>>  hash *= 16777619;
>>  hash ^= e.m_y;
>>  hash *= 16777619;   
>>  hash ^= e.m_layer;
>>  hash *= 16777619;   
>>  hash ^= e.m_net;
>>
>>  return hash;
>>  }
>> };
>>
>>
>> It puts in the members in reverse order of importance, m_net being most 
>> important.
>> I got this from my "const char*" hash function for which there is a URL 
>> reference in
>> hashtables.h
> 
> Surely, I will give it a try during tests. I was also considering using 
> netcodes for identification of nodes, but in the end I skipped them. Are 
> coordinates & layer number not enough to unambiguously determine a node?

In space, yes.  Good point.   No telling when you will get ahold of the BOARD 
however,
before or after the DRC.  A BOARD with two nets going to the same place (read 
point in
space) might get missed or confused.  This is a user error, but you need to be 
able to
identify all possibilities at that point in space, no?


m_net => was intended to be netcode, but it may not be needed as you suggest.




> 
> Regards,
> Orson
> .
> 


___
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] Ratsnest for the GAL

[Maciej Sumiński]

On 10/16/2013 02:59 PM, Dick Hollenbeck wrote:


On Oct 16, 2013 7:53 AM, "Dick Hollenbeck" mailto:d...@softplc.com>> wrote:
 >
 > Looks promising, and super job on the presentation.
 >
 > Once you have it working, give some thought to using a special
purpose allocator for the elements of your container.   A memory pool
scheme, anchored on the container, might pay dividends if it removes the
size test for element allocations.  If you want the pool anchored on the
container, then overloading operator new is not best, but rather have a
container function do the allocations of its elements (from a pool it
owns.)

Invariably
this means having an "in place" new operator for the element, not a
normal new operator overload.

Such anchoring of pool in container is a separate decision from deciding
to use a fixed block allocator at all.  The fixed block allocator will
be worth it regardless of where the pool lives.  If you have to move
elements from one container to another, then anchoring the pool on the
container is not appropriate.  But you could then have a class that held
all your containers and a pool common to those containers.  I bring this
up because when instantiating hundreds of thousands of elements, memory
heap calls can be the bottleneck.


Thanks for the suggestion - I like the idea. I have briefly read the 
boost::pool project page and initially it seems to be an easy solution 
to the problem. Especially that nodes are very likely going to be POD 
structures with fixed size.
I guess it is already included in C++11 as the emplace() function that 
is available for many std containers.


Regards,
Orson

___
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] Ratsnest for the GAL

[Maciej Sumiński]

On 10/16/2013 03:54 PM, Carl Poirier wrote:

FYI, in step 4 of the algorithm, I believe you wanted to refer to step 3:

*4. Remove edges with zero weight.*
The last step is to remove zero weight edges (as they are already
connected). The remaining edges make the ratsnest. This step could be
integrated with the step 3, as 0-weight edges could be filtered

Carl


You are right, thanks for catching this. Good that you can find careful 
readers here. It's already fixed.


Regards,
Orson


___
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] Ratsnest for the GAL

[Carl Poirier]

FYI, in step 4 of the algorithm, I believe you wanted to refer to step 3:

*4. Remove edges with zero weight.*
The last step is to remove zero weight edges (as they are already
connected). The remaining edges make the ratsnest. This step could be
integrated with the step 3, as 0-weight edges could be filtered

Carl


On Wed, Oct 16, 2013 at 8:59 AM, Dick Hollenbeck  wrote:

>
> On Oct 16, 2013 7:53 AM, "Dick Hollenbeck"  wrote:
> >
> > Looks promising, and super job on the presentation.
> >
> > Once you have it working, give some thought to using a special purpose
> allocator for the elements of your container.   A memory pool scheme,
> anchored on the container, might pay dividends if it removes the size test
> for element allocations.  If you want the pool anchored on the container,
> then overloading operator new is not best, but rather have a container
> function do the allocations of its elements (from a pool it owns.)
>
> Invariably
> this means having an "in place" new operator for the element, not a normal
> new operator overload.
>
>  Such anchoring of pool in container is a separate decision from deciding
> to use a fixed block allocator at all.  The fixed block allocator will be
> worth it regardless of where the pool lives.  If you have to move elements
> from one container to another, then anchoring the pool on the container is
> not appropriate.  But you could then have a class that held all your
> containers and a pool common to those containers.  I bring this up because
> when instantiating hundreds of thousands of elements, memory heap calls can
> be the bottleneck.
> >
> >
> > Since you probably want the pool anchored on the container
> >
> > On Oct 16, 2013 4:10 AM, "Maciej Sumiński" 
> wrote:
> >>
> >> Hi all,
> >>
> >> We need a ratsnest that works with the GAL, therefore I present to you
> the blueprints for that part:
> >> https://blueprints.launchpad.net/kicad/+spec/ratsnest-gal
> >>
> >> I have seen many great ideas appearing on the mailing list, that's why
> everyone is welcome to share thoughts. I believe it may lead to a
> better/faster/more functional implementation in the end.
> >> Regards,
> >> Orson
> >>
> >> ___
> >> 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
>
>
___
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] Ratsnest for the GAL

[Dick Hollenbeck]

On 10/16/2013 04:09 AM, Maciej Sumiński wrote:
> Hi all,
> 
> We need a ratsnest that works with the GAL, therefore I present to you 
> the blueprints for that part:
> https://blueprints.launchpad.net/kicad/+spec/ratsnest-gal
> 
> I have seen many great ideas appearing on the mailing list, that's why 
> everyone is welcome to share thoughts. I believe it may lead to a 
> better/faster/more functional implementation in the end.
> Regards,
> Orson
> 
> ___
> 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
> .
> 


> It requires hashing function to be prepared (eg. using boost::hash), possibly 
> not very >
demanding on CPU cycles.


Sounds good.  A hashtable is probably the best bet.  Suggest adding it to 
hashtables.h
which is where we've put all the hashtables.

Might this work?

/// hash function for RATS_ELEM type
/// taken from: 
http://www.boost.org/doc/libs/1_53_0/libs/unordered/examples/fnv1.hpp
struct rats_hash
{
std::size_t operator()( const RATS_ELEM& e ) const
{
std::size_t hash = 2166136261u;

hash ^= e.m_x;
hash *= 16777619;
hash ^= e.m_y;
hash *= 16777619;   
hash ^= e.m_layer;
hash *= 16777619;   
hash ^= e.m_net;

return hash;
}
};


It puts in the members in reverse order of importance, m_net being most 
important.
I got this from my "const char*" hash function for which there is a URL 
reference in
hashtables.h



___
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] Ratsnest for the GAL

[Dick Hollenbeck]

On Oct 16, 2013 7:53 AM, "Dick Hollenbeck"  wrote:
>
> Looks promising, and super job on the presentation.
>
> Once you have it working, give some thought to using a special purpose
allocator for the elements of your container.   A memory pool scheme,
anchored on the container, might pay dividends if it removes the size test
for element allocations.  If you want the pool anchored on the container,
then overloading operator new is not best, but rather have a container
function do the allocations of its elements (from a pool it owns.)

Invariably
this means having an "in place" new operator for the element, not a normal
new operator overload.

 Such anchoring of pool in container is a separate decision from deciding
to use a fixed block allocator at all.  The fixed block allocator will be
worth it regardless of where the pool lives.  If you have to move elements
from one container to another, then anchoring the pool on the container is
not appropriate.  But you could then have a class that held all your
containers and a pool common to those containers.  I bring this up because
when instantiating hundreds of thousands of elements, memory heap calls can
be the bottleneck.
>
>
> Since you probably want the pool anchored on the container
>
> On Oct 16, 2013 4:10 AM, "Maciej Sumiński" 
wrote:
>>
>> Hi all,
>>
>> We need a ratsnest that works with the GAL, therefore I present to you
the blueprints for that part:
>> https://blueprints.launchpad.net/kicad/+spec/ratsnest-gal
>>
>> I have seen many great ideas appearing on the mailing list, that's why
everyone is welcome to share thoughts. I believe it may lead to a
better/faster/more functional implementation in the end.
>> Regards,
>> Orson
>>
>> ___
>> 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

Re: [Kicad-developers] Ratsnest for the GAL

[Dick Hollenbeck]

Looks promising, and super job on the presentation.

Once you have it working, give some thought to using a special purpose
allocator for the elements of your container.   A memory pool scheme,
anchored on the container, might pay dividends if it removes the size test
for element allocations.  If you want the pool anchored on the container,
then overloading operator new is not best, but rather have a container
function do the allocations of its elements (from a pool it owns.)  Such
anchoring of pool in container is a separate decision from deciding to use
a fixed block allocator at all.  The fixed block allocator will be worth it
regardless of where the pool lives.  If you have to move elements from one
container to another, then anchoring the pool on the container is not
appropriate.  But you could then have a class that held all your containers
and a pool common to those containers.  I bring this up because when
instantiating hundreds of thousands of elements, memory heap calls can be
the bottleneck.


Since you probably want the pool anchored on the container
On Oct 16, 2013 4:10 AM, "Maciej Sumiński"  wrote:

> Hi all,
>
> We need a ratsnest that works with the GAL, therefore I present to you the
> blueprints for that part:
> https://blueprints.launchpad.**net/kicad/+spec/ratsnest-gal
>
> I have seen many great ideas appearing on the mailing list, that's why
> everyone is welcome to share thoughts. I believe it may lead to a
> better/faster/more functional implementation in the end.
> Regards,
> Orson
>
> __**_
> 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

Re: [Kicad-developers] Building OpenSSL with CMake on Windows

[Wayne Stambaugh]

On 10/16/2013 5:25 AM, Brian Sidebotham wrote:
> I patched the LuaDist CMake build system to work successfully on OpenSSL
> 1.0.1e.
> 
> Downloading, patching and building OpenSSL with CMake on Windows has an
> issue though (Doesn't everything being built on Windows!?)
> 
> The issue is that CMake, or more precisely libarchive used by CMake
> doesn't deal with symbolic links on Windows. Even 7z doesn't deal with
> them at all well either. The source archive for OpenSSL includes
> symbolic links in the include directory.
> 
> 7z outputs an ascii file with a line of text that is the relative path
> to the actual file. Not very useful, but this was at least parse-able
> and therefore fixable in CMake.
> 
> CMake -E tar fails with the message: "Cannot create \". There's plenty
> of information about this, and a fix is targeted at the 2.8.12
> release: http://www.cmake.org/Bug/print_bug_page.php?bug_id=13251
> 
> It may work okay under the MSYS shell actually - I've not tried as I
> don't have it.

I successfully built OpenSSL using the MSYS shell.  It does build, test,
and install properly for 32 bit builds.  It even installs ssleay32.dll
in /mingw/bin instead of /mingw/lib which is where most autotools
installs end up.

> 
> I'm unsure how we will get around this problem on Windows.
> 
> Best Regards,
> 
> Brian.
> 
> 
> ___
> 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

Re: [Kicad-developers] Building OpenSSL with CMake on Windows

[Dick Hollenbeck]

I assumed the doctored file was directly useable.  Since that is not the
case, would you prefer preparing a proper archive without symlinks? Then
put that someplace else?  In the case of avhttp I brought the zip into our
source tree, but I am viewing that as temporary until cmake has https
download capabilty. It does already, but we all use older versions.
On Oct 16, 2013 6:14 AM, "Brian Sidebotham" 
wrote:

> On 16 October 2013 12:04, Dick Hollenbeck  wrote:
>
>> On windows, can you try downloading from github the doctor-ed zip file
>> like the person in the bug report said?  Lets put that bug report URL in
>> our download script too as a comment.
>>
>
> Okay, I will do that.
>
> The zip file is awkward. It simply has nothing in place of the symbolic
> links, so the include directory is empty. I can modify the cmake scripts to
> populate it when it doesn't exist, or the patch can contain the include
> files. In the latter case the patch sits around 1.5Mb!
>
> I think I'll do the magic in the CMake script to populate the include
> directory if it is empty, and our patch step will apply the CMake files
> only. I'll add the bug report URL into our download_openssl.cmake too. It's
> a shame, it just makes a neat External_Add into a mess of if( MINGW ) crap.
>
> Ideally I wanted this CMake build system to work on top of the .tar.gz so
> it could be a common build step for all platforms.
>
> Best Regards,
>
> Brian.
>
>
___
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] Building OpenSSL with CMake on Windows

[Brian Sidebotham]

On 16 October 2013 12:04, Dick Hollenbeck  wrote:

> On windows, can you try downloading from github the doctor-ed zip file
> like the person in the bug report said?  Lets put that bug report URL in
> our download script too as a comment.
>

Okay, I will do that.

The zip file is awkward. It simply has nothing in place of the symbolic
links, so the include directory is empty. I can modify the cmake scripts to
populate it when it doesn't exist, or the patch can contain the include
files. In the latter case the patch sits around 1.5Mb!

I think I'll do the magic in the CMake script to populate the include
directory if it is empty, and our patch step will apply the CMake files
only. I'll add the bug report URL into our download_openssl.cmake too. It's
a shame, it just makes a neat External_Add into a mess of if( MINGW ) crap.

Ideally I wanted this CMake build system to work on top of the .tar.gz so
it could be a common build step for all platforms.

Best Regards,

Brian.
___
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] Building OpenSSL with CMake on Windows

[Dick Hollenbeck]

On windows, can you try downloading from github the doctor-ed zip file like
the person in the bug report said?  Lets put that bug report URL in our
download script too as a comment.
 On Oct 16, 2013 4:26 AM, "Brian Sidebotham" 
wrote:

> I patched the LuaDist CMake build system to work successfully on OpenSSL
> 1.0.1e.
>
> Downloading, patching and building OpenSSL with CMake on Windows has an
> issue though (Doesn't everything being built on Windows!?)
>
> The issue is that CMake, or more precisely libarchive used by CMake
> doesn't deal with symbolic links on Windows. Even 7z doesn't deal with them
> at all well either. The source archive for OpenSSL includes symbolic links
> in the include directory.
>
> 7z outputs an ascii file with a line of text that is the relative path to
> the actual file. Not very useful, but this was at least parse-able and
> therefore fixable in CMake.
>
> CMake -E tar fails with the message: "Cannot create \". There's plenty of
> information about this, and a fix is targeted at the 2.8.12 release:
> http://www.cmake.org/Bug/print_bug_page.php?bug_id=13251
>
> It may work okay under the MSYS shell actually - I've not tried as I don't
> have it.
>
> I'm unsure how we will get around this problem on Windows.
>
> Best Regards,
>
> Brian.
>
> ___
> 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] Building OpenSSL with CMake on Windows

[Brian Sidebotham]

I patched the LuaDist CMake build system to work successfully on OpenSSL
1.0.1e.

Downloading, patching and building OpenSSL with CMake on Windows has an
issue though (Doesn't everything being built on Windows!?)

The issue is that CMake, or more precisely libarchive used by CMake doesn't
deal with symbolic links on Windows. Even 7z doesn't deal with them at all
well either. The source archive for OpenSSL includes symbolic links in the
include directory.

7z outputs an ascii file with a line of text that is the relative path to
the actual file. Not very useful, but this was at least parse-able and
therefore fixable in CMake.

CMake -E tar fails with the message: "Cannot create \". There's plenty of
information about this, and a fix is targeted at the 2.8.12 release:
http://www.cmake.org/Bug/print_bug_page.php?bug_id=13251

It may work okay under the MSYS shell actually - I've not tried as I don't
have it.

I'm unsure how we will get around this problem on Windows.

Best Regards,

Brian.
___
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] Ratsnest for the GAL

[Maciej Sumiński]

Hi all,

We need a ratsnest that works with the GAL, therefore I present to you 
the blueprints for that part:

https://blueprints.launchpad.net/kicad/+spec/ratsnest-gal

I have seen many great ideas appearing on the mailing list, that's why 
everyone is welcome to share thoughts. I believe it may lead to a 
better/faster/more functional implementation in the end.

Regards,
Orson

___
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