Find in a list ... or Find in LSD?

[primerib1]

Okay something tickled my mind...

I have this function:

integer Allowed(key avatar_id, key hud_id) {
    list avid = (list)avatar_id;
    list grid = llGetObjectDetails(hud_id, (list)OBJECT_GROUP);
    // $Blockeds is a global list containing UUIDs to block, initialized by reading a notecard
    if (~llListFindList($Blockeds, avid)) return FALSE;
    if (~llListFindList($Blockeds, grid)) return FALSE;
    // $Alloweds is a global list containing UUIDs to block, initialized by reading a notecard
    if (~llListFindList($Alloweds, avid)) return TRUE;
    if (~llListFindList($Alloweds, grid)) return TRUE;
    return FALSE;
}

I wonder if its performance will be better if I turn it into this instead:

integer Allowed(key avatar_id, key hud_id) {
    string avid = (string)avatar_id;
    string grid = llList2String(llGetObjectDetails(hud_id, (list)OBJECT_GROUP), 0);
    // The LSD is initialized to contain "_block-<UUID>" and "_allow-<UUID>" keys by reading a notecard
    if (llLinksetDataFindKeys("_block-(" + avid + "|" + grid + ")", 0, 0) != EMPL) return FALSE;
    if (llLinksetDataFindKeys("_allow-(" + avid + "|" + grid + ")", 0, 0) != EMPL) return TRUE;
    return FALSE;
}

One benefit of course is I can save quite a bit of script memory by not keeping a list of UUIDs (102 bytes per UUID!)
==> consume LSD store instead (44 bytes per UUID saved = 7 bytes prefix + 36 bytes UUID + 1 byte dummy value)

Edited January 19, 2023 by primerib1

[Qie Niangao]

For performance, I think you need to test it. My hunch is LSD regular expression matching will win but that's a pretty baseless hunch. It's two function calls instead of four, but each call involves constructing the pattern string, although that may be comparable to forming the one-element ID lists for llListFindList to test.

Personally, unless performance is a really big consideration, I'd probably favor the LSD approach anyway if I was pretty sure nothing else would be needing lots of LSD storage. That way script enhancements aren't constrained by all that UUID memory. (I'd probably shrink the 7 byte prefixes to single unicode characters, but I'm cheap that way.)

[Lucia Nightfire]

LSDRead is 10x slower than List2*

LSDListKeys is 6.5x slower than ListFindList

LSDFindKeys is 13x slower than ListFindList

This also means LSD generally uses more script timing.

With this in mind, unless you're saving a significant amount of script memory and/or script timing, you probably shouldn't convert EVERYTHING from list handling to LSD, else I predict in the years to come, that LSD could become a new concerning source of region script lag.

My 2 pennies...

Edited January 19, 2023 by Lucia Nightfire

[Quistess Alpha]

I'm a little bit confused by your implementation format for LSD. In non-LSD you have uncorrelated lists, in LSD you have group IDs and AV ids grouped in pairs in the LSD?

why not just treat AV IDs and Group IDs identically? There's very little chance of a collision

Also, I would store the block or allowed in the value of the LSD:

// LSD keys of the form "Acc:"+UUID.
key avId;
key grId;
string val;
if(val=llLinksetDataRead("Acc:"+avId))
{   if("allowed"!=val)
    {  return FALSE;
    }
}
if(val=llLinksetDataRead("Acc:"+grId))
{   if("allowed"==val);
    {  return TRUE;
    }else
    {  return FALSE; 
    }
}
return FALSE;
// or so; there are 9 cases to check, and I'm too lazy to set up a truth table for the implementation in the OP.

 

Edited January 19, 2023 by Quistess Alpha

[Coffee Pancake]

12 minutes ago, Lucia Nightfire said:

I predict in the years to come, that LSD will become a new concerning source of region script lag.

Years ? oh it's not going to take us years !!

[primerib1]

24 minutes ago, Quistess Alpha said:

in LSD you have group IDs and AV ids grouped in pairs in the LSD?

It's not grouped in pairs. It's using the regex operator "|" So the search will be, for instance:

_block:(94ea---5e42|6cd9--4eff)

Which means it will be searching for keys that match either _block:94ea---5e42 or _block:6cd9--4eff

If I put the "allowed" part on the value side, I cannot leverage the regex "|" operator. I also will have to do 2 fetches, one for the avid, and one for the grid

30 minutes ago, Lucia Nightfire said:

LSDRead is 10x slower than List2*

LSDListKeys is 6.5x slower than ListFindList

LSDFindKeys is 13x slower than ListFindList

Ahh interesting timing.

