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

1 files changed, 117 insertions, 0 deletions

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();