Author name = James Player
Email = james.w.player@gmail.com

Ping @kazu for commit. If you're not the right person to ask, could you kindly suggest someone else?

Thanks for the review @kazu

In D134076#3797962, @dblaikie wrote:

My gut reaction is that this is quite a lot of API surface area to add without current or near-future planned usage.

Any chance you're interested in proposing this as part of a patch series to at least migrate some of the existing iterator-adaptor or custom algorithms to this usage? (@kazu - maybe this'd be of some interest to you too?)

I'd be happy to break this down into bite-sized chunks. Is discourse the right place to iterate on the details of such a patch series? I can start with the ability to default construct and copy-assign existing iterators which carry a callable.

I wrote this code for a private target (as well as for a non-LLVM compiler framework), and was wondering if some form of it would be useful upstream (I fully expect some high-level refactoring). It seems strange that there are things defined in STLExtras.h which mimic the behavior of std::ranges elements but are named differently (mapped_iterator vs transform_iterator for example).

In D112175#3482069, @dexonsmith wrote:

If your host toolchain has C++17, I'd be curious if the regression goes away when you switch to that mode and use if constexpr.

I'd also be curious how this performs on your benchmark (after you fix the compiler errors / etc.):

template <class U, std::enable_if_t<U::TakesParamByValue, bool> = false>
static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
                                                 size_t N) {
  size_t NewSize = This->size() + N;
  if (LLVM_LIKELY(NewSize <= This->capacity()))
    return &Elt;

  This->grow(NewSize);
  return &Elt;
}
template <class U, std::enable_if_t<!U::TakesParamByValue, bool> = false>
static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
                                                 size_t N) {
  size_t NewSize = This->size() + N;
  if (LLVM_LIKELY(NewSize <= This->capacity()))
    return &Elt;

  bool ReferencesStorage = false;
  int64_t Index = -1;
  if (!U::TakesParamByValue) {
    if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {
      ReferencesStorage = true;
      Index = &Elt - This->begin();
    }
  }
  This->grow(NewSize);
  return ReferencesStorage ? This->begin() + Index : &Elt;
}

Seems like it should be mostly equivalent to your solution, but the specialization is at a lower level where it's easy to verify the logic is equivalent... and it's also still obvious how if constexpr would apply once we have it.

In D112175#3481996, @dexonsmith wrote:

Ideally the outer if would be if constexpr(!U::TakesParamByValue) but that needs to wait for C++17.

The current implementation is easy to verify since the check is just in one place. Is it just a synthetic benchmark where it's causing a slowdown? Or, can we help the optimizer along somehow without changing the layering? (I don't feel strongly attached to exact design of the current thing, but IIRC it took some compromise at the time to make everyone happy. But I could be remembering the patch series incorrectly.)

[ RUN      ] StaticVsSmall/0.TimedStaticVector
[       OK ] StaticVsSmall/0.TimedStaticVector (371 ms)
[ RUN      ] StaticVsSmall/0.TimedSmallVector
[       OK ] StaticVsSmall/0.TimedSmallVector (596 ms)

Which demonstrates that simple insertions are significantly faster (almost 38%) with the StaticVector compared to a SmallVector which stays within its small buffer limit.

Just to give a concrete example of what I believe to be the benefit behind StaticVector, I ran this contrived test pitting SmallVector<uint64_t,N> vs StaticVector<uint64_t,N> (with a few tweaks to ensure the push_back param is passsed by value like in SmallVector):

TYPED_TEST(StaticVsSmall, TimedStaticVector) {
  const size_t N = this->NumBuiltinElts(this->TheStaticVector);
  for (int I = 0; I < OutterLimit; ++I) {
    this->TheStaticVector.clear();
    for (int J = 0; J < N; ++J) {
      this->TheStaticVector.push_back(I + J);
    }
  }
}

Call llvm::consumeError() when an Error is returned in the StaticVector unit test.

Resurrecting this review for the following:

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

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.

Older MSVC has trouble with is_trivially_copyable

we also do not have a LLVM version of that implementation.

Here's another example of a possible StaticVector conversion:

In D112175#3080023, @mgorny wrote:

I'd grep for std::array<llvm::Optional<...>, ...> — I suppose this would be a good replacement for at least some instances of that.

