On Wed, Oct 21, 2015 at 5:14 PM, David Herrmann <dh.herrmann@xxxxxxxxx> wrote: > On Wed, Oct 21, 2015 at 5:11 PM, Daniel Vetter <daniel@xxxxxxxx> 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@xxxxxxxxxxxxxxxxxx> >>> Cc: dri-devel@xxxxxxxxxxxxxxxxxxxxx >> >> Reviewed-by: Daniel Vetter <daniel.vetter@xxxxxxxx> >> >> 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@xxxxxxxxx> 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@xxxxxxxxxxxxxxxxxxxxx http://lists.freedesktop.org/mailman/listinfo/dri-devel
