Glaurung 0.2.1: Faster Windows executable

[milix]

Hi Tord,

When I also noticed different node counts between different compiled executables of the same version I did the following:

1) I used valgrind to fix all bugs related with unitialized or partially initialized variables
2) extensively use of parenthesis for || and && operators (just don't assume anything about procedence with these!)
3) if problem still exists found about when (in node count) this happens and just log everything whithin a rage of +- 10000 nodes. Then use a diff program to find the difference and track the bug.

[Volker Annuss]

Unfortunately, there is one thing which worries me. The node count is different in all three executables, and the MSVC executable even has a different score and PV than the two others. Were all three tests done with the same hash table size? If they were, I'm afraid I have a nasty bug to hunt down.

Hello Tord,

in Hermann there are different node counts from different compilers too. It results from different implementations of the C++ function std::sort that is used for move ordering.

In the different implementations, moves with equal values are sorted in a different order.

I did not look at the glaurung source code and don't have a program to decompress .bz2 here, so I cannot verify if you use qsort or std::sort in Glaurung.

Hope that helps.

Greetings,
Volker

[Tord Romstad]

Hi Milix,

Thanks for your suggestions!

Hi Tord,

When I also noticed different node counts between different compiled executables of the same version I did the following:

1) I used valgrind to fix all bugs related with unitialized or partially initialized variables

The last time I tried, valgrind didn't work on our computers. I should probably try again, and complain to the admins if there is still a problem.

2) extensively use of parenthesis for || and && operators (just don't assume anything about procedence with these!)

I never remember the precedence of any C operators except '+' and '*', and always put lots of superfluous paranthesises everywhere. I doubt that this is the problem.

3) if problem still exists found about when (in node count) this happens and just log everything whithin a rage of +- 10000 nodes. Then use a diff program to find the difference and track the bug.

This is what I usually do in such cases, but in this case there is a problem. The different node counts appear when running different Windows compiles from the same position. I have no Windows computer avaliable for testing and debugging.

I will look for differences in node counts between Linux and Mac OS X, or between binaries compiled with different optimisation settings.

Tord

[Tord Romstad]

Hi Volker!

Unfortunately, there is one thing which worries me. The node count is different in all three executables, and the MSVC executable even has a different score and PV than the two others. Were all three tests done with the same hash table size? If they were, I'm afraid I have a nasty bug to hunt down.

in Hermann there are different node counts from different compilers too. It results from different implementations of the C++ function std::sort that is used for move ordering.

In my case the problem must be something else. I only use qsort() when picking book moves.

By the way, are you sure using sort() or qsort() in your move ordering is a good idea? I have never tried this myself, but intuitively I would guess that it is a rather inefficient thing to do. If the first move at a node fails high, you have done a lot of unnecessary work when sorting your entire move list. It seems better to leave the move list unsorted, and just loop through the list and pick the highest valued move.

I did not look at the glaurung source code and don't have a program to decompress .bz2 here, so I cannot verify if you use qsort or std::sort in Glaurung.

Apparently the .bz2 format is not as wide-spread as I thought (which is strange, because it compresses text files better than all the other formats I have tried). I have now changed the source code download to a .tar.gz file. This makes it slightly bigger, but I suppose a 36 KB download is still acceptable.

Tord

[Dann Corbit]

{snip}
By the way, are you sure using sort() or qsort() in your move ordering is a good idea? I have never tried this myself, but intuitively I would guess that it is a rather inefficient thing to do. If the first move at a node fails high, you have done a lot of unnecessary work when sorting your entire move list. It seems better to leave the move list unsorted, and just loop through the list and pick the highest valued move.
Tord

You can use quickselect to partition the hot ones on top (maybe top 3 or 4) and then sort those 3-4 items with a very few operations. You can almost never go wrong with that.

Code: Select all

// Quickselect: find Kth smallest of first N items in array A
// recursive routine finds Kth smallest in A[Low..High]
// Etype: must have copy constructor, oeprator=, and operator<

