Lists are funny things in LSL; their basic functions are not implemented as efficiently as they should have been. Furthermore, the very nature of call-by-value requires that lists be copied in their entirety as function parameters. Under the old interpreter, this often resulted in stack-heap errors for long lists.
Luckily things are a bit better under Mono. I have yet to receive a stack-heap error under Mono, but admittedly I may be in the habit of coding defensively now. And its implementation of lists now seems reasonable enough to forgo the obscure hacks developed even for simple list operations, such as the addition of an element.
Lists nevertheless are not arrays per se; any operation to construct, examine, and traverse lists will take a few more machine cycles than anyone has a desire to expect. Much of this comes from the need to call system functions explicitly to obtain any information about a list. So coders continue to look for ways to speed up the process.
I’ll set up a very basic loop which examines each node/entry:
[lsl]
Traverse_List (list myList) {
integer position;
for (position = 0; position < llGetListLength (myList); ++position) {
integer entry = llList2Integer (myList, position);
// Do something with the entry value here.
}
}
default {
state_entry() {
Traverse_List ([4, -87, -23, -145, 1, -812, -37, -790, 9, -71, 6]);
}
}
[/lsl]
Notice I have constructed a list of numbers in which each entry greater than one decimal digit in length is negative. This just permits a test condition which allows me to confirm the results of my code at a glance.
If I were simply to examine the list without modifying it, then I would isolate the loop invariant, the list length. Without researching the benchmarks, I’ll accept the hypothesis that it is far more efficient to cache an unchanging value in a local variable than to call a system function that returns the same value in every iteration. I’ll leave it to others to prove it.
While I’m at it, I’ll shave off a few cycles by initializing the loop variable at the time of declaration. I consider this simply a personal stylistic choice, acceptable because it does not violate the integrity of the control structure.
With these two changes in place, the script now looks like this:
[lsl]
Traverse_List (list myList) {
integer position = 0;
integer limit = llGetListLength (myList);
for (; position < limit; ++position) {
integer entry = llList2Integer (myList, position);
// Do something with the entry value here.
}
}
default {
state_entry() {
Traverse_List ([4, -87, -23, -145, 1, -812, -37, -790, 9, -71, 6]);
}
}
[/lsl]
Let’s filter this list to remove negative-number entries. My first reaction luckily coincides with good practice, that being to copy the nonnegative numbers into a new list, rather than deleting the negative numbers from my input:
[lsl]
list Ignore_Negatives (list myList) {
integer position = 0;
integer limit = llGetListLength (myList);
list newlist = [];
for (; position < limit; ++position) {
integer entry = llList2Integer (myList, position);
if (entry >= 0)
newlist += [entry];
}
return newlist;
}
default {
state_entry() {
list numbers = [4, -87, -23, -145, 1, -812, -37, -790, 9, -71, 6] ;
llOwnerSay ("Original list: " + llDumpList2String (numbers, ", "));
list no_negatives = Ignore_Negatives (numbers);
llOwnerSay ("Filtered list: " + llDumpList2String (no_negatives, ", "));
}
}
[/lsl]
By this time, I’m sure some of you out there are politely encouraging me to abandon the stereotypically good practice of encapsulating subroutine data into local variables, which requires the communication of global values through function parameters. That would certainly be da rigor in most languages.
LSL, of course, isn’t quite like most languages; it just looks like them. If LSL had implemented call-by-reference for its formal function parameters, then I would adopt this syntax for production code in a heartbeat; but it doesn’t, so normally I won’t. Though scalar variables such as integers benefit from encapsulation in LSL, for efficient memory management it is far more practical though far more dangerous to access a global list variable in a subroutine than it is to copy a potentially long list onto the limited stack as call-by-value requires. Sometimes it sucks to be us.
I will now stipulate that we don’t need the original list once it has been modified, so let’s try to work our magic upon the only copy of the input list. To simulate a more real virtual-world example, I will trigger the modification upon touch and move the subroutine code directly into the event. To ensure that this modification occurs only once, I will change state. And to access the same variable in different events, I will transfer the input list into the global scope:
[lsl]
list g_numbers = [4, -87, -23, -145, 1, -812, -37, -790, 9, -71, 6];
default {
state_entry() {
llOwnerSay ("Original list: " + llDumpList2String (g_numbers, ", "));
}
touch_start (integer numDetected) {
integer position = 0;
integer limit = llGetListLength (g_numbers);
// Will this delete negative numbers from the given input list?
for (; position < limit; ++position) {
if (llList2Integer (g_numbers, position) < 0)
g_numbers = llDeleteSubList (g_numbers, position, position);
}
state NEXT_STEP;
}
state_exit() {
llOwnerSay ("Filtered list: " + llDumpList2String (g_numbers, ", "));
}
}
state NEXT_STEP {
state_entry() {
// Perform the next step in the process.
}
}
[/lsl]
Pretty cool, huh? There’s only one problem: it doesn’t work. Yet. Before proceeding, see if you can tell where the problem lies.
(Feel free to insert your favorite quiz-show Muzak here.)
The problem is that I am modifying the list I am traversing. Once an entry is deleted, the list length is no longer a loop invariant, and the loop counter after its increment no longer points to the entry I expect within the list.
To fix this, the retrieval of the list length goes back into the loop header, and the loop counter is incremented only if the entry examined in that iteration is not deleted. The for header is then better written as a while:
[lsl]
list g_numbers = [4, -87, -23, -145, 1, -812, -37, -790, 9, -71, 6];
default {
state_entry() {
llOwnerSay ("Original list: " + llDumpList2String (g_numbers, ", "));
}
touch_start (integer numDetected) {
integer position = 0;
// This will delete negative numbers from the given input list.
while (position < llGetListLength (g_numbers)) {
if (llList2Integer (g_numbers, position) < 0)
g_numbers = llDeleteSubList (g_numbers, position, position);
else
++position;
}
state NEXT_STEP;
}
state_exit() {
llOwnerSay ("Filtered list: " + llDumpList2String (g_numbers, ", "));
}
}
state NEXT_STEP {
state_entry() {
// Perform the next step in the process.
}
}
[/lsl]
I have used the above model often, which produces the expected and desired effect. We can, however, avoid a conditional adjustment by stepping down the list instead of up. When an entry is deleted, we just decrement to the next lower entry unconditionally. Let’s focus on the loop, which now no longer needs to recompute the list length with every iteration:
[lsl]
integer position = llGetListLength (g_numbers);
while (–position >= 0) {
if (llList2Integer (g_numbers, position) < 0)
g_numbers = llDeleteSubList (g_numbers, position, position);
}
[/lsl]
Lately I came across a delightful, alternate coding for this same function, which is not so much a better method as it is an intriguingly different way of looking at the problem. Allow me to present this piece of resistance, which I place in the above framework. Here first is a conservative rendition, again focusing on the loop:
[lsl]
// Use the negative (two’s complement) of the list length.
integer position = – llGetListLength (g_numbers);
for (; position < 0; ++position) {
if (llList2Integer (g_numbers, position) < 0)
g_numbers = llDeleteSubList (g_numbers, position, position);
}
[/lsl]
The loop counter here, instead of a positive offset from the start of the list, ascends as a negative index from the end. The limit is zero, since the last entry in the list can be specified by an index of -1. When an entry is deleted, the negative index can be incremented without conditional adjustment.
Now, if you really want to get fancy, you can take advantage of the one’s complement of the length—that is, a reversal of all its bits—instead of using the negative, which is the two’s complement. This allows you to simplify the loop header even further:
[lsl]
// Use the one’s complement of the list length.
integer position = ~ llGetListLength (g_numbers);
while (++position) {
if (llList2Integer (g_numbers, position) < 0)
g_numbers = llDeleteSubList (g_numbers, position, position);
}
[/lsl]
Granted, this “backwards” way of looking at loop traversal requires a bit (as it were) of knowledge about the binary system and its manipulations, but the code is sound, well structured, and I think a tad more elegant than my version.
I think I’ll start using this implementation, just for fun.