* [PATCH] drm: should break if already get the best size
@ 2018-11-22 12:33 Monk Liu
2018-11-23 8:01 ` FW: " Liu, Monk
` (2 more replies)
0 siblings, 3 replies; 12+ messages in thread
From: Monk Liu @ 2018-11-22 12:33 UTC (permalink / raw)
To: amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW; +Cc: Monk Liu
Signed-off-by: Monk Liu <Monk.Liu@amd.com>
---
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@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
^ permalink raw reply related [flat|nested] 12+ messages in thread
* FW: [PATCH] drm: should break if already get the best size
2018-11-22 12:33 [PATCH] drm: should break if already get the best size Monk Liu
@ 2018-11-23 8:01 ` Liu, Monk
2018-11-23 8:02 ` Liu, Monk
[not found] ` <1542889986-13261-1-git-send-email-Monk.Liu-5C7GfCeVMHo@public.gmane.org>
2 siblings, 0 replies; 12+ messages in thread
From: Liu, Monk @ 2018-11-23 8:01 UTC (permalink / raw)
To: dri-devel
-----Original Message-----
From: amd-gfx <amd-gfx-bounces@lists.freedesktop.org> On Behalf Of Monk Liu
Sent: Thursday, November 22, 2018 8:33 PM
To: amd-gfx@lists.freedesktop.org
Cc: Liu, Monk <Monk.Liu@amd.com>
Subject: [PATCH] drm: should break if already get the best size
Signed-off-by: Monk Liu <Monk.Liu@amd.com>
---
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@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply [flat|nested] 12+ messages in thread
* FW: [PATCH] drm: should break if already get the best size
2018-11-22 12:33 [PATCH] drm: should break if already get the best size Monk Liu
2018-11-23 8:01 ` FW: " Liu, Monk
@ 2018-11-23 8:02 ` Liu, Monk
2018-11-23 9:03 ` Chris Wilson
2018-11-23 14:28 ` Chunming Zhou
[not found] ` <1542889986-13261-1-git-send-email-Monk.Liu-5C7GfCeVMHo@public.gmane.org>
2 siblings, 2 replies; 12+ messages in thread
From: Liu, Monk @ 2018-11-23 8:02 UTC (permalink / raw)
To: dri-devel
-----Original Message-----
From: amd-gfx <amd-gfx-bounces@lists.freedesktop.org> On Behalf Of Monk Liu
Sent: Thursday, November 22, 2018 8:33 PM
To: amd-gfx@lists.freedesktop.org
Cc: Liu, Monk <Monk.Liu@amd.com>
Subject: [PATCH] drm: should break if already get the best size
Signed-off-by: Monk Liu <Monk.Liu@amd.com>
---
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@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: FW: [PATCH] drm: should break if already get the best size
2018-11-23 8:02 ` Liu, Monk
@ 2018-11-23 9:03 ` Chris Wilson
2018-11-23 9:11 ` Liu, Monk
2018-11-23 14:28 ` Chunming Zhou
1 sibling, 1 reply; 12+ messages in thread
From: Chris Wilson @ 2018-11-23 9:03 UTC (permalink / raw)
To: Liu, Monk, dri-devel
Quoting Liu, Monk (2018-11-23 08:02:11)
>
>
> -----Original Message-----
> From: amd-gfx <amd-gfx-bounces@lists.freedesktop.org> On Behalf Of Monk Liu
> Sent: Thursday, November 22, 2018 8:33 PM
> To: amd-gfx@lists.freedesktop.org
> Cc: Liu, Monk <Monk.Liu@amd.com>
> Subject: [PATCH] drm: should break if already get the best size
>
> Signed-off-by: Monk Liu <Monk.Liu@amd.com>
> ---
> 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;
No. The point is to find the first in the chain that matches because not
every node is suitable. By not checking all best_sizes you may end up
skipping the perfect match.
-Chris
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply [flat|nested] 12+ messages in thread
* RE: FW: [PATCH] drm: should break if already get the best size
2018-11-23 9:03 ` Chris Wilson
@ 2018-11-23 9:11 ` Liu, Monk
2018-11-23 9:34 ` Chris Wilson
0 siblings, 1 reply; 12+ messages in thread
From: Liu, Monk @ 2018-11-23 9:11 UTC (permalink / raw)
To: Chris Wilson, dri-devel
What do you mean the first in the chain ? and also can you explain the " perfect match." ? thanks
Assume there is couple nodes equal to the size you requested, without this patch it will traveler to the bottom level of the RB tree and gives you
the node that close to the bottom level, which takes more time compared with break on the first node, but anyway you eventually get the node with the same size
if there is no node that equal to the size you requested, without or with my patch the logic is totally the same.
/Monk
-----Original Message-----
From: Chris Wilson <chris@chris-wilson.co.uk>
Sent: Friday, November 23, 2018 5:03 PM
To: Liu, Monk <Monk.Liu@amd.com>; dri-devel@lists.freedesktop.org
Subject: Re: FW: [PATCH] drm: should break if already get the best size
Quoting Liu, Monk (2018-11-23 08:02:11)
>
>
> -----Original Message-----
> From: amd-gfx <amd-gfx-bounces@lists.freedesktop.org> On Behalf Of
> Monk Liu
> Sent: Thursday, November 22, 2018 8:33 PM
> To: amd-gfx@lists.freedesktop.org
> Cc: Liu, Monk <Monk.Liu@amd.com>
> Subject: [PATCH] drm: should break if already get the best size
>
> Signed-off-by: Monk Liu <Monk.Liu@amd.com>
> ---
> 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;
No. The point is to find the first in the chain that matches because not every node is suitable. By not checking all best_sizes you may end up skipping the perfect match.
-Chris
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply [flat|nested] 12+ messages in thread
* RE: FW: [PATCH] drm: should break if already get the best size
2018-11-23 9:11 ` Liu, Monk
@ 2018-11-23 9:34 ` Chris Wilson
2018-11-23 9:39 ` Liu, Monk
0 siblings, 1 reply; 12+ messages in thread
From: Chris Wilson @ 2018-11-23 9:34 UTC (permalink / raw)
To: Liu, Monk, dri-devel
Quoting Liu, Monk (2018-11-23 09:11:02)
> What do you mean the first in the chain ? and also can you explain the " perfect match." ? thanks
>
> Assume there is couple nodes equal to the size you requested, without this patch it will traveler to the bottom level of the RB tree and gives you
> the node that close to the bottom level, which takes more time compared with break on the first node, but anyway you eventually get the node with the same size
Size is but of one many checks the node must pass before being returned.
-Chris
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply [flat|nested] 12+ messages in thread
* RE: FW: [PATCH] drm: should break if already get the best size
2018-11-23 9:34 ` Chris Wilson
@ 2018-11-23 9:39 ` Liu, Monk
0 siblings, 0 replies; 12+ messages in thread
From: Liu, Monk @ 2018-11-23 9:39 UTC (permalink / raw)
To: Chris Wilson, dri-devel
There is no checks at all in this best_hole() ... can you review the patch again ?
/Monk
-----Original Message-----
From: Chris Wilson <chris@chris-wilson.co.uk>
Sent: Friday, November 23, 2018 5:34 PM
To: Liu, Monk <Monk.Liu@amd.com>; dri-devel@lists.freedesktop.org
Subject: RE: FW: [PATCH] drm: should break if already get the best size
Quoting Liu, Monk (2018-11-23 09:11:02)
> What do you mean the first in the chain ? and also can you explain the
> " perfect match." ? thanks
>
> Assume there is couple nodes equal to the size you requested, without
> this patch it will traveler to the bottom level of the RB tree and
> gives you the node that close to the bottom level, which takes more
> time compared with break on the first node, but anyway you eventually
> get the node with the same size
Size is but of one many checks the node must pass before being returned.
-Chris
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] drm: should break if already get the best size
[not found] ` <1542889986-13261-1-git-send-email-Monk.Liu-5C7GfCeVMHo@public.gmane.org>
@ 2018-11-23 9:44 ` Zhu, Rex
2018-11-23 9:49 ` FW: " Liu, Monk
[not found] ` <BN7PR12MB2770EAF767A7AFC6CE0A6ADCFBD40-Zx/IyJUqfGIGZxRL2V81NwdYzm3356FpvxpqHgZTriW3zl9H0oFU5g@public.gmane.org>
0 siblings, 2 replies; 12+ messages in thread
From: Zhu, Rex @ 2018-11-23 9:44 UTC (permalink / raw)
To: Liu, Monk, amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW
[-- Attachment #1.1: Type: text/plain, Size: 2777 bytes --]
Tested-by: Rex Zhu <Rex.Zhu-5C7GfCeVMHo@public.gmane.org>
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-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org> on behalf of Monk Liu <Monk.Liu-5C7GfCeVMHo@public.gmane.org>
Sent: Thursday, November 22, 2018 8:33 PM
To: amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
Cc: Liu, Monk
Subject: [PATCH] drm: should break if already get the best size
Signed-off-by: Monk Liu <Monk.Liu-5C7GfCeVMHo@public.gmane.org>
---
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-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
amd-gfx Info Page - freedesktop.org<https://lists.freedesktop.org/mailman/listinfo/amd-gfx>
lists.freedesktop.org
To see the collection of prior postings to the list, visit the amd-gfx Archives.. Using amd-gfx: To post a message to all the list members, send email to amd-gfx-PD4FTy7X32lNgt0PjOBp9xlNPtJONSTn@public.gmane.org You can subscribe to the list, or change your existing subscription, in the sections below.
[-- Attachment #1.2: Type: text/html, Size: 8311 bytes --]
[-- Attachment #2: Type: text/plain, Size: 154 bytes --]
_______________________________________________
amd-gfx mailing list
amd-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
^ permalink raw reply related [flat|nested] 12+ messages in thread
* FW: [PATCH] drm: should break if already get the best size
2018-11-23 9:44 ` Zhu, Rex
@ 2018-11-23 9:49 ` Liu, Monk
[not found] ` <BN7PR12MB2770EAF767A7AFC6CE0A6ADCFBD40-Zx/IyJUqfGIGZxRL2V81NwdYzm3356FpvxpqHgZTriW3zl9H0oFU5g@public.gmane.org>
1 sibling, 0 replies; 12+ messages in thread
From: Liu, Monk @ 2018-11-23 9:49 UTC (permalink / raw)
To: Chris Wilson, dri-devel
[-- Attachment #1.1: Type: text/plain, Size: 3109 bytes --]
Hi Chris
Please check the sanity test of the patch from Rex
/Monk
From: Zhu, Rex
Sent: Friday, November 23, 2018 5:45 PM
To: Liu, Monk <Monk.Liu@amd.com>; amd-gfx@lists.freedesktop.org
Subject: Re: [PATCH] drm: should break if already get the best size
Tested-by: Rex Zhu <Rex.Zhu@amd.com<mailto:Rex.Zhu@amd.com>>
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@lists.freedesktop.org<mailto:amd-gfx-bounces@lists.freedesktop.org>> on behalf of Monk Liu <Monk.Liu@amd.com<mailto:Monk.Liu@amd.com>>
Sent: Thursday, November 22, 2018 8:33 PM
To: amd-gfx@lists.freedesktop.org<mailto:amd-gfx@lists.freedesktop.org>
Cc: Liu, Monk
Subject: [PATCH] drm: should break if already get the best size
Signed-off-by: Monk Liu <Monk.Liu@amd.com<mailto:Monk.Liu@amd.com>>
---
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@lists.freedesktop.org<mailto:amd-gfx@lists.freedesktop.org>
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
amd-gfx Info Page - freedesktop.org<https://lists.freedesktop.org/mailman/listinfo/amd-gfx>
lists.freedesktop.org
To see the collection of prior postings to the list, visit the amd-gfx Archives.. Using amd-gfx: To post a message to all the list members, send email to amd-gfx@lists.freedesktop.org<mailto:amd-gfx@lists.freedesktop.org>. You can subscribe to the list, or change your existing subscription, in the sections below.
[-- Attachment #1.2: Type: text/html, Size: 11845 bytes --]
[-- Attachment #2: Type: text/plain, Size: 160 bytes --]
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: FW: [PATCH] drm: should break if already get the best size
2018-11-23 8:02 ` Liu, Monk
2018-11-23 9:03 ` Chris Wilson
@ 2018-11-23 14:28 ` Chunming Zhou
1 sibling, 0 replies; 12+ messages in thread
From: Chunming Zhou @ 2018-11-23 14:28 UTC (permalink / raw)
To: dri-devel
Totally find to me, but can we change it a bit like:
if (size < node->hole_size) {
best = node;
rb = rb->rb_right;
} else if (size > node->hole_size){
rb = rb->rb_left;
} else {
break;
}
-David
在 2018/11/23 16:02, Liu, Monk 写道:
>
> -----Original Message-----
> From: amd-gfx <amd-gfx-bounces@lists.freedesktop.org> On Behalf Of Monk Liu
> Sent: Thursday, November 22, 2018 8:33 PM
> To: amd-gfx@lists.freedesktop.org
> Cc: Liu, Monk <Monk.Liu@amd.com>
> Subject: [PATCH] drm: should break if already get the best size
>
> Signed-off-by: Monk Liu <Monk.Liu@amd.com>
> ---
> 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@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/amd-gfx
> _______________________________________________
> dri-devel mailing list
> dri-devel@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/dri-devel
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] drm: should break if already get the best size
[not found] ` <BN7PR12MB2770EAF767A7AFC6CE0A6ADCFBD40-Zx/IyJUqfGIGZxRL2V81NwdYzm3356FpvxpqHgZTriW3zl9H0oFU5g@public.gmane.org>
@ 2018-11-23 19:34 ` Deucher, Alexander
[not found] ` <BN6PR12MB18098F780A02FF1CEAE32D07F7D40-/b2+HYfkarSEx6ez0IUAagdYzm3356FpvxpqHgZTriW3zl9H0oFU5g@public.gmane.org>
0 siblings, 1 reply; 12+ messages in thread
From: Deucher, Alexander @ 2018-11-23 19:34 UTC (permalink / raw)
To: Zhu, Rex, Liu, Monk, amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW
[-- Attachment #1.1: Type: text/plain, Size: 3198 bytes --]
Please add a proper patch description.
Alex
________________________________
From: amd-gfx <amd-gfx-bounces-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org> on behalf of Zhu, Rex <Rex.Zhu-5C7GfCeVMHo@public.gmane.org>
Sent: Friday, November 23, 2018 4:44:31 AM
To: Liu, Monk; amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
Subject: Re: [PATCH] drm: should break if already get the best size
Tested-by: Rex Zhu <Rex.Zhu-5C7GfCeVMHo@public.gmane.org>
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-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org> on behalf of Monk Liu <Monk.Liu-5C7GfCeVMHo@public.gmane.org>
Sent: Thursday, November 22, 2018 8:33 PM
To: amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
Cc: Liu, Monk
Subject: [PATCH] drm: should break if already get the best size
Signed-off-by: Monk Liu <Monk.Liu-5C7GfCeVMHo@public.gmane.org>
---
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-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
amd-gfx Info Page - freedesktop.org<https://lists.freedesktop.org/mailman/listinfo/amd-gfx>
lists.freedesktop.org
To see the collection of prior postings to the list, visit the amd-gfx Archives.. Using amd-gfx: To post a message to all the list members, send email to amd-gfx-PD4FTy7X32lNgt0PjOBp9xlNPtJONSTn@public.gmane.org You can subscribe to the list, or change your existing subscription, in the sections below.
[-- Attachment #1.2: Type: text/html, Size: 9279 bytes --]
[-- Attachment #2: Type: text/plain, Size: 154 bytes --]
_______________________________________________
amd-gfx mailing list
amd-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
^ permalink raw reply related [flat|nested] 12+ messages in thread
* RE: [PATCH] drm: should break if already get the best size
[not found] ` <BN6PR12MB18098F780A02FF1CEAE32D07F7D40-/b2+HYfkarSEx6ez0IUAagdYzm3356FpvxpqHgZTriW3zl9H0oFU5g@public.gmane.org>
@ 2018-11-26 7:44 ` Liu, Monk
0 siblings, 0 replies; 12+ messages in thread
From: Liu, Monk @ 2018-11-26 7:44 UTC (permalink / raw)
To: Deucher, Alexander, Zhu, Rex, amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW
[-- Attachment #1.1: Type: text/plain, Size: 4063 bytes --]
Ok, will send a v2 version with description
From: Deucher, Alexander
Sent: Saturday, November 24, 2018 3:34 AM
To: Zhu, Rex <Rex.Zhu-5C7GfCeVMHo@public.gmane.org>; Liu, Monk <Monk.Liu-5C7GfCeVMHo@public.gmane.org>; amd-gfx@lists.freedesktop.org
Subject: Re: [PATCH] drm: should break if already get the best size
Please add a proper patch description.
Alex
________________________________
From: amd-gfx <amd-gfx-bounces-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org<mailto:amd-gfx-bounces@lists.freedesktop.org>> on behalf of Zhu, Rex <Rex.Zhu-5C7GfCeVMHo@public.gmane.org<mailto:Rex.Zhu-5C7GfCeVMHo@public.gmane.org>>
Sent: Friday, November 23, 2018 4:44:31 AM
To: Liu, Monk; amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org<mailto:amd-gfx-PD4FTy7X32nrcLQh/DF6ew@public.gmane.orgop.org>
Subject: Re: [PATCH] drm: should break if already get the best size
Tested-by: Rex Zhu <Rex.Zhu-5C7GfCeVMHo@public.gmane.org<mailto:Rex.Zhu-5C7GfCeVMHo@public.gmane.org>>
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-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org<mailto:amd-gfx-bounces@lists.freedesktop.org>> on behalf of Monk Liu <Monk.Liu-5C7GfCeVMHo@public.gmane.org<mailto:Monk.Liu-5C7GfCeVMHo@public.gmane.org>>
Sent: Thursday, November 22, 2018 8:33 PM
To: amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org<mailto:amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org>
Cc: Liu, Monk
Subject: [PATCH] drm: should break if already get the best size
Signed-off-by: Monk Liu <Monk.Liu-5C7GfCeVMHo@public.gmane.org<mailto:Monk.Liu-5C7GfCeVMHo@public.gmane.org>>
---
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-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org<mailto:amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org>
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
amd-gfx Info Page - freedesktop.org<https://lists.freedesktop.org/mailman/listinfo/amd-gfx>
lists.freedesktop.org
To see the collection of prior postings to the list, visit the amd-gfx Archives.. Using amd-gfx: To post a message to all the list members, send email to amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org<mailto:amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org>. You can subscribe to the list, or change your existing subscription, in the sections below.
[-- Attachment #1.2: Type: text/html, Size: 13331 bytes --]
[-- Attachment #2: Type: text/plain, Size: 154 bytes --]
_______________________________________________
amd-gfx mailing list
amd-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
^ permalink raw reply related [flat|nested] 12+ messages in thread
end of thread, other threads:[~2018-11-26 7:44 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-11-22 12:33 [PATCH] drm: should break if already get the best size Monk Liu
2018-11-23 8:01 ` FW: " Liu, Monk
2018-11-23 8:02 ` Liu, Monk
2018-11-23 9:03 ` Chris Wilson
2018-11-23 9:11 ` Liu, Monk
2018-11-23 9:34 ` Chris Wilson
2018-11-23 9:39 ` Liu, Monk
2018-11-23 14:28 ` Chunming Zhou
[not found] ` <1542889986-13261-1-git-send-email-Monk.Liu-5C7GfCeVMHo@public.gmane.org>
2018-11-23 9:44 ` Zhu, Rex
2018-11-23 9:49 ` FW: " Liu, Monk
[not found] ` <BN7PR12MB2770EAF767A7AFC6CE0A6ADCFBD40-Zx/IyJUqfGIGZxRL2V81NwdYzm3356FpvxpqHgZTriW3zl9H0oFU5g@public.gmane.org>
2018-11-23 19:34 ` Deucher, Alexander
[not found] ` <BN6PR12MB18098F780A02FF1CEAE32D07F7D40-/b2+HYfkarSEx6ez0IUAagdYzm3356FpvxpqHgZTriW3zl9H0oFU5g@public.gmane.org>
2018-11-26 7:44 ` Liu, Monk
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.