Page MenuHomeWildfire Games

DiskPlacer improvements.
AbandonedPublic

Authored by lyv on Jun 23 2018, 3:23 PM.

Details

Reviewers
FeXoR
Summary

DiskPlacer previously loops over the whole map each time regardless of disk size. Even though the performance cost is not That Huge, this seems to be really wasteful. This diff loops over the coordinates that are in the square with sides 2R. So placing smaller disks would be significantly faster than before.

A giant new_rms_test with 3 disks placed. Second one is with the diff:

create mapSized disk... 0.791s.
create halfMapSized disk... 0.208s.
create small disk... 0.021s.

create mapSized disk... 0.771s.
create halfMapSized disk... 0.188s.
create small disk... 0.001s.

There is also a trivial comment fix.

Test Plan

Place some Disks.

Diff Detail

Repository
rP 0 A.D. Public Repository
Lint
Lint Skipped
Unit
Unit Tests Skipped
Build Status
Buildable 6678
Build 10994: Vulcan BuildJenkins

Event Timeline

lyv created this revision.Jun 23 2018, 3:23 PM
Owners added a subscriber: Restricted Owners Package.Jun 23 2018, 3:23 PM
lyv edited the summary of this revision. (Show Details)Jun 23 2018, 3:24 PM
Vulcan added a subscriber: Vulcan.Jun 23 2018, 3:27 PM

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

Link to build: https://jenkins.wildfiregames.com/job/differential/666/display/redirect

elexis added a subscriber: elexis.Jun 23 2018, 3:36 PM
elexis added inline comments.
binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
23

Could abstract a bit
let radius = new Vector2D(this.radius, this.radius);;
let bottomLeft = Vector2D.sub(this.centerPosition, radius);
let topRight = Vector2D.add(centerPosition, radius);

Also can use getPointsInBoundingBox() after that I suppose.
That maybe slower for now, but it would be more descriptive and not reinvent something.

In fact we can prevent the unneeded array creation in getPointsInBoundingBox by executing a callback function for every point instead of adding those points to the array. At least in the places that don't really need an array to operate on.

lyv added inline comments.Jun 23 2018, 3:45 PM
binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
23

Ignoring the last paragraph, the current getPointsInBoundingBox() would make it even worse for larger DiskSizes as there would be the creation of a mapSize*mapSize array and then the looping over of that as well. It was used first and here are the results:

create MapSizedDisk... 0.864s.
create MapSizedDisk... 1.500s.

It would still lead to a better performance on smaller disks though.

Which is why I posted that last paragraph :P

So we should consider if these 6 calls can benefit. Looks like all of them can be transformed easily, not sure about the benefit, but there will be one I suspect.
Could be done in a separate patch (but then the DiskPlacer would have to be changed a bit redundantly).

Also misses rounding, an Area consists of integer coordinates. We totally need this performance improvement either way.

elexis added a comment.Jul 5 2018, 2:09 AM

Also needs to exclude points outside of the mapBounds

lyv planned changes to this revision.Jul 5 2018, 3:31 PM
lyv updated this revision to Diff 6801.Jul 5 2018, 6:50 PM
Vulcan added a comment.Jul 5 2018, 6:55 PM

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

Link to build: https://jenkins.wildfiregames.com/job/differential/675/display/redirect

elexis added a comment.Jul 5 2018, 6:59 PM

g_Map.inMapBounds? This patch was about performance improvements, if the center is near the map border half of the area can be skipped.

I didn't necessarily mean round() when I spoke of rounding, but ceil might also be a thought. The possible problem with round() is that a relevant point could be missed due to the rounding right?

That's what I had used, but I'm not sure that is the cleanest way, should probably have ceil and floor in Vector2D, no?

	let bottomLeft = Vector2D.max(
		new Vector2D(mapBounds.left, mapBounds.bottom),
		new Vector2D(this.centerPosition.x - this.maxRadius - 1, this.centerPosition.y - this.maxRadius - 1).round());

	let topRight = Vector2D.min(
		new Vector2D(mapBounds.right, mapBounds.top),
		new Vector2D(this.centerPosition.x + this.maxRadius + 1, this.centerPosition.y + this.maxRadius + 1).round());
elexis added inline comments.Jul 5 2018, 7:01 PM
binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
6–7

It's good practice to only pass unique data, i.e. to square the number only locally in the place function. (https://en.wikipedia.org/wiki/Single_source_of_truth)

lyv added a comment.Jul 6 2018, 7:00 AM

Is vectors the best approach to this? It is not used for anything more than those 2 loops. And I’m guessing using something else would have less overhead (negligible). But code would be a bit more shorter and readable I think

lyv added a comment.EditedJul 6 2018, 8:44 AM

That's what I had used, but I'm not sure that is the cleanest way,

It's cleaner than the Math.mins and Math.maxs I used. I was not aware of Vector.max/min before.

FeXoR added a reviewer: FeXoR.Jul 6 2018, 9:11 AM
FeXoR added a subscriber: FeXoR.
FeXoR added inline comments.
binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
11

