fdo#38513 - Accelerate non-poolable item add / remove.

For large documents we create and destroy a large number of non-poolable
SfxPoolItems, which get inserted into and removed from a vector.
Unfortunately the performance of this (depending on pattern) is O(N) and
this insert/remove/extend pattern can happen per text span we insert.
This patch makes this O(const) via a hash. This gives a 5x speedup for
the above bug; 176s to 34s or so, and moves the remaining performance
issues elsewhere.

Unfortunately, we have to retain the ordered array to keep the binary
file format code (used for editeng cut-and-paste) in place, so have to
keep both a hash, and an array, and a list around for free slots. cf.
fdo#79851 where there is a start at removing that.

This wastes space; but not that much - for a large open document
collection we have O(100's) of SfxItemPools, and O(1000's) of
SfxPoolItemArray_Impls; having fixed fdo#79851 we can consolidate this.

Add skeletal unit test; translate several German comments; remove
un-necessary include.

Change-Id: Ie0de32b1a29217560c5591c71a6cd4e26d39a531

3 files changed, 79 insertions, 51 deletions

diff --git a/svl/source/items/itempool.cxx b/svl/source/items/itempool.cxx
index 457b946fca19..d18b1226a33e 100644
--- a/svl/source/items/itempool.cxx
+++ b/svl/source/items/itempool.cxx
@@ -698,7 +698,8 @@ const SfxPoolItem& SfxItemPool::Put( const SfxPoolItem& rItem, sal_uInt16 nWhich
         return *pPoolItem;
     }
 
