FS#6472 - Various link graph performance improvements

Attached to Project: OpenTTD
Opened by J G Rennison (JGR) - Wednesday, 25 May 2016, 20:08 GMT
Type Patch
Category Core
Status New
Assigned To No-one
Operating System All
Severity Low
Priority Normal
Reported Version trunk
Due in Version Undecided
Due Date Undecided
Percent Complete 0%
Votes 0
Private No


Cache the calculated value of CapacityAnnotation.

This is because CapacityAnnotation::Comparator::operator()
was appearing at the top of profiler output due to regenerating
the annotation value on every comparison when performing a set operation.

Replace three uses of std::list with std::deque/vector.

Use a flat vector instead of a map in FlowEdgeIterator.

This reduced the cost of Dijkstra<CapacityAnnotation> by approx. 25%,
in a test profiling.

Use a fixed array instead of a map for link refresher cargo capacities.

In MultiCommodityFlow::Dijkstra:
Store annotation and node ID in set key, to reduce ptr derefs on sort.
Store the set iterator in the node, for faster erasing during forks.
This task depends upon

Comment by fonsinchen (fonsinchen) - Sunday, 19 June 2016, 11:04 GMT
About 2:

Conceptually the thing in demands.cpp is a queue, and in fact std::queue does the right thing here, with a more descriptive interface. As we're changing it already we might just fix it properly. For the RefitList we could also use a vector, as it only does append and iterate, just like the StationSupplyList.

Comment by J G Rennison (JGR) - Monday, 20 June 2016, 23:07 GMT
Agreed. Those seem like good ideas. I'll put up an updated patch soon.
Comment by J G Rennison (JGR) - Sunday, 03 July 2016, 21:54 GMT
I've attached an update of patch 2, which changes NodeList to a std::queue, and RefitList to a std::vector.

As this then conflicts with patch 4 due to an adjacent edit, I've uploaded an update which does not conflict.
Comment by fonsinchen (fonsinchen) - Sunday, 10 July 2016, 12:43 GMT
I think #5 can be simplified. There is no reason to nest 3 templates there. Why not just change the annotations to contain a path rather than inherit it and cache whatever they need? Maybe I'll manage to fix it today. I've committed the other four with slight changes.