Perft speed optimization (renamed)

[mvanthoor]

I'm an idiot. Working with Rust for too long and not touched C in years. I completely forgot to look into the "src"-folder, as Rust by default compiles from the root (one level up from "src"). I ran perft 7 from the starting position... and while I improved my time with about 13 seconds to drop about a second under your _PREVIOUS_ version I've tested, you're now 8.5 seconds ahead again:

Code: Select all

Marcel@WORKSTATION MINGW64 /c/Code/weiss/src
$ ./weiss-dev.exe
perft 7 rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Starting perft to depth 7

move 1 : a2a3 : 106743106
move 2 : b2b3 : 133233975
move 3 : c2c3 : 144074944
move 4 : d2d3 : 227598692
move 5 : e2e3 : 306138410
move 6 : f2f3 : 102021008
move 7 : g2g3 : 135987651
move 8 : h2h3 : 106678423
move 9 : a2a4 : 137077337
move 10 : b2b4 : 134087476
move 11 : c2c4 : 157756443
move 12 : d2d4 : 269605599
move 13 : e2e4 : 309478263
move 14 : f2f4 : 119614841
move 15 : g2g4 : 130293018
move 16 : h2h4 : 138495290
move 17 : b1a3 : 120142144
move 18 : b1c3 : 148527161
move 19 : g1f3 : 147678554
move 20 : g1h3 : 120669525

Perft complete:
Time  : 78494ms
Leaves: 3195901860
LPS   : 40715237

You hit 40 million leaves/s in 78.5 seconds. Congrats: another 10% speedup since last time.
I'm now doing 36.7 million leaves/s in 87.1 seconds (which is about 1.5 seconds faster than the _previous_ version of Weiss I tested) on this system; and at the time, _that_ version was also ahead of Rustic by 8-9 seconds or thereabouts.

Since I began in this thread, I gained about 30% speed in move generation/make/unmake, so it has been worth it.

I don't know where I can gain another 8+ seconds. Everything I do now makes the code slower.