template < class Etype >
void
QuickSelect (Etype A[], int Low, int High, int k)
{
    if (Low + Cutoff > High)
        InsertionSort (&A[Low], High - Low + 1);
    else
    {
// Sort Low, Middle, High
        int Middle = (Low + High) / 2;

        if (A[Middle] < A[Low])
            Swap (A[Low], A[Middle]);
        if (A[High] < A[Low])
            Swap (A[Low], A[High]);
        if (A[High] < A[Middle])
            Swap (A[Middle], A[High]);

// Place pivot at Position High-1
        Etype Pivot = A[Middle];
        Swap (A[Middle], A[High - 1]);

// Begin partitioning
        int i, j;
        for (i = Low, j = High - 1;;)
        {
            while (A[++i] < Pivot);
            while (Pivot < A[--j]);
            if (i < j)
                Swap (A[i], A[j]);
            else
                break;
        }

// Restore pivot
        Swap (A[i], A[High - 1]);

// Recurse: only this part changes
        if (k < i)
            QuickSelect (A, Low, i - 1, k);
        else if (k > i)
            QuickSelect (A, i + 1, High, k);
    }
}


template < class Etype >
void
QuickSelect (Etype A[], int N, int k)
{
    QuickSelect (A, 0, N - 1, k - 1);
}



[Harald Lüßen]

Code: Select all

// Quickselect: find Kth smallest of first N items in array A
// recursive routine finds Kth smallest in A[Low..High]
// Etype: must have copy constructor, oeprator=, and operator<

template < class Etype >
void
QuickSelect (Etype A[], int Low, int High, int k)

template < class Etype >
void
QuickSelect (Etype A[], int N, int k)


How does this compare to standard C++
std::partial_sort(beg,sort_beg,end);
std::partial_sort(beg,sort_beg,end,cmp);
std::partial_sort_copy(src_beg,src_end,dest_beg, dest_end);
std::partial_sort_copy(src_beg,src_end,dest_beg, dest_end,cmp);

And how does it compare to not sorting at all and picking
the next element?

Harald

[Volker Annuss]

By the way, are you sure using sort() or qsort() in your move ordering is a good idea? I have never tried this myself, but intuitively I would guess that it is a rather inefficient thing to do. If the first move at a node fails high, you have done a lot of unnecessary work when sorting your entire move list. It seems better to leave the move list unsorted, and just loop through the list and pick the highest valued move.

Hi Tord,

Hermann leaves the list unsorted for PV move, killer moves and some captures. Sorting in only done, when there is a high chance that no cutoff occurs.

Greetings,
Volker

[José Carlos]

By the way, are you sure using sort() or qsort() in your move ordering is a good idea? I have never tried this myself, but intuitively I would guess that it is a rather inefficient thing to do. If the first move at a node fails high, you have done a lot of unnecessary work when sorting your entire move list. It seems better to leave the move list unsorted, and just loop through the list and pick the highest valued move.

Hi Tord,

Hermann leaves the list unsorted for PV move, killer moves and some captures. Sorting in only done, when there is a high chance that no cutoff occurs.

Greetings,
Volker

If no cutoff occurs, sorting is wasted time. Some people (not me) try picking the first 3 or 4 and, after that, assume cutoff is not probable and search the rest of the moves without any sorting, which saves some time.
However, the cost of sorting must be tiny compared to the cost of having to search all moves, so maybe it doesn't make any difference after all.

[Dann Corbit]

Code: Select all

// Quickselect: find Kth smallest of first N items in array A
// recursive routine finds Kth smallest in A[Low..High]
// Etype: must have copy constructor, oeprator=, and operator<

template < class Etype >
void
QuickSelect (Etype A[], int Low, int High, int k)

template < class Etype >
void
QuickSelect (Etype A[], int N, int k)


How does this compare to standard C++
std::partial_sort(beg,sort_beg,end);
std::partial_sort(beg,sort_beg,end,cmp);
std::partial_sort_copy(src_beg,src_end,dest_beg, dest_end);
std::partial_sort_copy(src_beg,src_end,dest_beg, dest_end,cmp);

And how does it compare to not sorting at all and picking
the next element?

Harald

Quickselect is linear time O(n) just like not sorting at all and picking the top element.

The implementation I supplied here is a kind of crappy one (that I just happened to find first). I have posted much better versions elsewhere. At any rate, it illustrated the idea easily. You can approximately sort items (putting the best N at the top) in linear time. If you make N=1, then you have the very standard method of searching the pile for the top thing.

I like to use N=3, because it is quite unusual to have the best move not be in the top 3.

It is stupendously faster than sorting, when you have high mobility situations.