Are lexicon lookups O(1) or O(n)?

[u/SilverNuke911]

Hey there! I'm trying to do a little bit of an implementation of a switch-case in KOS, since it has no in-built one and I'm kinda starting to get put off by the if-else ladder of runmodes in a loop. An example code of my usual implementation would be something like this. However, the problem with this the code has to run every if-else check for every runmode before arriving to the desired runmode state, which I imagine would take a long time, especially if we're talking like, 20+ state cases.

function open_loop_guidance {
    local runmode to 1.
    until runmode = 0 {
        // Runmode states
        if runmode = 1 { // Ignition
            stage.
            lock steering to heading(90,90,-90).
            set runmode to 2.
        } else if runmode = 2 { // Clearing tower
            if ship:verticalSpeed > 100 or alt:radar > 1000 {
                set shift_alt to ship:altitude.
                lock steering to heading(90,90-0.4 * sqrt(max(ship:altitude-shift_alt,0)),-90).
                set runmode to 3.
            }
        } else if runmode = 3 { // Waiting for the ship to point to a specific altitude angle (slew)
            if vang(ship:facing:vector, ship:up:vector) > slew_angle {
                lock steering to heading(90,90-slew_angle,-90).
                set runmode to 4.
            }
        } else if runmode = 4 { // Wait until pointing and velocity vectors line up
            if vang(ship:facing:vector, ship:srfPrograde:vector) < 0.25 {
                set runmode to 5.
            }
        } else if runmode = 5 { // Zero aoa gravity turn
            lock steering to heading(90,90-vang(ship:up:vector, ship:srfprograde:vector),-90).
            set runmode to 6.
        } else if runmode = 6 { // Minimize acceleration to 2g after surpassing it
            if ship:availableThrust / (ship:mass * constant:g0) > 2 {
                lock throttle to throttle_2g().
                set runmode to 7.
            }
        } else if runmode = 7 { // Jettison the first stage and end the open loop guidance.
            if ship:availableThrust < 2 {
                lock throttle to 0.
                safestage().
                wait 1.
                safestage().
                lock throttle to throttle_2g().
                set runmode to 0.
            }
        }

        // Real-time telemetry updates every frame
        set cycles to cycles + 1. // Cycle count
        screen_data(). // Just displays relevant flight telemetry data on the screen
        wait 0. 
    }
    clearScreen.
}

As such, I'm experimenting with code that uses a lexicon lookup table, like this:

// States are the same on the if-else ladder. 
function open_loop_guidance {
    // Define state handlers that return next state
    local handlers to lexicon().

    handlers:add(1, function() {
        stage.
        lock steering to heading(90,90,-90).
        return 2.
    }).

    handlers:add(2, function() {
        if ship:verticalSpeed > 100 or alt:radar > 1000 {
            set shift_alt to ship:altitude.
            lock steering to heading(90,90-0.4 * sqrt(max(ship:altitude-shift_alt,0)),-90).
            return 3.
        }
        return 2.
    }).

    handlers:add(3, function() {
        if vang(ship:facing:vector, ship:up:vector) > slew_angle {
            lock steering to heading(90,90-slew_angle,-90).
            return 4.
        }
        return 3.
    }).

    handlers:add(4, function() {
        if vang(ship:facing:vector, ship:srfPrograde:vector) < 0.25 {
            return 5.
        }
        return 4.
    }).

    handlers:add(5, function() {
        lock steering to heading(90,90-vang(ship:up:vector, ship:srfprograde:vector),-90).
        return 6.
    }).

    handlers:add(6, function() {
        if ship:availableThrust / (ship:mass * constant:g0) > 2 {
            lock throttle to throttle_2g().
            return 7.
        }
        return 6.
    }).

    handlers:add(7, function() {
        if ship:availableThrust < 2 {
            lock throttle to 0.
            safestage().
            wait 1.
            safestage().
            lock throttle to throttle_2g().
            return 0.
        }
        return 7.
    }).

    // Main guidance loop
    local current_state to 1.
    until current_state = 0 {
        local handler to handlers[current_state].
        if handler:istype("function") {
            set current_state to handler().
        }

        // Telemetry 
        set cycles to cycles + 1.
        screen_data().
        wait 0.
    }
    clearScreen.
}

I haven't done benchmarking yet, and honestly they behave kind of the same, though I think this is only because it has 7 cases and that's pretty small. I wanna know if this lexicon lookup implementation is at least marginally better than an if-else ladder in finding the correct case, i.e., are lexicon lookups O(1) or O(n)?. Because if they aren't, I don't think there's a point on changing the tried and tested if-else ladder implementation. I don't even know if the if-else ladder is faster than this lexicon implementation. But hey, points for trying, I guess.

Anyway, thanks!

Edit: This might be a bit wrong, idk how anonymous or lamda functions work as of yet. This new code is untested, but yeah consider the heart of the question to be the same: Are lexicon lookups O(1) or O(n).

[u/rc1024]