- Replace clear/set-bit with square bitboards and the |= and ^= trick: -10%
- REMOVE 4 asserts that erronously got left in as an array bound check: -12%
- NOT doing gamestate updates (move counter and such) if the move is illegal (because they'll be reverted anyway), i.e. returning the function early on an illegal move: -12%
- Fold the rook capture code into the castle perms array code: slower by 10-15% (varies)
- Even compiling code into the engine that isn't used during perft (the console) makes it slower by at least 10%.

I can't control this.

It probably has to do with memory alignment and related things as discussed earlier in this topic. It's not logical that when I return early from make() when the move is illegal, which omits doing certain steps, is SLOWER than actually doing the superfluous steps and THEN returning. It's not only slower in the start position (where there aren't many illegal moves), but in all positions I've tested.

Maybe if I just finish the search and UCI functionality, and then try again... as said, it seems that speedup tricks become usable when the code gets bigger. In the beginning, the to ^ 8 trick didn't work (slower), and the CastlePerms update didn't either (slower); now the to ^ 8 trick for EP does work (a second or two gain), and the CastlePerms array is now equal to what I had before, but with less code.

[Terje]

...

You hit 40 million leaves/s in 78.5 seconds. Congrats: another 10% speedup since last time.
I'm now doing 36.7 million leaves/s in 87.1 seconds (which is about 1.5 seconds faster than the _previous_ version of Weiss I tested) on this system; and at the time, _that_ version was also ahead of Rustic by 8-9 seconds or thereabouts.

Since I began in this thread, I gained about 30% speed in move generation/make/unmake, so it has been worth it.

Thanks, and thanks for testing!

Speeding up your engine is well worth it as it benefits you greatly when you get to playing test matches. You can use shorter time controls while keeping the searches as deep as before, or use the same time and get deeper searches which better correlates to long time control strength.

[mvanthoor]

Even when you think it can't be made any faster, you can still combine some if-statements and find a few straggling instructions here or there that can be removed...

Since yesterday, perft 7 from the starting position dropped from 87.2 to 84.2 seconds. KiwiPete position dropped from 223 seconds to 212. (It ran at 231 seconds three days ago.) KiwiPete is a good position to test perft speed; better than the starting position, because it is more realistic and tests more code paths. A very small speedup in Perft, such as 3 seconds, can have a great effect on more difficult positions such as KiwiPete.

Startpos Perft 7: 84.2 vs 87.2 = 3.5% speedup since yesterday.
Startpos Perft 7: 84.2 vs. 89.5 = 6% speedup since three days ago.

Kiwipete Perft 6: 212 vs 223 = 5% speedup since yesterday.
Kiwipete Perft 6: 212 vs 231 = 8.3% speedup since three days ago.

Code: Select all

Benchmarking perft 1-7:

8   r n b q k b n r
7   i i i i i i i i
6   . . . . . . . .
5   . . . . . . . .
4   . . . . . . . .
3   . . . . . . . .
2   I I I I I I I I
1   R N B Q K B N R

    A B C D E F G H

Zobrist key:        819aa694337673fb
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (5 ms, 39456200 leaves/sec)
Perft 5: 4865609 (129 ms, 37717899 leaves/sec)
Perft 6: 119060324 (3223 ms, 36940838 leaves/sec)
Perft 7: 3195901860 (84266 ms, 37926350 leaves/sec)
Total time spent: 87623 ms
Execution speed: 37889987 leaves/second


===================================================

Benchmarking perft 1-6:

8   r . . . k . . r
7   i . i i q i b .
6   b n . . i n i .
5   . . . I N . . .
4   . i . . I . . .
3   . . N . . Q . i
2   I I I B B I I I
1   R . . . K . . R

    A B C D E F G H

Zobrist key:        fb86acbc2034870e
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Perft 1: 48 (0 ms, inf leaves/sec)
Perft 2: 2039 (0 ms, inf leaves/sec)
Perft 3: 97862 (2 ms, 48931000 leaves/sec)
Perft 4: 4085603 (107 ms, 38183205 leaves/sec)
Perft 5: 193690690 (5131 ms, 37749111 leaves/sec)
Perft 6: 8031647685 (212537 ms, 37789409 leaves/sec)
Total time spent: 217777 ms
Execution speed: 37788765 leaves/second

One thing I find strange is that board.swap_side() at the end of make() takes quite some time. I was doing this before testing legality. If the move is not legal, everything is reversed, so swapping sides before this test would be unneeded. I have changed make() to return early and do swap_side() only after the legality check.

It made absolutely no difference.

Even taking swap_side() out of make() and doing it in perft after a legal move, made no difference.

I wonder if I can ever reach Weiss' 78.5 seconds without actually improving the move generator (as in, generate less moves to check). I'm running out of idea's. Some of the optimizations Weiss has don't work in my engine. I have some things that Weiss doesn't have; and when I try those in Weiss, it gets slower.

I've also quickly tested LLD. There are now three possibilities to compile on Windows; in decreasing speed order for running perft 7:

GNU toolchain + GNU LD: 84.2 seconds
MSVC toolchain + LLVM LLD: 85.x
MSVC toolchain + MS Link.exe: 88.x seconds.

(Unexpected enough, LLD doesn't play nice when using the GNU toolchain.)

[mvanthoor]

Well, it has been a good evening for Rustic

In unmake(), I popped the board state from history into a separate variable, used it to set my flags for the move, and then at the end of the function I copied it into board.game_state. I *thought* the compiler would optimize that intermediate variable away, but in this case it didn't.

I now pop the history directly into board.game_state, and set my move bits from there. It dropped perft 7 into the from 84.2 into the 80.xx range, and the KiwiPete position went from 212 in the previous post to 205.9 seconds now.

Startpos perft 7 since last post: 80.8 vs 84.2 : 4.1% improvement.
Kiwipete perft 6 since last post: 205.9 vs 212.0 : 2.9% improvement.

In just two optimization rounds, perft 6 on the kiwipete position dropped from 231 to 206 seconds; about 11% improvement. Since I started this thread, startpos perft 7 improved by 33%, just by tinkering with make() and unmake()

Code: Select all

Benchmarking perft 1-7:

8   r n b q k b n r
7   i i i i i i i i
6   . . . . . . . .
5   . . . . . . . .
4   . . . . . . . .
3   . . . . . . . .
2   I I I I I I I I
1   R N B Q K B N R

    A B C D E F G H

Zobrist key:        819aa694337673fb
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (5 ms, 39456200 leaves/sec)
Perft 5: 4865609 (126 ms, 38615944 leaves/sec)
Perft 6: 119060324 (3077 ms, 38693637 leaves/sec)
Perft 7: 3195901860 (80871 ms, 39518515 leaves/sec)
Total time spent: 84079 ms
Execution speed: 39487082 leaves/second

=========================================

Benchmarking perft 1-6:

8   r . . . k . . r
7   i . i i q i b .
6   b n . . i n i .
5   . . . I N . . .
4   . i . . I . . .
3   . . N . . Q . i
2   I I I B B I I I
1   R . . . K . . R

    A B C D E F G H

Zobrist key:        fb86acbc2034870e
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Perft 1: 48 (0 ms, inf leaves/sec)
Perft 2: 2039 (0 ms, inf leaves/sec)
Perft 3: 97862 (2 ms, 48931000 leaves/sec)
Perft 4: 4085603 (106 ms, 38543424 leaves/sec)
Perft 5: 193690690 (5009 ms, 38668534 leaves/sec)
Perft 6: 8031647685 (205993 ms, 38989905 leaves/sec)
Total time spent: 211110 ms
Execution speed: 38982160 leaves/second

[Terje]

Nice progress, I'll have to find something else to improve to keep my lead

Out of curiosity, how does weiss compare on the kiwipete position on your machine?

[mvanthoor]

Nice progress, I'll have to find something else to improve to keep my lead

Out of curiosity, how does weiss compare on the kiwipete position on your machine?

Between work and dinner I merged the |= and ^= trick (BB_SQUARES bitboards instead of setbit and clearbit) into the engine and ran a quick test. I tried it before, but it didn't work back then. However, after the previous optimization round it now does seem to work. The speedup is tiny, but consistent. Startpos perft 7 is now 79 seconds, +/- half a second; exactly the same as Weiss. Both engines are hitting 40M positions/second.

Rustic startposition Perft 7: 79.xx seconds

Code: Select all

Benchmarking perft 1-7:

8   r n b q k b n r
7   i i i i i i i i
6   . . . . . . . .
5   . . . . . . . .
4   . . . . . . . .
3   . . . . . . . .
2   I I I I I I I I
1   R N B Q K B N R

    A B C D E F G H

Zobrist key:        819aa694337673fb
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (5 ms, 39456200 leaves/sec)
Perft 5: 4865609 (121 ms, 40211644 leaves/sec)
Perft 6: 119060324 (2998 ms, 39713250 leaves/sec)
Perft 7: 3195901860 (79190 ms, 40357391 leaves/sec)
Total time spent: 82314 ms
Execution speed: 40333775 leaves/second

The BB_SQUARES trick dropped just barely a second off of the startposition perft, but it did drop another 11 seconds from the KiwiPete position. It now runs at 201.xx seconds (yesterday: 212 seconds). Speedup: 5.2%. I also tested Weiss. It runs at 211.xx seconds.

Rustic, KiwiPete perft 6: 201.xx seconds

Code: Select all

Benchmarking perft 1-6:

8   r . . . k . . r
7   i . i i q i b .
6   b n . . i n i .
5   . . . I N . . .
4   . i . . I . . .
3   . . N . . Q . i
2   I I I B B I I I
1   R . . . K . . R

    A B C D E F G H

Zobrist key:        fb86acbc2034870e
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Perft 1: 48 (0 ms, inf leaves/sec)
Perft 2: 2039 (0 ms, inf leaves/sec)
Perft 3: 97862 (2 ms, 48931000 leaves/sec)
Perft 4: 4085603 (102 ms, 40054931 leaves/sec)
Perft 5: 193690690 (4861 ms, 39845852 leaves/sec)
Perft 6: 8031647685 (201737 ms, 39812467 leaves/sec)
Total time spent: 206702 ms
Execution speed: 39813470 leaves/second

Weiss, KiwiPete perft 6: 211.xx seconds

Code: Select all

$ ./weiss-dev.exe
perft 6 r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

Starting perft to depth 6

move 1 : g2h3 : 158328615
move 2 : d5e6 : 203255191
move 3 : e5g6 : 165477768
move 4 : e5d7 : 193856446
move 5 : e5f7 : 176070755
move 6 : e2a6 : 130642863
move 7 : f3h3 : 210100865
move 8 : f3f6 : 146338070
move 9 : e1g1 : 172063416
move 10 : e1c1 : 148701308
move 11 : a2a3 : 197413067
move 12 : b2b3 : 153953689
move 13 : g2g3 : 141076301
move 14 : d5d6 : 151133066
move 15 : a2a4 : 183872225
move 16 : g2g4 : 135208177
move 17 : c3b1 : 165673862
move 18 : c3d1 : 165415976
move 19 : c3a4 : 191260040
move 20 : c3b5 : 166970874
move 21 : e5d3 : 140737072
move 22 : e5c4 : 145182844
move 23 : e5g4 : 144264874
move 24 : e5c6 : 169836097
move 25 : a1b1 : 160413321
move 26 : a1c1 : 159720218
move 27 : a1d1 : 149265033
move 28 : h1f1 : 154273720
move 29 : h1g1 : 166086672
move 30 : d2c1 : 158801466
move 31 : d2e3 : 184114087
move 32 : d2f4 : 165805784
move 33 : d2g5 : 177883051
move 34 : d2h6 : 161319567
move 35 : e2d1 : 131348645
move 36 : e2f1 : 174218453
move 37 : e2d3 : 167737155
move 38 : e2c4 : 170094798
move 39 : e2b5 : 158033152
move 40 : f3d3 : 164583144
move 41 : f3e3 : 189120807
move 42 : f3g3 : 198078522
move 43 : f3f4 : 181938761
move 44 : f3g4 : 189789456
move 45 : f3f5 : 226135507
move 46 : f3h5 : 197839051
move 47 : e1d1 : 148612404
move 48 : e1f1 : 139601450

Perft complete:
Time  : 211480ms
Leaves: 8031647685
LPS   : 37978284

Even though both engines are within half a second from one another in the starting position, there somehting in the KiwiPete position that gives Rustic a 10 second lead. This could even be compiler differences.

Fastest: (rustc / LLVM + MSVC libraries + MS Link; MSVC toolchain) <-- officially supported toolchain
Slowest: (rustc / LLVM + GNU libraries + GNU linker; GNU toolchain) <-- officially supported toolchain

The difference between the two toolchains is about 5 seconds in startpos perft 7, and 12 seconds in KiwiPete perft 6. The weird Frankenstein combo where MS Link is replaced with LLVM LLD, is somewhere in between the two.

I compiled Weiss using GCC, latest version, by the way, using your makefile.

[mvanthoor]

@Terje: I don't know if you're still interested in this, but today I realised I made a mistake in my last test. I forgot to disable Weiss' PEXT mode before compiling. As I did a bit of restructuring in Rustic while writing the search and UCI functions, I ran the tests again. Once with PEXT off, once with PEXT on.

Summary:
Weiss Without Pext, startpos perft 7: 81.87 seconds
Weiss With Pext, startpos perft 7: 78.61 seconds
Rustic Without Pext, startpos perft 7: 78.82 seconds.

PEXT gains about 4% extra speed for your engine. Rustic has no PEXT-bitboards (yet), so I can't test that. I'm not going to add those until the engine has obtained a fair strength, as the magic bitboard is working fine.

Your last optimization round brought a fair bit of extra speed (88 -> 81.87 seconds), but not as much as I first reported, because that report was with the extra speed gained by leaving PEXT enabled.

=====

Weiss, current master-branch
No PEXT, startpos, perft 7
Speed: 81.87 seconds.

Code: Select all

Marcel@WORKSTATION MINGW64 /c/code/weiss/src
$ ./weiss_nopext.exe
perft 7 rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Starting perft to depth 7

move 1 : a2a3 : 106743106
move 2 : b2b3 : 133233975
move 3 : c2c3 : 144074944
move 4 : d2d3 : 227598692
move 5 : e2e3 : 306138410
move 6 : f2f3 : 102021008
move 7 : g2g3 : 135987651
move 8 : h2h3 : 106678423
move 9 : a2a4 : 137077337
move 10 : b2b4 : 134087476
move 11 : c2c4 : 157756443
move 12 : d2d4 : 269605599
move 13 : e2e4 : 309478263
move 14 : f2f4 : 119614841
move 15 : g2g4 : 130293018
move 16 : h2h4 : 138495290
move 17 : b1a3 : 120142144
move 18 : b1c3 : 148527161
move 19 : g1f3 : 147678554
move 20 : g1h3 : 120669525

Perft complete:
Time  : 81872ms
Leaves: 3195901860
LPS   : 39035346

Weiss, current master-branch
WITH PEXT, startpos, perft 7
Speed: 78.61 seconds.

Code: Select all

Marcel@WORKSTATION MINGW64 /c/code/weiss/src
$ ./weiss_pext.exe
perft 7 rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Starting perft to depth 7

move 1 : a2a3 : 106743106
move 2 : b2b3 : 133233975
move 3 : c2c3 : 144074944
move 4 : d2d3 : 227598692
move 5 : e2e3 : 306138410
move 6 : f2f3 : 102021008
move 7 : g2g3 : 135987651
move 8 : h2h3 : 106678423
move 9 : a2a4 : 137077337
move 10 : b2b4 : 134087476
move 11 : c2c4 : 157756443
move 12 : d2d4 : 269605599
move 13 : e2e4 : 309478263
move 14 : f2f4 : 119614841
move 15 : g2g4 : 130293018
move 16 : h2h4 : 138495290
move 17 : b1a3 : 120142144
move 18 : b1c3 : 148527161
move 19 : g1f3 : 147678554
move 20 : g1h3 : 120669525

Perft complete:
Time  : 78613ms
Leaves: 3195901860
LPS   : 40653605

Rustic, current version
No PEXT, startpos perft 7
Speed: 78.82 seconds

Code: Select all

Benchmarking perft 1-7:

8   r n b q k b n r
7   i i i i i i i i
6   . . . . . . . .
5   . . . . . . . .
4   . . . . . . . .
3   . . . . . . . .
2   I I I I I I I I
1   R N B Q K B N R

    A B C D E F G H

Zobrist key:        819aa694337673fb
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (7 ms, 28183000 leaves/sec)
Perft 5: 4865609 (120 ms, 40546741 leaves/sec)
Perft 6: 119060324 (2986 ms, 39872847 leaves/sec)
Perft 7: 3195901860 (78823 ms, 40545295 leaves/sec)
Total time spent: 81936 ms
Execution speed: 40519849 leaves/second

[mvanthoor]

Also reran the test for the Kiwipete position at perft 6.

Weiss without PEXT : 214.91 seconds
Weiss with PEXT: 208.60 seconds
Rustic without PEXT: 202.87 seconds.

Restructuring was just putting some constants (such as squares and files and such) into structs to make importing them easier.
This shouldn't have had any effect on speed. It must be the code/memory layout. Rustic gained about 2 seconds in the starting position @ perft 7, but lost about 1.5 seconds in Kiwipete @perft 6.

Tomorrow I'll be testing the search function... I think I'll have to write a quiescence search, even in my bare-bones engine, so it will stop throwing pieces away

======

Weiss no PEXT, Kiwipete perft 6
Speed: 214.91 seconds

Code: Select all

Marcel@WORKSTATION MINGW64 /c/code/weiss/src
$ ./weiss_nopext.exe
perft 6 r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

Starting perft to depth 6

move 1 : g2h3 : 158328615
...
move 48 : e1f1 : 139601450

Perft complete:
Time  : 214912ms
Leaves: 8031647685
LPS   : 37371797

Weiss no PEXT, Kiwipete perft 6
Speed: 208.60 seconds

Code: Select all

Marcel@WORKSTATION MINGW64 /c/code/weiss/src
$ ./weiss_pext.exe
perft 6 r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

Starting perft to depth 6

move 1 : g2h3 : 158328615
...
move 48 : e1f1 : 139601450

Perft complete:
Time  : 208600ms
Leaves: 8031647685
LPS   : 38502625

Rustic Kiwipete perft 6: 202.87 seconds

Code: Select all

Benchmarking perft 1-6:

8   r . . . k . . r
7   i . i i q i b .
6   b n . . i n i .
5   . . . I N . . .
4   . i . . I . . .
3   . . N . . Q . i
2   I I I B B I I I
1   R . . . K . . R

    A B C D E F G H

Zobrist key:        fb86acbc2034870e
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Perft 1: 48 (0 ms, inf leaves/sec)
Perft 2: 2039 (0 ms, inf leaves/sec)
Perft 3: 97862 (2 ms, 48931000 leaves/sec)
Perft 4: 4085603 (102 ms, 40054931 leaves/sec)
Perft 5: 193690690 (4891 ms, 39601449 leaves/sec)
Perft 6: 8031647685 (202866 ms, 39590900 leaves/sec)
Total time spent: 207861 ms
Execution speed: 39591476 leaves/second

[Terje]

Thanks for testing, I am still and will always be interested in speeding up Weiss! I will report back if/when I find something

Also it's been a while so I forgot - does Rustic do any kind of move ordering? Weiss gains some speed if I comment out the code that adds scores to moves (which is pointless in perft), so if you don't do it Weiss might still technically have the lead

[mvanthoor]

Rustic has no move ordering yet, but it does incremental material updates. How could I add scores without running the evaluation?

Simple move ordering will be the first addition after I finish the search and UCI functions.

At some point I'll look into pext bitboards, but they're only useful on Intel... BMI2 and Pext are really slow on Ryzen. Pity that Intel is so far behind now. Maybe I'll wait another year. Or more. I don't feel like buying a cpu that is slow with a function I'll probably want to use...

PS: Found another engine in Rust: Savant. It seems to be written as if Rust is an object oriented language (which it isn't; it only has some look-alike features). It also seems to be an engine hell bent on using as much Rust features as possible. Using macro's to define bitboards... oh my! That's die-hard. (But the description says the engine is experimental.)

Even though it uses bitboards (don't know if they're magic; haven't looked into it that far), it's slow. I added timing to its perft function. Startpos perft 7 takes 379 seconds, at 8M leaves per second. With 40M leaves/s, both Weiss and Rustic are about 5 times as fast.

Savant is even slower than my very first fully working perft, which ran at a (for me) disappointing speed of 277 seconds for perft 7.