[Opensim-users] LSL could support nested lists

[Haravikk]

> On 27 Feb 2019, at 09:05, Ethan Gardener <eekee57 at fastmail.fm> wrote:
> 
> On Tue, Feb 26, 2019, at 10:16 PM, Haravikk wrote:
>> [...] I mean seriously, no proper array but instead we 
>> get a linked-list that is fully copied on even minor modifications, 
> 
> I remembered this just as I was falling asleep after my last big email.  Basically, LSL has two ways of preventing reference loops, each of which is quite good enough on its own.  Given that a list is copied on even the smallest of modifications, there's no reason to prevent lists containing list references. There's no way to make a circular reference because each list becomes immutable before its reference can be obtained.  
> 
> We could have nested lists as soon as appropriate functions could be designed and implemented.  (Now I think about it, I can't understand why no-one's implemented it before.)

That's an interesting point, though strictly speaking I'm not sure reference loops are something LSL ever needed to worry about; if you use it to create a memory leak in your script then it only ever affects that script (runs out of memory and halts), and traversal loops can only becomes an infinite loop if you also use recursion to do-so, but again it only affects the one script which is throttled and currently would then run out of stack space and halt.

So while it's useful not to have this as a possibility I'm not sure I'm convinced it was an intentional decision; after all, without the ability to add lists, plus an llList2NestedList() function to retrieve them it was never going to be a problem anyway. Even if it did all that was really required was a warning "don't put lists inside themselves, ya dafty", just like divide by zero and other things you just have to learn.

> Don't get hung up on it being a linked list, the truth about performance is often very surprising and quite contrary to popular opinion.  For instance, a hash table may spend more time hashing than a linked list would searching.  This was an actual *serious* problem a few years ago with programmers producing terribly slow designs because they thought some techniques were always faster.  It's probably still going on, but I stopped paying attention because it makes me angry.  (Same with the async i/o / node.js hubris.)  In any case, because it's always copied, the actual implementation could be anything.

Sure, but there are only really two main advantages to linked-lists, the first being that they don't require contiguous memory (which makes some sense in a very constrained memory environment) the second is that adding or removing the head of a linked list is very fast (same with the tail if the list includes a reference to that as well), which can make them good for use as queues in certain scenarios. There are also weirder things you can do with them like constant time appends (add one linked list onto the tail of another) or certain sorts that swap entire chunks of the list around but none of these apply to LSL either.

The big problem with the decisions around lists in LSL is that the fragmentation problem is only really a problem because of the linked lists in the first place, and under Mono I don't believe it's a problem at all (total memory used is just a value, there's no true stack heap collision, you can verify this using strings since they're contiguous). Meanwhile the design decision around copying meant that the low overhead add/remove to head/tail was eliminated entirely.

But yeah, you're right that there's no real reason that OpenSim can't just implement "lists" however it wants behind the scenes, even using arrays, since none of the functions enforce the use of a list rather than any indexed container, ignoring the naming, and it's just a compilation detail. All a user would see is faster access and less overhead, depending upon how array sizing was implemented (e.g- double in size up to 64, then add to size in increments of 64 to keep things sane, rather than always doubling as is common).

I have always been interested in the technical aspects of it all, but it's not easy to shake the feeling that every question asked during the design of LSL was answered incorrectly 😏