Page MenuHomePhabricator

ADT: Fix reference invalidation in SmallVector APIs that pass in a value
AbandonedPublic

Authored by dexonsmith on Nov 19 2020, 6:14 PM.

Details

Summary

Fix reference invalidation in SmallVector APIs that pass in a T, taking it by value when it's small enough and trivially copyable, and doing a pointer-to-index-to-pointer dance otherwise.

This doesn't fix all possible reference invalidation, but if it avoids the compile-time regressions from https://reviews.llvm.org/D87326 (which does fix them all) it seems like a good incremental step. The mental model also seems more clear than https://reviews.llvm.org/D91467 (which only fixed invalidation for small enough, trivially copyable T).

I'm currently building a few variants of clang (matching how the patches are sequenced in my local tree (probably they should be committed separately so they can be reverted individually if necessary, but I figured it made more sense to start with a single Phab review)) to test effects on compile-time:

  • baseline
  • fix only push_back and single-element insert (tied together since insert uses `push_back)
  • fix also N-element versions of append and insert (tied together since insert uses append)
  • fix also resize

I'll start with compiling a "big" file a few times (in the other review I used llvm/lib/Target/X86/X86ISelLowering.cpp), but I'm happy to do more work if it seems prudent.

Diff Detail

Event Timeline

dexonsmith created this revision.Nov 19 2020, 6:14 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 19 2020, 6:14 PM
dexonsmith requested review of this revision.Nov 19 2020, 6:14 PM

Compile-time results below for llvm/lib/Target/X86/X86ISelLowering.cpp:

$ for c in $(find refinvalid-*/build -type f -name clang-12); do du $c; cabs=$PWD/$c; (cd build && for n in {0..4}; do /usr/bin/time ../compile-big-file.sh $cabs; done); done
231952	refinvalid-baseline/build/bin/clang-12
       30.66 real        30.28 user         0.36 sys
       30.14 real        29.79 user         0.34 sys
       30.11 real        29.77 user         0.33 sys
       29.85 real        29.52 user         0.33 sys
       30.04 real        29.72 user         0.32 sys
232200	refinvalid-pushback+append+insert+resize/build/bin/clang-12
       30.55 real        30.20 user         0.34 sys
       30.59 real        30.27 user         0.31 sys
       30.14 real        29.80 user         0.33 sys
       30.02 real        29.69 user         0.33 sys
       30.11 real        29.80 user         0.30 sys
232200	refinvalid-pushback+append+insert/build/bin/clang-12
       30.30 real        29.93 user         0.36 sys
       30.45 real        30.11 user         0.34 sys
       30.14 real        29.82 user         0.31 sys
       30.74 real        30.40 user         0.32 sys
       30.86 real        30.52 user         0.33 sys
232224	refinvalid-pushback/build/bin/clang-12
       30.29 real        29.95 user         0.32 sys
       30.35 real        30.00 user         0.33 sys
       30.22 real        29.87 user         0.34 sys
       30.01 real        29.68 user         0.33 sys
       30.36 real        30.04 user         0.31 sys

Seems mostly in the noise to me. (top is baseline, next is this patch, next is just push_back, append, and insert, final is just push_back and single-element insert)

njames93 added inline comments.Nov 24 2020, 2:38 PM
llvm/include/llvm/ADT/SmallVector.h
698

Shouldn't this use the move constructor T(std::move(Elt)) Otherwise this adds the unnecessary requirement that T is copyable when calling the xvalue version of insert.

@njames93, thanks for the review, I've responded inline (I was out last week).

llvm/include/llvm/ADT/SmallVector.h
286–294

Note: TakesParamByValue is always false when T is not copy-constructible.

698

The enable_if restricts this to when TakesParamByValue, which already requires that T is copyable (see note above). Do you think an expanded comment would be a good idea?

Or, maybe I've missed your point, let me know if I didn't understand.

njames93 added inline comments.Nov 30 2020, 2:35 PM
llvm/include/llvm/ADT/SmallVector.h
698

No I missed the point, disregard it.

dexonsmith added inline comments.Dec 3 2020, 5:31 PM
llvm/include/llvm/ADT/SmallVector.h
698

Just to confirm, do you think this is good to commit?

@njames93, do you have any other concerns? Do you think this is a reasonable approach?

njames93 added a subscriber: nikic.Dec 18 2020, 4:03 AM

I'd like to get @nikic's input first, but I have no issues here.

Here are the number I see for this patch:

Instructions retired: https://llvm-compile-time-tracker.com/compare.php?from=2af2f58ec09257d65a2a6f99f833a1b242d434a3&to=1d9e441fa77400d0a97a371b4d9bdbf9c6979266&stat=instructions Geomean 0.2% regression, which is much better than the previous versions (which were something like 1.5%)
Max-RSS: https://llvm-compile-time-tracker.com/compare.php?from=2af2f58ec09257d65a2a6f99f833a1b242d434a3&to=1d9e441fa77400d0a97a371b4d9bdbf9c6979266&stat=max-rss Geomean 0.3% regression (changes here are always a bit mysterious...)
Code size for clang binary: From 82761400 to 82820191, which is a 0.07% increase, which is negligible. (Code size increase with GCC host compiler was a big issue in some of the earlier versions.)

Overall the impact looks reasonable to me now.

Great, thanks for doing that analysis @nikic!

@njames93, I'll land this once you accept.

njames93 accepted this revision.Dec 22 2020, 9:18 AM

Great, thanks for doing that analysis @nikic!

@njames93, I'll land this once you accept.

LGTM, but I'm not the gatekeeper of ADT.

This revision is now accepted and ready to land.Dec 22 2020, 9:18 AM
dblaikie added inline comments.Dec 22 2020, 11:02 AM
llvm/include/llvm/ADT/SmallVector.h
141

Absurd C++ pedantry, but I believe op< on pointers to unrelated objects is unspecified in C++? ("If two pointers are not specified to compare greater or compare equal, the result of the comparison is unspecified. An unspecified result may be nondeterministic, and need not be consistent even for multiple evaluations of the same expression with the same operands in the same execution of the program" - https://en.cppreference.com/w/cpp/language/operator_comparison) but std::less is specified to handle this case: "A specialization of std::less for any pointer type yields a strict total order, even if the built-in operator< does not." - https://en.cppreference.com/w/cpp/utility/functional/less)

Because C++ is fun like that.

334

Is there any case where 'Elt' could be contained within a subobject of an element of the SmallVector, while not being an element itself? I guess not, because T can't contain (directly) another T - but asking just in case I've missed a possibility (if this were true, then an index would be inadequate for persisting 'Elt' across the grow operation).

454–467

Is this text identical between the trivially copyable and non-trivially copyable specializations? If so, can it be shared at all? I guess it'd need to be in a CRTP base placed between these specializations and SmallVectorTemplateCommon, and possibly not worth the added complexity?

677–686

Perhaps all this infrastructure and SFINAE might merit a separate patch? (breaking this patch up into separate changes for adding reference validity for each independent operation might be nice in general, but especially this part/set of changes, if they can be separate - it'd also make some of the other changes a bit clearer, once the reserveForAndGetAddress is added, subsequent changes would be "port to use that, and add test")

But I know that can be a hassle to make, manage the reviews, etc, so not vital by any means.

llvm/unittests/ADT/SmallVectorTest.cpp
1083–1085

By this you mean "sanitizers would catch use-after-free if this support were missing/broken"? Otherwise this reads as though it might be a sanitizer-only death test, specifically checking that misuse fails/is diagnosed, which it isn't.

Oh, one other question: How's all this implementation strategy compared to std::vector? Be nice to be relying on prior art where possible.

Thanks for the review!

A few responses inline; I'll try to update the patch tomorrow.

Regarding number of patches, this is already split into multiple patches in my local tree:

  1. Fix invalidation for push_back and insert (one), the latter of which sometimes calls push_back.
  2. Fix invalidation for append and insert (N), the latter of which sometimes calls append.
  3. Fix invalidation for resize.

(The various helpers get added as needed.)

Happy to split it now that the performance has been validated. I'll probably find time to rebase and post tomorrow -- let me know if there's something else you'd like split out.

Oh, one other question: How's all this implementation strategy compared to std::vector? Be nice to be relying on prior art where possible.

Libc++'s std::vector uses a more general, split buffer approach that fixes all the invalidation, quite similar to https://reviews.llvm.org/D87326. Unfortunately that was reverted due to compile-time and code size regressions. My thinking is that we can try to land https://reviews.llvm.org/D87326 again after this patch (series) to fix the remaining invalidation (and that the regressions may be less bad / acceptable since the common cases in this patch are handled in a more lightweight manner).

llvm/include/llvm/ADT/SmallVector.h
141

Hah; I wondered about this, but couldn't find it in the standard, so ended up leaving it as it was in the prep patch. I'll fix in a prep commit.

334

Correct, not possible. As a result this code wouldn't handle V.emplace_back(subobject_reference), but it's not used for that at this point. (We could probably handle emplace_back somehow with this technique, but I'm not sure it would still be lightweight / worth it.)

454–467

Yes, it's identical. I can take a look to see how bad it is with CRTP.

677–686

Very happy to split this up; just wanted to start with the holistic patch to get numbers (it's already split up locally).

llvm/unittests/ADT/SmallVectorTest.cpp
1083–1085

Correct; not a death test, but I expect the sanitizers to catch the problem if the implementation is wrong.

Thanks for the review!

A few responses inline; I'll try to update the patch tomorrow.

Regarding number of patches, this is already split into multiple patches in my local tree:

  1. Fix invalidation for push_back and insert (one), the latter of which sometimes calls push_back.
  2. Fix invalidation for append and insert (N), the latter of which sometimes calls append.
  3. Fix invalidation for resize.

(The various helpers get added as needed.)

Happy to split it now that the performance has been validated. I'll probably find time to rebase and post tomorrow -- let me know if there's something else you'd like split out.

Makes sense/sounds good.

Oh, one other question: How's all this implementation strategy compared to std::vector? Be nice to be relying on prior art where possible.

Libc++'s std::vector uses a more general, split buffer approach that fixes all the invalidation, quite similar to https://reviews.llvm.org/D87326. Unfortunately that was reverted due to compile-time and code size regressions. My thinking is that we can try to land https://reviews.llvm.org/D87326 again after this patch (series) to fix the remaining invalidation (and that the regressions may be less bad / acceptable since the common cases in this patch are handled in a more lightweight manner).

*thumbs up*

llvm/unittests/ADT/SmallVectorTest.cpp
1083–1085

Would probably be good to rephrase this comment (& elsewhere the same text appears) to clarify. I'd find this confusing if/when I come across it in the future.

dexonsmith abandoned this revision.Dec 23 2020, 2:40 PM

Thanks again for the reviews here. For landing this (and a bit more review from @dblaikie) I've split this up into:

"Abandoning" this one, but that patch series gets to essentially the same end result (modulo incorporating some feedback from here).