Playback optimization

[penolakushari]

Current SMH does playback by running calculations every tick, at least on workshop version and the smooth playbacked beta, while beta does at least try to run calculations every frame change on normal playback. It does get messy, and I think having a way to keep track of current frames would be better by somewhat caching them in memory, and not having to parse through all of the keyframes as often.

I was thinking having a way to tell where our playhead is should help with tracking the keyframes we should be playing, so there could be some way to track previous frames of entities we're playing, their next ones, and the current interpolation % we're going between them. Having all of these calculations done on playhead change and tracking next keyframes through linked lists (as keyframes could put pointers to their next and previous frames inside themselves?) could allow for lessening amount of calculations to be done to see where we're at, at the cost of increasing memory usage, I assume.

Currently I forgot the finer details of what I've wanted to do, but probably we could get something from here, even if explanation is sort of messy.

[vlazed]

The first paragraph is addressed by this PR, which I called the first part of the playback optimization.

It localizes tables and setting checks to reduce function and indexing overhead. It also memoizes GetBetweenKeyframes, an expensive function which iterates over keyframes, for a given entity, modifier, and frame. Lastly, it also sorts keyframes by frame number in an entity's KeyframeData, to take advantage of the fact that a frame can easily be between a previous and next keyframe, allowing for early exits for GetBetweenKeyframes. If I observe any performance increases through benchmarking, I will PR it, with comparisons between the three PR commits.

The next PR, Part 2, will handle the second paragraph of this issue.

[vlazed]

Did a bunch of benchmarking with lots of results.

Conclusion

Playback caching and keyframe sorting bring some significant performance increases. Together, they increase performance by 1336% on average for tween-disabled or normal playback, and around 346% on average for smooth playback. This PR would make a convenient reference for illustrating how caching can speed up a system. Nonetheless, the tradeoff is memory, and this can definitely be seen with PlaybackSmooth: it caches frames with decimal points, rather than integers. This reduces the playback cache's effectiveness. However, sorting keyframes on keyframe updates allows one to reduce iteration overall, which results in bigger performance gains.

Click here for more details

The benchmarking happened on the x86-64 Chromium branch, running GMod at 64-bit. I use a Ryzen 9 4900HS processor with an RTX 2060.

The following graphs use this notation:

• Set refers to SetFrame functions
• Smooth refers to PlaybackSmooth functions
• The numbers 1, 2, 3 refer to commits 61c7a3b, 24c27de, and 93f8c29 respectively.

Here, Set 1 and Smooth 1 refer to the commit that reduces indexing and function call overhead. Nonetheless, the performance increases from these are not as noticeable versus the latter commits, so for simplicity, I'll be using Set 1 and Smooth 1 as the baseline that playback caching and keyframe sorting must improve.

Methodology

To perform some benchmarking on the playback functions, I made a script which detours the SMH's Playback Think hook with a version that gets the frame time for the SetFrame and PlaybackSmooth functions.

smh_benchmarker.lua

