Opened 10 years ago

Closed 10 years ago

#2025 closed defect (invalid)

[PATCH] Pathfind performance

Reported by: tuan kuranes Owned by:
Priority: Nice to Have Milestone:
Component: Core engine Keywords: patch
Cc: Patch:


Pathfind code optimisations without any single behaviour change(no hash change). 30% improvements, as tested directly on pathfind code.

(pathfind_test_branch_vanilla_update.path is for vanilla 0AD svn benchmark adding for fair comparison)

Attachments (2)

pathfind.patch (148.2 KB ) - added by tuan kuranes 10 years ago.
pathfind_test_banch_vanilla_update.patch (3.5 KB ) - added by tuan kuranes 10 years ago.

Download all attachments as: .zip

Change History (5)

by tuan kuranes, 10 years ago

Attachment: pathfind.patch added

by tuan kuranes, 10 years ago

comment:1 by tuan kuranes, 10 years ago

Summary: Pathfind performance[PATCH] Pathfind performance

comment:2 by Kieran P, 10 years ago

Keywords: patch review added
Milestone: BacklogAlpha 14
Priority: Should HaveNice to Have

comment:3 by historic_bruno, 10 years ago

Keywords: review removed
Milestone: Alpha 14
Resolution: invalid
Status: newclosed

Thanks for the work on this patch. Even though it's somewhat of an improvement (more like 5-15% reduction in short path computation time, depending on testing method, this matches comments from #1923), the short pathfinder algorithm is not scalable, so anything short of redesigning it doesn't have much value - we know this because it can easily consume 1-2s per turn, when a turn is only 200ms... This patch unfortunately makes the existing logic harder to understand, complicating a rewrite, and does yucky things like moving locals to global variables, which even though it may reduce allocations, is a problem that can be solved in a better way by redesign of the algorithm.

Reviewing the patch, it's hard to differentiate the changes that impact performance from those that are simply personal convention, in fact going line-by-line through it, I was able to revert most of the changes without changing performance at all (it was time consuming, but I compared them, building the game with VS2010 and profiling with Very Sleepy). I think some of the suggestions are things we should keep in mind when designing the new pathfinder algorithm and writing future code, but maintaining readable code is also important if it can be helped (given profiling data, it can be helped in this case).

Note: See TracTickets for help on using tickets.