Finding the bottleneck

Hi! It's been a long time since I last posted anything...

Lately I have been doing some scripting (my first large script), and I find that it can be a bit slow. I'm sure it is because it's poorly written so I have been investigating into performance issues trying to find the weak link. The script is written in python but the question would extend to Grasshopper too.

My question is how can I find out which processes (either from python for Rhino or from Grasshopper components) are done in O(1) is constant runtime, O(n) linearly, or O(n²) quadratic time and so on.

Thanks!

Replies to This Discussion

Permalink Reply by David Rutten on August 15, 2013 at 12:00pm

Hi Jesus,

runtime-complexity measures are theoretical measures. Basically, you should be able to see whether an algorithm is O(1), O(N), O(N log N), O(N²) etc. just by looking at at. I can only do this for the simplest cases, I have no formal training in computer science and algorithm design.

However more important than the runtime complexity is the actual time it takes to run a piece of code. To do this you have to measure how long bits of your script take. A good way to do so is the stopwatch class. Measure the time between two lines of code using the stopwatch and see if it's sort of what you expected or way more or way less. You can then narrow down your search by adding more fine-grained stopwatch measures in between slow code. Eventually you should be able to narrow it down to a single line, loop or function call.

Once you've found a piece of code that runs very slow, you can maybe ask for specific tips on how to optimize it, but the response for Python questions isn't as good as for VB/C# I'm afraid.

David Rutten

david@mcneel.com

Tirol, Austria

Permalink Reply by Jesus Galvez on August 15, 2013 at 2:51pm

Hey David,

I thought it took quite a bit of experience to be able to know analytically the complexity of a process. Programming issues always seem more difficult to me than they really are.

Yes, I have read of using a timer, and also profiling tools. But I was wondering if the complexity rhino's processes were listed somewhere for amusement of the unenlightened.

Best

Permalink Reply by David Rutten on August 16, 2013 at 2:17am

They are not listed. Also complexity is not the whole story. First off it only tells you how much slower an algorithm gets as you make it operate on a larger data set. It doesn't tell you how long each 'tick' takes. It could well be that an O(log N) algorithm takes longer than an O(N²) algorithm for all realistic cases. The only guarantee is that eventually (nobody knows when) the former will become quicker than the latter, but it may take unrealistically large inputs before that happens.

Then there's best-case and worst-case scenarios. Sorting is a good example. Different sorting algorithms have different complexities and QuickSort is usually the fastest. However, if your original data-set is already -almost- sorted, then there are better options than QuickSort.

I think all you should care about is the actual runtime rather than the theoretical runtime. And the only way to figure that out is to measure it.

David Rutten

david@mcneel.com

Tirol, Austria

Permalink Reply by Jesus Galvez on August 16, 2013 at 2:45pm

Hi David,

the following is a bit off topic and just to report a couple of things.

well after talking a bit with djordje I got interested in Rhinocommon. It turns out my script was running so slow mostly because I used a mix of rhinoscriptsyntax methods to do things which could easily be achieved with Rhinocommon. For example at one point I had to get the adjacent faces to each face in a mesh. The way I did it with rhinoscriptsyntax was to first get the facecount, then the faceindexes, then the vertices shared by each face, then the faces shared by each vertex, and finally doing some set intersections! Turns out I could do it with Rhinocommon in one step.

As a consequence I managed to speed things up (for that step) by an order of magnitude! If I apply the same practice throughout the script I might be able to speed the whole thing by an order of magnitude.

RSS