| View previous topic :: View next topic |
| Author |
Message |
Richard Allbert
Joined: 19 Jul 2006
Posts: 678
|
 Posted: Sat Jan 28, 2012 10:31 am Post subject: Re: C# Performance |
  |
|
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.. |
|
| Back to top |
|
 |
Richard Allbert
Joined: 19 Jul 2006
Posts: 678
|
| Posted: Sat Jan 28, 2012 11:41 am Post subject: 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..
 |
|
| Back to top |
|
|
Mark Pearce
Joined: 12 Jan 2012
Posts: 61
Location: London, England
|
| Posted: Sat Jan 28, 2012 11:44 am Post subject: Re: C# Performance |
|
|
| 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. |
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.
_________________
Theory is when you know something, but it doesn't work. Practice is when something works, but you don't know why. Chess programmers combine theory and practice: Nothing works and they don't know why. |
|
| Back to top |
|
|
Marco Costalba
Joined: 14 Jun 2008
Posts: 2090
|
| Posted: Sat Jan 28, 2012 1:09 pm Post subject: Re: C# Performance |
|
|
| Richard Allbert wrote: |
| 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. |
|
| Back to top |
|
|
Lucas Braesch
Joined: 31 May 2010
Posts: 1752
|
| Posted: Sat Jan 28, 2012 1:52 pm Post subject: Re: C# Performance |
|
|
| mcostalba wrote: |
| Richard Allbert wrote: |
| 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 |
|
| Back to top |
|
|
Richard Allbert
Joined: 19 Jul 2006
Posts: 678
|
| Posted: Sat Jan 28, 2012 2:05 pm Post subject: 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. |
|
| Back to top |
|
|
Marco Costalba
Joined: 14 Jun 2008
Posts: 2090
|
| Posted: Sat Jan 28, 2012 2:30 pm Post subject: Re: C# Performance |
|
|
| Richard Allbert wrote: |
| 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. |
|
| Back to top |
|
|
Thomas Petzke
Joined: 03 Mar 2011
Posts: 263
Location: Germany
|
| Posted: Sat Jan 28, 2012 4:21 pm Post subject: Re: C# Performance |
|
|
| Quote: |
| 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... |
|
| Back to top |
|
|
Richard Allbert
Joined: 19 Jul 2006
Posts: 678
|
| Posted: Sat Jan 28, 2012 5:22 pm Post subject: 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!
| Code: |
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 |
|
| Back to top |
|
|
Sven Schüle
Joined: 15 May 2008
Posts: 2243
Location: Berlin, Germany
|
| Posted: Sat Jan 28, 2012 6:02 pm Post subject: Re: C# Performance |
|
|
| 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!
| Code: |
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: |
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 |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