-    SFX_ASSERT( rItem.IsA(GetDefaultItem(nWhich).Type()), nWhich,
+    SFX_ASSERT( !pImp->ppStaticDefaults ||
+                rItem.IsA(GetDefaultItem(nWhich).Type()), nWhich,
                 "SFxItemPool: wrong item type in Put" );
 
     SfxPoolItemArray_Impl* pItemArr = pImp->maPoolItems[nIndex];
@@ -712,20 +713,21 @@ const SfxPoolItem& SfxItemPool::Put( const SfxPoolItem& rItem, sal_uInt16 nWhich
     bool ppFreeIsSet = false;
     if ( IsItemFlag_Impl( nIndex, SFX_ITEM_POOLABLE ) )
     {
-        // wenn es ueberhaupt gepoolt ist, koennte es schon drin sein
+        // if is already in a pool, then it is worth checking if it is in this one.
         if ( IsPooledItem(&rItem) )
         {
-            // 1. Schleife: teste ob der Pointer vorhanden ist.
-            SfxPoolItemArrayBase_Impl::iterator itr =
-                std::find(pItemArr->begin(), pItemArr->end(), &rItem);
-            if (itr != pItemArr->end())
+            SfxPoolItemArray_Impl::Hash::const_iterator it;
+            it = pItemArr->maHash.find(const_cast<SfxPoolItem *>(&rItem));
+
+            // 1. search for an identical pointer in the pool
+            if (it != pItemArr->maHash.end())
             {
-                AddRef(**itr);
-                return **itr;
+                AddRef(rItem);
+                return rItem;
             }
         }
 
-        // 2. Schleife: dann muessen eben die Attribute verglichen werden
+        // 2. search for an item with matching attributes.
         SfxPoolItemArrayBase_Impl::iterator itr = pItemArr->begin();
         for (; itr != pItemArr->end(); ++itr)
         {
@@ -749,20 +751,18 @@ const SfxPoolItem& SfxItemPool::Put( const SfxPoolItem& rItem, sal_uInt16 nWhich
     }
     else
     {
-        // freien Platz suchen
-        SfxPoolItemArrayBase_Impl::iterator itr = pItemArr->begin();
-        std::advance(itr, pItemArr->nFirstFree);
-        for (; itr != pItemArr->end(); ++itr)
+        // look for a freed place
+        if (pItemArr->maFree.size() > 0)
         {
-            if (!*itr)
-            {
-                ppFree = itr;
-                ppFreeIsSet = true;
-                break;
-            }
+            SfxPoolItemArrayBase_Impl::iterator itr = pItemArr->begin();
+            sal_uInt32 nIdx = pItemArr->maFree.back();
+            pItemArr->maFree.pop_back();
+
+            assert(nIdx < pItemArr->size());
+            std::advance(itr, nIdx);
+            ppFreeIsSet = true;
+            ppFree = itr;
         }
-        // naechstmoeglichen freien Platz merken
-        pItemArr->nFirstFree = std::distance(pItemArr->begin(), itr);
     }
 
     // nicht vorhanden, also im PtrArray eintragen
@@ -782,17 +782,41 @@ const SfxPoolItem& SfxItemPool::Put( const SfxPoolItem& rItem, sal_uInt16 nWhich
 #endif
     AddRef( *pNewItem, pImp->nInitRefCount );
 
-    if ( ppFreeIsSet == false )
+    assert( pItemArr->maHash.find(pNewItem) == pItemArr->maHash.end() );
+    if ( !ppFreeIsSet )
+    {
+        sal_uInt32 nOffset = pItemArr->size();
+        pItemArr->maHash.insert(std::make_pair(pNewItem, nOffset));
         pItemArr->push_back( pNewItem );
+    }
     else
     {
-        DBG_ASSERT( *ppFree == 0, "using surrogate in use" );
+        sal_uInt32 nOffset = std::distance(pItemArr->begin(), ppFree);
+        pItemArr->maHash.insert(std::make_pair(pNewItem, nOffset));
+        assert(*ppFree == NULL);
         *ppFree = pNewItem;
     }
     return *pNewItem;
 }
 
+/// Re-build our free list and pointer hash.
+void SfxPoolItemArray_Impl::ReHash()
+{
+    maFree.clear();
+    maHash.clear();
 
+    for (sal_uInt32 nIdx = 0; nIdx < size(); ++nIdx)
+    {
+        SfxPoolItem *pItem = (*this)[nIdx];
+        if (!pItem)
+            maFree.push_back(nIdx);
+        else
+        {
+            maHash.insert(std::make_pair(pItem,nIdx));
+            assert(maHash.find(pItem) != maHash.end());
+        }
+    }
+}
 
 void SfxItemPool::Remove( const SfxPoolItem& rItem )
 {
@@ -841,33 +865,40 @@ void SfxItemPool::Remove( const SfxPoolItem& rItem )
     // Item im eigenen Pool suchen
     SfxPoolItemArray_Impl* pItemArr = pImp->maPoolItems[nIndex];
     SFX_ASSERT( pItemArr, rItem.Which(), "removing Item not in Pool" );
-    SfxPoolItemArrayBase_Impl::iterator ppHtArrBeg = pItemArr->begin(), ppHtArrEnd = pItemArr->end();
-    for (SfxPoolItemArrayBase_Impl::iterator ppHtArr = ppHtArrBeg; ppHtArr != ppHtArrEnd; ++ppHtArr)
+
+    SfxPoolItemArray_Impl::Hash::iterator it;
+    it = pItemArr->maHash.find(const_cast<SfxPoolItem *>(&rItem));
+    if (it != pItemArr->maHash.end())
     {
-        SfxPoolItem*& p = *ppHtArr;
-        if (p == &rItem)
+        sal_uInt32 nIdx = it->second;
+        assert(nIdx < pItemArr->size());
+        SfxPoolItem*& p = (*pItemArr)[nIdx];
+        assert(p == &rItem);
+
+        if ( p->GetRefCount() ) //!
+            ReleaseRef( *p );
+        else
         {
-            if ( p->GetRefCount() ) //!
-                ReleaseRef( *p );
-            else
-            {
-                SFX_ASSERT( false, rItem.Which(), "removing Item without ref" );
-            }
+            SFX_ASSERT( false, rItem.Which(), "removing Item without ref" );
+        }
+
+        //! MI: Hack, solange wir das Problem mit dem Outliner haben
+        //! siehe anderes MI-REF
+        if ( 0 == p->GetRefCount() && nWhich < 4000 )
+        {
+            DELETEZ(p);
 
-            // ggf. kleinstmoegliche freie Position merken
-            size_t nPos = std::distance(ppHtArrBeg, ppHtArr);
-            if ( pItemArr->nFirstFree > nPos )
-                pItemArr->nFirstFree = nPos;
+            // remove ourselves from the hash
+            pItemArr->maHash.erase(it);
 
-            //! MI: Hack, solange wir das Problem mit dem Outliner haben
-            //! siehe anderes MI-REF
-            if ( 0 == p->GetRefCount() && nWhich < 4000 )
-                DELETEZ(p);
-            return;
+            // record that this slot is free
+            pItemArr->maFree.push_back( nIdx );
         }
+
+        return;
     }
 
-    // nicht vorhanden
+    // not found
     SFX_ASSERT( false, rItem.Which(), "removing Item not in Pool" );
 }
 
@@ -966,8 +997,6 @@ const SfxPoolItem *SfxItemPool::GetItem2(sal_uInt16 nWhich, sal_uInt32 nOfst) co
     return 0;
 }
 
-
-
 sal_uInt32 SfxItemPool::GetItemCount2(sal_uInt16 nWhich) const
 {
     if ( !IsInRange(nWhich) )
diff --git a/svl/source/items/poolio.cxx b/svl/source/items/poolio.cxx
index 68c93ef062d7..caad85d65435 100644
--- a/svl/source/items/poolio.cxx
+++ b/svl/source/items/poolio.cxx
@@ -303,7 +303,6 @@ void SfxItemPool::LoadCompleted()
     // wurden keine Ref-Counts mitgeladen?
     if ( pImp->nInitRefCount > 1 )
     {
-
         // "uber alle Which-Werte iterieren
         std::vector<SfxPoolItemArray_Impl*>::iterator itrItemArr = pImp->maPoolItems.begin();
         for( sal_uInt16 nArrCnt = GetSize_Impl(); nArrCnt; --nArrCnt, ++itrItemArr )
@@ -314,6 +313,7 @@ void SfxItemPool::LoadCompleted()
                 // "uber alle Items mit dieser Which-Id iterieren
                 SfxPoolItemArrayBase_Impl::iterator ppHtArr = (*itrItemArr)->begin();
                 for( size_t n = (*itrItemArr)->size(); n; --n, ++ppHtArr )
+                {
                     if (*ppHtArr)
                     {
                         #ifdef DBG_UTIL
@@ -326,6 +326,8 @@ void SfxItemPool::LoadCompleted()
                         if ( !ReleaseRef( **ppHtArr, 1 ) )
                             DELETEZ( *ppHtArr );
                     }
+                }
+                (*itrItemArr)->ReHash();
             }
         }
 
@@ -453,9 +455,9 @@ void SfxItemPool_Impl::readTheItems (
         }
     }
     delete pOldArr;
-}
-
 
+    (*ppArr)->ReHash(); // paranoid
+}
 
 SvStream &SfxItemPool::Load(SvStream &rStream)
 {
@@ -981,7 +983,6 @@ SvStream &SfxItemPool::Load1_Impl(SvStream &rStream)
 }
 
 
-
 const SfxPoolItem* SfxItemPool::LoadSurrogate
 (
     SvStream&           rStream,    // vor einem Surrogat positionierter Stream
@@ -1180,7 +1181,6 @@ sal_uInt32 SfxItemPool::GetSurrogate(const SfxPoolItem *pItem) const
 }
 
 
-
 bool SfxItemPool::IsInStoringRange( sal_uInt16 nWhich ) const
 {
     return nWhich >= pImp->nStoringStart &&
diff --git a/svl/source/items/style.cxx b/svl/source/items/style.cxx
index c729f0e93d28..d6c9a3055eac 100644
--- a/svl/source/items/style.cxx
+++ b/svl/source/items/style.cxx
@@ -27,7 +27,6 @@
 #include <svl/itemset.hxx>
 #include <svl/itempool.hxx>
 #include <svl/IndexedStyleSheets.hxx>
-#include <poolio.hxx>
 #include <svl/itemiter.hxx>
 #include <svl/style.hxx>
 #include <unotools/syslocale.hxx>