Page MenuHomeWildfire Games

DiskPlacer improvements.
Needs ReviewPublic

Authored by smiley 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
Branch
/ps/trunk
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 6287
Build 10436: Vulcan BuildJenkins
Build 10435: arc lint + arc unit

Event Timeline

smiley created this revision.Jun 23 2018, 3:23 PM
Owners added a subscriber: Restricted Owners Package.Jun 23 2018, 3:23 PM
smiley 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
22

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.

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

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

smiley planned changes to this revision.Jul 5 2018, 3:31 PM
smiley 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)

smiley 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

smiley 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
10

AFAICS

this.centerPosition = centerPosition;

should do (if the argument is valid)..

15

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.

20–22

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

smiley 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

smiley 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

smiley 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

smiley 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.Mon, Nov 12, 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.