The International Simutrans Forum

 

Author Topic: Patch to search_route*  (Read 212 times)

0 Members and 1 Guest are viewing this topic.

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4614
  • Languages: EN, DE, AT
Patch to search_route*
« on: January 10, 2020, 08:25:39 PM »
Here is a small patch for the search-route routines. Instead of a binary heap, it uses a combination of a fixed-length array of vectors and a binary heap as open list. In the fixed length array (the buckets) the nodes will be inserted
in the list with index equal to the node weight. If the weight is larger than the array length, the node goes into the heap. Surprisingly, the rather small length of the arrary is sufficient: the patch currently uses 200. The largest game i have available is the op-game, which uses the array up to length ~160.

This reduces the runtime of search_route by 10%. The additional memory consumption is negligible.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Devotee
  • *
  • Posts: 19078
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Patch to search_route*
« Reply #1 on: January 10, 2020, 08:55:23 PM »
This is very interesting. I wonder how well that this would work multi-threadedly* as has been done in Extended since late 2016?

* I.e. multiple vehicles route searching at once concurrently with some other processes in step(), but not doing anything with the route found other than saving the resulting route until the next single threaded step.

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4614
  • Languages: EN, DE, AT
Re: Patch to search_route*
« Reply #2 on: January 11, 2020, 10:10:04 AM »
This is only used for cargo routing. I did not investigate vehicle routing.

The patch introduces a new data structure that replaces binary heap. It works under the assumption that the maximal weight of an inserted node is somehow small. For cargo routing in standard, max weight does not exceed 200 even for very large games.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Devotee
  • *
  • Posts: 19078
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Patch to search_route*
« Reply #3 on: January 11, 2020, 11:15:17 AM »
Thank you - that is a helpful clarification. This will not be relevant to Extended, in that case, as Extended uses an entirely different routing system for passengers, mail and goods.

However, there may be some benefit to Standard in multi-threading some of the routing code (both for cargo and for vehicles; both are multi-threaded in Extended) as this can make a noticeable difference to performance in a larger game.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9633
  • Languages: De,EN,JP
Re: Patch to search_route*
« Reply #4 on: January 12, 2020, 01:32:37 PM »
Since Extended uses precalculated tables (or did this change?) for the actual routing (which is then very cheap), the building of the tables is the critical part. It is about if everything is connected to everything or just a much smaller fraction is accessible. In the latter case, (which standard's assumption) the routing allows for much faster reaction to schedule changes, but the cost of routing increases with network size each time a new packet enters. In Extended, the cost is upfront in building the tables, but then routing is cheap.

Back on topic: Since goods routing is one of the remaining biggest effort in Simutrans Standard, improvement is a very good idea. Since most route searches are a few hops, I am surprised there is so much improvement. Please submit.