Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#2358 closed enhancement (fixed)

[PATCH] Make entity selection faster

Reported by: Josh Owned by: Josh
Priority: Must Have Milestone: Alpha 16
Component: UI & Simulation Keywords: performance
Cc: Patch:

Description (last modified by Josh)

Right now, on every mouse movement event we call EntitySelection::PickEntitiesAtPoint. This sometimes happens multiple times per frame. The existing function loops through every entity that is selectable and computes their distance from the mouse which is very inefficient.

Here's a ~hour long profile of a normal game in 0AD: https://googledrive.com/host/0BwIjnJSd7iThRXRiN0ExcVVaeDQ/cpuprofile5.svg

As you can see, entity selection is a good 1.5%. (I've seen over 3% in some profiles) The in-game profiler also confirmed the problem showing ~5-15 calls of the function per frame, each taking ~50ms.

The attached patch improves the situation by getting a smaller group of entities from the range manager's spatial subdivisions before checking the distance of each one. Initial measurements from the in-game profiler show the new function taking ~45us which is an improvement of over a hundred times.

Attachments (1)

fast-select.diff (19.5 KB ) - added by Josh 10 years ago.
Second version, ignore all the whitespace stripping. (vim did that automatically) See helpers/Selection.cpp for the main changes. This version adds the ability to specify the selection range from JS.

Download all attachments as: .zip

Change History (5)

comment:1 by Josh, 10 years ago

Description: modified (diff)

by Josh, 10 years ago

Attachment: fast-select.diff added

Second version, ignore all the whitespace stripping. (vim did that automatically) See helpers/Selection.cpp for the main changes. This version adds the ability to specify the selection range from JS.

comment:2 by Josh, 10 years ago

After a little more profiling on combat demo huge, I'm seeing ~600us before and ~18us after spent in the function. (improvement is less dramatic because of a lower total number of entities)

Last edited 10 years ago by Josh (previous) (diff)

comment:3 by JoshuaJB, 10 years ago

Resolution: fixed
Status: newclosed

In 14532:

Make PickEntitiesAtPoint faster yielding 1-3% overall performance improvement. Fixes #2358. Also removes some trailing whitespace.

comment:4 by Josh, 10 years ago

Keywords: patch removed
Milestone: BacklogAlpha 16
Type: defectenhancement

I tried fiddling with the range radius constant, and 100 seemed to work reliably. Further adjustments should change SELECTION_SEARCH_RADIUS in input.js. It's not insanely fast with the current setting, but works reliably and is in any account faster then the old version.

Note: See TracTickets for help on using tickets.