Coding Functional style taking longer time than its Imperative style

Question

I wanted to try out F# so I decided to I converted a library file from c# to f#. I have done that successfully(thanks a you people in stackoverflow). At first I ported the code from c# to f#. Than I tried to covert the code into FP after a lot of pain I have managed to get this far.

Here is the Source Code for the whole project if anyone what to use it.

dl.dropboxusercontent.com/u/87039989/TicTacToe.zip The code has changed so the speed test may not be 100%. To the one here.

[Speed: Average of 5 calls to Move() with same scenario]

C# 466.4 (ticks/1000)

public class Agent
{
    private readonly Reffery _reff = new Reffery();

    public Agent(Board cBoard, int symbol)
    {
        this.Symbol = symbol;
        RootBoard = new Board(cBoard);
    }

    public Board RootBoard { get; set; }
    public int Symbol { get; set; }

    public int Move()
    {
        var max = -10;
        var bestMove = 0;
        if (RootBoard.MoveNumber == 0)
            return 4;
        for (var i = 0; i <= 8; i++)
        {
            var board = new Board(RootBoard);

            if (!board.SetBoardBool(i)) continue;
            var val = MinMaxAlphaBeta(board, true, -10, 10);
            if (val >= max)
            {
                max = val;
                bestMove = i;
            }
        }
        return bestMove;
    }
    private int MinMaxAlphaBeta(Board board, bool min, int alpha, int beta)
    {

        var point = BoardPoint(board);
        if (point != -2)
        {
            return point;
        }
        for (var i = 0; i <= 8; i++)
        {
            var newBoard = new Board(board);
            newBoard.Copy(board);
            if (!newBoard.SetBoardBool(i)) continue;
            var val = MinMaxAlphaBeta(newBoard, !min, alpha, beta);
            if (min && val < beta)
                beta = val;
            else if (!min && val > alpha)
                alpha = val;
        }
        return min ? beta : alpha;
    }

    private int BoardPoint(Board board)
    {
        int hum = Symbol == 1 ? 2 : 1;
        var condition = _reff.checkBoardCondition(board);
        if (condition == (Reffery.Condition)Symbol) return 1;
        if (condition == (Reffery.Condition)hum) return -1;
        if (condition == (Reffery.Condition.Draw)) return 0;
        return -2;
    }
}

F# imperative 327(Ticks/1000)

type Agent(board:Board,symbol:int)=
    let mutable _nodeCount=0;
    let mutable _rootBoard= new Board(board)

    let mutable _symbol = symbol
    let mutable _reff = new Boards.Reffery()
    new (board:Board) = Agent(board,0)

    member this.Move() :int = 
        let mutable max= -10
        let mutable bestMove=0
        if _rootBoard.MoveNumber = 0 then 4
        else
            for i= 0 to 8 do
                let mutable b = new Board(_rootBoard)
                if b.SetBoardBool(i) then 
                    let mutable value = this.MinMaxAlphaBeta(b, true, -10, 10)
                    //Debug.Print (i.ToString() + " , " + value.ToString())
                    if value >= max then
                        max <- value
                        bestMove <- i
            bestMove

    member private this.MinMaxAlphaBeta(board:Board, min:bool,  alpha:int,  beta:int):int=
        let mutable a=alpha //Extra Line
        let mutable b=beta  //Extra Line
        let point = this.BoardPoint(board);
        if point <>  -2 then
            point
        else
            for i = 0 to 8 do
                let mutable newBoard = new Board(board)
                if newBoard.SetBoardBool(i)  then
                    let mutable value = this.MinMaxAlphaBeta(newBoard,not min, a, b)
                    if min && value < b then
                        b <- value
                    elif (not min) && value > a then
                        a <- value;
            if min then b else a

    member private this.BoardPoint(board:Board):int=
        let hum = if _symbol= 1 then 2 else 1
        let mutable pos = _reff.checkBoardCondition(board)
        if pos = enum<Reffery.Condition> _symbol then 1
        elif  pos = enum<Reffery.Condition> hum then -1
        elif pos = Reffery.Condition.Draw then 0
        else -2

F# functional 453.6(Ticks/1000)

type Agent(board:Board,symbol:int)=
    let aisymbol= symbol 
    let rootBoard= new Board(board)
    let _reff = new Boards.Reffery()

    member this.Move() :int =
        if rootBoard.MoveNumber=0 then 4
        else
        let GetVal (i)= 
            let b = new Board(rootBoard) 
            if b.SetBoardBool(i) then this.MinMaxAlphaBeta(b, true, -10, 10)
            else -3
        [| for i = 0 to 8 do yield (GetVal i , i) |] |> Array.max |> snd

    member private this.MinMaxAlphaBeta(board:Board, isMin:bool, alpha:int, beta:int):int=
        let  betaF= ref beta
        let  alphaF= ref alpha
        let point= this.BoardPoint(board)
        if point <> -2 then point
        else
            let UpdateAlplaBeta(x)= 
                if x <> 10 then
                    if isMin &&   x < !betaF then betaF := x
                    elif (not isMin) &&  x > !alphaF then alphaF:=x 
                    x
                else if isMin then !betaF else !alphaF
            let GetVal (i,isMin,al, be)= 
                let b = new Board(board) 
                if b.SetBoardBool(i) then this.MinMaxAlphaBeta(b, isMin, al, be)
                else 10
            let list = [| for i =0 to 8 do yield UpdateAlplaBeta(GetVal (i, (not isMin), !alphaF , !betaF)) |]
            if isMin then list|>Array.min else list|>Array.max 

    member private this.BoardPoint(board:Board):int=
        let human = if aisymbol= 1 then 2 else 1
        let condition = _reff.checkBoardCondition(board)
        if condition = enum<Reffery.Condition> aisymbol then 1
        elif  condition = enum<Reffery.Condition> human then -1
        elif condition = Reffery.Condition.Draw then 0
        else -2

