drm: should return upon the best size(v3)

Commit Message

Liu, Monk Nov. 27, 2018, 3:10 a.m. UTC

v2:
amend description:
for RB tree traveler we don't need to travel to
the bottom level if already found the equal size node,
thus the search performance can get improved.

v3:
split "<=" to "<" case and "==" case

Tested-by: Rex Zhu <[e-mail]>
Signed-off-by: Monk Liu <[e-mail]>
---
 drivers/gpu/drm/drm_mm.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

Comments

Chris Wilson Nov. 27, 2018, 9:20 a.m. UTC | #1

Quoting Monk Liu (2018-11-27 03:10:34)
> v2:
> amend description:
> for RB tree traveler we don't need to travel to
> the bottom level if already found the equal size node,
> thus the search performance can get improved.
> 
> v3:
> split "<=" to "<" case and "==" case
> 
> Tested-by: Rex Zhu <[e-mail]>
> Signed-off-by: Monk Liu <[e-mail]>

Still fundamentally broken.
-Chris

Christian König Nov. 27, 2018, 10 a.m. UTC | #2

Am 27.11.18 um 10:20 schrieb Chris Wilson:
> Quoting Monk Liu (2018-11-27 03:10:34)
>> v2:
>> amend description:
>> for RB tree traveler we don't need to travel to
>> the bottom level if already found the equal size node,
>> thus the search performance can get improved.
>>
>> v3:
>> split "<=" to "<" case and "==" case
>>
>> Tested-by: Rex Zhu <[e-mail]>
>> Signed-off-by: Monk Liu <[e-mail]>
> Still fundamentally broken.

Can you explain that further? Do we need to return the deepest hole of 
the right size because the following algorithm depends on that?

Thanks,
Christian.

> -Chris
> _______________________________________________
> dri-devel mailing list
> [e-mail]
> https://lists.freedesktop.org/mailman/listinfo/dri-devel

Christian König Nov. 27, 2018, 12:54 p.m. UTC | #3

Am 27.11.18 um 11:00 schrieb Christian König:
> Am 27.11.18 um 10:20 schrieb Chris Wilson:
>> Quoting Monk Liu (2018-11-27 03:10:34)
>>> v2:
>>> amend description:
>>> for RB tree traveler we don't need to travel to
>>> the bottom level if already found the equal size node,
>>> thus the search performance can get improved.
>>>
>>> v3:
>>> split "<=" to "<" case and "==" case
>>>
>>> Tested-by: Rex Zhu <[e-mail]>
>>> Signed-off-by: Monk Liu <[e-mail]>
>> Still fundamentally broken.
>
> Can you explain that further? Do we need to return the deepest hole of 
> the right size because the following algorithm depends on that?

Ok figured it out myself by thinking more about it.

A node with the searched size is not necessary the leftmost one, so we 
would not see all nodes with the searched size and potentially use the 
wrong one.

Sorry Monk, but Chris is right this optimization is illegal.

Regards,
Christian.

>
> Thanks,
> Christian.
>
>> -Chris
>> _______________________________________________
>> dri-devel mailing list
>> [e-mail]
>> https://lists.freedesktop.org/mailman/listinfo/dri-devel
>

Liu, Monk Nov. 27, 2018, 1:40 p.m. UTC | #4

> A node with the searched size is not necessary the leftmost one,

We may have two nodes with the same size, and the one return first will be sure *not* the leftmost one, I aware of that ...
But my question is why we need the leftmost one ? 


-----Original Message-----
From: Christian König <[e-mail]> 
Sent: Tuesday, November 27, 2018 8:54 PM
To: Chris Wilson <[e-mail]>; Liu, Monk <[e-mail]>; [e-mail]
Subject: Re: [PATCH] drm: should return upon the best size(v3)

Am 27.11.18 um 11:00 schrieb Christian König:
> Am 27.11.18 um 10:20 schrieb Chris Wilson:
>> Quoting Monk Liu (2018-11-27 03:10:34)
>>> v2:
>>> amend description:
>>> for RB tree traveler we don't need to travel to the bottom level if 
>>> already found the equal size node, thus the search performance can 
>>> get improved.
>>>
>>> v3:
>>> split "<=" to "<" case and "==" case
>>>
>>> Tested-by: Rex Zhu <[e-mail]>
>>> Signed-off-by: Monk Liu <[e-mail]>
>> Still fundamentally broken.
>
> Can you explain that further? Do we need to return the deepest hole of 
> the right size because the following algorithm depends on that?

Ok figured it out myself by thinking more about it.

A node with the searched size is not necessary the leftmost one, so we would not see all nodes with the searched size and potentially use the wrong one.

