Second Life Forums Archive - How slow are lists?

Ziggy Puff

Registered User

Join date: 15 Jul 2005

Posts: 1,143

08-02-2005 08:47

I have a situation where an object needs to communicate multiple values to another. I tried separate llSay calls, and that takes a while. The data is small, so now I'm thinking of llSaying one big string, and having the reader parse it out. I can either use llParseString2List and then use individual llList2XXX functions to get the values out, or I can write the parser by hand where I search for the separator characters. Which would be faster? I know lists are built to handle any data types, and all I need is strings (floats nd rotations, which I'll pull out as strings and then typecast, because the wiki says that llList2Vector and llList2Rot don't work.

Thanks,
Ziggy

Minsk Oud

Registered User

Join date: 12 Jul 2005

Posts: 85

08-02-2005 12:41

I would suggest you try a quick benchmark on the size of list you happen to be working with. In my tests on a full dump from llGetPrimitiveParams, using llParseString2List and accessing elements was orders of magnitude faster than parsing it into variables myself. Think it was something like 0.3s vs 15s for a ~1200 character string.

Chris

Ziggy Puff

Registered User

Join date: 15 Jul 2005

Posts: 1,143

08-02-2005 13:15

Thanks. That's good news. I wrote up my own parsing code, but that's hampered by the fact that I can't search for a substring starting at a certain location in the main string. Or at least, I couldn't find any way of doing it. So once I've found the first separator, I had to make a substring from that point and then search within that for the next separator. It would be neat if we could access strings by index like C allows you to do, though I'm sure the C++/Java people wouldn't like that

Or maybe even:

llSubStringIndex(string source, string pattern, integer searchStartIndex)

Anyway... thanks once again.

Frans Charming

You only need one Frans

Join date: 28 Jan 2005

Posts: 1,847

08-02-2005 13:30

wouldn't llCSV2List be a better option. It does all the parsing for you and puts it in a list. You only have to put a , between the values.
http://secondlife.com/badgeo/wakka.php?wakka=llCSV2List

_____________________

Minsk Oud

Registered User

Join date: 12 Jul 2005

Posts: 85

08-02-2005 13:52

Aside from the obvious problem that the CSV functions mangle vectors and rotations... The OP presumably noticed that, which is why llParseString2List (or llParseStringKeepNulls) was suggested.

IMO anyway, splitting on a pipe "|" is a much better choice. In some ugly experiments I wound up using |!|, |@|, |#|, |$| to nest lists. Not pretty, but it works (using symbol characters to avoid accidentally matching single-digit integers).

Frans Charming

You only need one Frans

Join date: 28 Jan 2005

Posts: 1,847

08-02-2005 13:58

Hmm, i believe i have written a script where i put a vector through csv. Thought it worked
I will give it a test later today, and report back.

_____________________

Ziggy Puff

Registered User

Join date: 15 Jul 2005

Posts: 1,143

08-02-2005 14:02

Actually, I hadn't thought of CSV. I haven't tried any of this at all, this is all un-run code still being written. I noticed that multiple talk/listens introduced significant delay, so I was thinking of ways to send everything in one message.

CSV would help if it executes faster than ParseString2List. I was planning on using | as the separator too. Some of my entries are 'names', i.e. they can contain spaces. <, >, ','... those are out since I'll have vectors in there, unless I write extra code to handle them, which makes no sense since using | as a separator will take care of the problem and be faster.

Thanks for all the advice, BTW. If you have working CSV code and it'll be faster than the ParseString2List function, I'm definitely interested.

Strife Onizuka

Moonchild

Join date: 3 Mar 2004

Posts: 5,887

08-02-2005 18:40

CODE


string dump(list a, string b) {
    string c = (string)a;
    if(llStringLength(b)==1)
        if(llSubStringIndex(c,b) == -1)
            jump end;
    integer d = 1 - llStringLength(b += "|\\/?!@#$%^&*()_=:;~{}[],\n\" qQxXzZ");
    while(1+llSubStringIndex(c,llGetSubString(b,d,d)) && d)
        ++d;
    b = llGetSubString(b,d,d);
    @end;
    c = "";//save memory
    return b + llDumpList2String(a, b);
}

list parse(string a) {
    string b = llGetSubString(a,0,0);//save memory
    return llParseStringKeepNulls(llDeleteSubString(a,0,0), ,[]);
}

_____________________

Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river.
- Cyril Connolly

Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence.
- James Nachtwey

Ziggy Puff

Registered User

Join date: 15 Jul 2005

Posts: 1,143

08-02-2005 20:22

OK, I've stared at this code for a couple of minutes, and I can't figure it out. What does it do? How does it work? Why does nulling a string that's a local variable right before the function returns save memory, since locals should be freed when the function returns anyway?

Strife Onizuka

Moonchild

Join date: 3 Mar 2004

Posts: 5,887

08-03-2005 04:59

