Page MenuHomeWildfire Games

FixedVector2D CompareLengthSquared
Changes PlannedPublic

Authored by elexis on Jul 10 2019, 12:17 AM.

Details

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

Having the FixedVector2D implementation in the header means that half the engine has to be compiled again if one wants to change it.
Moving it to its own C++ file means it can be changed without having to do that.
Update: It also prevents inline optimizations, so don't move it.

This patch also adds static_cast conversions, a CompareLengthSquared function that is used in the RangeManager once (exemplary use) and tests.

Test Plan

Read through the lines and see that the code was unchanged except for the advertized changes.
Check that the new function computes properly, especially the bitshift was not obvious (it is multiplication of 1.GetInternal()).

Diff Detail

Repository
rP 0 A.D. Public Repository
Branch
/ps/trunk
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 8298
Build 13542: Vulcan BuildJenkins
Build 13541: arc lint + arc unit

Event Timeline

elexis created this revision.Jul 10 2019, 12:17 AM

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

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

elexis updated this revision to Diff 8806.Jul 10 2019, 1:03 AM

Missing parenthesis

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

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

wraitii added a subscriber: wraitii.EditedJul 10 2019, 7:57 AM

CompareLength is already comparing squared vectors, so I'm assuming you just want to avoid paying the cost of a multiplication every time ?
The name might need to be improved slightly though.

Otherwise this looks good and a good idea.

One warning: you should check if it decreases performance by lowering the chances of inlining, since these will be in different TUs.
I don't believe we compile with LOT, but true with that also?

wraitii added a reviewer: Restricted Owners Package.Jul 11 2019, 3:04 PM

CompareLength is already comparing squared vectors, so I'm assuming you just want to avoid paying the cost of a multiplication every time ?

Yes

you should check if it decreases performance by lowering the chances of inlining, since these will be in different TUs.

That is a point. I moved it to a custom TU because changing that file consumes a lot of time to compile as many files depend on it. But if it has a performance disadvantage, then it was a wrong idea.

From #0ad-dev today:

(06:35:04 PM) elexis: as wraitii mentioned it may make it harder to inline
(06:35:13 PM) elexis: as far as I read that inlining may happen during the linking stage
(06:35:55 PM) elexis: (the same for Pathfinder.h btw)
(06:36:37 PM) Vladislav_: it's certainly not bad, but yes, inlining depends on compiler and a lot of other stuff.
(06:37:17 PM) Vladislav_: I'd like to measure it.
(06:37:39 PM) elexis: but is it known to make inlining impossible?
(06:37:54 PM) elexis: at least the getters have the const keyword, but theyre in different translation units
(06:38:42 PM) elexis: (the caller and callee)
(06:40:49 PM) Vladislav_: gcc has http://gcc.gnu.org/wiki/LinkTimeOptimization
(06:40:57 PM) Vladislav_: clang should have something similar.
(06:41:10 PM) Vladislav_: I don't know about vs < 2017.
(06:42:18 PM) Vladislav_: So I'd like to measure.

I then copied the function to the header (so I had the same function in cpp and .h), wrote a testcase that runs the affected function 10000000 times and measured microseconds.
The cpp variant consumes N > 0ms while the other variant consumed 0ms.
I compiled with gcc 9.
So observation (1), gcc 9 can optimize the header file in was that the cpp file can't.

(12:51:40 AM) elexis: Vladislav_: I dont understand
(12:52:00 AM) elexis: I wrote a test calling the function 10000000 times and measured microseconds
(12:52:34 AM) elexis: the one in the header always consumes 0.0000, but its called, the one in c++ 142ms
(12:53:12 AM) elexis: I must have made a mistake but I dont find it
(12:53:21 AM) elexis: (sometimes 1microsecond)
(12:55:00 AM) elexis: or it could compute all the results in advance by inlining and killed the loop, somehow
(12:55:50 AM) Vladislav_: Yes, it's possible that it was optimised. True to use some random or input dependent data.
(12:55:58 AM) Vladislav_: s/True/Try
(12:58:56 AM) elexis: notice that the first loop was not optimized but the second was

I then tried rand() use in the test and consistently got values like:

Test1 254441.000000 // .cpp
Test2 222263.000000 // .h

Thats around 13% difference.
So it seems like it must remain in the header.

elexis retitled this revision from Move FixedVector implementation from header to cpp, add CompareLengthSquared to FixedVector2D CompareLengthSquared.Jul 12 2019, 1:37 AM
elexis edited the summary of this revision. (Show Details)
elexis updated this revision to Diff 8836.Jul 12 2019, 1:38 AM

Revert cpp move.

elexis updated this revision to Diff 8837.Jul 12 2019, 1:40 AM

Remove commented out line.

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

Linter detected issues:
Executing section Source...

source/maths/FixedVector2D.h
|  24| class·CFixedVector2D
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCFixedVector2D{' is invalid C code. Use --std or --language to configure the language.

source/maths/tests/test_FixedVector2D.h
|  30| class·TestFixedVector2D·:·public·CxxTest::TestSuite
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classTestFixedVector2D:' is invalid C code. Use --std or --language to configure the language.
Executing section JS...
Executing section cli...

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

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

Linter detected issues:
Executing section Source...

source/maths/FixedVector2D.h
|  24| class·CFixedVector2D
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCFixedVector2D{' is invalid C code. Use --std or --language to configure the language.

source/maths/tests/test_FixedVector2D.h
|  30| class·TestFixedVector2D·:·public·CxxTest::TestSuite
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classTestFixedVector2D:' is invalid C code. Use --std or --language to configure the language.
Executing section JS...
Executing section cli...

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

vladislavbelov added inline comments.
source/maths/FixedVector2D.h
124

I'm wondering will our supported compilers inline correctly if we merge common parts of CompareLength and CompareLengthSquared into a separate function.

145

What does cmp prefix mean here? Why squared? In theory we may want to compare our squared length not only with squared values.

155

It means that we account low fractional part of the squared length (cmpSquared contains zeroes for that part) and we get that:

vec.GetSquaredLength().Compare(squaredValue) != vec.CompareLengthSquared(squaredValue)

Is this expected?

elexis planned changes to this revision.Jul 15 2019, 2:44 AM

As discussed with Vladislav on IRC in the past days, this iteration of the diff fails for fractional values, specifically this test:

		fixed n = fixed::FromFloat(1.0f / 10.0f);
		fixed n2 = n.Square();
		CFixedVector2D vec(n, n);
		fixed len = n2.Multiply(fixed::FromInt(2));
		TS_ASSERT_EQUALS(n2, len);

Since Length().Square() right shifts after multiplication, thus less precise than the squaring of GetInternalValue using the u64 which doesn't shift.