Optimize Result<Ok, E> with sizeof(E) < sizeof(uintptr_t)

RESOLVED FIXED in Firefox 54

Status

()

defect
RESOLVED FIXED
3 years ago
3 years ago

People

(Reporter: jandem, Assigned: nbp)

Tracking

unspecified
mozilla54
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox54 fixed)

Details

Attachments

(4 attachments, 2 obsolete attachments)

nbp wants to use Result<> in IonBuilder. In this case the error type is an enum and it should be possible to add a ResultImplementation that fits in a single word.
Flags: needinfo?(nicolas.b.pierron)
This change the current code such that masking out the least significant bit
does not require a large mask, i-e large instruction immediates.
Attachment #8820835 - Flags: review?(jdemooij)
This patch replaces multiple unrelated flags by a single flag which
describes the implementation strategy.

This change the way we select templates in order to make it easier to read,
and understand.

This patch also adds UnusedZero structure as a predicate needed to ensure
that nullptr value can be used as a tag.
Attachment #8820837 - Flags: review?(jwalden+bmo)
This patch adds a new strategy which solve this bug, in order to reduce the
memory overhead of having a variant with { uint64_t; VariantTag } returned
value.

I first tried the approach of using the sign bit as a discriminant, but this
has some pit-falls such as the integer representations on various
systems. In the mean time, this should be enough for the memory saving
aspect.
Attachment #8820839 - Flags: review?(jwalden+bmo)
Add a type to AbortReason such that we can benfit from the part 3 optimization.
Attachment #8820840 - Flags: review?(jdemooij)
Comment on attachment 8820835 [details] [diff] [review]
part 1 - Use a smaller mask to remove the error tag.

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

::: mfbt/Result.h
@@ +103,5 @@
>      MOZ_ASSERT((uintptr_t(aValue) % MOZ_ALIGNOF(V)) == 0,
>                 "Result value pointers must not be misaligned");
>    }
>    explicit ResultImplementation(E& aErrorValue)
> +    : mBits(reinterpret_cast<uintptr_t>(&aErrorValue) ^ 1)

I think I'd prefer keeping the | 1 here because it's a bit more obviously correct.
Attachment #8820835 - Flags: review?(jdemooij) → review+
Comment on attachment 8820840 [details] [diff] [review]
part 4 - Use a smaller enum representation for js::jit::AbortReason.

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

Nice.
Attachment #8820840 - Flags: review?(jdemooij) → review+
Comment on attachment 8820837 [details] [diff] [review]
part 2 - mdft::Result: Use a single enum to dispatch to the Result implementation.

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

::: mfbt/Result.h
@@ +125,5 @@
> +// To use nullptr as a special value, we need the counter part to exclude zero
> +// from its range of valid representations.
> +//
> +// By default assume that zero can be represented.
> +template <typename T> struct UnusedZero { static const bool value = false; };

template<typename T>
struct UnusedZero
{
  static const bool value = false;
};

@@ +127,5 @@
> +//
> +// By default assume that zero can be represented.
> +template <typename T> struct UnusedZero { static const bool value = false; };
> +
> +// References are assumed to never be null.

// References can't be null.

(not without dereferencing a null pointer which is undefined behavior, that is)

@@ +130,5 @@
> +
> +// References are assumed to never be null.
> +template <typename T> struct UnusedZero<T&> {
> +  static const bool value = true;
> +};

template<typename T>
struct UnusedZero<T&>
{
  static const bool value = true;
};

@@ +160,5 @@
> +      (IsEmpty<V>::value && UnusedZero<E>::value)
> +    ? PackingStrategy::NullIsOk
> +    : (detail::HasFreeLSB<V>::value && detail::HasFreeLSB<E>::value)
> +    ? PackingStrategy::LowBitTagIsError
> +    : PackingStrategy::Variant;

Add in

  using Type = detail::ResultImplementation<V, E, value>;

