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

From: Daniel Vetter <daniel@ffwll.ch>
To: David Herrmann <dh.herrmann@gmail.com>
Cc: Intel Graphics Development <intel-gfx@lists.freedesktop.org>,
	"dri-devel@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: Thu, 22 Oct 2015 10:07:16 +0200	[thread overview]
Message-ID: <CAKMK7uHMUA_hqKW88KGZ5yhrVoVK6=7oixCxmnmNdf97yer-dA@mail.gmail.com> (raw)
In-Reply-To: <CANq1E4Q0oxMx4t0ATvu6HZbAkL7t4f-1EHE=GVrRB6uzqzBFQA@mail.gmail.com>

On Wed, Oct 21, 2015 at 5:14 PM, David Herrmann <dh.herrmann@gmail.com> wrote:
> On Wed, Oct 21, 2015 at 5:11 PM, Daniel Vetter <daniel@ffwll.ch> 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
>>
>> Reviewed-by: Daniel Vetter <daniel.vetter@ffwll.ch>
>>
>> I guess for simpler merge ordering we can just pull this into drm-intel
>> and patch up the vma manager (just need to drop a lot of code and adjust
>> the search to use the drm_mm internal_tree nodes) later on.
>
> Agreed.
>
> Acked-by: David Herrmann <dh.herrmann@gmail.com>

Also has Dave's irc-ack for pushing through drm-intel.
-Daniel
-- 
Daniel Vetter
Software Engineer, Intel Corporation
+41 (0) 79 365 57 48 - http://blog.ffwll.ch
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/dri-devel