pure C++ design pattern non-blocking for loop

Question

I tried to read about my problem but can't even find the right words to google it.

Lets say I have a function like this in pure C++ (will run on an ESP32, no threads):

void do_something_for_a_long_time(vector a) {
  for(int i=0; i < 1000; i++) {
    for(int j=0; j < 1000; j++) {
      if(a.start == a.end) {
        //go deeper
        do_something_for_a_long_time(a[1]);
      } else {
        //end of recursion
        //do something with vector
      }
    }
  }
}

The problem is a little bit more complex but the main task is like the code above. I calculate a few things in a loop and with recursion. I have to use pure C++ without threads as it will run on Arduino.

What would be a good design pattern to solve something like this to be able to get a non-blocking calculation:

loop() {
  //call this often
  do_something_non_blocking(...);
  //other stuff
}

The thing I mean is that I would like to do one next step if the non-blocking function is called and would call the function very, very often instead of call it once and get the result (and block everything). I could create some complex state machine but would like to find a general clean solution. It is partly to get better with the design if problems like this come up.

Ideas:

• split for loops in
  • init
  • body
  • exit
• write a macro library to encapsulate code in a state machine

Answer 1

You could do something similar to this, it leverages C switch statements in a creative(and honestly horrifying) way to implement co-routines, in this case he uses static variables which in general might not be a good idea but I think it'll work for your use case as well.

Answer 2

The general concept you're looking for is coroutines or co-operative multi-tasking.

The idea is that functions can be suspended and resumed, so that multiple activities can be interleaved on a single thread.

It's "co-operative" because the functions need to explicitly yield (for example with co_yield or co_await) instead of being pre-empted by a scheduler like with threads.

You can always write some kind of state machine(s) to do this manually, in much the same way that we could write functor classes that manually stored their state before we had lambdas with first-class language support.

NB. For your specific use case, a state machine would need to somehow break your search space into discrete chunks (of acceptable duration) and then just process one chunk per "step". If you can manage this so that you get a reasonably good result even if you run out of time to find the best possible move, even better.