Best way to debug search speed?

[konsolas]

I've just gone and refactored a large amount of my engine. Despite the NPS being similar, there has been a huge increase in my nodes-to-depth.

It's obviously unrealistic to step through the search with a debugger, and I'm not sure whether the speed drop is caused by a bug in the move ordering, or something in the search pruning.

I've been staring at the diff between the refactors, and cannot figure out for the life of me what has been changed.

What's the best way to debug search speed?

[brtzsnr]

Hi, Vincent! This won't help now, but you can try this in the future.

The way I do refactorings is like this. First every refactor should have _zero impact_ on the program's behavior (i.e. same nodes must be evaluated, in the same order, but possible faster/slower). Then I run the engine on ECM or other relatively large test positions suite and note down how many nodes were evaluated. This number should absolutely not change.

Then every incremental change I retest and verify the that the node count hasn't changed. If the node count doesn't change, then I commit the current changes. I do this until I'm satisfied with the refactor. In the end I run 'git rebase -i' to squash all commits into a large, less noisy commit which is later merged into the master branch. If at anypoint I notice a bug that was not in the original code (unlikely, but it happens) I can bisect to find the culprit change. As you see it's important to have many small incremental changes and verify each of them.

[konsolas]

Thanks for the advice Alexandru, Looks like I'll have to revert in Git and try again.

[Sven]

I've just gone and refactored a large amount of my engine. Despite the NPS being similar, there has been a huge increase in my nodes-to-depth.

It's obviously unrealistic to step through the search with a debugger, and I'm not sure whether the speed drop is caused by a bug in the move ordering, or something in the search pruning.

I've been staring at the diff between the refactors, and cannot figure out for the life of me what has been changed.

What's the best way to debug search speed?

If you have saved both the original source code version (let's call it A) and the current one (B) then you could still follow the advice given by Alexandru. Go through your changes and make a complete list of topics that you addressed, possibly grouping similar stuff together. This results in a set of N disjoint changes that should be repeatable. If there are dependencies between these changes then put them in an appropriate order. Now redo these changes step by step, starting from A, and after each single step save the resulting code version and then do as proposed by Alexandru, or at least do the same measurements that you have done now and that have told you that there must be something wrong. Always save your measurement results "old vs. new". Finally verify that the last package of changes results exactly (!) in source code version B (otherwise your list was incomplete, so you have to extend it now). Do not miss to include all of your "cosmetic" changes, as sometimes you might make 500 small "zero-impact" changes where in fact one of them has an unexpected effect.

As initial preparation step I would also ensure that all changes related directly to "measurement technology", like the way you are counting nodes or measuring time, are done first, producing a modified reference version "A1" so that you get a correct comparison starting from A1 up to B.

Even if the biggest part of this effort appearts to be wasted at a first glance, and even if you don't find the problem quickly this way, it will still help you to understand better what you really did. Apart from measuring the impact on search speed of each single change it also enables you to isolate bugs within these smaller "packages".

In addition to this method which is valid more or less for isolating all kinds of trouble that may have been introduced when making a huge amount of changes - not restricted to "search speed" stuff - there are certainly more ways to address the problem. For instance, if you have other statistical data about your search, like number of cutoffs, number of null move cutoffs, number of hash hits, you could have a look at the differences of these data between versions A1 and B, and try to find some pattern in that difference. E.g. number of hash hits decreases dramatically and everything else keeps stable => take a deeper look at all your changes related to hash table.

In my experience the behaviour that you describe indicates the introduction of at least one subtle bug.

[konsolas]

I've just gone and refactored a large amount of my engine. Despite the NPS being similar, there has been a huge increase in my nodes-to-depth.

It's obviously unrealistic to step through the search with a debugger, and I'm not sure whether the speed drop is caused by a bug in the move ordering, or something in the search pruning.

I've been staring at the diff between the refactors, and cannot figure out for the life of me what has been changed.

What's the best way to debug search speed?

If you have saved both the original source code version (let's call it A) and the current one (B) then you could still follow the advice given by Alexandru. Go through your changes and make a complete list of topics that you addressed, possibly grouping similar stuff together. This results in a set of N disjoint changes that should be repeatable. If there are dependencies between these changes then put them in an appropriate order. Now redo these changes step by step, starting from A, and after each single step save the resulting code version and then do as proposed by Alexandru, or at least do the same measurements that you have done now and that have told you that there must be something wrong. Always save your measurement results "old vs. new". Finally verify that the last package of changes results exactly (!) in source code version B (otherwise your list was incomplete, so you have to extend it now). Do not miss to include all of your "cosmetic" changes, as sometimes you might make 500 small "zero-impact" changes where in fact one of them has an unexpected effect.

As initial preparation step I would also ensure that all changes related directly to "measurement technology", like the way you are counting nodes or measuring time, are done first, producing a modified reference version "A1" so that you get a correct comparison starting from A1 up to B.

Even if the biggest part of this effort appearts to be wasted at a first glance, and even if you don't find the problem quickly this way, it will still help you to understand better what you really did. Apart from measuring the impact on search speed of each single change it also enables you to isolate bugs within these smaller "packages".

In addition to this method which is valid more or less for isolating all kinds of trouble that may have been introduced when making a huge amount of changes - not restricted to "search speed" stuff - there are certainly more ways to address the problem. For instance, if you have other statistical data about your search, like number of cutoffs, number of null move cutoffs, number of hash hits, you could have a look at the differences of these data between versions A1 and B, and try to find some pattern in that difference. E.g. number of hash hits decreases dramatically and everything else keeps stable => take a deeper look at all your changes related to hash table.

In my experience the behaviour that you describe indicates the introduction of at least one subtle bug.

It appears that you are right; the subtle bug which I was able to find after refactoring incrementally was inside SEE, which was returning results based on the start position.