Lexicons are implemented as a C# Dictionary so lookups are approximately O(1) in the general case.

[u/SnooPets5564]

The lookups are O(1), iirc. It doesn't matter though. You're going to have, you say, like 20 state cases. So even if you do an O(n) operation, it is O(20)=O(1). The performance impact is so negligible that you don't need to worry about time complexity for this. Especially because the O(1) lookup has overhead to it that could easily take longer than an O(n) if else ladder for the small values you are using. 

If you are using smaller numbers though, why use that method? You could have a list of functions rather than a lexicon, right?

[u/nuggreat → u/SnooPets5564]

In most cases you would be correct but the lookup time for both lists and lexicons are the same and all of the lookup overhead is abstracted away to the C# side of kOS so you are looking at around 3 kRISK OPcodes (kRISK being the OPcodes the kOS compiles your scripts into and then executes on it's VM) for any one look up which makes the if else ladder a more costly for even n of 2.

[u/Teh_Original → u/nuggreat]

• How can lookup time be abstracted away?

• Are they still built as Lists vs Dictionaries in C#? Or are you saying they are all just 'compiled' to the same data type when it gets 'compiled'.

[u/Jonny0Than → u/Teh_Original]

Because the KOS CPU is an abstract virtual machine, and it only executes a specific number of KRISC opcodes per frame. You actually don’t care about how may x64 operations are being done (well, a bit) but the number of KRISC opcodes actually has an impact on whether your Kos program fully executes whatever it needs to do in one frame or not, which can have a big impact on whether it actually works correctly.

[u/nuggreat → u/Teh_Original]

In kOS there are 2 perspectives to think about, there is the in game in universe perspective and then there is what actually exists and executes on your hardware.

From the in universe perspective a kOS CPU has a maximum clock speed of 100khz. As a result of this very slow clock speed kOS CPUs provide a lot of advanced native operations such as native 3d vector math that costs no more instructions than integer operations. One such advanced set of instructions would be accessing a value by key from a lexicon which takes only one OPcode.

From the actual hardware perspective kOS compiles your code into kRISK which is then run on the kOS VM which translates from the kRISK OPcodes to the actual C# code that your computer executes to do things.

The result of all of this is that if you can you in most cases you want to move operations from being implemented in kRISK to executing as C# code because any kRISK OPcode is so much more costly in terms of time than the executing C#. This is mostly because any one OPcode is "given" a few µs to do it's operation and the vast majority of them do not need that full time so if every now and then some of them take more time it doesn't matter that much as you won't lag the game unless you spam a lot of really heavy operations.

EDIT: From what I remember of some of my discussions with devs both lists and lexicons use the same underlying C# structure and so while presented differently to users preform very similarly in use.

[u/DBooots]

The short answer is yes, lexicon (and list) lookups are O(1).

As a longer answer, there’s still a lot of overhead to the method you’ve implemented, but it will definitely be faster (at least for later states). A better pattern would be:

Until [condition for next state] {current state code}

And then repeat. Your program will be easier to read and faster, at a marginal increase in file size.

[u/SilverNuke911 → u/DBooots]

Thanks for the answer! For my programs I prefer to do looping because there are some runmodes that I will return to after some condition is met, i.e., two or three runmodes just passing the current task to each another until the condition is met. The code above is just an example.

[u/nuggreat]

When it comes to kOS there are always 2 sides to a big o question the C# side and the kerboscript side. The difference is important because C# is a lot faster to do things and so in most cases even something that isn't O(1) in C# can be treated as O(1) on the kerboscript side. So even if the C# side of a lexicon was not O(1) the kerbscript side is and thus you get much more performance by shifting the overhead to C#.

Also for your lexicon based run mode system you should only get the handler once per change in state not every pass of the loop.

As for the syntax of anonymous functions it depends as there are 2 main ways to go about making function delegates depending on exactly how you set things up. You can make and store delegates for functions using the @ symbol like this LOCAL foo TO some_function@.. You can also directly store a delegate like this LOCAL foo TO { PARAMETER a, b. RETURN a + b.}.. You can also push the control structure farther into abstraction than you currently are as an example this is my go to time warp control library.

Lastly for your example run mode state machine you would be better off doing neither and instead implementing it as a sequence of different until loops that just do the screen printing and between each loop is where you change the guidance and other things related to craft control state. I say this because your current thing only advances state by 1 each time or keeps the same state so runmode which is a more complex structure intended to let you go back to previous modes adds overhead for that feature that you never use.

[u/SilverNuke911 → u/nuggreat]

Thanks!. I prefer doing runmode loops for this one because there would be conditions that I would need to return later on in the launch, this is mainly just an an example. Anyway, would the lexicon implementation be faster than the if-else implementation during loops? Would it take longer? Is there no significant difference?

[u/nuggreat → u/SilverNuke911]

The lexicon implementation will be significantly faster than an if else tree. You can even give the modes more descriptive names which can help a lot coming back to a script after some time away.