Page MenuHomeWildfire Games

Upgrade engine to handle up to 30 players
Needs RevisionPublic

Authored by nani on Mar 25 2020, 12:44 AM.
Tags
None
Subscribers
Stan, elexis, Restricted Owners Package and 3 others
Tokens
"The World Burns" token, awarded by nani."Yellow Medal" token, awarded by Freagarach.

Details

Reviewers
Angen
wraitii
Trac Tickets
#4004
Summary

Take (2nd try) on enabling games with more than 8 players.

The diff can be condensed in two main changes:

  • Unify all data structures and methods used in the c++ range manager component in a class that handles the players/ownership data and the bit-wise operator it uses.
  • Allow to specify the number of GUI entries to be repeated before the <repeat> tag is expanded.

This diff is only meant to upgrade the engine to handle 30 players and capable of launching from the command line not from the GUI. That will need another patch.

At first sight the changes seems to not have affected the performance but the increase of players will probably make it more noticeable.

Add @Angen as reviewer as he (if I recall correctly) already worked on this similar code with data that this diff touches.

Test Plan

Look for logic inconsistencies on the code passed to the class, possible better approaches and performance concerns.

Diff Detail

Repository
rP 0 A.D. Public Repository
Branch
/ps/trunk
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 11418
Build 20765: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Angen added inline comments.Mar 26 2020, 10:49 PM
source/simulation2/components/CCmpRangeManager.cpp
2054

, LOS

2414–2415

It would be good to avoid auto we know that there are player_id_t no?

2415

j * m_Ter

source/simulation2/components/ICmpRangeManager.h
1

years

271

j * m_Ver

283

j * m_Ver

296

j * m_Ver

308

j * m_Ver

source/simulation2/helpers/ArrayData.cpp
2

copyright

35

