[Intel-gfx] [PATCH 10/10] drm/i915: Improve DFS for priority inheritance

[Andi Shyti]

Hi Chris,

On Wed, Jan 20, 2021 at 12:22:05PM +0000, Chris Wilson wrote:
> The core of the scheduling algorithm is that we compute the topological
> order of the fence DAG. Knowing that we have a DAG, we should be able to
> use a DFS to compute the topological sort in linear time. However,
> during the conversion of the recursive algorithm into an iterative one,
> the memoization of how far we had progressed down a branch was

memoization?

> forgotten. The result was that instead of running in linear time, it was
> running in geometric time and could easily run for a few hundred
> milliseconds given a wide enough graph, not the microseconds as required.
> 
> Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>

I have seen this patch long time ago... I'm r-b'eing starting
from the last patch :)

Reviewed-by: Andi Shyti <andi.shyti at intel.com>

Andi