C# Performance

[Richard Allbert]

Well, I've spent the morning changing some code.

First test (on laptop this time) was in the original state, 8s to do a 1.000.000x loop.

I changed the move direction lookups, which were a 2D array, to a single array (I had to add an (if piece == P) then (moveArray = moveArrayForP) in to the move generator),

and the same loop took 11s!

I then changed the move class to a structure, adding the moves to a predefined size List (original was an array), and left the adding code pretty much the same.

test took 11s again.

So no real improvement.

Next up is the piece lists, which are also 2D array, and I guess this is where the problem lies..

[Richard Allbert]

Actually you're right, in most cases the tests stayed the same, only a few required changing.

Board.GetPiece() does the same thing irrespective of the internal workings..

[RoadWarrior]

It does make the two 'mantras'

1. Don 't code for performance first
2. Build unit tests first, code after

a little conflicting, though.

The danger with that “premature optimisation is the root of all evil" phrase is that it encourages developers not to think about performance until far too late in their development cycle, and they can always point to that nice-sounding phrase as justification.

If you’re very lucky performance problems can be fixed after the fact. But as often as not, it will take a great deal of effort to get your code to where it needs to be for acceptable performance. This is a very bad trap to fall into.

Think of your chess engine as having one or more performance budgets. These are nothing more than a statement of the maximum cost that a particular feature or unit in your engine can afford to pay against each of the key performance goals. For example, if your performance goals call for perft [http://chessprogramming.wikispaces.com/Perft] 6 to complete in less than 10 seconds, then you might budget a maximum of 3 seconds each to move GEN, move MAKE, and move UNMAKE.

That 3 seconds is a very liberating number if you’re an engineer. It will help you a lot by quickly ruling out many approaches and letting you focus on the winning options.

Now once you've achieved your performance budget, don’t go the other way and micro-tune the winners. That's where "premature optimisation" really does kick-in.

Coding unit tests first is called TDD (test-driven design). In the context of a chess engine, I'm not a great fan. For example, using perft to test your move generation, make, and unmake is much faster and more accurate than creating a bunch of unit tests. Don't let the TDD zealots convince you that "best practice" is independent of context. because it most certainly isn't.

[mcostalba]

Thanks for any tips

Here are mt 2 cents:

1) Use a profiler to spot bottlenecks and don't rely on comments /suggestions on talkchess

2) Chess engines are supposed to be fast, so you should have clear in your mind how your source code is translated in machine instructions. For instance I have a clear picture for C and C++, but I don't have for C# so probably I'd not write an engine in that language before I am quite confident I understand the C# compiler.

3) Early optimization is bad, but much worst are handbook rules taken blindly as bible: most of them are pure garbage if not filtered out (and understood) with a grain of salt: use always your judgment and always ask yourself "Why am I doing this?".

4) Speed optimization: always measure, never guess.

5) Generic unit tests are useless in the context of chess engine development: much better rely some kind of perft of bench facilities to verify if a patch introduced an unwanted functionality change.

[lucasart]

Thanks for any tips

Here are mt 2 cents:

1) Use a profiler to spot bottlenecks and don't rely on comments /suggestions on talkchess

2) Chess engines are supposed to be fast, so you should have clear in your mind how your source code is translated in machine instructions. For instance I have a clear picture for C and C++, but I don't have for C# so probably I'd not write an engine in that language before I am quite confident I understand the C# compiler.

3) Early optimization is bad, but much worst are handbook rules taken blindly as bible: most of them are pure garbage if not filtered out (and understood) with a grain of salt: use always your judgment and always ask yourself "Why am I doing this?".

4) Speed optimization: always measure, never guess.

5) Generic unit tests are useless in the context of chess engine development: much better rely some kind of perft of bench facilities to verify if a patch introduced an unwanted functionality change.

100% agree

[Richard Allbert]

1. Of course, I will (and have done in the past) when appropriate.

2. Agree, I've no idea, which is the root cause

3. Again, agree and do so.

4. Agree, and do so, hence the question

