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..
C# Performance
Moderators: hgm, Rebel, chrisw
-
- Posts: 792
- Joined: Wed Jul 19, 2006 9:58 am
Re: C# Performance
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..
Board.GetPiece() does the same thing irrespective of the internal workings..
-
- Posts: 73
- Joined: Fri Jan 13, 2012 12:39 am
- Location: London, England
Re: C# Performance
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.Richard Allbert wrote:It does make the two 'mantras'
1. Don 't code for performance first
2. Build unit tests first, code after
a little conflicting, though.
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.
There are two types of people in the world: Avoid them both.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: C# Performance
Here are mt 2 cents:Richard Allbert wrote: Thanks for any tips
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.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: C# Performance
100% agreemcostalba wrote:Here are mt 2 cents:Richard Allbert wrote: Thanks for any tips
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.
-
- Posts: 792
- Joined: Wed Jul 19, 2006 9:58 am
Re: C# Performance
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.
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.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: C# Performance
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.Richard Allbert wrote:Add/Remove, Attack detect, etc are all working as expected for all possible scenarios is helpful.
-
- Posts: 686
- Joined: Thu Mar 03, 2011 4:57 pm
- Location: Germany
Re: C# Performance
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.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.
I wished all functionality tests related to chess engine development were so straight forward.
Thomas...
-
- Posts: 792
- Joined: Wed Jul 19, 2006 9:58 am
Re: C# Performance
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!
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
"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%
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
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: C# Performance
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")?Richard Allbert wrote: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!
GenerateWQSCAMoves and GenerateWKSCAMoves are the castle move generators, they check for attacks on the squares the king jumps acrossCode: 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%
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.
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%
Have you tried to step through your move generator with a debugger? Sometimes this can help to understand why something is slow.
Sven