Trying to find a low lag way to generate multiple semirandom values

[Madelaine McMasters]

37 minutes ago, Nova Convair said:

That is alot faster, needs about 60% of the llFrand-test-script time.

Probably some room for optimizations but I doubt that it's possible to squeeze out much more performance since llFrand is already not too bad.

Yep, it's looking like llFrand() is not the issue. Here's my random number generator in your test loop...

integer lfsr;
integer bit;

integer rand()
{
  bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
  return lfsr =  (lfsr >> 1) | (bit << 15);
}

default
{
    touch_start(integer total_number)
    {
        float avg;
        float test;
        integer count = 100000;
        
        llSay(0,"START");
        float t=llGetTime();

        integer i=count;
        while (i-->0) {
            test+= llFrand(1);
        }
        
        llSay(0,"llFrand "+(string)((llGetTime()-t)/count*1000000)+"µs "+(string)(test/count));
 
        t=llGetTime();
        i=count;
        lfsr=(integer)llFrand(65536);
        while (i-->0) {
            test+= rand();
        }
        
        llSay(0,"rand "+(string)((llGetTime()-t)/count*1000000)+"µs "+(string)(test/count/65535));

   }
}

This results in...

[05:55] Object: llFrand 29.160310µs 0.498387
[05:55] Object: rand 12.688040µs 0.500439

[ChinRey]

36 minutes ago, Madelaine McMasters said:

Yep, it's looking like llFrand() is not the issue.

Yes, that seems pretty conclusive by now. However, the question wasn't only about alternative ways to generate (semi)random values but also whether a predefined list with a limited dataset would be better.

I modified Nova's test script to cycle through a list of 11 values, first generated by her semirandom float generator, then with fixed values. The result I got was about the same as with llFrand();

• 20,000 list lookups: 4.30 seconds
• 20,000 floats generaated Nova's way: 2.69 second
• 20,000 floats egnerated with llFrand(): 4.26 second

(All results here are typical values. I did each test several times of course but the deviations were so minute I never bothered to calculate average or mean values).

So, it seems a list lookup takes about the same time as an llFrand() - that can be good to know.

But a vector needs three floats but can still be stored as a single list item. So I tried with vectors rather than floats:

• 20,000 lookups in a list of 11 vectors created by a crude hack of Nova's generator took 4.40 seconds
• 20,000 vectors generated on the fly with a crude hack of Nova's generator took 7.35 seconds
• 20,000 vectors generated on the fly with llFrand() took 11.42 seconds

Not really surprising perhaps. Looking up vectors doesn't take much more time than looking up floats. But generating them takes three times as long.

Here are the scripts I used for the vector test (with apologies to Nova for butchering her code)

integer seed = 837465481;

default
{
    touch_start(integer total_number)
    {
        vector avg;
        vector test;
        
        llSay(0,"START");
        float t=llGetTime();
        list values=[];
        integer i=11;
        while (i-->0) {
            
            seed = (seed * 16807 % 2147483647) & 0x7FFFFFFF;
            test = <((float)(seed-1) / 2147483646),0,0>;
            seed = (seed * 16807 % 2147483647) & 0x7FFFFFFF;
            test = test+<0,((float)(seed-1) / 2147483646),0>;
            seed = (seed * 16807 % 2147483647) & 0x7FFFFFFF;
            test = test+<0,0,((float)(seed-1) / 2147483646)>;


            values=values+[test];
            
        }
        
        i=200000;
        while (i-->0) {
            
            test = llList2Vector(values,i%11);

            avg += test;
            
            if (i%20000==0) llSay(0,(string)test);
            
        }
        
        llSay(0,"STOP "+(string)(llGetTime()-t)+" / "+(string)(avg/200000));
    }
}

integer seed = 837465481;

default
{
    touch_start(integer total_number)
    {
        vector avg;
        vector test;
        
        llSay(0,"START");
        float t=llGetTime();

        integer i=200000;
        while (i-->0) {
            
            seed = (seed * 16807 % 2147483647) & 0x7FFFFFFF;
            test = <((float)(seed-1) / 2147483646),0,0>;
            seed = (seed * 16807 % 2147483647) & 0x7FFFFFFF;
            test = test+<0,((float)(seed-1) / 2147483646),0>;
            seed = (seed * 16807 % 2147483647) & 0x7FFFFFFF;
            test = test+<0,0,((float)(seed-1) / 2147483646)>;

            avg += test;
            
            if (i%20000==0) llSay(0,(string)test);
            
        }
        
        llSay(0,"STOP "+(string)(llGetTime()-t)+" / "+(string)(avg/200000));
    }
}