5. For the C++ programs I use a file of 100 or so positions, and will do so here.

However, the tests are not useless. If perft shows an error, it can still take a long time to dig down and find it, espicially if it's obscure. A collection of simple tests proving that piece Add/Remove, Attack detect, etc are all working as expected for all possible scenarios is helpful.

[mcostalba]

Add/Remove, Attack detect, etc are all working as expected for all possible scenarios is helpful.

For these cases you may want to prefer asserts in the code, anyhow here the golden rule (that I don't always follow BTW) is: patch should be small and focused and developer should check for functionality change after each patch.

[tpetzke]

However, the tests are not useless. If perft shows an error, it can still take a long time to dig down and find it, espicially if it's obscure. A collection of simple tests proving that piece Add/Remove, Attack detect, etc are all working as expected for all possible scenarios is helpful.

It should not take so long. If you find a wrong perft score, you just calculate the sub perft values for every move and compare them with the correct sub perft values per move. You follow the path of the moves with the wrong perft score until you hit the position where perft 1 is wrong. You see exactly what move is missing or wrongly added to the move list. It helps to implement a "divide" command for that.

I wished all functionality tests related to chess engine development were so straight forward.

Thomas...

[Richard Allbert]

Right, I ran the loop with a profiler, position this time

"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1"

unfortunately the results seemed to show that everything is slow in equal measure!

Code: Select all

GenerateMoves 99.44%
    GenerateSliderMoves         27.17%
    GenerateWQSCAMoves      22.21%
       AttackedByDark                 18.68%
    GenerateWKSCAMoves      20.49%
       AttackedByDark                 17.25%
    GenerateNonSlideMoves         14.62%
    GenerateWhitePawnMoves  10.60%
      AddWhitePawnMove              5.76%     

GenerateWQSCAMoves and GenerateWKSCAMoves are the castle move generators, they check for attacks on the squares the king jumps across

In GenerateWhitePawnMoves, Add white pawn move is called if the the move is a normal pawn move as it check for promotion, and adds the four promotion moves if necessary.

I've now implemented All piece lists as singla arrays, and the movelist is literally a List<Move>()

Anyway, I'll keep digging.

Thanks

Richard

[Sven]

Right, I ran the loop with a profiler, position this time

"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1"

unfortunately the results seemed to show that everything is slow in equal measure!

Code: Select all

GenerateMoves 99.44%
    GenerateSliderMoves         27.17%
    GenerateWQSCAMoves      22.21%
       AttackedByDark                 18.68%
    GenerateWKSCAMoves      20.49%
       AttackedByDark                 17.25%
    GenerateNonSlideMoves         14.62%
    GenerateWhitePawnMoves  10.60%
      AddWhitePawnMove              5.76%

GenerateWQSCAMoves and GenerateWKSCAMoves are the castle move generators, they check for attacks on the squares the king jumps across

In GenerateWhitePawnMoves, Add white pawn move is called if the the move is a normal pawn move as it check for promotion, and adds the four promotion moves if necessary.

I've now implemented All piece lists as singla arrays, and the movelist is literally a List<Move>()

Anyway, I'll keep digging.

If GenerateMoves takes 99,44%, what is the remainder to 100%? Was it a "perft" test, or some specialized test containing movegen+make+unmake only (but no legality test or "in check")?

Can you describe what your "CanLandOrTake(board, pce, toSq)" method does (assuming it still exists, I took it from your first post in this thread)?

In the following:

Code: Select all

    GenerateWQSCAMoves      22.21%
       AttackedByDark                 18.68%

, is the 18.68% relative to GenerateWQSCAMoves (=100%), or do you have 18.68% for "AttackedByDark" + 3.53% for "Other" = 22.21%? In any case I believe that 22.21% of the whole move generation is way too much for generating one specific castle move (white queenside castling), that looks very suspicious to me. Is there some generic code used within "AttackedByDark" that is also used in other places of your move generator?

Have you tried to step through your move generator with a debugger? Sometimes this can help to understand why something is slow.

Sven