Need a fast infix math evaluator

dracflamloc · Post by **dracflamloc** » Mon Mar 06, 2006 1:55 am

I'm creating a scripting language in pb to be released LGPL. I need a fast infix math evaluator. It doesn't need to handle string concatenation or functions. It just needs to take an expression as a string and return the result as a string.

So far I've tried 2 evaluators I've found on the forums. After stripping down Xombies as much as I could, and finding srod's ifix->rpn->solution code, here is what i've discovered so far.

100,000 evaluations of "100+1" takes 700ms on my computer using Xombies. Using srods, it takes 1200ms.

However once you start adding more operations, Xombies falls behind srod's after just 2 more operations and starts to REALLY lag behind with 5+ operations. Does anyone have any suggestions?

The dillemma is that when evaluating loop conditions, typically its an expression like "i+1" which would mean Xombies is a faster algo to use for looping. However once you add a couple more operations, it becomes much much slower (about 60% slower than srods).

I was considering adding a special case to srod's to detect if its a 1-operation expression and handle it in a faster way.

Once I get the math evaluator speed faster the language will be very nearly done. It's pretty quick, though not as fast as lua yet

Also I don't think either of these has a modulus % operator so if anyone can recommend one that does it'd be handy.

I could of course write my own but with all the heads here at pb I figured some of have probably made quite a few already =)

Trond · Post by **Trond** » Mon Mar 06, 2006 5:01 pm

Did you try mine? (Did I even release it?)
Edit: Did I even make one?

I'll have one ready in a few seconds. Just a normal +-*/() expression?

Edit:
Could you test the speed of this?

Code: Select all

snip

Faster code below

dracflamloc · Post by **dracflamloc** » Mon Mar 06, 2006 5:51 pm

Oops. Should have specified. PB 3.94. No API either.

I did convert yours (removed the match macro)
Seems to be pretty good. Yours is a good bit faster than Xombies except in the i+1 type of expressions. You are a bit faster than srod on i+1 but the same for most of the other cases.

I modified srod's to handle single operator cases more efficiently, and it put it on par with yours trond. But still falls behind Xombies by a bit.

500ms on this machine here at work for 100,000 "100+1" operations using Xombie, 700ms for the modified srods or yours Trond.

Trond · Post by **Trond** » Mon Mar 06, 2006 6:36 pm

dracflamloc wrote:Oops. Should have specified. PB 3.94. No API either.

I did convert yours (removed the match macro)
Seems to be pretty good. Yours is a good bit faster than Xombies except in the i+1 type of expressions. You are a bit faster than srod on i+1 but the same for most of the other cases.

I modified srod's to handle single operator cases more efficiently, and it put it on par with yours trond. But still falls behind Xombies by a bit.

500ms on this machine here at work for 100,000 "100+1" operations using Xombie, 700ms for the modified srods or yours Trond.

Arrrgrgrgrrr time for some optimization then. Try if this is faster:
http://pastebin.com/587298

Edit: This should blow the doors and windows and everything off everything:

Code: Select all

OpenConsole()

Global Look.s
Look.s = " " ; Yes, that space is IMPORTANT!!!! Remove and DIE!!!
Global Stream.s
Global StreamPos.l        ; Read position in stream

Procedure.s VisibleToken(s.s)
  Select s.s
    Case #CR$
      s.s = "newline"
    Case #LF$
      s.s = "newline"
    Case ""
      s.s = "nothing"
  EndSelect
  ProcedureReturn s.s
EndProcedure

;Cleanup then end
Procedure Finish()
  PrintN("Ending.")
  Input()
  End
EndProcedure

;Report an error
Procedure Error(s.s)
  PrintN("Error: " + s + ".")
EndProcedure

;Report an error and abort
Procedure Abort(s.s)
  Error(s.s)
  Finish()
EndProcedure

;Report what was expected
Procedure Expected(expected.s)
  Abort("Expected: " + expected + ", got '" + VisibleToken(Look) + "'")
EndProcedure

;Read a character into Look
Goto GetChar_End
GetChar:
  PokeB(@Look, PeekB(@Stream + StreamPos))
  StreamPos + 1
  Return
GetChar_End:

