URL:
<http://gna.org/patch/?5668>
Summary: Node to store its priority queue index
Project: Freeciv
Submitted by: cazfi
Submitted on: Sun 04 Jan 2015 07:29:30 PM EET
Category: general
Priority: 5 - Normal
Status: Ready For Test
Privacy: Public
Assigned to: None
Originator Email:
Open/Closed: Open
Discussion Lock: Any
Planned Release:
_______________________________________________________
Details:
pf_normal_map_iterate() accounts over 20% of the server CPU time, so any
optimization to it counts, and can be even higher priority than cleanest
possible APIs. There's also other related path finding functions in the list
of top CPU hogs.
When it finds faster route to the given node, it calls priority queue
_replace() to set new cost for it. _replace() needs to find the node being
replaced, and as the nodes in the hash are not ordered, it has to iterate
though them all to find the correct one.
Attached patch changes that by keeping the node's index in the priority queue
in the node itself so there's no need to search it.
This is not very clean solution as it exposes index that should be internal
detail of the priority queue to the path finding code. I'll test this to see
if it gives any noticeable performance gain.
Earlier I considered replacing use of generic priority queue with (mostly
duplicate) implementation internal to, and specifically crafted and optimised
for, path finding.
_______________________________________________________
File Attachments:
-------------------------------------------------------
Date: Sun 04 Jan 2015 07:29:30 PM EET Name: PqIndexCache.patch Size: 10kB
By: cazfi
<http://gna.org/patch/download.php?file_id=23398>
_______________________________________________________
Reply to this item at:
<http://gna.org/patch/?5668>
_______________________________________________
Message sent via/by Gna!
http://gna.org/
_______________________________________________
Freeciv-dev mailing list
Freeciv-dev@gna.org
https://mail.gna.org/listinfo/freeciv-dev
