Need a fast infix math evaluator

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

Updated code works.

Overall using my speed.ds:

qwe=10
While qwe>0
	;messagebox qwe,'exec first loop'
	asd=100
	While asd>0
		;messagebox asd,'exec second loop'
		zxc=100
		While zxc>0
			;messagebox zxc,'exec third loop'
			zxc=zxc-1
		Wend
		asd=asd-1
	Wend
	qwe=qwe-1
Wend

Your algo comes in about 1000ms slower than Xombies.

THe 100,000 times test of 100+1 comes in at 750ms with your new code. Xombies still 530 or so.

However: With a complex operation like "100.000000-1*6+7.9/8.334", you finished in 1200ms and Xombies took 4900ms.

So your code is darn good. Just missing that simplistic case that happens to be o so important =) Good work so far though!

But anyway I've written the code so its pretty easy for any evaluation algo to be used. In a few days I'll release the first version of the code to everyone here.

akj · Post by **akj** » Mon Mar 06, 2006 10:35 pm

Trond, I have spotted a few bugs:

Code: Select all

While ((PeekB(@Look) > 47 And PeekB(@Look) < 58) Or PeekB(@Look) = '.')

should be:

Code: Select all

While ((PeekB(@Look) > 47 And PeekB(@Look) < 58)) Or PeekB(@Look) = '.'

Expression() needs rewriting as:

Code: Select all

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

This will then correctly handle expressions like -(2+3) having a leading + or - sign. However, it will still not handle -(2+-3).

Also, instead of repeatedly calling EatWhite(), it will probably be faster to remove all whitespace initially by using RemoveString() within Solve().

jack · Post by **jack** » Mon Mar 06, 2006 10:37 pm

if you want speed, byte compile your script, for example i wrote an eval routine many years ago that byte compiles the expression and then evaluates it.
my routine evaluates "100+1" 100000 times in 125 ms vs Trond's 280 ms
sorry for not posting the code, it's way ugly.

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

I don't see the problem with

Code: Select all

While ((PeekB(@Look) > 47 And PeekB(@Look) < 58) Or PeekB(@Look) = '.')

akj · Post by **akj** » Mon Mar 06, 2006 11:09 pm

Sorry Dracflamloc,

I now realise that your code is correct.

I was mislead by the Reference Manual section of the Help file which stated that the operators AND and OR had equal priority. But I now realise that AND (correctly) has greater priority than OR.

The relevant extract from the Reference Manual is:

Operators priorities
Priority Level | Operators
---------------+---------------------
7 | ~
6 | <<, >>, %, !
5 | |, &
4 | *, /
3 | +, -
2 | >, >=, <, <=, =, <>
1 | And, Or, Not, XOr

But it seems to me this does not exactly reflect the compiler's expression evaluation logic. I think the bottom line should be further prioritised:
Not
And
Or, Xor

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

no prob

Trond · Post by **Trond** » Tue Mar 07, 2006 2:08 pm

dracflamloc wrote:Updated code works.

THe 100,000 times test of 100+1 comes in at 750ms with your new code. Xombies still 530 or so.

However: With a complex operation like "100.000000-1*6+7.9/8.334", you finished in 1200ms and Xombies took 4900ms.

So your code is darn good. Just missing that simplistic case that happens to be o so important =) Good work so far though!

Arg, Xombie must have done some dark magic, how did his get so fast on 100+1?

Also, instead of repeatedly calling EatWhite(), it will probably be faster to remove all whitespace initially by using RemoveString() within Solve().

Great idea, thanks for that!

Initially the program was written to be exandable with strings, that's why I did it that way.

Edit:
Are you absolutely sure that your speed tests are correct? On my computer:
My evaluator with EatWhite() replaced by a single RemoveString() at the start calculates 100+1 in about 395 milliseconds.
Xombie's evaluator uses about 635 milliseconds to complete the same test.
I used this code: http://pastebin.com/588805

dracflamloc · Post by **dracflamloc** » Tue Mar 07, 2006 3:24 pm

I'll try it with a single removestring then!

Trond · Post by **Trond** » Tue Mar 07, 2006 3:31 pm

dracflamloc wrote:I'll try it with a single removestring then!

It's in the test code I posted in the post above yours.

dracflamloc · Post by **dracflamloc** » Tue Mar 07, 2006 3:40 pm

Nice!

Its almost exactly the same as Xombies on this computer (P4 3.2ghz) for the 100+1 case.

Pretty darn awesome! Thanks!

Now I just need to go through your code and add "DS_" to everything to make sure it doesnt conflict with people's projects =P

Xombie · Post by **Xombie** » Tue Mar 07, 2006 7:54 pm

Ahah! A secret topic that I didn't see

dracflamloc - I update my code under my posting. I grabbed Trond's code from http://pastebin.com/588805 and ran his test. On this computer I get 578 from my old code and 360 from Trond's code.

However, with my latest code that I uploaded, I get about 187 on my code and 360 on Trond's.

Running it with a more complex equation still shows mine as slower. With "100.000000-1*6+7.9/8.334" my old code takes about 5530 with the new code taking 2141. Trond's take 1187.

I'll take a look to see if I can get mine to handle larger expressions more quickly.

Nik · Post by **Nik** » Tue Mar 07, 2006 8:48 pm

The cooles possible way would be to use the expression evaluater that transaltes ithe expression to asm and instead of letting it compile to mnenemonics you could let i produce mashien code with the needed procedure code and then use this procedure to process it, should be verry fast if you do the compiling when the script is loaded, this would be a little JITC which would then be cool marketing.
Sorry just had to post this crazy idea.

Trond · Post by **Trond** » Tue Mar 07, 2006 8:55 pm

Nik wrote:The cooles possible way would be to use the expression evaluater that transaltes ithe expression to asm and instead of letting it compile to mnenemonics you could let i produce mashien code with the needed procedure code and then use this procedure to process it, should be verry fast if you do the compiling when the script is loaded, this would be a little JITC which would then be cool marketing.
Sorry just had to post this crazy idea.

Or even faster: Just compile it to asm in the first place!

dracflamloc · Post by **dracflamloc** » Tue Mar 07, 2006 8:56 pm

Just tested your new evaluator in dracscript. Runs pretty good. Thats a huge improvement over the last one. =)

Hopefully we can get the complex equation time down a bit.

Nik · Post by **Nik** » Tue Mar 07, 2006 8:57 pm

Then it's not a scripting language anymore and it's alot harder, but you could combine mashine with scripting code, only using compiled stuff for mathematic functions, and JITC are really cool I think