"List Dumping" vs "String Building"

[primerib1]

I have the following snippet of code:

 

list behaviors = llParseString2List(s1, (list)",", EMPL);
list results;
i = -(behaviors != EMPL);
do {
    s1 = llList2String(behaviors, i);
    if ((integer)GetParam(s_me, s1, "|", "=")) {
        results += s1 + "=✓";
    }
    else {
        if ((integer)GetParam(s_all, s1, "|", "=")) {
            results += s1 + "=!";
        }
        else {
            results += s1 + "=✗";
        }
    }
} while (++i);
SayToMaster("OK:rlvcheck|p=" + llDumpList2String(results, ","));

 

Is it better to just build the string directly rather than building a list then dumping it? So, like this:

 

list behaviors = llParseString2List(s1, (list)",", EMPL);
string results;
i = -(behaviors != EMPL);
do {
    s1 = llList2String(behaviors, i);
    if ((integer)GetParam(s_me, s1, "|", "=")) {
        results += s1 + "=✓,";
    }
    else {
        if ((integer)GetParam(s_all, s1, "|", "=")) {
            results += s1 + "=!,";
        }
        else {
            results += s1 + "=✗,";
        }
    }
} while (++i);
SayToMaster("OK:rlvcheck|p=" + llDeleteSubString(results, -1, -1));

 

What do you think?

[Love Zhaoying]

I suspect you'll find that strings are faster than lists and use less memory.

But in this example, since you're just building and dumping, not searching and manipulating a list, the difference could be trivial. 

I suppose my "rule of thumb" is, "did I need to use a list, when I could have used a string or JSON?"

[Frionil Fang]

Out of curiosity I made a similar test script (just mashes randomly generated characters together like the params in your example) with minimum other code and did a few thousand timing/memory test loops.

With 50 entries, the list based version has roughly 1000 bytes higher maximum memory usage (I didn't store the temporary strings/lists that get dumped in output, just said them on a dummy channel directly, like in your example) and is roughly 20% slower. 

With 250 entries, the whole process took about 5.7x longer for strings, and 5.3x for lists, with the memory difference being about 4000 bytes and lists being 13% slower - the memory use is expected, but strings seem to lose efficiency more quickly with size.

If I turn off the data dumping, the differences stay similar.

As a final note of curiosity, storing integers in a list directly instead of llChar of the integer results in performance between the string/list solution, and with dumping off it's faster than either (20%ish vs. building a string, 30%ish vs. building a list of strings, I did not put much effort into this check).

Conclusion: building a string directly instead of a list of strings seems the most effective solution for both memory and performance. For other uses and for non-string data, lists might be faster, though; in the only test I have written down -- a system that stores 1024 bytes of binary data packed into a list of 256 integers vs. a string solution with llChar/llOrd -- the reads with integer lists were about 100x faster, writes 30x.

[primerib1]

Wow, fantastic findings! Thanks!

[Love Zhaoying]

1 hour ago, Frionil Fang said:

With 250 entries, the whole process took about 5.7x longer for strings, and 5.3x for lists, with the memory difference being about 4000 bytes and lists being 13% slower - the memory use is expected, but strings seem to lose efficiency more quickly with size.

Awesome analysis! I am confused however, by the above snippet. 

With 250 entries vs. 50 entries, it took longer for strings (5.7x), than for lists (5.3x)?

But for 50 entries, it took longer for lists, than for strings?

Thank you!

[Frionil Fang]

17 minutes ago, Love Zhaoying said:

With 250 entries vs. 50 entries, it took longer for strings (5.7x), than for lists (5.3x)?

But for 50 entries, it took longer for lists, than for strings?

Sorry, I'm not the best at expressing things and probably didn't make it clear enough.

Increasing entries by 5x made list building 5.3x slower, but string building 5.7x slower. Combined with the speed difference being initially in favor of string building, strings are still faster, but lists might catch up at some point as the entries go up -- but seems running out of memory before reaching that point is more likely. 

Edited February 24, 2023 by Frionil Fang

[Lucia Nightfire]

7 hours ago, Love Zhaoying said:

I suspect you'll find that strings are faster than lists and use less memory.

AFAIK, in either LSO or Mono, lists support memory address space fragmentation. Strings do not. Strings use sequential available memory block allocation.

Edited February 24, 2023 by Lucia Nightfire

[Love Zhaoying]

19 minutes ago, Lucia Nightfire said:

AFAIK, in either LSO or Mono, lists support memory address space fragmentation. Strings do not. Strings use sequential available memory block allocation.

Does that mean that lists may be able to take advantage of "split" memory / be more GC relevant?

That could explain some stack-heap collisions used by large strings..

I can see implementing strings without using non-contiguous memory blocks, since a string is usually "contiguous data". They COULD have implemented it with non-contiguous blocks, of couse but if they didn't..

Anyway, thanks for the information!

 

 

[primerib1]

15 hours ago, Lucia Nightfire said:

AFAIK, in either LSO or Mono, lists support memory address space fragmentation. Strings do not. Strings use sequential available memory block allocation.

Yes in LSO, not in Mono.

Many notes in the wiki repeatedly say that "defragmenting" tricks used in LSO has no effect in Mono.

Basically the Mono runtime is smarter about memory allocation.

[primerib1]

On 2/25/2023 at 12:21 AM, Love Zhaoying said:

That could explain some stack-heap collisions used by large strings..

The main issue is that string is immutable.

So if you have the following:

    string s;
    integer i;
    for (i=0; i<100; ++i) {
        s = s + (string)i;
    }

Within the loop, the memory usage goes like this (ignoring everything else):

1. (At start) An integer, and an empty string ""
2. (First iteration) An integer, "", and "0"
3. (Second iteration) An integer, "", "0", and "01"
4. (Third iteration) An integer, "", "0", "01" and "012"
5. (Fourth iteration) An integer, "", "0", "01", "012" and "0123"
6. ... and so on ...

Yes, the previous 'versions' of the string are not gone... yet. Not until GC kicks in.

Now if you consider that the size of a string is (12 bytes + 2 x number of characters in the string) [1], you can see that before GC kicks in, doing a simple loop like that will consume memory really quickly. A 100-iteration loop like that will easily consume 1200 bytes just for the string type overhead, plus (2 x total number of characters in all those strings).

 

Alternate Moral of the Story: It's always a good idea to pepper your code with llSleep(0.01); here and there to regularly try to trigger GC.

 

[1] https://wiki.secondlife.com/wiki/LSL_Script_Memory#Variable_Memory_Usage but with a correction because string is encoded as UCS-2 / UTF-16, so 2 bytes per character

Edited February 25, 2023 by primerib1

[Love Zhaoying]

2 hours ago, primerib1 said:

goes like this (ignoring everything else):

My favorite part!!!

Thanks for the details.

Too bad there's no mutable string. One nice saving grace is local variables.

[Lucia Nightfire]

12 hours ago, primerib1 said:

Yes in LSO, not in Mono.

Many notes in the wiki repeatedly say that "defragmenting" tricks used in LSO has no effect in Mono.

Basically the Mono runtime is smarter about memory allocation.

I still use it in Mono for maximum memory allocation detection purposes sometimes versus relying on what the memory profiler can come up with.

I do not suggest anyone else do that, though. heh

Mono is mostly smarter in regards to memory handling of duplicate list entries.

Edited February 25, 2023 by Lucia Nightfire