From 5839a14828f31f1c2876003677e0ce8e28544b1f Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Mon, 18 Mar 2024 07:11:24 -0700 Subject: Add a feature to container_internal::Layout that lets you specify some array sizes at compile-time as template parameters. This can make offset and size calculations faster. In particular, it seems to always improve the performance of AllocSize(), and it sometimes improves the performance of other functions, e.g. when the Layout object outlives the function that created it. PiperOrigin-RevId: 616817169 Change-Id: Id1d318d7d2af68783f9f59090d89c642be6ae558 --- absl/container/internal/layout_test.cc | 396 ++++++++++++++++++++++++++++++++- 1 file changed, 392 insertions(+), 4 deletions(-) (limited to 'absl/container/internal/layout_test.cc') diff --git a/absl/container/internal/layout_test.cc b/absl/container/internal/layout_test.cc index ae55cf7e..47fc9f33 100644 --- a/absl/container/internal/layout_test.cc +++ b/absl/container/internal/layout_test.cc @@ -68,9 +68,7 @@ struct alignas(8) Int128 { // int64_t is *not* 8-byte aligned on all platforms! struct alignas(8) Int64 { int64_t a; - friend bool operator==(Int64 lhs, Int64 rhs) { - return lhs.a == rhs.a; - } + friend bool operator==(Int64 lhs, Int64 rhs) { return lhs.a == rhs.a; } }; // Properties of types that this test relies on. @@ -271,6 +269,35 @@ TEST(Layout, Offsets) { } } +TEST(Layout, StaticOffsets) { + using L = Layout; + { + using SL = L::WithStaticSizes<>; + EXPECT_THAT(SL::Partial().Offsets(), ElementsAre(0)); + EXPECT_THAT(SL::Partial(5).Offsets(), ElementsAre(0, 8)); + EXPECT_THAT(SL::Partial(5, 3, 1).Offsets(), ElementsAre(0, 8, 24)); + EXPECT_THAT(SL(5, 3, 1).Offsets(), ElementsAre(0, 8, 24)); + } + { + using SL = L::WithStaticSizes<5>; + EXPECT_THAT(SL::Partial().Offsets(), ElementsAre(0, 8)); + EXPECT_THAT(SL::Partial(3).Offsets(), ElementsAre(0, 8, 24)); + EXPECT_THAT(SL::Partial(3, 1).Offsets(), ElementsAre(0, 8, 24)); + EXPECT_THAT(SL(3, 1).Offsets(), ElementsAre(0, 8, 24)); + } + { + using SL = L::WithStaticSizes<5, 3>; + EXPECT_THAT(SL::Partial().Offsets(), ElementsAre(0, 8, 24)); + EXPECT_THAT(SL::Partial(1).Offsets(), ElementsAre(0, 8, 24)); + EXPECT_THAT(SL(1).Offsets(), ElementsAre(0, 8, 24)); + } + { + using SL = L::WithStaticSizes<5, 3, 1>; + EXPECT_THAT(SL::Partial().Offsets(), ElementsAre(0, 8, 24)); + EXPECT_THAT(SL().Offsets(), ElementsAre(0, 8, 24)); + } +} + TEST(Layout, AllocSize) { { using L = Layout; @@ -295,6 +322,30 @@ TEST(Layout, AllocSize) { } } +TEST(Layout, StaticAllocSize) { + using L = Layout; + { + using SL = L::WithStaticSizes<>; + EXPECT_EQ(136, SL::Partial(3, 5, 7).AllocSize()); + EXPECT_EQ(136, SL(3, 5, 7).AllocSize()); + } + { + using SL = L::WithStaticSizes<3>; + EXPECT_EQ(136, SL::Partial(5, 7).AllocSize()); + EXPECT_EQ(136, SL(5, 7).AllocSize()); + } + { + using SL = L::WithStaticSizes<3, 5>; + EXPECT_EQ(136, SL::Partial(7).AllocSize()); + EXPECT_EQ(136, SL(7).AllocSize()); + } + { + using SL = L::WithStaticSizes<3, 5, 7>; + EXPECT_EQ(136, SL::Partial().AllocSize()); + EXPECT_EQ(136, SL().AllocSize()); + } +} + TEST(Layout, SizeByIndex) { { using L = Layout; @@ -370,6 +421,27 @@ TEST(Layout, Sizes) { } } +TEST(Layout, StaticSize) { + using L = Layout; + { + using SL = L::WithStaticSizes<>; + EXPECT_THAT(SL::Partial().Sizes(), ElementsAre()); + EXPECT_THAT(SL::Partial(3).Size<0>(), 3); + EXPECT_THAT(SL::Partial(3).Size(), 3); + EXPECT_THAT(SL::Partial(3).Sizes(), ElementsAre(3)); + EXPECT_THAT(SL::Partial(3, 5, 7).Size<0>(), 3); + EXPECT_THAT(SL::Partial(3, 5, 7).Size(), 3); + EXPECT_THAT(SL::Partial(3, 5, 7).Size<2>(), 7); + EXPECT_THAT(SL::Partial(3, 5, 7).Size(), 7); + EXPECT_THAT(SL::Partial(3, 5, 7).Sizes(), ElementsAre(3, 5, 7)); + EXPECT_THAT(SL(3, 5, 7).Size<0>(), 3); + EXPECT_THAT(SL(3, 5, 7).Size(), 3); + EXPECT_THAT(SL(3, 5, 7).Size<2>(), 7); + EXPECT_THAT(SL(3, 5, 7).Size(), 7); + EXPECT_THAT(SL(3, 5, 7).Sizes(), ElementsAre(3, 5, 7)); + } +} + TEST(Layout, PointerByIndex) { alignas(max_align_t) const unsigned char p[100] = {0}; { @@ -720,6 +792,61 @@ TEST(Layout, MutablePointers) { } } +TEST(Layout, StaticPointers) { + alignas(max_align_t) const unsigned char p[100] = {0}; + using L = Layout; + { + const auto x = L::WithStaticSizes<>::Partial(); + EXPECT_EQ(std::make_tuple(x.Pointer<0>(p)), + Type>(x.Pointers(p))); + } + { + const auto x = L::WithStaticSizes<>::Partial(1); + EXPECT_EQ(std::make_tuple(x.Pointer<0>(p), x.Pointer<1>(p)), + (Type>(x.Pointers(p)))); + } + { + const auto x = L::WithStaticSizes<1>::Partial(); + EXPECT_EQ(std::make_tuple(x.Pointer<0>(p), x.Pointer<1>(p)), + (Type>(x.Pointers(p)))); + } + { + const auto x = L::WithStaticSizes<>::Partial(1, 2, 3); + EXPECT_EQ( + std::make_tuple(x.Pointer<0>(p), x.Pointer<1>(p), x.Pointer<2>(p)), + (Type>( + x.Pointers(p)))); + } + { + const auto x = L::WithStaticSizes<1>::Partial(2, 3); + EXPECT_EQ( + std::make_tuple(x.Pointer<0>(p), x.Pointer<1>(p), x.Pointer<2>(p)), + (Type>( + x.Pointers(p)))); + } + { + const auto x = L::WithStaticSizes<1, 2>::Partial(3); + EXPECT_EQ( + std::make_tuple(x.Pointer<0>(p), x.Pointer<1>(p), x.Pointer<2>(p)), + (Type>( + x.Pointers(p)))); + } + { + const auto x = L::WithStaticSizes<1, 2, 3>::Partial(); + EXPECT_EQ( + std::make_tuple(x.Pointer<0>(p), x.Pointer<1>(p), x.Pointer<2>(p)), + (Type>( + x.Pointers(p)))); + } + { + const L::WithStaticSizes<1, 2, 3> x; + EXPECT_EQ( + std::make_tuple(x.Pointer<0>(p), x.Pointer<1>(p), x.Pointer<2>(p)), + (Type>( + x.Pointers(p)))); + } +} + TEST(Layout, SliceByIndexSize) { alignas(max_align_t) const unsigned char p[100] = {0}; { @@ -769,7 +896,6 @@ TEST(Layout, SliceByTypeSize) { EXPECT_EQ(7, L(3, 5, 7).Slice(p).size()); } } - TEST(Layout, MutableSliceByIndexSize) { alignas(max_align_t) unsigned char p[100] = {0}; { @@ -820,6 +946,39 @@ TEST(Layout, MutableSliceByTypeSize) { } } +TEST(Layout, StaticSliceSize) { + alignas(max_align_t) const unsigned char cp[100] = {0}; + alignas(max_align_t) unsigned char p[100] = {0}; + using L = Layout; + using SL = L::WithStaticSizes<3, 5>; + + EXPECT_EQ(3, SL::Partial().Slice<0>(cp).size()); + EXPECT_EQ(3, SL::Partial().Slice(cp).size()); + EXPECT_EQ(3, SL::Partial(7).Slice<0>(cp).size()); + EXPECT_EQ(3, SL::Partial(7).Slice(cp).size()); + + EXPECT_EQ(5, SL::Partial().Slice<1>(cp).size()); + EXPECT_EQ(5, SL::Partial().Slice(cp).size()); + EXPECT_EQ(5, SL::Partial(7).Slice<1>(cp).size()); + EXPECT_EQ(5, SL::Partial(7).Slice(cp).size()); + + EXPECT_EQ(7, SL::Partial(7).Slice<2>(cp).size()); + EXPECT_EQ(7, SL::Partial(7).Slice(cp).size()); + + EXPECT_EQ(3, SL::Partial().Slice<0>(p).size()); + EXPECT_EQ(3, SL::Partial().Slice(p).size()); + EXPECT_EQ(3, SL::Partial(7).Slice<0>(p).size()); + EXPECT_EQ(3, SL::Partial(7).Slice(p).size()); + + EXPECT_EQ(5, SL::Partial().Slice<1>(p).size()); + EXPECT_EQ(5, SL::Partial().Slice(p).size()); + EXPECT_EQ(5, SL::Partial(7).Slice<1>(p).size()); + EXPECT_EQ(5, SL::Partial(7).Slice(p).size()); + + EXPECT_EQ(7, SL::Partial(7).Slice<2>(p).size()); + EXPECT_EQ(7, SL::Partial(7).Slice(p).size()); +} + TEST(Layout, SliceByIndexData) { alignas(max_align_t) const unsigned char p[100] = {0}; { @@ -1230,6 +1389,39 @@ TEST(Layout, MutableSliceByTypeData) { } } +TEST(Layout, StaticSliceData) { + alignas(max_align_t) const unsigned char cp[100] = {0}; + alignas(max_align_t) unsigned char p[100] = {0}; + using L = Layout; + using SL = L::WithStaticSizes<3, 5>; + + EXPECT_EQ(0, Distance(cp, SL::Partial().Slice<0>(cp).data())); + EXPECT_EQ(0, Distance(cp, SL::Partial().Slice(cp).data())); + EXPECT_EQ(0, Distance(cp, SL::Partial(7).Slice<0>(cp).data())); + EXPECT_EQ(0, Distance(cp, SL::Partial(7).Slice(cp).data())); + + EXPECT_EQ(4, Distance(cp, SL::Partial().Slice<1>(cp).data())); + EXPECT_EQ(4, Distance(cp, SL::Partial().Slice(cp).data())); + EXPECT_EQ(4, Distance(cp, SL::Partial(7).Slice<1>(cp).data())); + EXPECT_EQ(4, Distance(cp, SL::Partial(7).Slice(cp).data())); + + EXPECT_EQ(24, Distance(cp, SL::Partial(7).Slice<2>(cp).data())); + EXPECT_EQ(24, Distance(cp, SL::Partial(7).Slice(cp).data())); + + EXPECT_EQ(0, Distance(p, SL::Partial().Slice<0>(p).data())); + EXPECT_EQ(0, Distance(p, SL::Partial().Slice(p).data())); + EXPECT_EQ(0, Distance(p, SL::Partial(7).Slice<0>(p).data())); + EXPECT_EQ(0, Distance(p, SL::Partial(7).Slice(p).data())); + + EXPECT_EQ(4, Distance(p, SL::Partial().Slice<1>(p).data())); + EXPECT_EQ(4, Distance(p, SL::Partial().Slice(p).data())); + EXPECT_EQ(4, Distance(p, SL::Partial(7).Slice<1>(p).data())); + EXPECT_EQ(4, Distance(p, SL::Partial(7).Slice(p).data())); + + EXPECT_EQ(24, Distance(p, SL::Partial(7).Slice<2>(p).data())); + EXPECT_EQ(24, Distance(p, SL::Partial(7).Slice(p).data())); +} + MATCHER_P(IsSameSlice, slice, "") { return arg.size() == slice.size() && arg.data() == slice.data(); } @@ -1339,6 +1531,43 @@ TEST(Layout, MutableSlices) { } } +TEST(Layout, StaticSlices) { + alignas(max_align_t) const unsigned char cp[100] = {0}; + alignas(max_align_t) unsigned char p[100] = {0}; + using SL = Layout::WithStaticSizes<1, 2>; + { + const auto x = SL::Partial(); + EXPECT_THAT( + (Type, Span>>( + x.Slices(cp))), + Tuple(IsSameSlice(x.Slice<0>(cp)), IsSameSlice(x.Slice<1>(cp)))); + EXPECT_THAT((Type, Span>>(x.Slices(p))), + Tuple(IsSameSlice(x.Slice<0>(p)), IsSameSlice(x.Slice<1>(p)))); + } + { + const auto x = SL::Partial(3); + EXPECT_THAT((Type, Span, + Span>>(x.Slices(cp))), + Tuple(IsSameSlice(x.Slice<0>(cp)), IsSameSlice(x.Slice<1>(cp)), + IsSameSlice(x.Slice<2>(cp)))); + EXPECT_THAT((Type, Span, Span>>( + x.Slices(p))), + Tuple(IsSameSlice(x.Slice<0>(p)), IsSameSlice(x.Slice<1>(p)), + IsSameSlice(x.Slice<2>(p)))); + } + { + const SL x(3); + EXPECT_THAT((Type, Span, + Span>>(x.Slices(cp))), + Tuple(IsSameSlice(x.Slice<0>(cp)), IsSameSlice(x.Slice<1>(cp)), + IsSameSlice(x.Slice<2>(cp)))); + EXPECT_THAT((Type, Span, Span>>( + x.Slices(p))), + Tuple(IsSameSlice(x.Slice<0>(p)), IsSameSlice(x.Slice<1>(p)), + IsSameSlice(x.Slice<2>(p)))); + } +} + TEST(Layout, UnalignedTypes) { constexpr Layout x(1, 2, 3); alignas(max_align_t) unsigned char p[x.AllocSize() + 1]; @@ -1377,6 +1606,36 @@ TEST(Layout, Alignment) { static_assert(Layout::Alignment() == 8, ""); static_assert(Layout::Alignment() == 8, ""); static_assert(Layout::Alignment() == 8, ""); + static_assert(Layout::Alignment() == 8, ""); + static_assert( + Layout>::WithStaticSizes<>::Alignment() == 64, ""); + static_assert( + Layout>::WithStaticSizes<2>::Alignment() == 64, ""); +} + +TEST(Layout, StaticAlignment) { + static_assert(Layout::WithStaticSizes<>::Alignment() == 1, ""); + static_assert(Layout::WithStaticSizes<0>::Alignment() == 1, ""); + static_assert(Layout::WithStaticSizes<7>::Alignment() == 1, ""); + static_assert(Layout::WithStaticSizes<>::Alignment() == 4, ""); + static_assert(Layout::WithStaticSizes<0>::Alignment() == 4, ""); + static_assert(Layout::WithStaticSizes<3>::Alignment() == 4, ""); + static_assert( + Layout>::WithStaticSizes<>::Alignment() == 64, ""); + static_assert( + Layout>::WithStaticSizes<0>::Alignment() == 64, ""); + static_assert( + Layout>::WithStaticSizes<2>::Alignment() == 64, ""); + static_assert( + Layout::WithStaticSizes<>::Alignment() == 8, ""); + static_assert( + Layout::WithStaticSizes<0, 0, 0>::Alignment() == + 8, + ""); + static_assert( + Layout::WithStaticSizes<1, 1, 1>::Alignment() == + 8, + ""); } TEST(Layout, ConstexprPartial) { @@ -1384,6 +1643,15 @@ TEST(Layout, ConstexprPartial) { constexpr Layout> x(1, 3); static_assert(x.Partial(1).template Offset<1>() == 2 * M, ""); } + +TEST(Layout, StaticConstexpr) { + constexpr size_t M = alignof(max_align_t); + using L = Layout>; + using SL = L::WithStaticSizes<1, 3>; + constexpr SL x; + static_assert(x.Offset<1>() == 2 * M, ""); +} + // [from, to) struct Region { size_t from; @@ -1458,6 +1726,41 @@ TEST(Layout, PoisonPadding) { } } +TEST(Layout, StaticPoisonPadding) { + using L = Layout; + using SL = L::WithStaticSizes<1, 2>; + + constexpr size_t n = L::Partial(1, 2, 3, 4).AllocSize(); + { + constexpr auto x = SL::Partial(); + alignas(max_align_t) const unsigned char c[n] = {}; + x.PoisonPadding(c); + EXPECT_EQ(x.Slices(c), x.Slices(c)); + ExpectPoisoned(c, {{1, 8}}); + } + { + constexpr auto x = SL::Partial(3); + alignas(max_align_t) const unsigned char c[n] = {}; + x.PoisonPadding(c); + EXPECT_EQ(x.Slices(c), x.Slices(c)); + ExpectPoisoned(c, {{1, 8}, {36, 40}}); + } + { + constexpr auto x = SL::Partial(3, 4); + alignas(max_align_t) const unsigned char c[n] = {}; + x.PoisonPadding(c); + EXPECT_EQ(x.Slices(c), x.Slices(c)); + ExpectPoisoned(c, {{1, 8}, {36, 40}}); + } + { + constexpr SL x(3, 4); + alignas(max_align_t) const unsigned char c[n] = {}; + x.PoisonPadding(c); + EXPECT_EQ(x.Slices(c), x.Slices(c)); + ExpectPoisoned(c, {{1, 8}, {36, 40}}); + } +} + TEST(Layout, DebugString) { { constexpr auto x = Layout::Partial(); @@ -1500,6 +1803,62 @@ TEST(Layout, DebugString) { } } +TEST(Layout, StaticDebugString) { + { + constexpr auto x = + Layout::WithStaticSizes<>::Partial(); + EXPECT_EQ("@0(1)", x.DebugString()); + } + { + constexpr auto x = + Layout::WithStaticSizes<>::Partial(1); + EXPECT_EQ("@0(1)[1]; @4(4)", x.DebugString()); + } + { + constexpr auto x = + Layout::WithStaticSizes<1>::Partial(); + EXPECT_EQ("@0(1)[1]; @4(4)", x.DebugString()); + } + { + constexpr auto x = + Layout::WithStaticSizes<>::Partial(1, + 2); + EXPECT_EQ("@0(1)[1]; @4(4)[2]; @12(1)", + x.DebugString()); + } + { + constexpr auto x = + Layout::WithStaticSizes<1>::Partial(2); + EXPECT_EQ("@0(1)[1]; @4(4)[2]; @12(1)", + x.DebugString()); + } + { + constexpr auto x = Layout::WithStaticSizes<1, 2>::Partial(); + EXPECT_EQ("@0(1)[1]; @4(4)[2]; @12(1)", + x.DebugString()); + } + { + constexpr auto x = Layout::WithStaticSizes<1, 2, 3, 4>::Partial(); + EXPECT_EQ( + "@0(1)[1]; @4(4)[2]; @12(1)[3]; " + "@16" + + Int128::Name() + "(16)[4]", + x.DebugString()); + } + { + constexpr Layout::WithStaticSizes<1, 2, 3, + 4> + x; + EXPECT_EQ( + "@0(1)[1]; @4(4)[2]; @12(1)[3]; " + "@16" + + Int128::Name() + "(16)[4]", + x.DebugString()); + } +} + TEST(Layout, CharTypes) { constexpr Layout x(1); alignas(max_align_t) char c[x.AllocSize()] = {}; @@ -1638,6 +1997,35 @@ TEST(CompactString, Works) { EXPECT_STREQ("hello", s.c_str()); } +// Same as the previous CompactString example, except we set the first array +// size to 1 statically, since we know it is always 1. This allows us to compute +// the offset of the character array at compile time. +class StaticCompactString { + public: + StaticCompactString(const char* s = "") { // NOLINT + const size_t size = strlen(s); + const SL layout(size + 1); + p_.reset(new unsigned char[layout.AllocSize()]); + layout.PoisonPadding(p_.get()); + *layout.Pointer(p_.get()) = size; + memcpy(layout.Pointer(p_.get()), s, size + 1); + } + + size_t size() const { return *SL::Partial().Pointer(p_.get()); } + + const char* c_str() const { return SL::Partial().Pointer(p_.get()); } + + private: + using SL = Layout::WithStaticSizes<1>; + std::unique_ptr p_; +}; + +TEST(StaticCompactString, Works) { + StaticCompactString s = "hello"; + EXPECT_EQ(5, s.size()); + EXPECT_STREQ("hello", s.c_str()); +} + } // namespace example } // namespace -- cgit v1.2.3