wesnoth/wesnoth-old — pull request #37 by yieldthought (2013-07-21 19:14:01+00:00)
Title: Speed up AI turns by around 25%

This is my first patch to Wesnoth; it's a small set of pretty trivial changes that speed AI turns up by 25-40% on my machine, measured by running --no-gui a hundred times and comparing the mean of the internal turn timers. It does this by reordering a few tests (semantic no-ops) and caching the vconfig has_attribute results within a terrain_filter.

The long version: While running thousands of times with --no-gui to gather AI statistics, I became interested in the performance of the default AI and ran it through a profiler.

I found that a surprising amount of AI turn-time is spent inside a couple of terrain_filter functions, a side effect of being called to find the leader as part of find villages, I think.

Anyway, to cut a long story shot per-line profiling showed that there were a bunch of relatively expensive operations that could be trivially avoided most of the time by reordering tests and caching a small number of cfg_.has_attribute calls, which looks semantically valid.

Longer term it might be interesting to look at the performance of vconfig more directly and decide whether to cache inside that class instead, or indeed to decide whether there's a more efficient way to find leaders and villages than loop through every tile on the map.

This, however, is a very small, localized change that has a pretty decent (~25% on my system) speedup. I guess it will apply to all AI types too, as I think find villages is likely to be called by e.g. various LUA functions too.