Improving lists

Okay, lists suck. Now, while I'm still hoping that arrays are on their way, there are cases where lists /should/ be more efficient than using an array, but aren't.

To this end, I would like to gather ideas on improving LSL's implementation of lists, so that we can use them more efficiently.

One of my main gripes is the inability to modify list-entries without creating a whole new copy of the list they reside in. This makes it very inefficient to have, for example, a list of counters which are incremented depending on some criteria such as counting how many times each avatar in range was found by a sensor.
To this end I've made a JIRA proposal for editing basic data-types 'in-place' so that we can change the value of list-entries we know to be integers, floats, vectors or rotations. Here is the proposal:
http://jira.secondlife.com/browse/SVC-2861

Essentially what I'd like is for lists to behave more like actual linked-lists, whereby they can shrink, grow and change with very little cost except in searching/sorting them (which other data-types are better suited for anyway). Arrays are great for things of fixed size, but lists should in theory be better for items with variable length. However, currently they're just uncompromisingly crap.

Screw that, I'd rather have real arrays.

Arrays are fine for data-sets of fixed size, and can be used cleverly I suppose (make the array too big then have an integer defining how much you've actually used), but useful linked-lists are still a good thing to have for several reasons as they have advantages over arrays:
- They do not require contiguous blocks of memory, as entries link to one another, thus they can fit more easily into low-memory objects.
- There is very little cost to insert an entry into a proper linked-list. By insert I mean (for example) placing a new entry at index 4 in a 10 item list, shifting later entries 'right' (so the old entry 4 becomes entry 5, 5 becomes 6 etc.).
- Likewise with removing items, it takes very little to remove an entry from an actual linked-list.
- Linked lists can contain a range of data-types of varying size.

Current LSL lists of course have none of these advantages, as it's impossible to modify them in-place (a copy is always created), it's also unclear if they are single-linked (entries only point to the next one) or double-linked (entries point to both the previous and next entry for faster traversal).

I know what linked lists are, I did have OOP education.

The thing is, LSL's lists aren't linked lists. There somewhere between linked lists and arrays. You define them like an array, interact with them like an array (except for all the nice my_arry[n] = i fancy stuff), but are stored in a manner like linked lists (only without all the neat fancy stuff you can do with a linked list, my_list.Object.previousObject.nextObject = my_list.Object.nextObject, instant deletion!)

It's like we have all the annoying parts of each, and none of the good parts.

Their likeness to arrays seems circumstantial really, the [item1, item2, ... itemn] notation seems for convenience only unfortunately =(

However, as I understand it they ARE implemented as linked-lists, so in theory we could have at least the advantages of a linked-list if only we could manipulate them by reference instead of copying them all the time.

It's just that if we do get arrays now that Mono is here and in theory they should be simple (since Mono happily supports languages with arrays anyway) then there's no reason to keep lists unless they are made more useful, as everyone will just switch to arrays. Even in cases where lists SHOULD be better an array will always be more useful with lists in their current state; if you have an ever growing list of items for example then you would just use an over-large array instead with a counter to track how many entries you have.

Actually my biggest problem with lists is how much memory they gobble up in an already memory-starved environment.

A singly-linked list of integers 100 elements large should only take up 800 bytes (100 x (4 + 4)), but because of the fact that each element must keep track of its type + whatever other book-keeping info, you end up with a list of 100 ints taking up 2k bytes or so. Madness.

-Savant Hax