[Freeciv-Dev] [Patch] [RFC] Path finding version 14

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

Changes to the interface
 - remove PF_IGNORE_COST
 - add enum tile_behavior
 - add get_TB
 - add ignore_enemy and omniscience flags

The first three should be obvious. I will explain the last one latter.

Changes to the implementation:
 - add bucket list heap (activate with USE_HEAP2)
 - add some inlining (activate with USE_INLINE) This is a moderate
 inline which brings the path finding in the same area as
 really_generate_warmap. The 8 small helper function are all moved
 into plain_get_next_position and so plain_get_next_position and
 really_generate_warmap are now the big functions.
 - support for the get_TB, ignore_enemy and omniscience
 - added a missing heap_destroy call

Beware: The version isn't tested this much.

Comparing the profiles of really_generate_warmap and the path finding
revealed that the path finding does too much work: it checks for ZOC
and if a unit can attack an enemy. The really_generate_warmap also
doesn't do any visibility checks. So I added the ignore_enemy and
omniscience flags to be able to compare the performance. It is still
unknown if they functions calulcate the same amount of
work. really_generate_warmap stops after a BMC of "THRESHOLD * 6 + 2"
= 74. The path finding doesn't step into unknown. However judging from
the calls to heap_dequeue and get_from_mapqueue it appears that the
warmap does 2.4 times the work.

Results:

 with profiling, USE_INLINE and heap:
  2: gotohand=45,400000s path_finding=40,530000s factor=0,892731

 USE_INLINE and heap:
  2: gotohand=14,820000s path_finding=38,540000s factor=2,600540

 with profiling, USE_INLINE and heap2:
  2: gotohand=45,040000s path_finding=47,580000s factor=1,056394

 USE_INLINE and heap2:
  2: gotohand=15,580000s path_finding=38,400000s factor=2,464698

As you can see the profiling results may be wrong.

Start of profile for with profiling, USE_INLINE and heap:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 34.36      8.28     8.28  2155900     0.00     0.01  plain_get_next_position
 25.19     14.35     6.07    13300     0.46     0.86  really_generate_warmap
  4.44     15.42     1.07 19330939     0.00     0.00  map_get_terrain
  4.32     16.46     1.04  2142600     0.00     0.00  sift_down
  3.90     17.40     0.94 28282301     0.00     0.00  get_unit_type
  3.24     18.18     0.78 22708405     0.00     0.00  map_get_tile
  3.11     18.93     0.75 28282209     0.00     0.00  unit_type
  3.03     19.66     0.73  7041000     0.00     0.00  
ground_unit_transporter_capacity

index % time    self  children    called     name
[10]     5.3    0.24    1.04 2142600         heap_dequeue [10]
[19]     2.4    0.57    0.00 5197800         get_from_mapqueue [19]
[20]     2.3    0.47    0.09 5184500         add_to_mapqueue [20]
[21]     2.1    0.37    0.13 2142600         heap_enqueue [21]
[27]     1.4    0.04    0.29   87300         heap_change_cost [27]

Same with heap2:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 35.83      8.31     8.31  2155900     0.00     0.01  plain_get_next_position
 24.75     14.05     5.74    13300     0.43     0.85  really_generate_warmap
  4.44     15.08     1.03 19330939     0.00     0.00  map_get_terrain
  4.10     16.03     0.95 28284301     0.00     0.00  get_unit_type
  3.58     16.86     0.83  7041600     0.00     0.00  
ground_unit_transporter_capacity
  3.54     17.68     0.82 28284209     0.00     0.00  unit_type
  3.23     18.43     0.75 22709605     0.00     0.00  map_get_tile

index % time    self  children    called     name
[12]     3.7    0.31    0.56 2142600         heap2_dequeue [12]
[17]     2.7    0.62    0.00 5197800         get_from_mapqueue [17]
[18]     2.6    0.18    0.43 2142600         heap2_enqueue [18]
[19]     2.5    0.52    0.07 5184500         add_to_mapqueue [19]
[65]     0.1    0.00    0.03   88100         heap2_change_cost [65]

Conclusions:
 - the warmap code creates a lot of map_get_terrain, get_unit_type,
 unit_type and map_get_tile calls. The path finding caches the map
 related ones and doesn't have to do the unit related ones.
 - the performance of heap, heap2 and mapqueue is comparable and not a
 big factor in the whole picture
 - we should think about caching the value of
 ground_unit_transporter_capacity in the tile for each player (+32
 bytes per tile).
 - profiles are misleading

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "The Internet is really just a series of bottlenecks 
  joined by high speed networks."
    -- Sam Wilson

path_finding14.diff.gz
Description: GNU Zip compressed data