Sorry Monk, but Chris is right this optimization is illegal.

Regards,
Christian.

>
> Thanks,
> Christian.
>
>> -Chris
>> _______________________________________________
>> dri-devel mailing list
>> [e-mail]
>> https://lists.freedesktop.org/mailman/listinfo/dri-devel
>

Christian König Nov. 27, 2018, 1:48 p.m. UTC | #5

Am 27.11.18 um 14:40 schrieb Liu, Monk:
>> A node with the searched size is not necessary the leftmost one,
> We may have two nodes with the same size, and the one return first will be sure *not* the leftmost one, I aware of that ...
> But my question is why we need the leftmost one ?

Because the code is designed to iterate over all available nodes. The 
size is just the primary criteria to judge on.

If we won't return all nodes with the same size we won't necessary find 
a fitting one.

See how the code is used in drm_mm_insert_node_in_range().

Christian.

>
>
> -----Original Message-----
> From: Christian König <[e-mail]>
> Sent: Tuesday, November 27, 2018 8:54 PM
> To: Chris Wilson <[e-mail]>; Liu, Monk <[e-mail]>; [e-mail]
> Subject: Re: [PATCH] drm: should return upon the best size(v3)
>
> Am 27.11.18 um 11:00 schrieb Christian König:
>> Am 27.11.18 um 10:20 schrieb Chris Wilson:
>>> Quoting Monk Liu (2018-11-27 03:10:34)
>>>> v2:
>>>> amend description:
>>>> for RB tree traveler we don't need to travel to the bottom level if
>>>> already found the equal size node, thus the search performance can
>>>> get improved.
>>>>
>>>> v3:
>>>> split "<=" to "<" case and "==" case
>>>>
>>>> Tested-by: Rex Zhu <[e-mail]>
>>>> Signed-off-by: Monk Liu <[e-mail]>
>>> Still fundamentally broken.
>> Can you explain that further? Do we need to return the deepest hole of
>> the right size because the following algorithm depends on that?
> Ok figured it out myself by thinking more about it.
>
> A node with the searched size is not necessary the leftmost one, so we would not see all nodes with the searched size and potentially use the wrong one.
>
> Sorry Monk, but Chris is right this optimization is illegal.
>
> Regards,
> Christian.
>
>> Thanks,
>> Christian.
>>
>>> -Chris
>>> _______________________________________________
>>> dri-devel mailing list
>>> [e-mail]
>>> https://lists.freedesktop.org/mailman/listinfo/dri-devel
> _______________________________________________
> dri-devel mailing list
> [e-mail]
> https://lists.freedesktop.org/mailman/listinfo/dri-devel

Liu, Monk Nov. 27, 2018, 2:10 p.m. UTC | #6

The logic this patch change is only for "best_hole" which is only get called with " DRM_MM_INSERT_BEST", 
In drm_mm_insert_node_in_range(), is there other aspect also need calculation and judge for the mode " DRM_MM_INSERT_BEST"  ??

/Monk


-----Original Message-----
From: Christian König <[e-mail]> 
Sent: Tuesday, November 27, 2018 9:48 PM
To: Liu, Monk <[e-mail]>; Koenig, Christian <[e-mail]>; Chris Wilson <[e-mail]>; [e-mail]
Subject: Re: [PATCH] drm: should return upon the best size(v3)

Am 27.11.18 um 14:40 schrieb Liu, Monk:
>> A node with the searched size is not necessary the leftmost one,
> We may have two nodes with the same size, and the one return first will be sure *not* the leftmost one, I aware of that ...
> But my question is why we need the leftmost one ?

Because the code is designed to iterate over all available nodes. The size is just the primary criteria to judge on.

If we won't return all nodes with the same size we won't necessary find a fitting one.

See how the code is used in drm_mm_insert_node_in_range().

Christian.

>
>
> -----Original Message-----
> From: Christian König <[e-mail]>
> Sent: Tuesday, November 27, 2018 8:54 PM
> To: Chris Wilson <[e-mail]>; Liu, Monk 
> <[e-mail]>; [e-mail]
> Subject: Re: [PATCH] drm: should return upon the best size(v3)
>
> Am 27.11.18 um 11:00 schrieb Christian König:
>> Am 27.11.18 um 10:20 schrieb Chris Wilson:
>>> Quoting Monk Liu (2018-11-27 03:10:34)
>>>> v2:
>>>> amend description:
>>>> for RB tree traveler we don't need to travel to the bottom level if 
>>>> already found the equal size node, thus the search performance can 
>>>> get improved.
>>>>
>>>> v3:
>>>> split "<=" to "<" case and "==" case
>>>>
>>>> Tested-by: Rex Zhu <[e-mail]>
>>>> Signed-off-by: Monk Liu <[e-mail]>
>>> Still fundamentally broken.
>> Can you explain that further? Do we need to return the deepest hole 
>> of the right size because the following algorithm depends on that?
> Ok figured it out myself by thinking more about it.
>
> A node with the searched size is not necessary the leftmost one, so we would not see all nodes with the searched size and potentially use the wrong one.
>
> Sorry Monk, but Chris is right this optimization is illegal.
>
> Regards,
> Christian.
>
>> Thanks,
>> Christian.
>>
>>> -Chris
>>> _______________________________________________
>>> dri-devel mailing list
>>> [e-mail]
>>> https://lists.freedesktop.org/mailman/listinfo/dri-devel
> _______________________________________________
> dri-devel mailing list
> [e-mail]
> https://lists.freedesktop.org/mailman/listinfo/dri-devel

