Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Michel Lespinasse
Various minor optimizations in rb_erase(): - Avoid multiple loading of node->__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Michel Lespinasse
On Mon, Aug 6, 2012 at 1:58 PM, Peter Zijlstra wrote: > On Mon, 2012-08-06 at 13:50 -0700, Michel Lespinasse wrote: >> On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra wrote: >> > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> >> + /* Case 3: node's successor

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Peter Zijlstra
On Mon, 2012-08-06 at 13:50 -0700, Michel Lespinasse wrote: > On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra wrote: > > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > >> + /* Case 3: node's successor is leftmost under its > >> +* right

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Michel Lespinasse
On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra wrote: > On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: >> + /* Case 3: node's successor is leftmost under its >> +* right child subtree > > Hmm? Would 'leftmost under node's right child

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Peter Zijlstra
On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: > + /* > +* Case 2: node's successor is its right child > + /* Case 3: node's successor is leftmost under its > +* right child subtree Hmm?

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Peter Zijlstra
On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: + /* +* Case 2: node's successor is its right child + /* Case 3: node's successor is leftmost under its +* right child subtree Hmm? -- To

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Michel Lespinasse
On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra pet...@infradead.org wrote: On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: + /* Case 3: node's successor is leftmost under its +* right child subtree Hmm? Would 'leftmost under node's

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Peter Zijlstra
On Mon, 2012-08-06 at 13:50 -0700, Michel Lespinasse wrote: On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra pet...@infradead.org wrote: On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: + /* Case 3: node's successor is leftmost under its +

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Michel Lespinasse
On Mon, Aug 6, 2012 at 1:58 PM, Peter Zijlstra pet...@infradead.org wrote: On Mon, 2012-08-06 at 13:50 -0700, Michel Lespinasse wrote: On Mon, Aug 6, 2012 at 7:21 AM, Peter Zijlstra pet...@infradead.org wrote: On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote: +

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-06 Thread Michel Lespinasse
Various minor optimizations in rb_erase(): - Avoid multiple loading of node-__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-05 Thread Rik van Riel
On 08/02/2012 06:34 PM, Michel Lespinasse wrote: Various minor optimizations in rb_erase(): - Avoid multiple loading of node->__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child

Re: [PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-05 Thread Rik van Riel
On 08/02/2012 06:34 PM, Michel Lespinasse wrote: Various minor optimizations in rb_erase(): - Avoid multiple loading of node-__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child

[PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-02 Thread Michel Lespinasse
Various minor optimizations in rb_erase(): - Avoid multiple loading of node->__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field

[PATCH v2 6/9] rbtree: low level optimizations in rb_erase()

2012-08-02 Thread Michel Lespinasse
Various minor optimizations in rb_erase(): - Avoid multiple loading of node-__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field