Re: [glob2-devel] gradient improvement

[Nuage]

I did apply and committed the patch, thanks for it. I added access to the the
kind of gradient being computed too. I put every computation mode into one
function, so it's ready for dynamic optimization too (see below). See CVS.


>>>The algorithm depends on the order in which
>>>fields that need to be processed are listed.
> 
> I forgot that Simon's algorithm already "repairs" the local order in
> which the fields will be listed by inserting the diagonal neighbours
> before the others.
> In fact that was one of the smart things that I liked about his
> algorithm.

I'm sorry, but I still didn't get the overall idea. It's not mandatory that you
explain it to me, but if you send me things I'll read them.


>>>But Simon has an idea to partition the map like a chess board into
>>>let's say white and black fields.  
> 
> After what you explained to me about the cache, I am no longer sure
> that this will be beneficial.  I'll try it anyway.
> (my mail took about one week till it appeared in the mailing list)
> 
> I always thought Simon's algorithm outperformed my own, because it
> was designed smarter.
> In my own implementations I included the direction in which the
> gradient spreads.  For this I needed additional arrays, and this
> resulted in worse cache usage.  I tried to limit the number of
> operations, but of course this didn't gain anything.

>From what I measure, what I think and what I extrapolate, we a limited by two
factors (at least on my CPU):
1- the execution speed of branches, the "if".
2- the memory bandwidth.
For these reasons the my algorithm is optimized on the number of branches, and
the number of array calls. But I may be wrong. I encourage other tries,
scientific analysis and measurement, as well as reporting the results on the ML.


> But I have two ideas which might use the cache better:
> 
> 1. When initializing the array listedAddr, omit the fields
> which have a right and left neighbour of same or higher gradient value,
> if these will be put in the list.  This uses only information which
> just was processed or will be in the next step.
> Since resources tend to cluster, also checking for upper and lower
> values wouldn't gain much.
> (The idea is that every neighbour of the omited field, is also
> neighbouring one of the other two fields.)

This can work, if the extra computation time needed is smaller than the saved
computation time of the gradient algorithm. There is a chance it works, and a
chance it doesn't. So just try it.


> 2. In updateGlobalGradient:  check if the next field in listedAddr
> is my right neighbour.  If it is, check if the next one is its right
> reighbour. And so on ...
> And then process that whole part of the line.
> You also would have to check, if the right neighbour has the same
> gradient value as you.
> 
> Why is it possible to have so different gradient values in field which
> are in listedAddr?
> I would expect only two values:
> the present one and the present one minus one

Same remark.


>>What about processing the various gradient differently depending on its type ?
>>For instance, we have at least 3 types:
>>1- resources gradients
>>2- buildings gradients
> 
> Has each building its own gradient?

Yes, when needed. There is a quite complex system to avoid gradient
(re)-computation as much as possible. Roughly, an unit first tries to use a
smaller gradient around the building (32x32), then use the already computed big
gradient, and last, recompute a gradient. You can see all related logs into
Map.log. The names are pathToBuildingCount* and can be found in Map.h/cpp too.


>>3- forbidden gradients
> 
> What do we need forbidden gradients for?
> Is this a gradient which will be initialized from every free
> non-forbidden field?
> So that a glob on a forbidden field can find a way out.

Exactly, this is a "negative" gradient, as this is the way for an unit to get
out of the forbidden areas, as fast as possible.


>>Theirs statical behaviors are different, and there is probably some speed to 
>>be gained out of it.
>>If you think it's useful, I can add structure in the code, so you can access 
>>this information. Then I'll let you try to take this into account.
> 
> 
> Might be useful.
> But I must know more of their differences to exploit them.

What more do you need to know ? I don't know much about them :D

1- the resource gradients have big "255" sources, which starts at various
places, which are usually round and may often meet other gradients starting.

2- the building gradients have only one "small" source. The gradient probably
spread out most likely in a "circle" (which is a square in our non-euclidean 
space).

3- the forbidden gradients has huge sources, and small free areas.

4- the guard area gradients (I forgot about this one!), it can have many shapes.

The idea is this: Maybe my gradient algorithm is faster for resources and yours
is for buildings. If we use a different algorithm for each case, we'll get an
overall faster algorithm.

We could use the "canSwim" boolean too. The problem is that it depends on the
kind of maps.

To get more infos, we need to collect statical values. That mean, create
variable and count the number of times such a situation exists. This may be a
good thing to try to check if your thought about the statistical behavior of the
gradient propagation is true or not.

Over the static optimization, we can use the dynamical optimization. It's a
really cool idea:
1- For some time, you try each gradient computation system. Doing so you collect
speed measurement, in order to find out which is the fastest one, given the type
of gradient.
2- After some time, you only use the fastest gradient.
3- Optionally you can retry another measurement time.
This way, the gradient computation way will automatically adapt to the CPU and
map. I have put the structure so it's ready for such an use. I'll maybe try a
few things with it another day.

Nuage