bounding solution times

[wrigjl]

The problems currently in Redux are, by definition, computationally difficult. It is very easy for a user to create a problem that will cause the server to spin solving a problem that might take until the heat death of the universe.

I have started to play with the idea of spawning solvers in a separate thread and then killing the thread if it takes too long.

The idea is sound, but the implementation is a more subtle. The problem lies in the fact that you can't just kill a thread (thread.Abort has been deprecated since .net 5). Instead, the model is that the thread should be signaled (i.e. call something like solver.YourTimeIsUp() after a reasonable amount of time). The thread must regularly check this value (i.e. in its main loop) and cease operations.

The solver main loop would look something like:

while (!done) {
   do_a_unit_of_work(); // one node, one slice, one whatever
   if (timeIsUp) {
       return "timeout";
   }
}

The good news is that a naïve solver (one not fitted with this abort logic) would be no worse than current (i.e. if it runs to heat death of universe now, it will continue to do so). Below is a quick proof of concept for comment. (No ? or ! shaming... they're just hacks so I can produce a minimal proof-of-concept).

using System.Threading;

namespace wrigjaso.factortimer;
/// <summary>
/// This is used to pass data to and from the solver thread.
/// </summary>
class WorkItem
{
    public Solver? solver;
    public string? instance;
    public string? result;
}

/// <summary>
/// This is a dummy solver that simulates a long computation.
/// </summary>
class Solver
{
    // Indicates whether the solver should time out or not.
	private bool timeOut;

    /// <summary>
    /// Indicates whether the time has run out. A solver need to check this flag periodically.
    /// while attempting a solution.
    /// </summary>
	private bool timeIsUp = false;
	
    public Solver() => timeOut = false;

	public Solver(bool _timeout)
	{
		timeOut = _timeout;
		timeIsUp = false;
	}

	public void TimeIsUp()
    {
        timeIsUp = true;
    }

	public string solve(string instance)
    {
        if (timeOut)
		{
			for (;;) {
                // simulate a long computation (this one will never finish)
				TimeSpan waitTime = new TimeSpan(0, 0, 1);
				Thread.Sleep(waitTime);

                // If someone notifies us that time is up, we break out of the loop.
				if (timeIsUp) {
					break;
				}
			}
			return "timeout";
		}
        return "solved";
    }
}

internal class Program
{
    static void Main(string[] args)
    {
        // Construct a work item to pass to the thread.
        // It needs a fully constructed solver and an instance as input.
        // Any solution found will be stored in the result field.
        WorkItem workItem = new WorkItem();
        workItem.solver = new Solver(true);
        workItem.instance = "instance";

        Thread thread = new Thread(ThreadWorkFunction);
        thread.Start(workItem);

        // Wait for the thread to complete, but only for 5 seconds.
        if (thread.Join(new TimeSpan(0, 0, 5))) {
            Console.WriteLine("Computation completed.");
        } else {
            // Time is up, notify the solver and wait for the thread to finish.
            Console.WriteLine("Computation timed out.");
            workItem.solver.TimeIsUp();
            thread.Join();
        }

        Console.WriteLine($"Solution: {workItem.result}");
    }

    public static void ThreadWorkFunction(object? obj)
    {
        WorkItem workItem = (WorkItem)obj!;
        workItem.result = workItem.solver!.solve(workItem.instance!);
    }
}