The trouble is when dealing with very large quantities of data that you can run out of memory with the stack alone.

All functions are pass by value, meaning that everything needs to be copied before it can be passed to a function.

So in dump() we null c so we can have more memory available for when return, otherwise we would have 3 copies of the data in memory in different forms.

In parse() we have a similar problem which we eliminate by breaking the function across multiple lines.

Use these functions to safely pass lists through strings (course you loose the type)

_____________________

Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river.
- Cyril Connolly

Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence.
- James Nachtwey

Strife Onizuka

Moonchild

Join date: 3 Mar 2004

Posts: 5,887

08-03-2005 06:10

You might think that adding curly brackets to indicate a new scope would cause LSL to de-allocate variables allocated in that scope. This is not the case. All cleanup is done at function or event return.

_____________________

Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river.
- Cyril Connolly

Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence.
- James Nachtwey

Ziggy Puff

Registered User

Join date: 15 Jul 2005

Posts: 1,143

08-03-2005 08:19

OK, that makes sense I guess. And now I can see what the functions are doing, kinda. The dump searches through the list and figures out a good one-character separator and puts that at the beginning of the result string, the parse then uses that knowledge to break it back out. This is probably safer than using the dump and parse functions directly, but I'm not sure if it's faster

I built my solution with using '|' as a separator and treating everything as strings. That seems to work well for the types I have - integers, vectors, rotations and strings. Of course, the limitation is that the string cannot have the '|' character in it.

Strife Onizuka

Moonchild

Join date: 3 Mar 2004

Posts: 5,887

08-03-2005 08:33

And your function can't nest lists.

_____________________

Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river.
- Cyril Connolly

Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence.
- James Nachtwey

Tiger Crossing

The Prim Maker

Join date: 18 Aug 2003

Posts: 1,560

08-03-2005 09:06

I use:

llWhisper( 12345, llDumpList2String( gList, "|" ) );

And:

gList = llParseString2List( msg, ["|"], [] );

To pass data over non-vocal channels. There's a limit of 255 of course, which sucks. Removing that limit, or at least extending it, for non-zero channels would be a big start.

EDIT: EWW! Strife used a GOTO! Ick! Ick! Ick!

_____________________

~ Tiger Crossing
~ (Nonsanity)

Ziggy Puff

Registered User

Join date: 15 Jul 2005

Posts: 1,143

08-03-2005 09:48

From: Strife Onizuka

And your function can't nest lists.

That's a good point. If I ever end up in a situation where I need to do that, I'll remember this. Thanks for the advice.

