Re: [glob2-devel] forums! nuag eplease read thx

[simon schuler]

Hi

address@hidden wrote:
> Very interested, but could you also try to first compute using your
> algorithm then using the old one? Indeed, there is a high probability the
> speed difference is partially due to the gradient already being cached by
> updateGlobalGradientSmallOld (thus the slowness) when
> updateGlobalGradientSmall is called (thus the fastness).
>   
I tested it both ways and it's almost the same result.
I've made a patch against 0.8.17. It's attached.
note: i have only compile-tested it with 0.8.17 because I can't compile 
the whole  release. But on 0.8.15 it worked perfectly.
I hope it doesn't interfere with nuage's new optimization...

Simon


--- ./src/Map.cpp.orig  2005-12-29 13:27:47.272807750 +0100
+++ ./src/Map.cpp       2005-12-29 14:34:56.980648750 +0100
@@ -2125,12 +2125,16 @@
 
 void Map::updateGlobalGradientSmall(Uint8 *gradient)
 {
-        Uint16 *listedAddr = new Uint16[size];
+        Uint16 listedAddr[size];
         size_t listCountWrite = 0;
         
         // make the first list:
         for (int y = 0; y < h; y++)
-                for (int x = 0; x < w; x++)
+                for (int x = y % 2; x < w; x += 2)
+                        if (gradient[(y << wDec) | x] >= 3)
+                                listedAddr[listCountWrite++] = (y << wDec) | x;
+        for (int y = 0; y < h; y++)
+                for (int x = (y + 1) % 2; x < w; x += 2)
                         if (gradient[(y << wDec) | x] >= 3)
                                 listedAddr[listCountWrite++] = (y << wDec) | x;
         
@@ -2149,20 +2153,19 @@
                 
                 Uint8 g = gradient[(y << wDec) | x] - 1;
                 
-                size_t deltaAddrC[8];
+                size_t deltaAddrC[4];
                 Uint8 *addr;
                 Uint8 side;
                 
-                deltaAddrC[0] = (yu << wDec) | xl;
-                deltaAddrC[1] = (yu << wDec) | x ;
-                deltaAddrC[2] = (yu << wDec) | xr;
-                deltaAddrC[3] = (y  << wDec) | xr;
-                deltaAddrC[4] = (yd << wDec) | xr;
-                deltaAddrC[5] = (yd << wDec) | x ;
-                deltaAddrC[6] = (yd << wDec) | xl;
-                deltaAddrC[7] = (y  << wDec) | xl;
-                for (int ci=0; ci<8; ci++)
-                {
+               //first the diagonal squares:
+               deltaAddrC[0] = (yu << wDec) | xl;
+               deltaAddrC[1] = (yu << wDec) | xr;
+               deltaAddrC[2] = (yd << wDec) | xr;
+               deltaAddrC[3] = (yd << wDec) | xl;
+               unsigned int horizFlag = 0;
+               for (int ci = 0; ci < 4; ci++)
+               {
+                       const unsigned int diagFlags[4] = {9, 3, 6, 12};
                         addr = &gradient[deltaAddrC[ci]];
                         side = *addr;
                         if (side > 0 && side < g)
@@ -2171,21 +2174,42 @@
                                 if (g > 2)
                                         listedAddr[listCountWrite++] = 
deltaAddrC[ci];
                         }
+                       else if (side == 0)
+                               horizFlag |= diagFlags[ci];
+               }
+                deltaAddrC[0] = (yu << wDec) | x ;
+                deltaAddrC[1] = (y  << wDec) | xr;
+                deltaAddrC[2] = (yd << wDec) | x ;
+                deltaAddrC[3] = (y  << wDec) | xl;
+                for (int ci=0; ci<4; ci++)
+                {
+                        addr = &gradient[deltaAddrC[ci]];
+                        side = *addr;
+                        if (side > 0 && side < g)
+                        {
+                                *addr = g;
+                                if ((g > 2) && (horizFlag & 1))
+                                        listedAddr[listCountWrite++] = 
deltaAddrC[ci];
+                        }
+                       horizFlag >>= 1;
                 }
         }
         assert(listCountWrite<=size);
