halide/Halide — pull request #591 by white-pony (2014-12-15 05:41:06+00:00)
Title: Faster implementation of 'realization_order' function

Probably, this is not important (performance difference will be really subtle) for most of the real world pipelines, but complexity of the current method is *O(number_of_functions * number_of_calls)*, this PR contains algorithm which is based on DFS and it has *O(number_of_functions + number_of_calls)* complexity (in both cases complexity of map lookup is ignored).

In order to illustrate, program below takes about 30 seconds to do .compile_jit() in master and less than second in this branch.

```c++
#include

#include

using namespace Halide;

int main(int argc, char **argv) {
Var x("x");

const int N = 10000;
std::vector fs;

Func first("first");
first(x) = 0;

fs.push_back(first);

for(int ix = 0; ix < N; ix++)
{
Func f(std::to_string(N - ix));
f(x) = fs.back()(x);

fs.push_back(f);
}

fs.back().compile_jit();

return 0;
}
```
Note: it's easy to add back cycle detection assert if needed (not sure about it).

Beside that, this PR touches a little bit #460: realization order is not arbitrary anymore, it's basically depth-first order, so it tends to keep things more local, for example, for the following pipeline:
```
a(x) = 0;

b(x) = a(x) + 1;
c(x) = a(x) + 2;

b2(x) = b(x) * 2;
b3(x) = b(x) * 3;
b4(x) = b2(x) + b3(x);

c2(x) = c(x) * 2;
c3(x) = c2(x) * c2(x);

d(x) = c3(x) + b4(x);
```
it will produce:
```
a, b, b2, b3, b4, c, c2, c3, d.
```