Date: Thu, 2 Jul 2020 16:44:47 +0200 From: Markus Wichmann <nullplan@....net> To: musl@...ts.openwall.com Subject: Re: Superfluous shift in qsort()? On Wed, Jul 01, 2020 at 11:23:09PM +0200, Valentin Ochs wrote: > On Wed, Jul 01, 2020 at 04:44:56PM -0400, Rich Felker wrote: > > On Wed, Jul 01, 2020 at 08:50:26PM +0200, Markus Wichmann wrote: > > > Hi all, > > > > > > I noticed something while reading code today: Near the end of qsort(), > > > we have this gem: > > > > > > shl(p, 2); > > > pshift -= 2; > > > p ^= 7; > > > shr(p, 1); > > > > > > Now, I don't know if I am missing something, but don't the shl and the > > > shr partially cancel out? Isn't this the same as > > > > > > shl(p, 1); > > > p ^= 3; > > > > > > As it is, it isn't wrong, just weird. > > > > Assuming non-overflow, I think they're equivalent (also assuming you > > keep the pshift-=2). > > Yes, it looks that way. I'm afraid I don't have any further insight - > it's been quite a while since I thought about the qsort code, and I've > not been doing much work on algorithms over the last couple of years. > The only thing I can think of is that one could figure out which > behaviour with regard to overflow in shl() should be the valid one. I > suspect that replacing it would be valid and this is some transformation > I did while implementing smoothsort without realizing that this can be > simplified. > > Cheers, > Valentin > Overflow on shl() is completely impossible. To overflow a shl(p, 2), we would need the penultimate bit in p to be set. Every bit in p stands in for a tree of that order, so if bit n is set, the heap contains a tree with a number of elements equal to the n'th Leonardo number. I don't know how big the Leonardo number corresponding to the penultimate bit is, but I do know that halfway through the upper word (wasn't the factor something like 1.44 or so?), the Leonardo numbers get too big to be contained in a machine word. Meaning that tree would be way too large to be addressed. I concur that this looks like a missed optimization opportunity, and not a deliberate design decision. Ciao, Markus
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.