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

8 files changed, 259 insertions, 67 deletions

diff --git a/svl/CppunitTest_svl_itempool.mk b/svl/CppunitTest_svl_itempool.mk
new file mode 100644
index 000000000000..4b594989f855
--- /dev/null
+++ b/svl/CppunitTest_svl_itempool.mk
@@ -0,0 +1,36 @@
+# -*- Mode: makefile-gmake; tab-width: 4; indent-tabs-mode: t -*-
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+
+$(eval $(call gb_CppunitTest_CppunitTest,svl_itempool))
+
+$(eval $(call gb_CppunitTest_use_external,svl_itempool,boost_headers))
+
+$(eval $(call gb_CppunitTest_use_api,svl_itempool, \
+    offapi \
+    udkapi \
+))
+
+$(eval $(call gb_CppunitTest_add_exception_objects,svl_itempool, \
+	svl/qa/unit/items/test_itempool \
+))
+
+$(eval $(call gb_CppunitTest_use_libraries,svl_itempool, \
+	svl \
+	comphelper \
+	sal \
+	cppu \
+	cppuhelper \
+))
+
+$(eval $(call gb_CppunitTest_set_include,svl_itempool,\
+	-I$(SRCDIR)/svl/source/inc \
+	$$(INCLUDE) \
+))
+
+# vim: set noet sw=4 ts=4:
diff --git a/svl/CppunitTest_svl_items.mk b/svl/CppunitTest_svl_items.mk
index d51b8fc43af3..501c91ae14f7 100644
--- a/svl/CppunitTest_svl_items.mk
+++ b/svl/CppunitTest_svl_items.mk
@@ -16,11 +16,6 @@ $(eval $(call gb_CppunitTest_use_api,svl_items, \
     udkapi \
 ))
 
-
-#$(eval $(call gb_CppunitTest_use_components,svl_items, \
-#    ucb/source/core/ucb1 \
-#))
-
 $(eval $(call gb_CppunitTest_add_exception_objects,svl_items, \
 	svl/qa/unit/items/test_IndexedStyleSheets \
 ))
@@ -33,10 +28,4 @@ $(eval $(call gb_CppunitTest_use_libraries,svl_items, \
 	cppuhelper \
 ))
 
-#$(eval $(call gb_CppunitTest_use_ure,svl_items))
-
-#$(eval $(call gb_CppunitTest_use_components,svl_urihelper,\
-#    i18npool/util/i18npool \
-#))
-
 # vim: set noet sw=4 ts=4:
diff --git a/svl/Module_svl.mk b/svl/Module_svl.mk
index f52c7a4bfb72..75890301e31b 100644
--- a/svl/Module_svl.mk
+++ b/svl/Module_svl.mk
@@ -34,6 +34,7 @@ $(eval $(call gb_Module_add_check_targets,svl,\
 	CppunitTest_svl_qa_cppunit \
 	CppunitTest_svl_inetcontenttype \
 	CppunitTest_svl_items \
+	CppunitTest_svl_itempool \
 ))
 
 #TODO: CppunitTest_svl_urihelper depends on ucb, can only be added once svl is
