From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.3 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 8395 invoked from network); 6 Jul 2020 22:02:08 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 6 Jul 2020 22:02:08 -0000 Received: (qmail 9367 invoked by uid 550); 6 Jul 2020 22:02:07 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 9347 invoked from network); 6 Jul 2020 22:02:06 -0000 Date: Mon, 6 Jul 2020 18:01:54 -0400 From: Rich Felker To: musl@lists.openwall.com Message-ID: <20200706220154.GL6430@brightrain.aerifal.cx> References: <20200701185026.GA6635@voyager> <20200701204456.GI6430@brightrain.aerifal.cx> <20200701212309.5ooyvfq47sh4llwi@mae> <20200702144447.GB6635@voyager> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20200702144447.GB6635@voyager> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] Superfluous shift in qsort()? On Thu, Jul 02, 2020 at 04:44:47PM +0200, Markus Wichmann wrote: > 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[0] ^= 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[0] ^= 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. Indeed, I don't believe overflow is possible here; I just mentioned it for completeness. I think the change proposed here is correct but I'll hold off on touching it til after release since it's not fixing a bug, just a minor missed simplification. Rich