AFAICS

this.centerPosition = centerPosition;

should do (if the argument is valid)..

16

The center point of the disk size should not be rounded IMO so it remains a point (as the name implies, not a tile).
Using round only in the two constricting points (bottomLeft and topRight) will return tiles with a center more accurate matching the given one (if the radius is not a hole number).
If the center TILE is needed name it that way and leave this.centerPosition as given in the argument to use it to calculate the framing points.

21

AFAICS this will be an array of tiles (well, of Vector2D representing tiles) so IMO it should be called that way.

lyv updated this revision to Diff 6807.Jul 18 2018, 5:43 PM

IMO, the variable renaming and other trivial things could be done in a rmgen wide style cleanup.

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

Link to build: https://jenkins.wildfiregames.com/job/differential/680/display/redirect

lyv updated this revision to Diff 6808.Jul 18 2018, 5:51 PM

Oversight

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

Linter detected issues:
Executing section Default...
Executing section Source...
Executing section JS...
|    | [NORMAL] ESLintBear (no-trailing-spaces):
|    | Trailing spaces not allowed.
|----|    | /mnt/data/jenkins-phabricator/workspace/differential/binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
|    |++++| /mnt/data/jenkins-phabricator/workspace/differential/binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
|  19|  19| DiskPlacer.prototype.place = function(constraint)
|  20|  20| {
|  21|  21| 	let points = [];
|  22|    |-	
|    |  22|+
|  23|  23| 	let mapBounds = g_Map.getBounds();
|  24|  24| 
|  25|  25| 	let bottomLeft = Vector2D.max(

Link to build: https://jenkins.wildfiregames.com/job/differential/681/display/redirect

lyv updated this revision to Diff 6809.Jul 18 2018, 6:05 PM

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

Link to build: https://jenkins.wildfiregames.com/job/differential/682/display/redirect

lyv added inline comments.Sep 6 2018, 4:52 AM
binaries/data/mods/public/maps/random/rmgen/math.js
111

Wouldnt it be better to add a callback function to this so that the points would be whats needed?
Pretty sure there are a number of places that can be optimized that way.

FeXoR added inline comments.Nov 12 2018, 10:21 PM
binaries/data/mods/public/maps/random/rmgen/math.js
111

If using this function to replace your added code in the other function I agree. Else I don't understand what you mean.

elexis added a comment.EditedJan 3 2019, 2:38 PM

getPointsInBoundingBox (which could receive an optional filter function argument)

lyv updated this revision to Diff 7217.Jan 3 2019, 6:32 PM

Add filter to getPointsInBoundingBox and use that.

binaries/data/mods/public/maps/random/rmgen/math.js
111

function which returns true instead of undefined better?

Vulcan added a comment.Jan 3 2019, 6:33 PM

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

Linter detected issues:
Executing section Source...
Executing section JS...
|    | [NORMAL] ESLintBear (object-curly-spacing):
|    | A space is required after '{'.
|----|    | /mnt/data/jenkins-phabricator/workspace/differential/binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
|    |++++| /mnt/data/jenkins-phabricator/workspace/differential/binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
|  30|  30| 
|  31|  31| 	let filter = (point) => this.centerPosition.distanceToSquared(point) <= radiusSquared && constraint.allows(point);
|  32|  32| 
|  33|    |-	return getPointsInBoundingBox({"min": bottomLeft, "max": topRight}, filter);
|    |  33|+	return getPointsInBoundingBox({ "min": bottomLeft, "max": topRight}, filter);
|  34|  34| };
|    | [NORMAL] ESLintBear (object-curly-spacing):
|    | A space is required before '}'.
|----|    | /mnt/data/jenkins-phabricator/workspace/differential/binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
|    |++++| /mnt/data/jenkins-phabricator/workspace/differential/binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
|  30|  30| 
|  31|  31| 	let filter = (point) => this.centerPosition.distanceToSquared(point) <= radiusSquared && constraint.allows(point);
|  32|  32| 
|  33|    |-	return getPointsInBoundingBox({"min": bottomLeft, "max": topRight}, filter);
|    |  33|+	return getPointsInBoundingBox({"min": bottomLeft, "max": topRight }, filter);
|  34|  34| };
Executing section cli...

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

elexis added a comment.Jan 7 2019, 2:50 PM

Perhaps it can be simplified a bit more by using getBoundingBox, perhaps getPointsInBoundingBox could even become a Placer, perhaps the filter function could become a Constraint (didn't investigate).

binaries/data/mods/public/maps/random/rmgen/math.js
111

A callback function would avoid creating the array if it's not needed, but also require each user of the array to create it manually. So it's a trade-off and one would need to put on glasses to decide.

binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
33

Can inline the function, functionName\narg1\narg2.
also point => and space after/before { / }
Can inline bottomLeft and topRight too (the meaning of the value is still described by the property name)

lyv abandoned this revision.Jun 23 2022, 12:33 PM

Superseded by D2710 and retrospectively speaking, unsure if getPointsInBB with filter callback was actually the right call over a simple for loop.