1131783 - Optimize branches in Vector

Status: RESOLVED FIXED

(Core :: MFBT, enhancement)

Description

[Dan Gohman [:sunfish]]

I happened to be looking at some assembly code generated for the mfbt Vector class and noticed a few things which could be optimized.

Comment 1

[Dan Gohman [:sunfish]]

Attachment: unlikely.patch

This patch adds MOZ_LIKELY and MOZ_UNLIKELY to some predictable branches in Vector and elsewhere.

Comment 2

[Dan Gohman [:sunfish]]

Attachment: vector-nullchecks.patch

The semantics of C++ placement new require it to avoid calling the constructor if the pointer is null. In practice, this means it often uses an extra branch to chec for null. mfbt Vector uses placement new in contexts where the pointer will never be null, so these null checks are needless overhead.

The attached patch extends the VectorImpl with new_ methods that perform placement new for non-POD, and plain assignment for POD. This eliminates the null checks for POD types, which is a common case.

Comment 3

[Dan Gohman [:sunfish]]

Attachment: vector-more-nullchecks.patch

This patch adds a MOZ_NONNULL function attribute and applies it to the non-POD new_ functions introduced in the previous patch. This allows some optimizers to eliminate the null checks for non-POD types in some cases.

Comment 4

[Jeff Walden [:Waldo]]

Comment on attachment 8562336 [details] [diff] [review]
vector-more-nullchecks.patch

Review of attachment 8562336 [details] [diff] [review]:
-----------------------------------------------------------------

It's a little shocking compilers can't see that the callers are passing non-null pointers here, but oh well.  Maybe worth filing bugs on the compilers?  Bonus points if you do, but certainly not required.

Or, another possibility.  Make the argument a reference, then have callers pass in *p and such, and the functions can do |new (&ref) T(...)|?  That'd solve it for every compiler, at the expense of the reference-ness not being super-clear.  Maybe worth renaming new_ to defaultConstruct(T&) and placementNew(T&, U&&) or something, if you did that.

Comment 5

[Dan Gohman [:sunfish]]

remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/c280abdc083f
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/588d1e20a4bb
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/3571f361d779

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #4)
> Comment on attachment 8562336 [details] [diff] [review]
> vector-more-nullchecks.patch
> 
> Review of attachment 8562336 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> It's a little shocking compilers can't see that the callers are passing
> non-null pointers here, but oh well.  Maybe worth filing bugs on the
> compilers?  Bonus points if you do, but certainly not required.

In many cases, it's not possible for compilers to do this. Vector append is a more complicated form of code like this:

void foo(Vector<T> &v) {
  new (v.ptr + v.length) T();
}

But even in this simplified version, the compiler has no way of knowing that v.ptr isn't null. That's an invariant of the Vector class, but the compiler doesn't know that. So while compilers do indeed eliminate null checks in some cases, in practice there are often reasons that they can't, which is why it's useful for us to optimize our code.

> Or, another possibility.  Make the argument a reference, then have callers
> pass in *p and such, and the functions can do |new (&ref) T(...)|?  That'd
> solve it for every compiler, at the expense of the reference-ness not being
> super-clear.  Maybe worth renaming new_ to defaultConstruct(T&) and
> placementNew(T&, U&&) or something, if you did that.

The POD use case is the more common one, and that's covered by the first patch which doesn't need compiler-specific magic, so I decided not to clutter the code with reference-ness just for the non-POD case. The compiler-specific magic is happily pretty non-invasive.

Comment 6

[Nathan Froyd [:froydnj]]

(In reply to Dan Gohman [:sunfish] from comment #5)
> (In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #4)
> > It's a little shocking compilers can't see that the callers are passing
> > non-null pointers here, but oh well.  Maybe worth filing bugs on the
> > compilers?  Bonus points if you do, but certainly not required.
> 
> In many cases, it's not possible for compilers to do this. Vector append is
> a more complicated form of code like this:
> 
> void foo(Vector<T> &v) {
>   new (v.ptr + v.length) T();
> }
> 
> But even in this simplified version, the compiler has no way of knowing that
> v.ptr isn't null. That's an invariant of the Vector class, but the compiler
> doesn't know that. So while compilers do indeed eliminate null checks in
> some cases, in practice there are often reasons that they can't, which is
> why it's useful for us to optimize our code.

Recent-ish GCC and clang do have __attribute__(...) magic to declare things non-null, though I suppose that doesn't work for MSVC, which is a large part of what we care about.

Comment 7

[Dan Gohman [:sunfish]]

The situation with the patches above checked in is:

  - when T is POD, we get no null checks on any compiler
  - when T is non-POD, we use the nonnull magic attribute on compilers which support it

Comment 4 describes a possible approach using reference types which may allow null checks to be optimized away for non-POD in a compiler-independent manner, in case someone wants to try that.

Comment 8

[Nathan Froyd [:froydnj]]

(In reply to Dan Gohman [:sunfish] from comment #7)
> The situation with the patches above checked in is:
> 
>   - when T is POD, we get no null checks on any compiler
>   - when T is non-POD, we use the nonnull magic attribute on compilers which
> support it
> 
> Comment 4 describes a possible approach using reference types which may
> allow null checks to be optimized away for non-POD in a compiler-independent
> manner, in case someone wants to try that.

Oh, duh, I see comment 3.  Please ignore me!

Comment 9

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/c280abdc083f
https://hg.mozilla.org/mozilla-central/rev/588d1e20a4bb
https://hg.mozilla.org/mozilla-central/rev/3571f361d779