SSE (papyrus) Utiliy.RandomInt is glacial... rant and alternative

[subhuman0100]

Ok, let's get the rant out of the way first.

I'm aware of the difference between delayed and non-delayed functions. What I don't get is why RandomInt (or RandomFloat) is the former. Why does it have to interact with the game world and get a lock on "some object"?? It shouldn't have to. The Math functions aren't delayed. I can do Math.Pow(14.7, 8.3) numerous times before RandomInt(0, 1) gives me the result of a virtual coin-flip.

Ok, I'm old. I'm allowed to rant sometimes. Now that's out of the way, let's move on...

 

So, profiling a script I'm working with and count how many times RandomInt appears in the profile log with just one iteration of the script: 972. Ok, there's a push and a pop for each time, so the number of times I asked for the RNG was half that, or 486. That's 8 seconds (rock-steady 60fps) spent waiting for results from random numbers. Unacceptable. Another solution is needed.

Thought about it a while. Slept on it. Thought about it some more. Knocked around some ideas.

 

Step 1:

Create an array. And pre-populate it with random numbers.

; up top
int[] Property RandomIntArray Auto  
; pre-existing crap goes here
; --snip--    
if (RandomIntArray.Length != 1024)
        Debug.Notification("Initializing Random Array")
        RandomIntArray = Utility.ResizeIntArray(RandomIntArray, 1024, -1)
        int n = 1024
        while (n)
            n -= 1
            RandomIntArray[n] = Utility.RandomInt(0, 99)
        endWhile
        Debug.Notification("Array Created.")
    endIf

Ok, let's make an array with length 1024 and stuff randomly generated values from 0-99 into it.

I'm already married to SKSE, so the array length isn't an issue. With an array of 1024, it's very likely (but not guaranteed) that every possible value is in it at least once. With the "vanilla" limitation of 128 entries on an array, the same can't be said. There, it would be likely that at least one value would be missed.

But it's not foolproof. It's possible, albiet unlikely, that one or more values would never appear in the array.

This also takes about 17 seconds to populate (at 60FPS) but luckily it only runs once, unless you make a new character.

 

That bit-o-code is called as part of the OnPlayerLoadGame event.

 

Step 2:

This, is a replacement for Utility.GetRandomInt

Call it with no parameters, or with an offset to the seed, and it returns a value in the range of 0-99, same as GetRandomInt would. But a lot faster. More on that later.

; up top:
int _seed = 42 ; because... why not? 
; --snip-- 
int function FetchRandom(int modifier = 1)
{tries to return a pre-generated random from our array, if that fails generate one}
; if there\'s something wrong with the array, GTFO
    if (RandomIntArray.Length != 1024)
        return Utility.RandomInt(0, 99)
    endIf
; limit check the modifier
    if (modifier == 0)
        modifier = 1
    elseIf (modifier < -511)
        modifier = 1
    elseIf (modifier > 511)
        modifier = 1
    endIf
    int newseed = (_seed + modifier)
    while (newseed > 1023)
        newseed -= 1024
    endWhile
    while (newseed < 0)
        newseed += 1024
    endWhile
    int retInt = RandomIntArray[newseed]
    if ((retInt > -1) && (retInt < 100))    ; paranoid check to ensure our response is in bounds
        _seed = newseed
        return retInt
    else
        return Utility.RandomInt(0, 99)
    endIf
endFunction

There's two fallbacks, if either the array hasn't been initialized yet or if the returned value is out of bounds it goes to the slow Utility.GetRandomInt. Based on profiling timings, this isn't happening. It's working. And occurrances that only trigger with a 1% chance are occasionally happening, so it seems my array has an acceptable distribution of numbers in it.

However, there's no guarantee that it would for anyone else.

So far it's looking great. Profiling shows this spitting up values in 0-4mSec, much much better than GetRandomInt with it's 16-17 mSec.

So it's considerably faster.

But as I said, no guarantee that any *other* array would have a good distribution of values in it. So...

 

Step 3:

This is called by the OnLocationChange event.

function RefreshRandoms()
{when called, re-rolls 20 of the values stored in the random array}
; ensures the randomintarray get fresh values periodically.
; of course, replacing 20 at a time in an array with 1,000
; entries takes a few iterations...
    if RandomIntArray.Length != 1024
        debug.notification("lengthcheck failed!")
        return
    endIf
    int replacements = _seed
    while (replacements > 1023)
        replacements -= 1024
    endWhile
    while (replacements < 0)
        replacements += 1024
    endWhile
    int iterations = 20
