mirror of
https://github.com/revng/revng
synced 2026-06-21 14:07:57 +00:00
Pietro Fezzardi
e1b283b0b6
RecursiveCoroutines are a facility intended to be used as-drop in
replacement of recursive functions.
They provide the following features.
- They can be written almost as regular recursive functions,
with 4 caveats.
1. A recursive coroutine that returns a type `T`, needs to be declared
to return a `RecursiveCoroutine<T>`.
2. Inside the body of a recursive coroutine, when recursively calling
another recursive coroutine, the recursive call needs to be
prepended by the new keyword `rc_recur`.
3. Inside the body of a recursive coroutine, the `return` statement
needs to be substituted with `rc_return`.
4. When launching a recursive coroutine `A` from a function that is
not a recursive coroutine, `A` needs to be called with the provided
dedicated template wrapper `rc_run`.
The syntax is the following `rc_run(A, arg0, arg1, ...)`.
This is necessary to enable swapping off recursive coroutine and
fall back to regular recursion for debug.
See below for how to do it.
- Unlike regular recursive functions, they don't use the system stack
for recursion. They use a custom heap-allocated stack to manage
recursion. This makes them more robust for implementing recursive
functions that manipulate user-defined input, because they are much
less likely to trigger stack overflow.
- They can be turned off compiling with
`-DDISABLE_RECURSIVE_COROUTINES`, falling back to regular recursion,
for debug purposes.
- They support both direct and indirect recursion, i.e. a recursive
coroutine A can recursively call itself, or it can recursively call
another recursive coroutine B, which in turns recursively calls A.
140 lines
3.0 KiB
C++
140 lines
3.0 KiB
C++
//
|
|
// This file is distributed under the MIT License. See LICENSE.md for details.
|
|
//
|
|
|
|
#include <chrono>
|
|
#include <experimental/coroutine>
|
|
#include <functional>
|
|
#include <iostream>
|
|
#include <vector>
|
|
|
|
// TODO: increase height up to explosion
|
|
// TODO: compare performance and peak memory
|
|
|
|
#include "revng/ADT/RecursiveCoroutine.h"
|
|
#include "revng/Support/Assert.h"
|
|
|
|
#include "DepthFirstVisit.h"
|
|
#include "SimpleRecursiveCoroutine.h"
|
|
|
|
size_t MaxDepth = 0;
|
|
size_t Iterations = 0;
|
|
|
|
int main(int, char *[]) {
|
|
|
|
//
|
|
// Run a simple recursive coroutine
|
|
//
|
|
std::vector<MyState> MyStateRCS;
|
|
MyStateRCS.emplace_back();
|
|
rc_run(my_coroutine, MyStateRCS, 0);
|
|
|
|
//
|
|
// Visit a simple graph
|
|
//
|
|
Graph SimpleGraph = createSimpleGraph();
|
|
#ifdef ITERATIVE
|
|
|
|
std::vector<Entry> ThisRCS;
|
|
|
|
auto *Root = SimpleGraph.root();
|
|
auto &Children = Root->children();
|
|
|
|
ThisRCS.emplace_back(Entry{ Root, true, Children.begin(), Children.end() });
|
|
iterativeFindMaxDepth(ThisRCS);
|
|
|
|
#else
|
|
|
|
std::vector<Node *> ThisRCS;
|
|
// findMaxDepth expects the RCS to already contain the state for the first
|
|
// element
|
|
ThisRCS.emplace_back(SimpleGraph.root());
|
|
// run the coroutine
|
|
rc_run(findMaxDepth, ThisRCS);
|
|
|
|
#endif
|
|
|
|
std::cerr << "MaxDepth: " << MaxDepth << std::endl;
|
|
std::cerr << "Iterations: " << Iterations << std::endl;
|
|
revng_check(MaxDepth == 4);
|
|
revng_check(Iterations == 7);
|
|
|
|
//
|
|
// Visit a complex graph
|
|
//
|
|
Graph G = createRandomGraph();
|
|
|
|
using namespace std::chrono;
|
|
using us = long long;
|
|
const us Repeat = 1;
|
|
us Average = 0;
|
|
|
|
for (size_t I = 0; I < Repeat; I++) {
|
|
Iterations = 0;
|
|
MaxDepth = 0;
|
|
|
|
auto Start = high_resolution_clock::now();
|
|
#ifdef ITERATIVE
|
|
|
|
std::vector<Entry> Stack;
|
|
|
|
auto *Root = G.root();
|
|
auto &Children = Root->children();
|
|
|
|
Stack.emplace_back(Entry{ Root, true, Children.begin(), Children.end() });
|
|
iterativeFindMaxDepth(Stack);
|
|
|
|
#else
|
|
|
|
std::vector<Node *> RCS;
|
|
// findMaxDepth expects the RCS to already contain the state for the first
|
|
// element
|
|
RCS.emplace_back(G.root());
|
|
// run the coroutine
|
|
rc_run(findMaxDepth, RCS);
|
|
|
|
#endif
|
|
auto End = high_resolution_clock::now();
|
|
|
|
if (I != 0) {
|
|
Average += (duration_cast<microseconds>(End - Start).count() / Repeat);
|
|
}
|
|
|
|
std::cerr << "MaxDepth: " << MaxDepth << std::endl;
|
|
std::cerr << "Iterations: " << Iterations << std::endl;
|
|
revng_check(MaxDepth == 31);
|
|
revng_check(Iterations == 1227752);
|
|
}
|
|
|
|
std::cout << "Average: " << Average << std::endl;
|
|
Average = 0LL;
|
|
|
|
for (size_t I = 0; I < Repeat; I++) {
|
|
Iterations = 0;
|
|
MaxDepth = 0;
|
|
|
|
size_t X = 0ULL;
|
|
std::set<Node *> Stack;
|
|
|
|
auto Start = high_resolution_clock::now();
|
|
#ifdef ITERATIVE
|
|
|
|
X = iterativeFindMaxRet(G.root(), Stack);
|
|
|
|
#else
|
|
|
|
X = rc_run(findMaxDepthRet, G.root(), Stack);
|
|
|
|
#endif
|
|
auto End = high_resolution_clock::now();
|
|
|
|
if (I != 0) {
|
|
Average += (duration_cast<microseconds>(End - Start).count() / Repeat);
|
|
}
|
|
|
|
revng_check(X == 34);
|
|
}
|
|
|
|
std::cout << "Average: " << Average << std::endl;
|
|
}
|