[Kicad-developers] Ratsnest for the GAL
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
[Kicad-developers] Building OpenSSL with CMake on Windows
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
Re: [Kicad-developers] Building OpenSSL with CMake on Windows
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 brian.sidebot...@gmail.com 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
Re: [Kicad-developers] Building OpenSSL with CMake on Windows
On 16 October 2013 12:04, Dick Hollenbeck d...@softplc.com 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
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 brian.sidebot...@gmail.com wrote: On 16 October 2013 12:04, Dick Hollenbeck d...@softplc.com 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
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] Ratsnest for the GAL
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 maciej.sumin...@cern.ch 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-galhttps://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-**developershttps://launchpad.net/~kicad-developers Post to : kicad-developers@lists.**launchpad.netkicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-**developershttps://launchpad.net/~kicad-developers More help : https://help.launchpad.net/**ListHelphttps://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
On Oct 16, 2013 7:53 AM, Dick Hollenbeck 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. Since you probably want the pool anchored on the container On Oct 16, 2013 4:10 AM, Maciej Sumiński maciej.sumin...@cern.ch 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
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
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 d...@softplc.com wrote: On Oct 16, 2013 7:53 AM, Dick Hollenbeck 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. Since you probably want the pool anchored on the container On Oct 16, 2013 4:10 AM, Maciej Sumiński maciej.sumin...@cern.ch 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
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
On 10/16/2013 02:59 PM, Dick Hollenbeck wrote: On Oct 16, 2013 7:53 AM, Dick Hollenbeck d...@softplc.com 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
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
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 d...@softplc.com 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. 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