diff --git a/svl/qa/unit/items/test_itempool.cxx b/svl/qa/unit/items/test_itempool.cxx
new file mode 100644
index 000000000000..469287eecc83
--- /dev/null
+++ b/svl/qa/unit/items/test_itempool.cxx
@@ -0,0 +1,117 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include <svl/itempool.hxx>
+#include <poolio.hxx>
+
+#include <cppunit/TestAssert.h>
+#include <cppunit/TestFixture.h>
+#include <cppunit/extensions/HelperMacros.h>
+#include <cppunit/plugin/TestPlugIn.h>
+
+class PoolItemTest : public CppUnit::TestFixture
+{
+  public:
+             PoolItemTest() {}
+    virtual ~PoolItemTest() {}
+
+    void testPool();
+
+    // Adds code needed to register the test suite
+    CPPUNIT_TEST_SUITE(PoolItemTest);
+
+    CPPUNIT_TEST(testPool);
+
+    // End of test suite definition
+    CPPUNIT_TEST_SUITE_END();
+};
+
+void PoolItemTest::testPool()
+{
+    SfxItemInfo aItems[] =
+        { { 0, SFX_ITEM_POOLABLE },
+          { 1, 0 /* not poolable */ },
+          { 2, SFX_ITEM_NOT_POOLABLE },
+          { 3, 0 /* not poolable */}
+        };
+
+    SfxItemPool *pPool = new SfxItemPool("testpool", 0, 3, aItems);
+    SfxItemPool_Impl *pImpl = SfxItemPool_Impl::GetImpl(pPool);
+    CPPUNIT_ASSERT(pImpl != NULL);
+    CPPUNIT_ASSERT(pImpl->maPoolItems.size() == 4);
+
+    // Poolable
+    SfxVoidItem aItemZero( 0 );
+    SfxVoidItem aNotherZero( 0 );
+
+    {
+        CPPUNIT_ASSERT(pImpl->maPoolItems[0] == NULL);
+        const SfxPoolItem &rVal = pPool->Put(aItemZero);
+        CPPUNIT_ASSERT(rVal == aItemZero);
+        CPPUNIT_ASSERT(pImpl->maPoolItems[0] != NULL);
+        const SfxPoolItem &rVal2 = pPool->Put(aNotherZero);
+        CPPUNIT_ASSERT(rVal2 == rVal);
+        CPPUNIT_ASSERT(&rVal2 == &rVal);
+
+        // Clones on Put ...
+        CPPUNIT_ASSERT(&rVal2 != &aItemZero);
+        CPPUNIT_ASSERT(&rVal2 != &aNotherZero);
+        CPPUNIT_ASSERT(&rVal != &aItemZero);
+        CPPUNIT_ASSERT(&rVal != &aNotherZero);
+    }
+
+    // non-poolable
+    SfxVoidItem aItemOne( 1 );
+    SfxVoidItem aNotherOne( 1 );
+    {
+        CPPUNIT_ASSERT(pImpl->maPoolItems[1] == NULL);
+        const SfxPoolItem &rVal = pPool->Put(aItemOne);
+        CPPUNIT_ASSERT(rVal == aItemOne);
+        CPPUNIT_ASSERT(pImpl->maPoolItems[1] != NULL);
+
+        const SfxPoolItem &rVal2 = pPool->Put(aNotherOne);
+        CPPUNIT_ASSERT(rVal2 == rVal);
+        CPPUNIT_ASSERT(&rVal2 != &rVal);
+    }
+
+    // not-poolable
+    SfxVoidItem aItemTwo( 2 );
+    SfxVoidItem aNotherTwo( 2 );
+    {
+        CPPUNIT_ASSERT(pImpl->maPoolItems[2] == NULL);
+        const SfxPoolItem &rVal = pPool->Put(aItemTwo);
+        // those guys just don't go in ...
+        CPPUNIT_ASSERT(pImpl->maPoolItems[2] == NULL);
+        CPPUNIT_ASSERT(rVal == aItemOne);
+    }
+
+    // Test rehash
+    for (size_t i = 0; i < pImpl->maPoolItems.size(); ++i)
+    {
+        SfxPoolItemArray_Impl *pSlice = pImpl->maPoolItems[i];
+        if (pSlice)
+            pSlice->ReHash();
+    }
+
+    // Test removal.
+    SfxVoidItem aRemoveThree(3);
+    SfxVoidItem aNotherThree(3);
+    const SfxPoolItem &rKeyThree = pPool->Put(aRemoveThree);
+    pPool->Put(aNotherThree);
+    CPPUNIT_ASSERT(pImpl->maPoolItems[3]->size() > 0);
+    CPPUNIT_ASSERT(pImpl->maPoolItems[3]->maFree.size() == 0);
+    pPool->Remove(rKeyThree);
+    CPPUNIT_ASSERT(pImpl->maPoolItems[3]->maFree.size() == 1);
+    pPool->Put(aNotherThree);
+    CPPUNIT_ASSERT(pImpl->maPoolItems[3]->maFree.size() == 0);
+}
+
+CPPUNIT_TEST_SUITE_REGISTRATION(PoolItemTest);
+
+CPPUNIT_PLUGIN_IMPLEMENT();
diff --git a/svl/source/inc/poolio.hxx b/svl/source/inc/poolio.hxx
index ffff7a308c70..9e3ccd162da8 100644
--- a/svl/source/inc/poolio.hxx
+++ b/svl/source/inc/poolio.hxx
@@ -22,14 +22,17 @@
 
 #include <svl/brdcst.hxx>
 #include <boost/shared_ptr.hpp>
+#include <boost/unordered_map.hpp>
 #include <deque>
 #include <vector>
 
+class SfxPoolItem;
+class SfxItemPoolUser;
+
 #ifndef DELETEZ
 #define DELETEZ(pPtr) { delete pPtr; pPtr = 0; }
 #endif
 
-
 struct SfxPoolVersion_Impl
 {
     sal_uInt16          _nVer;
@@ -56,13 +59,27 @@ typedef std::vector<SfxPoolItem*> SfxPoolItemArrayBase_Impl;
 typedef boost::shared_ptr< SfxPoolVersion_Impl > SfxPoolVersion_ImplPtr;
 typedef std::deque< SfxPoolVersion_ImplPtr > SfxPoolVersionArr_Impl;
 
+/**
+ * This array contains a set of SfxPoolItems, if those items are
+ * poolable then each item has a unique set of properties, and we
+ * often search linearly to ensure uniqueness. If they are
+ * non-poolable we maintain an (often large) list of pointers.
+ */
 struct SfxPoolItemArray_Impl: public SfxPoolItemArrayBase_Impl
 {
-    size_t  nFirstFree;
+    typedef std::vector<sal_uInt32> FreeList;
+    typedef boost::unordered_map<SfxPoolItem*,sal_uInt32> Hash;
 
-    SfxPoolItemArray_Impl ()
-        : nFirstFree( 0 )
-    {}
+public:
+    /// Track list of indicees into our array that contain an empty slot
+    FreeList maFree;
+    /// Hash of SfxPoolItem pointer to index into our array that contains that slot
+    Hash     maHash;
+
+    SfxPoolItemArray_Impl () {}
+
+    /// re-build the list of free slots and hash from clean
+    void SVL_DLLPUBLIC ReHash();
 };
 
 struct SfxItemPool_Impl
@@ -140,6 +157,10 @@ struct SfxItemPool_Impl
 
     void readTheItems(SvStream & rStream, sal_uInt32 nCount, sal_uInt16 nVersion,
                       SfxPoolItem * pDefItem, SfxPoolItemArray_Impl ** pArr);
+
+    // unit testing
+    friend class PoolItemTest;
+    static SfxItemPool_Impl *GetImpl(SfxItemPool *pPool) { return pPool->pImp; }
 };
 
 
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>