uBASIC speed optimizations (topic split from another thread) - page 3 - General Discussion and Assistance - CHDK Forum supplierdeeply

uBASIC speed optimizations (topic split from another thread)

  • 36 Replies
  • 6742 Views
*

Offline reyalp

  • ******
  • 12159
Re: uBASIC speed optimizations (topic split from another thread)
« Reply #20 on: 24 / November / 2011, 01:21:04 »
Advertisements
I've committed my code in changeset 1427.

1420_ubasic.patch doesn't apply in tortoise, says "an unknown line type was found in line 53"
Don't forget what the H stands for.

Re: uBASIC speed optimizations (topic split from another thread)
« Reply #21 on: 24 / November / 2011, 03:08:22 »
Below is patch for 1427.

I have no tortoise installed right now. I do generate it by CHDK-shell and check that CHDK-shell is able to succesfully apply it.

*

Offline whim

  • ******
  • 2013
  • A495/590/620/630 ixus70/115/220/230/300/870 S95
Re: uBASIC speed optimizations (topic split from another thread)
« Reply #22 on: 24 / November / 2011, 09:16:28 »
@tsvstar

GNU diff (as used in CHDK-Shell) and svn-diff often don't play together nicely ....
It does sometimes work, but only if you use the Unix/LF style output, as opposed to the DOS/CRLF style.
(see attached pic of relevant dialog)

cheers,

wim

Re: uBASIC speed optimizations (topic split from another thread)
« Reply #23 on: 24 / November / 2011, 09:26:29 »
Ok. I understand. In attachment same patch but with Unix/LF EOL


Re: uBASIC speed optimizations (topic split from another thread)
« Reply #24 on: 24 / November / 2011, 11:17:51 »
Ok. I understand. In attachment same patch but with Unix/LF EOL
I'm confused.  I believe reyalp added the code to change the way uBasic yields as of v1427. 

Is this then the changes needed for:
Quote
  * Parser optimized to be 4-6 times faster on first pass and 30-40 times faster(runtime compilation used) on next passes
  * Control flow operators are now zero-cost (do not parse script from begin each time). So now size and complexity of script has no matter

And if so, how does that relate to the changes posted as :
No real changes.
1. Just well documenting script.c module before its upcoming improvement
2. Minor renames ( conf.ubasic_vars -> conf.script_vars) to match name to usage.

Also some changes are produced because tab to space replacing.
Ported :   A1200    SD940   G10    Powershot N    G16

Re: uBASIC speed optimizations (topic split from another thread)
« Reply #25 on: 24 / November / 2011, 11:54:24 »
Yes, reyalp add scheduling control in 1427

yes my last attachments this thread are ubasic parser/control_flow enhancement, adapted to 1427.
Easy to just apply them and compare perfomance on yield -1,-1. My camera is in service now so I can't compare by myself.

My last post in "Re: [REQ]Adding new cameras, applying patches into trunk (with source code prepared)" have no relation to ubasic issue.

I have a lot of ready stable code to improve different other aspects of CHDK. And I propose it step-by-step.
Post which you refer to, contain just intermediary changes before futher non-descructable script calls implementation. Good documented code is always save a lot of time in future.
« Last Edit: 24 / November / 2011, 11:56:06 by tsvstar »

Re: uBASIC speed optimizations (topic split from another thread)
« Reply #26 on: 24 / November / 2011, 12:00:20 »
I have a lot of ready stable code to improve different other aspects of CHDK. And I propose it step-by-step.
Post which you refer to, contain just intermediary changes before futher non-descructable script calls implementation. Good documented code is always save a lot of time in future.
Thanks - that makes sense.  What is a "non-descructable script call"  ?
Ported :   A1200    SD940   G10    Powershot N    G16

Re: uBASIC speed optimizations (topic split from another thread)
« Reply #27 on: 24 / November / 2011, 12:28:03 »
Running CHDK script but do not touch currently selected script configuration.

