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
overkill.