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

Fix: Vehicle list windows did not update when this year's profit changed #8715

Merged
merged 1 commit into from Feb 28, 2021

Conversation

LordAro
Copy link
Member

@LordAro LordAro commented Feb 21, 2021

Motivation / Problem

#8575 (update commit message when merging)
584df54 introduced Vehicle groups, which cached age, this-year-profit & last-year-profit of the groups. These groups were not (and could not be) updated when the profit of the group changed, meaning that

Description

Remove caching from vehicle group object and recalculate it whenever required instead.

Was an awful lot less effort than finding all the places where vehicle profit changes and updating the relevant group object.

Limitations

Might slow things down for group-heavy games. Needs further testing with a game with such properties. Perhaps @btzy would like to test?

Checklist for review

Some things are not automated, and forgotten often. This list is a reminder for the reviewers.

  • The bug fix is important enough to be backported? (label: 'backport requested')
  • This PR affects the save game format? (label 'savegame upgrade')
  • This PR affects the GS/AI API? (label 'needs review: Script API')
    • ai_changelog.hpp, gs_changelog.hpp need updating.
    • The compatibility wrappers (compat_*.nut) need updating.
  • This PR affects the NewGRF API? (label 'needs review: NewGRF')

Remove caching from vehicle group object. and recalculate it whenever
required instead.
@btzy
Copy link
Contributor

btzy commented Feb 21, 2021

Thanks for this fix! I should be able to try it out maybe tomorrow. However, it appears that we're doing O(n log n) recalculations (because the comparator for std::sort is called that many times) when we could have done it in O(n) (by saving the calculations on each vehicle group into an auxilliary array just before doing the sort), I wonder if it is worth doing that instead?

@LordAro
Copy link
Member Author

LordAro commented Feb 21, 2021

Up to you. Doing less is always better, but it doesn't appear to have any great impact on an average game. Might be diminishing returns

@btzy
Copy link
Contributor

btzy commented Feb 21, 2021

Nevermind, it shouldn't matter at all, since each vehicle can only be in one vehicle group, so it works out to O(n log n), which is what we used to have when not using vehicle groups at all.

@btzy
Copy link
Contributor

btzy commented Feb 22, 2021

I tried some saves with around 200-500 buses and 20-70 groups, and it doesn't appear to be any slower than normal. Unfortunately, I don't have a save with 65535 vehicles to push it to the limit... but I would be fairly surprised if it was any slower because the time complexity works out to be the same as not grouping the vehicles at all.

const Vehicle *oldest = *std::max_element(this->vehicles_begin, this->vehicles_end, [](const Vehicle *v_a, const Vehicle *v_b) {
return v_a->age < v_b->age;
});
return oldest->age;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can the list be empty? Then "oldest" is an invalid iterator.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No, each vehicle group must have at least one vehicle, since they are formed by partitioning the list of vehicles into groups.

@TrueBrain TrueBrain added this to the 1.11.0 milestone Feb 27, 2021
@LordAro LordAro merged commit 6b8f9b5 into OpenTTD:master Feb 28, 2021
@LordAro LordAro deleted the group-view-uncache branch February 28, 2021 11:24
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

4 participants