[XRay][compiler-rt] Segmented Array: Simplify and Optimise

Summary:
This is a follow-on to D49217 which simplifies and optimises the
implementation of the segmented array. In this patch we co-locate the
book-keeping for segments in the `__xray::Array<T>` with the data it's
managing. We take the chance in this patch to actually rename `Chunk` to
`Segment` to better align with the high-level description of the
segmented array.

With measurements using benchmarks landed in D48879, we've identified
that calls to `pthread_getspecific` started dominating the cycles, which
led us to revert the change made in D49217 to use C++ thread_local
initialisation instead (it reduces the cost by a huge margin, since we
save one PLT-based call to pthread functions in the hot path). In
particular, this is in `__xray::getThreadLocalData()`.

We also took the opportunity to remove the least-common-multiple based
calculation and instead pack as much data into segments of the array.
This greatly simplifies the API of the container which hides as much of
the implementation details as possible. For instance, we calculate the
number of elements we need for the each segment internally in the Array
instead of making it part of the type.

With the changes here, we're able to get a measurable improvement on the
performance of profiling mode on top of what D48879 already provides.

Depends on D48879.

Reviewers: kpw, eizan

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D49363

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@337343 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 21 insertions, 31 deletions

diff --git a/lib/xray/tests/unit/segmented_array_test.cc b/lib/xray/tests/unit/segmented_array_test.cc
index b48d481ff..035674ccf 100644
--- a/lib/xray/tests/unit/segmented_array_test.cc
+++ b/lib/xray/tests/unit/segmented_array_test.cc
@@ -15,16 +15,14 @@ struct TestData {
 TEST(SegmentedArrayTest, ConstructWithAllocators) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 4);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> Data(A, CA);
+  Array<TestData> Data(A);
   (void)Data;
 }
 
 TEST(SegmentedArrayTest, ConstructAndPopulate) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 4);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  Array<TestData> data(A);
   ASSERT_NE(data.Append(TestData{0, 0}), nullptr);
   ASSERT_NE(data.Append(TestData{1, 1}), nullptr);
   ASSERT_EQ(data.size(), 2u);
@@ -33,8 +31,7 @@ TEST(SegmentedArrayTest, ConstructAndPopulate) {
 TEST(SegmentedArrayTest, ConstructPopulateAndLookup) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 4);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  Array<TestData> data(A);
   ASSERT_NE(data.Append(TestData{0, 1}), nullptr);
   ASSERT_EQ(data.size(), 1u);
   ASSERT_EQ(data[0].First, 0);
@@ -44,8 +41,7 @@ TEST(SegmentedArrayTest, ConstructPopulateAndLookup) {
 TEST(SegmentedArrayTest, PopulateWithMoreElements) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 24);