default
{
    touch_start(integer total_number)
    {
        vector avg;
        vector test;
        
        llSay(0,"START");
        float t=llGetTime();

        integer i=200000;
        while (i-->0) {
            
            test = <llFrand(1),llFrand(1),llFrand(1)>;

            avg += test;
            
            if (i%20000==0) llSay(0,(string)test);
            
        }
        
        llSay(0,"STOP "+(string)(llGetTime()-t)+" / "+(string)(avg/200000));
    }
}

 

Edited November 24, 2017 by ChinRey

[Madelaine McMasters]

1 hour ago, ChinRey said:

Not really surprising perhaps. Looking up vectors doesn't take much more time than looking up floats. But generating them takes three times as long.

Rather than call my rand() function for each random number, I placed the code inline, as you did with Nova's method. Execution time is virtually unchanged, even though 3x more numbers are being generated.

integer lfsr;
integer bit;

integer rand()
{
  bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
  return lfsr =  (lfsr >> 1) | (bit << 15);
}

default
{
    touch_start(integer total_number)
    {
        float avg;
        float test = 0;
        integer count = 100000;
        
        llSay(0,"START");
        float t=llGetTime();

        integer i=count;
        while (i-->0) {
            test+= llFrand(1);
        }
        
        llSay(0,"llFrand "+(string)((llGetTime()-t)/count*1000000)+"µs "+(string)(test/count));
 
        t=llGetTime();
        i=count;
        lfsr=(integer)llFrand(65536);
        test = 0;
        
        while (i-->0) {
            bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
            lfsr =  (lfsr >> 1) | (bit << 15);
            test+= lfsr;
            
            bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
            lfsr =  (lfsr >> 1) | (bit << 15);
            test+= lfsr;
            
            bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
            lfsr =  (lfsr >> 1) | (bit << 15);
            test+= lfsr;
        }
        
        llSay(0,"rand "+(string)((llGetTime()-t)/count*1000000)+"µs "+(string)(test/count/65535/3));

   }
}

This doesn't surprise me. Function calls aren't free.

Edited November 24, 2017 by Madelaine McMasters

[ChinRey]

2 hours ago, Madelaine McMasters said:

This doesn't surprise me. Function calls aren't free.

They should be! Maybe somebody could file a JIRA about that.

But I thought setting a value for a variable took time too?

Can somebody please check this script for me and tell me what I've done wrong? It's supposed to be a modified version of Madelaine's code inside Nova's test harness. But as far as I can see, it spends a little bit more than half a second to generate 20,000 randomish vectors and that's not possible!

integer lfsr;
integer lfss;
integer lfst;
integer bit;

integer rand()
{
  bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
  return lfsr =  (lfsr >> 1) | (bit << 15);
}

default
{
    touch_start(integer total_number)
    {
        vector avg;
        float test;
        vector output;
        lfsr=lfss=lfst=(integer)llFrand(65536);
        
        llSay(0,"START");
        float t=llGetTime();

        integer i=20000;
        while (i-->0) {
            bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
            lfsr =  (lfsr >> 1) | (bit << 15);
            test+= lfsr;
            
            bit  = ((lfss >> 0) ^ (lfss >> 2) ^ (lfss >> 3) ^ (lfss >> 5) ) & 1;
            lfss = (lfss >> 2) | (bit << 16);
            test+= lfss;
            
            bit  = ((lfst >> 0) ^ (lfst >> 2) ^ (lfst >> 3) ^ (lfst >> 5) ) & 1;
            lfst =(lfst >> 3) | (bit << 17);
            test+= lfst;
            output=<(lfsr%100)*.01-.5,(lfss%100)*.01-.5,(lfst%100)*.01-.5>;
            
            if (i%2000==0) llSay(0,(string)output);
        }

        llSay(0,"STOP "+(string)(llGetTime()-t)+" / "+(string)(avg/200000));
    }
}

Edit: I tried with a shorter series of only 200 vectors and all of them posted in local chat. That gave me this message:

Quote

Your chat is blocked in this region.  You and your scripts or objects will not be able to send chat until fewer messages are sent.

That's something I've only heard rumours about before.

But it does actually work and if I eliminate the readout every x values, it's 30 times as fast as the traditional <llFrand(),llFrand(),llFrand()> method!

Edited November 24, 2017 by ChinRey
Typo

[Madelaine McMasters]

Why isn't it possible to generate 20K random numbers per half second? Are you thinking that's too fast, or too slow?

The way you've modified my random number generator will cause all three axes of your vector to contain the same value. lfsr, lfss and lfst, all starting from the same seed, will all generate the same sequence. Do it like this...

vector v;

bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
lfsr =  (lfsr >> 1) | (bit << 15);
v.x = lfsr;
            
bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
lfsr =  (lfsr >> 1) | (bit << 15);
v.y = lfsr;
            
bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
lfsr =  (lfsr >> 1) | (bit << 15);
v.z = lfsr;