So the main benefit for LSD is not really the speed (although LSD is quite fast), but more towards space efficiency (40-ish bytes per UUID instead of 102 bytes per UUID).

Ohh and also persistence against script reset, so if my script ever gets b0rked I can just reset & rerun it and things will pick up.

30 minutes ago, Lucia Nightfire said:

This also means LSD generally uses more script timing... LSD will become a new concerning source of region script lag.

Not necessarily though, depending on how it is architected. It is quite possible that when the runtime encounters LSD functions, the runtime switches context to execute other script (async await); that's why the timing is very high. But on the other hand since it was an async await, the timeslice used to await LSD func completion gets used to run other scripts, ultimately reducing lag.

However, if LSD functions are implemented as synchronous funcs, then yeah, that will consume more script timing.

50 minutes ago, Qie Niangao said:

Personally, unless performance is a really big consideration, I'd probably favor the LSD approach anyway if I was pretty sure nothing else would be needing lots of LSD storage. That way script enhancements aren't constrained by all that UUID memory. (I'd probably shrink the 7 byte prefixes to single unicode characters, but I'm cheap that way.)

In the big picture, I prefer my script running slightly slower than encountering "Stack-Heap Collision" error 😎

Edited January 19, 2023 by primerib1

[Love Zhaoying]

1 hour ago, Lucia Nightfire said:

With this in mind, unless you're saving a significant amount of script memory and/or script timing, you probably shouldn't convert EVERYTHING from list handling to LSD

And don't be like me, and convert EVERYTHING from list handling to JSON handling, then from JSON handling to LSD..

 

[Qie Niangao]

2 hours ago, primerib1 said:

If I put the "allowed" part on the value side, I cannot leverage the regex "|" operator. I also will have to do 2 fetches, one for the avid, and one for the grid

But now you're doing two fetches, one for "allowed" and one for "blocked" conditions, right?

I must be making some silly error, but in a quick test I'm seeing ridiculously fast results for llLinksetDataRead(), and if that's correct it should be much cheaper to check whether the fetched value signifies "allowed" or "blocked as @Quistess Alpha suggested.

Eventually I'll refine this quick and dirty test, hunting for where I've oversimplified stuff, but a question came up while trying to make a representative test: For most applications, I'd expect the vast majority of queries to match neither allowed nor blocked records. But that may not be this application. And trying to guess the probabilities got me wondering: the logic of the Allowed() user function as shown returns FALSE for anything not identified as "allowed" whether it's "blocked" or not, so testing for "blocked" seems pointless… unless maybe there are so relatively few "blocked" that it's expected to be a much faster test than searching the much more numerous "allowed" entries. (Recording "blocked", though, might be useful for preventing blocked keys ever being set "allowed" without some special operation lifting the "blocked" condition… or something… maybe?) Probably I've confused myself here.

[primerib1]

It is possible for someone to be in an allowed group, but they are a*holes so they're blocked by UUID.

The reverse is kinda more petty... so if a resident is allowed by UUID but if they have a certain Group tag active, no joy for you! 😂

In any case, search for "blocked" must always trump search for "allowed".

As to fetches... Hmm, you have a point there... Though I don't actually fetch the related value, so I just do a search in the key space. Depending on how it is implemented, it might be faster or not faster.

[Qie Niangao]

Okay, well this is an ugly lot of code [EDIT: In a Quote block—thanks @Quistess Alpha ! ] :

Quote

list $Blockeds;
list $Alloweds;
list EMPL = [];
string BLOCKED_FLAG = "-";
string ALLOWED_FLAG = "+";

// ignore llGetObjectDetails(hud_id, [OBJECT_GROUP]) overhead for all options so hand-in the grp_id
integer memAllowed(key avatar_id, key grp_id)
{
    list avid = (list)avatar_id;
    list grid = (list)grp_id;
    // $Blockeds is a global list containing UUIDs to block, initialized by reading a notecard
    if (~llListFindList($Blockeds, avid)) return FALSE;
    if (~llListFindList($Blockeds, grid)) return FALSE;
    // $Alloweds is a global list containing UUIDs to block, initialized by reading a notecard
    if (~llListFindList($Alloweds, avid)) return TRUE;
    if (~llListFindList($Alloweds, grid)) return TRUE;
    return FALSE;
}
integer regexAllowed(key avatar_id, key grp_id) 
{
    string avid = (string)avatar_id;
    string grid = (string)grp_id;
    // The LSD is initialized to contain "_block-<UUID>" and "_allow-<UUID>" keys by reading a notecard
    if (llLinksetDataFindKeys("_block-(" + avid + "|" + grid + ")", 0, 0) != EMPL) return FALSE;
    if (llLinksetDataFindKeys("_allow-(" + avid + "|" + grid + ")", 0, 0) != EMPL) return TRUE;
    return FALSE;
}
integer valAllowed(key avatar_id, key grp_id)
{
    string avid = (string)avatar_id;
    string grid = (string)grp_id;
    // The LSD is initialized to contain "+" and "-" values for avatar and group keys by reading a notecard
    string avVal = llLinksetDataRead(avatar_id);
    if (BLOCKED_FLAG == avVal) return FALSE;
    string grpVal = llLinksetDataRead(grp_id);
    if (BLOCKED_FLAG == grpVal) return FALSE;
    if (ALLOWED_FLAG == avVal) return TRUE;
    if (ALLOWED_FLAG == grpVal) return TRUE;
    return FALSE;
}

