April 23rd 2011
I've been working on this algorithm now for 11 solid months, and it is nearing initial completion with fairly decent results.
The algorithm traverses and evaluates paths and does nodal analysis. I will focus for today on the path analysis since the nodal analysis has not changed much in the past few months.
Path analysis is tricky on a cyclic graph, because you somehow have to keep from running into an infinite loop and you also need to keep from running into memory overflows.
Even after that, however, efficiency is a major concern. The number of paths grows 2^n minimally where n is the number of if statements. Given loops it grows even faster as every loop that the path potentially can follow must be accounted for.
I now have the algorithm down to approximately 2 and a half minutes for over 1 million paths, and I think I can get it under 1 minute due to a large inefficiency I recently discovered but have not been able to implement a fix to yet.
The inefficiencies so far have mostly been in loops. Valgrind, specifically callgrind, is an excellent tool for finding bottlenecks in your program. I found that the culprit for 80+% of the time was an algorithm to determine whether two paths were disjoint except for the end of one connecting to the front of the other. Fixing this required realizing that I was already keeping track of the information for another purpose but hadn't realized it could be used in both situations.
The program builds paths from discovered branching statements. These get stored in a data structure along with the paths they lead to. This caused an immense speed up when I first programmed it. I found that in building the paths I had all the information I needed because in order to build them I had to avoid loops specific to that path. This information could be stored and thus I was able to check those potential loop nodes against nodes in the proceeding path extensions (the paths are built from branch to branch).
I realized late yesterday as I was working that I was doing the same operation too many times, and that I
I've been working on this algorithm now for 11 solid months, and it is nearing initial completion with fairly decent results.
The algorithm traverses and evaluates paths and does nodal analysis. I will focus for today on the path analysis since the nodal analysis has not changed much in the past few months.
Path analysis is tricky on a cyclic graph, because you somehow have to keep from running into an infinite loop and you also need to keep from running into memory overflows.
Even after that, however, efficiency is a major concern. The number of paths grows 2^n minimally where n is the number of if statements. Given loops it grows even faster as every loop that the path potentially can follow must be accounted for.
I now have the algorithm down to approximately 2 and a half minutes for over 1 million paths, and I think I can get it under 1 minute due to a large inefficiency I recently discovered but have not been able to implement a fix to yet.
The inefficiencies so far have mostly been in loops. Valgrind, specifically callgrind, is an excellent tool for finding bottlenecks in your program. I found that the culprit for 80+% of the time was an algorithm to determine whether two paths were disjoint except for the end of one connecting to the front of the other. Fixing this required realizing that I was already keeping track of the information for another purpose but hadn't realized it could be used in both situations.
The program builds paths from discovered branching statements. These get stored in a data structure along with the paths they lead to. This caused an immense speed up when I first programmed it. I found that in building the paths I had all the information I needed because in order to build them I had to avoid loops specific to that path. This information could be stored and thus I was able to check those potential loop nodes against nodes in the proceeding path extensions (the paths are built from branch to branch).
I realized late yesterday as I was working that I was doing the same operation too many times, and that I