Each iteration of the calculation on lfsr will produce a new pseudo random integer.

You will also need to scale and potentially offset the lfsr value (which ranges from 0-65535) to achieve the range you want, and that will probably take about as long as generating the random numbers. You'd probably have to do this no matter which method you use to generate a random number.

ETA: Function calls can be quite expensive, as they require saving the current context of the code stream, switching it to the function, then recovering it upon return. Good compilers will automatically inline functions that are so short they're smaller than the call/return overhead.

Edited November 24, 2017 by Madelaine McMasters

[Rolig Loon]

1 hour ago, ChinRey said:

Quote

Your chat is blocked in this region.  You and your scripts or objects will not be able to send chat until fewer messages are sent.

That's something I've only heard rumours about before.

Most of the chatty functions have throttles.  You're using llSay, so peek at the caveats in its wiki entry to find

Messages sent on channel zero^[1] and DEBUG_CHANNEL are throttled to a rate of <200/10sec, per region, per owner/user.

• Once the rate is exceeded, all following messages on channel zero or DEBUG_CHANNEL will be dropped until the send rate is again below 200/10sec for the previous 10 sec. Dropped messages, despite being dropped still count against the limit.

[ChinRey]

51 minutes ago, Madelaine McMasters said:

Why isn't it possible to generate 20K random numbers per half second? Are you thinking that's too fast, or too slow?

It's just so much faster than any other method I've thought of or heard of, it's amazing!

 

51 minutes ago, Madelaine McMasters said:

The way you've modified my random number generator will cause all three axes of your vector to contain the same value.

 

No, it won't. If you examine the code closely, you will see why. I suppose you don't want me to tell you the solution I went for

 

51 minutes ago, Madelaine McMasters said:

 Do it like this...

I tried something similar first. That was not quite as fast. The difference is marginal but why add unnecessary computing time?

 

51 minutes ago, Madelaine McMasters said:

You will also need to scale and potentially offset the lfsr value (which ranges from 0-65535) to achieve the range you want, and that will probably take about as long as generating the random numbers.

That's already in the code. It generates two decimal values between -0.50 and 0.50. I may have to reduce the span a little bit but that's easy enough and shouldn't add anything to the time.

 

One thing that is not clear to me though, is how do these times relate to actual frame time?

 

Let me see...

