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(-)
New commits:
commit 8aff83b95fa5969edfc48022ddaae05031b178cf
Author: Michael Meeks <michael.me...@collabora.com>
Date: Mon Jun 16 22:27:00 2014 +0100
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 <ke...@collabora.com>
Tested-by: Jan Holesovsky <ke...@collabora.com>
diff --git a/svl/CppunitTest_svl_itempool.mk b/svl/CppunitTest_svl_itempool.mk
new file mode 100644
index 0000000..4b59498
--- /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 d51b8fc..501c91a 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 f52c7a4..7589030 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 0000000..469287e
--- /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 9fa2dac..19395b5 100644
--- a/svl/source/inc/poolio.hxx
+++ b/svl/source/inc/poolio.hxx
@@ -18,14 +18,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;
@@ -52,13 +55,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
@@ -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 457b946..d18b122 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 68c93ef..caad85d 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 40e8eee..4626e59 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>
_______________________________________________
Libreoffice-commits mailing list
libreoffice-comm...@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
