| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 112 | 5803979 | ▶ | if ($keys[$i] == $key16) { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 118 | 285022 | ▶ | $bucket[0] = $occupied && 1; # The occupied flag. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Condition50%1/2
$occupied && 1
MC/DC0%0/1
$occupied && 1
$occupied
Truth table50%1/2
A
A= $occupied
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition100%3/3
not $move and $key == $k
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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
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
$bound == 3 or $key != $k or $stored_depth = unpack("C", substr($bucket, 0, 1)) || 0 or $depth - -3 + ($pv << 1) > $stored_depth - 4
$bound == 3 or $key != $k or $stored_depth = unpack("C", substr($bucket, 0, 1)) || 0
$bound == 3 or $key != $k
unpack('C', substr($bucket, 0, 1)) || 0
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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||