Re: [glob2-devel] gradient improvement

[Nuage]

Kai Antweiler wrote:
>>Alright, there is a possible problem. I did hope to keep it secret :P for the
>>sake of the performance. 
> 
> Bad choice.  That's only a waste of (my) time.  There shoud be a comment in
> code.  I knew glob2 had a documentation problem, but I didn't think this was
> intended.

That was a more like a joke. I actually forgot about my analysis of the problem.

>>5) I added some code to check how this behave. I compute the biggest size of 
>>the
>>queue at any moment of the gradient computation, and report it once per
>>gradient. Here is the result for all gradients of a game:
>>
>>listCountSizeStatsOver=0
>>listCountSizeStats:
>>[    0->  255]: 9906
>>[  256->  511]: 4244
>>[  512->  767]: 6177
>>[  768-> 1023]: 1648
>>[ 1024-> 1279]: 1802
>>[ 1280-> 1535]:    0
>>[ 1536-> 1791]:    2
>>[ 1792-> 2047]:    3
>>[ 2048-> 2303]:    0
>>[ 2304-> 2559]:    0
>>[ 2560-> 2815]:    1
>>[ 2816-> 3071]:    1
>>[ 3072-> 3327]:    2
>>[ 3328-> 3583]:    0
>>[ 3584-> 3839]:    0
>>[ 3840-> 4095]:    0
>>[ 4096-> 4351]:    0
>>[ 4352-> 4607]:    0
>>[ 4608-> 4863]:   13
>>[ 4864-> 5119]:    0
>>[ 5120-> 5375]:    3
>>[ 5376-> 5631]:    2
>>[ 5632-> 5887]:    1
>>[ 5888-> 6143]:    3
>>[ 6144-> 6399]:   15
>>[ 6400-> 6655]:    2
>>[ 6656-> 6911]:    1
>>[ 6912-> 7167]:    4
>>[ 7168-> 7423]:    0
>>[ 7424-> 7679]:    1
>>[ 7680-> 7935]:    0
>>[ 7936-> 8191]:   13
>>[ 8192-> 8447]:    0
>>[ 8448-> 8703]:    3
>>[ 8704-> 8959]:    2
>>[ 8960-> 9215]:    1
>>[ 9216-> 9471]:    1
>>[ 9472-> 9727]:    0
>>[ 9728-> 9983]:   14
>>[ 9984->10239]:    5
>>[10240->10495]:    0
>>[10496->10751]:    1
>>[10752->11007]:    1
>>[11008->11263]:    3
>>[11264->11519]:    1
>>[11520->11775]:    0
>>[11776->12031]:    0
>>[12032->12287]:    0
>>[12288->12543]:    0
>>[12544->12799]:    0
>>[12800->13055]:    0
>>[13056->13311]:    0
>>[13312->13567]:    0
>>[13568->13823]:    0
>>[13824->14079]:    0
>>[14080->14335]:    0
>>[14336->14591]:    0
>>[14592->14847]:    0
>>[14848->15103]:    0
>>[15104->15359]:    0
>>[15360->15615]:    0
>>[15616->15871]:    0
>>[15872->16127]:    0
>>[16128->16383]:    0
>>
>>The worst is 11456 over 16384. Note that it never "smash" the queue. You can
>>play with it by adding:
>>#define check_gradient_error_probability
>>in Map.h
> 
> 
> I might use this for optimization too.
> If we are cutting the size for performance we might reduce it even more,
> but we have to make sure this will not compromize crucial parts.
> What do the three number per row stand for?
These stats are made on a 128x128 map, Garden4, with 4 AICastor.
You can read the full meaning in CVS, and how it's implemented.
The first two number is the max of listCountSize in a gradient.
size_t listCountSize = listCountWrite - listCountRead;
The last number is the number of occurrences it happen to be in the range.

That mean, for instance that there where 9906 occurrences of gradient
computation where the "listCountWrite" is at worse 255 ahead of "listCountRead".


>>If you can notice any "smash", we can add a simple argument "const size_t
>>listedAddrSize" which will be big enough for everything. The method caller 
>>will
>>use a bigger size in case it may smash, like the AI. Well, maybe you want this
>>to be added now anway ? Or you see another nice solution ?
> 
> 
> I have to think about it.
> But again: I think that belongs to the AI programmers since they exactly
> know what this algorithm must tolerate and (more important) how bad the
> consequences will be.

Finally you convinced me. I think I'll fix it.