[ADT] Weaken the initialization condition in SmallVector::resize_for_overwrite

[bkramer]

Summary

This method was originally modeled after std::make_unique_for_overwrite, which
default initializes everything, making it a lot less useful.

Using is_trivially_copyable as the condition gives uninitialized memory for
classes that have a default constructor but still allows using
resize_for_overwrite for classes with a non-trivial assignment operator or
destructor. In other words, it makes
SmallVector<std::unique_ptr>::resize_for_overwrite safe and
SmallVector<clang::SourceLocation>::resize_for_overwrite efficient.

[dexonsmith]

(Just seeing this now; sorry for the slow response...)

I think your logic is sound and the patch looks good in principle, except that I wonder if landing it will hit similar problems to https://reviews.llvm.org/D93510 (see also: https://reviews.llvm.org/D117254)

• Older MSVC has trouble with is_trivially_copyable (note the Windows pre-merge check failed)
• Older GCC has trouble with std::is_trivially_copy_constructible and std::is_trivally_move_constructible, which were applied to work around the MSVC troubles

[jplayer-nv]

Older MSVC has trouble with is_trivially_copyable

If I recall correctly from https://reviews.llvm.org/D93510, the original problem was not due to std::is_trivially_copyable being wrong. It was just an insufficient condition to select the trivial OptionalStorage specialization because there were additional assumptions rolled up into taking that specialization. The Optional bug existed independent of the changes MSVC made to the std::pair class (which triggered the compile failure in my build environment).

In theory, we could separate these assumptions into to multiple specializations of the trivial OptionalStorage specialization omitting copy/move constructors and cover the entire breadth of std::is_trivially_copyable types.

---

For this review:

My concern would be the variations in the result of std::is_trivially_copyable across different c++ standards. It's possible that you could have a class considered non-trivially copyable in one compiler and trivially copyable in another. This means that it becomes unclear whether you can populate the buffer with std::uninitialized_copy or you should call std::copy (for example).

Personally, I don't think resize_for_overwrite() should construct values regardless of type traits. In that case, std::uninitialized_copy() and std::uninitialized_fill() would always be appropriate follow-ups.

Are there currently many instances of resize_for_overwrite() called for a non-POD type?

[bkramer]

In D115443#3242421, @jplayer-nv wrote:

My concern would be the variations in the result of std::is_trivially_copyable across different c++ standards. It's possible that you could have a class considered non-trivially copyable in one compiler and trivially copyable in another. This means that it becomes unclear whether you can populate the buffer with std::uninitialized_copy or you should call std::copy (for example).

But is this really a problem? If std::is_trivially_copyable isn't aggressive you get redundant initializations, but it's not a bug. ABI-wise this should also be fine because no struct layout is affected.

Personally, I don't think resize_for_overwrite() should construct values regardless of type traits. In that case, std::uninitialized_copy() and std::uninitialized_fill() would always be appropriate follow-ups.

I somewhat agree, but I'm really concerned about cases like

{
  SmallVector<std::unique_ptr<T>> v;
  v.resize_for_overwrite(42);
}
<crash in destructor>

And also operator= no longer working. Maybe it's not an issue in reality ...

Are there currently many instances of resize_for_overwrite() called for a non-POD type?

No, this function is only used on PODs. I was planning to use it on SmallVectors of SourceLocations in Clang.

[dblaikie]

(yeah, if a resize that does, effectively "new T" for each element instead of "new T()" is all the power we need (rather than a full "don't construct elements at all" mode), that seems like a safer tool/less likely to be a source of bugs, etc, and so probably a better thing to have)

[jplayer-nv]

My concern would be the variations in the result of std::is_trivially_copyable across different c++ standards. It's possible that you could have a class considered non-trivially copyable in one compiler and trivially copyable in another. This means that it becomes unclear whether you can populate the buffer with std::uninitialized_copy or you should call std::copy (for example).

But is this really a problem? If std::is_trivially_copyable isn't aggressive you get redundant initializations, but it's not a bug. ABI-wise this should also be fine because no struct layout is affected.

How about the other direction? You treat a class as non-trivially copyable expecting a constructor call in resize_for_overwrite(), but you actually get back uninitialized data because the class is trivially copyable in some compiler implementation.

Personally, I don't think resize_for_overwrite() should construct values regardless of type traits. In that case, std::uninitialized_copy() and std::uninitialized_fill() would always be appropriate follow-ups.

I somewhat agree, but I'm really concerned about cases like

{
  SmallVector<std::unique_ptr<T>> v;
  v.resize_for_overwrite(42);
}

<crash in destructor>
And also operator= no longer working. Maybe it's not an issue in reality ...

I agree that's a bug, but no one should be calling resize_for_overwrite() without follow-on initialization of the new elements. The proposed change makes resize_for_overwrite() identical to resize() in the case of a non-trivially copyable class, which is a non-value add. So why not static_assert() in case of a non-trivially copyable value_type?

