tdf#63640 FILEOPEN/FILESAVE: particular .odt loads/saves very slow, part2

Use the existing sorting functionality in SfxItemPool and extend it to
search for NameOrIndex item in SvxUnoNameItemTable

This is a little tricky in that we are defining only a partial ordering
over the CntUnencodedStringItem (and their subclasses) items.
Partial because I can only use the part of
the item that is not randomly mutated by various code, which is why
the other fields in the subclasses are mostly out of bounds.

I had to exclude FillBitmapItem because it triggers a unit test
failure and I cannot figure out why that specific item does
not play nice with this optimisation.

After this optimisation, the load time goes from
3.6s to 2s on my machine.

Change-Id: I52d58c68db2536b69a7b0a9611a2b4c703bc4928
Reviewed-on: https://gerrit.libreoffice.org/71461
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

2 files changed, 94 insertions, 13 deletions

diff --git a/svl/source/inc/poolio.hxx b/svl/source/inc/poolio.hxx
index cc2039b97a66..2939d50aaf2f 100644
--- a/svl/source/inc/poolio.hxx
+++ b/svl/source/inc/poolio.hxx
@@ -33,13 +33,10 @@ class SfxItemPoolUser;
 
 static const sal_uInt32 SFX_ITEMS_DEFAULT = 0xfffffffe;
 
