Re: [Intel-gfx] [PATCH 1/3] drm: Track drm_mm nodes with an interval tree

From: Chris Wilson <chris@chris-wilson.co.uk>
To: Daniel Vetter <daniel@ffwll.ch>
Cc: intel-gfx@lists.freedesktop.org, dri-devel@lists.freedesktop.org
Subject: Re: [Intel-gfx] [PATCH 1/3] drm: Track drm_mm nodes with an interval tree
Date: Tue, 6 Oct 2015 12:19:43 +0100	[thread overview]
Message-ID: <20151006111943.GI26237@nuc-i3427.alporthouse.com> (raw)
In-Reply-To: <20151006111156.GH3383@phenom.ffwll.local>

On Tue, Oct 06, 2015 at 01:11:56PM +0200, Daniel Vetter wrote:
> On Tue, Oct 06, 2015 at 11:53:09AM +0100, Chris Wilson wrote:
> > In addition to the last-in/first-out stack for accessing drm_mm nodes,
> > we occasionally and in the future often want to find a drm_mm_node by an
> > address. To do so efficiently we need to track the nodes in an interval
> > tree - lookups for a particular address will then be O(lg(N)), where N
> > is the number of nodes in the range manager as opposed to O(N).
> > Insertion however gains an extra O(lg(N)) step for all nodes
> > irrespective of whether the interval tree is in use. For future i915
> > patches, eliminating the linear walk is a significant improvement.
> > 
> > Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> > Cc: dri-devel@lists.freedesktop.org
> 
> For the vma manager David Herrman put the interval tree outside of drm_mm.
> Whichever way we pick, but I think we should be consistent about this.

Given that the basis of this patch is that functionality exposed by
drm_mm (i.e. drm_mm_reserve_node) is too slow for our use case (i.e.
there is a measurable perf degradation if we switch over from the mru
stack to using fixed addresses) it makes sense to improve that
functionality. The question is then why the drm_vma_manager didn't use
and improve the existing functionality...
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/dri-devel