for ( ++i

36

i, ve

75

ArrayData<extra>&

81

ArrayData<extra>&

87

ArrayData<extra>&

93

ArrayData<extra>&

107

2 * i

113

2 * i

source/simulation2/helpers/ArrayData.h
2

copyright

31

ArrayData<extra>&

32

ArrayData<extra>&

34

ArrayData<extra>&

Angen added a reviewer: Restricted Owners Package.Mar 27 2020, 3:08 PM
Angen added inline comments.Mar 27 2020, 3:47 PM
source/simulation2/helpers/ArrayData.h
18

I would be careful using u64 as we still compile with 32 bit compiler, that means storing that value in 2 registers instead just one what makes reading and writing slower. (just a note, did not check if we can do something about it to not use u64)

Angen added inline comments.Mar 27 2020, 4:02 PM
source/graphics/tests/test_LOSTexture.h
35–46

also 0, 0 same below

nani updated this revision to Diff 11587.Mar 27 2020, 7:52 PM
nani added inline comments.Mar 27 2020, 7:53 PM
source/simulation2/helpers/ArrayData.h
18

ok

nani awarded a token.Mar 27 2020, 7:57 PM
nani marked 32 inline comments as done.Mar 27 2020, 8:01 PM
nani added inline comments.Mar 27 2020, 8:03 PM
source/simulation2/helpers/ArrayData.cpp
75

The const is needed.

some more comments

source/simulation2/helpers/ArrayData.cpp
43

If you expect here i = -1 (Comment at line 119). that is not possible. size_t is non negative.

52

for ( i += 2

53

value & 0x3 always returns the same result, should be computed before loop

113

static_cast<u64>(0x3) << 2 * i static_cast<u64>(v & 0x3) << 2 * i

nani marked 4 inline comments as done.Mar 28 2020, 7:00 PM
nani added inline comments.
source/simulation2/helpers/ArrayData.cpp
43

size_t can accept a negative value given it just applies a % operator afterwards (C++ unsigned int specification defined) so at a practical level is the same (-1 would just return the max size_t value possible and be corrected internally to 0 inside the class) and avoids doing a type conversion.

But I can change it if you are very against it.

nani updated this revision to Diff 11599.Mar 28 2020, 7:03 PM
nani marked an inline comment as done.
Stan added a subscriber: Stan.Mar 28 2020, 7:09 PM
Stan added inline comments.
source/simulation2/helpers/ArrayData.cpp
43

Maybe use ssize_t?

Angen requested changes to this revision.Mar 29 2020, 1:10 PM
Angen added inline comments.
source/simulation2/helpers/ArrayData.cpp
113

static_cast<u64>(0x3) else you are shifting at the best 32bit number, at the worst 8bit number

This revision now requires changes to proceed.Mar 29 2020, 1:10 PM
Angen added a comment.Mar 29 2020, 1:19 PM

Aside from this I got idea how this could be unlimited number of players.
You would need to store inside PlayerData an array of m_data and work with the value based on index you get.
Lets say you store m_data as u32. So if you get index 0 - 16 you get first item from array. If you get index from 17 - 32 you get second item from array and substract 16 from index.

Angen added inline comments.Mar 29 2020, 2:08 PM
source/simulation2/components/CCmpRangeManager.cpp
113

remove & 0x3, thats redundant because how getInternal is written

123

maybe you could think to pass 0x1 so it is not done & 0x3 in getinternal

193

this is not 1 bit per player. You are doubling here required memory usage.

351

same here, double memory

373

also here, this is using 0x3 internally so doubling needed memory per player

nani marked 3 inline comments as done.Mar 29 2020, 5:00 PM
nani added inline comments.
source/simulation2/components/CCmpRangeManager.cpp
193

I would prefer to leave the comment to clarify we are actually only using 1 bit of the two available for each player. Maybe the wording could be different.

nani marked an inline comment as done.Mar 29 2020, 5:04 PM
In D2667#112888, @Angen wrote:

Aside from this I got idea how this could be unlimited number of players.
You would need to store inside PlayerData an array of m_data and work with the value based on index you get.
Lets say you store m_data as u32. So if you get index 0 - 16 you get first item from array. If you get index from 17 - 32 you get second item from array and subtract 16 from index.

Yes I already tried that path but the performance hit from using an array is quite expensive compared to a primitive type. Also tried with an unordered map but couldn't get it to run (compiled but crashed for unknown reasons).

nani updated this revision to Diff 11606.Mar 29 2020, 5:15 PM
Stan added a comment.Mar 29 2020, 5:26 PM

I guess you can also update _default.xml map to use 9 players.

source/simulation2/components/CCmpRangeManager.cpp
801

spaces between operators while at it.

1025

Can you use the real type? can it be const?

1036–1037

Same here

1350

I believe & is useless for non reference types

source/simulation2/helpers/ArrayData.h
55

Is there a convention for this?

players_data_t? Dunno just wondering

Angen added a comment.Mar 29 2020, 9:43 PM

m_data = (m_data & ~(0x3 << 2 * i)) | (static_cast<u64>(v & 0x3) << 2 * i); -> m_data = (m_data & ~(static_cast<u64>(0x3) << 2 * i)) | (static_cast<u64>(v & 0x3) << 2 * i);
else 0x3 is 32bit integer

Angen requested changes to this revision.Apr 1 2020, 8:25 PM
This revision now requires changes to proceed.Apr 1 2020, 8:25 PM
nani updated this revision to Diff 11613.Apr 1 2020, 9:11 PM

Added more parameters to the class template to specify how many bits per "value" we use.
Fixed all the code style issues and inline comments Stan and Angen mentioned.

Angen added inline comments.Apr 1 2020, 10:11 PM
source/simulation2/components/CCmpRangeManager.cpp
1118

could you merge ?

1350

yep, remove &

source/simulation2/helpers/ArrayData.h
24

minus one \n

nani updated this revision to Diff 11647.Apr 8 2020, 7:14 PM
nani marked 2 inline comments as done.

Inline fixes.

Also, simplified the template. Removed the mask template parameter and move it inside as a constexpr method.
Added documentation so the class and some of the methods.

nani marked 8 inline comments as done.Apr 8 2020, 7:18 PM
nani added inline comments.
source/simulation2/helpers/ArrayData.cpp
43

From what I read ssize_t is not part of the c++ standard.

nani edited reviewers, added: wraitii; removed: Restricted Owners Package.May 17 2020, 11:42 PM
nani marked an inline comment as done.

Adding wraitii as it might interest him.

Indeed this interests me :)
I do have a hunch that we're not going beyond 32 players, as there must be a performance impact for using any data structure. Perhaps 128 bits primitives will become possible someday.
That being said, with 30 players the engine is already going to lag like a madman, so I don't really see this as a problem.
I'm adding this to my list, though I do have plenty of things I want to look at first (mainly release blockers).

wraitii requested changes to this revision.May 23 2020, 5:23 PM

No comment on the JS side as I don't think it's relevant yet.

C++ wise, it's a good effort: it works, it doesn't actively harm readability and it improves the engine's capabilities.
That being said, I think your arrayData abstraction is not the way to go, and given that it's basically 'the diff' it means you'll mostly have to rewrite everything again. Sorry about that.


First, let me point out my issues with arrayData as you're using it compared to u32 or u64

  • For a thing, the signal-to-noise ratio is super high (1 line for the template, 1 line for the function name, 1 LOC only).
  • The code doesn't improve much in readability from u32 code, since you still have to do many bit-wise operations.
  • further, playerData1b and playerData2b are as undescriptive as u32. If you're going to alias, you might as well use actually descriptive names ;)

But the real problem is that it's abstracting the wrong thing.
What is important here is that all these data structures actually represent 2D maps as 1D-arrays, they're accessed via (i,j) coordinates. So if you're going to add an abstraction, that's what its interface should be.
Now as I said, these are 2D maps, storing "some data" per player. That's currently either 1 or 2 bits, per player, which is currently up to 2*9 = 18 bits, which fits u32. But it's actually _wasting_ 12 bytes every time.
So you actually have an opportunity for optimisation here.

The target is this: P207 . It's much clearer what everything does (2D maps are Grid, LosMask is called LosMask, and you specify what data type you're operating on). I use array instead of vector since we know the size is fixed and that seems more natural too.
Grid is a data structure we already have. However you still need to create a specialisation for LosMask (and create LosMask). LosMask will be a "ghost" data type, because you'll actually be storing packed bits into the raw grid array, but from the c++ caller code it'll look indifferent.