resize_for_overwrite() enables users to write fast code... it is inherently bug-prone if misused. There's a reason why there's no comparable member function on std::vector. So to me, having resize_for_overwrite() sounds like it's breaking the components of resize() into

1. buffer growth + back element pointer / size update
2. Initialization / construction; done manually... optimized in calling context.

If there are type_trait scenarios where resize_for_overwrite() does both 1. and 2., it may as well not exist in those contexts (maybe it should be SFINAE'd out or just static_assert()).

[dblaikie]

{
  SmallVector<std::unique_ptr<T>> v;
  v.resize_for_overwrite(42);
}

<crash in destructor>
And also operator= no longer working. Maybe it's not an issue in reality ...

I agree that's a bug, but no one should be calling resize_for_overwrite() without follow-on initialization of the new elements. The proposed change makes resize_for_overwrite() identical to resize() in the case of a non-trivially copyable class, which is a non-value add. So why not static_assert() in case of a non-trivially copyable value_type?

resize_for_overwrite() enables users to write fast code... it is inherently bug-prone if misused.

It's less safe, yes - but the question is how much less safe do we want to make it. What's the tradeoff of efficiency and safety.

There's a reason why there's no comparable member function on std::vector. So to me, having resize_for_overwrite() sounds like it's breaking the components of resize() into

1. buffer growth + back element pointer / size update
2. Initialization / construction; done manually... optimized in calling context.

If there are type_trait scenarios where resize_for_overwrite() does both 1. and 2., it may as well not exist in those contexts (maybe it should be SFINAE'd out or just static_assert()).

It can be/probably is useful for the API to be there, but be a no-op - so that it can be used in generic code (eg: in templates that don't know if they're operating on trivial or non-trivial element types, they call it, then carry on - for non-trivial types it doesn't do anything, for trivial ones it provides some performance improvement opportunities).

I wouldn't be entirely against SFINAE or static_asserting, but I don't think it adds much value - maybe it avoids callers accidentally using the API where it'd be no different than a plain resize and confusing readers/themselves about any extra performance benefit. (I'd /generally/ discourage folks from using resize_for_overwrite in cases where it's statically known to be no better than resize due to possible confusion about construction order, etc - while there are other API situations where I'd encourage use of distinct APIs that aren't any different but maybe make intent more clear (eg: a container with O(1) "length" you could argue that "empty()" is no better than "length() == 0", but I think the intent is beneficial even if it doesn't have any performance impact - but in the case of "resize_for_overwrite" I think it's a nuanced enough API (even in the safer version that's a no-op for non-trivially-constructible types) that it should raise eyebrows when you see it, and should only be seen when necessary so it can continue to be a "read the surrounding code carefully" signal)

[jplayer-nv]

In D115443#3252648, @dblaikie wrote:

It can be/probably is useful for the API to be there, but be a no-op - so that it can be used in generic code (eg: in templates that don't know if they're operating on trivial or non-trivial element types, they call it, then carry on - for non-trivial types it doesn't do anything, for trivial ones it provides some performance improvement opportunities).

I generally agree with everything you're saying. Just wanted to point out that calling resize_for_overwrite() in template code can be worked around with a helper template that has a POD specialization:

https://godbolt.org/z/5s5srhx4b

I do agree that keeping resize_for_overwrite() available for non-pod types simplifies templated callers by avoiding this extra layer, but the desired effect is still possible when resize_for_overwrite() is only callable on PODs.

Another argument to disable for non-POD is code evolution. Suppose you write proper code around a SmallVector of a POD type (call it SmallVector<Foo>). You use resize_for_overwrite() like you're supposed to. Later someone adds a constructor to Foo... suddenly your nice efficient code is now less efficient because of a very natural code evolution.

Leaving resize_for_overwrite() as an alias to resize() in that case silently continues to function with unnecessary overhead (assuming there's a follow-on init loop). If this evolution becomes a compile failure, then the writer of the Foo constructor must deal with all the old resize_for_overwrite() callsites (hopefully code them as efficiently as possible).

[dblaikie]

In D115443#3253101, @jplayer-nv wrote:

In D115443#3252648, @dblaikie wrote:

It can be/probably is useful for the API to be there, but be a no-op - so that it can be used in generic code (eg: in templates that don't know if they're operating on trivial or non-trivial element types, they call it, then carry on - for non-trivial types it doesn't do anything, for trivial ones it provides some performance improvement opportunities).

I generally agree with everything you're saying. Just wanted to point out that calling resize_for_overwrite() in template code can be worked around with a helper template that has a POD specialization:

https://godbolt.org/z/5s5srhx4b

I do agree that keeping resize_for_overwrite() available for non-pod types simplifies templated callers by avoiding this extra layer, but the desired effect is still possible when resize_for_overwrite() is only callable on PODs.

Yep - though once we'd done that we'd end up basically back where we were before in terms of the design space (though with a more explicit indication of which code is intentionally trying to be generic over POD and non-POD and which code is not, which has some value - but my tendency is that it doesn't feel like it carries enough benefit to be worth the added complexity)

Another argument to disable for non-POD is code evolution. Suppose you write proper code around a SmallVector of a POD type (call it SmallVector<Foo>). You use resize_for_overwrite() like you're supposed to. Later someone adds a constructor to Foo... suddenly your nice efficient code is now less efficient because of a very natural code evolution.

Leaving resize_for_overwrite() as an alias to resize() in that case silently continues to function with unnecessary overhead (assuming there's a follow-on init loop). If this evolution becomes a compile failure, then the writer of the Foo constructor must deal with all the old resize_for_overwrite() callsites (hopefully code them as efficiently as possible).

Yeah, if it wasn't a generic caller like above this would be an extra reminder to revisit this code, and maybe change it to "resize" if you realize the non-triviality is more important than the resize_for_overwrite (or to find another way rather than making it trivial). You could get this checking by adding a static_assert at the caller (much like you could get the genericity with a helper as you suggested) with a message explaining why this is important, etc.

I don't feel /amazingly/ strongly either way, but I think it's simpler (in implementation and callers) to have the same API & for it to be a no-op for trivially default constructible types.

llvm/include/llvm/ADT/SmallVector.h

601

Should this be is_trivially_constructible<T>?

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

601

IIUC, the intent is:

• Trivial to overwrite, for moving/copying values in right after.
• Trivial to destroy, if followed by a truncate because N was bigger than necessary.
• UB to read/use if not copied/overwritten.

This would allow it to skip constructors for types like SourceLocation, which is not trivially constructible, since it should be safe to overwrite or destroy an un-constructed value.

[dblaikie]

llvm/include/llvm/ADT/SmallVector.h

601

Ah, pity. :/ It'd be rather nice/simple/tidy if this only applied to trivially constructible things (where "new (x) T" is a no-op anyway) but I guess there's enough types we want to use this with that benefit from safe default constructibility in other places... :/ Ah well.

llvm/include/llvm/ADT/SmallVector.h

if (N == this->size())
       return;
 
     if (N < this->size()) {
       this->truncate(N);
       return;
     }
 
     this->reserve(N);
+    if (!ForOverwrite || !is_trivially_copyable<T>::value)
       for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
-      if (ForOverwrite)
-        new (&*I) T;
-      else
         new (&*I) T();
     this->set_size(N);
   }
 
 public:
   void resize(size_type N) { resizeImpl<false>(N); }
 
-  /// Like resize, but \ref T is POD, the new values won't be initialized.
+  /// Like resize, but if \ref T is trivially copyable, the new values won't be
+  /// initialized. This is similar in spirit to std::make_unique_for_overwrite,
+  /// but does not default initialize.
   void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
 
   /// Like resize, but requires that \p N is less than \a size().
   void truncate(size_type N) {
     assert(this->size() >= N && "Cannot increase size with truncate");
     this->destroy_range(this->begin() + N, this->end());
     this->set_size(N);
   }

llvm/unittests/ADT/SmallVectorTest.cpp

TEST(SmallVectorTest, ResizeForOverwrite) {
     V.push_back(5U);
     V.pop_back();
     V.resize_for_overwrite(V.size() + 1U);
     EXPECT_EQ(5U, V.back());
     V.pop_back();
     V.resize(V.size() + 1);
     EXPECT_EQ(0U, V.back());
   }
+  {
+    struct DefaultConstructible {
+      unsigned U = 10;
+    };
+    SmallVector<DefaultConstructible> V;
+    V.push_back({5U});
+    V.pop_back();
+    V.resize_for_overwrite(V.size() + 1U);
+    EXPECT_EQ(5U, V.back().U);
+    V.pop_back();
+    V.resize(V.size() + 1);
+    EXPECT_EQ(10U, V.back().U);
+  }
+  {
+    struct DefaultConstructible {
+      unsigned U = 20;
+      ~DefaultConstructible() {}
+    };
+    SmallVector<DefaultConstructible> V;
+    V.push_back({5U});
+    V.pop_back();
+    V.resize_for_overwrite(V.size() + 1U);
+    EXPECT_EQ(20U, V.back().U);
+    V.pop_back();
+    V.resize(V.size() + 1);
+    EXPECT_EQ(20U, V.back().U);
+  }
 }
 
 // Overflow past fixed size.
 TYPED_TEST(SmallVectorTest, OverflowTest) {
   SCOPED_TRACE("OverflowTest");
 
   // Push more elements than the fixed size.
   this->makeSequence(this->theVector, 1, 10);