Received: by 2002:ac0:a874:0:0:0:0:0 with SMTP id c49csp233109ima; Fri, 15 Mar 2019 01:22:13 -0700 (PDT) X-Google-Smtp-Source: APXvYqz3Y41o4+lMLRDM9zdoH8/WsKWcpp2N+xzYdpN8cyRvXxBE3vHTRBLYqKVgNZPl3YTQziJq X-Received: by 2002:a17:902:b617:: with SMTP id b23mr2811424pls.200.1552638133868; Fri, 15 Mar 2019 01:22:13 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1552638133; cv=none; d=google.com; s=arc-20160816; b=odhD80lchz0fBsJr6mPAjN8VJr3vqbaAzzkTFAwI6T2Uv1erGtwaIykx8xpWGfqadx hIGKljwWGgqsBYY9QZJZgK1fduKNrSBsiHEQYc5dcq+HaVBI6fkq4uSk1mIsT1zmySvd pJtNkWlRblZvL5GBeTKY80AmswRjXDTfUAR4ePO3uaoPwEQW9wHQmCR5Rdqgiu/Xq1k6 E4dJqConkz7IHI8YAZlBCgzUguB/EU5EUxY9ThphLbCHwuL/3j0vZxdofdGIxhoYinSh 0rgPELzQsCQ3XJ15d0Y8lztNouvzNQNEBpAc1WrMewz7OK3yodBHbG7ZS72/dORE7C9c Zpwg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:content-transfer-encoding:cc:to:subject :message-id:date:from:in-reply-to:references:mime-version; bh=JF19OxokZx2mwizQRVgf6Qp65/IMhMWDh2O7Zqzi20g=; b=kgHcZl9yTbotiBcd4OgkG58SpXtoTC/E27s2l4SSx7TKqoTEkO1ph82tX76FTIxSqG vi0+RYVYKFyaVnhiiJ3tZHQZlMsvmUtqQWgjY3bGyj+njaCaHZXoAIs/3Emw5RQ3TePY qAbkqkKy118iLfCa9w+8JhyhoeB6HkkkOJpCpQe2CZo2U2URHb4CBsHa+3Wk+sQCLxg1 yRx3MsFR9IwALKqIuZOTn3HT+E/+WuJh0o5BBtOouNnfIJG7Sa7Tg9cZb5rRYDpzvi75 hWhrdEElIwltKTnMVCnnpQ2kol2IAe786rUKIPwX4YmCoPkYyE47UBm+FuFL3TJ19grV JPLg== 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 73si1269186pgb.250.2019.03.15.01.21.59; Fri, 15 Mar 2019 01:22:13 -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 S1727282AbfCOIVL convert rfc822-to-8bit (ORCPT + 99 others); Fri, 15 Mar 2019 04:21:11 -0400 Received: from mail-vs1-f67.google.com ([209.85.217.67]:34154 "EHLO mail-vs1-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726584AbfCOIVL (ORCPT ); Fri, 15 Mar 2019 04:21:11 -0400 Received: by mail-vs1-f67.google.com with SMTP id e126so4672549vse.1 for ; Fri, 15 Mar 2019 01:21:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=nfllzvU4LySFmRQhIlKP42JxfvqsqpZKDJK6PX4JQIo=; b=ljs9JxTCIAJP294FqE8GewVs1h3+lzFY9DGbmV4QPEwsX/77giPCVJL2zKzo2dzfu4 1+xWqfl2MvzhrLl7ip2bzJmw2/8erzL+aMu4ZDBZex88gsGQidaOhYYwc/nKqs4F/cUh Yoa2NiEuDICIAIjfvK6Bdp8jBr0S9gPZD4zMktcz2DL8J7KaMxoADVI72h+6n79YZmKR yk+0vDldbQLDySYqo0RDs/lmHceOe9mfpQvP6ANKs3O39uH9nVov+oDheaVKFW9Im5Go qQaLRvZOJQEd9ufiyfuqs/UzO5sTQ0vJNBMtD04jeHs9vyicPH3lNtNi4PoOEXNUc952 Lqvg== X-Gm-Message-State: APjAAAWVnIgZOUmMZR9dwXkEesNNRb5Oehlu+srAohij8VML3uWpIha+ m7PGGiPGwhrX1ZJnHGlKALDx9A0XTruNFQyhwJw= X-Received: by 2002:a67:8588:: with SMTP id h130mr1256899vsd.11.1552638069743; Fri, 15 Mar 2019 01:21:09 -0700 (PDT) MIME-Version: 1.0 References: <20190314091041.GU9224@smile.fi.intel.com> <201903150433.x2F4X9oT024601@sdf.org> In-Reply-To: <201903150433.x2F4X9oT024601@sdf.org> From: Geert Uytterhoeven Date: Fri, 15 Mar 2019 09:20:58 +0100 Message-ID: Subject: Re: [PATCH 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS To: George Spelvin Cc: Andy Shevchenko , Andrew Morton , Daniel Wagner , Dave Chinner , Don Mullis , Linux Kernel Mailing List , Rasmus Villemoes , Andrey Abramov Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8BIT Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi George, On Fri, Mar 15, 2019 at 5:33 AM George Spelvin wrote: > On Thu, 14 Mar 2019 at 11:10:41 +0200, Andy Shevchenko wrote: > > On Tue, Mar 05, 2019 at 03:06:44AM +0000, George Spelvin wrote: > >> + for (bit = 1; count & bit; bit <<= 1) { > >> + cur = merge(priv, (cmp_func)cmp, pending, cur); > >> + pending = pending->prev; /* Untouched by merge() */ > >> } > > > > Wouldn't be it the same to > > > > bit = ffz(count); > > while (bit--) { > > ... > > } > > ? > > > > Though I dunno which one is generating better code. > > One question I should ask everyone: should "count" be 32 or 64 bits > on 64-bit machines? That would let x86 save a few REX bytes. (815 > vs. 813 byte code, if anyone cares.) > > Allegedy ARM can save a few pJ by gating the high 32 > bits of the ALU. > > Most other 64-bit processors would prefer 64-bit operations as > it saves masking operations. > > If we never sort a list with more than 2^32 entries, it > makes no difference. > > If we use a 32-bit count and we *do* sort a list with more than > 2^32 entries, then it still sorts, but the performance degrades to > O((n/2^32)^2). > > Just how often do we expect the kernel to face lists that long? > (Note that the old code was O((n/2^20)^2).) Using size_t sounds most logical to me (argument of least surprise). > In the code, I could do something like > > #ifdef CONFIG_X86_64 > /* Comment explaining why */ > typedef uint32_t count_t; > #else > typedef size_t count_t; > #endif > > ... > count_t count = 0; Using different types makes it more complex, e.g. to print the value in debug code. And adding more typedefs is frowned upon. Just my 0.02€. Gr{oetje,eeting}s, Geert -- Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that. -- Linus Torvalds