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 ful
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 thre
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
> t
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 c
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 instructi
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" i
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 elements
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 c
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 sch
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 efficien
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.
>
> su
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 mor
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 Java
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 sam
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_yi
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 well-def
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_ent
* 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 slowin
* 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 t
__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_enti
25 matches
Mail list logo
