[Numpy-discussion] Optimization advice

[John Eikenberry]

After getting some advice off the pygame list I think I have a pretty
good version of my influence map now. I thought someone on this list
might be interested or at least someone checking the archives.

The new and improved code is around 6-7x faster. The main gain was
obtained by converting all the array functions to slice notation and
eliminating most of the needless copying of arrays. 

The new version is attached and is much better commented. It is also
unabridged, as it was pointed out that it wasn't entirely clear what was
going on in the last (edited) version. Hopefully things are more obvious
in this one.

Anyways... I just hating leaving a thread without a conclusion. Hope
someone finds this useful.

-- 

John Eikenberry
[jae at zhar.net - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin
-------------- next part --------------
# /usr/bin/env python
#
# John Eikenberry <jae at zhar.net>

from Numeric import *
from types import *

FACTOR = array(6.).astype(Float32)
EDGE_MOD = array(0.66).astype(Float32)
ONE = array(1.).astype(Float32)
ZERO = array(0.).astype(Float32)

class InfluenceMap: 
    """ 

    There are 2 primary ways to setup the influence map, either might be useful
    depending on your needs. The first is to recreate the map each 'turn' the
    second is to keep the map around and just update it each turn. The first
    way is simple and easy to understand, both in terms of tweaking and later
    analysis. The second gives the map a sense of time and allows for fewer
    iterations of the spreading algorithm per 'turn'. 

    Setting up the map to for one or the other of these is a matter of tweaking
    the code. There are 3 main bits of code which are described below and
    indicated via comments in the code.
    
    First some terminology:

    - weightmap stores the current influence map
    - neighbors is used as the memory buffer to calculate a the influence
      spreading
    - constmap contains a map with only the unit's scores present
    - when I refer to a 'multi-turn map' I mean using one instance of the
      influence map throughout the game without resetting it.

    [1] neighbors *= ZERO

        At the end of each iteraction, the neighbors take on the values of the
        weightmap from the previous step. This will reset those values to
        zero.

        This has a 1% performance hit.

    [2] putmask(neighbors,constmap,constmap)

        This keeps the values of the units hexes constant through all
        iterations.

        This results in about a 40% performance hit. This needs improvement.

    [3] setDecayRate([float])
        
        This is meant to be used with a multi-turn map. It sets the floating
        point value (N>0.0<1.0)which is used on the map each turn to modify
        the current map before the influence spreading. 

        No performance hit.

    If just [1] used then it will cause all influence values to decend
    toward zero. Not sure what this would be useful for, just documenting the
    effect.

    If [1] is not used (commented out) then the map values will never balance
    out, rising with each iteration. This is fine if you plan on resetting the
    influence map each turn. Allowing you to tweak the number of iterations to
    get the level of values you want. But it would cause problem with a
    multi-turn map unless [3] is used to keep this in check. 
        
    Using [2] without [1] will accellerate the rising of the values described
    above. It will also lead to more variation amoung the influence values
    when using fewer iterations. High peaks and steep sides. Using neither [1]
    nor [2] the peaks are much lower.

    If [1] and [2] are both used the map will always attain a point of balance
    no matter how many iterations are run. This is desirable for maps used
    throughout the entire game (multi-turn maps) for obvious reasons. Given the
    effect of [1] this also limits the need for [3] as the influence values in
    areas of the map where units are no longer present will naturally decrease.
    Though the decay rate may still be useful for tweaking this.
    
    """

    _decay_rate = None

    def __init__(self,hex_map):
        """ hex_map is the in game (civl) map object """
        self.map_size = map_size = hex_map.size
        ave_size = (map_size[0] + map_size[1])/2
        self._iterations = ave_size/2
        # is the hex_map useful for anything other than size?
        self.hex_map = hex_map

        # weightmap == influence map
        self.weightmap = weightmap = zeros((map_size[0],map_size[1]),Float32)
        # constmap == initial unit locations
        self.constmap = zeros((map_size[0],map_size[1]),Float32)

    def setUnitMap(self,units):
        """ Put unit scores on map 
            -units is a list of (x,y,score) tuples
             where x,y are map coordinates and score is the units influence
             modifier
        """
        weightmap = self.weightmap
        constmap = self.constmap
        constmap *= ZERO
        # mayby use the hex_map here to get terrain effects?
        for (x,y,score) in units:
            weightmap[x,y] = score
            constmap[x,y]=score

    def setInterations(self,iterations):
        """ Set number of times through the influence spreading loop """
        assert type(iterations) == IntType, "Bad arg type: setIterations([int])"
        self._iterations = iterations

    # [3] above
    def setDecayRate(self,rate):
        """ Set decay rate for a multi-turn map. """
        assert type(rate) == FloatType, "Bad arg type: setDecayRate([float])"
        self._decay_rate = array(rate).astype(Float32)

    def reset(self):
        """ Reset an existing map back to zeros """
        map_size = self.map_size
        self.weightmap = zeros((map_size[0],map_size[1]),Float32)

    def step(self,iterations=None):
        """ One set of loops through influence spreading algorithm """
        # save lookup time
        constmap = self.constmap
        weightmap = self.weightmap
        if not iterations:
            iterations = self._iterations

        # decay rate can be used when the map is kept over duration of game,
        # instead of a new one each turn. the old values are retained,
        # degrading slowly over time. this allows for fewer iterations per turn
        # and gives sense of time to the map. its experimental at this point.
        if self._decay_rate:
            weightmap = weightmap * self._decay_rate

        # It might be possible to pre-allocate the memory for neighbors in the
        # init method. But I'm not sure how to update that pre-allocated array.
        neighbors = weightmap.copy()
        # spread the influence
        while iterations:
            # [1] in notes above
#            neighbors *= ZERO
            # diamond_hex layout
            neighbors[:-1,:] += weightmap[1:,:] # shift up
            neighbors[1:,:] += weightmap[:-1,:] # shift down
            neighbors[:,:-1] += weightmap[:,1:] # shift left
            neighbors[:,1:] += weightmap[:,:-1] # shift right
            neighbors[1::2][:-1,:-1] += weightmap[::2][1:,1:] # hex up (even)
            neighbors[1::2][:,:-1] += weightmap[::2][:,1:] # hex down (even)
            neighbors[::2][:,1:] += weightmap[1::2][:,:-1] # hex up (odd)
            neighbors[::2][1:,1:] += weightmap[1::2][:-1,:-1] # hex down (odd)
            # keep influence values balanced
            neighbors *= (ONE/FACTOR)
            
            # [2] above - maintain scores in unit hexes
#            putmask(neighbors,constmap,constmap)

            # 'putmask' adds almost 40% to the overhead. There should be a
            # faster way. A little testing seems to show that this problem is
            # related to the usage of floats for the map values. 

            # prepare for next iteration
            weightmap,neighbors = neighbors,weightmap
            iterations -= 1

        # save for next turn
        self.weightmap = weightmap