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

Comments

@DorpsGek
Copy link

@DorpsGek DorpsGek commented May 25, 2016

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

This comment has been minimized.

Copy link
Author

@DorpsGek DorpsGek commented Jun 19, 2016

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

This comment has been minimized.

Copy link
Author

@DorpsGek DorpsGek commented Jun 21, 2016

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

This comment has been minimized.

Copy link
Author

@DorpsGek 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

This comment has been minimized.

Copy link
Author

@DorpsGek DorpsGek commented Jul 10, 2016

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
@andythenorth

This comment has been minimized.

Copy link
Contributor

@andythenorth andythenorth commented Jan 12, 2019

@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

This comment has been minimized.

Copy link
Contributor

@andythenorth andythenorth commented Jan 12, 2019

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

@JGRennison

This comment has been minimized.

Copy link
Contributor

@JGRennison JGRennison commented Jan 13, 2019

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

This comment has been minimized.

Copy link
Member

@LordAro LordAro commented Feb 14, 2020

@JGRennison Did you ever manage to profiling this?

@JGRennison

This comment has been minimized.

Copy link
Contributor

@JGRennison JGRennison commented Feb 15, 2020

@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 Feb 15, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants
You can’t perform that action at this time.