if SERVER then
    local performanceMetrics = {
        frameTimes = {},
        isRecording = false
    }

    timer.Simple(0, function ()
        local originalThink = hook.GetTable()["Think"]["SMHPlaybackManagerThink"]

        if originalThink then
            hook.Remove("Think", "SMHPlaybackManagerThink")
            hook.Add("Think", "SMHPlaybackManagerThink_Instrumented", function ()
                if performanceMetrics.isRecording then
                    local frameStart = SysTime()
                    originalThink()
                    local frameTime = SysTime() - frameStart

                    table.insert(performanceMetrics.frameTimes, {
                        time = frameTime,
                        timestamp = SysTime()
                    })
                else
                    originalThink()
                end
            end)
        end
    end)

    util.AddNetworkString("SMHBenchRecording")
    net.Receive("SMHBenchRecording", function (len, ply)
        local isRecording = net.ReadBool()
        performanceMetrics.isRecording = isRecording
        performanceMetrics.frameTimes = isRecording and {} or performanceMetrics.frameTimes
        print(isRecording and "[SMH Bench] Recording started" or "[SMH Bench] Recording stopped - " .. #performanceMetrics.frameTimes .. " samples")
    end)

    util.AddNetworkString("SMHBenchExport")
    net.Receive("SMHBenchExport", function (len, ply)
        local filename = net.ReadString() or "default"
        if not performanceMetrics.frameTimes[1] then
            print("[SMH Bench] No data to export")
            return
        end

        local csv = "Timestamp, Time_ms\n"
        for _, data in ipairs(performanceMetrics.frameTimes) do
            csv = csv .. Format("%.6f,%.6f\n", data.timestamp, data.time * 1000)
        end
        
        file.Write("smh_bench_" .. filename .. ".csv", csv)
        print("[SMH Bench] Exported to smh_bench_" .. filename .. ".csv")
    end)
    return
end

concommand.Add("smh_bench_start", function (ply, cmd, args, argStr)
    net.Start("SMHBenchRecording")
    net.WriteBool(true)
    net.SendToServer()
end)

concommand.Add("smh_bench_stop", function (ply, cmd, args, argStr)
    net.Start("SMHBenchRecording")
    net.WriteBool(false)
    net.SendToServer()
end)

concommand.Add("smh_bench_export", function (ply, cmd, args, argStr)
    net.Start("SMHBenchExport")
    net.WriteString(args[1])
    net.SendToServer()
end)

I used a macro (see this addon) to automate the console commands from this script: smh_bench_start, smh_bench_stop, and smh_bench_export. This macro starts benchmarking, executes +smh_playback to start the playback hook, and then waits 60 seconds to allow the animation to run for 60 seconds. At the end, it stops benchmarking and exports a csv file for plotting and analysis.

Macro

[{"Type":1,"Var":1},{"Type":2,"Var":"smh_bench_start"},{"Type":1,"Var":0.01},{"Type":2,"Var":"+smh_playback"},{"Type":1,"Var":60},{"Type":2,"Var":"-smh_playback"},{"Type":2,"Var":"smh_bench_stop"},{"Type":1,"Var":0.01},{"Type":2,"Var":"smh_bench_export smooth_3"}]

Finally, I had a 60-second animation prepared for this. The animation is a race car with one wheel driving around gm_highway223. This was achieved with my vehicle recorder addon and Glide.

Results

To understand the graphs, lower render times is better for performance.

SetFrame

I noticed that the Set 1 line graph had some weird render times, where some frames took longer to render than others. This resulted in a plot where points jumped from below 1 to above 6. This is noticeable too in Set 2 and Set 3 line graphs. The bar graphs show this outlier behavior with the inclusion of 95th percentile and 99th percentile bars.

To help show render times, the below figure excludes Set 1.

Here, it is clear that playback caching dramatically reduces render times down to below 1 millisecond. There does not appear to be much difference between the two commits: Set 2 is slightly faster than Set 3 (by average and by percentile). However, when using PlaybackSmooth, the next set of figures tell a different story.

PlaybackSmooth

Here, the line graphs do not suffer from jumps, which helps make clear the difference between the 3 commits. In the bar graph, playback caching reduces the frame rendering time for PlaybackSmooth by about 1 millisecond. This is because frames in PlaybackSmooth are doubles, rather than integers. Hence, it is less likely to have a frame in the cache.

By sorting keyframes by frame number, GetBetweenKeyframes is likely to early-exit from iteration. This results in a significant decrease in render time, to around 3 milliseconds.

[vlazed]

Clearly there were performance gains, so I went ahead and PR'd this. I'll keep an eye on any issues that pop up soon with this. Otherwise, we await Part 2

[vlazed]

Reminder for myself: To address some concerns related to memory with the current playback cache implementation, I plan to rewrite this such that caching only happens between two keyframes. This might involve a cursor table that tracks its between keyframes for a given entity/modifier pair.

[vlazed]

The next PR addresses the second paragraph of this issue. It introduces three playback improvemenets:

• It changes playbackCache to store the previous keyframe, next keyframe, and 1 / interval between the two keyframes, per player-entity-modifier triplet.
• It adds Next and Previous fields, which point to the next and previous keyframes in a sorted keyframe array (commonly known as keyframes inSMH.KeyframeData.Players[ply].Entities[entity]).
• It uses a new function, WalkBetweenKeyframes, which uses the Next and Previous fields to walk to the nearest keyframes for a given frame. It can also use a start keyframe to provide a beginning point for walking.

By reducing playbackCache to store two keyframes, I've noticed slightly worse performance for SetFrame and slightly improved performance for PlaybackSmooth. To simplify this ambiguity, I'll say that I haven't observed any performance gains.

Adding Next and Previous fields does increase memory, but it uses (pointer) references to these keyframes. The memory from using references would have to be smaller than the deep keyframe copies. By how much, I'd like to know. (I've read that key-value pairs to anything, like table references, are worth 40 bytes when storing them in the hash part.)

