Jens Axboe wrote:
> On Thu, Feb 21 2008, Jens Axboe wrote:
>> On Thu, Feb 21 2008, Peter Zijlstra wrote:
>>> On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
>>>
You use the empty pointer (missing right child), so why do we need a list.
May
be I am missing something.
>>> A
On Thu, Feb 21 2008, Jens Axboe wrote:
> On Thu, Feb 21 2008, Peter Zijlstra wrote:
> >
> > On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
> >
> > > You use the empty pointer (missing right child), so why do we need a
> > > list. May
> > > be I am missing something.
> >
> > A fully
On Thu, Feb 21 2008, Peter Zijlstra wrote:
>
> On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
>
> > You use the empty pointer (missing right child), so why do we need a list.
> > May
> > be I am missing something.
>
> A fully threaded tree also has back-pointer to traverse backwards
>
On Thu, 21 February 2008 12:21:33 +0530, Balbir Singh wrote:
>
> For a large number of tasks - say 1, we need to walk 14 levels before we
16.7, actually. rbtrees are balanced treed, but they are not balanced
binary trees. The average fan-out is sqrt(3) instead of 2.
Jörn
--
The cost of
Mike Galbraith wrote:
> Hi,
>
> On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
>> Ingo Molnar wrote:
>>> * Balbir Singh <[EMAIL PROTECTED]> wrote:
>>>
If you insist that sched_yield() is bad, I might agree, but how does
my patch make things worse. [...]
>>> it puts new
On Thu, 2008-02-21 at 13:02 +0100, Mike Galbraith wrote:
> sched_cycles: 7198444348 unpatched
> vs
> sched_cycles: 8574036268 patched
(in case it's not clear, patched means your patch, not my quick/dirty
countem patch:)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel"
Hi,
On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
> Ingo Molnar wrote:
> > * Balbir Singh <[EMAIL PROTECTED]> wrote:
> >
> >> If you insist that sched_yield() is bad, I might agree, but how does
> >> my patch make things worse. [...]
> >
> > it puts new instructions into the hotpath.
Peter Zijlstra wrote:
> On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
>
>> You use the empty pointer (missing right child), so why do we need a list.
>> May
>> be I am missing something.
>
> A fully threaded tree also has back-pointer to traverse backwards
> through the ordered
On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
> You use the empty pointer (missing right child), so why do we need a list. May
> be I am missing something.
A fully threaded tree also has back-pointer to traverse backwards
through the ordered elements.
That said, overloading the right
Balbir Singh wrote:
> Ingo Molnar wrote:
>> * Balbir Singh <[EMAIL PROTECTED]> wrote:
>>
>>> If you insist that sched_yield() is bad, I might agree, but how does
>>> my patch make things worse. [...]
>> it puts new instructions into the hotpath.
>>
>>> [...] In my benchmarks, it has helped the
Peter Zijlstra wrote:
> On Thu, 2008-02-21 at 15:12 +0530, Balbir Singh wrote:
>> Peter Zijlstra wrote:
>>> On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
>>>
I have an alternate approach in mind (that I need to find time for),
threaded-rbtrees. Walking the tree is really
On Thu, 2008-02-21 at 15:12 +0530, Balbir Singh wrote:
> Peter Zijlstra wrote:
> > On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
> >
> >> I have an alternate approach in mind (that I need to find time for),
> >> threaded-rbtrees. Walking the tree is really efficient, specially finding
>
Ingo Molnar wrote:
> * Balbir Singh <[EMAIL PROTECTED]> wrote:
>
You did not answer some of my earlier questions.
>> I have an alternate approach in mind (that I need to find time for),
>> threaded-rbtrees. Walking the tree is really efficient, specially
>> finding successor of a node.
>
>
Peter Zijlstra wrote:
> On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
>
>> I have an alternate approach in mind (that I need to find time for),
>> threaded-rbtrees. Walking the tree is really efficient, specially finding
>> successor of a node.
>
> Threading the rbtrees would be even
On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
> I have an alternate approach in mind (that I need to find time for),
> threaded-rbtrees. Walking the tree is really efficient, specially finding
> successor of a node.
Threading the rbtrees would be even more expensive, it would require a
* Balbir Singh <[EMAIL PROTECTED]> wrote:
> I have an alternate approach in mind (that I need to find time for),
> threaded-rbtrees. Walking the tree is really efficient, specially
> finding successor of a node.
sure, feel free to experiment with those details.
But if you want to improve
Ingo Molnar wrote:
> * Balbir Singh <[EMAIL PROTECTED]> wrote:
>
>> If you insist that sched_yield() is bad, I might agree, but how does
>> my patch make things worse. [...]
>
> it puts new instructions into the hotpath.
>
>> [...] In my benchmarks, it has helped the sched_yield case, why is
* Balbir Singh <[EMAIL PROTECTED]> wrote:
> If you insist that sched_yield() is bad, I might agree, but how does
> my patch make things worse. [...]
it puts new instructions into the hotpath.
> [...] In my benchmarks, it has helped the sched_yield case, why is
> that bad? [...]
I had the
Peter Zijlstra wrote:
> On Thu, 2008-02-21 at 13:09 +0530, Balbir Singh wrote:
>
>> sched_yield() is supported API
>
> For SCHED_FIFO/SCHED_RR.
>
>> and also look at http://lkml.org/lkml/2007/9/19/351.
>
> Read on (http://lkml.org/lkml/2007/9/19/371) and find:
>
> The
On Thu, 2008-02-21 at 13:09 +0530, Balbir Singh wrote:
> sched_yield() is supported API
For SCHED_FIFO/SCHED_RR.
> and also look at http://lkml.org/lkml/2007/9/19/351.
Read on (http://lkml.org/lkml/2007/9/19/371) and find:
The sched_yield() behaviour is actually very
On Thu, 2008-02-21 at 13:09 +0530, Balbir Singh wrote:
sched_yield() is supported API
For SCHED_FIFO/SCHED_RR.
and also look at http://lkml.org/lkml/2007/9/19/351.
Read on (http://lkml.org/lkml/2007/9/19/371) and find:
The sched_yield() behaviour is actually very
Peter Zijlstra wrote:
On Thu, 2008-02-21 at 13:09 +0530, Balbir Singh wrote:
sched_yield() is supported API
For SCHED_FIFO/SCHED_RR.
and also look at http://lkml.org/lkml/2007/9/19/351.
Read on (http://lkml.org/lkml/2007/9/19/371) and find:
The sched_yield()
* Balbir Singh [EMAIL PROTECTED] wrote:
If you insist that sched_yield() is bad, I might agree, but how does
my patch make things worse. [...]
it puts new instructions into the hotpath.
[...] In my benchmarks, it has helped the sched_yield case, why is
that bad? [...]
I had the same
Ingo Molnar wrote:
* Balbir Singh [EMAIL PROTECTED] wrote:
If you insist that sched_yield() is bad, I might agree, but how does
my patch make things worse. [...]
it puts new instructions into the hotpath.
[...] In my benchmarks, it has helped the sched_yield case, why is
that bad?
* Balbir Singh [EMAIL PROTECTED] wrote:
I have an alternate approach in mind (that I need to find time for),
threaded-rbtrees. Walking the tree is really efficient, specially
finding successor of a node.
sure, feel free to experiment with those details.
But if you want to improve Java
On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
I have an alternate approach in mind (that I need to find time for),
threaded-rbtrees. Walking the tree is really efficient, specially finding
successor of a node.
Threading the rbtrees would be even more expensive, it would require a
Ingo Molnar wrote:
* Balbir Singh [EMAIL PROTECTED] wrote:
You did not answer some of my earlier questions.
I have an alternate approach in mind (that I need to find time for),
threaded-rbtrees. Walking the tree is really efficient, specially
finding successor of a node.
sure, feel
Peter Zijlstra wrote:
On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
I have an alternate approach in mind (that I need to find time for),
threaded-rbtrees. Walking the tree is really efficient, specially finding
successor of a node.
Threading the rbtrees would be even more
On Thu, 2008-02-21 at 15:12 +0530, Balbir Singh wrote:
Peter Zijlstra wrote:
On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
I have an alternate approach in mind (that I need to find time for),
threaded-rbtrees. Walking the tree is really efficient, specially finding
successor
Peter Zijlstra wrote:
On Thu, 2008-02-21 at 15:12 +0530, Balbir Singh wrote:
Peter Zijlstra wrote:
On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
I have an alternate approach in mind (that I need to find time for),
threaded-rbtrees. Walking the tree is really efficient, specially
Balbir Singh wrote:
Ingo Molnar wrote:
* Balbir Singh [EMAIL PROTECTED] wrote:
If you insist that sched_yield() is bad, I might agree, but how does
my patch make things worse. [...]
it puts new instructions into the hotpath.
[...] In my benchmarks, it has helped the sched_yield case, why
On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
You use the empty pointer (missing right child), so why do we need a list. May
be I am missing something.
A fully threaded tree also has back-pointer to traverse backwards
through the ordered elements.
That said, overloading the right
Peter Zijlstra wrote:
On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
You use the empty pointer (missing right child), so why do we need a list.
May
be I am missing something.
A fully threaded tree also has back-pointer to traverse backwards
through the ordered elements.
The
Hi,
On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
Ingo Molnar wrote:
* Balbir Singh [EMAIL PROTECTED] wrote:
If you insist that sched_yield() is bad, I might agree, but how does
my patch make things worse. [...]
it puts new instructions into the hotpath.
[...] In my
On Thu, 2008-02-21 at 13:02 +0100, Mike Galbraith wrote:
sched_cycles: 7198444348 unpatched
vs
sched_cycles: 8574036268 patched
(in case it's not clear, patched means your patch, not my quick/dirty
countem patch:)
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
Mike Galbraith wrote:
Hi,
On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote:
Ingo Molnar wrote:
* Balbir Singh [EMAIL PROTECTED] wrote:
If you insist that sched_yield() is bad, I might agree, but how does
my patch make things worse. [...]
it puts new instructions into the hotpath.
On Thu, 21 February 2008 12:21:33 +0530, Balbir Singh wrote:
For a large number of tasks - say 1, we need to walk 14 levels before we
16.7, actually. rbtrees are balanced treed, but they are not balanced
binary trees. The average fan-out is sqrt(3) instead of 2.
Jörn
--
The cost of
On Thu, Feb 21 2008, Peter Zijlstra wrote:
On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
You use the empty pointer (missing right child), so why do we need a list.
May
be I am missing something.
A fully threaded tree also has back-pointer to traverse backwards
through the
On Thu, Feb 21 2008, Jens Axboe wrote:
On Thu, Feb 21 2008, Peter Zijlstra wrote:
On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
You use the empty pointer (missing right child), so why do we need a
list. May
be I am missing something.
A fully threaded tree also has
Jens Axboe wrote:
On Thu, Feb 21 2008, Jens Axboe wrote:
On Thu, Feb 21 2008, Peter Zijlstra wrote:
On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote:
You use the empty pointer (missing right child), so why do we need a list.
May
be I am missing something.
A fully threaded tree also
Ingo Molnar wrote:
> * Balbir Singh <[EMAIL PROTECTED]> wrote:
>
>> I disagree. The cost is only adding a field to cfs_rq [...]
>
> wrong. The cost is "only" of adding a field to cfs_rq and _updating it_,
> in the hottest paths of the scheduler:
>
> @@ -256,6 +257,7 @@ static void
* Balbir Singh <[EMAIL PROTECTED]> wrote:
> I disagree. The cost is only adding a field to cfs_rq [...]
wrong. The cost is "only" of adding a field to cfs_rq and _updating it_,
in the hottest paths of the scheduler:
@@ -256,6 +257,7 @@ static void __enqueue_entity(struct cfs_
Ingo Molnar wrote:
> * Balbir Singh <[EMAIL PROTECTED]> wrote:
>
>> __pick_last_entity() walks the entire tree on O(lgn) time to find the
>> rightmost entry. This patch makes the routine more efficient by
>> reducing the cost of the lookup
>
> hm, i'm not sure we want to do this: we'd be
* Balbir Singh <[EMAIL PROTECTED]> wrote:
> __pick_last_entity() walks the entire tree on O(lgn) time to find the
> rightmost entry. This patch makes the routine more efficient by
> reducing the cost of the lookup
hm, i'm not sure we want to do this: we'd be slowing down the fastpath
of all
__pick_last_entity() walks the entire tree on O(lgn) time to find the
rightmost entry. This patch makes the routine more efficient by
reducing the cost of the lookup
Description
---
Cache the rightmost entry in the rb_tree in the same way that we cache
the leftmost entry.
__pick_last_entity() walks the entire tree on O(lgn) time to find the
rightmost entry. This patch makes the routine more efficient by
reducing the cost of the lookup
Description
---
Cache the rightmost entry in the rb_tree in the same way that we cache
the leftmost entry.
* Balbir Singh [EMAIL PROTECTED] wrote:
__pick_last_entity() walks the entire tree on O(lgn) time to find the
rightmost entry. This patch makes the routine more efficient by
reducing the cost of the lookup
hm, i'm not sure we want to do this: we'd be slowing down the fastpath
of all the
Ingo Molnar wrote:
* Balbir Singh [EMAIL PROTECTED] wrote:
__pick_last_entity() walks the entire tree on O(lgn) time to find the
rightmost entry. This patch makes the routine more efficient by
reducing the cost of the lookup
hm, i'm not sure we want to do this: we'd be slowing down the
* Balbir Singh [EMAIL PROTECTED] wrote:
I disagree. The cost is only adding a field to cfs_rq [...]
wrong. The cost is only of adding a field to cfs_rq and _updating it_,
in the hottest paths of the scheduler:
@@ -256,6 +257,7 @@ static void __enqueue_entity(struct cfs_
*/
Ingo Molnar wrote:
* Balbir Singh [EMAIL PROTECTED] wrote:
I disagree. The cost is only adding a field to cfs_rq [...]
wrong. The cost is only of adding a field to cfs_rq and _updating it_,
in the hottest paths of the scheduler:
@@ -256,6 +257,7 @@ static void __enqueue_entity(struct
50 matches
Mail list logo
