The International Simutrans Forum

 

Author Topic: [Fixes 3.14] calculate_paths() and others  (Read 3341 times)

0 Members and 1 Guest are viewing this topic.

knightly

  • Guest
[Fixes 3.14] calculate_paths() and others
« on: June 01, 2009, 06:31:49 PM »
Hi James,

I have made a few commits to my forked branch. Please check them out when you have time. Following are the info regarding the commits :

(1) K6 :

I have made some changes to refresh_routing(). Particularly, I have changed calls to this function on old schedules to use path_option 0, since only reshedule[c] needs to be set. Besides, paths_timestamp[c] are set simply to 0 to save processing time.


(2) K7 :

In the following code from calculate_paths() :

Quote
      if(current_node->link != NULL && paths[category].put(current_node->halt, current_node))
      {
         // Track the path back to get the next transfer from this halt
         path* track_node = current_node;
         for(uint8 depth = 0; depth <= 255; depth ++)
         {
            if(track_node->halt.is_bound())
            {

               if(track_node->link->link == NULL)
               {
                  path* tmp = paths[category].get(current_node->halt);
                  tmp->halt = track_node->halt;
                  break;
               }
            }
            
            track_node = track_node->link;
         }

         if(!paths[category].get(current_node->halt)->halt.is_bound())
         {
            // Remove bad paths (transfer depth too great, so aborted)
            delete paths[category].remove(current_node->halt);
         }
      }
      
      INT_CHECK( "simhalt 1694" );

      if(current_node->halt == goal)
      {
         // Abort the search early if the goal stop is found.
         // Because the open list is stored on the heap, the search
         // can be resumed where it left off if another goal, as yet
         // not found, is searched for, unless the index is stale.

         if(open_list[category].empty())
         {
            search_complete[category] = true;
         }
         return;
      }   
      
      current_node = NULL;
   }

For the code in blue, origin path nodes are not added to path[c], so when paths are flushed afterwards, they are not recycled, causing memory leak.

For the code in green, now that halt in path will become the next immediate transfer, it is not necessary to do back-tracing anymore.

For the code in orange, this is now wrong -- you are comparing the next immediate transfer against the goal halt. This will cause exhaustive search if the goal is not also the next transfer halt. I guess this is an important cause of increased lagginess when Colin compares v3.8 and v3.14, as many searches become unnecessarily exhaustive.


(3) K8 :

Actually, there is another more problematic bug related to the merge :

Quote
      if(current_node->link != NULL)
      {
         previous_connexion = current_node->link->halt->get_connexions(category)->get(current_node->halt);
         if(previous_connexion != NULL)
         {
            previous_best_line = previous_connexion->best_line;
            previous_best_convoy = previous_connexion->best_convoy;
         }
      }

The above code now always try to fetch a connexion object between the immediate transfer halt and the current halt, which in some cases ends up in failure. The result is, more unnecessary new nodes are added to open_list. I guess this also contribute to a minor extent to lagginess.

This problem is not easy to fix. If we search for the next transfer halt every time it is requested, it will not be efficient. Deferring such search will still cause the same problem in some cases. So, do we need to add an extra variable for current_halt? The size of a halthandle_t object is only 2 bytes, but since we are using freelist, any increase are in multiples of 4.

So I think, maybe adding previous_best_line and previous_best_convoy is better -- we can save the processing time of going back to predecessor node to look them up. But since these 2 variables are useful only during searching, I want to get rid of them after the path is stored in paths[c]. The link variable too is no longer useful after path data are determined. So, I add back path_node to store all info used during the search, but store path objects (only contain transfer halt and journey time) in paths[c]. In that way, memory consumption is roughly the same as before, as the larger size of path_node is offset by the reduced size of path.


(4) K9 :

I have checked and confirmed that binary_heap_tpl only works with pointers. So, I added a function to that class to delete/recycle the objects referenced by the array of node pointers, to reduce the time of clearing open_list.

I also fixes some memory leaks, particularly for paths and open_list entries which are not recycled when a halt is deleted. This reduces the increase in memory consumption when reloading the same save game -- though there might still be other memory leaks.


(5) K10 :

Since lagginess persists, I have added some INT_CHECK() calls to step_passagiere() -- this function, together with the path-searching-related functions, probably consume the most processing time. As your implementation of step_passagiere() is much longer than in Simutrans Standard, a single INT_CHECK() call is likely to be insufficient.





As Colin and Dante continue to complain about lagginess, I am sure that you are now considering changing back to partial recalculation of paths/connexions again. But before you do so, please try out my patches above first, so that they can check to see if there is any significant improvement. Please also think about spreading recalculation further as suggested by Dwachs. If in the end, nothing can be done to resolve lagginess, please add an option in simuconf.tab (full / partial recalculation / monthly recalculation) so that players can choose. Actually, even for the 1982.sve that you recommended to me some time ago, I haven't experienced much lagginess after these fixes.
« Last Edit: June 01, 2009, 07:18:18 PM by Knightly »

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Fixes 3.14] calculate_paths() and others
« Reply #1 on: June 01, 2009, 09:48:44 PM »
Knightly,

