Implement run-ahead

[dirkwhoffmann]

There is a neat summary of the run-ahead technique here: https://bsnes.org/articles/input-run-ahead

I think the run-ahead technique can be integrated into VirtualC64 with reasonable effort, and the emulator would benefit significantly from it.

As preparatory work, the following should be done:

• Don't let the C64 class inherit from Thread anymore. Instead, create a new Emulator class which inherits from Thread and contains a C64 object as a member. Later, this class will maintain a second run-ahead instance.
• Remove the time-slicing stuff which has been added in v4.7. It will no longer be needed and is too complicated to be mixed with the run-ahead technique.
• Implement a fast clone function that copies the contents of one emulator instance to another.

[dirkwhoffmann]

Update:

• Class Emulator has been added.
• The old time-slicing code has been trashed.
• Cloning has been added in the form of an overloaded assignment operator =.
• The == operator has been overloaded, too. It invokes checksum() underneath.
• a = b is supposed to satisfy the postcondition a == b, but it might fail yet if cartridges or tapes are attached.

My current run-ahead prototyping code looks as follows:

void
Emulator::computeFrame()
{
    // Emulate the main instance for one frame
    main.execute();

    if (config.runAhead) {

        if (updateRunAhead || RUA_ON_STEROIDS) {

            // Recreate the runahead instance from scratch
            ahead = main; updateRunAhead = false;

            if (debugBuild && ahead != main) {

                main.dump(Category::Checksums);
                ahead.dump(Category::Checksums);
                fatal("Corrupted run-ahead clone");
            }

            // Advance to the proper frame
            ahead.fastForward(config.runAhead);

        } else {

            // Run the run-ahead instance in parallel to the main instance
            ahead.execute();
        }
    }
}

Currently, it only works with debug option RUA_ON_STEROIDS enabled, which forces the emulator to recreates the run-ahead instance every frame. This is a performance nightmare, but it is still fast enough in release builds for experimental testing. Later, the run-ahead instance will only be recreated if the primary instance diverges due to an external event.

It already works pretty nicely. Below, I’ve tested with Boulder Dash and a run-ahead of 4 frames. It does feel snappier, but this is just a first personal impression and not backed up by any data.

A good test candidate would be a program that explicitly tests the user’s reaction time by displaying something on the screen and measuring how fast the user reacts, e.g., by pressing a button. If somebody knows such a program, any hint is highly appreciated.

[dirkwhoffmann]

Just thinking out loud: Instead of running two instances in parallel and recreating the second one via fast-forwarding when an external event comes in, the same effect is achievable by rewinding. In detail:

• Run a single emulator instance
• After each frame, clone the state and store it in a ring buffer

When the instance gets dirty due to an external event (joystick movement, etc.), fast-rewind by n frames by copying over a state from the ring buffer and fast-forward by emulating n frames.

Pros:

• Better performance (cloning a state is cheaper than emulating a frame)

Cons:

• Larger memory footprint. If we run ahead 8 frames, we must keep 8 emulator instances inside the ring buffer. Of course, we could also keep snapshots (which have a smaller memory footprint), but serializing to or from a snapshot is much more costly than cloning.

UPDATE: There is another big Con: We cannot easily rewind what's been written in the audio buffer. The advantage of the current approach is that the run-ahead instance only provides the texture. Audio is still coming from the main instance.

[dirkwhoffmann]

Update: The run-ahead instance is only recreated when needed. In addition, frames that are not displayed are computed in headless mode, which further saves computation time. Now, run-ahead can be used in debug builds without any issues. The new run-ahead logic looks as follows and should be pretty self-explanatory:

void
Emulator::computeFrame()
{
    if (config.runAhead) {

        // Run the main instance
        main.executeHeadless();

        // Recreate the run-ahead instance if necessary
        if (main.isDirty || RUA_ON_STEROIDS) recreateRunAheadInstance();

        // Run the runahead instance
        ahead.execute();

    } else {

        // Run the main instance
        main.execute();
    }
}

void 
Emulator::recreateRunAheadInstance()
{
    // Recreate the runahead instance from scratch
    ahead = main; main.isDirty = false;

    if (RUA_DEBUG && ahead != main) {

        main.dump(Category::Checksums);
        ahead.dump(Category::Checksums);
        fatal("Corrupted run-ahead clone detected");
    }

    // Advance to the proper frame
    ahead.fastForward(config.runAhead - 1);
}

void 
C64::fastForward(isize frames)
{
    auto target = frame + frames;

    // Execute until the target frame has been reached
    while (frame < target) executeHeadless();
}

[dirkwhoffmann]

Fixed in v5.0b1