Page MenuHomePhabricator

ADT: Shrink SmallVector by 8B on 64-bit platforms
ClosedPublic

Authored by dexonsmith on Jun 23 2018, 8:40 AM.

Details

Reviewers
rnk
Summary

Shrink sizeof(SmallVector) by 8B on 64-bit platforms by representing size and capacity directly as unsigned and calculating end() from begin() + size().

This limits the maximum size/capacity of a vector to UINT32_MAX.

A few notes:

  • I haven't profiled whether there is a compile-time hit, but I'm tempted to check the bots post-commit to check for regressions since this is no more branchy than before. Happy to be proactive if others think it's warranted.
  • I noticed that SmallVectorImpl::resetToSmall, used by SmallVectorImpl::operator=(SmallVectorImpl &&), drops the small capacity to 0. This is a little sad so I left behind a FIXME.
  • I lifted set_size() up to SmallVectorBase to use in place of setEnd().

Diff Detail

Event Timeline

dexonsmith created this revision.Jun 23 2018, 8:40 AM
dexonsmith edited the summary of this revision. (Show Details)

Updating the patch since I decided to just lift set_size() up to SmallVectorBase. My ASan-ified check-llvm and check-clang came back happy.

Does anyone feel this needs compile-time testing pre-commit?

rnk accepted this revision.Jul 19 2018, 2:27 PM

lgtm

Sorry, I was on vacation. Let's do this unsigned thing.

This revision is now accepted and ready to land.Jul 19 2018, 2:27 PM
dexonsmith closed this revision.Jul 19 2018, 3:38 PM

Committed in r337504.

dexonsmith reopened this revision.Jul 19 2018, 5:15 PM

Reverted in r337511 due to a bot failure:

#8 0x000055581f2895d8 (/b/sanitizer-x86_64-linux-autoconf/build/tsan_debug_build/bin/clang-7+0x1eb45d8)
#9 0x000055581f294323 llvm::ConstantAggrKeyType<llvm::ConstantArray>::create(llvm::ArrayType*) const /b/sanitizer-x86_64-linux-autoconf/build/llvm/lib/IR/ConstantsContext.h:409:0
#10 0x000055581f294323 llvm::ConstantUniqueMap<llvm::ConstantArray>::create(llvm::ArrayType*, llvm::ConstantAggrKeyType<llvm::ConstantArray>, std::pair<unsigned int, std::pair<llvm::ArrayType*, llvm::ConstantAggrKeyType<llvm::ConstantArray> > >&) /b/sanitizer-x86_64-linux-autoconf/build/llvm/lib/IR/ConstantsContext.h:635:0
#11 0x000055581f294323 llvm::ConstantUniqueMap<llvm::ConstantArray>::getOrCreate(llvm::ArrayType*, llvm::ConstantAggrKeyType<llvm::ConstantArray>) /b/sanitizer-x86_64-linux-autoconf/build/llvm/lib/IR/ConstantsContext.h:654:0
#12 0x000055581f2944cb llvm::ConstantArray::get(llvm::ArrayType*, llvm::ArrayRef<llvm::Constant*>) /b/sanitizer-x86_64-linux-autoconf/build/llvm/lib/IR/Constants.cpp:964:0
#13 0x000055581fa27e19 llvm::SmallVectorBase::size() const /b/sanitizer-x86_64-linux-autoconf/build/llvm/include/llvm/ADT/SmallVector.h:53:0
#14 0x000055581fa27e19 llvm::SmallVectorImpl<llvm::Constant*>::resize(unsigned long) /b/sanitizer-x86_64-linux-autoconf/build/llvm/include/llvm/ADT/SmallVector.h:347:0
#15 0x000055581fa27e19 (anonymous namespace)::EmitArrayConstant(clang::CodeGen::CodeGenModule&, clang::ConstantArrayType const*, llvm::Type*, unsigned int, llvm::SmallVectorImpl<llvm::Constant*>&, llvm::Constant*) /b/sanitizer-x86_64-linux-autoconf/build/llvm/tools/clang/lib/CodeGen/CGExprConstant.cpp:669:0

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/26526

This revision is now accepted and ready to land.Jul 19 2018, 5:15 PM

Hmm... that bot was green again in r337508, before I had a chance to revert. Maybe the blame-list was faulty.

Hmm... that bot was green again in r337508, before I had a chance to revert. Maybe the blame-list was faulty.

Committed again (unchanged) in r337514.

This patch is causing the http://lab.llvm.org:8011/builders/clang-cmake-aarch64-lld to fail. Unfortunately (for me) the failures seems to be restricted to older versions of clang and are not reproducible on Arm or X86. The buildbot itself is using the default /usr/bin/clang for Ubuntu 16.04 LTS (clang version 3.8.0-2ubuntu4 (tags/RELEASE_380/final). The failures go away if I use the 3.9.1 release (No failures on 4.0.1, 6.0.0 or built from master). At this stage I think that this could be a code-gen bug in the AArch64 backend of clang 3.8.1 so I don't think it is worth reverting, but I'm mentioning it here just in case there is a subtle problem that is only being exposed by that version.

The failures on the bot are all a llvm::unreachable in checkDeducedTemplateArguments() clang/lib/Sema/SemaTemplateDeduction.cpp:367. The only way that I can see that the unreachable gets hit is if there is some kind of corruption of the ArgKind.

A stripped down bit of code that will cause a clang built with 3.8.1 on AArch64 to fail is:

template<typename T, typename U>
class test_attach30 { };

template<typename T>
class test_attach30<T, int> { };

$ clang++ -fsyntax-only test.cpp
Invalid TemplateArgument Kind!
UNREACHABLE executed at
clang/lib/Sema/SemaTemplateDeduction.cpp:367!
dexonsmith added a subscriber: rnk.Jul 26 2018, 6:02 PM

Hi Peter,

Thanks for the heads up. I tend to agree with your intuition/conclusion (i.e., it seems like a bug in 3.8.1 and not worth reverting for). But, FYI, I'll be OOO for a couple of weeks. If for some reason your conclusion changes, please don't wait for my response before reverting. I already know it won't revert cleanly because I committed r337820 (https://reviews.llvm.org/D49163 https://reviews.llvm.org/D49163) on top, but it should be pretty easy to resolve the conflict (you should just have to fine-tune the static_asserts).

Good luck,
Duncan

dexonsmith closed this revision.Nov 11 2019, 1:42 PM

Looks like I forgot to close when recommitting in r337514.

Herald added a project: Restricted Project. · View Herald TranscriptNov 11 2019, 1:42 PM
Herald added a subscriber: ributzka. · View Herald Transcript