From 8aff83b95fa5969edfc48022ddaae05031b178cf Mon Sep 17 00:00:00 2001 From: Michael Meeks Date: Mon, 16 Jun 2014 22:27:00 +0100 Subject: 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 Reviewed-on: https://gerrit.libreoffice.org/9818 Reviewed-by: Jan Holesovsky Tested-by: Jan Holesovsky --- svl/CppunitTest_svl_itempool.mk | 36 +++++++++++ svl/CppunitTest_svl_items.mk | 11 ---- svl/Module_svl.mk | 1 + svl/qa/unit/items/test_itempool.cxx | 117 +++++++++++++++++++++++++++++++++++ svl/source/inc/poolio.hxx | 31 ++++++++-- svl/source/items/itempool.cxx | 119 ++++++++++++++++++++++-------------- svl/source/items/poolio.cxx | 10 +-- svl/source/items/style.cxx | 1 - 8 files changed, 259 insertions(+), 67 deletions(-) create mode 100644 svl/CppunitTest_svl_itempool.mk create mode 100644 svl/qa/unit/items/test_itempool.cxx 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 +#include + +#include +#include +#include +#include + +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 9fa2dace14c9..19395b5fba3e 100644 --- a/svl/source/inc/poolio.hxx +++ b/svl/source/inc/poolio.hxx @@ -18,14 +18,17 @@ */ #include #include +#include #include #include +class SfxPoolItem; +class SfxItemPoolUser; + #ifndef DELETEZ #define DELETEZ(pPtr) { delete pPtr; pPtr = 0; } #endif - struct SfxPoolVersion_Impl { sal_uInt16 _nVer; @@ -52,13 +55,27 @@ typedef std::vector 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 FreeList; + typedef boost::unordered_map 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 @@ -136,6 +153,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(&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(&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::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 40e8eeec207f..4626e59fe0b0 100644 --- a/svl/source/items/style.cxx +++ b/svl/source/items/style.cxx @@ -27,7 +27,6 @@ #include #include #include -#include #include #include #include -- cgit v1.2.3