ITEM: speedup WhichRanges access by buffering

I checked for was to speedup SfxItemSet stuff, so had
(besides other things) a look at WhichRangesContainer
and it's usage(s). Problem with the WhichRanges is that
a WhichID which you try to find is usually inside that
range, so binary search is no option. You have to detect
in which range the WhichID is hosted and can the directly
calculate the index into the array of Items at the
SfxtemSet.
Currently when needing to transform a WhichID to an index
into the array of Items in SfxItemSet the array of the
WhichRangesContainer is searched linearly from the start
every time.
This can be a little bit speed up by buffering the last
successful 'hit' and trying to re-use it. Also the
special case of a single WhichPair (e.g. UI stuff) is
worth having a look.
All acesses to that transformation are changed to use
the tooling method getOffsetFromWhich() at the
WhichRangesContainer which does the transformation.
This also needed cleanup of ItemOffsetHint instances
& stuff around it. It does not more than before but
also profits from the single entry buffer.
I added some DBG_UTIL-based stuff to watch the hit/miss
ratio, which is heavily changing from app to app & usage,
but varies around 1.5 to 3.5, also saw 6.5 and more at
document import.
NOTE: I already checked if sorting the WhichPair(s) in
WhichRangesContainer by their 'width' (highest WhichID
mnius lowest WhichID helps. The idea was when the Items
would be used in a regular manner that when having the
widest WhichPairs at the start, the buffer would even
be better used - but doing tests in all apps shows
nearly no gain, so I left that out.
NOTE: Not too much speedup, but faster...

Had to deep-debug due to CppunitTest_sw_odfexport failing,
found a slight diff between GetItemState impls, corrected.
Also added more changes, e.g. TotalCount is now a member
to not always have to calculate it from the
WhichRangesContainer.
Extended GetWhichByPos to 1st try to find a set Item, else
iterate over WhichRangesContainer.
This is due to SfxItemIter's implementations of
GetItemState and ClearItem which both up to now just
accessed the SfxPoolItem array of the SfxItemSet, ignoring
that no Item (nullptr) or state DONTCARE (-1) may have been
set there (no item is prevented by ite Iterator, but better
be careful).

Added WhichRangesContainer::getWhichFromOffset and made
SfxItemSet::GetWhichByOffset use it. Addedd optimizations
there for single-entry WhichPair and using the buffer at
WhichRangesContainer which is possible.
Removed debug comparing stuff (had a test that used the
former adapted GetItemStateImpl method in
SfxItemSet::GetItemState and compared with the changed
GetItemState_ForWhichID).
Added some comments and assertions where useful.
Made ClearSingleItem_ForOffset work without handing
over WhichID, that makes calls using it simpler and
avoids calculating the WhichID just for that call.

Change-Id: I54de552368b654f00f115978715f8241eb603752
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/155316
Tested-by: Jenkins
Reviewed-by: Armin Le Grand <Armin.Le.Grand@me.com>

2 files changed, 35 insertions, 10 deletions

diff --git a/include/svl/itemset.hxx b/include/svl/itemset.hxx
index 52966ecc96d6..468893557b5e 100644
--- a/include/svl/itemset.hxx
+++ b/include/svl/itemset.hxx
@@ -40,9 +40,10 @@ class SAL_WARN_UNUSED SVL_DLLPUBLIC SfxItemSet
 
     SfxItemPool*      m_pPool;         ///< pool that stores the items
     const SfxItemSet* m_pParent;       ///< derivation
+    sal_uInt16        m_nCount;        ///< number of items
+    sal_uInt16        m_nTotalCount;   ///< number of WhichIDs, also size of m_ppItems array
     SfxPoolItem const** m_ppItems;     ///< pointer to array of items, we allocate and free this unless m_bItemsFixed==true
     WhichRangesContainer m_pWhichRanges;  ///< array of Which Ranges
-    sal_uInt16        m_nCount;        ///< number of items
     bool              m_bItemsFixed; ///< true if this is a SfxItemSetFixed object
 
 friend class SfxItemPoolCache;
@@ -69,7 +70,7 @@ protected:
     enum class SfxAllItemSetFlag { Flag };
     SfxItemSet( SfxItemPool&, SfxAllItemSetFlag );
     /** special constructor for SfxItemSetFixed */
-    SfxItemSet( SfxItemPool&, WhichRangesContainer&& ranges, SfxPoolItem const ** ppItems );
+    SfxItemSet( SfxItemPool&, WhichRangesContainer&& ranges, SfxPoolItem const ** ppItems, sal_uInt16 nTotalCount );
 
 public:
     SfxItemSet( const SfxItemSet& );
@@ -93,7 +94,7 @@ public:
 
     // Get number of items
     sal_uInt16                  Count() const { return m_nCount; }
-    sal_uInt16                  TotalCount() const;
+    sal_uInt16                  TotalCount() const { return m_nTotalCount; }
 
     const SfxPoolItem&          Get( sal_uInt16 nWhich, bool bSrchInParent = true ) const;
     template<class T>
@@ -140,7 +141,7 @@ public:
         return GetItem<T>(pItemSet, static_cast<sal_uInt16>(nWhich), bSearchInParent);
     }
 
