Bug 872869 - Make nsMsgDatabase::ListAllKeys() not provide a sorted array, as that led to bad perf when the sorting was not really needed. Idea by Derrick Moser. r=rkent, a=rkent IGNORE IDL
authoracelists@atlas.sk
Fri, 27 Mar 2015 14:59:17 -0700
changeset 25827 e600ae00a71887208dd93ffa9fe421da7e3aed15
parent 25826 bc07ed1b0df8bc8aeb4cf4fab28d4c730d9a939a
child 25828 9e636fb9a213904f0d36f55f9ddd2204fa3fa504
push id1850
push userclokep@gmail.com
push dateWed, 08 Mar 2017 19:29:12 +0000
treeherdercomm-esr52@028df196b2d9 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersrkent, rkent
bugs872869
Bug 872869 - Make nsMsgDatabase::ListAllKeys() not provide a sorted array, as that led to bad perf when the sorting was not really needed. Idea by Derrick Moser. r=rkent, a=rkent IGNORE IDL
mailnews/base/src/nsMsgFolderCompactor.cpp
mailnews/base/util/nsMsgKeyArray.cpp
mailnews/base/util/nsMsgKeyArray.h
mailnews/db/msgdb/public/nsIMsgDatabase.idl
mailnews/db/msgdb/src/nsMsgDatabase.cpp
mailnews/imap/src/nsAutoSyncState.cpp
mailnews/imap/src/nsImapMailFolder.cpp
mailnews/news/src/nsNNTPArticleList.cpp
--- a/mailnews/base/src/nsMsgFolderCompactor.cpp
+++ b/mailnews/base/src/nsMsgFolderCompactor.cpp
@@ -396,16 +396,21 @@ nsresult nsFolderCompactState::StartComp
   // messages to be copied because the summary database still gets blown away
   // which is still pretty interesting.  (And we like consistency.)
   nsCOMPtr<nsIMsgFolderNotificationService>
     notifier(do_GetService(NS_MSGNOTIFICATIONSERVICE_CONTRACTID));
   if (notifier)
     notifier->NotifyItemEvent(m_folder,
                               NS_LITERAL_CSTRING("FolderCompactStart"),
                               nullptr);
