Is libiberty's splay-tree.c really a splay tree?
OK, I know I'm embarrassing myself here, but is libiberty's splay-tree.c
doing the right thing for the zig-zig and zag-zag cases? The code reads:
/* Now we have the four cases of double-rotation. */
if (cmp1 < 0 && cmp2 < 0)
{
rotate_left (&n->left, c, c->left);
rotate_left (&sp->root, n, n->left);
}
else if (cmp1 > 0 && cmp2 > 0)
{
rotate_right (&n->right, c, c->right);
rotate_right (&sp->root, n, n->right);
}
else ...
whereas I thought you were supposed to rotate on the root first
for these cases. E.g. instead of:
X YZ
/ \ / \ / \
Y DZ X A Y
/ \ / \ / \ / \
Z C ---> A B C D --->B X
/ \/ \
A B C D
the above seems to implement:
X XZ
/ \ / \ / \
Y D Z DA X
/ \ / \ / \
Z C ---> A Y > Y D
/ \ / \ / \
A B B CB C
(The other two cases seem fine.)
Richard
Re: Is libiberty's splay-tree.c really a splay tree?
On Mon, Jul 4, 2011 at 2:23 PM, Richard Sandiford
wrote:
> OK, I know I'm embarrassing myself here, but is libiberty's splay-tree.c
> doing the right thing for the zig-zig and zag-zag cases? The code reads:
>
> /* Now we have the four cases of double-rotation. */
> if (cmp1 < 0 && cmp2 < 0)
> {
> rotate_left (&n->left, c, c->left);
> rotate_left (&sp->root, n, n->left);
> }
> else if (cmp1 > 0 && cmp2 > 0)
> {
> rotate_right (&n->right, c, c->right);
> rotate_right (&sp->root, n, n->right);
> }
> else ...
>
> whereas I thought you were supposed to rotate on the root first
> for these cases. E.g. instead of:
>
> X Y Z
> / \ / \ / \
> Y D Z X A Y
> / \ / \ / \ / \
> Z C ---> A B C D ---> B X
> / \ / \
> A B C D
>
> the above seems to implement:
>
> X X Z
> / \ / \ / \
> Y D Z D A X
> / \ / \ / \
> Z C ---> A Y > Y D
> / \ / \ / \
> A B B C B C
>
> (The other two cases seem fine.)
There were other people pointing out issues with the splay tree
(but all w/o copyright assignment and much larger patches).
I know I did the last re-write of this piece of code but it's been
a long time ... in any case, previous reports were that the
current implementation degenerates in some cases.
So yes, it could be that there is a bug ...
Richard.
> Richard
>
Re: Validity of __asm__ transformation with "m" reference
Hi, On Fri, 1 Jul 2011, Jakub Jelinek wrote: > > GCC turns this into: > > "movaps%0, %%xmm0 > > shufps$27, %%xmm0, %%xmm0 > > movaps%1, %%xmm5 > > movaps%%xmm5, %%xmm6 > > " : : "m" costab_mmx[24], *"m" -2147483648*); > > > > The new constant might end up in an unaligned address causing the > > program to segfault on Intel platforms. > > But you said the operand is an int sized memory, while you expect > 4 times as big data with different alignment. > So you want "m"(*(__m128d *)) (or "m"(*(__m128i *)) ). Right. But even then the replacement of a memory location with a constant seems useless in an asm operand whose constraint requires memory. The only thing that we get out of this is some shuffling between the old and some temporary memory. Ciao, Michael.
Re: Is libiberty's splay-tree.c really a splay tree?
Hi, On Mon, 4 Jul 2011, Richard Guenther wrote: > There were other people pointing out issues with the splay tree (but all > w/o copyright assignment and much larger patches). > > I know I did the last re-write of this piece of code but it's been a > long time ... in any case, previous reports were that the current > implementation degenerates in some cases. And I also distinctly remember some actual measurements where our current non-splay-tree is faster for a bootstrap (or similar testcases) than a real splay tree. Couple years ago, on this list. Ciao, Michael.
Re: Validity of __asm__ transformation with "m" reference
On Mon, Jul 04, 2011 at 03:49:58PM +0200, Michael Matz wrote:
> > But you said the operand is an int sized memory, while you expect
> > 4 times as big data with different alignment.
> > So you want "m"(*(__m128d *)) (or "m"(*(__m128i *)) ).
>
> Right. But even then the replacement of a memory location with a constant
> seems useless in an asm operand whose constraint requires memory. The
> only thing that we get out of this is some shuffling between the old and
> some temporary memory.
No, what you can get out of that is e.g. optimizing away otherwise unneeded
large variable.
Consider:
static const int i[131072] = { 1, 2, 3, 4, 5 };
void foo (void)
{
__asm volatile ("" : : "m" (i[0]));
}
By giving the asm just address of an const int 1 instead of the whole array
you can optimize the large array away.
Jakub
Re: Is libiberty's splay-tree.c really a splay tree?
Hi, On Mon, 4 Jul 2011, Michael Matz wrote: > > There were other people pointing out issues with the splay tree (but > > all w/o copyright assignment and much larger patches). > > > > I know I did the last re-write of this piece of code but it's been a > > long time ... in any case, previous reports were that the current > > implementation degenerates in some cases. > > And I also distinctly remember some actual measurements where our > current non-splay-tree is faster for a bootstrap (or similar testcases) > than a real splay tree. Couple years ago, on this list. Referenced from: http://gcc.gnu.org/ml/gcc/2006-10/msg00616.html Basically the reimplementation of richi (r106584) improved on the benchmarks (the former implementation was fairly bogus). The one from Brian Makin with some changes by Ian Barnes was only slightly better (and without copyright assignment). So it's very well possible that Richi doesn't rotate in optimal order. I think it's harmless for the average O(log n) invariants of a splay tree. Try some benchmarks :) Ciao, Michael.
Re: Validity of __asm__ transformation with "m" reference
Hi,
On Mon, 4 Jul 2011, Jakub Jelinek wrote:
> No, what you can get out of that is e.g. optimizing away otherwise unneeded
> large variable.
> Consider:
> static const int i[131072] = { 1, 2, 3, 4, 5 };
> void foo (void)
> {
> __asm volatile ("" : : "m" (i[0]));
> }
> By giving the asm just address of an const int 1 instead of the whole array
> you can optimize the large array away.
Hmm, that's right. If that happens often. As soon as you use the same
element multiple times you'll offset some of the potential savings. I
guess we don't take this into account, so I'm not sure if that reason is
very convincing.
Ciao,
Michael.
[pph] Running a single test in pph.exp
So, I thought this was not working, but it is: $ make check-g++ RUNTESTFLAGS=pph.exp='c1eabi1.*' will run all the tests for c1eabi1.cc and c1eabi1.h. Diego.
Re: Long paths with ../../../../ throughout
Ian Lance Taylor wrote, On 03/07/11 05:27: Jon Grant writes: [.] Another reply for this old thread. I wondered, if collect2 is possibly not needed in normal use on GNU/Linux, could GCC be configured to call ld directly in those cases to save launching another binary. collect2 is needed if you use -frepo or -flto. Hi Ian. Not sure how easy this is, but could those options simply be checked to determine if the linker could be called directly? Would save launching collect2 then, to speed up builds a bit! Best regards, Jon
Re: Validity of __asm__ transformation with "m" reference
Jakub Jelinek wrote:
> On Mon, Jul 04, 2011 at 03:49:58PM +0200, Michael Matz wrote:
>> > But you said the operand is an int sized memory, while you expect
>> > 4 times as big data with different alignment.
>> > So you want "m"(*(__m128d *)) (or "m"(*(__m128i *)) ).
>>
>> Right. But even then the replacement of a memory location with a
>> constant
>> seems useless in an asm operand whose constraint requires memory. The
>> only thing that we get out of this is some shuffling between the old and
>> some temporary memory.
I commented on http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46615
about how I patched the mpeg2dec package in mandriva.
> No, what you can get out of that is e.g. optimizing away otherwise
> unneeded
> large variable.
> Consider:
> static const int i[131072] = { 1, 2, 3, 4, 5 };
> void foo (void)
> {
> __asm volatile ("" : : "m" (i[0]));
> }
> By giving the asm just address of an const int 1 instead of the whole
> array
> you can optimize the large array away.
The solution I used was to not declare the vector as const. It
probably is a fragile solution, but at the moment I considered
safer than attempting to patch the asm, and inserting bugs on
code I do not fully understand.
> Jakub
Paulo
