Received: by 2002:ac0:950c:0:0:0:0:0 with SMTP id f12csp3384029imc; Wed, 13 Mar 2019 17:04:33 -0700 (PDT) X-Google-Smtp-Source: APXvYqwaLL1qxSrWPYj3A5oS9dZBVwVRT6YToIwrPzONSt+++j5Bf8DQcybQHi1MiJ1WzGKjB8KN X-Received: by 2002:a62:e910:: with SMTP id j16mr46246590pfh.44.1552521873740; Wed, 13 Mar 2019 17:04:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1552521873; cv=none; d=google.com; s=arc-20160816; b=tiWgcxDs5PywPQEeFldhKNF/DKLufz935bzG/FiKIaqdEAOnuX3QWArReRxjUstFpA fQffD2KYzulTMN7w6wnxmhQ8KMyzwhdEfYUZisKtdmuVM1wtQN0+Hr5PbemFWB/oXdAL pTIJ+NqZJXBz7alkV8GdPbE6GqKuQhlHBEUraDcS2fI8tx6MXae7jKnoMFjsEuVdtYO/ s1hzPPUfc/KEBQxb7RligIatewCCFjLvw6c5D/WcABbDfNsoPRZn28He3rV8JbTmDC2a bvwTED7YmWfmh+j71PCSxeTBdjrhLG+ncu/mvSJfIEF21JpmL+IjN4H7I2uauQW7Q2yz 9jaQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:cc:subject:to :message-id:from:date; bh=1pbys9KN4I2AcmeqrOg8DEKSf0gT95497m3GWzwxa2M=; b=TQgvIEUcdfbv44d1xLNHCXGyMnpgyEJKgwvOeQLH8yQ2JdvqfoEIKWa0MRfcxGt7Fc +20Z/1hfWrrM3+XSpOoyhC1mVxibCFwskng8ya50ZJ55AFshABtaOUIEEGQsQz42cPS7 M9JD80E5ZAR6CYYe0O5Dwy8VBQ2kEaZL2eq0Q/q7Iuhc/FXvxnTv6pwrOsI0RQCUdcKR ngj07VdamgVyY0CQpZKISFobWPWfMcqMtEUn6KOVbP/JHzdpBsw2fgEXfOG/i+NKmE3X Z1f7CWlPoQ/cOjK+TzIijdUb1mBuS5kllJdIrzgvbU5ObsC6Te6Qc5kJQNQYDwYf8SP5 8m0g== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id y1si11129671pgf.32.2019.03.13.17.04.15; Wed, 13 Mar 2019 17:04:33 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726629AbfCNADz (ORCPT + 99 others); Wed, 13 Mar 2019 20:03:55 -0400 Received: from mx.sdf.org ([205.166.94.20]:51035 "EHLO mx.sdf.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726078AbfCNADz (ORCPT ); Wed, 13 Mar 2019 20:03:55 -0400 Received: from sdf.org (IDENT:lkml@sdf.lonestar.org [205.166.94.16]) by mx.sdf.org (8.15.2/8.14.5) with ESMTPS id x2E03YBx027700 (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256 bits) verified NO); Thu, 14 Mar 2019 00:03:34 GMT Received: (from lkml@localhost) by sdf.org (8.15.2/8.12.8/Submit) id x2E03VZO028625; Thu, 14 Mar 2019 00:03:31 GMT Date: Thu, 14 Mar 2019 00:03:31 GMT From: George Spelvin Message-Id: <201903140003.x2E03VZO028625@sdf.org> To: linux-kernel@vger.kernel.org, linux@rasmusvillemoes.dk, lkml@sdf.org Subject: Re: [PATCH 2/5] lib/sort: Use more efficient bottom-up heapsort variant Cc: akpm@linux-foundation.org, andriy.shevchenko@linux.intel.com, daniel.wagner@siemens.com, dchinner@redhat.com, don.mullis@gmail.com, geert@linux-m68k.org, st5pub@yandex.ru In-Reply-To: <472510ad-77f9-49e8-4122-52f447cb1c15@rasmusvillemoes.dk> References: , , <472510ad-77f9-49e8-4122-52f447cb1c15@rasmusvillemoes.dk> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Wed, 13 Mar 2019 at 23:29:40 +0100, Rasmus Villemoes wrote: > On 21/02/2019 09.21, George Spelvin wrote: >> +/** >> + * parent - given the offset of the child, find the offset of the parent. >> + * @i: the offset of the heap element whose parent is sought. Non-zero. >> + * @lsbit: a precomputed 1-bit mask, equal to "size & -size" >> + * @size: size of each element >> + * >> + * In terms of array indexes, the parent of element j = i/size is simply >> + * (j-1)/2. But when working in byte offsets, we can't use implicit >> + * truncation of integer divides. >> + * >> + * Fortunately, we only need one bit of the quotient, not the full divide. >> + * size has a least significant bit. That bit will be clear if i is >> + * an even multiple of size, and set if it's an odd multiple. >> + * >> + * Logically, we're doing "if (i & lsbit) i -= size;", but since the >> + * branch is unpredictable, it's done with a bit of clever branch-free >> + * code instead. >> + */ >> +__attribute_const__ __always_inline >> +static size_t parent(size_t i, unsigned int lsbit, size_t size) >> +{ >> + i -= size; >> + i -= size & -(i & lsbit); >> + return i / 2; >> +} >> + > > Really nice :) I had to work through this by hand, but it's solid. Thank you! Yes, the way the mask doesn't include the low-order bits that don't matter anyway is a bit subtle. When the code is subtle, use lots of comments. The entire reason for making this a separate helper function is to leave room for the large comment. >> + unsigned const lsbit = size & -size; /* Used to find parent */ > > Nit: qualifier before type, "const unsigned". And this sets ZF, so a > paranoid check for zero size (cf. the other mail) by doing "if (!lsbit) > return;" is practically free. Though it's probably a bit obscure doing > it that way... Actually, this is a personal style thing which I can ignore for the sake of the kernel, but I believe that it's better to put the qualifier *after* the type. This is due to C's pointer declaration syntax. The standard example of the issue is: typedef char *pointer; const char *a; char const *b; char * const c; const pointer d; pointer const e; Now, which variables are the same types? The answer is that a & b are the same (mutable pointer to const char), and c, d & e are the same (const pointer to mutable char). I you make a habit of putting the qualifier *after* the type, then a simple "textual substitution" mental model for the typedef works, and it's clear that c and e are the same. It's also clear that b cannot be represented by the typedef because the const is between "char" and "*", and you obviously can't do that with the typedef. But if you put the qualifier first, it's annoying to rememeber why a and d are not the same type. So I've deliberately cultivated the style of putting the qualifier after the type. But if the kernel prefers it before... >> + if (!n) >> + return; > > I'd make that n <= 1. Shouldn't be much more costly. (Actually, it's "num <= 1"; n is the pre-multiplied form so n <= 1 can only happen when sorting one one-byte value.) I actually thought about this and decided not to bother. I did it this way during development to stress the general-case code. But should I change it? === NEVER MIND === I had written a long reply justifying leaving it alone to save one instruction when the light dawned: I can do *both* tests in one step with size_t n = num * size, a = (num/2) * size; unsigned const lsbit = size & -size; /* Used to find parent */ if (!a) /* num < 2 || size == 0 */ return; So now everyone's happy. > Nice! Thank you. May I translate that into Acked-by?