Re: [glob2-devel] gradient improvement

[Kai Antweiler]

> Btw, I had a nice system to prevent bad situations at the beginning. My
> original patch replaced the creation of the first list:
> I changed
> 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;
>
> to
> 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;

> I never tested if it's really that useful. (your gprof stats seem
> pretty good, without it...) 

I would expect it to make a difference.  I just haven't seen this
because I used the Map.cpp and concentrated on updateGlobalGradient.



How about something which would omit fields which have neighbours
up and below (or left and right) with greater or equal gradient.

_|+|_
_|*|_
 |+|

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;
                Uint8 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;
                }
        }

This locks hulking but might be worth a try.  It should work because
every field which is checked for dominatating the present one belongs
to the other loop and will therefore be listed.


> But it allows Horizontal lines to be
> optimised right at the beginning. This could even be extended to have 2
> seperate lists for fields with (x+y)%2 == 0 and (x+y)%2 == 1 and then
> always process one of them first. But I don't know if that would really
> be an optimisation. I'd do some more testing about it, but i can't
> compile glob2 atm (don't have boost)... perhaps i'll have some time
> this week to install boost and make more tests.

I think the two lists method has potential.  This should be easy to
implement efficiently, since your optimization handles
diagonal-neighbours and other neighbours in different loops.
I suggest to also try your optimized method on the even list and the
normal one for the odd list.


> Nice to see that you have such impressive results, too ;-)

I thought about an architecture independent way to measure the quality
of our optimizations.  In your case we could implement a global 64-bit
counter for the sum of all listCountWrite values in total and cerr
that at the end of a mission (or put it in a logfile).  By comparing
the results of the normal implementation to optimized ones (using
"glob2 -nox" on a few maps with the different versions of glob2) we
could get further insight into the algorithm.  Thereby we could see if
an optimization is as good as we duduced from simple cases.  If it is
not - then there is no need to think about cleaning up the code to
reduce the overhead.

One thing I would like to check is how much the speed up by an
optimization differs on swim/nonswim gradient calculations.  It might
turn out that it is bad on nonswim and that Nuage used maps with alot
of water and thin long land-bridges.


> I think it is correct. At least the way I first submitted it it
> produced correct gradients in all my tests.

How did you check it?  Running both gradient calculations and compare
their result field by field?


>> ps: I like Simons algorithm
> Thanks, pleased to hear this. I just don't seem to find a clean
> implementation for it... (e.g without this cryptic and ugly flag ;-))

I had to try something different for an idea.  But this was slow
and used two boolean flags.  Your flags would be really nice if
c++ would allow to define constants in binary representation.
I would put comments like
// 9  = 1001
// 3  = 0011
// 6  = 0110
// 12 = 1100
in the code.


-- 
Kai Antweiler