Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Cargodist: various link graph performance improvements #6472

Closed
DorpsGek opened this issue May 25, 2016 · 9 comments
Closed

Cargodist: various link graph performance improvements #6472

DorpsGek opened this issue May 25, 2016 · 9 comments
Assignees
Labels
flyspray This issue is imported from FlySpray (https://bugs.openttd.org/) patch from FlySpray This issue is in fact a Patch, but imported from FlySrpay

Comments

@DorpsGek
Copy link
Member

JGR opened the ticket and wrote:

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 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.

Attachments

Reported version: trunk
Operating system: All


This issue was imported from FlySpray: https://bugs.openttd.org/task/6472
@DorpsGek
Copy link
Member Author

fonsinchen wrote:

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.


This comment was imported from FlySpray: https://bugs.openttd.org/task/6472#comment14218

@DorpsGek
Copy link
Member Author

JGR wrote:

Agreed. Those seem like good ideas. I'll put up an updated patch soon.


This comment was imported from FlySpray: https://bugs.openttd.org/task/6472#comment14222

@DorpsGek
Copy link
Member Author

DorpsGek commented Jul 3, 2016

JGR wrote:

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.

Attachments


This comment was imported from FlySpray: https://bugs.openttd.org/task/6472#comment14230

@DorpsGek
Copy link
Member Author

fonsinchen wrote:

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.


This comment was imported from FlySpray: https://bugs.openttd.org/task/6472#comment14232

@DorpsGek DorpsGek added Core flyspray This issue is imported from FlySpray (https://bugs.openttd.org/) patch from FlySpray This issue is in fact a Patch, but imported from FlySrpay labels Apr 7, 2018
@frosch123 frosch123 removed the Core label Apr 14, 2018
@andythenorth andythenorth added the stale Stale issues label Jan 5, 2019
@andythenorth
Copy link
Contributor

@JGRennison Thanks for this :) Looks like 4 out of 5 patches went in. For #5, there's been no activity on this for some time, and as it stands, it doesn't look likely that it will go any further. I'm closing it as we try to keep the issue count low for OpenTTD, it helps us focus on things that are important and fun. Feel free to discuss in irc or request re-opening if you disagree. Thanks for contributing!

@andythenorth
Copy link
Contributor

Actually @LordAro requested I re-open it. So eh.

@andythenorth andythenorth reopened this Jan 12, 2019
@andythenorth andythenorth removed the stale Stale issues label Jan 12, 2019
@JGRennison
Copy link
Contributor

When time permits I can look into re-doing the profiling/testing for patch 5.
I'm happy to submit a PR if the results look sufficiently worthwhile.

@LordAro
Copy link
Member

LordAro commented Feb 14, 2020

@JGRennison Did you ever manage to profiling this?

@JGRennison
Copy link
Contributor

@JGRennison Did you ever manage to profiling this?

I completely forgot about this unfortunately. I've since replaced that change with something else in my branch. I'm fine to just let it lapse. There are other areas of the linkgraph which are probably more fruitful to pursue.

@nielsmh nielsmh closed this as completed Feb 15, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
flyspray This issue is imported from FlySpray (https://bugs.openttd.org/) patch from FlySpray This issue is in fact a Patch, but imported from FlySrpay
Projects
None yet
Development

No branches or pull requests

6 participants