Page MenuHomePhabricator

[SmallVector] Allow SmallVector<T>
ClosedPublic

Authored by silvas on Dec 2 2020, 4:13 PM.

Details

Summary

This patch adds a capability to SmallVector to decide a number of inlined
elements automatically. The policy is:

  • A minimum of 1 inlined elements, with more as long as sizeof(SmallVector<T>) <= 64.
  • If sizeof(T) is "too big", then trigger a static_assert: this dodges the more pathological cases

This is expected to systematically improve SmallVector use in the
LLVM codebase, which has historically been plagued by semi-arbitrary /
cargo culted N parameters, often leading to bad outcomes due to
excessive sizeof(SmallVector<T, N>). This default also makes
programming more convenient by avoiding edit/rebuild cycles due to
forgetting to type the N parameter.

Diff Detail

Event Timeline

silvas created this revision.Dec 2 2020, 4:13 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 2 2020, 4:13 PM
silvas requested review of this revision.Dec 2 2020, 4:13 PM

I'm generally good with this in terms of incremental forward progress. Still don't feel super great about the "at least 1" thing and the disparate storage limits (preferred size versus break-because-too-big size), but given the varied opinions, seems like the incremental progress is probably the best path forward for now. (perfect being the enemy of good and all that)

llvm/include/llvm/ADT/SmallVector.h
994

Could/should this be sizeof(SmallVector<T, 0>)? So that if we move members around for any reason (it's SmallVector, so it's not likely to get willy-nilly refactoring of this kind, but just on principle) this would still correctly capture the size of the SmallVector base footprint before inline buffer?

dexonsmith added inline comments.Dec 2 2020, 4:27 PM
llvm/include/llvm/ADT/SmallVector.h
994

There could be difference, if it matters (not sure it does), since there's an alignas on SmallVector<T, 0> (IIRC, somehow used in isSmall).

silvas updated this revision to Diff 309105.Dec 2 2020, 4:50 PM

Use SmallVector<T, 0> as the header size.

silvas marked 2 inline comments as done.Dec 2 2020, 4:54 PM
silvas added inline comments.
llvm/include/llvm/ADT/SmallVector.h
994

Good catch!

silvas marked an inline comment as done.Dec 2 2020, 5:04 PM

I'm generally good with this in terms of incremental forward progress. Still don't feel super great about the "at least 1" thing and the disparate storage limits (preferred size versus break-because-too-big size), but given the varied opinions, seems like the incremental progress is probably the best path forward for now. (perfect being the enemy of good and all that)

Thanks Dave. Totally agreed that this is a mismash of compromises but that even in this form it still helps push the discussion forward towards rationalizing our vector/smallvector usage. Once we rationalize it, we will hopefully be able to circle back and put this on a more principled foundation consistent with our overarching conclusions.

lattner accepted this revision.Dec 2 2020, 9:17 PM

the patch looks good to me, I think the most important thing here is to nail down the programmer manual dox to be airtight :-)

llvm/docs/ProgrammersManual.rst
1527

I expand on what reasonable means here. I'd say "reasonable for inline allocation on the stack" or something like that, maybe even give the target number of inline bytes so people have a mental model.

llvm/include/llvm/ADT/SmallVector.h
990

Huh, interesting approach, I agree with the comment, I didn't think about it that way!

This revision is now accepted and ready to land.Dec 2 2020, 9:17 PM
silvas updated this revision to Diff 309305.Dec 3 2020, 10:41 AM
silvas marked an inline comment as done.

Address Chris's comments about the docs.

llvm/docs/ProgrammersManual.rst
1527

Good point. I incorporated your suggestions.

dexonsmith accepted this revision.Dec 3 2020, 10:56 AM

This LGTM too. Thanks for working through all the discussion on this!

lattner accepted this revision.Dec 3 2020, 10:58 AM

Thx Sean!

silvas updated this revision to Diff 309410.Dec 3 2020, 5:13 PM

Replace constexpr function with old-school class with static members.

It looks like GCC5 does not support multi-statement constexpr functions.

This revision was landed with ongoing or failed builds.Dec 3 2020, 5:22 PM
This revision was automatically updated to reflect the committed changes.