• I know how to make butterflies with the lowest render load possible...
• I got the wing flapping problem solved thanks to Arduenn (that's the key reason why his system worked at all)...
• Casper probably doesn't realize it but he's solved the problem how to define more complex boundaries for movements than the usual box-or-no-limits-at-all (not relevant for the butterflies but definitely something to keep in mind for other animals in the future)...
• We got the rezzer's load problem solved thanks to Kyltyna...
• We got the vector generator streamlined beyond belief thanks to Wulife, Qie, Madelaine and Nova...

Next is how to get them critters moving. llSetLinkPrimitiveParamsFast() or llSetPos()? Or maybe keyframe motion?

It seems the idea of a hundred butterflies roaming freely in a sim is possible after all. If LL would be willing to switch from OpenGL to Vulkan we could even have them all in the same scene (and surely they would be willing to do that for such a noble cause, wouldn't they?).

Now, if only we had animated mesh, we should be able make far more elaborate low lag animals than simple butterflies. But I suppose that's too much to wish for.

Bryn Oh once said she dreamed of a virtual city where pigeons roamed freely among the houses. She was taking about the upcoming Sansar then but right now it seems SL is the place to watch out for that.

ChinRey's eyes gradually glazes over as she continues her increasingly grandiose rant...

Edited November 24, 2017 by ChinRey

[ChinRey]

9 minutes ago, Rolig Loon said:

Most of the chatty functions have throttles.

Yes, I actually knew about it but I never thought I would see it.

[Rolig Loon]

 

[Qie Niangao]

39 minutes ago, ChinRey said:

llSetLinkPrimitiveParamsFast() or llSetPos()? Or maybe keyframe motion?

If individual objects are being moved around -- that is, the entire linkset is following the same trajectory -- I think you'll find KFM is more efficient because it's basically fire-and-forget as far as the script is concerned. The motion is still simulated server-side and the corresponding object updates are still sent out, but no script action is needed to keep the motion going. Scripts can interrupt KFM but otherwise it just follows the trajectory defined in the function call.

40 minutes ago, ChinRey said:

Now, if only we had animated mesh, we should be able make far more elaborate low lag animals than simple butterflies. But I suppose that's too much to wish for.

Animesh gets interesting for a different reason than more elaborately dancing animals. Instead, the entire butterfly flight can be a sequence of animations -- indeed, it should be possible to animate a whole flock of butterflies at the same time, all with different animations playing on different butterfly-bedecked bits of the skeleton simultaneously.* The reason this can be a big win, performance-wise, is that once the anims are cached to the viewer and triggered, there's no need for the simulator to do anything until the next anim needs playing. So just as KFM is "fire and forget" for the script, each anim is "fire and forget" both for the sim and for the network.

________
* I'm not sure if animesh can play the same number of simultaneous layered animations as the avatar does -- and I forget how many that is, even -- but somebody probably knows.

[ChinRey]

2 hours ago, Qie Niangao said:

If individual objects are being moved around -- that is, the entire linkset is following the same trajectory -- I think you'll find KFM is more efficient because it's basically fire-and-forget as far as the script is concerned.

Yes. KFM is an intriguing option. I've only used it once before. That was for an elevator for a house that was to be launched at a rather crowded event. Getting it to work reliably even in an ultra high lag sim was quite a challenge but I did solve it. The butterflies don't need precise movements though so it should be much easier.

However, here is a picture of an almost empty Mesh Sandbox 3 - the prim is a lucnpad for butterflies - I didn't want them to rez on ground:

Here it is with 100 butterfly mockups (small flattened prims tinted red and with glow to make them easier to spot) fluttering by:

Madelaine's semi-random number generator is actually so efficient it reduces the script time of the sim!

Seriously, a hundred of them and no measurable increase in the server load. I had to try a good thousand of course:

Render load was surprsingly low too. The finished butterflies will of course be heavier than these prim mocups but they shouldn't be that much and I can't imagine anybody would want a hundred butterflies in the smae scene, ket alone a thousand.

 

2 hours ago, Qie Niangao said:

Animesh gets interesting for a different reason than more elaborately dancing animals. Instead, the entire butterfly flight can be a sequence of animations -- indeed, it should be possible to animate a whole flock of butterflies at the same time, all with different animations playing on different butterfly-bedecked bits of the skeleton simultaneously.

Yes but I think it's clear now that animesh is not the right solution in this particular case and I think that answers a question @Vir Linden couldn't answer when I asked in the animesh feedback thread: animesh should be regarded as a supplement to and not a replacement for existing object animation methods.

Use all methods available to create animal simulations, keep a decent level of resource management and add what I was actually supposed to work ont hese days - dense, ultra low lag/LI vegetation - and we can have nature scenes so much richer and more real than anything ever seen in SL before, they can't even be compared.

That's one of my personal Second Life dreams. In RL I spend at least an hour a day walking and I once was so incredibly lucky I found me a house right in the middle of the kind of natore people come from halfway across the earth to see. I've always wanted to share a hint of that experience with my fellow SL'ers and now I'm actually beginning to think it's possible.

Edited November 24, 2017 by ChinRey

[ChinRey]

Just one more.

This is me surrounded by 100 butterflies busy flapping their wings and moving around. The load on both server and client is measurable but low enough it'll only be a problem if the scene and/or sim is already under heavy pressure. I still need to fine tune some parameters and I may try a few ways to lower the load even more but I guess all the hard work is done now.

Thanks a lot to everybody who helped me in this thread!

 

 

 

Edited November 25, 2017 by ChinRey

[Madelaine McMasters]

7 hours ago, ChinRey said:

No, it won't. If you examine the code closely, you will see why.

Oops, yep. Though you do use up additional variables. And you must be careful about the tap points as some combinations can result in LFSR lockup or truncated sequences.

;-).

[Madelaine McMasters]

7 hours ago, ChinRey said:

Bryn Oh once said she dreamed of a virtual city where pigeons roamed freely among the houses.

And I dream of a virtual city where pigeons roam freely over other people's convertibles.

[ChinRey]

2 hours ago, Madelaine McMasters said:

Oops, yep. Though you do use up additional variables.

Yes but it means I don't have to change the output thrice. I tried both options and the one I ended up with showed up as faster but with so little margin - about 10 ms for 20,000 rounds - I can't really say which would be the most efficient in the long run. It's not even micro-optimization anyway, it's pico. Or quantum even.

 

2 hours ago, Madelaine McMasters said:

And you must be careful about the tap points

I noticed. The ones I ended up with was actually the first ones I tried since they seemed to be the most obvious ones. But I had to try others of course and got some really odd results.

Another thign I played around with btw, was the range of the llFrand(). Reducing the range seemed to slow down the script considerably. I don't know why. I can think of two possible explanations but neither seems plausible and they shouldn't cause a performance drop anywhere near what I got anyway.

 

2 hours ago, Madelaine McMasters said:

And I dream of a virtual city where pigeons roam freely over other people's convertibles.

Arcadia Asylum did that more than ten years ago! If you visit the Arcadia Asylum Library at Keswick you may want to be a bit careful where you park your car...

Edited November 25, 2017 by ChinRey