Optimum indexing

I guess a lot of my scripts do a lot of loop indexing, so I thought it'd be a good idea to ask what the best techniques for doing this are.

I can see two sets of two cases: either the loop may sometimes have nothing to do (as when processing a possibly empty list) or it is guaranteed to have at least one item to be dealt with (as when processing a touch event), and either the order in which the items are processed is important or it is not. (There's probably more that I haven't encountered yet.)

Here's an opportunity for the forum to save a few nanoseconds before it closes

Well, the simplest case is

integer i;
integer STOP = 10;
for (;i<=STOP,++i)
{ //Do stuff}

which counts up to STOP. If you count down, you can simplify with

integer i=11;
while(--i)
{ //Do stuff}

If you're in a touch (or collision, or sensor) event, where you already have a handy index, you can get rid of the extra counter, so long as you don't need to keep the one triggered by the event.....

touch_start(integer num)
{
while(--num+1)
{ //Do stuff}
}

There's the obvious starter set.......

Well, the simplest case is

integer i;
integer STOP = 10;
for (;i<=STOP,++i)
{ //Do stuff}

which counts up to STOP. If you count down, you can simplify with

integer i=11;
while(--i)
{ //Do stuff}

If you're in a touch (or collision, or sensor) event, where you already have a handy index, you can get rid of the extra counter, so long as you don't need to keep the one triggered by the event.....

touch_start(integer num)
{
while(--num+1)
{ //Do stuff}
}

There's the obvious starter set.......

ETA: Unless you had something else in mind .. ?

an event that can have multiple data set to deal with won't trigger with less than one in it's count variable (touch, collision, sensor) so if you need to process all their inputs, a do while loop is the fastest way to handle them.

depending on if order is important, the optimum is either reverse the order as in this

do{
  --vIntCount;
  //-- code goes here
}while (vIntCount);

or if you absolutely must handle them in forward order...

integer vIdxCnt = 0;
do{
  //-- code goes here using vIdxCnt for your variable
}while (++vIdxCnt < vIntCount);

there's another way to do it but it's not as efficient

unfortunately events don't allow for negative indexes or you could simply use the negative length or index, and add to it in a plain while loop.

lists have an easy trick for walking forwards or backwards during a loop...

vIntCount = (vLstStuff != []); //-- returns list length for walking backwards with --
if the data is processed before the test (do-while) decrement runs before either, if the test comes first (while loop) then the decrement must be after the test, but before preocessing

vIntCount = ([] != vLstStuff); //-- returns negative list length for walking forwards with ++
if the data is processed before the text, use postfix-increment in the test, if the test comes first, increment after the data.

the same rules apply to walking strings, and the structure for getting their count similarly is
vIntCount = llStringLength( vStrStuff ); //-- positive for walking backwards
and
vIntCount = -llStringLength( vStrStuff ); //-- negative for walking forwards

list notes:
with lists, if possible, storing the most likely requested data near the front will save time in some cases.

multiple lists are preferable to searching strided lists. This not only increases your max memory, but it saves time either searching data you can't possibly need, or converting the list to just the strided elements for search.

strides are only better for sorting sets, but it can be done insertion style in multiple lists without too much pain, if you need the searching functionality the most

in the case of a pair of matched lists that store a user key and a timestamp, you can update the timestamp and presort the list by finding the matching key, removing that index from both lists and then re-adding the key and new timestamp to their respective lists.... this is helpful if you are wanting to keep frequent users in the list when you're removing older ones to limit list size.

to limit list size and prevent possible stack heap overflows, you have 2 different data structures you can use...

vLstStuff = llList2List( vLstStuff, 0, ~-vIntMaxCount ); //-- remove entries from the end
vLstStuff = llList2List( vLstStuff, -vIntMaxCount, -1 ); //-- remove entries from the front

both are return vIntMaxCount entry lists, and both are safe with lists that are less than max count. Use the first if you add entries to the front, the second if you add entries to the end.

that's all I can think of for count/index walking at the moment, but I'm sure there's more.

@Rolig (Void posted while I was digesting and replying - more digesting there...): You raise a couple of points that intigue me...

I haven't used for loops since ages ago, mainly on the basis that anything that looks that ugly can't possibly be the best way to go. But perhaps they are more efficient in LSL than using dos and whiles?

For the four cases I mention in my post I tend to go like this...

//A possibly empty list in reverse order
integer index = llGetListLength (my_list);
while (--index > -1)
{
DoSomethingWith (index);
}

//A possibly empty list in order
integer count = llGetListLength (my_list);
integer index = 0;
while (index < count)
{
DoSomethingWith (index++);
}

//A never-empty list (or event returning values to llDetected* functions) in reverse order
event (integer count)//or however else the count is obtained
{
do
{
DoSomethingWith (--count);
} while (count);
}

//A never-empty list (or event returning values to llDetected* functions) in order
event (integer count)
{
index = 0;
do
{
DoSomethingWith (index++);
} while (index < count);
}

I've already asked if for is sometimes better; and I'm looking for suggestions about which of those methods are just plain stupid, and what I should be doing instead, like using your technique of while (--index + 1) instead of my while (--index > -1).

(And I sure hope I've got those samples right - my brain seems in particularly poor condition today.)

I dunno about stupid, Pete. Not being a well-trained scripter, I tend to do whatever works, which means that I truly don't know what works best. I would love to know the answer to your questions myself, though, because I do care what's best.

On the subject of whether to use for ... , while ....., or do .. while, I am hopeless. I began programming in the 60s in Fortran II and then IV, where the only option was "for." I have worked my way through several languages since then, but old habits are hard to break. My mind still snaps first to using "for," even when I know on reflection that there's a smarter way to loop.

At least I'm cured of using GoTo ......

I truly do appreciate seeing Void's list all in one place, BTW. Those are tricks that I have gradually absorbed from her posts and am finally getting comfortable with.

The immediate lessons I think I've learned or had reinforced so far:

DON'T post- or pre-increment in-line when you can do it in the test at the end of a do... while; that *is* just plain stupid.

While I knew about (my_list != []) from the wiki (and do use it, but only in the privacy of my own code), ([] != my_list) for a negative index is a new one on me - I guess I missed it because I haven't thought about using negative indexes for looping before. Clearly, negative indexes are GOOD.

DON'T use strided lists if you don't need to (I keep forgetting the implications of LSL's passing by value habit).

DO try to put your lists together in the optimum order in the first place.

~- is a useful operation that I need to get my head around.

And I'm sure there's more to come as this all sinks in.

My next target is to stop using multiple returns...

the first version in each of the following structures will always be the fastest/smallest...

the major trick here is to avoid extra variables, and comparisons in the test.

guaranteed items in list:

//-- backwards #1
vIntCnt = (vLstStuff != []); // == llGetListLength( vLstStuff )
do{
  // use --vIntCnt on the first needed line... faster, but potentially
  // breakable used on the same code line with multiple references to vIntCnt
while (vIntCnt); // vIntCnt will be 0 after exit

//-- backwards #2
vIntCnt = ~-(vLstStuff != []); // == llGetListLength( vLstStuff ) - 1
do{
  // code goes here, note possible inaccuracy of vIntCnt on exit
while (vIntCnt--); // vIntCnt will be -1 after exit

//-- forwards #1
vIntCnt = ([] != vLstStuff); // == -(llGetListLength( vLstStuff ))
do{
  // code goes here
while (++vIntCnt); // vIntCnt will be 0 after exit

//-- forward #1a (safety for functions that don't accept negative indexes)
vIntMax = (vLstStuff != []); // == llGetListLength( vLstStuff )
vIntCnt = 0;
do{
  // code goes here
while (++vIntCnt < vIntMax); // vIntCnt will be vIntMax after exit

possibly empty lists:

//-- backwards #1
vIntCnt = (vLstStuff != []); // == llGetListLength( vLstStuff )
while (vIntCnt){
  // use --vIntCnt on the first needed line... faster, but potentially
  // breakable used on the same code line with multiple references to vIntCnt
} // vIntCnt will be 0 after exit

//-- backwards #2
vIntCnt = (vLstStuff != []); // == llGetListLength( vLstStuff )
while (vIntCnt--){
  // code goes here, note the possible inaccuracy on exit for vIntCnt.
} // vIntCnt will be -1 after exit

//-- forwards #1
vIntCnt = ~-([] != vLstStuff); // == -(llGetListLength( vLstStuff )) - 1
while (++vIntCnt){
  // code goes here
}  // vIntCnt will be 0 after exit

//-- forwards #1a (safety for functions that don't accept negative indexes)
vIntMax = (vLstStuff != []); // == llGetListLength( vLstStuff )
vIntCnt = -1;
while (++vIntCnt < vIntMax){
  // code goes here
} // vIntCnt will be vIntMax after exit

I can't remember if it's faster to subtract or compare in the tests, so I left the safety versions of of the forward walks as comparisons... technically it's faster to compare them with the bitwise XOR operator (^) regardless, since matching numbers will return 0 / FALSE, but talarus would have a stroke if you did that

notes:
for functions that accept negative indexes, 0 == -llGetListLength( x );

--var
is faster than
var--

var--
is faster than
var
--var
and less space

-~var
is faster and less space than
var + 1

(~-var)
is faster and less space than
var - 1
but should be enclosed in brackets for safety, since there is a compiler bug that screws with the order of operations there

those two are easiest to remember what they do if you remember that if negative is closest to the variable, it's subtract

(vLstStuff != [])
is faster less space than
llGetListLength( vLstStuff )

([] != vLstStuff)
is faster and less space than
-llGetListLength( vLstStuff )

the action of != on lists is (ListA != listB) == (llGetListLength( listA ) - llGetListLength( listB ))

loop structures in order of speed (fastest first)
do-while
while
@-if-jump (not recommended at this time, used to be the fastest, may still be in LSO)
for

there are also event chained loops where an action that triggers an event is then repeated in the action... these are still technically the fastest loops available... an example would be calling a color change from the changed event (which will fire the changed event again with CHANGED_COLOR).... I do NOT recommend using these types of loops EVER because they play holy hell with script time in the sim, and if they are visible or physical changes they will also spike bandwidth with updates (especially for people in render range) and cause "Very Bad Things™" with physics

I dunno about stupid, Pete. Not being a well-trained scripter, I tend to do whatever works, which means that I truly don't know what works best. I would love to know the answer to your questions myself, though, because I do care what's best.

On the subject of whether to use for ... , while ....., or do .. while, I am hopeless. I began programming in the 60s in Fortran II and then IV, where the only option was "for." I have worked my way through several languages since then, but old habits are hard to break. My mind still snaps first to using "for," even when I know on reflection that there's a smarter way to loop.

At least I'm cured of using GoTo ......

I truly do appreciate seeing Void's list all in one place, BTW. Those are tricks that I have gradually absorbed from her posts and am finally getting comfortable with.

ETA: Damn. I deleted two double posts, and the one that's left is out of sequence now.

... preview will help avoid those nasty 500 error double posts..

I dunno about stupid, Pete. Not being a well-trained scripter, I tend to do whatever works, which means that I truly don't know what works best. I would love to know the answer to your questions myself, though, because I do care what's best.

On the subject of whether to use for ... , while ....., or do .. while, I am hopeless. I began programming in the 60s in Fortran II and then IV, where the only option was "for." I have worked my way through several languages since then, but old habits are hard to break. My mind still snaps first to using "for," even when I know on reflection that there's a smarter way to loop.

At least I'm cured of using GoTo ......

I truly do appreciate seeing Void's list all in one place, BTW. Those are tricks that I have gradually absorbed from her posts and am finally getting comfortable with.

LOL... I've been wrestling with 500 errors in these %&^% forums all day. I can't tell when something gets posted (or double posted) until I finally get a page to load. Thanks, as always, for the tip.

Chapter and verse, Void. Thank you very much indeed.

I realise this is all pretty basic stuff, and I guess one of the things that makes it basic is that it appears in some form in virtually every script that goes beyond "Hello, Avatar!". That post deserves a wiki page to itself.

the page is now going into my archives for help, it'll probably be added to my user page in some form and crosslinked wherever it applies.

on one hand, it is basic because it deals with structures that are almost always in use in one form or another, in another sense it's an advanced topic as it deals with the specific quirks of LSL, some gathered by accidents and long experience, and deals with the efficiency of each structure... dunno if I'll try to separate out the two concepts or leave it as a whole.

if I'm lucky I can get the rest of the scripting library archived before the next wave of 500 errors strikes... this is becoming ridiculous.

Thanks for asking the question, Pete, and THANK you Void, for the responses. I no longer trust bookmarks. Even if LL magically resurrects the forum archives at some point, this one is going directly into my hard drive now.