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

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Jan de Mooij [:jandem]]

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.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: part 1 - Use a smaller mask to remove the error tag.

This change the current code such that masking out the least significant bit
does not require a large mask, i-e large instruction immediates.

Comment 2

[Nicolas B. Pierron [:nbp]]

Attachment: part 2 - mdft::Result: Use a single enum to dispatch to the Result implementation.

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.

Comment 3

[Nicolas B. Pierron [:nbp]]

Attachment: part 3 - mdft::Result: Add a new packing strategy to pack small enumerated values in a single word.

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.

Comment 4

[Nicolas B. Pierron [:nbp]]

Attachment: part 4 - Use a smaller enum representation for js::jit::AbortReason.

Add a type to AbortReason such that we can benfit from the part 3 optimization.

Comment 5

[Jan de Mooij [:jandem]]

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.

Comment 6

[Jan de Mooij [:jandem]]

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.

Comment 7

[Jeff Walden [:Waldo]]

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;

Comment 8

[Jeff Walden [:Waldo]]

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.

Comment 9

[Nicolas B. Pierron [:nbp]]

(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.

Comment 10

[Nicolas B. Pierron [:nbp]]

Attachment: part 3 - mdft::Result: Add a new packing strategy to pack small enumerated values in a single word.

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.

Comment 11

[Jeff Walden [:Waldo]]

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?

Comment 12

[Nicolas B. Pierron [:nbp]]

(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.

Comment 13

[Nicolas B. Pierron [:nbp]]

Attachment: part 3 - mdft::Result: Add a new packing strategy to pack small enumerated values in a single word.

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.

Comment 14

[Jeff Walden [:Waldo]]

(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 15

[Jeff Walden [:Waldo]]

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.)

Comment 16

[Pulsebot]

Pushed by [e-mail]:
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

Comment 17

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/2d01a306f0f4
https://hg.mozilla.org/mozilla-central/rev/9d73f4423034
https://hg.mozilla.org/mozilla-central/rev/f8643ee1df78
https://hg.mozilla.org/mozilla-central/rev/7bfd00786ef6