Author Topic: Cargo routing performance improvement by caching  (Read 489 times)

0 Members and 1 Guest are viewing this topic.

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4273
  • Total likes: 193
  • Helpful: 149
  • Languages: EN, DE, AT
Cargo routing performance improvement by caching
« on: August 10, 2017, 09:07:08 AM »
The idea of this patch is to cache information about the shortest routes between transfer halts. Then during route search, only the shortest connection through the network of transfer halts has to be computed. This should speedup route search a lot during times when the transport network does not change.

The cache is filled when the traditional (Dijkstra) method is executed. Thus, the cache is gradually filled with very small overhead. Once the cache contains enough information, routing is done based on the cache, and Dijkstra is not called.

I ensured that the new method generates the same routes as the currently implemented one.

See attachment. Please test & comment.
Parsley, sage, rosemary, and maggikraut.

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4894
  • Total likes: 213
  • Helpful: 108
  • Languages: EN, NO
Re: Cargo routing performance improvement by caching
« Reply #1 on: August 10, 2017, 10:16:11 AM »
connected_comp_t has a count member variable. Confusingly, this is used by the is_empty member function, but the get_count member function returns something different. There might be a very good reason for this, but some better naming would then be a good idea.

Ownership of connected_comp_t isn't easy to follow. Looks like some form of reference counting, but unlike the one in COM (and std::shared_ptr, depending on how it is implemented and how you look at it), it is the one releasing references that has the responsibility of doing the deleting if necessary.

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4273
  • Total likes: 193
  • Helpful: 149
  • Languages: EN, DE, AT
Re: Cargo routing performance improvement by caching
« Reply #2 on: August 10, 2017, 01:14:32 PM »
Thanks for the comment. get_count was not used. I modified the class to call 'delete this' if the connected component is empty.
Parsley, sage, rosemary, and maggikraut.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 8830
  • Total likes: 324
  • Helpful: 229
  • Languages: De,EN,JP
Re: Cargo routing performance improvement by caching
« Reply #3 on: August 11, 2017, 02:18:17 AM »
In praxis, isn't there a good amount of caching done, by first trying to join ware with exisiting ware with the same destination? So the next transfer stop might have already a ceche, which are just ware already waiting there.

However, improvements, especially during rerouting after schedule schanges is certainly a clever idea. Did you try some benchmarks with the Honkong map?

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4273
  • Total likes: 193
  • Helpful: 149
  • Languages: EN, DE, AT
Re: Cargo routing performance improvement by caching
« Reply #4 on: August 11, 2017, 06:01:16 AM »
This caching still has an impact, even if there is some implicit caching in already existing and routed cargo.

During rerouting the cache will be build up, so I expect the performance gain during rerouting is not that large. Once the cache is build up, after rerouting, the improvement kicks in.

I did some benchmark for some large savegames from online plays. There, it pays off after the cache is filled to some extent. I did not try the Hongkong map. I also did not benchmark the rerouting separately.
Parsley, sage, rosemary, and maggikraut.