Speeding scripts up

[Mikero]

@Thob

much of what you mention above is done on the file read. These wrinkles are parsed out of the script there and then. It raises the issue of a performance hit accompanying any file read that also requires comments to be stripped out as well (sigh). But, in terms of goto's there is NO distinction or performance problem with 1 squillion lines of comment and white space because they are only read (parsed) ONCE (per file read). They do not affect loop time. Only the amount of statements above the #label affect it.

What the engine does is parse all strings of text into a linked list on any file read. This is separate to interpreting, done later.

Each 'object' of the list is a string, containing some pertinent, humanly legible command(s) and a pointer to the next command string, which, conceptually, is the next line of the script. (In fact, the next line of script that isn't a comment a whitespace a tab character eg)

You can see this 'parsing' in the example jpegs provided earlier

If you look reasonably carefully, you'd notice that none of the actual command syntax is touched in any way, it is simply parsed, by the engine, so that only the truly relevent text instruction is kept and all the noise, all the comments, are removed. The important bit is none of this is 'compiled' because if it were, then whether goto's were 90 miles down the page would be irrelevant because they would have been compiled into binary jumps.

Because it is a sequentially ordered, linked list, of statements (which is a very reasonable way to do things), in order to find anything[i/] in that list you have to start at the first one and search for it (DUH!). The engine can't magically 'skip over' 30 lines of text,  to the intended goto label because that label might in fact (and mostly is) behind it. It is the fact that most labels are behind, not ahead, of the goto that makes a 'forward search from current position' intensely wasteful. Most searches would fail, and the engine would have to go to the top and try again. The bis engine simply goes to the top in an all bets are off.

>The number of lines above the target lable

the number of command statements above the target lable, given that there will be a performance hit, once, to get rid of any comments 'above the target label' that is why

goto init
#loop
goto loop

is the fastest performance (search) you can do.

>The number of blank characters at the start of all the lines above the target lable

nope. They don't affect the performance of the loop (as you imagined) they do affect the performance of the script of course.

>The number of lables above the target lable.

nope. Each 'string' is inspected with equal vigour for a match against the label's name. The reason for using # (or any other unique symbol) is to mismatch the search strings asap. An instant first character mismatch between what are labels and what are mostly not labels in the linked list. There would, of course, be some small crunch in examining progressive characters in each encountered #label, but that's trivial. To reinforce the point here, labels are not treated in any special way in the link list, there is no 'tag' to say "i am a label" there is no hash index to say, 'here are the labels'.  Labels are termed 'unnassigned strings' exactly the same way any command with no paramaters is. 'Assigned strings' are items like elephants = 123.4

these are the only two (of four) possible tags used to describe what a 'string' is in a link list (from the piccies above). The other two tags are classes and arrays. This parsed string and it's linked list is the foundation of how the engine creates 'save' files.

[Mikero]

@KTottE

What is the relative performance hit of instantiating new scripts as opposed to jmp:ing to labels

Frightening. An exec requires a file to be read AND parsed (but not interpreted), an existing internal script requires only to be re-interpreted. The _exception_ to this _might_ be sqf (functions) I believe the real difference between them and sqs is that functions remain, as parsed, in memory. ( I am aware of specific differences between sqf and sqs but I suspect *this* is the real difference)

In that instance a sqf call would not be slower, but still need a string search thru a 'resident-in-memory' table similar to a goto #label in most practical respects.

An easy test would be to edit a sqf while a mission is running, if the differences show, then it aint resident and the above is waffle.

> Would performance be gained by using if {} then {}-statements instead?

your first example shows a which statement, 2nd, a classic if else. Anyone sane would assume the which is interpreted faster. The oppposite is true. A which needs massaging back into an if else, each time, every time, it is encountered. The if else construct on the other hand is already predisposed to the internal string tables mentioned earlier {if else is a pseudo class tag, it contains 'body'} my braces are intentional

But i think I misread your Q. 'classic' if else will beat any form of goto each time every time because all statements that affect the if (or the else) are forward references

[THobson]

Mikro:

Thanks for that.  I actually understood it.

On the overall issue of performance and speed of scripts, I think it is worth considering how often and how fast the relevant loops are.  If I have a script that runs once every 5 minutes or so and has a loop through half a dozen units I am not going to be too worried about how fast it all runs.  Other scripts can obviously benefit from a lot of optimisation.

Bye the way, in my experience:

{set; of; instructions} forEach [set, of, elements]

completely blows away a goto/loop combination in terms of how quickly it executes.  But paradoxically it does seem to contribute to lag in the mission as the cpu at least appears to be more dedicated to the forEach instruction than to doing other stuff.  This makes sense as it is only a single instruction, but a lot of work can be packed into it.

[Fragorl]

With nothing much to add as yet, I thought I might just say: very interesting topic, and I'm following it closely

[Terox]

Ok, the reason i misinterpreted the info was because
I already took it that when a script runs it's course, it terminates and removes itself from resident memory

But something so basic was posted in this forum, it then threw me, and i assumed there was more too it.

It was like saying water is wet, but this particular drop is also wet, if you get my meaning




So basically, to summarise this thread

1) Always start your looping scripts with goto "INIT"
2) Have your fastest or most called loop at the top of the script and any additional loops up at the top also

