Received: by 2002:ac0:aed5:0:0:0:0:0 with SMTP id t21csp7015679imb; Sat, 9 Mar 2019 13:06:13 -0800 (PST) X-Google-Smtp-Source: APXvYqzOWn/nkULTxs92H9JqdhdQB/2qHQnzlvQS1imIB9dKopWxizM2h19pqDJKo2rx5cS8VeYR X-Received: by 2002:a17:902:b708:: with SMTP id d8mr25318614pls.322.1552165573197; Sat, 09 Mar 2019 13:06:13 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1552165573; cv=none; d=google.com; s=arc-20160816; b=xeCk7AjJeqHEHmUXU6gI+hBcKJSScgtBND9rtRHw8wLPU9v44l/khj1/d3GVstZMSw r7SV5JlkMtRpayrGkBF3UWCm2F1vyKnxXnBsjrM5lQzHBdsmkJ6tN9wmNvutFCK8qbTR kYHBpY0belguEHupbvT+jbI6GRLOFyZuea+o/hT2m3eoos9Ie/oAg72qxOg3IezhOmcg EQy3Qwma3HjU8I6PzznowDZr34DgJbTaF8IroARP4pD7G1d0uAZ/EG9MTAdwXObbdSol s73KC4s9sX3YDvMjRMkhvZi0D+OkJzjKvgDxdyk8d38wC61UqGr9ltrr4VpRVJM850Tk Nt7Q== 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=LMGVl2WZYzo9jfdh5vXCf0PQ8TjANkzi0Z+nROWrGiU=; b=E3g/htq/EfBnrBJsakYayORykfYnZqJSQrTxejorrlhRZ6AGlqWlNEMmj+CCoO6WJz Ua7xbKpxHnpaki2gV7GXwF1xxnKdGQq5+OWHxSEmX6HyrH9ZZl/femn0j4JEts21U7TS j/QxWtoESXOrKZOLSOiocylOqXZJw5z5mSgX2xq23ht+ey35fYjQAJu87MYjvYZqtnlF Xy66WrugZbZKk8iDYbsYqUrdzakRMfEs5LasVr6c+IqmBK7jA9NMjxUkgjPbNpqUzsj/ xXpwTzd5GiglmhMuva1g3qXzhrHbXRfH2Ce0edYRhGCHAldb8AWYo1hohswkuDM894pK r6Rg== 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 e28si1280984pgm.368.2019.03.09.13.05.44; Sat, 09 Mar 2019 13:06:13 -0800 (PST) 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 S1726436AbfCIVEk (ORCPT + 99 others); Sat, 9 Mar 2019 16:04:40 -0500 Received: from mx.sdf.org ([205.166.94.20]:61342 "EHLO mx.sdf.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726298AbfCIVEk (ORCPT ); Sat, 9 Mar 2019 16:04:40 -0500 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 x29L2Tb1029151 (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256 bits) verified NO); Sat, 9 Mar 2019 21:02:30 GMT Received: (from lkml@localhost) by sdf.org (8.15.2/8.12.8/Submit) id x29L2TvG017588; Sat, 9 Mar 2019 21:02:29 GMT Date: Sat, 9 Mar 2019 21:02:29 GMT From: George Spelvin Message-Id: <201903092102.x29L2TvG017588@sdf.org> To: andriy.shevchenko@linux.intel.com, lkml@sdf.org Subject: Re: [PATCH 1/5] lib/sort: Make swap functions more generic Cc: akpm@linux-foundation.org, daniel.wagner@siemens.com, dchinner@redhat.com, don.mullis@gmail.com, geert@linux-m68k.org, linux-kernel@vger.kernel.org, linux@rasmusvillemoes.dk, st5pub@yandex.ru In-Reply-To: <20190309140653.GO9224@smile.fi.intel.com> References: , , <20190309140653.GO9224@smile.fi.intel.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Andy Shevchenko wrote: > Shouldn't simple memcpy cover these case for both 32- and 64-bit architectures? Speaking of replacing swap with copying via temporary buffers, one idea that did come to mind was avoiding swap for sufficiently small objects. Every sift-down is actually a circular shift. Once the target position hs been found, we rotate the path from the root to the target up one, with the target filled in by the previous root. (When breaking down the heap, there's one additional link in the cycle, where the previous root goes to the end of the heap and the end of the heap goes to the target.) If we had a temporary buffer (128 bytes would handle most things), we could copy the previous root there and *copy*, rather than swap, the elements on the path to the target up, then finally copy the previous root to the target. However, to rotate up, the this must be done in top-down order. The way the code currently works with premultiplied offsets, it's easy to traverse bottom-up, but very awkward to retrace the top-down path. The only solution I can think of is to build a bitmap of the left/right turnings from the root to the leaf, and then back it up to the target. There are a few ways to do this: 1) The obvious big-endian order. The bitmap is simply the 1-based position of the leaf. To add a level, shift left and add the new bit at the bottom. To back up a step, shift right. To retrace, create a 1-bit mask equal to the msbit of the index ((smear_right(x) >> 1) + 1) and repeatedly shift the mask right. 2) The reverse order. We use a 1-bit mask while building the bitmap, and while retracing, just examine the lsbit while shifting the bitmap right. 3) As option 1, but don't build the bitmap as we're walking down; rather reconstruct it from the premultiplied offset using reciprocal_divide(). Nothing really jumps out to me as The Right Way to do it. I don't want to bloat the code to the point that it would be easier to implement a different algorithm entirely.