Re: [glob2-devel] gradient improvement

[Kai Antweiler]

I have done a quick hack.  I have put an initialization of the two
lists at the beginning of updateGlobalGradient, because I didn't want
to track down all the locations the listedAddr is initialized right now.

To be able to compare the results I have put a simple initialization of
the listedAddr in the same place in a reference Map.cpp that uses
the kai algorithm.

gprof show a small improvement on the WaterInTheDessert map.
(Sorry Nuage, I don't have time to test it the way you want right now.
But I'll do it when I have more time and cleaned things up.)


Here is the hacked and dirty updateGlobalGradient dealing with to lists:
(Just for inspiration)

template<typename Tint> void Map::updateGlobalGradient(Uint8 *gradient, Tint 
*listedAddr_, size_t listCountWrite_)
{
        Tint *listedEvenAddr = new Tint[size>>1];
        Tint *listedOddAddr = new Tint[size>>1];
        size_t listCountEvenWrite = 0;
        size_t listCountOddWrite = 0;

        {
                Uint8 grad;
                for (int y = 0; y < h; y++)
                        for (int x = y & 1; x < w; x += 2)
                                if (gradient[(y << wDec) | x] >= 3)
                                        listedEvenAddr[listCountEvenWrite++] = 
(y << wDec) | x;
                for (int y = 0; y < h; y++)
                        for (int x = (y + 1) & 1; x < w; x += 2)
                        {
                                size_t shifted_y = y << wDec;
                                grad = gradient[shifted_y | x];
                                if (grad >= 3)
                                {       // only list this field if it is not 
dominated from left AND right, or obove AND below
                                        if ((grad > gradient[shifted_y | 
((x-1)&wMask)]) ||
                                            (grad > gradient[shifted_y | 
((x+1)&wMask)]))
                                                if ((grad > 
gradient[(((y-1)&hMask) << wDec) | x]) ||
                                                    (grad > 
gradient[(((y+1)&hMask) << wDec) | x]))
                                                        
listedOddAddr[listCountOddWrite++] = shifted_y | x;
                                }
                        }
        }

        
        size_t listCountEvenRead = 0;
        size_t listCountOddRead = 0;
        while (listCountEvenRead + listCountOddRead < listCountEvenWrite + 
listCountOddWrite)
        {
                for (int i=listCountEvenWrite-listCountEvenRead; i>0; i--)
                {
                        Tint deltaAddrG = listedEvenAddr[listCountEvenRead++];
                        
                        size_t y = deltaAddrG >> wDec;
                        size_t x = deltaAddrG & wMask;
                        
                        size_t yu = ((y - 1) & hMask);
                        size_t yd = ((y + 1) & hMask);
                        size_t xl = ((x - 1) & wMask);
                        size_t xr = ((x + 1) & wMask);
                        
                        Uint8 g = gradient[(y << wDec) | x] - 1;
                        if (g <= 2)
                                continue;
                        
                
                        // This is the fastest version, but it's quite cryptic
                        // This is the same idea, but with the improvement idea 
of Simon.
                        Uint32 flag = 0;
                        Uint8 *addr;
                        Uint8 side;
                        {
                                const Uint32 diagFlags[4] = {9, 3, 6, 12};
                                size_t deltaAddrC[4];
                                
                                deltaAddrC[0] = (yu << wDec) | xl;
                                deltaAddrC[1] = (yu << wDec) | xr;
                                deltaAddrC[2] = (yd << wDec) | xr;
                                deltaAddrC[3] = (yd << wDec) | xl;
                                for (size_t ci = 0; ci < 4; ci++)
                                {
                                        addr = &gradient[deltaAddrC[ci]];
                                        side = *addr;
                                        if (side < g)
                                        {
                                                if (side > 0)
                                                {
                                                        *addr = g;
                                                        
listedEvenAddr[listCountEvenWrite++] = deltaAddrC[ci];
                                                }
                                                else
                                                        flag |= diagFlags[ci];
                                        }
                                }
                        }
                        {
                                size_t deltaAddrC[4];
                                
                                deltaAddrC[0] = (yu << wDec) | x ;
                                deltaAddrC[1] = (y  << wDec) | xr;
                                deltaAddrC[2] = (yd << wDec) | x ;
                                deltaAddrC[3] = (y  << wDec) | xl;
                                for (size_t ci = 0; ci < 4; ci++)
                                {
                                        addr = &gradient[deltaAddrC[ci]];
                                        side = *addr;
                                        if (side > 0 && side < g)
                                        {
                                                *addr = g;
                                                if (flag & 1)
                                                        
listedOddAddr[listCountOddWrite++] = deltaAddrC[ci];
                                        }
                                        flag >>= 1;
                                }
                        }
                }  //end of the even loop


                for (int i=listCountOddWrite-listCountOddRead; i>0; i--)
                {
                        Tint deltaAddrG = listedEvenAddr[listCountOddRead++];
                        
                        size_t y = deltaAddrG >> wDec;
                        size_t x = deltaAddrG & wMask;
                        
                        size_t yu = ((y - 1) & hMask);
                        size_t yd = ((y + 1) & hMask);
                        size_t xl = ((x - 1) & wMask);
                        size_t xr = ((x + 1) & wMask);
                        
                        Uint8 g = gradient[(y << wDec) | x] - 1;
                        if (g <= 2)
                                continue;
                        
                        size_t deltaAddrC[8];
                        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++)
                        {
                                addr = &gradient[deltaAddrC[ci]];
                                side = *addr;
                                if (side > 0 && side < g)
                                {
                                        *addr = g;
                                        if ((x+y)&1)
                                                
listedOddAddr[listCountOddWrite++] = deltaAddrC[ci];
                                        else
                                                
listedEvenAddr[listCountEvenWrite++] = deltaAddrC[ci];
                                }
                        }
                }  //end of the odd loop                
        }
        //assert(listCountWrite<=size);
}

-- 
Kai Antweiler