for example

SCRIPT

goto "INIT"

#LOOP
~1
XXXXX
XXXXX
XXXXX
XXXXX
if(condition == whatever)then{goto LOOP}else[exit}

#INIT
_a = _this select 0
_b = whatever
goto "LOOP"

and the reason for the above layout
When a goto command is issued, the scripting engine will start searching for that label at the top of the script, working its way downwards.
So the closer the label is to the top, the less searching it has to do per loop

[Bluelikeu]

@KTottE Frightening. An exec requires a file to be read AND parsed (but not interpreted), an existing internal script requires only to be re-interpreted. The _exception_ to this _might_ be sqf (functions) I believe the real difference between them and sqs is that functions remain, as parsed, in memory. ( I am aware of specific differences between sqf and sqs but I suspect *this* is the real difference)

In that instance a sqf call would not be slower, but still need a string search thru a 'resident-in-memory' table similar to a goto #label in most practical respects.

An easy test would be to edit a sqf while a mission is running, if the differences show, then it aint resident and the above is waffle.

> Would performance be gained by using if {} then {}-statements instead?

your first example shows a which statement, 2nd, a classic if else. Anyone sane would assume the which is interpreted faster. The oppposite is true. A which needs massaging back into an if else, each time, every time, it is encountered. The if else construct on the other hand is already predisposed to the internal string tables mentioned earlier {if else is a pseudo class tag, it contains 'body'} my braces are intentional

But i think I misread your Q. 'classic' if else will beat any form of goto each time every time because all statements that affect the if (or the else) are forward references

How can we be sure of how the BIS team built OFP? Based on what I've seen, programmers nowadays don't care how ineffient their code may be(except for some older-generation people), they rather rely on the idea that faster and better processors will come out to subsitute for their lack of thinking things out before writing them. Also, why do we expect that BIS did a good job in programming? The behaviour of scripts is erratic and you can never count on them even 80% of the time to do what you really want them to. I'm not bashing the BIS team but I think that they could have done a better job. There is absolutely no reason that the scripts should be unreliable.

[Mikero]

@Terox

thank you. That was the point behind the post, neatly summed up by you. We can keep extrapolating examples but that's all they'd be. The principle is to keep recurrent labels at the top and develop techniques to achieve that.

But the rest is not off topic it's just a fascinating (for me) discussion on some internal workings of the engine.

@Blue

>how can we be so sure

scripts but most especially classes, smacks C++ and (most of) what is discussed here has been about parsing the text, not the actual execution or interpretation of those commands. It is unlikely Bis would re-invent wheels from a 'standard' way of parsing these things. Looking at one of the dlls in the game (I forget name, it appears to have a yacc parser embedded in it, perhaps not). Everything about the so-called 'binary' encrypted missions and anything I've ever seen in a save file has structures that would be produced if Bis followed classic parsing techniques.

It is only because Bis do not, then, go on and compile these 'stamements' into binary code that parsing has achieved an importance it doesn't deserve.

@Thob
>{set; of; instructions} forEach [set, of, elements]

that would help to explain some wrinkles where video is clearly not lagging but the game goes temporarily awol, lots of where are you's , things like that. The 'engine' can't keep up with background tasks, but 'appearance' seems normal.

[Sui]

BIS have come a long way since OFP v1.0 in regards to scripting performance... that's for sure.

I remember the days where you could easily create infinite loops by forgetting to put pauses in them! ;D
Some of us had to learn the hard way over and over again not to do that...

the foreach syntax (and I think also the count syntax) are by far the quickest in execution in my humble experience. I often use them for tasks that need 'instant' results, as it seems to take a whole chunk of CPU time and execute the whole operation at once.

eg.
"unit addmagazine {M16}" foreach [1,2,3,4]

Not a 'time critical' example that, but a good example to show that you don't need to include the use of an _x in a foreach loop.

However I did once managed to pause flashpoint for about 10 minutes using a monster foreach call... it ran fine after it had finished, but literally 1 frame every 10 seconds while it was trying to execute it ;D

[THobson]

"unit addmagazine {M16}" foreach [1,2,3,4]

That is one of those - 'now why the hell didn't I think of that' bits of code.  Very neat.  

[h-]

This is actually very nice find...

We tested this on some MCAR guidance codes and it seems to have even visible impact on how the code guides an object...

