[scudo] Improve performance of pushBlocks sort. (#200297)

Ran this on an Android device using both algorithms, the new algorithm
is on average 10% faster, but gets to be 15% faster in some cases. This
is an example of the speed-ups.

Average Operation Time    Maximum Operation Time   Name
        326.9(ns)                 80770(ns)        PushBlocks New
        365.9(ns)                108032(ns)        PushBlocks Old

GitOrigin-RevId: c9cdbc4a30b83b8a8d100c19c4aba16c848b9dfb

primary64.h

diff --git a/primary64.h b/primary64.h
index 2c3ccdf..b8ff156 100644
--- a/primary64.h
+++ b/primary64.h
@@ -802,21 +802,24 @@
 
   // TODO(chiahungduan): Consider not doing grouping if the group size is not
   // greater than the block size with a certain scale.
-
   bool SameGroup = true;
-  if (GroupSizeLog < RegionSizeLog) {
-    // Sort the blocks so that blocks belonging to the same group can be
-    // pushed together.
+  if (GroupSizeLog < RegionSizeLog && Size > 1) {
+    // Sort the blocks such that blocks belonging to the same group are
+    // ordered together.
+    uptr FirstPtrGroup = compactPtrGroup(Array[0]);
     for (u32 I = 1; I < Size; ++I) {
-      if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I]))
-        SameGroup = false;
       CompactPtrT Cur = Array[I];
-      u32 J = I;
-      while (J > 0 && compactPtrGroup(Cur) < compactPtrGroup(Array[J - 1])) {
-        Array[J] = Array[J - 1];
-        --J;
+      uptr CurPtrGroup = compactPtrGroup(Cur);
+      SameGroup = SameGroup && CurPtrGroup == FirstPtrGroup;
+      if (!SameGroup) {
+        // Sorting only necessary if there are different groups.
+        u32 J = I;
+        while (J > 0 && CurPtrGroup < compactPtrGroup(Array[J - 1])) {
+          Array[J] = Array[J - 1];
+          --J;
+        }
+        Array[J] = Cur;
       }
-      Array[J] = Cur;
     }
   }
 

tests/primary_test.cpp

diff --git a/tests/primary_test.cpp b/tests/primary_test.cpp
index 2fbfadf..cd4b0b8 100644
--- a/tests/primary_test.cpp
+++ b/tests/primary_test.cpp
@@ -503,3 +503,68 @@
   }
   SizeClassAllocator.drain();
 }
+
+#if !defined(GWP_ASAN_HOOKS)
+// This test doesn't work when GWP-Asan is enabled.
+TEST(ScudoPrimaryTest, PushBlocksDifferentGroups) {
+  using Primary = TestAllocator<TestConfig2, scudo::DefaultSizeClassMap>;
+  std::unique_ptr<Primary> Allocator(new Primary);
+  Allocator->init(/*ReleaseToOsInterval=*/-1);
+  typename Primary::SizeClassAllocatorT SizeClassAllocator;
+  SizeClassAllocator.init(nullptr, Allocator.get());
+
+  static_assert(
+      TestConfig2<scudo::DefaultSizeClassMap>::Primary::GroupSizeLog <
+      TestConfig2<scudo::DefaultSizeClassMap>::Primary::RegionSizeLog);
+
+  const scudo::uptr GroupScale =
+      TestConfig2<scudo::DefaultSizeClassMap>::Primary::GroupSizeLog -
+      TestConfig2<scudo::DefaultSizeClassMap>::Primary::CompactPtrScale;
+  const scudo::uptr Mask = (static_cast<scudo::uptr>(1) << GroupScale) - 1;
+
+  scudo::uptr ClassId = 1;
+  for (scudo::uptr C = 1; C < Primary::SizeClassMap::NumClasses; ++C) {
+    if (Primary::SizeClassMap::getSizeByClassId(C) >= 64 * 1024) {
+      ClassId = C;
+      break;
+    }
+  }
+  EXPECT_NE(1U, ClassId);
+
+  std::vector<void *> Pointers;
+  size_t SecondGroupIndex = 0;
+  for (scudo::uptr FirstGroup = 0, I = 0; I < 100; ++I) {
+    void *P = SizeClassAllocator.allocate(ClassId);
+    EXPECT_NE(P, nullptr);
+    Pointers.push_back(P);
+    typename Primary::CompactPtrT CompactP =
+        Allocator->compactPtr(ClassId, reinterpret_cast<scudo::uptr>(P));
+    scudo::uptr Group = static_cast<scudo::uptr>(CompactP) & ~Mask;
+    if (I == 0) {
+      FirstGroup = Group;
+    } else if (Group != FirstGroup) {
+      SecondGroupIndex = I;
+      break;
+    }
+  }
+  EXPECT_NE(0U, SecondGroupIndex);
+
+  std::vector<typename Primary::CompactPtrT> Array;
+  for (void *P : Pointers) {
+    Array.push_back(
+        Allocator->compactPtr(ClassId, reinterpret_cast<scudo::uptr>(P)));
+  }
+  EXPECT_GT(Array.size(), 1U);
+
+  std::swap(Array[0], Array[SecondGroupIndex]);
+
+  Allocator->pushBlocks(&SizeClassAllocator, ClassId, Array.data(),
+                        static_cast<scudo::u32>(Array.size()));
+
+  for (size_t I = 0; I < Array.size(); I++)
+    EXPECT_LE(Array[I - 1] & ~Mask, Array[I] & ~Mask)
+        << "Array not ordered: index " << I - 1 << " is < index " << I;
+
+  SizeClassAllocator.destroy(nullptr);
+}
+#endif