-  ChunkAllocator CA(1 << 20);
-  Array<TestData> data(A, CA);
+  Array<TestData> data(A);
   static const auto kMaxElements = 100u;
   for (auto I = 0u; I < kMaxElements; ++I) {
     ASSERT_NE(data.Append(TestData{I, I + 1}), nullptr);
@@ -60,8 +56,7 @@ TEST(SegmentedArrayTest, PopulateWithMoreElements) {
 TEST(SegmentedArrayTest, AppendEmplace) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 4);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  Array<TestData> data(A);
   ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
   ASSERT_EQ(data[0].First, 1);
   ASSERT_EQ(data[0].Second, 1);
@@ -70,8 +65,7 @@ TEST(SegmentedArrayTest, AppendEmplace) {
 TEST(SegmentedArrayTest, AppendAndTrim) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 4);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  Array<TestData> data(A);
   ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
   ASSERT_EQ(data.size(), 1u);
   data.trim(1);
@@ -82,8 +76,7 @@ TEST(SegmentedArrayTest, AppendAndTrim) {
 TEST(SegmentedArrayTest, IteratorAdvance) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 4);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  Array<TestData> data(A);
   ASSERT_TRUE(data.empty());
   ASSERT_EQ(data.begin(), data.end());
   auto I0 = data.begin();
@@ -104,8 +97,7 @@ TEST(SegmentedArrayTest, IteratorAdvance) {
 TEST(SegmentedArrayTest, IteratorRetreat) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 4);
-  ChunkAllocator CA(1 << 4);
-  Array<TestData> data(A, CA);
+  Array<TestData> data(A);
   ASSERT_TRUE(data.empty());
   ASSERT_EQ(data.begin(), data.end());
   ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
@@ -126,17 +118,16 @@ TEST(SegmentedArrayTest, IteratorRetreat) {
 TEST(SegmentedArrayTest, IteratorTrimBehaviour) {
   using AllocatorType = typename Array<TestData>::AllocatorType;
   AllocatorType A(1 << 20);
-  ChunkAllocator CA(1 << 10);
-  Array<TestData> Data(A, CA);
+  Array<TestData> Data(A);
   ASSERT_TRUE(Data.empty());
   auto I0Begin = Data.begin(), I0End = Data.end();
   // Add enough elements in Data to have more than one chunk.
-  constexpr auto Chunk = Array<TestData>::ChunkSize;
-  constexpr auto ChunkX2 = Chunk * 2;
-  for (auto i = ChunkX2; i > 0u; --i) {
+  constexpr auto Segment = Array<TestData>::SegmentSize;
+  constexpr auto SegmentX2 = Segment * 2;
+  for (auto i = SegmentX2; i > 0u; --i) {
     Data.AppendEmplace(static_cast<s64>(i), static_cast<s64>(i));
   }
-  ASSERT_EQ(Data.size(), ChunkX2);
+  ASSERT_EQ(Data.size(), SegmentX2);
   {
     auto &Back = Data.back();
     ASSERT_EQ(Back.First, 1);
@@ -144,18 +135,18 @@ TEST(SegmentedArrayTest, IteratorTrimBehaviour) {
   }
 
   // Trim one chunk's elements worth.
-  Data.trim(Chunk);
-  ASSERT_EQ(Data.size(), Chunk);
+  Data.trim(Segment);
+  ASSERT_EQ(Data.size(), Segment);
 
   // Check that we are still able to access 'back' properly.
   {
     auto &Back = Data.back();
-    ASSERT_EQ(Back.First, static_cast<s64>(Chunk + 1));
-    ASSERT_EQ(Back.Second, static_cast<s64>(Chunk + 1));
+    ASSERT_EQ(Back.First, static_cast<s64>(Segment + 1));
+    ASSERT_EQ(Back.Second, static_cast<s64>(Segment + 1));
   }
 
   // Then trim until it's empty.
-  Data.trim(Chunk);
+  Data.trim(Segment);
   ASSERT_TRUE(Data.empty());
 
   // Here our iterators should be the same.
@@ -164,10 +155,10 @@ TEST(SegmentedArrayTest, IteratorTrimBehaviour) {
   EXPECT_EQ(I0End, I1End);
 
   // Then we ensure that adding elements back works just fine.
-  for (auto i = ChunkX2; i > 0u; --i) {
+  for (auto i = SegmentX2; i > 0u; --i) {
     Data.AppendEmplace(static_cast<s64>(i), static_cast<s64>(i));
   }
-  EXPECT_EQ(Data.size(), ChunkX2);
+  EXPECT_EQ(Data.size(), SegmentX2);
 }
 
 struct ShadowStackEntry {
@@ -179,8 +170,7 @@ struct ShadowStackEntry {
 TEST(SegmentedArrayTest, SimulateStackBehaviour) {
   using AllocatorType = typename Array<ShadowStackEntry>::AllocatorType;
   AllocatorType A(1 << 10);
-  ChunkAllocator CA(1 << 10);
-  Array<ShadowStackEntry> Data(A, CA);
+  Array<ShadowStackEntry> Data(A);
   static uint64_t Dummy = 0;
   constexpr uint64_t Max = 9;