News:

The Forum Rules and Guidelines
Our forum has Rules and Guidelines. Please, be kind and read them ;).

Cargo routing performance improvement by caching

Started by Dwachs, August 10, 2017, 09:07:08 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Dwachs

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.

Ters

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.

Dwachs

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.

prissi

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?

Dwachs

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.