Performance limited by writing into an array | Discord Gophers | Page 1

fleet vortex Dec 18, 2022, 4:41 PM

#

Hello there, i am currently optimizing the move generator of the chess engine i am currently writing. Everything was going smoothly until i checked my profiles. My code is spending 81% of the time not generating moves, but writing them into the result list. Being a bit baffled at first, i triple checked this result until i convinced myself that even though i am writing into an already allocated array, which i am passing by pointer this is infact tanking my performance.

This is the function that is spend 81% of my time in (this function is inlined by the compiler):

func commitMoveBoard(moveList *[120]Move, moveCount int, mb bitmap.Bitmap, pieceType PieceType, origin int8, board *Board) int {
    for mb != 0 {
        square := mb.Scan()
        moveList[moveCount] = Move{
            Origin:            Square(origin),
            Destination:       Square(square),
            PieceType:         pieceType,
            CapturedPieceType: board.SquareCache[square].Type,
        }
        moveCount++
        mb &= mb - 1
    }
    return moveCount
}

Does anyone have an idea how i could improve this?

#

i specifically spend my time in the line that inserts into the movelist

#

In case this is relevant, i built the binary that i used to profile using the following options: compile: CGO_ENABLED=0 GOOS=linux GOARCH=amd64 GOAMD64=v3 go build -gcflags=all='-B -C' -ldflags='-s -w' -trimpath -o ./dist/revelation cmd/main.go

#

Here is the assembly generated by the compiler for the function

📎 message.txt

old violet Dec 18, 2022, 6:09 PM

#

I'm not sure I can help you with this but using maps for performance oriented stuff might not give you the best results. Try converting the map to a slice. It should give you quite a big boost in performance

fleet vortex Dec 18, 2022, 6:33 PM

#

Thanks for the tip, i am not using maps though. MoveList is a constant size array and bitmap.Bitmap is an alias for uint64

old violet Dec 18, 2022, 7:03 PM

#

Ops apologies

#

Is this called multiple times? Are you monitoring GC at the same time?

#

Are you locking before you write there ? Maybe the issue is not the function it self, but how you call it

fleet vortex Dec 18, 2022, 9:34 PM

#

The function is called a lot (several hundred million times per second). There are no mutexes involved here, the entire program is currently single threaded. The entire codepath contains no heap allocations and therefore no garbage collections. Currently my movegenerator runs in ~30ns/op, of which 81% is the function listed above.

#

#Performance limited by writing into an array