@@ +195,5 @@
>  template <typename V, typename E>
>  class MOZ_MUST_USE_TYPE Result final
>  {
>    using Impl =
> +    detail::ResultImplementation<V, E, detail::SelectResultImpl<V, E>::value>;

...and then this can be

  using Impl = typename detail::SelectResultImpl<V, E>::Type;
Attachment #8820837 - Flags: review?(jwalden+bmo) → review+
Comment on attachment 8820839 [details] [diff] [review]
part 3 - mdft::Result: Add a new packing strategy to pack small enumerated values in a single word.

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

This looks wholly little-endian-centric and would totally fall over on big-endian.  I grant that that's not tier-1, but you basically make it impossible to even implement this for big-endian, and that's no good.

This isn't a bad idea -- it just should probably apply only to IsIntegral<V>::value, and you should be munging the tag bit into and out of it manually.  Give that a try without the unions.
Attachment #8820839 - Flags: review?(jwalden+bmo) → review-
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #8)
> This isn't a bad idea -- it just should probably apply only to
> IsIntegral<V>::value, and you should be munging the tag bit into and out of
> it manually.  Give that a try without the unions.

I thought the same thing at the beginning, but the problem is that the Ok struct is not an Integral type.

I will try something else quickly which should be less of an issue on big-endian platforms.
Assignee: nobody → nicolas.b.pierron
Status: NEW → ASSIGNED
Flags: needinfo?(nicolas.b.pierron)
This patch implements a different packing strategy than the previous
one. The difference being that this implementation is not capable of packing
2 uint32_t in an uint64_t.

This new packing stratgey does not use an union, but it uses a structure to
pack the content of it in a single word. As the alignment might require
fields to have some padding, we try to swap the V and E, then only consider the
smallest one.

This should remove the endianness question, and be much more portable.
Attachment #8821870 - Flags: review?(jwalden+bmo)
Attachment #8820839 - Attachment is obsolete: true
Comment on attachment 8821870 [details] [diff] [review]
part 3 - mdft::Result: Add a new packing strategy to pack small enumerated values in a single word.

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

r- until the union/test questions are answered, but in principle no significant objection to this like last time.

Is there a reason

template <typename V, typename E>
class ResultImplementation<V, E, PackingStrategy::PackedVariant>
{
  union {
    V mValue;
    E mError;
  };
  bool mOk;

public:
  explicit ResultImplementation(V aValue)
  {
    mValue = aValue;
    mOk = true;
  }
  explicit ResultImplementation(E aErrorValue)
  {
    mError = aErrorValue;
    mOk = false;
  }
 
  bool isOk() const { return mOk; }
 
  V unwrap() const { return mValue; }
  E unwrapErr() const { return mError; }
};

and IsPod<V>::value and IsPod<E>::value conditions on its use wouldn't work?  That'd avoid having to worry about ordering.  Or does the union make Result not registerize?

::: mfbt/Result.h
@@ +134,5 @@
> +      bool ok;
> +  };
> +  struct EVbool {
> +      V v;
> +      E e;

Wrong order!

::: mfbt/tests/TestResult.cpp
@@ +44,5 @@
> +static_assert(sizeof(Foo32) >= sizeof(uintptr_t) ||
> +              sizeof(Result<Foo32, Foo16>) == sizeof(uintptr_t),
> +              "Result with small types should be pointer-sized");
> +static_assert(sizeof(Foo32) >= sizeof(uintptr_t) ||
> +              sizeof(Result<Foo16, Foo32>) == sizeof(uintptr_t),

Given you had V+E ordering for both implementation layouts, why does this pass?  |struct { uint16_t; uint32_t; bool; };| on 64-bit should be larger than uintptr_t, shouldn't it?
Attachment #8821870 - Flags: review?(jwalden+bmo) → review-
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #11)
> Is there a reason
> 
>   union {
>     V mValue;
>     E mError;
>   };
> 
> and IsPod<V>::value and IsPod<E>::value conditions on its use wouldn't work?
> That'd avoid having to worry about ordering.  Or does the union make Result
> not registerize?

IsPod should help making sure we can pack the V and E in an union, but I don't think this would work for enumerated types, as we would have to specialize IsPod for each enum, which is what we are trying to encode here.

> ::: mfbt/tests/TestResult.cpp
> @@ +44,5 @@
> > +static_assert(sizeof(Foo32) >= sizeof(uintptr_t) ||
> > +              sizeof(Result<Foo32, Foo16>) == sizeof(uintptr_t),
> > +              "Result with small types should be pointer-sized");
> > +static_assert(sizeof(Foo32) >= sizeof(uintptr_t) ||
> > +              sizeof(Result<Foo16, Foo32>) == sizeof(uintptr_t),
> 
> Given you had V+E ordering for both implementation layouts, why does this
> pass?  |struct { uint16_t; uint32_t; bool; };| on 64-bit should be larger
> than uintptr_t, shouldn't it?

Mostly because this is a test case issue, and that I had no clue on how to get this test case compiled and I was hoping the try server to have the answer.  I did ran some of these assert in another file, but I might have added these cases after.

I finally figured how to run mfbt test suite, and noticed another corner case which is that we need V and E to have a default constructor, as the Result constructor only explicitly initialize one part of the structure, and the other should use the default constructor.

I will submit a new patch which contains the IsDefaultConstructible type trait class, and use it as a pre-condition for choosing the PackedVariant.
Delta:
 - Fix the test cases: use <= instead == when comparing against
   sizeof(uintptr_t).
 - Fix V and E ordering in EVbool.
 - Add IsDefaultConstructible class, and use it as a guard to check the
   IsPackableVariant case.  This is needed for small structures no default
   constructor. (issue found while running TestResult.cpp)
 - Add test cases for IsDefaultConstructible.
Attachment #8832915 - Flags: review?(jwalden+bmo)
Attachment #8821870 - Attachment is obsolete: true
(In reply to Nicolas B. Pierron [:nbp] from comment #12)

> IsPod should help making sure we can pack the V and E in an union, but I
> don't think this would work for enumerated types, as we would have to
> specialize IsPod for each enum, which is what we are trying to encode here.

I think we could work around this with IsEnum and IsIntegral, perhaps.  But I might as well just do this subsequent improvement myself, once I've landed some support for defining unrestricted unions.  So, okay.
Comment on attachment 8832915 [details] [diff] [review]
part 3 - mdft::Result: Add a new packing strategy to pack small enumerated values in a single word.

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

Your patch summary needs s/mfbt/mozilla/.

::: mfbt/TypeTraits.h
@@ +589,5 @@
> +};
> +
> +} // namespace detail
> +
> +template<typename T>

This needs the same sort of documentation comment by it that IsUnsigned has.  mfbt doc standards are high, and lack of a comment at all doesn't meet that.  :-)

(If I could persuade you to add the same sort of thing by IsDestructible as well, that'd be great, too.  Whoever landed/reviewed IsDestructible's lack thereof done goofed.)

::: mfbt/tests/TestTypeTraits.cpp
@@ +35,1 @@
>  using mozilla::IsDestructible;

These two usings should be moved earlier in this list to be alphabetical.

@@ +374,5 @@
> +enum class EnumClassCtor1 : int {};
> +
> +union UnionCtor0 {};
> +union UnionCtor1 { int mX; };
> +

Add

union UnionCustomCtor0
{
  UnionCustomCtor0(int) {}
};
union UnionCustomCtor1
{
  int mX;

  UnionCustomCtor1(int aX) : mX(aX) {}
};

and then test in the appropriate place far below that neither of these are default-constructible.  (No default constructor is implicitly generated when another constructor is present, as in these.)
Attachment #8832915 - Flags: review?(jwalden+bmo) → review+
Pushed by npierron@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/2d01a306f0f4
part 1 - Use a smaller mask to remove the error tag. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/9d73f4423034
part 2 - mozilla::Result: Use a single enum to dispatch to the Result implementation. r=Waldo
https://hg.mozilla.org/integration/mozilla-inbound/rev/f8643ee1df78
part 3 - mozilla::Result: Add a new packing strategy to pack small enumerated values in a single word. r=Waldo
https://hg.mozilla.org/integration/mozilla-inbound/rev/7bfd00786ef6
part 4 - Use a smaller enum representation for js::jit::AbortReason. r=jandem
You need to log in before you can comment on or make changes to this bug.