Hi 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> Thanks David _______________________________________________ dri-devel mailing list dri-devel@xxxxxxxxxxxxxxxxxxxxx http://lists.freedesktop.org/mailman/listinfo/dri-devel