• Define the MSVC visualizer for StaticVector.
• Bind StaticVector a simple yaml sequence.
• Change StaticVector::Capacity to an enum to make it available from the visualizer.
• Substitute some SmallVectors which never grow beyond inline storage.

I don't see too many simple substitutions in target independent code, although this class has a SmallVector which never exceeds the inline storage (drop-in type substitution + with YAML binding works):

Reverse include order of ArrayRef.h and StaticVector.h in unit test code to address pre-merge check failure.

In D112175#3076343, @tschuett wrote:

could fallible operations ala push_back return an llvm::error?

Quick reminder that I don't have commit access, and need someone to commit this patch on my behalf. Thanks!

Added !defined(__clang__) conditions to static_assert preprocessing. Also added large comment describing the mental gymnastics of the OptionalStorage specialization condition.

I just triaged the gcc 5.4 build break. It appears that std::is_trivially_copy_constructible<T> instantiates the copy constructor (which is... strange). So we can't query a compile-time property without the compiler forcing instantiation of the deleted copy constructor in this case.

Taking a look at the gcc 5.4 failure now.

@dblaikie, I don't have commit access. Are you the right person to ask to commit this patch on my behalf?

Properly update the patch to incorporate the separate static_asserts.

Split conditions into individual static_asserts.

With current change, pre-merge checks pass. I think I've resolved all issues / requests.

Added preprocessing around static_asserts added to OptionalTests.cpp to only include them in recent windows builds.

1. Expanded the check for the trivial specialization of OptionalStorage
2. Formatted the OptionalStorage template list.
3. Added a test to ensure that deleting move constructor / assignment will still choose the trivial OptionalStorage specialization.
4. Added requests static_asserts to validate class properties in Optional testing code.

Clarified comments above deleted volatile copy constructor / assignment in test classes.

any idea why this only fails for MSVC? It'd be good to understand more why this didn't trip up other builds so we can avoid those sort of divergences in the future, perhaps.

1. Use std::is_trivially_copyable instead of llvm::is_trivially_copyable in Optional storage template specialization logic.
2. Added test cases to OptionalTest.cpp which will fail compilation (verified on MSVC 16.8.3) if new conditions are absent from Optional storage template specialization logic.

In D92514#2461810, @dblaikie wrote:

In D92514#2461808, @jplayer-nv wrote:

I spent some time root causing an llvm::Optional build error on MSVC 16.8.3 today related to using std::is_trivially_copyable to set llvm::is_trivially_copyable<T>::value. It looks like the same failure mentioned in this review.

62>C:\src\ocg_llvm\llvm-project\llvm\include\llvm/ADT/BreadthFirstIterator.h(96,12): error C2280: 'llvm::Optional<std::pair<std::pair<unsigned int,llvm::Graph<4>::NodeSubset> *,llvm::Optional<llvm::Graph<4>::ChildIterator>>> &llvm::Optional<std::pair<std::pair<unsigned int,llvm::Graph<4>::NodeSubset> *,llvm::Optional<llvm::Graph<4>::ChildIterator>>>::operator =(const llvm::Optional<std::pair<std::pair<unsigned int,llvm::Graph<4>::NodeSubset> *,llvm::Optional<llvm::Graph<4>::ChildIterator>>> &)': attempting to reference a deleted function (compiling source file C:\src\ocg_llvm\llvm-project\llvm\unittests\ADT\BreadthFirstIteratorTest.cpp)
...

The "trivial" specialization of optional_detail::OptionalStorage assumes that the value type is trivially copy constructible and trivially copy assignable. The specialization is invoked based on a check of is_trivially_copyable, which does not imply both is_trivially_copy_assignable and is_trivially_copy_constructible are true.

According to the spec, a deleted assignment operator does not make is_trivially_copyable false. So I think all these properties need to be checked explicitly in order to specialize OptionalStorage to the "trivial" version:

/// Storage for any type.
template <typename T, bool = std::is_trivially_copy_constructible<T>::value
                          && std::is_trivially_copy_assignable<T>::value>
class OptionalStorage {

Above fixed my build break in MSVC, but I think we might need to explicitly check is_trivially_copy_constructible too since it might be possible the copy constructor is deleted.

All sounds pretty plausible to me - if you want to send a patch to add those checks?

I spent some time root causing an llvm::Optional build error on MSVC 16.8.3 today related to using std::is_trivially_copyable to set llvm::is_trivially_copyable<T>::value. It looks like the same failure mentioned in this review.