-        delete[] listedAddr;
 }
 void Map::updateGlobalGradientBig(Uint8 *gradient)
 {
-        size_t *listedAddr = new size_t[size];
+        size_t listedAddr[size];
         size_t listCountWrite = 0;
         
         // make the first list:
-        for (int y = 0; y < h; y++)
-                for (int x = 0; x < w; x++)
-                        if (gradient[(y << wDec) | x] >= 3)
-                                listedAddr[listCountWrite++] = (y << wDec) | x;
+       for (int y = 0; y < h; y++)
+               for (int x = y % 2; x < w; x += 2)
+                       if (gradient[(y << wDec) | x] >= 3)
+                               listedAddr[listCountWrite++] = (y << wDec) | x;
+       for (int y = 0; y < h; y++)
+               for (int x = (y + 1) % 2; x < w; x += 2)
+                       if (gradient[(y << wDec) | x] >= 3)
+                               listedAddr[listCountWrite++] = (y << wDec) | x;
         
         size_t listCountRead = 0;
         while (listCountRead < listCountWrite)
@@ -2202,20 +2226,19 @@
                 
                 Uint8 g = gradient[(y << wDec) | x] - 1;
                 
-                size_t deltaAddrC[8];
+                size_t deltaAddrC[4];
                 Uint8 *addr;
                 Uint8 side;
-                
-                deltaAddrC[0] = (yu << wDec) | xl;
-                deltaAddrC[1] = (yu << wDec) | x ;
-                deltaAddrC[2] = (yu << wDec) | xr;
-                deltaAddrC[3] = (y  << wDec) | xr;
-                deltaAddrC[4] = (yd << wDec) | xr;
-                deltaAddrC[5] = (yd << wDec) | x ;
-                deltaAddrC[6] = (yd << wDec) | xl;
-                deltaAddrC[7] = (y  << wDec) | xl;
-                for (int ci=0; ci<8; ci++)
-                {
+
+               //first the diagonal squares
+               deltaAddrC[0] = (yu << wDec) | xl;
+               deltaAddrC[1] = (yu << wDec) | xr;
+               deltaAddrC[2] = (yd << wDec) | xr;
+               deltaAddrC[3] = (yd << wDec) | xl;
+               unsigned int horizFlag = 0;
+               for (int ci = 0; ci < 4; ci++)
+               {
+                       const unsigned int diagFlags[4] = {9, 3, 6, 12};
                         addr = &gradient[deltaAddrC[ci]];
                         side = *addr;
                         if (side > 0 && side < g)
@@ -2224,10 +2247,27 @@
                                 if (g > 2)
                                         listedAddr[listCountWrite++] = 
deltaAddrC[ci];
                         }
+                       else if (side == 0)
+                               horizFlag |= diagFlags[ci];
+               }
+                deltaAddrC[0] = (yu << wDec) | x ;
+                deltaAddrC[1] = (y  << wDec) | xr;
+                deltaAddrC[2] = (yd << wDec) | x ;
+                deltaAddrC[3] = (y  << wDec) | xl;
+                for (int ci=0; ci<4; ci++)
+                {
+                        addr = &gradient[deltaAddrC[ci]];
+                        side = *addr;
+                        if (side > 0 && side < g)
+                        {
+                                *addr = g;
+                                if ((g > 2) && (horizFlag & 1))
+                                        listedAddr[listCountWrite++] = 
deltaAddrC[ci];
+                        }
+                       horizFlag >>= 1;
                 }
         }
         assert(listCountWrite<=size);
-        delete[] listedAddr;
 }
 
 void Map::updateGlobalGradient(Uint8 *gradient)