Performance

Mar 22, 2011 at 11:23 AM

Hi,

First of all thanks for this nice project. It has huge potential.

I used the Simplex solver to visualize a database scheme, which works quite well. It's only a bit slow. It takes very long to optimize the viz. for let's say 100 nodes with 200 edges or so. I looked a bit through the code and saw that most time is spend in the solver where a lot of LINQ is used in the core algorithms and methods. Also unnecessary ToList conversations. I just refactored the method signatures a bit and removed the ToList conversations and got a speed up of 170%. 

LINQ is nice and I use it often, but it's not a good choice when it comes to performance critical parts. Loops and arrays are the fastest, then Lists<>. Unrolling loops, inlining methods and caching of property return values also bring a good speed up. Use structs (value types) instead of classes for simple types like vertex. Prefer to pass value types using ref to avoid copies. 

Do you plan to work on the performance of the Simplex solver or should I try a different method for the optimization of the graph?

Thanks!

 

- Rene Schulte

Coordinator
Mar 25, 2011 at 8:30 PM

Hello! Thanks for feedback. I have plans to implement Network Simplex instead of algebraic simplex. It should greatly improve perfomance. Optimizing loops and structures will be made also, but first of all simplex algorythm must be optimized. Much time is spent to find initial solution, but ther is some euristics to avoid this.