GNOME Bugzilla – Bug 134273
Very long time to link tasks as task links grow (2^n time)
Last modified: 2004-12-22 21:47:04 UTC
I have a project which is a nice stress test. It has around 108 tasks (Grouped into various indented/sub-indent tasks). Attached is a diagram explaining the test. I won't describe the exact sequence except that I remove all constraints and links (to make testing easier) and I then link together two summary tasks, the second of which has many other tasks which have links under it. The execution time doubles for every 5 tasks that are linked within the 2nd summary. Times below obviously vary per machine - its CPU bound and this is for a Celeron 500 (in a dual processor machine with Planner using just one CPU). Linked tasks (in a chain) -> Execution time 70 -> 6 seconds to add link 75 -> 10 80 -> 22 85 -> 54 sec etc etc 105 -> around 15 minutes to complete. Some sort of 2^n looping within mrp-task.c, mrp-task-manager.c and mrp-relation.c but too hard to look at what it is superficially. In conclusion the act of linking just two tasks can cause many minutes of execute time if there are many other existing tasks that are linked within a summary.
Created attachment 24372 [details] Diagram showing what was clicked.
Look at my diagarma and you'll see under the Pre-Sale Work summary task that the tasks are linked to each other Finish to Start - this is what you increase i.e. try with 80,85,90, 95 tasks etc, and then simply link the Pre-Sale Planning Work summary to Pre-Sale Work as a Finish to Start (either with my button or using the edit tasks dialog on Pre-Sale Work and adding a predecessor. Wait the 2^n time (well I think its 2^n as it sort of doubles for linear increase in linked tasks). You can use ddd to trace this i.e. ddd planner
Created attachment 24378 [details] The actual project that I'm using pre-set with lots of links. Set Pre-sale work to have a predecessor or Pre-planing work - wait 140 seconds to complete (500MegPC)
Thanks a lot for investigating this! I've been meaning to tackle this performance problam so it's great that you are helping out! I'll take a look at how to improve the situation.
It was because it was so darn hard adding lots of predecessors prior to the link button patch that people probably didn't set predecessors much ! I've added a sample project that anyone can play with as it has lots of pre-set links where one task is predecessor of the previous task. To create this normally via GUI dialog would take about an hour or more. Anyone can now test the performance issue even if they have the old planner version without the link button. There must be some optimisations to be done to get it down to linear time (n) (ideally) or n^2 time rather than the current 2^n time. Maybe we cheat in the short term and add a loop counter to the code and break out if the loop counter gets too high. Then the user is prompted to reduce the number of links in their project - at least they won't think its hung. That would be an easier cludge pending a code review.
Nah, I'd rather fix this right away :) At least I'd like to try!
Created attachment 25370 [details] Kcachegrind shows mrp_task.c : mrp_task_get_type called 30,000 times.
My first guess at the way to solve this would be: 1) really use the cached values instead of recalculating everything when something changes 2) short-cut so we only recalculate things that depend on values that have changed (the _get_type function is part of GObject casting macros by the way, it will ge run everytime there is a MRP_TASK ())
OK, I've investigated a bit further. It looks like the thing that takes time is checking that a link won't create a loop. It should be really easy to fix that function, it's just never been optimized. I'll take a look.
*** Bug 130307 has been marked as a duplicate of this bug. ***
This is more or less the same bug as http://bugzilla.gnome.org/show_bug.cgi?id=136044 and http://bugzilla.gnome.org/show_bug.cgi?id=139275 in the sense that they will all get fixed by fixing the scheduler.
The branch new-sched fixes this, but needs a bit more work.
Fixed in CVS (file new reports if the scheduler has bugs).
Looks good - its closed for me on retest. Now I'll progress crash testing further and see just exactly what will break Planner e.g. 1,000 tasks ?, 5,000 tasks ? 10,000 tasks ?...Its got to slow down at some time and just have to find out where that is. If its so big that no one sensible will hit that limit then we're safe. Will bugzilla what I find if its bad.