Liu, Monk Nov. 27, 2018, 2:13 p.m. UTC | #7

Oh, yeah ... I find one aspect, we need to consider "range_start" and "range_end"

Yeah, you guys are right, cool 

/Monk

-----Original Message-----
From: Liu, Monk 
Sent: Tuesday, November 27, 2018 10:10 PM
To: Koenig, Christian <[e-mail]>; Chris Wilson <[e-mail]>; [e-mail]
Subject: RE: [PATCH] drm: should return upon the best size(v3)

The logic this patch change is only for "best_hole" which is only get called with " DRM_MM_INSERT_BEST", In drm_mm_insert_node_in_range(), is there other aspect also need calculation and judge for the mode " DRM_MM_INSERT_BEST"  ??

/Monk


-----Original Message-----
From: Christian König <[e-mail]>
Sent: Tuesday, November 27, 2018 9:48 PM
To: Liu, Monk <[e-mail]>; Koenig, Christian <[e-mail]>; Chris Wilson <[e-mail]>; [e-mail]
Subject: Re: [PATCH] drm: should return upon the best size(v3)

Am 27.11.18 um 14:40 schrieb Liu, Monk:
>> A node with the searched size is not necessary the leftmost one,
> We may have two nodes with the same size, and the one return first will be sure *not* the leftmost one, I aware of that ...
> But my question is why we need the leftmost one ?

Because the code is designed to iterate over all available nodes. The size is just the primary criteria to judge on.

If we won't return all nodes with the same size we won't necessary find a fitting one.

See how the code is used in drm_mm_insert_node_in_range().

Christian.

>
>
> -----Original Message-----
> From: Christian König <[e-mail]>
> Sent: Tuesday, November 27, 2018 8:54 PM
> To: Chris Wilson <[e-mail]>; Liu, Monk 
> <[e-mail]>; [e-mail]
> Subject: Re: [PATCH] drm: should return upon the best size(v3)
>
> Am 27.11.18 um 11:00 schrieb Christian König:
>> Am 27.11.18 um 10:20 schrieb Chris Wilson:
>>> Quoting Monk Liu (2018-11-27 03:10:34)
>>>> v2:
>>>> amend description:
>>>> for RB tree traveler we don't need to travel to the bottom level if 
>>>> already found the equal size node, thus the search performance can 
>>>> get improved.
>>>>
>>>> v3:
>>>> split "<=" to "<" case and "==" case
>>>>
>>>> Tested-by: Rex Zhu <[e-mail]>
>>>> Signed-off-by: Monk Liu <[e-mail]>
>>> Still fundamentally broken.
>> Can you explain that further? Do we need to return the deepest hole 
>> of the right size because the following algorithm depends on that?
> Ok figured it out myself by thinking more about it.
>
> A node with the searched size is not necessary the leftmost one, so we would not see all nodes with the searched size and potentially use the wrong one.
>
> Sorry Monk, but Chris is right this optimization is illegal.
>
> Regards,
> Christian.
>
>> Thanks,
>> Christian.
>>
>>> -Chris
>>> _______________________________________________
>>> dri-devel mailing list
>>> [e-mail]
>>> https://lists.freedesktop.org/mailman/listinfo/dri-devel
> _______________________________________________
> dri-devel mailing list
> [e-mail]
> https://lists.freedesktop.org/mailman/listinfo/dri-devel

Patch

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index 3cc5fbd..c966610 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -315,9 +315,11 @@  static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
 		struct drm_mm_node *node =
 			rb_entry(rb, struct drm_mm_node, rb_hole_size);
 
-		if (size <= node->hole_size) {
+		if (size < node->hole_size) {
 			best = node;
 			rb = rb->rb_right;
+		} else if (size == node->hole_size) {
+			return node;
 		} else {
 			rb = rb->rb_left;
 		}