|
Tested-by: Rex Zhu <Rex.Zhu@xxxxxxx>
Without this patch, if we search node via rb tree.
For example: we insert 9999 different node with rand size, size range in (1-9999).
the key in root node is 5587.
if we try to find the node with key equal to 5587 or 7381,
Loop:
node->key is 5587 node->key is 2273 node->key is 3706 node->key is 4892 node->key is 5296 node->key is 5461 node->key is 5519 node->key is 5549 node->key is 5570 node->key is 5581 node->key is 5584 node->key is 5585 node->key is 5586 node->key is 5586
Find the best node, key is 5587
(Loop 14 levels)
Loop:
node->key is 5587 node->key is 7381 node->key is 6474 node->key is 7034 node->key is 7228 node->key is 7314 node->key is 7339 node->key is 7349 node->key is 7372 node->key is 7377 node->key is 7378 node->key is 7379 node->key is 7379 find the best node, key is 7381. (Loop 13 levels) With this patch: we don't need to go down if we found the right node that size equal to we needed.
Best Regards Rex
From: amd-gfx <amd-gfx-bounces@xxxxxxxxxxxxxxxxxxxxx> on behalf of Monk Liu <Monk.Liu@xxxxxxx>
Sent: Thursday, November 22, 2018 8:33 PM To: amd-gfx@xxxxxxxxxxxxxxxxxxxxx Cc: Liu, Monk Subject: [PATCH] drm: should break if already get the best size Signed-off-by: Monk Liu <Monk.Liu@xxxxxxx>
--- drivers/gpu/drm/drm_mm.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 3cc5fbd..369fd9b 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -318,6 +318,8 @@ static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size) if (size <= node->hole_size) { best = node; rb = rb->rb_right; + if (size == node->hole_size) + break; } else { rb = rb->rb_left; } -- 2.7.4 _______________________________________________ amd-gfx mailing list amd-gfx@xxxxxxxxxxxxxxxxxxxxx https://lists.freedesktop.org/mailman/listinfo/amd-gfx
| ||
_______________________________________________ amd-gfx mailing list amd-gfx@xxxxxxxxxxxxxxxxxxxxx https://lists.freedesktop.org/mailman/listinfo/amd-gfx