;    debug.notification("replacing 20 randoms, " + replacements)
    while (iterations)
        if (replacements > 1023)
            replacements = 0
        endIf
        RandomIntArray[replacements] = Utility.RandomInt(0, 99)
        iterations -= 1
        replacements += 1
    endWhile
    _seed = replacements
;    debug.notification("randoms replaced, " + replacements)
endFunction

When the player changes location, 20 of the values in the array are replaced with other random values. The stored values are ever-changing, so if at any point in time the array doesn't contain at least every possible value, it will correct itself shortly as the player moves around. It might occasionally break itself, too. But it will self-correct over time. That's the beauty of randomness.

 

The _seed variable is just the starting index to retrieve. The modifier variable that may be passed to FetchRandom is added to the _seed to determine which index to retrieve, then _seed is replaced by that index. If the calling function has some int stored in a var, I pass that along. Maybe it's GetCurrentRealTime as int, or maybe it's something negative. Just some different value to encourage jumping all over the array to grab values.

_seed is initially 42, but the OnPlayerLoadGame event does "_seed += Utility.GetCurrentRealTime() as int" so it ends up being something else before it's ever utilized.

 

tldr: seems to be working, much faster than GetRandomInt. If anyone has thoughts, critiques or wants to put it to the test I'd love feedback.

Try to break it. If you do, let me know how so I can fix it.

Edited March 2, 2021 by subhuman0100

[Evangela]

It depends on the RNG algorithm used, some dev teams use some pretty bad ones lol, and we're talking about BGS here who isn't known for optimization.

[dylbill]

Since you're already using SKSE you might consider using Papyrus Extender: https://www.nexusmods.com/skyrimspecialedition/mods/22854

 

It has GenerateRandomInt and GenerateRandomFloat functions which I can confirm are a lot faster than the RandomInt and RandomFloat functions.

[subhuman0100]

 

 

Since you're already using SKSE you might consider using Papyrus Extender:

There's a %A0 at the end of that link that's causing it to break.

 

I've looked at his Papryus Extender in the past, for other purposes. For some reason, it never came up when I spent many, MANY hours over several days of searching for faster alternatives to RandomInt. Maybe because I always searched for "papyrus" in the terms, and it's not a papyrus implementation?

It actually adds multiple additional dependencies, since Papyrus Extender has dependencies itself (Address Library for SKSE plugins & VC Redistributables), but granted most people will already have (or should have) the VC Redistributables.

I'll have to profile some runs with it and see what sort of times I get.

[dylbill]

Most mods now that have an skse plugin require Address Library for SKSE Plugins, as it solves version conflicts. As a small test I did this script:

 

Event OnInit() 
    Debug.Notification("Test Init")
    Debug.OpenUserLog("DB_TestRandom")
    Float StartTime = Game.GetRealHoursPassed()
    Int I = 0 
    While I < 100 
        I += 1 
        Debug.TraceUser("DB_TestRandom", PO3_SKSEfunctions.GenerateRandomInt(0, 100))
    EndWhile 
    Float EndTime = Game.GetRealHoursPassed()
    Float Diff = EndTime - StartTime
    Debug.TraceUser("DB_TestRandom", "Time diff = " + Diff)
    Debug.MessageBox("Time diff = " + Diff)
EndEvent

The time diff using Utility.RandomInt was 0.000890, using PO3_SKSEfunctions.GenerateRandomInt it was 0.000031.

[subhuman0100]

 

 

The time diff using Utility.RandomInt was 0.000890, using PO3_SKSEfunctions.GenerateRandomInt it was 0.000031.

Using that method, I get Utility.RandomInt: 0.000458, PO3: 0.000023 and FetchRandom: 0.000084

in milliseconds per single iteration, that's: 16.48, 0.83, 3.02

It looks like the machine you ran that on isn't hitting 60FPS, which makes a delayed function like RandomInt even worse, your average is 32mSec per.

"100 iterations in only 0.00089" looks fast until you realize that's in hours

So far, RandomInt cons: glacial. Even moreso at lower framerates Pros: no dependencies

PO3's GenerateRandomInt cons: more dependencies Pros: fastest

FetchRandom Cons: slower than P03 Pros: less dependencies than PO3, much faster than RandomInt

 

But what you've shown here agrees with what I said in the opening post, the problem with RandomInt is it's a delayed function.