default
{
    state_entry()
    {
        llLinksetDataReset();
        // pre-populate (as if by notecard)
        integer i=200;  // blocked groups or avatars
        while (0 <= --i)
        {
            key saveKey = llGenerateKey();
            Blockeds += saveKey;    // for mem list matching
            llLinksetDataWrite("_block-"+(string)saveKey, "."); // for regex matching
            llLinksetDataWrite((string)saveKey, BLOCKED_FLAG);   // for val matching
        }
        i=200;  // allowed groups or avatars
        while (0 <= --i)
        {
            key saveKey = llGenerateKey();
            Alloweds += saveKey;    // for mem list matching
            llLinksetDataWrite("_allow-"+(string)saveKey, "."); // for regex matching
            llLinksetDataWrite((string)saveKey, ALLOWED_FLAG);   // for val matching
        }
        
        // first test misses (probably vast majority) that are neither blocked nor allowed
        i = 1000;
        key testKey;
        integer tested;

        llResetTime();
        while (0 <= --i)
            if (!memAllowed(NULL_KEY, NULL_KEY))
                ++tested;
        llOwnerSay((string)tested+" misses by mem list: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (!regexAllowed(NULL_KEY, NULL_KEY))
                ++tested;
        llOwnerSay((string)tested+" misses by regex: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (!valAllowed(NULL_KEY, NULL_KEY))
                ++tested;
        llOwnerSay((string)tested+" misses by val: "+(string)llGetTime());

        // next test allowed by avatar
        testKey = llList2Key(Alloweds, 100);
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (memAllowed(testKey, NULL_KEY))
                ++tested;
        llOwnerSay((string)tested+" allowed avatar by mem list: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (regexAllowed(testKey, NULL_KEY))
                ++tested;
        llOwnerSay((string)tested+" allowed avatar by regex: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (valAllowed(testKey, NULL_KEY))
                ++tested;
        llOwnerSay((string)tested+" allowed avatar by val: "+(string)llGetTime());

        // next test allowed by group
        testKey = llList2Key(Alloweds, 100);
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (memAllowed(NULL_KEY, testKey))
                ++tested;
        llOwnerSay((string)tested+" allowed group by mem list: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (regexAllowed(NULL_KEY, testKey))
                ++tested;
        llOwnerSay((string)tested+" allowed group by regex: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (valAllowed(NULL_KEY, testKey))
                ++tested;
        llOwnerSay((string)tested+" allowed group by val: "+(string)llGetTime());

        // next test blocked by group
        testKey = llList2Key(Blockeds, 100);
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (!memAllowed(NULL_KEY, testKey))
                ++tested;
        llOwnerSay((string)tested+" blocked group by mem list: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (!regexAllowed(NULL_KEY, testKey))
                ++tested;
        llOwnerSay((string)tested+" blocked group by regex: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (!valAllowed(NULL_KEY, testKey))
                ++tested;
        llOwnerSay((string)tested+" blocked group by val: "+(string)llGetTime());

        // next test blocked by avatar
        testKey = llList2Key(Blockeds, 100);
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (!memAllowed(testKey, NULL_KEY))
                ++tested;
        llOwnerSay((string)tested+" blocked avatar by mem list: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (!regexAllowed(testKey, NULL_KEY))
                ++tested;
        llOwnerSay((string)tested+" blocked avatar by regex: "+(string)llGetTime());
        i = 1000;
        tested = 0;
        llResetTime();
        while (0 <= --i)
            if (!valAllowed(testKey, NULL_KEY))
                ++tested;
        llOwnerSay((string)tested+" blocked avatar by val: "+(string)llGetTime());
        
        llOwnerSay("Test run complete");
    }
}

 

and the results from one run (which should be replicated, but maybe somebody will show it's all bogus anyway) :

Quote

1000 misses by mem list: 12.043700
1000 misses by regex: 44.481410
1000 misses by val: 0.265606
1000 allowed avatar by mem list: 7.467209
1000 allowed avatar by regex: 44.478680
1000 allowed avatar by val: 0.290892
1000 allowed group by mem list: 9.665533
1000 allowed group by regex: 44.443740
1000 allowed group by val: 0.222866
1000 blocked group by mem list: 4.778316
1000 blocked group by regex: 35.490920
1000 blocked group by val: 0.265456
1000 blocked avatar by mem list: 1.600033
1000 blocked avatar by regex: 35.150940
1000 blocked avatar by val: 0.134543
Test run complete

I mean… if this is at all correct, LSD regex matching is to by far the slowest, and simple filtering by fetched LSD value is by far the fastest (at least an order of magnitude faster than memory list matching). But maybe I'm still doing something stupid here.

Edited January 20, 2023 by Qie Niangao

[primerib1]

54 minutes ago, Qie Niangao said:

and the results from one run (which should be replicated, but maybe somebody will show it's all bogus anyway) :

Quote

1000 misses by mem list: 12.043700
1000 misses by regex: 44.481410
1000 misses by val: 0.265606
1000 allowed avatar by mem list: 7.467209
1000 allowed avatar by regex: 44.478680
1000 allowed avatar by val: 0.290892
1000 allowed group by mem list: 9.665533
1000 allowed group by regex: 44.443740
1000 allowed group by val: 0.222866
1000 blocked group by mem list: 4.778316
1000 blocked group by regex: 35.490920
1000 blocked group by val: 0.265456
1000 blocked avatar by mem list: 1.600033
1000 blocked avatar by regex: 35.150940
1000 blocked avatar by val: 0.134543
Test run complete

I mean… if this is at all correct, LSD regex matching is to by far the slowest, and simple filtering by fetched LSD value is by far the fastest (at least an order of magnitude faster than memory list matching). But maybe I'm still doing something stupid here.

Wow, very interesting!

No I don't see anything that screams any mistake, but this result is quite amazing, indeed!

[Quistess Alpha]

5 hours ago, Qie Niangao said:

I'd hide under spoiler tags if I remembered how to do that on these Forums

I usually put large blocks of code into quote blocks if I remember to (you don't have to quote someone specific to make a quote thing).

Quote

//some very large block of code
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

like so.

 

[primerib1]

23 hours ago, Qie Niangao said:

integer valAllowed(key avatar_id, key grp_id)
{
    string avid = (string)avatar_id;
    string grid = (string)grp_id;
    // The LSD is initialized to contain "+" and "-" values for avatar and group keys by reading a notecard
    string avVal = llLinksetDataRead(avatar_id);
    if (BLOCKED_FLAG == avVal) return FALSE;
    string grpVal = llLinksetDataRead(grp_id);
    if (BLOCKED_FLAG == grpVal) return FALSE;
    if (ALLOWED_FLAG == avVal) return TRUE;
    if (ALLOWED_FLAG == grpVal) return TRUE;
    return FALSE;
}

So I ended optimizing & genericizing my Allowed() function like so:

integer Allowed(key avid, key objid) {
    if (NULL_KEY == objid) objid = llList2Key(llGetAttachedList(avid), 0);
    key grid = llList2Key(llGetObjectDetails(objid, (list)OBJECT_GROUP), 0);
    string gr_verdict = llLinksetDataRead("_uuid:" + (string)grid);
    if ("blocked" == gr_verdict) return FALSE;
    string av_verdict = llLinksetDataRead("_uuid:" + (string)avid);
    if ("blocked" == av_verdict) return FALSE;
    return (("allowed" == gr_verdict) || ("allowed" == av_verdict));
}

Edited January 21, 2023 by primerib1

[Love Zhaoying]

25 minutes ago, primerib1 said:

So I ended optimizing & genericizing my Allowed() function like so:

integer Allowed(key avid, key objid) {
    if (NULL_KEY == objid) objid = llList2Key(llGetAttachedList(avid), 0);
    key grid = llList2Key(llGetObjectDetails(objid, (list)OBJECT_GROUP), 0);
    string gr_verdict = llLinksetDataRead("_uuid:" + (string)grid);
    if ("blocked" == gr_verdict) return FALSE;
    string av_verdict = llLinksetDataRead("_uuid:" + (string)avid);
    if ("blocked" == av_verdict) return FALSE;
    return (("allowed" == gr_verdict) || ("allowed" == av_verdict));
}

Yeah, my LSD that uses a UUID for part of the key, I make it the whole key (prefixed with a numeric "slot" for data grouping "by purpose").