Use quicksort to sort the string pool.

The current implementation of Vector::sort uses insertion sort
on the assumption that the data is mostly sorted.  It isn't.

This change brings the total time spent sorting packages by config
down to 500ms from about 93 seconds.

Bug: 6186278
Change-Id: Iec8da11e09297acd6c73733d063b0fa9dacf69f7

diff --git a/StringPool.cpp b/StringPool.cpp
index 963ae59cdb5c6c1b08eb04fa1c6f8cd310fe6f7d..b6295bd0e3a7730c992ad4602fc327b30186ae49 100644 (file)
--- a/StringPool.cpp
+++ b/StringPool.cpp
@@ -213,11 +213,11 @@ status_t StringPool::addStyleSpan(size_t idx, const entry_style_span& span)
     return NO_ERROR;
 }
 
     return NO_ERROR;
 }
 

-int StringPool::config_sort(const size_t* lhs, const size_t* rhs, void* state)
+int StringPool::config_sort(void* state, const void* lhs, const void* rhs)

 {
     StringPool* pool = (StringPool*)state;
 {
     StringPool* pool = (StringPool*)state;

-    const entry& lhe = pool->mEntries[pool->mEntryArray[*lhs]];
-    const entry& rhe = pool->mEntries[pool->mEntryArray[*rhs]];
+    const entry& lhe = pool->mEntries[pool->mEntryArray[*static_cast<const size_t*>(lhs)]];
+    const entry& rhe = pool->mEntries[pool->mEntryArray[*static_cast<const size_t*>(rhs)]];

     return lhe.compare(rhe);
 }
 
     return lhe.compare(rhe);
 }
 


@@ -232,13 +232,17 @@ void StringPool::sortByConfig()
     // At that point it maps from the new position in the array to the
     // original position the entry appeared.
     Vector<size_t> newPosToOriginalPos;
     // At that point it maps from the new position in the array to the
     // original position the entry appeared.
     Vector<size_t> newPosToOriginalPos;

-    for (size_t i=0; i<mEntryArray.size(); i++) {
+    newPosToOriginalPos.setCapacity(N);
+    for (size_t i=0; i < N; i++) {

         newPosToOriginalPos.add(i);
     }
 
     // Sort the array.
     NOISY(printf("SORTING STRINGS BY CONFIGURATION...\n"));
         newPosToOriginalPos.add(i);
     }
 
     // Sort the array.
     NOISY(printf("SORTING STRINGS BY CONFIGURATION...\n"));

-    newPosToOriginalPos.sort(config_sort, this);
+    // Vector::sort uses insertion sort, which is very slow for this data set.
+    // Use quicksort instead because we don't need a stable sort here.
+    qsort_r(newPosToOriginalPos.editArray(), N, sizeof(size_t), this, config_sort);
+    //newPosToOriginalPos.sort(config_sort, this);

     NOISY(printf("DONE SORTING STRINGS BY CONFIGURATION.\n"));
 
     // Create the reverse mapping from the original position in the array
     NOISY(printf("DONE SORTING STRINGS BY CONFIGURATION.\n"));
 
     // Create the reverse mapping from the original position in the array

diff --git a/StringPool.h b/StringPool.h
index 060dc6811c8bba5a4ff07821135a6e1b0f96bd06..d5010086b2928a55adad08884c6d98ddbdd29e48 100644 (file)
--- a/StringPool.h
+++ b/StringPool.h
@@ -139,7 +139,7 @@ public:
     const Vector<size_t>* offsetsForString(const String16& val) const;
 
 private:
     const Vector<size_t>* offsetsForString(const String16& val) const;
 
 private:

-    static int config_sort(const size_t* lhs, const size_t* rhs, void* state);
+    static int config_sort(void* state, const void* lhs, const void* rhs);

 
     const bool                              mUTF8;
 
 
     const bool                              mUTF8;