-    sal_uInt16                  GetWhichByPos(sal_uInt16 nPos) const;
+    sal_uInt16                  GetWhichByOffset(sal_uInt16 nOffset) const;
 
     SfxItemState                GetItemState(   sal_uInt16 nWhich,
                                                 bool bSrchInParent = true,
@@ -224,12 +225,15 @@ public:
     void dumpAsXml(xmlTextWriterPtr pWriter) const;
 
 private:
-    sal_uInt16 ClearSingleItemImpl( sal_uInt16 nWhich, std::optional<sal_uInt16> oItemOffsetHint );
+    // split version(s) of ClearSingleItemImpl for input types WhichID and Offset
+    sal_uInt16 ClearSingleItem_ForWhichID( sal_uInt16 nWhich );
+    sal_uInt16 ClearSingleItem_ForOffset( sal_uInt16 nOffset );
+
     sal_uInt16 ClearAllItemsImpl();
-    SfxItemState  GetItemStateImpl( sal_uInt16 nWhich,
-                                bool bSrchInParent,
-                                const SfxPoolItem **ppItem,
-                                std::optional<sal_uInt16> oItemsOffsetHint) const;
+
+    // split version(s) of GetItemStateImpl for input types WhichID and Offset
+    SfxItemState GetItemState_ForWhichID( SfxItemState eState, sal_uInt16 nWhich, bool bSrchInParent, const SfxPoolItem **ppItem) const;
+    SfxItemState GetItemState_ForOffset( sal_uInt16 nOffset, const SfxPoolItem **ppItem) const;
 };
 
 inline void SfxItemSet::SetParent( const SfxItemSet* pNew )
@@ -275,7 +279,7 @@ class SfxItemSetFixed : public SfxItemSet
 {
 public:
     SfxItemSetFixed( SfxItemPool& rPool)
-        : SfxItemSet(rPool, WhichRangesContainer(svl::Items_t<WIDs...>{}), m_aItems) {}
+        : SfxItemSet(rPool, WhichRangesContainer(svl::Items_t<WIDs...>{}), m_aItems, NITEMS) {}
 private:
     static constexpr sal_uInt16 NITEMS = svl::detail::CountRanges1<WIDs...>();
     const SfxPoolItem* m_aItems[NITEMS] = {};
diff --git a/include/svl/whichranges.hxx b/include/svl/whichranges.hxx
index 744a0f2edaf5..37a3d34e5613 100644
--- a/include/svl/whichranges.hxx
+++ b/include/svl/whichranges.hxx
@@ -71,6 +71,8 @@ template <sal_uInt16... WIDs> struct Items_t
 template <sal_uInt16... WIDs> inline static constexpr auto Items = Items_t<WIDs...>{};
 }
 
+#define INVALID_WHICHPAIR_OFFSET (sal_uInt16(0xffff))
+
 /**
  * Most of the time, the which ranges we point at are a compile-time literal.
  * So we take advantage of that, and avoid the cost of allocating our own array and copying into it.
@@ -85,12 +87,21 @@ struct SVL_DLLPUBLIC WhichRangesContainer
       * at a global const literal */
     bool m_bOwnRanges = false;
 
+    // variables for buffering the last used WhichPair to allow fast answers
+    // in getOffsetFromWhich
+    mutable sal_uInt16 m_aLastWhichPairOffset = INVALID_WHICHPAIR_OFFSET;
+    mutable sal_uInt16 m_aLastWhichPairFirst = 0;
+    mutable sal_uInt16 m_aLastWhichPairSecond = 0;
+
     WhichRangesContainer() = default;
 
     WhichRangesContainer(std::unique_ptr<WhichPair[]> wids, sal_Int32 nSize)
         : m_pairs(wids.release())
         , m_size(nSize)
         , m_bOwnRanges(true)
+        , m_aLastWhichPairOffset(INVALID_WHICHPAIR_OFFSET)
+        , m_aLastWhichPairFirst(0)
+        , m_aLastWhichPairSecond(0)
     {
     }
     template <sal_uInt16... WIDs>
@@ -98,6 +109,9 @@ struct SVL_DLLPUBLIC WhichRangesContainer
         : m_pairs(svl::Items_t<WIDs...>::value.data())
         , m_size(svl::Items_t<WIDs...>::value.size())
         , m_bOwnRanges(false)
+        , m_aLastWhichPairOffset(INVALID_WHICHPAIR_OFFSET)
+        , m_aLastWhichPairFirst(0)
+        , m_aLastWhichPairSecond(0)
     {
     }
     WhichRangesContainer(const WhichPair* wids, sal_Int32 nSize);
@@ -121,6 +135,13 @@ struct SVL_DLLPUBLIC WhichRangesContainer
     }
     void reset();
 
+    // calculate and return the offset inside the fixed SfxPoolItem
+    // array of SfxItemPool
+    sal_uInt16 getOffsetFromWhich(sal_uInt16 nWhich) const;
+
+    // extract the WhichID for given offset
+    sal_uInt16 getWhichFromOffset(sal_uInt16 nOffset) const;
+
     // Adds a range to which ranges, keeping the ranges in valid state (sorted, non-overlapping)
     SAL_WARN_UNUSED_RESULT WhichRangesContainer MergeRange(sal_uInt16 nFrom, sal_uInt16 nTo) const;
 };