stdLambda performance re-visited

[sancarn]

stdLambda Performance

It has come to my attention that there exists another library a lot like stdLambda, named clsMathParser. This library apparently existed since 2004(?!), so totally unsure how this skipped passed my radar! It's not a very intuitive library but essentially functions as follows:

With new clsMathParser
  .storeExpression("x+1")
  For i = 1 to 100
    variable("x") = i
    Debug.Print .eval()
  next
End With

This library is, according to my testing, 5x vaster than stdLambda. Test set:

Sub test()
  Dim math As New clsMathParser
  Dim lambda As stdLambda: Set lambda = stdLambda.Create("$1^2+$1+2")
  
  If math.StoreExpression("x^2+x+2") Then
    With stdPerformance.Measure("clsMathParser", 10000)
      Dim i As Double, l As Double
      For i = 1 To 1000000
        math.variable("x") = i / 1000
        l = math.Eval()
      Next
    End With
    
    With stdPerformance.Measure("stdLambda", 10000)
      For i = 1 To 1000000
        l = lambda.Run(i / 1000)
      Next
    End With
  End If
End Sub

Comparrison of algorithm

• clsMathParser's stack is pre-populated with values paired with operators. This ultimately means less operations done in VBA side:
  • clsMathParser splits x^2+x+2 into 3 operations:
    • ET(0) = completion op
    • ET(1) = ^ prevArg + varX^2 (???)
    • ET(2) = + prevArg + varX
    • ET(3) = + 0+2
  • stdLambda splits$1^2+$1+2 into 7 operations
    • ops(0) = Arg 1
    • ops(1) = Push 2
    • ops(2) = Op Pow
    • ops(3) = Arg 1
    • ops(4) = Op Add
    • ops(5) = Push 2
    • ops(6) = Op Add
    • ops(7) = Completion
• stdLambda's starts with an empty stack and alocates it with values at runtime. Though we're only copying a few bytes I guess this consumes a lot of time compared to having all that data pre-prepared. A pre-populated stack is something we should likely look into.
• stdLambda used to be copying argument location from a string at runtime, which is slow! I changed this and it saves some 30µs per operation. Fixed in 2a9b2e0
• clsMathParser isn't stand alone sadly, and doesn't provide object access. stdLambda does provide object access and is standalone by comparrison (although technically requires stdICallable - easily removed by comparrison)
• Cleverly clsMathParser uses a ByRef param for the return type. That shaves off some time, although not significant in my tests. But still clever fosho :)

[sancarn]

ws-garcia commented 7 days ago
I have been playing with stdLambda and a doubt is gnawing my head. Why is the evaluation of a function like sin(x) so slow compared to numeric evaluation in this class module, given the fact it is a single operation?

It's difficult to say for sure, it could be due to a number of reasons. Happy for help looking into exactly why. The relevant parts of the code are as follows:

1. Function symbol
2. Getting args off the stack
3. Function evaluation

Some whatchouts:

• Could be due to how much mem copying is going on, to prepare arguments etc.
• If you've added any overrides in oFuncExt that'd be why, as there is a check that sin is overwritten in the late-bound dictionary:

---

    If TypeName(Me.oFunctExt) = "Dictionary" Then
        If Me.oFunctExt.exists(sFuncName) Then
            Dim vInjectedVar As Variant
            Call CopyVariant(vInjectedVar, oFunctExt(sFuncName))
            If TypeOf vInjectedVar Is stdICallable Then
                Call CopyVariant(evaluateFunc, Me.oFunctExt(sFuncName).RunEx(args))
            Else
                Call CopyVariant(evaluateFunc, vInjectedVar)
            End If
            Exit Function
        End If
    End If

so that's where i'd check first

In general though it's likely because at min-3 stack pops are required (Func symbol, argLength, arg + timeWhileEvaluating); where with standard numerical evaluation only 1 stack pop is required (arg).

[ws-garcia]

-snip- (Moved by admin as was unrelated to performance)

[sancarn]

Had a discussion with @TarVK a few days ago. He thinks it's not too surprising that these performance issues exist as clsMathParser doesn't support recursion and thus doesn't need a stack (and thus has 0 stack pops instead of 2 + a simpler switch case).

Recompilation of operations approach

An option would be to search the compiled operation array and detect if any jumps occur. If no jump occurs then there is no need for a stack, and operation set can be compiled to a expression tree similar to that used by clsMathParser, increasing the performance. However this would of course increase complexity and decrease maintainability of the class too.

Expression / Statement seperation approach

Another option is to seperate what stdLambda sees as statements (which require a stack) and expressions (which don't require a stack).

• Statements
  • If statement
  • For loop
  • While loop
  • Function declaration
  • variable assignment
• Expressions
  • a+b
  • getSomething()
  • Math.getPi() + 4
  • getSmth().doSmth()

Expressions don't need a stack so can be evaluated quickly. Ultimately the design would be to have an evaluate expression command which can quickly evaluate an expression seperate from the stack.

[ws-garcia]

Another option is to seperate what stdLambda sees as statements (which require a stack) and expressions (which don't require a stack).

This looks like an easy path to implement the required hot fix. I think that the first proposal will end in an entirely class eval method rewriting.