-struct CompareSortablePoolItems
+static bool CompareSortablePoolItems(SfxPoolItem const* lhs, SfxPoolItem const* rhs)
 {
-    bool operator()(SfxPoolItem const* lhs, SfxPoolItem const* rhs) const
-    {
-        return (*lhs) < (*rhs);
-    }
-};
+    return (*lhs) < (*rhs);
+}
 /**
  * This array contains a set of SfxPoolItems, if those items are
  * poolable then each item has a unique set of properties, and we
@@ -50,7 +47,11 @@ struct SfxPoolItemArray_Impl
 {
 private:
     o3tl::sorted_vector<SfxPoolItem*> maPoolItemSet;
-    o3tl::sorted_vector<const SfxPoolItem*, CompareSortablePoolItems> maSortablePoolItems;
+    // In some cases, e.g. subclasses of NameOrIndex, the parent class (NameOrIndex) is sortable,
+    // but the subclasses do not define an operator<, which means that we don't get an ordering
+    // strong enough to enforce uniqueness purely with operator<, which means we need to do
+    // a partial scan with operator==
+    std::vector<SfxPoolItem*> maSortablePoolItems;
 public:
     o3tl::sorted_vector<SfxPoolItem*>::const_iterator begin() const { return maPoolItemSet.begin(); }
     o3tl::sorted_vector<SfxPoolItem*>::const_iterator end() const { return maPoolItemSet.end(); }
@@ -59,22 +60,87 @@ public:
     void clear();
     size_t size() const {return maPoolItemSet.size();}
     bool empty() const {return maPoolItemSet.empty();}
+    o3tl::sorted_vector<SfxPoolItem*>::const_iterator find(SfxPoolItem* pItem) const { return maPoolItemSet.find(pItem); }
     void insert(SfxPoolItem* pItem)
     {
         maPoolItemSet.insert(pItem);
         if (pItem->IsSortable())
-            maSortablePoolItems.insert(pItem);
+        {
+            // bail early if someone modified one of these things underneath me
+            assert( std::is_sorted_until(maSortablePoolItems.begin(), maSortablePoolItems.end(), CompareSortablePoolItems) == maSortablePoolItems.end());
+
+            auto it = std::lower_bound(maSortablePoolItems.begin(), maSortablePoolItems.end(), pItem, CompareSortablePoolItems);
+            maSortablePoolItems.insert(maSortablePoolItems.begin() + (it - maSortablePoolItems.begin()), pItem);
+        }
     }
-    o3tl::sorted_vector<SfxPoolItem*>::const_iterator find(SfxPoolItem* pItem) const { return maPoolItemSet.find(pItem); }
-    const SfxPoolItem* findByLessThan(const SfxPoolItem* pItem) const
+    const SfxPoolItem* findByLessThan(const SfxPoolItem* pNeedle) const
+    {
+        // bail early if someone modified one of these things underneath me
+        assert( std::is_sorted_until(maSortablePoolItems.begin(), maSortablePoolItems.end(), CompareSortablePoolItems) == maSortablePoolItems.end());
+        assert( maPoolItemSet.empty() || maPoolItemSet.front()->IsSortable() );
+
+        auto it = std::lower_bound(maSortablePoolItems.begin(), maSortablePoolItems.end(), pNeedle, CompareSortablePoolItems);
+        for (;;)
+        {
+            if (it == maSortablePoolItems.end())
+                return nullptr;
+            if (**it < *pNeedle)
+                return nullptr;
+            if (*pNeedle == **it)
+                return *it;
+            ++it;
+        }
+    }
+    std::vector<const SfxPoolItem*> findSurrogateRange(const SfxPoolItem* pNeedle) const
     {
-        auto it = maSortablePoolItems.find(pItem);
-        return it == maSortablePoolItems.end() ? nullptr : *it;
+        std::vector<const SfxPoolItem*> rv;
+        if (!maSortablePoolItems.empty())
+        {
+            // bail early if someone modified one of these things underneath me
+            assert( std::is_sorted_until(maSortablePoolItems.begin(), maSortablePoolItems.end(), CompareSortablePoolItems) == maSortablePoolItems.end());
+
+            auto range = std::equal_range(maSortablePoolItems.begin(), maSortablePoolItems.end(), pNeedle, CompareSortablePoolItems);
+            rv.reserve(std::distance(range.first, range.second));
+            for (auto it = range.first; it != range.second; ++it)
+                rv.push_back(*it);
+        }
+        else
+        {
+            for (const SfxPoolItem* p : maPoolItemSet)
+                if (*pNeedle == *p)
+                    rv.push_back(p);
+        }
+        return rv;
     }
     void erase(o3tl::sorted_vector<SfxPoolItem*>::const_iterator it)
     {
+        auto pNeedle = *it;
         if ((*it)->IsSortable())
-            maSortablePoolItems.erase(*it);
+        {
+            // bail early if someone modified one of these things underneath me
+            assert( std::is_sorted_until(maSortablePoolItems.begin(), maSortablePoolItems.end(), CompareSortablePoolItems) == maSortablePoolItems.end());
+
+            auto sortIt = std::lower_bound(maSortablePoolItems.begin(), maSortablePoolItems.end(), pNeedle, CompareSortablePoolItems);
+            for (;;)
+            {
+                if (sortIt == maSortablePoolItems.end())
+                {
+                    assert(false && "did not find item?");
+                    break;
+                }
+                if (**sortIt < *pNeedle)
+                {
+                    assert(false && "did not find item?");
+                    break;
+                }
+                if (**sortIt == *pNeedle)
+                {
+                    maSortablePoolItems.erase(sortIt);
+                    break;
+                }
+                ++sortIt;
+            }
+        }
         return maPoolItemSet.erase(it);
     }
 };
diff --git a/svl/source/items/itempool.cxx b/svl/source/items/itempool.cxx
index 7c6f746ba319..70809ac65ad4 100644
--- a/svl/source/items/itempool.cxx
+++ b/svl/source/items/itempool.cxx
@@ -843,6 +843,21 @@ SfxItemPool::Item2Range SfxItemPool::GetItemSurrogates(sal_uInt16 nWhich) const
     return { rItemArr.begin(), rItemArr.end() };
 }
 
+/* This is only valid for SfxPoolItem that override IsSortable and operator< */
+std::vector<const SfxPoolItem*> SfxItemPool::FindItemSurrogate(sal_uInt16 nWhich, SfxPoolItem const & rSample) const
+{
+    if ( !IsInRange(nWhich) )
+    {
+        if ( pImpl->mpSecondary )
+            return pImpl->mpSecondary->FindItemSurrogate( nWhich, rSample );
+        assert(false && "unknown WhichId - cannot resolve surrogate");
+        return std::vector<const SfxPoolItem*>();
+    }
+
+    SfxPoolItemArray_Impl& rItemArr = pImpl->maPoolItemArrays[GetIndex_Impl(nWhich)];
+    return rItemArr.findSurrogateRange(&rSample);
+}
+
 sal_uInt32 SfxItemPool::GetItemCount2(sal_uInt16 nWhich) const
 {
     if ( !IsInRange(nWhich) )