Re: [glob2-devel] Another speedup (computeColors)

[Joe Wells]

Erik Søe Sørensen <address@hidden> writes:

> Hi again,
> I said I'd look at algorithmic improvements to the gradient updating
> operations... well, I did, but I chose the wrong starting point. I've
> got some ideas to try out (most of which concern avoiding to update
> all of the map), but that'll wait a bit.
>
> For now, I've got some other spectacular result for ya :-D - a twofold
> increase in the speed of Minimap::computeColors() (on my box at least)
> :-)

Hurray!!!

Please keep going!!!

> I tried several different things, but what turned out to be the real
> problem was the use of floats (and perhaps especially the
> float-to-integer conversion which was done for each relevant map
> square).
>
> So the attached patch just replaces this with fixed-point
> computations,

This is so, like, “duh!”.  :-) ☺  If there is lots of other stuff like
that, I think you will be able to make a lot more speed improvements.

Thanks for the excellent work!!!

-- 
Joe

> and then moves some variable declarations to their
> 'proper' places (because that's nicer, for programmers and compilers
> alike :-).
>
> /Erik
> PS: Have you considered adding a '-Wall' switch or similar to the
> compiler invocation?
> (Not that I've noticed anything horrible - it's just good practise afaik)
>
> --- src/Minimap.cpp.org       2007-09-06 16:32:36.000000000 +0200
> +++ src/Minimap.cpp   2007-09-06 22:45:51.000000000 +0200
> @@ -216,22 +216,16 @@
>  
>  void Minimap::computeColors(int row, int localTeam)
>  {
> -     float dMx, dMy;
> -     int dx, dy;
> -     float minidx, minidy;
> -     int r, g, b;
> -     int nCount;
> -     int UnitOrBuildingIndex = -1;
>       assert(localTeam>=0);
>       assert(localTeam<32);
>  
> -     int terrainColor[3][3] = {
> +     const int terrainColor[3][3] = {
>               { 0, 40, 120 }, // Water
>               { 170, 170, 0 }, // Sand
>               { 0, 90, 0 }, // Grass
>       };
>  
> -     int buildingsUnitsColor[6][3] = {
> +     const int buildingsUnitsColor[6][3] = {
>               { 10, 240, 20 }, // self
>               { 220, 200, 20 }, // ally
>               { 220, 25, 30 }, // enemy
> @@ -241,44 +235,40 @@
>       };
>  
>       int pcol[3+MAX_RESSOURCES];
> -     int pcolIndex, pcolAddValue;
> -     int teamId;
> -
> -     int decSPX, decSPY;
>  
>       // get data
> -     int szX = mini_w, szY = mini_h;
> +     int szX = mini_w;
>       int decX = mini_offset_x, decY = mini_offset_y;
>  
> -     dMx=(float)(game->map.getW()) / (float)(mini_w);
> -     dMy=(float)(game->map.getH()) / (float)(mini_h);
> -
> -     decSPX=offset_x;
> -     decSPY=offset_y;
> -
> -     dy = row;
> +     // Variables for traversing each map square within a minimap square.
> +     // Using ?.16 fixed-point representation (gives a 2x speedup):
> +     const int dMx = ((game->map.getW())<<16) / (mini_w);
> +     const int dMy = ((game->map.getH())<<16) / (mini_h);
> +     const int decSPX=offset_x<<16, decSPY=offset_y<<16;
>  
>       bool useMapDiscovered = minimap_mode == ShowFOW;
>  
> -     for (dx=0; dx<szX; dx++)
> +     const int dy = row;
> +     for (int dx=0; dx<szX; dx++)
>       {
>               memset(pcol, 0, sizeof(pcol));
> -             nCount=0;
> +             int nCount = 0;
> +             int UnitOrBuildingIndex = -1;
>               
>               // compute
> -             for (minidx=(dMx*dx)+decSPX; minidx<=(dMx*(dx+1))+decSPX; 
> minidx++)
> -             {
> -                     for (minidy=(dMy*dy)+decSPY; 
> minidy<=(dMy*(dy+1))+decSPY; minidy++)
> +             for (int minidyFP=dMy*dy+decSPY; minidyFP<=(dMy*(dy+1))+decSPY; 
> minidyFP+=(1<<16)) { // Fixed-point numbers
> +                     int minidy = minidyFP>>16;
> +                     for (int minidxFP=dMx*dx+decSPX; 
> minidxFP<=(dMx*(dx+1))+decSPX; minidxFP+=(1<<16)) // Fixed-point numbers
>                       {
> -                             Uint16 gid;
> +                             int minidx = minidxFP>>16;
>                               bool seenUnderFOW = false;
>  
> -                             gid=game->map.getAirUnit((Sint16)minidx, 
> (Sint16)minidy);
> +                             Uint16 gid=game->map.getAirUnit(minidx, minidy);
>                               if (gid==NOGUID)
> -                                     
> gid=game->map.getGroundUnit((Sint16)minidx, (Sint16)minidy);
> +                                     gid=game->map.getGroundUnit(minidx, 
> minidy);
>                               if (gid==NOGUID)
>                               {
> -                                     
> gid=game->map.getBuilding((Sint16)minidx, (Sint16)minidy);
> +                                     gid=game->map.getBuilding(minidx, 
> minidy);
>                                       if (gid!=NOGUID)
>                                       {
>                                               if 
> (game->teams[Building::GIDtoTeam(gid)]->myBuildings[Building::GIDtoID(gid)]->seenByMask
>  & game->teams[localTeam]->me)
> @@ -289,8 +279,8 @@
>                               }
>                               if (gid!=NOGUID)
>                               {
> -                                     teamId=gid/1024;
> -                                     if (useMapDiscovered || 
> game->map.isFOWDiscovered((int)minidx, (int)minidy, 
> game->teams[localTeam]->me))
> +                                     int teamId=gid/1024;
> +                                     if (useMapDiscovered || 
> game->map.isFOWDiscovered(minidx, minidy, game->teams[localTeam]->me))
>                                       {
>                                               if (teamId==localTeam)
>                                                       UnitOrBuildingIndex = 0;
> @@ -312,21 +302,23 @@
>                                       }
>                               }
>                               
> -                             if (useMapDiscovered || 
> game->map.isMapDiscovered((int)minidx, (int)minidy, 
> game->teams[localTeam]->me))
> +                             if (useMapDiscovered || 
> game->map.isMapDiscovered(minidx, minidy, game->teams[localTeam]->me))
>                               {
>                                       // get color to add
> -                                     Ressource 
> r=game->map.getRessource((int)minidx, (int)minidy);
> +                                     int pcolIndex;
> +                                     Ressource 
> r=game->map.getRessource(minidx, minidy);
>                                       if (r.type!=NO_RES_TYPE)
>                                       {
>                                               pcolIndex=r.type + 3;
>                                       }
>                                       else
>                                       {
> -                                             
> pcolIndex=game->map.getUMTerrain((int)minidx,(int)minidy);
> +                                             
> pcolIndex=game->map.getUMTerrain(minidx,minidy);
>                                       }
>                                       
>                                       // get weight to add
> -                                     if (useMapDiscovered || 
> game->map.isFOWDiscovered((int)minidx, (int)minidy, 
> game->teams[localTeam]->me))
> +                                     int pcolAddValue;
> +                                     if (useMapDiscovered || 
> game->map.isFOWDiscovered(minidx, minidy, game->teams[localTeam]->me))
>                                               pcolAddValue=5;
>                                       else
>                                               pcolAddValue=3;
> @@ -341,6 +333,7 @@
>               // Yes I know, this is *ugly*, but this piece of code *needs* 
> speedup
>               unitOrBuildingFound:
>  
> +             int r, g, b;
>               if (UnitOrBuildingIndex >= 0)
>               {
>                       r = buildingsUnitsColor[UnitOrBuildingIndex][0];
>
> _______________________________________________
> glob2-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/glob2-devel