And then you'll be able to implement LosVisible directly on LosMask. And hopefully, with some clever compiler optimisations, it works well.
(I have to say, since "LosMask" is essentially not real data, just a pointer to data & a size essentially, it might be weird to work with, but it ought to work).

Then you'll be able to have MAX_PLAYER be as big as you want, it'll create larger grids but it won't require you to completely change your approach.


Let me know if this is unclear, and/or if you don't feel like this is a super good of your time going forward, as I'd be willing to take up the mantle to implement the above.

source/gui/CGUI.cpp
880

This is rather hacky. If you have to make it dynamic, just hardcode a "ENGINEPLAYERCOUNT" constant and don't run JS.
But it seems just as simple to keep it hardcoded tbh.

This revision now requires changes to proceed.May 23 2020, 5:23 PM
nani added a comment.May 25 2020, 4:28 AM

std::array bool doesn't do bitpacking and its size must be known at compile time ( < c++2020 ), std::vector allocates in the heap. current diff has many more chances than a more extensive refactor + upgrade to have less bugs. Is practically guaranteed same performance as previous because it doesn't leave to chance the optimisations that the compiler should make (is basically a wrapper of some operations and data encapsulation). So I don't see an extra benefit changing current diff to using grid.

nani added inline comments.May 25 2020, 4:31 AM
source/gui/CGUI.cpp
880

That's what I thought too at first but if you see the XML changes you can observe why it isn't enough.

In D2667#116873, @nani wrote:

std::array bool doesn't do bitpacking and its size must be known at compile time ( < c++2020 )

Unimportant, we'd use std::array when we store NB_PLAYERS items, which will be known at compile time.
The underlying storage for Grid would be a vector (of u8 perhaps), if that wasn't clear.

current diff has many more chances than a more extensive refactor + upgrade to have less bugs

I would disagree on the grounds that you can add tests to Grid, and a good abstraction is likely to reduce bugs.
Further, then, don't implement ArrayData, just swap u8/u16 out for u64.

So I don't see an extra benefit changing current diff to using grid.

Code clarity & readability, ability to extend beyond 30 players easily.


I understand if you don't want to do it, but I don't think we should commit your patch.

It's in the grey area where it's both too complex a change (just replace u32/u16/u8 by larger data types if the goal is to reach 30 players), and not complex enough (you can't go above 30 players).

nani added a comment.May 25 2020, 8:19 AM

Fair enough. Then I pass the commander to you if you want to try the grid approax.

In D2667#116877, @nani wrote:

Fair enough. Then I pass the commander to you if you want to try the grid approax.

I think I do (it sounds like the "fun" kind of c++ to me). I'm finished the D1781 related rework first, but I'll probably move on to that next.