lazysmp (again)

[flok]

I can't stand it that embla still doesn't do lazy smp so again a question about it.

I think the problem is in the TT as all threads seem to be working on the same ply constantly. Also ttd only increases with more threads.

My current tt store method is:

Code: Select all

        for&#40;int i=0; i<N_TE_PER_HASH_GROUP; i++)
        &#123;
                if &#40;e&#91;i&#93;.hash == hash&#41;
                &#123;
                        if &#40;e&#91;i&#93;.age != age || e&#91;i&#93;.depth <= d || &#40;flagExact && e&#91;i&#93;.flags != EXACT&#41;)
                                useSubIndex = i;
                        else
                                 useSubIndex = -1;
                        break;
                &#125;

                if &#40;e&#91;i&#93;.age != age&#41;
                        useSubIndex = i;

                if &#40;e&#91;i&#93;.flags == NOTVALID&#41;
                        useSubIndex = i;
        &#125;

This loops iterates through a tt bucket.
If the hash is found, the following checks are done:
- different move?
- bigger depth?
- we're replacing a lower/higher bound by an exact?
If any of these is true, then replace it and stop searching. If not, don't replace and and also stop searching.

Else: if an entry is found with a different age or maybe not used at all, then remember this entry in case no hash-match is found.


This should be sane, isn't it?


regards

[mar]

It seems to me this scheme is wrong.
You should always replace if the hash matches, but you do it the other way around.
What do you replace if age is the same and hash doesn't match? (=the majority of cases for current search) You should always replace some entry no matter what.

To verify that your TT scheme is indeed the problem you could try to do something like this:
Try to always replace a "random" entry, like useSubIndex = hash % N_TE_PER_HASH_GROUP and then see if it helps

[hgm]

Not replacing is a mistake and will cause your TT to become filled with useless entries. If multiple threads are filling the TT with useless etries, it will become useless even faster, and the main thread will suffer from that. So i that respect your results are not strange.

[flok]

@martin / h.g.

But didn't I read that it is different for lazysmp?
Because one thread could have calculated an exact value and then later on be overwritten by another thread that only has calculated a bound yet.

I also tried:
if hash matches { use index }
else if (age check, virgin field check) { }
...but that made no difference.

Martin suggested to try a random index instead and that also gives no difference so it probably is then not located in the tt. Well, not in the tt store code.

[hgm]

If you want to guard against that very specific case, you should check more precisiely. I.e. refrain from replacing if the old entry has a depth that is equal or better, and a score range that falls entirely within that of the new one. (E.g. if the new one is an upper bound, the old one should have a lower upper bound or a lower exact value.)

[cdani]

But didn't I read that it is different for lazysmp?

Tt stuff works equal with and without smp on Andscacs. I don't think any change is necessary.

[Sven]

My current tt store method is:

Code: Select all

        for&#40;int i=0; i<N_TE_PER_HASH_GROUP; i++)
        &#123;
                if &#40;e&#91;i&#93;.hash == hash&#41;
                &#123;
                        if &#40;e&#91;i&#93;.age != age || e&#91;i&#93;.depth <= d || &#40;flagExact && e&#91;i&#93;.flags != EXACT&#41;)
                                useSubIndex = i;
                        else
                                 useSubIndex = -1;
                        break;
                &#125;

                if &#40;e&#91;i&#93;.age != age&#41;
                        useSubIndex = i;

                if &#40;e&#91;i&#93;.flags == NOTVALID&#41;
                        useSubIndex = i;
        &#125;

For analysis purposes you could extend this code with some counters, e.g.:

Code: Select all

static uint64_t count01 = 0;
static uint64_t count02 = 0;
static uint64_t count03 = 0;
static uint64_t count04 = 0;
static uint64_t count05 = 0;
static uint64_t count06 = 0;
static uint64_t count07 = 0;
static uint64_t count08 = 0;

// ...

int useSubIndex = -1;
for&#40;int i=0; i<N_TE_PER_HASH_GROUP; i++)
&#123;
        if &#40;e&#91;i&#93;.hash == hash&#41;
        &#123;
                if &#40;e&#91;i&#93;.age != age&#41;
                &#123;
                        ++count01;
                        useSubIndex = i;
                        break;
                &#125;
                if &#40;e&#91;i&#93;.depth <= d&#41;
                &#123;
                        ++count02;
                        useSubIndex = i;
                        break;
                &#125;
                if &#40;flagExact && e&#91;i&#93;.flags != EXACT&#41;
                &#123;
                        ++count03;
                        useSubIndex = i;
                        break;
                &#125;
                ++count04;
                useSubIndex = -1;
                break;
        &#125;

        if &#40;e&#91;i&#93;.age != age&#41;
        &#123;
                ++count05;
                useSubIndex = i;
                break;
        &#125;

        if &#40;e&#91;i&#93;.flags == NOTVALID&#41;
        &#123;
                ++count06;
                useSubIndex = i;
                break;
        &#125;

        ++count07;
&#125;
if &#40;useSubIndex == -1&#41;
&#123;
        ++count08;
&#125;

and then see which of your conditions fire how often. My expectation is that count08 gets a high value, which might lead to the conclusion that you often miss to store anything.

I think in TT store you always need to find an entry that can be used to store the new information. That decision is either easy (e.g. there is an unused entry that can be used immediately) or not so easy (e.g. existing entry has same depth). But one of the entries of your "hash group" (or bucket) should be overwritten.

The restriction to only overwrite entries that have a greater depth if they were stored as an upper or lower bound while the new entry has an exact score seems a bit unusual to me. If count04 gets a very high value then this restriction might be the reason for it.