The problem I am facing now is these two lines

    let  betaF= ref beta
    let  alphaF= ref alpha

I can't remove these two variables.

Also as you can see F# dll executes faster than its c# counter part but the one in functional style it take a bit more time to execute then the is imperative counter part, is this suppose to happen or is there something i am doing wrong? If so how can fix it?

Update

b.SetBoardBool(i)

set a move on position i for the current player and returns true is successful other wise false.

_reff.checkBoardCondition(board)

take a board object check if it has X or O win condition, draw or no condition at all.

Answer 1

To start, I see a few issues with the functional version of your code which are contributing to the performance loss:

• Whenever you need maximum performance, use arrays instead of list or seq (if feasible for your specific application). Functions operating on arrays are generally faster than those operating on lists or sequences.
• Avoid creating intermediate variables. There are several places in the functional version of your code where you create a sequence, transform it into a list, then call a function (e.g., List.max) which uses the list once then discards it. That's fine to do when you're prototyping an application, but once things are working and you want to start improving the performance, look for places where you can consolidate two or more function calls to avoid creating intermediate variables. For example, you can use Seq.max instead of Seq.toList and List.max.
• Don't use ref cells unless you really need to. I know they seem like an obvious choice when you're coming from C#, since they allow you to update 'local' variables from within a locally-scoped function (e.g., your UpdateAlphaBeta function); however, they store your value in the heap instead of the stack so you end up paying an indirection penalty each time you access the value. You can often re-implement your functions to use recursion or mutual recursion and pass the values around to each other instead of using ref cells.

---

Here's a functional style reworking of your code. There are still some performance optimizations that could be made, but this code should be reasonably fast anyway (I would be surprised if it wasn't noticeably faster than your original functional code). You'll want to compile this in Release mode for benchmarking, otherwise the recursive functions won't get optimized/inlined into simple loops. I'd be interested to hear how this code performs in your benchmark, just to have the numbers to compare against your original code.

type Agent (board : Board, symbol : int) =
    let aisymbol = symbol
    let rootBoard = Board (board)
    let _reff = Boards.Reffery ()

    member private this.BoardPoint (board : Board) : int =
        let condition = _reff.checkBoardCondition (board)

        let human = if aisymbol = 1 then 2 else 1

        if condition = enum<Reffery.Condition> aisymbol then 1
        elif condition = enum<Reffery.Condition> human then -1
        elif condition = Reffery.Condition.Draw then 0
        else -2

    member private this.MinMaxAlphaBeta (board : Board, isMin : bool, alpha : int, beta : int) : int =
        let point = this.BoardPoint (board)
        if point <> -2 then point
        else
            let UpdateAlphaBeta x alpha beta =
                match x with
                | 10 ->
                    if isMin then
                        beta, alpha, beta
                    else
                        alpha, alpha, beta
                | _ ->
                    if isMin && x < beta then
                        x, alpha, x
                    elif not isMin && x > alpha then
                        x, x, beta
                    else
                        x, alpha, beta

            let rec loop x alpha beta i =
                if i > 8 then x
                else
                    let x', alpha', beta' =
                        let x =
                            let b = Board (board)
                            if b.SetBoardBool i then
                                // NOTE : This is a _recursive_ call!
                                this.MinMaxAlphaBeta (b, not isMin, alpha, beta)
                            else 10

                        UpdateAlphaBeta x alpha beta

                    let x_new =
                        if isMin then min x x' else max x x'

                    loop x_new alpha' beta' (i + 1)

            let x_initial = 0
            loop x_initial alpha beta 0   // Start at the zero-th element.

    member this.Move () : int =
        if rootBoard.MoveNumber = 0 then 4
        else
            let GetVal i =
                let b = Board (rootBoard)
                if b.SetBoardBool i then
                    this.MinMaxAlphaBeta (b, true, -10, 10)
                else -3

            // Gets the index (in the range [0..8]) which produces the maximum value.
            let rec getMaxVal maxValue maxIndex i =
                if i > 8 then maxIndex
                else
                    let value_i = GetVal i
                    if value_i > maxValue then
                        getMaxVal value_i i (i + 1)
                    else
                        getMaxVal maxValue maxIndex (i + 1)

            getMaxVal (GetVal 0) 0 1