;Eat whitespace
Procedure EatWhite()
  While (Look = " " Or Look = #TAB$)
    !CALL l_getchar
  Wend
EndProcedure

;Match a specific input character
Procedure Match(*s.s)
  If Look <> *s.s
    Expected("'"+*s.s+"'")
  Else
    !CALL l_getchar
    EatWhite()
  EndIf
EndProcedure

;Recognize a mulop
Procedure.l IsMulop(*s.s)
  ProcedureReturn (*s.s = "*" Or *s.s = "/")
EndProcedure

;Get a number
Procedure.l GetNum()
  Protected Value.l
  If (PeekB(Look) < 48 And PeekB(Look) > 57)
    Expected("Integer")
  EndIf
  While (PeekB(Look) > 47 And PeekB(Look) < 58)
    Value = Value * 10 + PeekB(@Look) - '0'
    !CALL l_getchar
  Wend
  ProcedureReturn Value
EndProcedure

;-----

Declare.l Expression()

Procedure.l Factor()
  Protected Value.l
  If (PeekB(Look) > 47 And PeekB(Look) < 58)
    ProcedureReturn GetNum()
  Else
    Match("(")
    Value = Expression()
    Match(")")
  EndIf
  ProcedureReturn Value
EndProcedure

Procedure.l Term() 
  Protected Value.l
  Value.l = Factor()
  While (Look = "*" Or Look = "/")
    If Look = "*"
      !CALL l_getchar
      Value * Factor()
    Else
      !CALL l_getchar
      Value / Factor()
    EndIf
  Wend
  ProcedureReturn Value
EndProcedure

Procedure.l Expression()
  Protected Value.l
  If (Look = "+" Or Look = "-")
    Value = 0
  Else
    Value = Term()
    While (Look = "+" Or Look = "-")
      If Look = "+"
        !CALL l_getchar
        Value + Term()
      Else
        !CALL l_getchar
        Value - Term()
      EndIf
    Wend
  EndIf
  ProcedureReturn Value
EndProcedure

Procedure.l Solve(*s.s)
  Stream = *s.s
  StreamPos = 0
  !CALL l_getchar
  ProcedureReturn Expression()
EndProcedure

#Tries = 100000

time = GetTickCount_()
For I = 0 To #Tries
  Solve("100+1")
Next
MessageRequester("", Str(GetTickCount_()-time))

;Input()

dracflamloc · Post by **dracflamloc** » Mon Mar 06, 2006 7:01 pm

609 ms =)

Thats pretty good. And yours is WAY faster once you add a couple more operations.

Only problem is when I try and plug it into my scripting language it doesnt seem to function

dracflamloc · Post by **dracflamloc** » Mon Mar 06, 2006 7:06 pm

In my scripting language loop test I loop through 3 while-wend's for a total of 100000 loops, which means 100000 decrements.

The math evaluation takes approximately 500ms using xombies, and the overall time taken for the script to execute is 1700ms.

So thats 1200 ms of logic to chip off. 500ms of arithmetic.

I'm thinking I might add a specific increment and decrement operator like C++ has (i++, i--) to speed up the single operations used in looping even more.

Trond · Post by **Trond** » Mon Mar 06, 2006 7:17 pm

It seems like I optimized a bit too much because it doesn't give the correct result any more.

Don't rely on it.

Edit: I just calculated wrongly in my head! I was wrong, my program is still right!

dracflamloc · Post by **dracflamloc** » Mon Mar 06, 2006 7:50 pm

I think the problem is my script stores the values as floats like "2.000000".

Your algo doesnt correctly compute something like "5.000000+1"

In fact now that I look at it srod's algo has this problem too. Guess I'll stick with Xombies unless I find one that can handle floats and such correctly.

Trond · Post by **Trond** » Mon Mar 06, 2006 8:11 pm

You need to process things like 5.4+1.2 = 6.6? If would be something like this, but for some reason I cannot understand, I get an invalid memory access on ProcedureReturn ValF(Temp).

Edit: I'm in the process of solving the mystery, it seems to be a combination of a PB bug in ValF and one with the boolean evaluation.
Edit: No, that was not the case, it seems to be a serious bug in the debugger. It works correctly without it enabled.
Edit: No, it's with boolean evalution.

Code: Select all

OpenConsole() 

Global Look.s 
Look.s = " " ; Yes, that space is IMPORTANT!!!! Remove and DIE!!! 
Global Stream.s 
Global StreamPos.l        ; Read position in stream 

Procedure.s VisibleToken(s.s) 
  Select s.s 
    Case #CR$ 
      s.s = "newline" 
    Case #LF$ 
      s.s = "newline" 
    Case "" 
      s.s = "nothing" 
  EndSelect 
  ProcedureReturn s.s 
EndProcedure 

;Cleanup then end 
Procedure Finish() 
  PrintN("Ending.") 
  Input() 
  End 
EndProcedure 

;Report an error 
Procedure Error(s.s) 
  PrintN("Error: " + s + ".") 
EndProcedure 

;Report an error and abort 
Procedure Abort(s.s) 
  Error(s.s) 
  Finish() 
EndProcedure 

;Report what was expected 
Procedure Expected(expected.s) 
  Abort("Expected: " + expected + ", got '" + VisibleToken(Look) + "'") 
EndProcedure 

;Read a character into Look 
Goto GetChar_End 
GetChar: 
  PokeB(@Look, PeekB(@Stream + StreamPos)) 
  StreamPos + 1 
  Return 
GetChar_End: 

