Likelihood of rt_tasks

Likelihood of rt_tasks

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 888 bytes --]

A quick question about the usefulness of making rt_task() checks 
unlikely in sched-unlikely-rt_task.patch which is in -mm

quote:

diff -puN include/linux/sched.h~sched-unlikely-rt_task include/linux/sched.h
--- 25/include/linux/sched.h~sched-unlikely-rt_task	Fri Jul  2 16:33:01 2004
+++ 25-akpm/include/linux/sched.h	Fri Jul  2 16:33:01 2004
@@ -300,7 +300,7 @@ struct signal_struct {

  #define MAX_PRIO		(MAX_RT_PRIO + 40)

-#define rt_task(p)		((p)->prio < MAX_RT_PRIO)
+#define rt_task(p)		(unlikely((p)->prio < MAX_RT_PRIO))

  /*
   * Some day this will be a full-fledged user tracking system..

---
While rt tasks are normally unlikely, what happens in the case when you 
are scheduling one or many running rt_tasks and the majority of your 
scheduling is rt? Would it be such a good idea in this setting that it 
is always hitting the slow path of branching all the time?

Con

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: Likelihood of rt_tasks

[Ingo Molnar]

* Con Kolivas <kernel@kolivas.org> wrote:

> While rt tasks are normally unlikely, what happens in the case when
> you are scheduling one or many running rt_tasks and the majority of
> your scheduling is rt? Would it be such a good idea in this setting
> that it is always hitting the slow path of branching all the time?

it's really not that big of an issue to hit the 'slow' path. And if it
is that common then the BTB of the CPU ought to cover it just fine.

	Ingo

Re: Likelihood of rt_tasks

[Peter Williams]

Con Kolivas wrote:
> A quick question about the usefulness of making rt_task() checks 
> unlikely in sched-unlikely-rt_task.patch which is in -mm
> 
> quote:
> 
> diff -puN include/linux/sched.h~sched-unlikely-rt_task 
> include/linux/sched.h
> --- 25/include/linux/sched.h~sched-unlikely-rt_task    Fri Jul  2 
> 16:33:01 2004
> +++ 25-akpm/include/linux/sched.h    Fri Jul  2 16:33:01 2004
> @@ -300,7 +300,7 @@ struct signal_struct {
> 
>  #define MAX_PRIO        (MAX_RT_PRIO + 40)
> 
> -#define rt_task(p)        ((p)->prio < MAX_RT_PRIO)
> +#define rt_task(p)        (unlikely((p)->prio < MAX_RT_PRIO))
> 
>  /*
>   * Some day this will be a full-fledged user tracking system..
> 
> ---
> While rt tasks are normally unlikely, what happens in the case when you 
> are scheduling one or many running rt_tasks and the majority of your 
> scheduling is rt? Would it be such a good idea in this setting that it 
> is always hitting the slow path of branching all the time?

Even when this isn't the case you don't want to make all rt_task() 
checks "unlikely".  In particular, during "wake up" using "unlikely" 
around rt_task() will increase the time that it takes for SCHED_FIFO 
tasks to get onto the CPU when they wake which will be bad for latency 
(which is generally important to these tasks as evidenced by several 
threads on the topic).

Peter
-- 
Peter Williams                                   pwil3058@bigpond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
  -- Ambrose Bierce

Re: Likelihood of rt_tasks

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 1815 bytes --]

Peter Williams wrote:
> Con Kolivas wrote:
> 
>> A quick question about the usefulness of making rt_task() checks 
>> unlikely in sched-unlikely-rt_task.patch which is in -mm
>>
>> quote:
>>
>> diff -puN include/linux/sched.h~sched-unlikely-rt_task 
>> include/linux/sched.h
>> --- 25/include/linux/sched.h~sched-unlikely-rt_task    Fri Jul  2 
>> 16:33:01 2004
>> +++ 25-akpm/include/linux/sched.h    Fri Jul  2 16:33:01 2004
>> @@ -300,7 +300,7 @@ struct signal_struct {
>>
>>  #define MAX_PRIO        (MAX_RT_PRIO + 40)
>>
>> -#define rt_task(p)        ((p)->prio < MAX_RT_PRIO)
>> +#define rt_task(p)        (unlikely((p)->prio < MAX_RT_PRIO))
>>
>>  /*
>>   * Some day this will be a full-fledged user tracking system..
>>
>> ---
>> While rt tasks are normally unlikely, what happens in the case when 
>> you are scheduling one or many running rt_tasks and the majority of 
>> your scheduling is rt? Would it be such a good idea in this setting 
>> that it is always hitting the slow path of branching all the time?
> 
> 
> Even when this isn't the case you don't want to make all rt_task() 
> checks "unlikely".  In particular, during "wake up" using "unlikely" 
> around rt_task() will increase the time that it takes for SCHED_FIFO 
> tasks to get onto the CPU when they wake which will be bad for latency 
> (which is generally important to these tasks as evidenced by several 
> threads on the topic).

Well I dont think making them unlikely is necessary either, but 
realistically the amount of time added by the unlikely() check will be 
immeasurably small in real terms - and hitting it frequently enough will 
be washed over by the cpu as Ingo said. I dont think the order of 
magnitude of this change is in the same universe as the problem of 
scheduling latency that people are complaining of.

Con

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: Likelihood of rt_tasks

[Peter Williams]

Con Kolivas wrote:
> Peter Williams wrote:
> 
>> Con Kolivas wrote:
>>
>>> A quick question about the usefulness of making rt_task() checks 
>>> unlikely in sched-unlikely-rt_task.patch which is in -mm
>>>
>>> quote:
>>>
>>> diff -puN include/linux/sched.h~sched-unlikely-rt_task 
>>> include/linux/sched.h
>>> --- 25/include/linux/sched.h~sched-unlikely-rt_task    Fri Jul  2 
>>> 16:33:01 2004
>>> +++ 25-akpm/include/linux/sched.h    Fri Jul  2 16:33:01 2004
>>> @@ -300,7 +300,7 @@ struct signal_struct {
>>>
>>>  #define MAX_PRIO        (MAX_RT_PRIO + 40)
>>>
>>> -#define rt_task(p)        ((p)->prio < MAX_RT_PRIO)
>>> +#define rt_task(p)        (unlikely((p)->prio < MAX_RT_PRIO))
>>>
>>>  /*
>>>   * Some day this will be a full-fledged user tracking system..
>>>
>>> ---
>>> While rt tasks are normally unlikely, what happens in the case when 
>>> you are scheduling one or many running rt_tasks and the majority of 
>>> your scheduling is rt? Would it be such a good idea in this setting 
>>> that it is always hitting the slow path of branching all the time?
>>
>>
>>
>> Even when this isn't the case you don't want to make all rt_task() 
>> checks "unlikely".  In particular, during "wake up" using "unlikely" 
>> around rt_task() will increase the time that it takes for SCHED_FIFO 
>> tasks to get onto the CPU when they wake which will be bad for latency 
>> (which is generally important to these tasks as evidenced by several 
>> threads on the topic).
> 
> 
> Well I dont think making them unlikely is necessary either,

No, just leave them unadorned.  I.e. the aim would just be to avoid the 
penalty of being on the "unlikely" path not to get special treatment.

> but 
> realistically the amount of time added by the unlikely() check will be 
> immeasurably small in real terms

It's not the time taken to do the check that's the issue. 
Unlikely/likely come with the warning that the "unlikely" path will take 
longer than it would otherwise have taken and consequently should only 
be used when you're pretty confident that your assessment of the 
likelihood is correct AND you're willing to pay a time penalty on the 
"unlikely" path whenever it is chosen.  My point is that I think that 
that penalty is unacceptable during "wake up".

> - and hitting it frequently enough will 
> be washed over by the cpu as Ingo said. I dont think the order of 
> magnitude of this change is in the same universe as the problem of 
> scheduling latency that people are complaining of.

They are talking very small times.

Peter
-- 
Peter Williams                                   pwil3058@bigpond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
  -- Ambrose Bierce

Re: Likelihood of rt_tasks

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 584 bytes --]

Peter Williams wrote:
> Con Kolivas wrote:
>> - and hitting it frequently enough will be washed over by the cpu as 
>> Ingo said. I dont think the order of magnitude of this change is in 
>> the same universe as the problem of scheduling latency that people are 
>> complaining of.
> 
> 
> They are talking very small times.

No I think you'll find some people are getting jitter and occasional 
latencies up to 50ms with rt tasks, as evidenced by Ingo's own testing. 
The problem is bigger than we'd like. Unlikely() would be pushing at 
worst not even microsecond differences.

Con

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: Likelihood of rt_tasks

[Elladan]

On Sat, Jul 10, 2004 at 09:53:22AM +1000, Peter Williams wrote:
> Con Kolivas wrote:
>
> >While rt tasks are normally unlikely, what happens in the case when you 
> >are scheduling one or many running rt_tasks and the majority of your 
> >scheduling is rt? Would it be such a good idea in this setting that it 
> >is always hitting the slow path of branching all the time?
> 
> Even when this isn't the case you don't want to make all rt_task() 
> checks "unlikely".  In particular, during "wake up" using "unlikely" 
> around rt_task() will increase the time that it takes for SCHED_FIFO 
> tasks to get onto the CPU when they wake which will be bad for latency 
> (which is generally important to these tasks as evidenced by several 
> threads on the topic).

Average wall speed of RT task wakeup isn't really an issue - the issue
is deterministic worst-case latency.  Adding a hundred cycles every time
won't cause someone to miss a deadline.  The deadlines need to be based
on the worst case, where the cache is 100% cold and you're at the
beginning of a long-held mutex section etc.

An unlikely branch won't have any measurable effect on worst-case wakeup
latency, but will reduce the average impact of the test on the common
fast path for normal processes.

I don't see how this is anything but a good idea.

-J

Re: Likelihood of rt_tasks

[Ingo Molnar]

* Con Kolivas <kernel@kolivas.org> wrote:

> Well I dont think making them unlikely is necessary either, but
> realistically the amount of time added by the unlikely() check will be
> immeasurably small in real terms - and hitting it frequently enough
> will be washed over by the cpu as Ingo said. I dont think the order of
> magnitude of this change is in the same universe as the problem of
> scheduling latency that people are complaining of.

very much so. This is (sub-)nanoseconds stuff, while the scheduling
latencies are tens of milliseconds or more - at least 7 orders of
magnitude difference.

the unlikely() check in rt_task() was mainly done because there was a
steady stream of microoptimizations that added unlikely() to rt_task().
So now we do in everywhere and have removed the unlikely()/likely()
branches from sched.c. It doesnt really matter in real-world terms, but
it will make the common case code (non-RT) a tiny bit more compact. And
i challenge anyone to be able to even measure the difference to an RT
task.

Not to mention that any truly RT-centric/embedded distribution would
compile the kernel for size anyway, at which point the compiler ignores
(or should ignore) the likely/unlikely attributes anyway. So there's
really no harm to anyone and the code got a bit more readable.

	Ingo

Re: Likelihood of rt_tasks

[Ingo Molnar]

* Elladan <elladan@eskimo.com> wrote:

> Average wall speed of RT task wakeup isn't really an issue - the issue
> is deterministic worst-case latency.  Adding a hundred cycles every time
> won't cause someone to miss a deadline. [...]

we are dealing here with about half a cycle or so overhead. (an extra
jump back to the 'likely' section) Often the BTB can even totally
eliminate the overhead. Worst-case we've got a slightly larger icache
footprint. But all in one it's not really an issue, and if you compile
for embedded it wont be done by the compiler anyway.

	Ingo

Re: Likelihood of rt_tasks

[Nick Piggin]

Ingo Molnar wrote:

> the unlikely() check in rt_task() was mainly done because there was a
> steady stream of microoptimizations that added unlikely() to rt_task().
> So now we do in everywhere and have removed the unlikely()/likely()
> branches from sched.c. It doesnt really matter in real-world terms, but
> it will make the common case code (non-RT) a tiny bit more compact. And
> i challenge anyone to be able to even measure the difference to an RT
> task.
> 

Also, the scenario where it may possibly make a tiny positive
contribution (something *very* scheduler bound) would be using
non-RT tasks I'd say.