Of course that may be caused by many other things, psychological 'wrinkles' being one of them and of course OFP itself but somehow it seems to make things a bit smoother since the initializing part of the guidance code is very long before any labels are reached...

So this gave one more optimizing method to use

[shinraiden]

BIS have come a long way since OFP v1.0 in regards to scripting performance... that's for sure.

I remember the days where you could easily create infinite loops by forgetting to put pauses in them! ;D
Some of us had to learn the hard way over and over again not to do that...

the foreach syntax (and I think also the count syntax) are by far the quickest in execution in my humble experience. I often use them for tasks that need 'instant' results, as it seems to take a whole chunk of CPU time and execute the whole operation at once.

eg.
"unit addmagazine {M16}" foreach [1,2,3,4]

Not a 'time critical' example that, but a good example to show that you don't need to include the use of an _x in a foreach loop.

However I did once managed to pause flashpoint for about 10 minutes using a monster foreach call... it ran fine after it had finished, but literally 1 frame every 10 seconds while it was trying to execute it ;D

You should still be able to make a runaway mem leaking hard lock by looping a drop[] with no ~_time in the loop. Even ~0.001 is more than enough to prevent the meltdown.

Further confirmation of some of this discussion I think can be found in the fact that if you exec an unpbo'd script, edit it while the engine is still running, then exec it again, the new script is processed. An example would be to make a 0,0,1 triggered script that displays a hint, exec it, alt-tab and change the string and save, then alt-tab back. Note the new results. Btw, that makes dev for missions and addons exponentially faster. Also, this does not work for files called with PreProcessFile for obvious reasons, as they are pre-loaded.

[Dinger]

ah yes...

Not a 'time critical' example that, but a good example to show that you don't need to include the use of an _x in a foreach loop.

[granpa voice] Back in my day, we didn't have Call, and ForEach on a null value was the only way to do call a string.[/granpa voice]

Now, the discussion:
The goto method described is indeed how I learned that Commodore BASIC processes things.
Whether OFP does, is a different question.
Frankly, I've seen a lot of debate over scripting efficiency over the years, and few people actually basing their theory on anything other than conjecture and parallel reasoning. Folks, those aren't theories, those are hypotheses.

UNN's objection is a valid one, and I'll build on it:
You can save the game state at any time, and look at how the data is stored.
If you look at the scripts section, you'll find that scripts are stored, stripped of comments and blank spaces, in a line-by-line fashion, with each line assigned a number.
Labels are stored separately, as pointers to the line that follows them. This seems to be true even if you have a bunch of labels at the end that are never used.

Therefore, it seems safe to assume -- in the absence of other evidence -- that the method Mikero describes is not the case. Now it may very well be that it is faster, but not for the reason given -- any performance improvement will be a result of the label appearing towards the top of the stack of labels. In any case, I'd like to see some verifiable tests before taking this as dogma.


As for Shin's hypothesis, it's hard to say what exactly happens.
REmember the "preview" in the mission editor is not necessarily the same as running a mission from the mission pbo: the mission editor preview intentionally allows the editor to change scripts "on the fly" -- at least those not running in memory (n.b., if a script is running in memory in the mission editor, and you alt-tab out, change the .sqs, and try to start a new instance of that script, it'll run the old one).

So it has not been determined whether on mission start, the whole mission pbo is loaded into memory, or only the parts that are needed. However, if mission pbos work anything like addon ones (and there is little reason to doubt it), one would suspect they and their contents are mapped to memory at mission start.

So my counter-hypotheses, backed up by what little OFP experience I have:

1. Outside of Mission Editor missions, missions are mapped to (real or virtual) memory
2. When a script is called, it gets parsed into the "game-state":
2.1 Comments and white space are stripped.
2.2 Functions and Wait instructions (@ and ~) are assigned line numbers
2.3 Labels are mapped to line numbers, and put in a separate pile
2.4 Any improvement gained by rearranging file lists is negligeable when compared to the performance costs of parsing instructions at runtime.

Now go show me I'm wrong.

[KTottE]

Heh, so we'll accept Dingers statements as true for now then. Doesn't seem like anyone is up to the task of disproving his statement

[THobson]

If I recall correctly  the view that goto lables are better placed near the top of a script came about at least in part from the fact that

@ condition

is much less laggy than

#wait
~0.5
if inverse_condition then {goto"wait"}

There then followed some discussion as to why that might be.

Dinger is certainly correct.  It is easy to imagine what is going on in the engine, and even to check it by looking at some of the saved bin files.  We just need people with the energy to test it all in mission to see the impact.

[Dinger]

As well all know @ statements will run at least as fast as any kind of goto loop with delay.
@ tells the engine to check the condition every time slice.
~.0001 wait and a goto has the effect of telling the engine to process all the other scripts running before coming back.