;Eat whitespace 
Procedure EatWhite() 
  While (Look = " " Or Look = #TAB$) 
    !CALL l_getchar 
  Wend 
EndProcedure 

;Match a specific input character 
Procedure Match(*s.s) 
  If Look <> *s.s 
    Expected("'"+*s.s+"'") 
  Else 
    !CALL l_getchar 
    EatWhite() 
  EndIf 
EndProcedure 

;Get a number 
Procedure.f GetNum() 
  Protected Temp.s
  If (PeekB(@Look) < 48 And PeekB(@Look) > 57) 
    Expected("Integer") 
  EndIf 
  While ((PeekB(@Look) > 47 And PeekB(@Look) < 58) Or PeekB(@Look) = '.') 
    Temp + Look
    !CALL l_getchar 
  Wend 
  ProcedureReturn ValF(Temp)
EndProcedure 

;----- 

Declare.f Expression() 

Procedure.f Factor() 
  Protected Value.f
  If (PeekB(@Look) > 47 And PeekB(@Look) < 58) 
    ProcedureReturn GetNum() 
  Else 
    Match("(") 
    Value = Expression() 
    Match(")") 
  EndIf 
  ProcedureReturn Value 
EndProcedure 

Procedure.f Term() 
  Protected Value.f
  Value = Factor() 
  While (Look = "*" Or Look = "/") 
    If Look = "*" 
      !CALL l_getchar 
      Value * Factor() 
    Else 
      !CALL l_getchar 
      Value / Factor() 
    EndIf 
  Wend 
  ProcedureReturn Value 
EndProcedure 

Procedure.f Expression() 
  Protected Value.f
  If (Look = "+" Or Look = "-") 
    Value = 0 
  Else 
    Value = Term() 
    While (Look = "+" Or Look = "-") 
      If Look = "+" 
        !CALL l_getchar 
        Value + Term() 
      Else 
        !CALL l_getchar 
        Value - Term() 
      EndIf 
    Wend 
  EndIf 
  ProcedureReturn Value 
EndProcedure 

Procedure.f Solve(*s.s) 
  Stream = *s.s 
  StreamPos = 0 
  !CALL l_getchar 
  ProcedureReturn Expression() 
EndProcedure 

#Tries = 100000 

time = GetTickCount_() 
For I = 0 To #Tries 
  Solve("100+1") 
Next 
MessageRequester("", Str(GetTickCount_()-time)) 

;Input()

srod · Post by **srod** » Mon Mar 06, 2006 8:13 pm

dracflamloc wrote:I think the problem is my script stores the values as floats like "2.000000".

Your algo doesnt correctly compute something like "5.000000+1"

In fact now that I look at it srod's algo has this problem too. Guess I'll stick with Xombies unless I find one that can handle floats and such correctly.

Uhm, works okay here! Am I missing something?

Although I agree with the general thrust of this thread in that a reverse polish method of expression evaluation is probably always going to lose out, in speed terms, to a more direct method. It would suit a compiler more than a scripting language.

dracflamloc · Post by **dracflamloc** » Mon Mar 06, 2006 8:17 pm

Code: Select all

Procedure.s DS_XS_Evaluate(*s.s)
  exp.s=PeekS(*s)
  If FindString(Exp,"'",1)>0
    ProcedureReturn DS_XS_Concatenate(Exp)
  EndIf 
 
  Stream = *s.s
  StreamPos = 0
  !CALL l_getchar
  ProcedureReturn StrF(Expression())
EndProcedure 

MessageRequester("",DS_XS_Evaluate("5.000000+1"))

This pops up a messagebox with "5.000000" in it

However with

Code: Select all

MessageRequester("",DS_XS_Evaluate("100+1"))

It pops up 101.000000

Trond · Post by **Trond** » Mon Mar 06, 2006 8:22 pm

dracflamloc wrote:

Code: Select all

Procedure.s DS_XS_Evaluate(*s.s)
  exp.s=PeekS(*s)
  If FindString(Exp,"'",1)>0
    ProcedureReturn DS_XS_Concatenate(Exp)
  EndIf 
 
  Stream = *s.s
  StreamPos = 0
  !CALL l_getchar
  ProcedureReturn StrF(Expression())
EndProcedure 

MessageRequester("",DS_XS_Evaluate("5.000000+1"))

This pops up a messagebox with "5.000000" in it

However with

Code: Select all

MessageRequester("",DS_XS_Evaluate("100+1"))

It pops up 101.000000

The new mine seems to always work, have you tested it?

dracflamloc · Post by **dracflamloc** » Mon Mar 06, 2006 8:24 pm

I wonder how hard it would be to port lua's code for this over to pb...

dracflamloc · Post by **dracflamloc** » Mon Mar 06, 2006 8:30 pm

ProcedureReturn ValF(Temp) gives me invalid memory access with your updated code

Trond · Post by **Trond** » Mon Mar 06, 2006 8:41 pm

dracflamloc wrote:ProcedureReturn ValF(Temp) gives me invalid memory access with your updated code

I forgot something

and so did Fred

. Please try again now, i added some brackets.