Re: [REVIEW 3-5] fdo#47644 performance regression on largish .doc

On Thu, 2012-05-10 at 21:56 +0100, Caolán McNamara wrote:
> with a scenario of nBgn = 11, nRel = 2, desired result is 13

        Ah ! how stupid of me, I missed that - but this case is almost totally
pointless ;-) we are just victims of this optimisation of starting in
the middle - which means we have to go lookup where we are; when we
actually precisely know our offset from the beginning of the chain/array
( which is nNew/nPageSize ).

        So - how about the attached diff, hopefully rather easier to review &
back-port :-) should I knock a version up for -3-5 ? the #ifdef bravery
is never triggered if enabled (FWIW) during import / export of the
slow .doc anyhow.

        All the best,

                Michael.

-- 
michael.meeks@suse.com  <><, Pseudo Engineer, itinerant idiot

diff --git a/sot/source/sdstor/stgstrms.cxx b/sot/source/sdstor/stgstrms.cxx
index 88bc416..67da8ee 100644
--- a/sot/source/sdstor/stgstrms.cxx
+++ b/sot/source/sdstor/stgstrms.cxx
@@ -334,27 +334,12 @@ void StgStrm::SetEntry( StgDirEntry& r )
     r.SetDirty();
 }
 
-namespace lcl
-{
-#if defined(__GXX_EXPERIMENTAL_CXX0X__) || __cplusplus >= 201103L
-    using std::is_sorted;
-#else
-    template <typename iter> bool is_sorted(iter aStart, iter aEnd)
-    {
-        if (aStart == aEnd)
-            return true;
-
-        for (iter aNext = aStart + 1; aNext != aEnd; aStart = aNext, ++aNext)
-        {
-            if (*aNext < *aStart)
-                return false;
-        }
-
-        return true;
-    }
-#endif
-}
-
+/*
+ * The page chain, is basically a singly linked list of slots each
+ * point to the next page. Instead of traversing the file structure
+ * for this each time build a simple flat in-memory vector list
+ * of pages.
+ */
 bool StgStrm::buildPageChainCache()
 {
     if (nSize > 0)
@@ -370,10 +355,6 @@ bool StgStrm::buildPageChainCache()
             return false;
     }
 
-    m_bSortedPageChain = lcl::is_sorted(m_aPagesCache.begin(), m_aPagesCache.end());
-
-    SAL_WARN_IF(!m_bSortedPageChain, "sot", "unsorted page chain, that's suspicious");
-
     return true;
 }
 
@@ -403,6 +384,35 @@ sal_Bool StgStrm::Pos2Page( sal_Int32 nBytePos )
     nPos = nBytePos;
     if( nOld == nNew )
         return sal_True;
+
+    if (m_aPagesCache.empty() && nNew > ARBITRARY_LARGE_AMOUNT_OF_PAGES)
+    {
+        SAL_WARN("sot", "kicking off large seek helper\n");
+        buildPageChainCache();
+    }
+
+    if (!m_aPagesCache.empty())
+    {
+        size_t nIdx = nNew / nPageSize;
+
+#ifdef BRAVE_BUT_UN_NECESSARY
+        // special case: seek to 1st byte of new, unallocated page
+        // (in case the file size is a multiple of the page size)
+        if( nBytePos == nSize && !nOffset )
+        {
+            nIdx--;
+            nOffset = nPageSize;
+        }
+#endif
+
+        if (nIdx < m_aPagesCache.size())
+        {
+            nPage = m_aPagesCache[ nIdx ];
+//            fprintf (stderr, "got page ! %d offset %d\n", (int)nPage, (int)nOffset);
+            return sal_Bool( nPage >= 0 );
+        }
+    }
+
     if( nNew > nOld )
     {
         // the new position is after the current, so an incremental
@@ -420,62 +430,19 @@ sal_Bool StgStrm::Pos2Page( sal_Int32 nBytePos )
     // now, traverse the FAT chain.
     nRel /= nPageSize;
 
-    sal_Int32 nLast = STG_EOF;
-    if (m_aPagesCache.empty() && nRel < ARBITRARY_LARGE_AMOUNT_OF_PAGES)
-    {
+        sal_Int32 nLast = STG_EOF;
         while (nRel && nBgn >= 0)
         {
             nLast = nBgn;
             nBgn = pFat->GetNextPage( nBgn );
             nRel--;
         }
-    }
-    else if (nBgn >= 0)
-    {
-        //Seeking large distances is slow, so if we're starting seeking (some
-        //fairly arbitrary) large distances, build a cache and re-use it for
-        //subsequent seeks
-        if (m_aPagesCache.empty())
-        {
-            SAL_WARN("sot", "kicking off large seek helper\n");
-            buildPageChainCache();
-        }
-
-        std::vector<sal_Int32>::iterator aI;
-
-        if (m_bSortedPageChain)
-            aI = std::lower_bound(m_aPagesCache.begin(), m_aPagesCache.end(), nBgn);
-        else
-            aI = std::find(m_aPagesCache.begin(), m_aPagesCache.end(), nBgn);
-
-        if (aI == m_aPagesCache.end())
-        {
-            SAL_WARN("sot", "Unknown page position");
-            nBgn = STG_EOF;
-        }
-        else
-        {
-            size_t nBgnDistance = std::distance(m_aPagesCache.begin(), aI);
-
-            size_t nIndex = nBgnDistance + nRel;
-
-            if (nIndex > m_aPagesCache.size())
-            {
-                nRel = m_aPagesCache.size() - nBgnDistance;
-                nIndex = m_aPagesCache.size() - 1;
-            }
-            else
-                nRel = 0;
-
-            nLast = nIndex ? m_aPagesCache[nIndex - 1] : STG_EOF;
-            nBgn = m_aPagesCache[nIndex];
-        }
-    }
 
     // special case: seek to 1st byte of new, unallocated page
     // (in case the file size is a multiple of the page size)
     if( nBytePos == nSize && nBgn == STG_EOF && !nRel && !nOffset )
         nBgn = nLast, nOffset = nPageSize;
+
     if( nBgn < 0 && nBgn != STG_EOF )
     {
         rIo.SetError( SVSTREAM_FILEFORMAT_ERROR );
diff --git a/sot/source/sdstor/stgstrms.hxx b/sot/source/sdstor/stgstrms.hxx
index 3b5c263..125dc67 100644
--- a/sot/source/sdstor/stgstrms.hxx
+++ b/sot/source/sdstor/stgstrms.hxx
@@ -79,7 +79,6 @@ protected:
     short nOffset;                      // offset into current page
     short nPageSize;                    // logical page size
     std::vector<sal_Int32> m_aPagesCache;
-    bool m_bSortedPageChain;
     bool buildPageChainCache();
     sal_Bool  Copy( sal_Int32 nFrom, sal_Int32 nBytes );
     StgStrm( StgIo& );