lkml.org 
[lkml]   [2023]   [Oct]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
SubjectRe: Re: [PATCH] sched/fair: fix pick_eevdf to always find the correct se
From
On 10/13/23 1:51 AM, Benjamin Segall Wrote:
> Abel Wu <wuyun.abel@bytedance.com> writes:
>
>> On 10/12/23 5:01 AM, Benjamin Segall Wrote:
>>> Abel Wu <wuyun.abel@bytedance.com> writes:
>>>
>>>> On 9/30/23 8:09 AM, Benjamin Segall Wrote:
>>>>> + /*
>>>>> + * Now best_left and all of its children are eligible, and we are just
>>>>> + * looking for deadline == min_deadline
>>>>> + */
>>>>> + node = &best_left->run_node;
>>>>> + while (node) {
>>>>> + struct sched_entity *se = __node_2_se(node);
>>>>> +
>>>>> + /* min_deadline is the current node */
>>>>> + if (se->deadline == se->min_deadline)
>>>>> + return se;
>>>>
>>>> IMHO it would be better tiebreak on vruntime by moving this hunk to ..
>>>>
>>>>> +
>>>>> + /* min_deadline is in the left branch */
>>>>> if (node->rb_left &&
>>>>> __node_2_se(node->rb_left)->min_deadline == se->min_deadline) {
>>>>> node = node->rb_left;
>>>>> continue;
>>>>> }
>>>>
>>>> .. here, thoughts?
>>> Yeah, that should work and be better on the tiebreak (and my test code
>>> agrees). There's an argument that the tiebreak will never really come up
>>> and it's better to avoid the potential one extra cache line from
>>> "__node_2_se(node->rb_left)->min_deadline" though.
>>
>> I see. Then probably do the same thing in the first loop?
>>
>
> We effectively do that already sorta by accident almost always -
> computing best and best_left via deadline_gt rather than gte prioritizes
> earlier elements, which always have a better vruntime.

Sorry for not clarifying clearly about the 'same thing'. What I meant
was to avoid touch left if the node itself has the min deadline.

@@ -894,6 +894,9 @@ static struct sched_entity *__pick_eevdf(struct cfs_rq *cfs_rq)
if (!best || deadline_gt(deadline, best, se))
best = se;

+ if (se->deadline == se->min_deadline)
+ break;
+
/*
* Every se in a left branch is eligible, keep track of the
* branch with the best min_deadline
@@ -913,10 +916,6 @@ static struct sched_entity *__pick_eevdf(struct cfs_rq *cfs_rq)
break;
}

- /* min_deadline is at this node, no need to look right */
- if (se->deadline == se->min_deadline)
- break;
-
/* else min_deadline is in the right branch. */
node = node->rb_right;
}
(But still thanks for the convincing explanation on fairness.)

Best,
Abel

>
> Then when we do the best_left->min_deadline vs best->deadline
> computation, we prioritize best_left, which is the one case it can be
> wrong, we'd need an additional
> "if (se->min_deadline == best->deadline &&
> (s64)(se->vruntime - best->vruntime) > 0) return best;" check at the end
> of the second loop.
>
> (Though again I don't know how much this sort of never-going-to-happen
> slight fairness improvement is worth compared to the extra bit of
> overhead)

\
 
 \ /
  Last update: 2023-10-13 05:47    [W:0.106 / U:0.440 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site