Page MenuHomeWildfire Games

Introduce a replacement container for EntityMap, std::map, std::unordered_map and boost::unordered_map
Changes PlannedPublic

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

Details

Reviewers
None
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Trac Tickets
#4347
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

Repository
rP 0 A.D. Public Repository
Branch
D1739_entmap
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 8808
Build 14445: Vulcan BuildJenkins
Build 14444: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
wraitii marked 2 inline comments as done.Jan 7 2019, 7:15 PM
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
349

Can't a function called resize be implemented ?

770

Dead code ?

990

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
349

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

990

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
77

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
77

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–202

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

wraitii updated this revision to Diff 9220.Aug 4 2019, 6:47 PM

Quick rebase, and also replace the std::map for static/unit shapes.

Been trying some "overall" profiling to no real avail on some contained cases such combat demonstrations (huge). I think the raw overhead is somewhat dwarfed by the other costs.

Vulcan added a comment.Aug 4 2019, 6:50 PM

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

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/304/display/redirect

elexis added a comment.Aug 4 2019, 9:32 PM

(only some linting)

source/simulation2/helpers/SparseFlatMap.h
32

The goal for this class, not for 0 A.D.

54

I wonder if this class has to be implemented in the header (for performance or template class requirement reasons)

64

Sometimes key_type is used, other times T is used. template<class key_type, class mapped_type> or using T and V, or KEY_T and VALUE_T consistently would remove the indirection and ambiguousity.
I remember Vladislav speaking of a preference for using over typedef. Also below it uses using.

98

I was directed to not align a line after code, because if someone adds one line that needs a different alignment, all the other lines have to be changed as well; whereas using always only 1 space character means that such a systematic issue won't occur.

101

The macro appears avoidable by putting it into a container that stores either one or two of those.

115

The previous code didn't implement copying, there is a macro NONCOPYABLE to do the same (deleting the copy constructor and copy assignment operator).
If one wants to support copies but wants to also get complaints by the compiler if one unintentionally copies things, then the class can remain NONCOPYABLE but have the copy in a static function with a different name.
I didn't check whether the copy ctor was inevitable.

193

What type is this?

219

What type is this?

238

Using emplace_back would throw a compiler warning if the value would end up being copied (force construct in place), whereas push_back accepts copies.

298

What type is this?

source/simulation2/system/ComponentManager.cpp
225
using MessageIt = std::map<MessageTypeId, std::vector<ComponentTypeId> >::iterator;
for (MessageIt it =

or perhaps there is EntityComponentMap.iterator_type_something

307

Doesn't this copy the pair? (also const?)

1067

pointer operator ->?

source/simulation2/tests/test_SparseFlatMap.h
2

9

source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp
1086–1087

What type does this have?

wraitii planned changes to this revision.Aug 5 2019, 2:59 PM

I'll do a pass over the autos' and the code.
I remember why I've used std::deque: I need a container that doesn't move items when expanding.

Performance wise, except for inserting/deleting which is about 3x worse, I've again tested this to be rather similar to EntityMap, better at iterating when sparsity becomes a factor of 2 or 3... I need to check what we realistically get in-game.

I think I could do an optimisation for when pointers are stored which might actually be interesting for the component manager.

source/simulation2/helpers/SparseFlatMap.h
32

for this class in the context of 0 A.D. would be more accurate

54

?
It's already in a header? Being a templated class I don't have much choice anyways.

64

Yeah I need a consistency pass for this.

98

This true. In this case though these are the only four possible combinations (const, non-const, secondary, non-secondary), and I feel like it really improves readability?

101

?

The macro is mostly here to help with readability for SFINAE

193

keys_container&, will change

238

mh, yes, vaguely seems like I had a compiling issue to use push_back here. Will check

298

this is a std::pair<T, V>, which doesn't feel much more informative.

source/simulation2/system/ComponentManager.cpp
307

Might be a compilation issue with some of the weirdness I've added, but perhaps. Might be trivial enough that copying over reference is rather equivalent.

1067

probably regex-modifying gone wrong

wraitii updated this revision to Diff 9292.Aug 11 2019, 6:44 PM
wraitii retitled this revision from Replace EntityMap, std::map, std::unordered_map and boost::unordered_map with an upgraded container to Introduce a replacement container for EntityMap, std::map, std::unordered_map and boost::unordered_map.

I've done much profiling, and much testing, and here's a CRTP-ed version (comes in single key and dual-key mode).
Overall this container should be similar to EntityMap performance wise, bit slower at inserting but bit faster in other contexts and it works out similarly.

It's at least as good as unordered_map, often-times much better, and I've ran some custom scenarios where I saw almost 10% increase in speed.

Haven't changed m_ComponentCaches (yet) as my testing showed unordered_map having similar perf to DualFlatMap. Can be tested later.

This introduces a side-effect change that subscriptions now keep pointers to entity-component maps, instead of going through an intermediate find, which should be a slight speedup.

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

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/355/display/redirect

wraitii added a subscriber: Itms.Aug 11 2019, 6:58 PM

@Itms It appears VM stability still isn't 100% ;)

Ran a few rejointests, all passing, which indicates that the serialisation keeps the deterministic non-linear order correctly, so this is good to go.

Stan updated the Trac tickets for this revision.Sep 9 2020, 1:13 PM
Stan added a comment.Oct 18 2020, 7:17 PM

Needs a rebase.

wraitii planned changes to this revision.Dec 6 2020, 7:16 PM

Feels like the above was a somewhat pointless exercise, TBH.
unordered_map is really good at what it does, particularly with a memory-pool backed allocator. EntityMap can beat it for small structs and low sparsity, but not even in general.

See D3186 for an actual improvement on the component front.

We could probably do with replacing some std::map with flat maps in the componentManager for stuff that indexes by interfaceID / component ID, but that's not going to be a huge improvement.

Rewriting EntityMap itself is probably still worthwhile though.

defc0n added a subscriber: defc0n.Jun 27 2022, 11:54 AM