On Tue, Oct 06, 2015 at 12:19:43PM +0100, Chris Wilson wrote: > 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@xxxxxxxxxxxxxxxxxx> > > > Cc: dri-devel@xxxxxxxxxxxxxxxxxxxxx > > > > 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... Yeah I'm trying to volunteer you to add a lookup-function and rework the vma-manager ;-) -Daniel -- Daniel Vetter Software Engineer, Intel Corporation http://blog.ffwll.ch _______________________________________________ dri-devel mailing list dri-devel@xxxxxxxxxxxxxxxxxxxxx http://lists.freedesktop.org/mailman/listinfo/dri-devel
