The International Simutrans Forum

 

Author Topic: Thoughts on optimisation and multithreading  (Read 886 times)

0 Members and 1 Guest are viewing this topic.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9438
  • Languages: De,EN,JP
Thoughts on optimisation and multithreading
« on: December 14, 2012, 02:43:27 PM »
You know, any opration which not changes the game state could be run concurrently. I played around a lot of sync_step, but in the end it was more pain than gain. A possible model could be deferred pathfinding, i.e. a second thread runs only for pathfinding and , if tasks are not finished within xxx steps (lets say four) then pathfinding is done immediately. That might help especially with many ships.



Mod note: split from this topic as these discussions are not specific to the particular issue of private car routes.
« Last Edit: December 16, 2012, 07:57:30 PM by jamespetts »

Offline sdog

  • Devotee
  • *
  • Posts: 2039
Re: Thoughts on optimisation and multithreading
« Reply #1 on: December 14, 2012, 09:42:24 PM »
Code: [Select]
That might help especially with many ships.
Couldn't the pathfinding for ships be made more efficient by storing the paths for a line? Re-search only after certain intervals or if the path is blocked?

The scenario where it is so problematic has very large numbers of boats in a line, thus they are starting in very quick succession. (Especially important with experimentals limited wait/travel times for pax, frequent service requires many convoys on long routes.)

The pathfinding system is already quite robust with regard to blockages, since the path-finding is only done at every start of a section of a trip.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9438
  • Languages: De,EN,JP
Re: Thoughts on optimisation and multithreading
« Reply #2 on: December 14, 2012, 11:35:04 PM »
That would work for blockades. But then ships will never ever search a better path when new channels were opened ...

One could of course argue that those are donje once per line and month. Line clears the cached routes once a month, and if a ships asked the line for a route, the line will calc the route and cache it. (If the ship has no line, it just have to do it every time. But those are unlikely traveling on big numbers on the maps.)

But ships route finding is very much optimized, I spent a long long time on this. Before ships need waypoints for more than 100 tiles of open water and could take seconds for a simple route around a corner.

Offline sdog

  • Devotee
  • *
  • Posts: 2039
Re: Thoughts on optimisation and multithreading
« Reply #3 on: December 15, 2012, 12:08:06 AM »
That would work for blockades. But then ships will never ever search a better path when new channels were opened ...

One could of course argue that those are donje once per line and month. Line clears the cached routes once a month, and if a ships asked the line for a route, the line will calc the route and cache it. (If the ship has no line, it just have to do it every time. But those are unlikely traveling on big numbers on the maps.)
That was excactly what i wanted to suggest.
Two modifications, i think you meant also, but i write them explicitly:  When starting check if the route has been calculated in the last month, calculate new route when not done. I think this is more sensible then calculating new routes fixed every month. It also keeps it from the start of the month lag, caused by lots of calculations and checks at that time.

This automatically makes it active only if there is a large number of ships in the line.

User action (closing schedule dialogue) causes re-calculation of route regardless of wether there was a check last month or not.

Since ships are on their way often enough for months, they don't take shorter routes like a newly dug canal anyway, without direct user action. There wouldn't be a major change in useability.

This could be restricted to ships only, since there is no way-choose sign. Such way choose signs would make things quite a bit more complicated, as the start tile would be different.

Quote
But ships route finding is very much optimized, I spent a long long time on this. Before ships need waypoints for more than 100 tiles of open water and could take seconds for a simple route around a corner.
I've noticed it, as a player. Just compare it to the pain in openTTD. It was one of the features that persuaded me to abandon openTTD for simutrans. I did not know who was responsible for it so far. Now that i know:

Excellent work, i've been very impressed by it and it works like a charm.