Re: [glob2-devel] gradient improvement

[Nuage]

Kai Antweiler wrote:
>>I add the fork and ran *allot* of tests! (not all displayed) Check the cvs to
>>see how your gradient is used now. (I changed only updateGlobalGradient()).
>>
>>At the end, I found out that the computations would differ :(
>>That mean there may be a problem in your computation ?
> 
> 
> I don't think so - but bugs sometimes hide were you least expect them :(
> Did it happen during GT_UNDEFINED gradient calculation?

I mean: When I run a game with USE_GRADIENT_VERSION_SIMPLE or
USE_DYNAMICAL_GRADIENT_VERSION then the game doesn't run the same way.
So the GT_UNDEFINED won't be a source of computations differences in this test.


>>Why do you compare yours with the one of Simon and not the Simple one ?
> 
> 
> I did that at the beginning, but since all algorithms handle listedAddr
> differently, an overflow would cause different results.  Simons and mine
> should put less elements into listedAddr, so I decided to check agains his
> version.  Simon said that he had already compared it against the normal one.

Based on checks, which you can enable with
"#define check_disorderable_gradient_error_probability" there is no overflow of
listedAddr in updateGlobalGradientVersionSimple().

If it ever happen, this would be in the GT_UNDEFINED case, and this is always
updateGlobalGradientVersionSimple() which computes it.

Do you have an idea where the computation get differences ?


>>Summary is that on the 128x128 map without x test case, this is 2.8% slower; 
>>and
>>on the 256x256 map with x test case this is 3.0% faster! (and as far as 
>>128x128
>>maps are fast enough, I want us to keep your code used).
> 
> 
> Might be because the big map was less crowed (relatively).
> 
> 
> 
>>Then I ran various test to see if using any specific GradientType would make a
>>difference. I noticed that the GT_RESOURCE acts quite differently, but I don't
>>know if it's because of the number of times it's called, or its statistical
>>properties.
> 
> 
> I will do statistics on the length the line segments grow (d)
> on different maps, resource types, amount of globs resources relative
> to map size, canswim value.  But this will take its time.

Right, I could run some tests on "canSwim" too.


>>ps: some tests:
> 
> 
> thanks :-)
> 
> 
>>As usually, all code is compiled with all optimization flags and run on my
>>freshly over-clocked, amd 2341mhz, 515k cache, 195mhz fsb :)
>>CFLAGS="-O3 -march=athlon-xp" CXXFLAGS="-O3 -march=athlon-xp" ./configure
>>
>>*test case 1*
>>5 runs, 128x128 map, without X:
>>time src/glob2 -nox Garden_4.test3.game
>>
>>USE_GRADIENT_VERSION_SIMPLE
>>nox:cpuSumCountStats = 20924
>>real    0m35.676s
>>real    0m35.556s
>>real    0m35.708s
>>real    0m35.814s
>>real    0m35.727s
>>sum=23465 steps
>>(median is 0m35.708s)
>>(virtualy  0m32.795s)
>>
>>USE_DYNAMICAL_GRADIENT_VESRION
>>nox:cpuSumCountStats = 20924
>>real    0m33.967s
>>real    0m33.770s
>>real    0m33.804s
>>real    0m33.626s
>>real    0m33.646s
>>sum=21551 steps
>>(median is 0m33.770s)
>>-2.81% speed (median vs median)
> 
> 
> Why are you using the user(?) time (virtualy) in the one case
> and real in the other?

Because the game differs. When I use GRADIENT_VERSION_SIMPLE the game lasts
23465 steps. But when I use DYNAMICAL_GRADIENT_VERSION then the game lasts 21551
steps.

If I compair the computation times dirrectly, then DYNAMICAL_GRADIENT_VERSION
would get and unfair advantage. The virtual time is a simple linear correction
(35.708s * 21551 / 23465). I should have computed something like a "time per
step" value.

I just started to read your code and there is one small problem. At line 2482 to
2485:

Uint8 myg = gradient[(y << wDec) | x];  // Get the gradient of the current field
Uint8 g = myg-1;   // g will be the gradient of the children.
if (g <= 2)        // All free non-source-fields start with gradient=1
        continue;  // There is no need to propagate gradient when g==2

If you test "g <= 2" instead of "myg <= 2", then you will never write gradients
with a value of "2", which can be used for pathfinding by an unit. (instead, the
values will "jump" from "1" to "3"). I haven't read the rest of the code yet.
Tell me when you want me to read it more extensively.


> Simon told me he had designed an algorithm, base on the same idea.
> But instead of using listedAddr to store fields he stored horizontal
> and vertical lines.  Gaining speed sometimes up to 40%.
> But the fusion of lines (he says) is too ugly.
> I have never seen it, however I believe a little documentation would
> cover that up.

That sounds great. Since we keep the updateGlobalGradientVersionSimple() for the
GT_UNDEFINED case, I don't care if this hard-core optimized code is a bit ugly.
Just add a new method if you want to make more tests!