+
+  // TODO: test whether sorting the messages (m_keyArray) by messageOffset
+  // would improve performance on large files (less seeks).
+  // The m_keyArray is in the order as stored in DB and on IMAP or News
+  // the messages stored on the mbox file are not necessarily in the same order.
   if (m_size > 0)
   {
     nsCOMPtr<nsIURI> notUsed;
     ShowCompactingStatusMsg();
     AddRef();
     rv = m_messageService->CopyMessages(m_size, m_keyArray->m_keys.Elements(),
                                         m_folder, this,
                                         false, nullptr, m_window,
--- a/mailnews/base/util/nsMsgKeyArray.cpp
+++ b/mailnews/base/util/nsMsgKeyArray.cpp
@@ -5,24 +5,30 @@
 
 #include "nsMsgKeyArray.h"
 #include "nsMemory.h"
 
 NS_IMPL_ISUPPORTS(nsMsgKeyArray, nsIMsgKeyArray)
 
 nsMsgKeyArray::nsMsgKeyArray()
 {
+#ifdef DEBUG
+  m_sorted = false;
+#endif
 }
 
 nsMsgKeyArray::~nsMsgKeyArray()
 {
 }
 
 NS_IMETHODIMP nsMsgKeyArray::Sort()
 {
+#ifdef DEBUG
+  m_sorted = true;
+#endif
   m_keys.Sort();
   return NS_OK;
 }
 
 NS_IMETHODIMP nsMsgKeyArray::GetKeyAt(int32_t aIndex, nsMsgKey *aKey)
 {
   NS_ENSURE_ARG_POINTER(aKey);
   *aKey = m_keys[aIndex];
@@ -39,29 +45,33 @@ NS_IMETHODIMP nsMsgKeyArray::GetLength(u
 NS_IMETHODIMP nsMsgKeyArray::SetCapacity(uint32_t aCapacity)
 {
   m_keys.SetCapacity(aCapacity);
   return NS_OK;
 }
 
 NS_IMETHODIMP nsMsgKeyArray::AppendElement(nsMsgKey aKey)
 {
+#ifdef DEBUG
+  NS_ASSERTION(!m_sorted || m_keys.Length() == 0 ||
+               aKey > m_keys[m_keys.Length() - 1],
+               "Inserting a new key at wrong position in a sorted key list!");
+#endif
   m_keys.AppendElement(aKey);
   return NS_OK;
 }
 
 NS_IMETHODIMP nsMsgKeyArray::InsertElementSorted(nsMsgKey aKey)
 {
-  m_keys.InsertElementSorted(aKey);
-  return NS_OK;
+  // Ths function should be removed after interfaces are not frozen for TB38.
+  return NS_ERROR_NOT_IMPLEMENTED;
 }
 
 NS_IMETHODIMP nsMsgKeyArray::GetArray(uint32_t *aCount, nsMsgKey **aKeys)
 {
   NS_ENSURE_ARG_POINTER(aCount);
   NS_ENSURE_ARG_POINTER(aKeys);
   *aCount = m_keys.Length();
   *aKeys =
     (nsMsgKey *) nsMemory::Clone(&m_keys[0],
                                  m_keys.Length() * sizeof(nsMsgKey));
   return (*aKeys) ? NS_OK : NS_ERROR_OUT_OF_MEMORY;
 }
-
--- a/mailnews/base/util/nsMsgKeyArray.h
+++ b/mailnews/base/util/nsMsgKeyArray.h
@@ -19,11 +19,15 @@ public:
 
   NS_DECL_ISUPPORTS
   NS_DECL_NSIMSGKEYARRAY
 
   nsTArray<nsMsgKey> m_keys;
 
 private:
   virtual ~nsMsgKeyArray();
+
+#ifdef DEBUG
+  bool m_sorted;
+#endif
 };
 
 #endif
--- a/mailnews/db/msgdb/public/nsIMsgDatabase.idl
+++ b/mailnews/db/msgdb/public/nsIMsgDatabase.idl
@@ -295,16 +295,21 @@ interface nsIMsgDatabase : nsIDBChangeAn
  *             we will auto-assign a new key.
  */
   nsIMsgDBHdr CreateNewHdr(in nsMsgKey aKey);
 
   void AddNewHdrToDB(in nsIMsgDBHdr newHdr, in boolean notify);
 
   nsIMsgDBHdr CopyHdrFromExistingHdr(in nsMsgKey key, in nsIMsgDBHdr existingHdr, in boolean addHdrToDB);
 
+  /**
+   * Returns all message keys stored in the database.
+   * Keys are returned in the order as stored in the database.
+   * The caller should sort them if it needs to.
+   */
   void ListAllKeys(in nsIMsgKeyArray array);
 
   nsISimpleEnumerator EnumerateMessages();
   nsISimpleEnumerator ReverseEnumerateMessages();
   nsISimpleEnumerator EnumerateThreads();
 
   /**
    * Get an enumerator for use with nextMatchingHdrs. The enumerator
--- a/mailnews/db/msgdb/src/nsMsgDatabase.cpp
+++ b/mailnews/db/msgdb/src/nsMsgDatabase.cpp
@@ -3153,54 +3153,42 @@ nsMsgDatabase::SyncCounts()
   (void) m_dbFolderInfo->GetNumMessages(&oldTotal);
   if (oldUnread != numUnread)
     m_dbFolderInfo->ChangeNumUnreadMessages(numUnread - oldUnread);
   if (oldTotal != numHdrs)
     m_dbFolderInfo->ChangeNumMessages(numHdrs - oldTotal);
   return NS_OK;
 }
 
-// resulting output array is sorted by key.
 NS_IMETHODIMP nsMsgDatabase::ListAllKeys(nsIMsgKeyArray *aKeys)
 {
   NS_ENSURE_ARG_POINTER(aKeys);
   nsresult  rv = NS_OK;
   nsCOMPtr<nsIMdbTableRowCursor> rowCursor;
 
   RememberLastUseTime();
 
   if (m_mdbAllMsgHeadersTable)
   {
-    mdb_id largestId = 0;
     uint32_t numMsgs = 0;
     m_mdbAllMsgHeadersTable->GetCount(GetEnv(), &numMsgs);
     aKeys->SetCapacity(numMsgs);
     rv = m_mdbAllMsgHeadersTable->GetTableRowCursor(GetEnv(), -1,
                                                      getter_AddRefs(rowCursor));
     while (NS_SUCCEEDED(rv) && rowCursor)
     {
       mdbOid outOid;
       mdb_pos  outPos;
 
       rv = rowCursor->NextRowOid(GetEnv(), &outOid, &outPos);
       // is this right? Mork is returning a 0 id, but that should valid.
       if (outPos < 0 || outOid.mOid_Id == (mdb_id) -1)
         break;
       if (NS_SUCCEEDED(rv))
-      {
-        if (outOid.mOid_Id < largestId)
-        {
-          aKeys->InsertElementSorted(outOid.mOid_Id);
-        }
-        else
-        {
-          largestId = outOid.mOid_Id;
-          aKeys->AppendElement(outOid.mOid_Id);
-        }
-      }
+        aKeys->AppendElement(outOid.mOid_Id);
     }
   }
   return rv;
 }
 
 class nsMsgDBThreadEnumerator : public nsISimpleEnumerator, public nsIDBChangeListener
 {
 public:
@@ -4915,17 +4903,16 @@ NS_IMETHODIMP nsMsgDatabase::ListAllOffl
       if(NS_SUCCEEDED(rv) && dbMessage)
       {
         nsMsgKey msgKey;
         dbMessage->GetMessageKey(&msgKey);
         aKeys->AppendElement(msgKey);
       }
     }
   }
-  aKeys->Sort();
   return rv;
 }
 
 NS_IMETHODIMP nsMsgDatabase::EnumerateOfflineOps(nsISimpleEnumerator **enumerator)
 {
   NS_ASSERTION(false, "overridden by nsMailDatabase");
   return NS_ERROR_NOT_IMPLEMENTED;
 }
--- a/mailnews/imap/src/nsAutoSyncState.cpp
+++ b/mailnews/imap/src/nsAutoSyncState.cpp
@@ -337,16 +337,17 @@ NS_IMETHODIMP nsAutoSyncState::ProcessEx
     return NS_ERROR_FAILURE;
 
   // create a queue to process existing headers for the first time
   if (mExistingHeadersQ.IsEmpty())
   {
     nsRefPtr<nsMsgKeyArray> keys = new nsMsgKeyArray;
     rv = database->ListAllKeys(keys);
     NS_ENSURE_SUCCESS(rv, rv);
+    keys->Sort();
     mExistingHeadersQ.AppendElements(keys->m_keys);
     mProcessPointer = 0;
   }
 
   // process the existing headers and find the messages not downloaded yet
   uint32_t lastIdx = mProcessPointer;
   nsTArray<nsMsgKey> msgKeys;
   uint32_t keyCount = mExistingHeadersQ.Length();
--- a/mailnews/imap/src/nsImapMailFolder.cpp
+++ b/mailnews/imap/src/nsImapMailFolder.cpp
@@ -2672,20 +2672,17 @@ NS_IMETHODIMP nsImapMailFolder::UpdateIm
       dbFolderInfo->SetCharProperty(kModSeqPropertyName, nsDependentCString(intStrBuf));
     }
     nsRefPtr<nsMsgKeyArray> keys = new nsMsgKeyArray;
     if (!keys)
       return NS_ERROR_OUT_OF_MEMORY;
     rv = mDatabase->ListAllKeys(keys);
     NS_ENSURE_SUCCESS(rv, rv);
     existingKeys.AppendElements(keys->m_keys);
-    uint32_t keyCount = existingKeys.Length();
     mDatabase->ListAllOfflineDeletes(&existingKeys);
-    if (keyCount < existingKeys.Length())
-      existingKeys.Sort();
   }
   int32_t folderValidity;
   aSpec->GetFolder_UIDVALIDITY(&folderValidity);
   nsCOMPtr <nsIImapFlagAndUidState> flagState;
   aSpec->GetFlagState(getter_AddRefs(flagState));
 
   // remember what the supported user flags are.
   uint32_t supportedUserFlags;
@@ -2782,16 +2779,18 @@ NS_IMETHODIMP nsImapMailFolder::UpdateIm
 
   }
   else if (!flagState /*&& !NET_IsOffline() */) // if there are no messages on the server
     keysToDelete = existingKeys;
   else /* if ( !NET_IsOffline()) */
   {
     uint32_t boxFlags;
     aSpec->GetBox_flags(&boxFlags);
+    // FindKeysToDelete and FindKeysToAdd require sorted lists
+    existingKeys.Sort();
     FindKeysToDelete(existingKeys, keysToDelete, flagState, boxFlags);
     // if this is the result of an expunge then don't grab headers
     if (!(boxFlags & kJustExpunged))
       FindKeysToAdd(existingKeys, m_keysToFetch, numNewUnread, flagState);
   }
   m_totalKeysToFetch = m_keysToFetch.Length();
   if (!keysToDelete.IsEmpty() && mDatabase)
   {
--- a/mailnews/news/src/nsNNTPArticleList.cpp
+++ b/mailnews/news/src/nsNNTPArticleList.cpp
@@ -43,16 +43,17 @@ nsNNTPArticleList::Initialize(nsIMsgNews
 
     rv = folder->GetMsgDatabase(getter_AddRefs(m_newsDB));
     NS_ENSURE_SUCCESS(rv,rv);
     if (!m_newsDB) return NS_ERROR_UNEXPECTED;
 
     nsRefPtr<nsMsgKeyArray> keys = new nsMsgKeyArray;
     rv = m_newsDB->ListAllKeys(keys);
     NS_ENSURE_SUCCESS(rv,rv);
+    keys->Sort();
     m_idsInDB.AppendElements(keys->m_keys);
 
     return NS_OK;
 }
 
 NS_IMETHODIMP
 nsNNTPArticleList::AddArticleKey(nsMsgKey key)
 {