EDIT: After rethinking I'd say the bug should now be obvious: you leave the loop immediately with a break after seeing the first entry that has a matching hash key but does not fulfill any of the three OR-ed conditions. I guess this will happen frequently.

[Ras]

You should always replace if the hash matches

I don't replace if:
- hash is the same, AND
- stored depth is higher, AND
- the stored entry either has the same flag OR is exact.

That situation can come up with iterative deepening when the stored entry is from the previous move turn with a high draft and the iterations in this move have not yet reached sufficient depth.

[flok]

For analysis purposes you could extend this code with some counters, e.g.:

Code: Select all

static uint64_t count01 = 0;
static uint64_t count02 = 0;
static uint64_t count03 = 0;
static uint64_t count04 = 0;
static uint64_t count05 = 0;
static uint64_t count06 = 0;
static uint64_t count07 = 0;
static uint64_t count08 = 0;

// ...

int useSubIndex = -1;
for&#40;int i=0; i<N_TE_PER_HASH_GROUP; i++)
&#123;
        if &#40;e&#91;i&#93;.hash == hash&#41;
        &#123;
                if &#40;e&#91;i&#93;.age != age&#41;
                &#123;
                        ++count01;
                        useSubIndex = i;
                        break;
                &#125;
                if &#40;e&#91;i&#93;.depth <= d&#41;
                &#123;
                        ++count02;
                        useSubIndex = i;
                        break;
                &#125;
                if &#40;flagExact && e&#91;i&#93;.flags != EXACT&#41;
                &#123;
                        ++count03;
                        useSubIndex = i;
                        break;
                &#125;
                ++count04;
                useSubIndex = -1;
                break;
        &#125;

        if &#40;e&#91;i&#93;.age != age&#41;
        &#123;
                ++count05;
                useSubIndex = i;
                break;
        &#125;

        if &#40;e&#91;i&#93;.flags == NOTVALID&#41;
        &#123;
                ++count06;
                useSubIndex = i;
                break;
        &#125;

        ++count07;
&#125;
if &#40;useSubIndex == -1&#41;
&#123;
        ++count08;
&#125;

and then see which of your conditions fire how often. My expectation is that count08 gets a high value, which might lead to the conclusion that you often miss to store anything.

Code: Select all

depth 13
    c1  c2    c3  c4   c5         c6 c7    c8
1: 0 51262 37 507 287134 0 30966 507
2: 0 93538 31 1025 448070 0 75020 1025
3: 0 175898 32 923 492698 0 99011 923
4: 0 280250 48 1400 615264 0 170834 1400
5: 0 294389 55 1107 523884 0 126811 1107
6: 0 338848 46 1071 532758 0 136604 1071

So c6 gets never triggered. This in hindsight to be expected: I always start a search with age++, so even for the first move that age != age matches.

What do you regard as a high value? Is this 1k hits a high value?

I think in TT store you always need to find an entry that can be used to store the new information. That decision is either easy (e.g. there is an unused entry that can be used immediately) or not so easy (e.g. existing entry has same depth). But one of the entries of your "hash group" (or bucket) should be overwritten.

The restriction to only overwrite entries that have a greater depth if they were stored as an upper or lower bound while the new entry has an exact score seems a bit unusual to me. If count04 gets a very high value then this restriction might be the reason for it.

EDIT: After rethinking I'd say the bug should now be obvious: you leave the loop immediately with a break after seeing the first entry that has a matching hash key but does not fulfill any of the three OR-ed conditions. I guess this will happen frequently.

Are you saying that a bucket should be able to store multiple entries with the same hash?
It doesn't get triggered very much by the way: 500-1500 times

For fun and kicks I replaced the flag-checker by:

Code: Select all

if ((flagExact && e[i].flags != EXACT) || f == e[i].flags)

1: 0 51262 532 12 287134 0 30945 12
2: 0 92974 946 7 423715 0 67202 7
3: 0 197129 951 4 463740 0 94564 4
4: 0 255629 2394 10 712740 0 205470 10
5: 0 303874 905 2 495376 0 118841 2
6: 0 399425 951 5 568930 0 159718 5

[Sven]

Code: Select all

depth 13
    c1  c2    c3  c4   c5         c6 c7    c8
1: 0 51262 37 507 287134 0 30966 507
2: 0 93538 31 1025 448070 0 75020 1025
3: 0 175898 32 923 492698 0 99011 923
4: 0 280250 48 1400 615264 0 170834 1400
5: 0 294389 55 1107 523884 0 126811 1107
6: 0 338848 46 1071 532758 0 136604 1071

What is the meaning of the six different rows (1: etc.)?

I always start a search with age++,

Where exactly do you increment age?

What do you regard as a high value? Is this 1k hits a high value?

Hard to say but 1k compared to 500k is not much.

EDIT: After rethinking I'd say the bug should now be obvious: you leave the loop immediately with a break after seeing the first entry that has a matching hash key but does not fulfill any of the three OR-ed conditions.

Are you saying that a bucket should be able to store multiple entries with the same hash?

No, but there can be a different entry in the same bucket that could be used for storing the data. If you don't want to do that then the only alternative I see is always overwriting an entry with matching hash key.

For fun and kicks I replaced the flag-checker by:

Code: Select all

if ((flagExact && e[i].flags != EXACT) || f == e[i].flags)

1: 0 51262 532 12 287134 0 30945 12
2: 0 92974 946 7 423715 0 67202 7
3: 0 197129 951 4 463740 0 94564 4
4: 0 255629 2394 10 712740 0 205470 10
5: 0 303874 905 2 495376 0 118841 2
6: 0 399425 951 5 568930 0 159718 5

Did you also test whether this last change (without the counters) improves strength?