URL:
<http://gna.org/patch/?1158>
Summary: map_location::operator<() performance hack
Project: Battle for Wesnoth
Submitted by: dfranke
Submitted on: Friday 04/10/2009 at 23:50
Priority: 5 - Normal
Status: None
Privacy: Public
Assigned to: dfranke
Originator Email:
Open/Closed: Open
Discussion Lock: Any
_______________________________________________________
Details:
map_location::operator<() is an enormous hotspot in the Wesnoth codebase. In
a single turn of the first HttT scenario, it gets hundreds of millions of
calls; Wesnoth spends about 3% of its time inside this method.
The attached patch is a GCC-specific optimization hack. It changes
map_location::x and map_location::y from int to short, and ensures that
appear consecutively in an aligned 32-bit word. operator<() then performs
the comparison in a single CPU instruction by treating x and y as a single
32-bit integer. This reduces the method's average running time on my system
from 10.4ns to 3.1ns.
I'm posting this here rather than just committing it because I'm not
convinced yet that it doesn't break anything. It makes operator<()'s
definition endianness-dependent. We need to make sure that there is no place
in the codebase that depends on any property of operator<() other than that it
defines a total ordering; it can't make any assumptions about what that
ordering is. We also need to make sure that it's okay for map coordinates to
be represented by a 16-bit integer; I'm fairly certain this is okay since
we've already established a maximum map-size policy in order to fix bug
#13031.
_______________________________________________________
File Attachments:
-------------------------------------------------------
Date: Friday 04/10/2009 at 23:50 Name: performance-hack.diff Size: 1kB
By: dfranke
<http://gna.org/patch/download.php?file_id=5599>
_______________________________________________________
Reply to this item at:
<http://gna.org/patch/?1158>
_______________________________________________
Message sent via/by Gna!
http://gna.org/
_______________________________________________
Wesnoth-bugs mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-bugs
