Page MenuHomeWildfire Games

FixedVector2D CompareLengthSquared
ClosedPublic

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

Details

Reviewers
None
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Commits
rP23489: Implement a FixedVector2D::CompareLengthSquared function to provide a more…
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
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

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 ↗(On Diff #8837)

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

145 ↗(On Diff #8837)

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

155 ↗(On Diff #8837)

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.

The test came from http://irclogs.wildfiregames.com/2019-07/2019-07-12-QuakeNet-%230ad-dev.log

19:02 < Vladislav> fixed n = fixed::FromFloat(1.0f / 10.0f); fixed n2 = n.Square(); CFixedVector2D vec(n, n); fixed len = n2.Multiply(fixed::FromInt(2));
19:02 < Vladislav> elexis: what should we get for vec.CompareLengthSquared(len)?
19:07 < elexis> according to vec definition, squared length of vec is 2*n², that is the same as len, therefore vec.CompareLengthSquared(len) ought to be 0 as the numbers are the same

source/maths/FixedVector2D.h
124 ↗(On Diff #8837)

One could do a macro, but the duplication is quite limited, 4 lines? then it already starts to differ

145 ↗(On Diff #8837)

What does cmp prefix mean here?

cmp means the same as in the function above, the value compared against.

Why squared?

squared because the value is squared.

In theory we may want to compare our squared length not only with squared values.

int CompareLength(fixed cmp) const still exists, this function is only an optimization thereof to avoid the repetitive squaring of the compared value. For example if one wants to iterate through all tiles on a disk in a bounding box, then one has to compute the square radius only once instead of x*y times.

155 ↗(On Diff #8837)

I didn't notice Square() would drop the fraction

elexis updated this revision to Diff 11261.Feb 3 2020, 12:57 AM
  • Add Vladislavs test case
  • Drop fractional part here as well.
Vulcan added a comment.Feb 3 2020, 1:16 AM

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/1702/display/redirect

The objective of the diff is to avoid repeating this operation in loops where this value doesn't change during the loop:

		i32 c = cmp.GetInternalValue();
		u64 c2 = (u64)FIXED_MUL_I64_I32_I32(c, c);

In Diff 5 11261 23475 https://code.wildfiregames.com/D2058?id=11261 this comes at the cost of one fract bitshift:

d2 >>= fixed::fract_bits;

elexis updated this revision to Diff 11278.Feb 5 2020, 2:21 AM

Fix rangemanager missing parentheses, add testcases proposed by Vladislav
http://irclogs.wildfiregames.com/2020-02/2020-02-04-QuakeNet-%230ad-dev.log

Vulcan added a comment.Feb 5 2020, 2:26 AM

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

Link to build: https://jenkins.wildfiregames.com/job/macos-differential/292/display/redirect

Vulcan added a comment.Feb 5 2020, 2:28 AM

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

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

elexis planned changes to this revision.Feb 5 2020, 1:40 PM

Squaring is no fun, because it uses Multiply and Multiply overflows without printing a warning (while warning when overflowing when casting).
Need to use the internal value (u64) for comparison, because fixed can only represent 2*128² at most and one often receives vector lengths an order of magnitude or more greater than 128 that need to be squared.

elexis updated this revision to Diff 11307.Feb 9 2020, 2:47 PM

Ditch Fixed as an arugment and implement FIXED_SQUARE_I32 macro

Vulcan added a comment.Feb 9 2020, 2:54 PM

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

Link to build: https://jenkins.wildfiregames.com/job/vs2015-differential/1215/display/redirect

Vulcan added a comment.Feb 9 2020, 3:16 PM

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

Linter detected issues:
Executing section Source...

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.

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/Fixed.h
|   1| /*·Copyright·(C)·2013·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2020" year instead of "2013"

source/maths/Fixed.h
| 101| template·<typename·T>
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' 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/1734/display/redirect

elexis added a comment.Feb 9 2020, 6:50 PM

refs https://docs.microsoft.com/de-de/cpp/intrinsics/emul-emulu?view=vs-2019

Ive done the following performance test:

		for (int j = 0; j < 5; ++j)
		{
			{
				int z = 0;
				auto start = std::chrono::high_resolution_clock::now();
				for (u64 i = 0; i < 100000000; ++i)
				{
					if (CFixedVector2D(fixed::FromInt(i / 1000), fixed::FromInt(0)).CompareLength(fixed::FromInt(5)) == 1)
						++z;
				}
				auto elapsed = std::chrono::high_resolution_clock::now() - start;
				debug_printf("unoptimized %ld\n", std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count());
				debug_printf("z is %d\n", z);
			}


			{
				int z = 0;
				auto start = std::chrono::high_resolution_clock::now();
				u64 cmpSquared = SQUARE_U64_FIXED(fixed::FromInt(5));
				for (u64 i = 0; i < 100000000; ++i)
				{
					if (CFixedVector2D(fixed::FromInt(i / 1000), fixed::FromInt(0)).CompareLengthSquared(cmpSquared) == 1)
						++z;
				}
				auto elapsed = std::chrono::high_resolution_clock::now() - start;
				debug_printf("optimized %ld\n", std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count());
				debug_printf("z is %d\n", z);
			}

			{
				int z = 0;
				auto start = std::chrono::high_resolution_clock::now();
				u64 cmpSquared = SQUARE_U64_FIXED(fixed::FromInt(5));
				for (u64 i = 0; i < 100000000; ++i)
				{
					if (CFixedVector2D(fixed::FromInt(i / 1000), fixed::FromInt(0)).CompareLengthSquared(cmpSquared) == 1)
						++z;
				}
				auto elapsed = std::chrono::high_resolution_clock::now() - start;
				debug_printf("optimized %ld\n", std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count());
				debug_printf("z is %d\n", z);
			}
			{
				int z = 0;
				auto start = std::chrono::high_resolution_clock::now();
				for (u64 i = 0; i < 100000000; ++i)
				{
					if (CFixedVector2D(fixed::FromInt(i / 1000), fixed::FromInt(0)).CompareLength(fixed::FromInt(5)) == 1)
						++z;
				}
				auto elapsed = std::chrono::high_resolution_clock::now() - start;
				debug_printf("unoptimized %ld\n", std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count());
				debug_printf("z is %d\n", z);
			}

		}

Notice the ABBA pattern, otherwise the results were invalid (making the first run through always slower, no matter if the first run through was the optimized or unoptimized variant).

The results were:

optimized	294939		unoptimized	294943
optimized	294943		unoptimized	294945
optimized	294945		unoptimized	294953
optimized	294990		unoptimized	295118
optimized	295006		unoptimized	296029
optimized	324439		unoptimized	324432
optimized	324442		unoptimized	324432
optimized	324450		unoptimized	324447
optimized	324534		unoptimized	324450
optimized	325474		unoptimized	335617

which makes the optimized variant 0.36% faster.
This however doesnt say much, because the test setup is also measured, and the test setup takes much more time.
So it definitely is faster, we know its faster because its at least one less instruction, and it was also measured, we just dont know how much faster it is.

elexis updated this revision to Diff 11311.Feb 9 2020, 6:57 PM

More static cast, drop old tests, use macro more often, rename macro.

Vulcan added a comment.Feb 9 2020, 7:26 PM

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

Linter detected issues:
Executing section Source...

source/maths/FixedVector3D.h
|   1| /*·Copyright·(C)·2013·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2020" year instead of "2013"

source/maths/FixedVector3D.h
|  24| class·CFixedVector3D
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCFixedVector3D{' 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.

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/Fixed.h
| 103| template·<typename·T>
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' 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/1738/display/redirect

elexis updated this revision to Diff 11313.Feb 9 2020, 8:54 PM

One abs less.

Vulcan added a comment.Feb 9 2020, 9:24 PM

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

Linter detected issues:
Executing section Source...

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.

source/maths/Fixed.h
| 103| template·<typename·T>
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' is invalid C code. Use --std or --language to configure the language.

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

source/maths/FixedVector2D.h
|  24| class·CFixedVector2D
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCFixedVector2D{' 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/1740/display/redirect

This revision was not accepted when it landed; it landed in state Needs Review.Feb 9 2020, 10:00 PM
This revision was automatically updated to reflect the committed changes.
Owners added a subscriber: Restricted Owners Package.Feb 9 2020, 10:00 PM