Re: FW: [PATCH] drm: should break if already get the best size

[Chunming Zhou]

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  On Behalf Of Monk Liu
> Sent: Thursday, November 22, 2018 8:33 PM
> To: amd-...@lists.freedesktop.org
> Cc: Liu, Monk 
> Subject: [PATCH] drm: should break if already get the best size
>
> Signed-off-by: Monk Liu 
> ---
>   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-...@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

FW: [PATCH] drm: should break if already get the best size

[Liu, Monk]

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 ; amd-...@lists.freedesktop.org
Subject: Re: [PATCH] drm: should break if already get the best size


Tested-by: Rex Zhu mailto:rex@amd.com>>



Without this patch, if we search node via rb tree.



For example: we insert  different node with rand size, size range in 
(1-).



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 
mailto:amd-gfx-boun...@lists.freedesktop.org>>
 on behalf of Monk Liu mailto:monk@amd.com>>
Sent: Thursday, November 22, 2018 8:33 PM
To: amd-...@lists.freedesktop.org
Cc: Liu, Monk
Subject: [PATCH] drm: should break if already get the best size

Signed-off-by: Monk Liu mailto:monk@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-...@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
amd-gfx Info Page - 
freedesktop.org
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-...@lists.freedesktop.org. You can 
subscribe to the list, or change your existing subscription, in the sections 
below.


___
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel

RE: FW: [PATCH] drm: should break if already get the best size

[Liu, Monk]

There is no checks at all in this best_hole() ... can you review the patch 
again ?

/Monk
-Original Message-
From: Chris Wilson  
Sent: Friday, November 23, 2018 5:34 PM
To: Liu, Monk ; 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

RE: FW: [PATCH] drm: should break if already get the best size

[Chris Wilson]

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

RE: FW: [PATCH] drm: should break if already get the best size

[Liu, Monk]

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  
Sent: Friday, November 23, 2018 5:03 PM
To: Liu, Monk ; 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  On Behalf Of 
> Monk Liu
> Sent: Thursday, November 22, 2018 8:33 PM
> To: amd-...@lists.freedesktop.org
> Cc: Liu, Monk 
> Subject: [PATCH] drm: should break if already get the best size
> 
> Signed-off-by: Monk Liu 
> ---
>  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

Re: FW: [PATCH] drm: should break if already get the best size

[Chris Wilson]

Quoting Liu, Monk (2018-11-23 08:02:11)
> 
> 
> -Original Message-
> From: amd-gfx  On Behalf Of Monk Liu
> Sent: Thursday, November 22, 2018 8:33 PM
> To: amd-...@lists.freedesktop.org
> Cc: Liu, Monk 
> Subject: [PATCH] drm: should break if already get the best size
> 
> Signed-off-by: Monk Liu 
> ---
>  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

FW: [PATCH] drm: should break if already get the best size

[Liu, Monk]

-Original Message-
From: amd-gfx  On Behalf Of Monk Liu
Sent: Thursday, November 22, 2018 8:33 PM
To: amd-...@lists.freedesktop.org
Cc: Liu, Monk 
Subject: [PATCH] drm: should break if already get the best size

Signed-off-by: Monk Liu 
---
 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-...@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

FW: [PATCH] drm: should break if already get the best size

[Liu, Monk]

-Original Message-
From: amd-gfx  On Behalf Of Monk Liu
Sent: Thursday, November 22, 2018 8:33 PM
To: amd-...@lists.freedesktop.org
Cc: Liu, Monk 
Subject: [PATCH] drm: should break if already get the best size

Signed-off-by: Monk Liu 
---
 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-...@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