I am implementing a specialized hashtable. I'm trying store a lot of data in a single 64-bit int key, for space usage and performance reasons.
Each key should have this structure:
// Key structure, from LSB
// eval result (16 bits)
// move (16 bits)
// age (16 bits): the move of the game on which this position would have occurred
// depth (8 bits)
// node type (8 bits): from the three constants above
Here is a simple implementation:
var keys [1000]uint64
var values [1000]uint64
func Put(b *dragontoothmg.Board, m dragontoothmg.Move, eval int16, depth uint8, ntype uint8) {
var value uint64 = uint64(eval) | (uint64(m) << 16) | (uint64(b.Fullmoveno) << 32) |
(uint64(depth) << 48) | (uint64(ntype) << 56)
hash := b.Hash()
key := hash ^ value
index := hash % uint64(len(keys))
keys[index] = key
values[index] = value
}
func Get(b *dragontoothmg.Board) (found bool, move dragontoothmg.Move,
eval int16, depth uint8, ntype uint8) {
hash := b.Hash()
index := hash % uint64(len(keys))
key := keys[index]
value := values[index]
found = (hash == (key ^ value))
if !found {
return false, 0, 0, 0, 0
}
eval = int16(value & 0xFFFF)
move = dragontoothmg.Move((value >> 16) & 0xFFFF)
depth = uint8((value >> 48) & 0xFF)
ntype = uint8((value >> 56) & 0xFF)
return
}
However, when I try to Get() the data, it comes back corrupted. I suspect this might be related to the fact that eval is a signed int, and the cast converts it to a signed uint64. What have I done wrong, and how can I fix it?
This is failing test result:
--- FAIL: TestSimpleTt (0.10s)
transtable_test.go:37: Simple ttable test failed.
Put data: (board: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 0) e2e4 -30 6 2
Fetched data: true h8h8 -30 255 255
FAIL
h8h8 is the maximum value of the field, for what it's worth.
Thanks to everyone who responded. This was the solution to my issue:
uint64(eval) for negative values was moving the sign bit to the most significant bit of the 64-bit int, which then interfered with the data that was supposed to be stored at that bit. I solved it by first converting to uint16:
uint64(uint16(eval))
I can't reproduce your resultat in simplified code https://play.golang.org/p/shPN-1waZa:
func Pack(m, eval int16, depth, ntype uint8) (value uint64) {
value = (uint64(eval) |
(uint64(m) << 16) |
// (uint64(b.Fullmoveno) << 32) | <-- My suspicion is here !
(uint64(depth) << 48) |
(uint64(ntype) << 56))
return
}
func Unpack(value uint64) (move int16, eval int16, depth uint8, ntype uint8) {
eval = int16(value & 0xFFFF)
move = int16((value >> 16) & 0xFFFF)
depth = uint8((value >> 48) & 0xFF)
ntype = uint8((value >> 56) & 0xFF)
return
}
func main() {
m, e, d, n := int16(8), int16(8), uint8(8), uint8(8)
packedValue := Pack(m, e, d, n)
fmt.Printf("%v
", packedValue)
move, eval, depth, ntype := Unpack(packedValue)
fmt.Printf("%v %v %v %v", move, eval, depth, ntype)
}
But I have suspicions:
a) dragonthooth.Move - is it really int16? I suppose you have set of consts with values for this type
b) You're packing 5 values and extract 4. Maybe it's not error, but check type of b.Fullmoveno is it int16?
c) I can not judge about correctness of your other code. I just hope that you did not make errors in hash, index, keys, values.
I can't quite understand your remaining code.
I suppose you mean value structure and not key structure (because in your code it's value packed)
Why did you define 2 keys and values in separate arrays? Why not []{uint64,uint64}? Or even map[uint64]uint64?