How slow are lists?
Ziggy Puff Registered User Join date: 15 Jul 2005 Posts: 1,143	08-02-2005 08:47 I have a situation where an object needs to communicate multiple values to another. I tried separate llSay calls, and that takes a while. The data is small, so now I'm thinking of llSaying one big string, and having the reader parse it out. I can either use llParseString2List and then use individual llList2XXX functions to get the values out, or I can write the parser by hand where I search for the separator characters. Which would be faster? I know lists are built to handle any data types, and all I need is strings (floats nd rotations, which I'll pull out as strings and then typecast, because the wiki says that llList2Vector and llList2Rot don't work. Thanks, Ziggy
Minsk Oud Registered User Join date: 12 Jul 2005 Posts: 85	08-02-2005 12:41 I would suggest you try a quick benchmark on the size of list you happen to be working with. In my tests on a full dump from llGetPrimitiveParams, using llParseString2List and accessing elements was orders of magnitude faster than parsing it into variables myself. Think it was something like 0.3s vs 15s for a ~1200 character string. Chris
Ziggy Puff Registered User Join date: 15 Jul 2005 Posts: 1,143	08-02-2005 13:15 Thanks. That's good news. I wrote up my own parsing code, but that's hampered by the fact that I can't search for a substring starting at a certain location in the main string. Or at least, I couldn't find any way of doing it. So once I've found the first separator, I had to make a substring from that point and then search within that for the next separator. It would be neat if we could access strings by index like C allows you to do, though I'm sure the C++/Java people wouldn't like that Or maybe even: llSubStringIndex(string source, string pattern, integer searchStartIndex) Anyway... thanks once again.
Frans Charming You only need one Frans Join date: 28 Jan 2005 Posts: 1,847	08-02-2005 13:30 wouldn't llCSV2List be a better option. It does all the parsing for you and puts it in a list. You only have to put a , between the values. http://secondlife.com/badgeo/wakka.php?wakka=llCSV2List _____________________
Minsk Oud Registered User Join date: 12 Jul 2005 Posts: 85	08-02-2005 13:52 Aside from the obvious problem that the CSV functions mangle vectors and rotations... The OP presumably noticed that, which is why llParseString2List (or llParseStringKeepNulls) was suggested. IMO anyway, splitting on a pipe "\|" is a much better choice. In some ugly experiments I wound up using \|!\|, \|@\|, \|#\|, \|$\| to nest lists. Not pretty, but it works (using symbol characters to avoid accidentally matching single-digit integers).
Frans Charming You only need one Frans Join date: 28 Jan 2005 Posts: 1,847	08-02-2005 13:58 Hmm, i believe i have written a script where i put a vector through csv. Thought it worked I will give it a test later today, and report back. _____________________
Ziggy Puff Registered User Join date: 15 Jul 2005 Posts: 1,143	08-02-2005 14:02 Actually, I hadn't thought of CSV. I haven't tried any of this at all, this is all un-run code still being written. I noticed that multiple talk/listens introduced significant delay, so I was thinking of ways to send everything in one message. CSV would help if it executes faster than ParseString2List. I was planning on using \| as the separator too. Some of my entries are 'names', i.e. they can contain spaces. <, >, ','... those are out since I'll have vectors in there, unless I write extra code to handle them, which makes no sense since using \| as a separator will take care of the problem and be faster. Thanks for all the advice, BTW. If you have working CSV code and it'll be faster than the ParseString2List function, I'm definitely interested.
Strife Onizuka Moonchild Join date: 3 Mar 2004 Posts: 5,887	08-02-2005 18:40 CODE string dump(list a, string b) { string c = (string)a; if(llStringLength(b)==1) if(llSubStringIndex(c,b) == -1) jump end; integer d = 1 - llStringLength(b += "\|\\/?!@#$%^&*()_=:;~{}[],\n\" qQxXzZ"); while(1+llSubStringIndex(c,llGetSubString(b,d,d)) && d) ++d; b = llGetSubString(b,d,d); @end; c = "";//save memory return b + llDumpList2String(a, b); } list parse(string a) { string b = llGetSubString(a,0,0);//save memory return llParseStringKeepNulls(llDeleteSubString(a,0,0), ,[]); } _____________________ Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river. - Cyril Connolly Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence. - James Nachtwey
Ziggy Puff Registered User Join date: 15 Jul 2005 Posts: 1,143	08-02-2005 20:22 OK, I've stared at this code for a couple of minutes, and I can't figure it out. What does it do? How does it work? Why does nulling a string that's a local variable right before the function returns save memory, since locals should be freed when the function returns anyway?
Strife Onizuka Moonchild Join date: 3 Mar 2004 Posts: 5,887	08-03-2005 04:59 The trouble is when dealing with very large quantities of data that you can run out of memory with the stack alone. All functions are pass by value, meaning that everything needs to be copied before it can be passed to a function. So in dump() we null c so we can have more memory available for when return, otherwise we would have 3 copies of the data in memory in different forms. In parse() we have a similar problem which we eliminate by breaking the function across multiple lines. Use these functions to safely pass lists through strings (course you loose the type) _____________________ Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river. - Cyril Connolly Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence. - James Nachtwey
Strife Onizuka Moonchild Join date: 3 Mar 2004 Posts: 5,887	08-03-2005 06:10 You might think that adding curly brackets to indicate a new scope would cause LSL to de-allocate variables allocated in that scope. This is not the case. All cleanup is done at function or event return. _____________________ Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river. - Cyril Connolly Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence. - James Nachtwey
Ziggy Puff Registered User Join date: 15 Jul 2005 Posts: 1,143	08-03-2005 08:19 OK, that makes sense I guess. And now I can see what the functions are doing, kinda. The dump searches through the list and figures out a good one-character separator and puts that at the beginning of the result string, the parse then uses that knowledge to break it back out. This is probably safer than using the dump and parse functions directly, but I'm not sure if it's faster I built my solution with using '\|' as a separator and treating everything as strings. That seems to work well for the types I have - integers, vectors, rotations and strings. Of course, the limitation is that the string cannot have the '\|' character in it.
Strife Onizuka Moonchild Join date: 3 Mar 2004 Posts: 5,887	08-03-2005 08:33 And your function can't nest lists. _____________________ Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river. - Cyril Connolly Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence. - James Nachtwey
Tiger Crossing The Prim Maker Join date: 18 Aug 2003 Posts: 1,560	08-03-2005 09:06 I use: llWhisper( 12345, llDumpList2String( gList, "\|" ) ); And: gList = llParseString2List( msg, ["\|"], [] ); To pass data over non-vocal channels. There's a limit of 255 of course, which sucks. Removing that limit, or at least extending it, for non-zero channels would be a big start. EDIT: EWW! Strife used a GOTO! Ick! Ick! Ick! _____________________ ~ Tiger Crossing ~ (Nonsanity)
Ziggy Puff Registered User Join date: 15 Jul 2005 Posts: 1,143	08-03-2005 09:48 From: Strife Onizuka And your function can't nest lists. That's a good point. If I ever end up in a situation where I need to do that, I'll remember this. Thanks for the advice.

Welcome to the Second Life Forums Archive

How slow are lists?