Combining the two points above, WalkBetweenKeyframes uses the Next and Previous fields to move across keyframes, with a start keyframe. This reduces the iterations to find Previous and Next Keyframes: it no longer has to span through keyframes to find the previous and next keyframe pair for a given modifier. For playback purposes, since previous and next keyframes tend to be paired together in order, this ends up being O(1). The benchmarking shows this improvement.

Video demonstration

Legacy Note

For preservation, the old method for setting frames, which is now called SelectFrames, still uses GetBetweenKeyframes to iterate over all keyframes. I've noticed that WalkBetweenKeyframes breaks the auto-smoothing feature, so I've kept the old method to ensure that works. In the future, I want WalkBetweenKeyframes to work like GetBetweenKeyframes.

Benchmarking

View benchmarking details here

I use the same methodology to measure the performance impact: two prop_physics entities with around 2000 keyframes, and a macro to record frame render times to a .csv file.

Results

Cache refers to Part 1's method. Cursor refers to Part 2's method. Set and Smooth refer to regular playback and smooth playback respectively.

SetFrame and PlaybackSmooth

I'll showcase the two graph pairs to quickly summarize the impacts of Part 2's playback improvements

Here, Set Cursor (Smooth Cursor) refers to caching the previous and next keyframes, while Set Cursor 2 (Smooth Cursor 2) adds onto this method by using WalkBetweenKeyframes instead of GetBetweenKeyframes.

The first step in the cursor method (Set / Smooth Cursor) does not increase or decrease performance overall; it decreases frame render time for smooth playback but increases it with nonsmooth playback. Observe that the render times (green line on line graph) increase consistently as times go down. This is because the keyframes are sorted in GetBetweenKeyframes, and as iteration starts at the beginning of keyframes, it takes longer to find the previous and next keyframe pair.

The second step illustrates a dramatic performance difference between the frame render times of Set Cache and Set Cursor 2. Rather than starting iteration at the beginning of keyframes, playback now references its neighboring keyframes to find the previous and next keyframe pair. Compared to the O(n) in the worst case (the playhead is at n keyframes), we now observe O(1) for accessing the next and previous keyframes. This achieves 0.002 ms (2 microseconds) of rendering on average per frame. (That's why the bar graph for Smooth/Set Cursor 2 is barely visible.) This is a 250x increase in performance compared to the caching method.

[vlazed]

I've merged #29 now. I've yet to close the issue, as I expect there to be some bugs that'll sprout up (see #26 and #27). I also belive that #24 and #29 do not span the entirety of playback optimization, with respect to the other features on the roadmap #2. When #4 and #16 have been resolved with respect to this issue, then I'll close this one

[penolakushari]

i recall now that having freeze all disabled was also making playback laggier, probably due to having more checks ran in physbones modifier for whether phys objects was frozen or unfrozen, and then applying freeze/unfreeze to it. does it still have an effect? though, to be honest i thought unfrozen stuff still being posed was rather counterproductive, so it may need some adjustments anyway rather than being kept as is

[vlazed]

It's an extra table index if Freeze All is disabled: it indexes with d.Moveable during the pb:EnableMotion(d.Moveable) call. Even then, I think the best way to squeeze more performance into the current modifiers is to cache some indices: e.g. localize settings.FreezeAll and settings.LocalizePhysBones before the loop

[vlazed]

Also, I've realized there's a mistake in the data from the benchmarking, so I plan to make another comment here that has the revised results. Long story short, we get more honest performance increases than the dramatic ones from earlier (1.1x increase for nonsmooth playback, and around 13x for smooth playback)