Closest example is such user story:
I do enter into file selector, select file, press left to get into popup menu, select "Edit". CHDK will call script/editor.lua with default settings. But content of "script menu" will not be touched. When I leave editor, same script will be selected as before, same parameter values are applied to it.


*

Offline reyalp

  • ******
  • 12159
Re: uBASIC speed optimizations (topic split from another thread)
« Reply #28 on: 24 / November / 2011, 20:38:00 »
Regarding 1427_basic.patch

I appreciate that you have put a lot of work into this. I'm not completely opposed to having it incorporated in the trunk, but I'm not ready to apply it in it's current form.

It's not immediately clear to me how it works, or whether it is safe and correct. It does appear to make the code significantly more convoluted and harder to maintain. The magic numbers and #ifdefs don't help. To me optimizing ubasic is polishing a turd, so I really don't want to spend a lot of time figuring it out and testing it.

In the past, I've applied some patches I didn't really like with just the assurance that they were well tested, and I've almost always regretted it.

It seems to me there should be a much simpler solution to the re-parsing the entire script for each while/for/goto etc. All you really need to do is store an offset or pointer into the program source, and a way to jump the tokenizer directly to it. For labels, you could run something like the current jump_label once at the start to build a list. For the ones with a stack, you should be able to store the offset with or instead of the line number. This wouldn't be as fast as your patch, but it will still make the runtime independent of program size, and combined with scheduling improvements ubasic will still be hundreds to thousands of times faster than it was before.

If you are writing code complicated enough to need even more performance, you'll be a lot better of using lua anyway.

On the plus side, your code is fast, test program with yield disabled runs in 40ms, vs ~3200ms with the current trunk.
Don't forget what the H stands for.

Re: uBASIC speed optimizations (topic split from another thread)
« Reply #29 on: 25 / November / 2011, 00:16:18 »
This code contain proposed by you changes.

It consist of three different equal by size and infulence(i think) pack of changes:

- Rearranging code in parser. to decrease number of unneeded checks and constant-time most of simple operations detection. this increase parsing speed 4-6 times.

- Runtime compilation. If enabled by #define, after token detection tokenizer check is size in the text enough and override this token right in text with three bytes \0x01-size-token_id. So next time when tokenizer will read this statement, it shouldn't search again what is this token and which its size. Even for rem.
Minor but still safe addition - If number value was asked I do write it in same way to avoid atoi.
This increase second and later passes speed up to 30-40 times faster

- Controlflow operator processing.
For cycles and return I go in same way as proposed by you. I store offset, but also store linenum because it should be tracked to correct display error place if any. I compose this into just integer (16bit+16bit) and call this "mark".
For goto and gosub - we have enough place right in script (size of "goto"+space+label) and already have infrastructure to write there (runtime compilation). So I write mark right after 0x01-size-token.

Advantages of used solution are:
- Ubasic become as fast as LUA
- We absolutely do nothing in heap. Ubasic still tiny with zero memory footprint
- Even for tokenizer almost nothing was changed. It goes in same way in same text. But check using quick tips and new kind of tokens (precompiled) appear.

Disadvantage is:
- Code is just different. I think it is little bit more complicate (yes, because we add some other layers and "classes"), but complexity do not increase a lot.
Personally I as senior software teamleader understand why you are very careful with unclear to you changes. I'm do same things on my job. :) That's why I do not propose this changes before they tested by me in many ways.

Stability:
Most changes (everything except control flow) are isolated inside tokenizer. Main ubasic part have no idea that something was changed.
So how I did test it:
a) I use unit test which call tokenizer for direct, reverse and random tokens. Its pass
b) I write reverter which log answers of tokenizer (convert back from token_id to token_text) and compare results of first and next passes with base scripts. Most existed in repository and in forum scripts was used.
c) I make dump of many complex scripts after precompilation and check that everything is clear
d) I use same reverter to log control flow operations and write test scripts with many for/if/while/goto/gosub etc. It works exactly as it expected
e) I just run different scripts and check are they worked ok

After many iterations this changes are stable.
« Last Edit: 25 / November / 2011, 00:28:07 by tsvstar »

 

Related Topics