LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Steven Rostedt <rostedt@goodmis.org>
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: LKML <linux-kernel@vger.kernel.org>,
	Ben Skeggs <bskeggs@redhat.com>, David Airlie <airlied@linux.ie>,
	Daniel Vetter <daniel@ffwll.ch>,
	Leon Romanovsky <leon@kernel.org>,
	Doug Ledford <dledford@redhat.com>,
	Jason Gunthorpe <jgg@ziepe.ca>,
	"Darrick J. Wong" <darrick.wong@oracle.com>,
	linux-xfs@vger.kernel.org,
	dri-devel <dri-devel@lists.freedesktop.org>,
	nouveau@lists.freedesktop.org,
	linux-rdma <linux-rdma@vger.kernel.org>,
	Andrew Morton <akpm@linux-foundation.org>
Subject: Re: [RFC][PATCH] kernel.h: Add generic roundup_64() macro
Date: Thu, 23 May 2019 11:27:40 -0400	[thread overview]
Message-ID: <20190523112740.7167aba4@gandalf.local.home> (raw)
In-Reply-To: <CAHk-=wg5HqJ2Kfgpub+tCWQ2_FiFwEW9H1Rm+an-BLGaGvDDXw@mail.gmail.com>

On Thu, 23 May 2019 08:10:44 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Thu, May 23, 2019 at 7:00 AM Steven Rostedt <rostedt@goodmis.org> wrote:
> >
> > +# define roundup_64(x, y) (                            \
> > +{                                                      \
> > +       typeof(y) __y = y;                              \
> > +       typeof(x) __x = (x) + (__y - 1);                \
> > +       do_div(__x, __y);                               \
> > +       __x * __y;                                      \
> > +}                                                      \
> 
> The thing about this is that it absolutely sucks for power-of-two arguments.
> 
> The regular roundup() that uses division has the compiler at least
> optimize them to shifts - at least for constant cases. But do_div() is
> meant for "we already know it's not a power of two", and the compiler
> doesn't have any understanding of the internals.
> 
> And it looks to me like the use case you want this for is very much
> probably a power of two. In which case division is all kinds of just
> stupid.
> 
> And we already have a power-of-two round up function that works on
> u64. It's called "round_up()".
> 
> I wish we had a better visual warning about the differences between
> "round_up()" (limited to powers-of-two, but efficient, and works with
> any size) and "roundup()" (generic, potentially horribly slow, and
> doesn't work for 64-bit on 32-bit).
> 
> Side note: "round_up()" has the problem that it uses "x" twice.
> 
> End result: somebody should look at this, but I really don't like the
> "force division" case that is likely horribly slow and nasty.

I haven't yet tested this, but what about something like the following:

# define roundup_64(x, y) (				\
{							\
	typeof(y) __y;					\
	typeof(x) __x;					\
							\
	if (__builtin_constant_p(y) &&			\
	    !(y & (y >> 1))) {				\
		__x = round_up(x, y);			\
	} else {					\
		__y = y;				\
		__x = (x) + (__y - 1);			\
		do_div(__x, __y);			\
		__x = __x * __y;			\
	}						\
	__x;						\
}							\
)

If the compiler knows enough that y is a power of two, it will use the
shift version. Otherwise, it doesn't know enough and would divide
regardless. Or perhaps forget about the constant check, and just force
the power of two check:

# define roundup_64(x, y) (				\
{							\
	typeof(y) __y = y;				\
	typeof(x) __x;					\
							\
	if (!(__y & (__y >> 1))) {			\
		__x = round_up(x, y);			\
	} else {					\
		__x = (x) + (__y - 1);			\
		do_div(__x, __y);			\
		__x = __x * __y;			\
	}						\
	__x;						\
}							\
)

This way even if the compiler doesn't know that this is a power of two,
it will still do the shift if y ends up being one.

-- Steve

  reply	other threads:[~2019-05-23 15:27 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-05-23 14:00 Steven Rostedt
2019-05-23 15:10 ` Linus Torvalds
2019-05-23 15:27   ` Steven Rostedt [this message]
2019-05-23 16:51     ` Linus Torvalds
2019-05-23 17:36       ` Steven Rostedt
2019-05-23 21:19         ` Linus Torvalds
2019-05-24 15:11     ` Roger Willcocks
2019-05-24 15:26       ` Steven Rostedt
2019-05-24 16:30         ` Nikolay Borisov
2019-05-24 16:36           ` Steven Rostedt

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20190523112740.7167aba4@gandalf.local.home \
    --to=rostedt@goodmis.org \
    --cc=airlied@linux.ie \
    --cc=akpm@linux-foundation.org \
    --cc=bskeggs@redhat.com \
    --cc=daniel@ffwll.ch \
    --cc=darrick.wong@oracle.com \
    --cc=dledford@redhat.com \
    --cc=dri-devel@lists.freedesktop.org \
    --cc=jgg@ziepe.ca \
    --cc=leon@kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-rdma@vger.kernel.org \
    --cc=linux-xfs@vger.kernel.org \
    --cc=nouveau@lists.freedesktop.org \
    --cc=torvalds@linux-foundation.org \
    --subject='Re: [RFC][PATCH] kernel.h: Add generic roundup_64() macro' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).