thank you very much for your continued hard work on these patches - I very much appreciate it. I have merged in your code and tested it. I have noticed a significant improvement in the performance in the bi-monthly refresh of paths. However, I have found, after testing (following a lead from Dante), that the unresponsiveness occurs primarily after updating a line. That seems to persist even after your updates. Curiously, for reasons that I have yet to fathom, it does not occur when adding a new line, or placing down new stops (or adding a new line that serves new stops, even when some of those stops are public). I am not sure whether there is anything in that - perhaps there might be some issue with the code for updating lines? It seems odd to me that the performance should be uniquely affected by updating lines.

I found only a tiny amount of unresponsiveness after updating a line on Dante's saved game, but a significant amount in "1982", so that is probably a good test platform. I also notice, on "1982", that the amount of time before the game is responsive after it loads is a little faster with your latest fixes than it was before (even comparing a debug build with your fixes and a release build without them). The overall speed of the game (when fast-forwarded, measured by the time multiplier) is not, however, noticably changed. I have not noticed a very great difference in memory consumption overall.

So, overall, your latest changes seem to be a success - some further consideration needs to be given to the line updating issue, however. Thank you very much for your work so far :-)

Offline dantedarkstar

  • *
  • Posts: 98
Re: [Fixes 3.14] calculate_paths() and others
« Reply #2 on: June 01, 2009, 10:27:53 PM »
About adding new lines: the "lag" appears when you start a bus, not when you make a line. The same happens if you retire the last bus on the line. After all, inactive line is not counted for connections, right ?

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: [Fixes 3.14] calculate_paths() and others
« Reply #3 on: June 01, 2009, 11:22:45 PM »
This bug seems to be selective. I haven't come across it yet. Mind you I only have a couple of buses running.

James, I might email you my SVE so you can check it out on your computer. It's grown a lot since you last saw it. Hope that's ok?

Regards

Colin
PS: Can you PM me your email address I removed it after the last one. (I respect peoples privacy)
« Last Edit: June 01, 2009, 11:27:56 PM by Colin »

knightly

  • Guest
Re: [Fixes 3.14] calculate_paths() and others
« Reply #4 on: June 02, 2009, 09:40:59 AM »
James,


I have noticed a significant improvement in the performance in the bi-monthly refresh of paths.

The reason why bi-monthly refresh is better than when refresh_routing() is triggered, is because bi-monthly refresh does *not* trigger re-routing of existing ware packets. Given the vast amount of packets in 1982.sve, it is not surprising that the responsiveness is worse when full-scale re-routing is done.


However, I have found, after testing (following a lead from Dante), that the unresponsiveness occurs primarily after updating a line. That seems to persist even after your updates. Curiously, for reasons that I have yet to fathom, it does not occur when adding a new line, or placing down new stops (or adding a new line that serves new stops, even when some of those stops are public). I am not sure whether there is anything in that - perhaps there might be some issue with the code for updating lines? It seems odd to me that the performance should be uniquely affected by updating lines.

I guess adding new stops, or adding new lines alone (without also assigning convoys to the lines) will not trigger refresh_routing(). I have checked again, and there should be no problem with the code in refresh_routing() or with the relevant code for updating lines.


I found only a tiny amount of unresponsiveness after updating a line on Dante's saved game, but a significant amount in "1982", so that is probably a good test platform.

The principal reason is that, in 1982.sve, there is a horribly large amount of ware packets. For instance, one halt which has only 8,xxx total capacity has 12x,xxx pax and 7,xxx mail waiting, and the list of packets is horribly long. refresh_routing() will trigger re-routing of all existing ware packets, so this is just understandable to experience unresponsiveness.


I also notice, on "1982", that the amount of time before the game is responsive after it loads is a little faster with your latest fixes than it was before (even comparing a debug build with your fixes and a release build without them).

Actually, there is a problem with selective updating compared to simply calling welt->set_schedule_counter() :  I can see that at least simline_t::add_convoy() is called repeatedly when loading a save game, meaning that refresh_routing() will also be repeatedly triggered. This is not good, because refresh_routing() is not as trivial as a call to set_schedule_counter().


The overall speed of the game (when fast-forwarded, measured by the time multiplier) is not, however, noticably changed.

I agree that the speed during global refresh is still relatively low for large games like 1982.sve . However, before the fixes, the speed of 1982.sve in fast-forward mode went down to as low as 0.98 ; but now it's 6.xx, which is already a lot better. Besides, in large games, there are really a lot of things to calculate, and we cannot expect fast-forwarding can cut down much of the work load -- if you have to do a lot of things in a short time frame, it is just reasonable to be slow.


