Received: by 2002:ac0:950c:0:0:0:0:0 with SMTP id f12csp3659321imc; Thu, 14 Mar 2019 02:13:50 -0700 (PDT) X-Google-Smtp-Source: APXvYqyoEkJYO7PDGPKp+FEHehjg0lTzaPTXhW7SNhzPz1DRXnyHxqWtAM7GpD58KhQYvQyUO6vV X-Received: by 2002:a17:902:e090:: with SMTP id cb16mr48719994plb.32.1552554830812; Thu, 14 Mar 2019 02:13:50 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1552554830; cv=none; d=google.com; s=arc-20160816; b=K6vB6iofZPEfN8Yfj/uXQ15INRm6MGsvtCsA5UKpuka6QIjiGt5wZeUzVp/2IUAP/Q +vhANwTEKEpmRchRoK26KtKYFVIg76ZQYLCvlL28Fmj1wuFxptaSlAHHwsJS3ePTdh0w M0P6QMZ2dUOXum/8BQB33jxy8DD8SXMG8Wh/UJmWZ19ikhrrL7XY0ZnEK0CpENLwOubc FhzmAEh2yxFvmpEbDRGHzTrwjUN2oTZijuMqeK4bOJXDFtmoCKoot/pkMu8gPbUd3top ND+oGbklk3JF2yCvIqTsty+WgIx05Hps8PrxJ+iQtya6lOGcwUqmNv72CxcWtGycAFfN C/hA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:user-agent:organization:in-reply-to :content-disposition:mime-version:references:message-id:subject:cc :to:from:date; bh=/MIv+7dOC0k4svnLhCmTYXMniKqWFcAQvHkeU+cBW8M=; b=BgeTDGNJxpRbfFny/OjH3MI/hzU4Qfo57kRML+lRfV1ZdxOohx8K1BlTqTi+7QgL+T QRsPVeqSpjKr4ec6Goi9KG1oPkC/OITWUvDUGV3Hh1Mr5P2UhHxRDmDCWzdJgoVPM8Kr dtx5pfU+fdR8p5o3rIBcxGKPrnHssn4WHDnAUthksiC/aXPcP6A7grzWq/koVWgNAc8h E72/FlbFlawvlBFplZZjQiRMOIbWJUgV/z80wFJypHpKo2PyP1ESDwmmNxwuZv47JldV g9uAudiiwe2jbSG3h+qq381N1dVZ8yOaclxLVq0TL33tzSN469fenG1D+3jg5n582rS4 R5rg== 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; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=intel.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id p6si11923561pga.151.2019.03.14.02.13.35; Thu, 14 Mar 2019 02:13:50 -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; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=intel.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726971AbfCNJKr (ORCPT + 99 others); Thu, 14 Mar 2019 05:10:47 -0400 Received: from mga04.intel.com ([192.55.52.120]:61403 "EHLO mga04.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726896AbfCNJKq (ORCPT ); Thu, 14 Mar 2019 05:10:46 -0400 X-Amp-Result: UNKNOWN X-Amp-Original-Verdict: FILE UNKNOWN X-Amp-File-Uploaded: False Received: from orsmga003.jf.intel.com ([10.7.209.27]) by fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 14 Mar 2019 02:10:46 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.58,477,1544515200"; d="scan'208";a="133982089" Received: from smile.fi.intel.com (HELO smile) ([10.237.72.86]) by orsmga003.jf.intel.com with ESMTP; 14 Mar 2019 02:10:43 -0700 Received: from andy by smile with local (Exim 4.92) (envelope-from ) id 1h4MNt-0002XB-ET; Thu, 14 Mar 2019 11:10:41 +0200 Date: Thu, 14 Mar 2019 11:10:41 +0200 From: Andy Shevchenko To: George Spelvin Cc: linux-kernel@vger.kernel.org, Andrew Morton , Andrey Abramov , Geert Uytterhoeven , Daniel Wagner , Rasmus Villemoes , Don Mullis , Dave Chinner Subject: Re: [PATCH 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS Message-ID: <20190314091041.GU9224@smile.fi.intel.com> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Organization: Intel Finland Oy - BIC 0357606-4 - Westendinkatu 7, 02160 Espoo User-Agent: Mutt/1.10.1 (2018-07-13) Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Mar 05, 2019 at 03:06:44AM +0000, George Spelvin wrote: > Rather than a fixed-size array of pending sorted runs, use the ->prev > links to keep track of things. This reduces stack usage, eliminates > some ugly overflow handling, and reduces the code size. > > Also: > * merge() no longer needs to handle NULL inputs, so simplify. > * The same applies to merge_and_restore_back_links(), which is renamed > to the less ponderous merge_final(). (It's a static helper function, > so we don't need a super-descriptive name; comments will do.) > > x86-64 code size 1086 -> 740 bytes (-346) > + do { > + size_t bit; > struct list_head *cur = list; > + > + /* Extract the head of "list" as a single-element list "cur" */ > list = list->next; > cur->next = NULL; > > + /* Do merges corresponding to set lsbits in count */ > + 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. > + /* And place the result at the head of "pending" */ > + cur->prev = pending; > + pending = cur; > + count++; > + } while (list->next); > + > + /* Now merge together last element with all pending lists */ > + while (pending->prev) { > + list = merge(priv, (cmp_func)cmp, pending, list); > + pending = pending->prev; > } -- With Best Regards, Andy Shevchenko