[Intel-gfx] [PATCH 6/6] drm/i915: Store the vma in an rbtree under the object

[Chris Wilson]

On Tue, Nov 01, 2016 at 08:41:01AM +0000, Tvrtko Ursulin wrote:
> 
> On 31/10/2016 10:26, Chris Wilson wrote:
> >With full-ppgtt one of the main bottlenecks is the lookup of the VMA
> >underneath the object. For execbuf there is merit in having a very fast
> >direct lookup of ctx:handle to the vma using a hashtree, but that still
> >leaves a large number of other lookups. One way to speed up the lookup
> >would be to use a rhashtable, but that requires extra allocations and
> >may exhibit poor worse case behaviour. An alternative is to use an
> >embedded rbtree, i.e. no extra allocations and deterministic behaviour,
> >but at the slight cost of O(lgN) lookups (instead of O(1) for
> >rhashtable). The major of such tree will be very shallow and so not much
> >slower, and still scales much, much better than the current unsorted
> >list.
> >
> >References: https://bugs.freedesktop.org/show_bug.cgi?id=87726
> >Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
> 
> I suggest leaving this out of the mini-series which fixes the
> recently introduced bugs.

Just review it now, it's a two year old bug that was impacting the test
cases I was running... :-p Then we won't have to review it next week ;)
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre