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

[core] Implement SmallVector using std::vector #7165

Merged
merged 25 commits into from Mar 26, 2019
Merged

Conversation

M3Henry
Copy link
Contributor

@M3Henry M3Henry commented Feb 3, 2019

This the starting point for removing SmallVector by making SmallVector an adapter type.
This replaces #6817.

The public and protected interface to SmallVector are unchanged
SmallVector now requires that items be default constructible
This isn't an issue since some contained items were previously created
uninitialized.

Temporary default constructors are added to the following structs

  • SmallPair
  • SmallStackItem
  • GRFPresence

Where vector is required, transition immediately to std::vector
to avoid returning proxy object references.

@LordAro
Copy link
Member

LordAro commented Feb 4, 2019

I'd be interested to see if there's any significant differences in compile and/or run time for this method

@M3Henry
Copy link
Contributor Author

M3Henry commented Feb 4, 2019

Running make clean; /usr/bin/time -ao result.txt twice:

Old:

189.65user 11.06system 3:21.75elapsed 99%CPU (0avgtext+0avgdata 262996maxresident)k
0inputs+200152outputs (0major+6462169minor)pagefaults 0swaps
188.01user 11.27system 3:20.21elapsed 99%CPU (0avgtext+0avgdata 262928maxresident)k
0inputs+200136outputs (0major+6458952minor)pagefaults 0swaps

New:

209.38user 12.56system 3:42.99elapsed 99%CPU (0avgtext+0avgdata 288344maxresident)k
8176inputs+202184outputs (4major+7621408minor)pagefaults 0swaps
212.88user 12.72system 3:46.66elapsed 99%CPU (0avgtext+0avgdata 288408maxresident)k
0inputs+202184outputs (0major+7622902minor)pagefaults 0swaps

So 11% slower compilation, not surprising seeing as this is an intermediate shim. I expect this to improve once SmallVector is removed completely, as only one template will be instantiated per use, rather than two.

Run time performance would hopefully be better, owing to exponential growth of storage rather than linear growth. The loss of realloc may counter that to some degree. But if trivially relocatable types (P1144R1) are approved for C++20 then that would be resolved automatically.

Also explicit template instantiation should yield good results.

@PeterN
Copy link
Member

PeterN commented Feb 4, 2019

Run-time performance is far more relevant that compile-time.

@M3Henry
Copy link
Contributor Author

M3Henry commented Feb 5, 2019

Is there a benchmark for that?

@Eddi-z
Copy link
Contributor

Eddi-z commented Feb 5, 2019

you used to be able to run a non-gui benchmark with "-v null:ticks=1000"

time ./openttd -c path_to_config -v null:ticks=1000 -m null -s null -g path_to_savegame

@M3Henry
Copy link
Contributor Author

M3Henry commented Feb 5, 2019

Running for 10000 ticks I got:

Real -2.1%
User -0.7%
Sys -12.3%

So a boost in all categories!

std::vector

real	0m1.005s
user	0m1.068s
sys	0m0.085s

real	0m1.014s
user	0m1.094s
sys	0m0.056s

real	0m1.010s
user	0m1.122s
sys	0m0.024s

real	0m1.008s
user	0m1.116s
sys	0m0.036s
--------------------
real	0m1.00925s
user	0m1.10000s
sys	0m0.05025s
====================

SmallVector

real	0m1.023s
user	0m1.103s
sys	0m0.064s

real	0m1.033s
user	0m1.095s
sys	0m0.072s

real	0m1.028s
user	0m1.117s
sys	0m0.044s

real	0m1.040s
user	0m1.114s
sys	0m0.049s
--------------------
real	0m1.03100s
user	0m1.10725s
sys	0m0.05730s

@TrueBrain
Copy link
Member

Possibly it might be good to run for more ticks; comparing two results based on runs of ~1 second means you are comparing heavily in the noise ;) Longer runtimes will give more comparable results :)

@glx22
Copy link
Contributor

glx22 commented Feb 10, 2019

It seems you forgot to replace some Clear() instances (as implied by the CI failure)

@glx22
Copy link
Contributor

glx22 commented Feb 10, 2019

And now it fails on Length()

Edit: missed the forced push ;)
Edit2: ok OS specific files are hard to check locally :)

@PeterN
Copy link
Member

PeterN commented Feb 10, 2019

This is turning into a somewhat large PR. Might it make sense to start individually converting some uses of SmallVector directly to std::vector in stages instead?

@LordAro
Copy link
Member

LordAro commented Feb 10, 2019

This was discussed in the previous version of the PR. I thought it made more sense to do the change in individual commits, but the same PR

@PeterN
Copy link
Member

PeterN commented Feb 10, 2019

I didn't say mean split into separate PRs, I'm suggesting to switch individual uses of SmallVector to std::vector directly instead of changing the SmallVector type, then hopefully that can just be dropped.

And yes, I realise doing this means throwing away a large portion of this PR :-(

EDIT: Reviewing individual commits is a must for this PR!

@LordAro
Copy link
Member

LordAro commented Feb 10, 2019

Maybe, maybe not. I figured that reviewing method a -> method b (lots of single line changes) was easier to review than object a -> object b (lots of bigger changes), hence the move to make SmallVector a subclass of std::vector

src/core/smallvec_type.hpp Outdated Show resolved Hide resolved
src/newgrf.cpp Outdated Show resolved Hide resolved
Copy link
Member

@PeterN PeterN left a comment

Choose a reason for hiding this comment

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

I'm happy with this, as it stands. There may be minor tweaks here and there but they can be done in master.

@PeterN PeterN merged commit 03ca319 into OpenTTD:master Mar 26, 2019
stormcone added a commit to stormcone/OpenTTD that referenced this pull request Mar 26, 2019
stormcone added a commit to stormcone/OpenTTD that referenced this pull request Mar 27, 2019
michicc added a commit to stormcone/OpenTTD that referenced this pull request Mar 27, 2019
…ng types.

Const and non-const Find() have different return types.
LordAro pushed a commit that referenced this pull request Mar 28, 2019
Const and non-const Find() have different return types.
PeterN added a commit to PeterN/OpenTTD that referenced this pull request Apr 27, 2019
stormcone added a commit to stormcone/OpenTTD that referenced this pull request May 26, 2019
…et relative' button crashes the game.

The 'offs_start_map' is a 'SmallMap', so its own 'Erase' function should be called instead of the underlying vector's 'erase' function.
And fix a "typo". :)
douiwby pushed a commit to douiwby/OpenTTD that referenced this pull request Apr 16, 2020
douiwby pushed a commit to douiwby/OpenTTD that referenced this pull request Apr 16, 2020
douiwby pushed a commit to douiwby/OpenTTD that referenced this pull request Apr 16, 2020
…ng types.

Const and non-const Find() have different return types.
douiwby pushed a commit to douiwby/OpenTTD that referenced this pull request Apr 16, 2020
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

7 participants