[glob2-devel] Optimization suggestions (Map::updateLocalGradient())

[Erik Søe Sørensen]

Hello,
I have been doing some profiling on Globulation 2, and found some useful
results.
(I began doing this because the Ubuntu release (0.8.21) had periods of
100% CPU activity, but that seems to have been fixed :-)

Map::updateLocalGradient() seems to be a bottleneck (~40% of the time
spent there).
In this function, there are at least two opportunities for speed
improvement.

For 21% improvement (of the function's run time), get rid of the array
introduced in Map.cpp:3889:
/----
--- Map.cpp.org  2007-09-04 05:20:41.000000000 +0200
+++ Map.cpp.erk  2007-09-04 05:23:52.000000000 +0200
@@ -3886,22 +3886,17 @@
                 else
                   xr=x+1;

-                Uint8 side[8];
-                side[0]=gradient[wyu+xl];
-                side[1]=gradient[wyu+x ];
-                side[2]=gradient[wyu+xr];
-
-                side[3]=gradient[wy +xr];
-
-                side[4]=gradient[wyd+xr];
-                side[5]=gradient[wyd+x ];
-                side[6]=gradient[wyd+xl];
-
-                side[7]=gradient[wy +xl];
-
-                for (int i=0; i<8; i++)
-                  if (side[i]>max)
-                    max=side[i];
+#define UPDATE_MAX(xy) {Uint8 tmp = gradient[(xy)]; if (tmp>max) max=tmp;}
+                UPDATE_MAX(wyu+xl);
+                UPDATE_MAX(wyu+x );
+                UPDATE_MAX(wyu+xr);
+                UPDATE_MAX(wy +xr);
+                UPDATE_MAX(wyd+xr);
+                UPDATE_MAX(wyd+x );
+                UPDATE_MAX(wyd+xl);
+                UPDATE_MAX(wy +xl);
+#undef UPDATE_MAX
+
                 assert(max);
                 if (max==1)
                   gradient[wy+x]=1;
\----

For further ~9% improvement, avoid copying a Case structure in
Map.cpp:3369, still in updateLocalGradient():
/----
--- Map.cpp.org 2007-09-04 05:20:41.000000000 +0200
+++ Map.cpp.erk  2007-09-04 05:28:23.000000000 +0200
@@ -3366,7 +3366,7 @@
         for (int xl=0; xl<32; xl++)
         {
           int xg=(xl+posX-15)&wMask;
-           Case c=cases[wyg+xg];
+           Case& c=cases[wyg+xg];
           int addrl=wyl+xl;
           if (gradient[addrl]!=255)
           {
\----
(This happens at several other locations, by the way... the second-worst
place in Map.cpp appears to be in Map::updateRessourcesGradient(), and
it'might also be worth the attention :-)

And another thing, now we're at reading code:
A couple of places in Map::updateLocalGradient(), there is code like this:
        if (xxi<0)
           xxi=0;
       else if (xxi>31)
           xxi=31;
      if (yyi<0)
           yyi=0;
       else if (yyi>31)
           xxi=31; // <-- Shouldn't this be yyi??
That last line does look like a typo (or more likely a copy'n'paste error?).

Regards,
Erik Søe Sørensen

PS: Great looking game, by the way! :-)


[Profiling done on a ThinkPad, CPU: Intel(R) Pentium(R) M processor
1300MHz stepping 05]
[Today's lesson: Don't begin profiling on a non-optimized build.]