Page MenuHomeWildfire Games

Replace EntityMap, std::map, std::unordered_map and boost::unordered_map with an upgraded container
Needs ReviewPublic

Authored by wraitii on Jan 7 2019, 7:14 PM.

Details

Reviewers
None
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Summary

Implement a new container to replace most of our std::maps in ComponentManager.
This also replaces EntityMap in the RangeManager.

Performance characteristics are "fast everything but very fast iteration".

Test Plan

Code review. Performance review. Gameplay profiling.

Performance testing can be done off-line through this repo: https://github.com/wraitii/entities_temp

Diff Detail

Event Timeline

wraitii created this revision.Jan 7 2019, 7:14 PM
wraitii marked 2 inline comments as done.
wraitii added inline comments.
source/simulation2/system/EntityMap.h
0

Added compared to D8.

1

Added compared to D8: this was where it crashed otherwise.

Vulcan added a subscriber: Vulcan.Jan 7 2019, 7:35 PM

Successful build - Chance fights ever on the side of the prudent.

Link to build: https://jenkins.wildfiregames.com/job/differential/938/

wraitii updated this revision to Diff 7340.Jan 13 2019, 8:03 PM
wraitii retitled this revision from EntityMap rewrite redux to Replace EntityMap, std::map, std::unordered_map and boost::unordered_map with an upgraded container.
wraitii edited the summary of this revision. (Show Details)
wraitii edited the test plan for this revision. (Show Details)
wraitii added a reviewer: Restricted Owners Package.

Might as well make this revision useful. BOOM. Massive SFINAE for this new container.

I need to assess performance exactly as testing results have proven rather inconclusive. A short AI game (30 minutes) would indicate this is slightly faster than svn, but I'd like longer replays and more profiling. Furthermore, this might still be optimised.

This works so long as you use D1736. I've tested that the hashes are the same, and the tests have become quite extensive so I'm rather confident that it works, the question is "how fast".

Owners added a subscriber: Restricted Owners Package.Jan 13 2019, 8:03 PM

Build failure - The Moirai have given mortals hearts that can endure.

Linter detected issues:
Executing section Source...

source/simulation2/Simulation2.h
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/system/ComponentManager.h
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/system/ComponentManagerSerialization.cpp
|   1| /*·Copyright·(C)·2017·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2017"

source/tools/atlas/GameInterface/DeltaArray.h
|   1| /*·Copyright·(C)·2009·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2009"

source/simulation2/system/ComponentManager.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"
Executing section JS...
Executing section cli...

Link to build: https://jenkins.wildfiregames.com/job/differential/961/

wraitii updated this revision to Diff 7373.Jan 20 2019, 3:09 PM
wraitii edited the summary of this revision. (Show Details)
wraitii edited the test plan for this revision. (Show Details)

After much performance testing, I've found that this variant using a vector and a deque is probably the most efficient as a map replacement, as it performs extremely well for iteration and only about 3x as slowly as our current EntityMap for other operations (which remains faster than unordered_map). The code is also smaller and neater.

The trouble is that this changes hashes because the order, while deterministic, is no longer sorted by ID when iterating. Thus I can't test so straightforwardly. I'll try to get an idea of the overall effect on actual game results regardless.

Owners added a subscriber: Restricted Owners Package.Jan 20 2019, 3:09 PM

Build failure - The Moirai have given mortals hearts that can endure.

Linter detected issues:
Executing section Source...

source/simulation2/system/ComponentManagerSerialization.cpp
|   1| /*·Copyright·(C)·2017·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2017"

source/simulation2/system/ComponentManager.h
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/helpers/Selection.cpp
|   1| /*·Copyright·(C)·2017·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2017"

source/simulation2/Simulation2.h
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/system/Component.h
|   1| /*·Copyright·(C)·2017·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2017"

source/simulation2/system/ComponentManager.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/graphics/ObjectManager.cpp
|   1| /*·Copyright·(C)·2015·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2015"

source/tools/atlas/GameInterface/DeltaArray.h
|   1| /*·Copyright·(C)·2009·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2009"

source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp
|  33| #include·"graphics/Terrain.h"
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Invalid number of character ({) when these macros are defined: ''.

source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp
|  33| #include·"graphics/Terrain.h"
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Invalid number of character ({) when these macros are defined: 'MESSAGES_SKIP_STRUCTS'.

source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp
|  33| #include·"graphics/Terrain.h"
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Invalid number of character ({) when these macros are defined: '_MSC_VER'.
Executing section JS...
Executing section cli...

Link to build: https://jenkins.wildfiregames.com/job/differential/988/

Stan added a subscriber: Stan.Jan 20 2019, 7:08 PM

After much performance testing, I've found that this variant using a vector and a deque is probably the most efficient as a map replacement, as it performs extremely well for iteration and only about 3x as slowly as our current EntityMap for other operations (which remains faster than unordered_map). The code is also smaller and neater.

Will the fact that it is 3 times slower impact performance.

source/simulation2/system/ComponentManager.cpp
357

Can't a function called resize be implemented ?

750

Dead code ?

950

nullptr ?

Will the fact that it is 3 times slower impact performance.

It's faster at iteration, so it might work out. Might also not. Hard to tell really.

wraitii marked 2 inline comments as done.Jan 20 2019, 7:53 PM
wraitii added inline comments.
source/simulation2/system/ComponentManager.cpp
357

Could. TBH I think this can be removed in the new implementation. I need to clean this up slightly

950

Haven't changed what I didn't need to change, but this could go.

Stan added a comment.Apr 16 2019, 9:16 AM

Any news on this ?

This really needs to be used for components before I decide if it's worth merging, but as it changes hashes it's kind of annoying. I'll probably have to do some fancy tests at some point.

Stan added a comment.Apr 16 2019, 10:23 AM

This really needs to be used for components before I decide if it's worth merging, but as it changes hashes it's kind of annoying. I'll probably have to do some fancy tests at some point.

When you committed last time it wasn't ?

Can D1736 be committed ?

source/simulation2/helpers/SparseFlatMap.h
76

According to the tests in D1682 vector is kind of always faster than anything else.

In D1739#75035, @Stan wrote:

This really needs to be used for components before I decide if it's worth merging, but as it changes hashes it's kind of annoying. I'll probably have to do some fancy tests at some point.

When you committed last time it wasn't ?

It wasn't because the former version was just a rewrite, this is a rather large behaviour change that makes some of the existing code slower and some faster (hopefully overall the result is faster though).

Can D1736 be committed ?

Sure If I commit it without a review since it's got no comments/reviews.

source/simulation2/helpers/SparseFlatMap.h
76

I think I tested it and deque was faster for my use case as it handled sparsity better or something. Should re-test perf later though.

@fabio would be happy to add boost references if it really improves performance?
(So the question then would be does it, and is it sufficent performance benefit or just an experiment)

source/graphics/ObjectManager.cpp
201

CSimulation2::InterfaceListUnordered::iterator or std::pair<whatever, thatis>?
Can cmps be inlined (I didn't check whether that function would be called everytime then)?