Page 1 of 4
Need a fast infix math evaluator
Posted: Mon Mar 06, 2006 1:55 am
by dracflamloc
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 =)
Posted: Mon Mar 06, 2006 5:01 pm
by Trond
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?
Faster code below
Posted: Mon Mar 06, 2006 5:51 pm
by dracflamloc
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.
Posted: Mon Mar 06, 2006 6:36 pm
by Trond
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()
Posted: Mon Mar 06, 2006 7:01 pm
by dracflamloc
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
Posted: Mon Mar 06, 2006 7:06 pm
by dracflamloc
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.
Posted: Mon Mar 06, 2006 7:17 pm
by Trond
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!
Posted: Mon Mar 06, 2006 7:50 pm
by dracflamloc
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.
Posted: Mon Mar 06, 2006 8:11 pm
by Trond
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()
Posted: Mon Mar 06, 2006 8:13 pm
by srod
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.
Posted: Mon Mar 06, 2006 8:17 pm
by dracflamloc
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
Posted: Mon Mar 06, 2006 8:22 pm
by Trond
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?
Posted: Mon Mar 06, 2006 8:24 pm
by dracflamloc
I wonder how hard it would be to port lua's code for this over to pb...
Posted: Mon Mar 06, 2006 8:30 pm
by dracflamloc
ProcedureReturn ValF(Temp) gives me invalid memory access with your updated code
Posted: Mon Mar 06, 2006 8:41 pm
by Trond
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.