patchBos Wars - Patches: patch #7141, Speed up pathfinder by caching...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

patch #7141: Speed up pathfinder by caching islands

Submitter:  Kalle Olavi Niemitalo <kon>
Submitted:  Sat 27 Mar 2010 07:30:37 PM UTC
   
 
Open/Closed:  Closed Status:  Wont Do
Assigned to:  None

Jump to the original submission

Thu 08 Jul 2010 01:51:22 PM UTC, comment #13: 

Now that jsalmon3 has fixed bug #29766, I think this patch will not be needed.  Thus closing; let's reopen later if the game turns out to be too slow still.

Kalle Olavi Niemitalo <kon>
Group Member
Sat 22 May 2010 12:58:43 PM UTC, comment #12: 

In comment #8, I mentioned a scenario that the island cache might not handle correctly.  That indeed is the case.  I'm attaching a map that demonstrates the problem.  First apply PATCHv9 (file #20591), uncomment #define VERIFY_ISLAND_CACHE, and build the debug configuration.  Start a game in this map, select all the units and tell them to move to the camera.

Assertion failed at engine/pathfinder/pathfinder.cpp:278: pf == PF_UNREACHABLE || !shouldBeUnreachable

One of the grenadiers tries to move first.  It looks for a path to the camera, but the assault unit is in the way.  The grenadier gives up for this GameCycle, and the island cache notes that the camera is unreachable.

Next, the assault unit moves out of the way.

Finally, the other grenadier tries to move to the camera.  The assault unit is no longer in the way but the island cache still thinks it is.  Thus, the assertion fails.


