From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.2 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,USER_AGENT_SANE_2 autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id AA4A6C76191 for ; Thu, 25 Jul 2019 12:40:46 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 8333222BED for ; Thu, 25 Jul 2019 12:40:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2388534AbfGYMkm (ORCPT ); Thu, 25 Jul 2019 08:40:42 -0400 Received: from bhuna.collabora.co.uk ([46.235.227.227]:43752 "EHLO bhuna.collabora.co.uk" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2388147AbfGYMkl (ORCPT ); Thu, 25 Jul 2019 08:40:41 -0400 Received: from localhost (unknown [IPv6:2a01:e0a:2c:6930:5cf4:84a1:2763:fe0d]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) (Authenticated sender: bbrezillon) by bhuna.collabora.co.uk (Postfix) with ESMTPSA id A27AE28AACA; Thu, 25 Jul 2019 13:40:38 +0100 (BST) Date: Thu, 25 Jul 2019 14:40:35 +0200 From: Boris Brezillon To: Mauro Carvalho Chehab , Hans Verkuil , Laurent Pinchart , Sakari Ailus , linux-media@vger.kernel.org, Andrew Morton Cc: linux-kernel@vger.kernel.org, Tomasz Figa , Nicolas Dufresne , kernel@collabora.com, Paul Kocialkowski , Ezequiel Garcia , Jonas Karlman , linux-rockchip@lists.infradead.org, Heiko Stuebner , Rasmus Villemoes , Philipp Zabel Subject: Re: [PATCH 1/9] lib/sort.c: implement sort() variant taking context argument Message-ID: <20190725144035.486a33ef@collabora.com> In-Reply-To: <20190619121540.29320-2-boris.brezillon@collabora.com> References: <20190619121540.29320-1-boris.brezillon@collabora.com> <20190619121540.29320-2-boris.brezillon@collabora.com> Organization: Collabora X-Mailer: Claws Mail 3.17.3 (GTK+ 2.24.32; x86_64-redhat-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: linux-media-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-media@vger.kernel.org Hi Andrew, On Wed, 19 Jun 2019 14:15:32 +0200 Boris Brezillon wrote: > From: Rasmus Villemoes > > Our list_sort() utility has always supported a context argument that > is passed through to the comparison routine. Now there's a use case > for the similar thing for sort(). > > This implements sort_r by simply extending the existing sort function > in the obvious way. To avoid code duplication, we want to implement > sort() in terms of sort_r(). The naive way to do that is > > static int cmp_wrapper(const void *a, const void *b, const void *ctx) > { > int (*real_cmp)(const void*, const void*) = ctx; > return real_cmp(a, b); > } > > sort(..., cmp) { sort_r(..., cmp_wrapper, cmp) } > > but this would do two indirect calls for each comparison. Instead, do > as is done for the default swap functions - that only adds a cost of a > single easily predicted branch to each comparison call. > > Aside from introducing support for the context argument, this also > serves as preparation for patches that will eliminate the indirect > comparison calls in common cases. > > Requested-by: Boris Brezillon > Signed-off-by: Rasmus Villemoes > Signed-off-by: Boris Brezillon > Cc: Andrew Morton > --- > Hi all, > > Andrew, you acked the first version of this patch, but Rasmus proposed > a better solution and posted a v2. Can you review/ack this version. Hans is planning to take that patch soon. Would you mind adding your Ack back (assuming you're okay with the new version of course)? Thanks, Boris > > Hans, Mauro, Andrew suggested to have this patch applied along with > its first user (the H264 backend of the hantro codec), so here it is. > Note that, if possible, I'd like to have this patch queued for the next > release even if the H264 bits don't get accepted as is. The rationale > here being that Rasmus told me he was planning to further improve the > sort() logic after the next -rc1 is out, and I fear his changes will > conflict with this patch, which might involve some kind synchronisation > (a topic branch) between the media maintainers and Andrew. > > Let me know how you want to proceed with that. > > Regards, > > Boris > --- > include/linux/sort.h | 5 +++++ > lib/sort.c | 34 ++++++++++++++++++++++++++++------ > 2 files changed, 33 insertions(+), 6 deletions(-) > > diff --git a/include/linux/sort.h b/include/linux/sort.h > index 2b99a5dd073d..61b96d0ebc44 100644 > --- a/include/linux/sort.h > +++ b/include/linux/sort.h > @@ -4,6 +4,11 @@ > > #include > > +void sort_r(void *base, size_t num, size_t size, > + int (*cmp)(const void *, const void *, const void *), > + void (*swap)(void *, void *, int), > + const void *priv); > + > void sort(void *base, size_t num, size_t size, > int (*cmp)(const void *, const void *), > void (*swap)(void *, void *, int)); > diff --git a/lib/sort.c b/lib/sort.c > index cf408aec3733..d54cf97e9548 100644 > --- a/lib/sort.c > +++ b/lib/sort.c > @@ -144,6 +144,18 @@ static void do_swap(void *a, void *b, size_t size, swap_func_t swap_func) > swap_func(a, b, (int)size); > } > > +typedef int (*cmp_func_t)(const void *, const void *); > +typedef int (*cmp_r_func_t)(const void *, const void *, const void *); > +#define _CMP_WRAPPER ((cmp_r_func_t)0L) > + > +static int do_cmp(const void *a, const void *b, > + cmp_r_func_t cmp, const void *priv) > +{ > + if (cmp == _CMP_WRAPPER) > + return ((cmp_func_t)(priv))(a, b); > + return cmp(a, b, priv); > +} > + > /** > * 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. > @@ -171,12 +183,13 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size) > } > > /** > - * sort - sort an array of elements > + * sort_r - sort an array of elements > * @base: pointer to data to sort > * @num: number of elements > * @size: size of each element > * @cmp_func: pointer to comparison function > * @swap_func: pointer to swap function or NULL > + * @priv: third argument passed to comparison function > * > * This function does a heapsort on the given array. You may provide > * a swap_func function if you need to do something more than a memory > @@ -188,9 +201,10 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size) > * O(n*n) worst-case behavior and extra memory requirements that make > * it less suitable for kernel use. > */ > -void sort(void *base, size_t num, size_t size, > - int (*cmp_func)(const void *, const void *), > - void (*swap_func)(void *, void *, int size)) > +void sort_r(void *base, size_t num, size_t size, > + int (*cmp_func)(const void *, const void *, const void *), > + void (*swap_func)(void *, void *, int size), > + const void *priv) > { > /* pre-scale counters for performance */ > size_t n = num * size, a = (num/2) * size; > @@ -238,12 +252,12 @@ void sort(void *base, size_t num, size_t size, > * average, 3/4 worst-case.) > */ > for (b = a; c = 2*b + size, (d = c + size) < n;) > - b = cmp_func(base + c, base + d) >= 0 ? c : d; > + b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d; > if (d == n) /* Special case last leaf with no sibling */ > b = c; > > /* Now backtrack from "b" to the correct location for "a" */ > - while (b != a && cmp_func(base + a, base + b) >= 0) > + while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0) > b = parent(b, lsbit, size); > c = b; /* Where "a" belongs */ > while (b != a) { /* Shift it into place */ > @@ -252,4 +266,12 @@ void sort(void *base, size_t num, size_t size, > } > } > } > +EXPORT_SYMBOL(sort_r); > + > +void sort(void *base, size_t num, size_t size, > + int (*cmp_func)(const void *, const void *), > + void (*swap_func)(void *, void *, int size)) > +{ > + return sort_r(base, num, size, _CMP_WRAPPER, swap_func, cmp_func); > +} > EXPORT_SYMBOL(sort);