diff options
| author | Chris Wilson <chris@chris-wilson.co.uk> | 2016-08-03 16:04:09 +0100 |
|---|---|---|
| committer | Sushmita Susheelendra <ssusheel@codeaurora.org> | 2017-05-31 17:33:09 -0600 |
| commit | 32d840be5605de0e50d5ede2a3fce5b58047bf89 (patch) | |
| tree | b2cb84cecaa4fa145833b513a6abc79e38bee03b /tools/perf/scripts/python/call-graph-from-postgresql.py | |
| parent | 9c0d1dc8c0ad47acfc0d3c2e3ea534c65e3ba3b7 (diff) | |
drm: Track drm_mm nodes with an interval tree
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.
v2: Use generic interval-tree template for u64 and faster insertion.
Change-Id: Iddcb7891480ca7d6e0469c8d394fcd1962ed4583
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: David Herrmann <dh.herrmann@gmail.com>
Cc: dri-devel@lists.freedesktop.org
Reviewed-by: David Herrmann <dh.herrmann@gmail.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/1470236651-678-1-git-send-email-chris@chris-wilson.co.uk
Git-commit: 202b52b7fbf70858609ec20829c7d69a13ffa351
Git-repo: git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Signed-off-by: Sushmita Susheelendra <ssusheel@codeaurora.org>
Diffstat (limited to 'tools/perf/scripts/python/call-graph-from-postgresql.py')
0 files changed, 0 insertions, 0 deletions