(file #20592, file #20593)

Kalle Olavi Niemitalo <kon>
Group Member
Sat 22 May 2010 12:48:18 PM UTC, comment #11: 

Fixed the out-of-range CostMoveTo call; PATCHv9 (for 2.6.0) attached.

(file #20591)

Kalle Olavi Niemitalo <kon>
Group Member
Sun 16 May 2010 12:07:21 AM UTC, comment #10: 

There is a bug in v7; it can call CostMoveTo with coordinates that are outside the map.  It's trivial to fix but anyway I'm noting the bug here before I forget.

Kalle Olavi Niemitalo <kon>
Group Member
Thu 13 May 2010 03:08:44 PM UTC, comment #9: 

The random variation in the call counts shown by gprof was caused by the SDL sound mixer thread:

http://colabti.org/irclogger/irclogger_log/bos?date=2010-05-09#l13
http://lists.gnu.org/archive/html/bug-binutils/2010-05/msg00029.html

Kalle Olavi Niemitalo <kon>
Group Member
Tue 04 May 2010 05:34:12 AM UTC, comment #8: 

Version 7 of the island-cache patch, for boswars-2.6 r9725.  This seems to be the fastest version so far.

Things to do before pushing to svn:

  • Add support for the case where the unit is can only move away from the goal but already happens to be close enough (within maxrange).
  • Test the case where there are three units trying to leave an area and the second of them is initially blocking the way but then moves out of the way.  If this doesn't work, I'm afraid the whole concept must be scrapped.
  • Add comments.
  • Add proper initialization.
  • Figure out what causes the random variation in call counts when profiling.


Things to do after pushing to svn:

  • Profile whether it's faster to check the cache also when there are uncached tiles around the unit.
  • Profile and optimize the threshold in AStarWasSlow.
  • Make IslandCache::GoalMightBeInIsland more accurate.
  • Add support for units larger than 1x1.


(file #20417)

Kalle Olavi Niemitalo <kon>
Group Member
Mon 12 Apr 2010 04:36:30 AM UTC, comment #7: 

Attached the hack I tried to use for unattended profiling of different variants of the pathfinder.  I left this running overnight and in the morning I saw v3 and v4 had failed with SIGABRT.


I had applied the patches on top of boswars-2.6 r9725.  The total times of the first runs:

  • original pathfinder: 11816.86user 154.11system 3:14:18elapsed 102%CPU (0avgtext+0avgdata 449984maxresident)k 0inputs+1920outputs (0major+29292minor)pagefaults 0swaps
  • PATCHv1: 5831.96user 71.98system 1:35:50elapsed 102%CPU (0avgtext+0avgdata 450064maxresident)k 0inputs+1912outputs (0major+29298minor)pagefaults 0swaps
  • PATCHv2: 5820.41user 70.48system 1:35:38elapsed 102%CPU (0avgtext+0avgdata 450032maxresident)k 0inputs+1912outputs (0major+29296minor)pagefaults 0swaps


so the patches do reduce the slowdown by half.  No timings for v3 and v4 because of the SIGABRT.

Kalle Olavi Niemitalo <kon>
Group Member
Mon 12 Apr 2010 04:19:25 AM UTC, comment #6: 

Version 4 of the island-cache patch, for boswars-2.6 r9725.  This version tries to let other units benefit from the cache built for one unit.

Unfortunately, I'm seeing SIGABRT with v3 and v4.  Not so with v1 and v2.  I haven't debugged that yet.

(file #20197)

Kalle Olavi Niemitalo <kon>
Group Member
Sun 11 Apr 2010 07:35:10 AM UTC, comment #5: 

Marking as postponed so feb won't apply this one yet.

Kalle Olavi Niemitalo <kon>
Group Member
Tue 06 Apr 2010 10:06:41 PM UTC, comment #4: 

Here's one problematic scenario.  This does NOT currently trigger a bug but might do so later.

Imagine a narrow corridor, only one tile wide.  There are two units near the middle of the corridor.

......A.....B......

Then you select both units, and tell them to move to the eastern end of the corridor.  Unit A happens to get the first turn.  It tries to find a path to the end, but cannot, so it marks the island.

111111A11111B......

The tile under A itself is also marked as belonging to island 1.  The tile under B is not so marked.  But imagine if it were.  Then unit B gets its turn to move, and looks for a path to the end.  Because unit B is in island 1, and the goal is not in that island, unit B decides the goal is unreachable, which is wrong.

So, if we change the island cache to mark also the tiles under nearby units as belonging to the island, in order to let those units benefit from the cache too, then we need to solve this situation somehow.

Kalle Olavi Niemitalo <kon>
Group Member
Tue 06 Apr 2010 09:49:12 PM UTC, comment #3: 

Version 3 of the island-cache patch, for trunk r9708.
Changes since v2:

  • Renamed AStarForEachInCloseSet to AStarForEachTileInIsland because it does not in fact list all the nodes in the close set.
  • IslandCache::MarkIslandTile sets self->MarkedAnythingThisCall = true like originally intended.  In v2, the flag was always false.


However, I've just noticed that A* does not add the tiles occupied by other units to the close set.  I think this means the island cache is currently useful only for the single unit for which it was built.  Not even for other units of the exact same type.  This seems ridiculous (why would the same unit try to compute several paths during the same game cycle?) but profiling showed the cache was beneficial anyway.  Perhaps it's because of how DoActionMove calls first NextPathElement and then AiCanNotMove, which calls PlaceReachable.  Anyway, if the cache is for only one unit, I think it could be optimized a few percent by dropping the separate IslandCache data structure and just using the A* variables directly.  That is not the way to big improvements though.

(file #20141)

Kalle Olavi Niemitalo <kon>
Group Member
Sat 03 Apr 2010 08:34:59 AM UTC, comment #2: 

Version 2 of the island-cache patch.
Notable changes since v1:

  • Don't trust the cache if TileWidth or TileHeight of CUnitType is different from the one for which the cache was constructed.
  • Don't bother caching if the reachable area is so small that A* can quickly scan it on its own.



(file #20096)

Kalle Olavi Niemitalo <kon>
Group Member
Sun 28 Mar 2010 08:17:46 AM UTC, comment #1: 

I tested file #20052 on trunk r9695 by uncommenting #define VERIFY_ISLAND_CACHE and replaying file #20005 from bug #29303 until game cycle 40139. (The last command in the log is at game cycle 36203.)  There were no assertion failures, which means all goals that were unreachable according to the island cache were also unreachable according to AStarFindPath.

However, I think there were no aircraft in this replay.

Kalle Olavi Niemitalo <kon>
Group Member
Sat 27 Mar 2010 07:30:37 PM UTC, original submission:  

When AStarFindPath decides that the goal is unreachable, it has already done a flood fill from the source position to all reachable tiles.  Save the filled island in a cache.  Then, if another unit in that island wants to move out of it, consider the goal unreachable right away.

In this version, the cache is flushed on every game cycle, so that it need not be updated when units move out of the way.  Regardless, it skipped 2031 of 6284 AStarFindPath calls when replaying the first 20480 game cycles of log_of_stratagus_0-4on4-assert-failed.log from <http://savannah.nongnu.org/bugs/?29303>, and the skipped calls would probably have been among the slowest ones.  The remaining 4253 AStarFindPath calls took 198.77 seconds in total, and the 6284 IslandCache::FindPath calls took 209.04 seconds in total, so the overhead from the caching was 10.27 seconds, which is probably less than what the skipped AStarFindPath calls would have cost.

This initial patch is somewhat sloppy code and should not be pushed to svn.  Comments and proper initialization are missing.

This patch is for trunk r9695.

Kalle Olavi Niemitalo <kon>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attached Files
file #20592:  presentation.smp added by kon (292B - application/octet-stream - island-miscache.map)
file #20593:  setup.sms added by kon (3KiB - application/octet-stream - island-miscache.map)
file #20591:  0001-Speed-up-pathfinder-by-caching-islands.patch added by kon (11KiB - text/x-patch - [PATCHv9] Speed up pathfinder by caching islands)
file #20417:  0001-Speed-up-pathfinder-by-caching-islands.patch added by kon (11KiB - text/x-patch - [PATCHv7] Speed up pathfinder by caching islands)
file #20200:  log_of_stratagus_0-4on4-assert-failed.log added by kon (79KiB - text/x-log - unattended profiling: stratagus log as benchmark, same as in bug #29303 except added automatic quit)
file #20199:  0001-Add-r-for-profiling-the-pathfinder-with-a-log.patch added by kon (6KiB - text/x-patch - unattended profiling: [PATCH] Add -r for profiling the pathfinder with a log)
file #20198:  profile added by kon (488B - application/octet-stream - unattended profiling: script to profile different variants in a loop)
file #20197:  0001-Speed-up-pathfinder-by-caching-islands.patch added by kon (10KiB - text/x-patch - [PATCHv4] Speed up pathfinder by caching islands)
file #20141:  0001-Speed-up-pathfinder-by-caching-islands.patch added by kon (9KiB - text/x-patch - [PATCHv3] Speed up pathfinder by caching islands)
file #20096:  0001-Speed-up-pathfinder-by-caching-islands.patch added by kon (9KiB - text/x-patch - [PATCHv2] Speed up pathfinder by caching islands)
file #20052:  0001-Speed-up-pathfinder-by-caching-islands.patch added by kon (8KiB - text/x-patch - [PATCH] Speed up pathfinder by caching islands)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by kon (Submitted the item)
  •  

    Follow 14 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2010-07-08 kon Open/ClosedOpen Closed
        StatusPostponed Wont Do
    2010-05-22 kon Attached File- Added presentation.smp, #20592
        Attached File- Added setup.sms, #20593
    2010-05-22 kon Attached File- Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20591
    2010-05-04 kon Attached File- Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20417
    2010-04-12 kon Attached File- Added log_of_stratagus_0-4on4-assert-failed.log, #20200
    2010-04-12 kon Attached File- Added 0001-Add-r-for-profiling-the-pathfinder-with-a-log.patch, #20199
    2010-04-12 kon Attached File- Added profile, #20198
    2010-04-12 kon Attached File- Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20197
    2010-04-11 kon StatusNone Postponed
    2010-04-06 kon Attached File- Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20141
    2010-04-03 kon Attached File- Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20096
    2010-03-27 kon Attached File- Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20052

    Back to the top

    Powered by Savane 3.13-bb6a.
    Corresponding source code