why MapShader is so slow

Last night I was doing some profiling work and happened to be using The
Devil’s Cauldron module as my test module, when I noticed a striking
performance difference across maps. E.g., scrolling around the tiny “Little
Omaha” map is painful, while scrolling around the huge campaign map is just
fine. I did some profiling to find out what the problem was, and found that
MapShader.draw() is very slow. (The campaign map has no shading, because no
hexes are out-of-bounds, while the topmost few rows are shaded in the Little
Omaha scenario.)

MapShader.draw() has two problems: (a) we’re recalculating the whole shading
area every time we use it, and (b) we’re repainting the whole shading image
from the shading area every time we repaint. These two operations, for which
the time is almost entirely used by calls to Area.add() and Graphics2D.fill(),
respectively, each consume roughly half of the time used by MapShader.draw().
The obvious optimization would be to introduce caching. If we could cache the
results of Area.add(), that would roughly double the drawing speed, and if we
could cache the results of Graphics2D.fill() we could reduce the drawing time
to just what it takes to draw an image the size of the area.

Unfortunately, Area is extremely caching-unfriendly. Suppose that you want
to keep a cache of the results of calling Area.add(), so you keep a
Map(Pair(Area, Area), Area) for that. Unfortunately, Area doesn’t override
hashCode(), so you have to traverse the Area with a PathIterator in order
to generate a sane hash for each Area in your key. That’s not exactly fast.
Secondly, Area.equals() is extremely expensive, because it checks for equality
by taking the XOR of the two Areas and testing whether the result is empty.
That’s just as expensive as calling Area.add(), and it’s going to be called
multiple times every time you get() anything from the cache. What this
amounts to is that you can’t efficiently memoize Area.add(), because doing
so requires you to be able to efficienlty recognize Areas you’ve seen before,
which is something you can’t efficiently do. I came to this realization after
implementing a caching scheme last night; there’s no way I can see to make it
perform well, so I chucked it in the bin.

An alternative is to dump all of the shading logic into an ImageOp—we
key the ImageOp to all of the data which goes into building the Area, and
then rebuild the Area and the shaded image whenever that data changes. I
tried this, and I think it improves performance considerably.

Brent, you’ll have to try this with your TDC module and tell me what you
think. There’s an implementation of it in the svn4029 build (only). I’ve
not checked anything in because the code is ugly and needs to be cleaned
up first. I think it could also be made more efficient still by being more
selective about what data is used in building the hash key (i.e., the
ImageOp), but I’m not sure what data is relevant exactly for determining
shading. Right now, I’m using as part of the key a List containing
all of the results of getState() for ShadedPieces, which I suspect is

Hi Joel,

Optimizing Map Shading has been in the back of my mind for some time, but I never got back to it.

I don’t understand how to access svn 4029, the latest I can see is 4028?

That should work for TDC, but I don’t think will work in the general case. At the moment, the only trait that can generate shade is the Area of Effect. With a fixed radius, you only need worry about whether or not it is activated, so your scheme will work. However, with the variable radius (which should really be just a $variablename$ formattedString), then it could depend on anything as it may be referencing Zone, Map or Module properties that are outside of the unit’s state. However, for a given range, the area shaded is fixed.

In the future, there will be more complex algorithms that may depend on terrain etc. I have been looking over the shoulder of another programmer who has been playing with this. We found that generating a large (half map sheet, very inneficient) shading, 97% of the elapsed time was in Area.add(), 3% was in everything else.

The general case is that a shading shades a set of hexes, determined by some algorithm. Perhaps the hash key should depend on a sorted list of hex references? By Hex reference, I mean an internal hex reference, not the grid reference. In the terrain work I have been working on, hexes defined by a grid on a board have a fixed internal reference (basically row, column) that is independent of the grid numbering.


Brent Easton
University of Western Sydney
Email: b.easton@uws.edu.au

Messages mailing list
forums.vassalengine.org/mailman/ … engine.org

Post generated using Mail2Forum (mail2forum.com)

Thus spake “Brent Easton”:

I haven’t committed it yet. I’m talking about the build svn4029, which is
in the usual place for builds.

Is the variable value interpolated into what you receive from getState()
or not?

A sorted list of hex references would work. (A sorted list of grid references
would work, too, for that matter.) The key just needs to contain sufficient
information to reproduce the shaded image.

Should we be looking for a more general solution to this problem? The
question “what data does the image which represents me depend on”
problem keeps coming up, and caching images is pretty much the highest
impact optimization we can do.


Messages mailing list
forums.vassalengine.org/mailman/ … engine.org

Post generated using Mail2Forum (mail2forum.com)

*********** REPLY SEPARATOR ***********

On 8/08/2008 at 4:24 PM Joel Uckelman wrote:

Ok, got it. It seems to work fine.

No, the variable name is recorded in the type, it is something that doesn’t change.

A more general solution for map shading would be good. I think it is a special case. Most image caching is pretty straight-forward.


Messages mailing list
forums.vassalengine.org/mailman/ … engine.org

Post generated using Mail2Forum (mail2forum.com)