Plisco/Engine/TranspositionTable.pm

filter: Statementstmt 100% 123 / 123 Branchbran 87.5% 21 / 24 Conditioncond 78.9% 15 / 19 MC/DCmcdc 25.0% 2 / 8 Subroutinesub 100% 20 / 20 Podpod 0.0% 0 / 7 totaltotal 90.0% 181 / 201 CC 23 SCAR 16.4
CC
23
Cov
96%
store
9.2
hashfull
8.0
probe
7.0
CRAP 5.1
« Plisco/Engine/Position.pm ↑ Summary Plisco/Engine/TimeControl.pm »
1 #! /bin/false
2  
3 # Copyright (C) 2021-2026 Guido Flohr <guido.flohr@cantanea.com>,
4 # all rights reserved.
5  
6 # This program is free software. It comes without any warranty, to
7 # the extent permitted by applicable law. You can redistribute it
8 # and/or modify it under the terms of the Do What the Fuck You Want
9 # to Public License, Version 2, as published by Sam Hocevar. See
10 # http://www.wtfpl.net/ for more details.
11  
12 # Rename that back to TranspositionTable, once done.
13 package Chess::Plisco::Engine::TranspositionTable;
14 9 $Chess::Plisco::Engine::TranspositionTable::VERSION = 'v1.0.3';
15 9 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
16 9 ▶use integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
17  
18 9 ▶use Time::HiRes qw(gettimeofday tv_interval);
Subroutine BEGIN: called CC=1 SCAR=0.0
19  
20 # Macros from Chess::Plisco::Macro are already expanded here!
21 9 ▶use Chess::Plisco::Engine::Constants;
Subroutine BEGIN: called CC=1 SCAR=0.0
22  
23 # The transposition table is organised into clusters, which in turn contain
24 # 4 buckets.
25 9 ▶use constant CLUSTER_CAPACITY => 4;
Subroutine BEGIN: called CC=1 SCAR=0.0
26  
27 # We store the keys separately from the actual entries, because that is easier
28 # to scan. The layout of a cluster is then like this:
29  
30 # key0 16 bit
31 # key1 16 bit
32 # key2 16 bit
33 # key3 16 bit
34 # depth 8 bit start of bucket 0
35 # generation 5 bit
36 # pv node 1 bit
37 # bound type 2 bit
38 # move 16 bit
39 # value 16 bit
40 # evaluation 16 bit end of bucket 0
41 # bucket1 64 bit
42 # bucket2 64 bit
43 # bucket3 64 bit
44  
45 9 ▶use constant KEY_BYTES => 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
46 9 ▶use constant BUCKET_BYTES => 8;
Subroutine BEGIN: called CC=1 SCAR=0.0
47  
48 9 ▶use constant TT_ENTRY_SIZE => 16;
Subroutine BEGIN: called CC=1 SCAR=0.0
49  
50 9 ▶use constant GENERATION_BITS => 3;
Subroutine BEGIN: called CC=1 SCAR=0.0
51 9 ▶use constant GENERATION_DELTA => (1 << (GENERATION_BITS));
Subroutine BEGIN: called CC=1 SCAR=0.0
52 9 ▶use constant GENERATION_CYCLE => 255 + GENERATION_DELTA;
Subroutine BEGIN: called CC=1 SCAR=0.0
53 9 ▶use constant GENERATION_MASK => (0xFF << (GENERATION_BITS)) & 0xFF;
Subroutine BEGIN: called CC=1 SCAR=0.0
54  
55 9 my $generation = 0;
56 9 my $last_hashfull;
57 9 my $last_hashfull_probe = 0;
58  
59 354 ▶sub new {
Subroutine new: called CC=1 SCAR=0.0
Pod undocumented
60 354 my ($class, $size) = @_;
61  
62 # Reading array entries is almost 50 % faster than access strings with
63 # substr.
64 354 my $self = [];
65 354 bless $self, $class;
66  
67 354 return $self->resize($size);
68 }
69  
70 361 ▶sub clear {
Subroutine clear: called CC=2 SCAR=6.9
Pod undocumented
71 361 my ($self) = @_;
72  
73 361 my $cluster_bytes = CLUSTER_CAPACITY * (KEY_BYTES + BUCKET_BYTES);
74  
75 361 $self->[$_] = "\0" x $cluster_bytes for 0 .. $#$self;
76  
77 361 return $self;
78 }
79  
80 354 ▶sub resize {
Subroutine resize: called CC=1 SCAR=0.0
Pod undocumented
81 354 my ($self, $size) = @_;
82  
83 354 my $cluster_bytes = CLUSTER_CAPACITY * (KEY_BYTES + BUCKET_BYTES);
84  
85 354 $#$self = 0;
86 # Perl possibly rounds the size up. Therefore the int.
87 354 $#$self = int($size * 1024 * 1024 / $cluster_bytes) - 1;
88  
89 354 $self->clear;
90  
91 354 $generation = 0;
92  
93 354 return $self;
94 }
95  
96 348 ▶sub newSearch {
Subroutine newSearch: called CC=1 SCAR=0.0
Pod undocumented
97 348 $generation += GENERATION_DELTA;
98 }
99  
100 1655036 ▶sub probe {
Subroutine probe: called CC=7 SCAR=19.5
Pod undocumented
101 1655036 my ($self, $signature) = @_;
102  
103 # Throw away the sign bit, because we cannot use negative indices.
104 1655036 my $cluster_index = ($signature & 0x7fff_ffff_ffff_ffff) % scalar @$self;
105 1655036 my $cluster = $self->[$cluster_index];
106
107 # Use the lower 16 bits.
108 1655036 my $key16 = $signature & 0xffff;
109  
110 1655036 my @keys = unpack 'S4', $cluster;
111 1655036 ▶ for (my $i = 0; $i < @keys; ++$i) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < @keys) 5803979 1370014 7173993
112 5803979 ▶ if ($keys[$i] == $key16) {
Branch: 1 branch
BranchTrueFalseTotal
if ($keys[$i] == $key16) 285110 5518869 5803979
113 285110 my $bucket = substr $cluster, 8 + $i * BUCKET_BYTES, BUCKET_BYTES;
114 # The list now contains the depth, move, value, evaluation, and
115 # encoded bitfield.
116 285110 my @bucket = (0, unpack 'CCSss', $bucket);
117 285110 ▶ my $occupied = $bucket[1] or next;
Branch: 1 branch
BranchTrueFalseTotal
my $occupied = $bucket[1] or next 285022 88 285110
118 285022 ▶ $bucket[0] = $occupied && 1; # The occupied flag.
Condition50%1/2
$occupied && 1
!ll
0285022
MC/DC0%0/1
$occupied && 1
$occupied
Truth table50%1/2
A
A= $occupied
Aresult
00
11
119 285022 $bucket[1] += DEPTH_ENTRY_OFFSET; # The actual depth.
120 285022 my $bitfield = $bucket[2];
121 285022 $bucket[2] &= 3; # Now contains the bound type.
122 285022 $bucket[3] = (($bucket[3]) << 6);
123 285022 push @bucket, $bitfield & 4, $cluster_index, $i, $bucket;
124  
125 285022 return @bucket;
126 }
127 }
128  
129 # Nothing found. Find a bucket to replace.
130 1370014 my ($depth, $generation) = unpack 'CC', substr $cluster, 8;
131 1370014 my $bucket_index = 0;
132 1370014 my $best = $depth - 8 * (GENERATION_CYCLE & GENERATION_MASK);
133 1370014 ▶ for (my $i = 1; $i < @keys; ++$i) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < @keys) 4110042 1370014 5480056
134 4110042 my $offset = 8 + $i * BUCKET_BYTES;
135 4110042 my $repl_bucket = substr $cluster, $offset, BUCKET_BYTES;
136 4110042 my ($repl_depth, $repl_generation) = unpack 'CC', $repl_bucket;
137 4110042 ▶ if ($repl_depth - 8 * ((GENERATION_CYCLE + $generation - $repl_generation) & GENERATION_MASK) < $best) {
Branch: 1 branch
BranchTrueFalseTotal
if ($repl_depth - 8 * (263 + $generation - $repl_generation & 248) < $best) 291486 3818556 4110042
138 291486 $depth = $repl_depth;
139 291486 $generation = $repl_generation;
140 291486 $bucket_index = $i;
141 }
142 }
143  
144 1370014 my $bucket = substr $cluster, 8 + $bucket_index * BUCKET_BYTES, BUCKET_BYTES;
145  
146 1370014 return 0, 0, 0, 0, undef, undef, 0, $cluster_index, $bucket_index, $bucket;
147 }
148  
149 1396715 ▶sub store {
Subroutine store: called CC=9 SCAR=22.1
Pod undocumented
150 1396715 my ($self, $cluster_index, $bucket_index, $bucket, $signature, $value,
151 $pv, $bound, $depth, $move, $eval) = @_;
152  
153 1396715 $pv = !!$pv;
154 1396715 $generation &= GENERATION_MASK;
155  
156 1396715 my $k = $signature & 0xffff;
157  
158 # Unpacking just one value is almost two times faster than unpacking all
159 # four keys and picking the right one.
160 1396715 my $key = unpack 'S', substr $self->[$cluster_index], $bucket_index << 1, 2;
161  
162 # Preserve the old move.
163 1396715 ▶ if (!$move && $key == $k) {
Branch: 1 branch
BranchTrueFalseTotal
if (not $move and $key == $k) 20505 1376210 1396715
Condition100%3/3
not $move and $key == $k
!ll&&!rl&&r
314477106173320505
MC/DC100%2/2
not $move and $key == $k
not $move $key == $k
Truth table100%3/3
not(A) and B
A= not $moveB= $key == $k
ABresult
0X0
100
111
164 20505 $move = ((unpack 'S') << 6);
165 }
166  
167 # Overwrite old entry?
168 1396715 my $stored_depth;
169 1396715 ▶ if ($bound == BOUND_EXACT || $key != $k
Branch: 1 branch
BranchTrueFalseTotal
if ($bound == 3 or $key != $k or $stored_depth = unpack("C", substr($bucket, 0, 1)) || 0 or $depth - -3 + ($pv << 1) > $stored_depth - 4 or 263 + $generation - $stored_depth & 248) 1396715 0 1396715
Condition78%11/14
$bound == 3 or $key != $k or $stored_depth = unpack("C", substr($bucket, 0, 1)) || 0 or $depth - -3 + ($pv << 1) > $stored_depth - 4 or 263 + $generation - $stored_depth & 248
l!l&&r!l&&!r
139671500
$bound == 3 or $key != $k or $stored_depth = unpack("C", substr($bucket, 0, 1)) || 0 or $depth - -3 + ($pv << 1) > $stored_depth - 4
l!l&&r!l&&!r
1396695200
$bound == 3 or $key != $k or $stored_depth = unpack("C", substr($bucket, 0, 1)) || 0
l!l&&r!l&&!r
13446905200520
$bound == 3 or $key != $k
l!l&&r!l&&!r
5283133940752025
unpack('C', substr($bucket, 0, 1)) || 0
l!l
5200520
MC/DC0%0/5
$bound == 3 or $key != $k or $stored_depth = unpack("C", substr($bucket, 0, 1)) || 0 or $depth - -3 + ($pv << 1) > $stored_depth - 4 or 263 + $generation - $stored_depth & 248
$bound == 3 $key != $k unpack('C', substr($bucket, 0, 1)) $depth - -3 + ($pv << 1) > $stored_depth - 4 263 + $generation - $stored_depth & 248
Truth table66%4/6
A or B or C or D or E
A= $bound == 3B= $key != $kC= unpack('C', substr($bucket, 0, 1))D= $depth - -3 + ($pv << 1) > $stored_depth - 4E= 263 + $generation - $stored_depth & 248
ABCDEresult
1XXXX1
01XXX1
001XX1
0001X1
000011
000000
170 || ($stored_depth = unpack('C', substr $bucket, 0, 1) || 0) # Always false, forces stored_depth to be defined.
171 || $depth - DEPTH_ENTRY_OFFSET + ($pv << 1) > $stored_depth - 4
172 || ((GENERATION_CYCLE + $generation - $stored_depth) & GENERATION_MASK)) {
173 # Overwrite!
174 1396715 substr($self->[$cluster_index], $bucket_index << 1, 2) = pack 'S', $k; # Key.
175 1396715 substr($self->[$cluster_index], 8 + ($bucket_index << 3), BUCKET_BYTES) =
176 pack('CCSss',
177 $depth - DEPTH_ENTRY_OFFSET, # Depth.
178 $generation | ($pv << 2) | $bound, # GenBound8.
179 ((($move) & 0x1fffc0) >> 6),
180 $value,
181 $eval,
182 );
183 }
184 }
185  
186 2009 ▶sub hashfull {
Subroutine hashfull: called CC=8 SCAR=20.8
Pod undocumented
187 2009 my ($self, $max_age) = @_;
188  
189 # Do not do that more than once a second.
190 2009 my $now = [gettimeofday];
191 2009 ▶ if (defined $last_hashfull) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $last_hashfull) 2002 7 2009
192 9 ▶ no integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
193  
194 2002 my $elapsed = tv_interval $last_hashfull_probe, $now;
195 2002 ▶ if ($elapsed < 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($elapsed < 1) 1767 235 2002
196 1767 return $last_hashfull;
197 }
198 }
199  
200 242 my $max_age_internal = $max_age << (GENERATION_BITS);
201 242 my $cnt = 0;
202  
203 242 ▶ my $limit = @$self < 1000 ? @$self : 1000;
Branch: 1 branch
BranchTrueFalseTotal
@$self < 1000 ? : 0 242 242
204  
205 242 for my $ci (0 .. $limit - 1) {
206 242000 my @c = unpack 'C40', $self->[$ci];
207  
208 242000 for my $bi (0 .. CLUSTER_CAPACITY - 1) {
209 968000 my $k_lo = $c[$bi * 2];
210 968000 my $k_hi = $c[$bi * 2 + 1];
211 968000 ▶ next if ($k_lo | $k_hi) == 0; # empty
Branch: 1 branch
BranchTrueFalseTotal
if ($k_lo | $k_hi) == 0 961975 6025 968000
212  
213 6025 my $base = 8 + ($bi << 3);
214 6025 my $gen = $c[$base + 1];
215  
216 6025 my $age =
217 (GENERATION_CYCLE + $generation - $gen)
218 & GENERATION_MASK;
219  
220 6025 ▶ $cnt++ if $age <= $max_age_internal;
Branch: 1 branch
BranchTrueFalseTotal
if $age <= $max_age_internal 6025 0 6025
221 }
222 }
223  
224 242 $last_hashfull = int($cnt / CLUSTER_CAPACITY);
225 242 $last_hashfull_probe = $now;
226  
227 242 return $last_hashfull;
228 }
229  
230 9 1;
« Plisco/Engine/Position.pm ↑ Summary Plisco/Engine/TimeControl.pm »