some further consideration needs to be given to the line updating issue, however.

I don't think there is any thing more I can do to fix/improve line updating, for there is really no problem with the code. Rather, I will try to see if I can revise the system of refresh mechanism.


Edit :

To make it easier to test and isolate the problem, I have compiled an unofficial GDI version with my fixes applied, based on v3.14.
Colin and Dante, please kindly download this and test it again. Many thanks!
« Last Edit: June 02, 2009, 10:07:54 AM by Knightly »

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Fixes 3.14] calculate_paths() and others
« Reply #5 on: June 02, 2009, 12:54:21 PM »
Colin,

as you will see, I have PMed you my e-mail address. I am most grateful for your offer of sending me your saved game, as it should be useful as a test platform.

Knightly,

interesting thoughts: thank you for your input :-) I think that I shall have to make instant re-routing optional given that there appears still to be a potential for significant unresponsiveness (albeit only in larger maps) even with the code as efficient as we can make it. I hope to have a simuconf.tab setting and a GUI button for it somewhere. This would mean a change to the major version number, however, as a change to simuconf.tab would require incrementing the save game version, and I do not want that to get out of synchronisation with the Simutrans-Experimental version number.

As to the special binary, perhaps it could be called something like 3.14a to avoid confusion?

Offline dantedarkstar

  • *
  • Posts: 98
Re: [Fixes 3.14] calculate_paths() and others
« Reply #6 on: June 02, 2009, 02:06:35 PM »
Maybe don't re-route packets after each update, but do it monthly ? This would make monthly freezes possibly longer, but since they usually happen less often than changing anything in the network, it should be a lot less inconvenient. And the update-lag would be significantly reduced, especially for large passenger networks.
If you snatch a bus from under passenger's nose in the middle of journey, they will just wait and they be very unhappy about that :) ("What the hell ?! Where's my bus !? It said in the schedule that...").
Does cargo have limited wait time ? It doesn't seem so, so it will just be "lost" until all the bureaucracy will re-route it correct way next month.
In general people don't know all the network changes all over the world, so delayed reactions might be actually somewhat realistic (I prefer such "friction" for the expanding transport empire than the "lag").

And I'll be testing the "Knightly nightly" immediately ;)

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Fixes 3.14] calculate_paths() and others
« Reply #7 on: June 02, 2009, 02:27:34 PM »
Dante,

I am planning to do what you suggest (more or less), but make it optional, so that players can choose between more GUI unresponsiveness and and a more up-to-date network, or less GUI unresponsiveness and a less up-to-date network.

As to cargo, only cargo with a speed bonus rating over zero has a limited wait time, and the limit is dependant on the speed bonus rating (the higher the rating, the lower the limit).

Offline dantedarkstar

  • *
  • Posts: 98
Re: [Fixes 3.14] calculate_paths() and others
« Reply #8 on: June 02, 2009, 02:34:24 PM »
That's great ! It would certainly allow you to have maximum efficiency when starting out and every passenger counts, and reduce lag as much as possible when you have huge network and are vomiting money anyway.


After testing the "Knightly nightly" I found out that the "lag" after line update is about HALF of the normal Simutrans-Experimental 3.14. On my own save, the lag became barely noticeable (on my comp).

I tested it also on the 1982 save and found out following:

after making the same modification (removing "Ashville Russian Church" stop (2nd from top) from "Ashville North" tram line), I had to wait:
about 10-12 seconds on normal Simutrans-Experimental-GDI 3.14
about 6-7 seconds on Knightly's 3.14 edition
after that time, the map scrolling finally worked again (r-button hold and movement), which I use to indicate that the "lag" finished.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Fixes 3.14] calculate_paths() and others
« Reply #9 on: June 02, 2009, 02:54:16 PM »
Dante,

thank you very much for your feedback! That is very useful as performance can differ substantially on different systems. Good to know that Knightly's improvements have made a difference :-)

knightly

  • Guest
Re: [Fixes 3.14] calculate_paths() and others
« Reply #10 on: June 02, 2009, 03:20:19 PM »
@ James

I think that I shall have to make instant re-routing optional given that there appears still to be a potential for significant unresponsiveness (albeit only in larger maps) even with the code as efficient as we can make it.

Thanks for adding an option so that I can choose full refresh -- you know how keen I am on that  :P

As to the special binary, perhaps it could be called something like 3.14a to avoid confusion?

I think we should not give my special compilation a version number. I have made it very clear that it is an unofficial version, and any unofficial version should not be given a version number. It is compiled only for the sake of ad hoc testing, and it is not a separate branch of ST EXP. :)


@ Dante

Many thanks for your testing. Your detailed report has been most helpful! ;)   BTW, "Knightly nightly" is really funny. :D
« Last Edit: June 02, 2009, 03:31:24 PM by Knightly »