On the efficiency of list access

Hi, I made a few simple tests to try to decypher what kind of implementation lists use and determine how lists can be accessed most efficiently.

For list accesses I tried accessing the first element of a list 500 time, the middle element of the list 500 times, and the last element of a list 500 times (using a 300 element list). I also tried to access the first nad last elements of a list alternately, as well as the first and middle, and middle and last element. I timed them all and got:

stats: Retrieving first element 500 times.
stats: Operation took: 23.197552 seconds
stats: Retrieving middle element 500 times.
stats: Operation took: 23.649410 seconds
stats: Retrieving last element 500 times.
stats: Operation took: 24.349136 seconds
stats: Flip-flop test: first and last: 500 accesses.
stats: Operation took: 19.149178 seconds
stats: Flip-flop test: first and middle: 500 accesses.
stats: Operation took: 18.698975 seconds
stats: Flip-flop test: middle and last: 500 accesses.
stats: Operation took: 19.166626 seconds

It seems to me that even if accessing lists is a linear walk through the list, its fast enough compared to whatever else the script does. Otherwise there does not seem to be enough evidence to say whether accessing an element of a list is O(1) or O(n).

====

Another issue I've seen is passing lists to functions. The conventional wisdom is that passing large lists takes more time than passing small ones, but that does bear out in my tests (again, its a 300-element list).

stats: Passing empty list 500 times
stats: Operation took: 8.759567 seconds
stats: Passing large list 500 times
stats: Operation took: 8.299210 seconds

====

My question is, what do you make of these numbers? Can I assume constant time access to an arbitrary element of a list? Does anyone know how LSL lists really behave?

anyway, below is the code for my tests.

list zero = [];
list small = [0,1,2,3,4,5,6,7,8,9];
list medium = [];
list large = [];

float get_elem(list l, integer pos, integer iters) {
    integer i;
    float x = llGetTime();
    for(i = 0; i < iters; i++) {
        llList2Integer(l, pos);    
    }
    return llGetTime() - x;
}

float flip_flop_test(list l, integer pos1, integer pos2, integer iters) {
    integer i;
    float x = llGetTime();
    iters = iters/2;
    for(i = 0; i < iters; i++) {
        llList2Integer(l, pos1);
        llList2Integer(l, pos2);   
    }
    return llGetTime() - x;   
}

float proc_test(list l, integer iters) {
    integer i;
    float x = llGetTime();
    for(i = 0; i < iters; i++) {
        pass_list(l);  
    }
    return llGetTime() - x;  
}

pass_list(list l) {
    return;   
}

default
{
    state_entry()
    {
        llSay(0, "Creating medium list...");
        integer i;
        for(i = 0; i < 100; i++) {
            medium += i;   
        }
        
        llSay(0, "Creating large list...");
        for(i = 0; i < 300; i++) {
            large += i;   
        }
        llSay(0, "Done.... touch me to run tests.");
    }

    touch_start(integer total_number)
    {
        if(llDetectedKey(0) != llGetOwner()) {
            return;   
        }
        
        float tm;
        llSay(0, "Retrieving first element 500 times.");
        tm = get_elem(large, 0, 500);
        llSay(0, "Operation took: " + (string) tm + " seconds");

        llSay(0, "Retrieving middle element 500 times.");
        tm = get_elem(large, llGetListLength(large)/2, 500);
        llSay(0, "Operation took: " + (string) tm + " seconds");
                     
        llSay(0, "Retrieving last element 500 times.");
        tm = get_elem(large, llGetListLength(large) - 1, 500);
        llSay(0, "Operation took: " + (string) tm + " seconds");
        
        llSay(0, "Flip-flop test: first and last: 500 accesses.");
        tm = flip_flop_test(large, 0, llGetListLength(large) - 1, 500);
        llSay(0, "Operation took: " + (string) tm + " seconds");
        
        llSay(0, "Flip-flop test: first and middle: 500 accesses.");
        tm = flip_flop_test(large, 0, llGetListLength(large)/2, 500);
        llSay(0, "Operation took: " + (string) tm + " seconds");
        
        llSay(0, "Flip-flop test: middle and last: 500 accesses.");
        tm = flip_flop_test(large, llGetListLength(large)/2, 
                                    llGetListLength(large) - 1, 500);
        llSay(0, "Operation took: " + (string) tm + " seconds");
        
        llSay(0, "Passing empty list 500 times");
        tm = proc_test(zero, 500);
        llSay(0, "Operation took: " + (string) tm + " seconds");
        
        llSay(0, "Passing large list 500 times");
        tm = proc_test(large, 500);
        llSay(0, "Operation took: " + (string) tm + " seconds");
        
    }
}

ehhh... scripter's talk.

As I understand lists, you're simply compiling multiple entries of bytecode into a convenient data store (the list itself). It makes sense, then, that callback functions for any entry in the list itself would be fairly rapid at the back end.

Thing with lists, though, is they're strange animals - usually you can only declare 71 or so entries upfront, and what appears to be an arbitrary amount up until you hit the script buffer and the script shuts itself down with a script.

So the moral of the story is, for all practical purposes that I can see (sans time to parse a list from a loop, which is linear), the access speed to list entries is roughly the same, regardless of entry.

Phew. That's a bit too much nerd talk for even me to maintain for long.

This I beleive is based on the compilers memory limitations.

It's good to know that list access speed is independant of list entry requested.

As far as the implementation goes, Flyingroc's results suggest that lists are hashed for near-linear time random access.

With respect to passing variables, yes, they appear to be passed by value, but I believe some things (like lists) might be passed by reference if the conditions are right. The pass_list function may not be that useful as implemented, because it doesn't actually do anything with the list; we don't know what sort of optimization the compiler might be doing. It would probably be a more useful test to make pass_list actually access the first item in the list, or better still, modify an item (the same each time, naturally, for consistency).

Finally, the "beginning", "middle", and "end" access tests could be specious -- it is a well-known, and oft-used trick to keep convenience handles to the first and last elements of a list, and probably not unheard-of to do the same for the middle element. A random-access test would probably be a more reliable indicator of performance.