reduce dynamic_cast usage in an O(N^2) algorithm

When scrolling down in tdf#130431 this is the major CPU cost.
Move the dynamic_cast out of the loops as much as possible.

Change-Id: I0ea9f457bb17fbdde880f09b059f07dec4b1790b
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/94858
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

3 files changed, 52 insertions, 55 deletions

diff --git a/drawinglayer/source/primitive2d/borderlineprimitive2d.cxx b/drawinglayer/source/primitive2d/borderlineprimitive2d.cxx
index a5c2a51bc44e..b264e2c028af 100644
--- a/drawinglayer/source/primitive2d/borderlineprimitive2d.cxx
+++ b/drawinglayer/source/primitive2d/borderlineprimitive2d.cxx
@@ -305,18 +305,11 @@ namespace drawinglayer::primitive2d
         ImplPrimitive2DIDBlock(BorderLinePrimitive2D, PRIMITIVE2D_ID_BORDERLINEPRIMITIVE2D)
 
         Primitive2DReference tryMergeBorderLinePrimitive2D(
-            const Primitive2DReference& rCandidateA,
-            const Primitive2DReference& rCandidateB)
+            const BorderLinePrimitive2D* pCandidateA,
+            const BorderLinePrimitive2D* pCandidateB)
         {
-            // try to cast to BorderLinePrimitive2D
-            const primitive2d::BorderLinePrimitive2D* pCandidateA = dynamic_cast< const primitive2d::BorderLinePrimitive2D* >(rCandidateA.get());
-            const primitive2d::BorderLinePrimitive2D* pCandidateB = dynamic_cast< const primitive2d::BorderLinePrimitive2D* >(rCandidateB.get());
-
-            // we need a comparable BorderLinePrimitive2D
-            if(nullptr == pCandidateA || nullptr == pCandidateB)
-            {
-                return Primitive2DReference();
-            }
+            assert(pCandidateA);
+            assert(pCandidateB);
 
             // start of candidate has to match end of this
             if(!pCandidateA->getEnd().equal(pCandidateB->getStart()))
diff --git a/include/drawinglayer/primitive2d/borderlineprimitive2d.hxx b/include/drawinglayer/primitive2d/borderlineprimitive2d.hxx
index 1a3bfa2b1b9b..537f503e5b9b 100644
--- a/include/drawinglayer/primitive2d/borderlineprimitive2d.hxx
+++ b/include/drawinglayer/primitive2d/borderlineprimitive2d.hxx
@@ -81,12 +81,6 @@ public:
     bool operator==(const BorderLine& rBorderLine) const;
 };
 
-/// helper to try to merge two instances of BorderLinePrimitive2D. If it was possible,
-/// a merged version is in the returned Primitive2DReference. Lots of preconditions
-/// have to be met to allow that, see implementation (and maybe even expand)
-Primitive2DReference DRAWINGLAYER_DLLPUBLIC tryMergeBorderLinePrimitive2D(
-    const Primitive2DReference& rCandidateA, const Primitive2DReference& rCandidateB);
-
 /** BorderLinePrimitive2D class
 
     This is the basic primitive to build frames around objects, e.g. tables.
@@ -141,6 +135,12 @@ public:
     virtual sal_uInt32 getPrimitive2DID() const override;
 };
 
+/// helper to try to merge two instances of BorderLinePrimitive2D. If it was possible,
+/// a merged version is in the returned Primitive2DReference. Lots of preconditions
+/// have to be met to allow that, see implementation (and maybe even expand)
+Primitive2DReference DRAWINGLAYER_DLLPUBLIC tryMergeBorderLinePrimitive2D(
+    const BorderLinePrimitive2D* pCandidateA, const BorderLinePrimitive2D* pCandidateB);
+
 } // end of namespace drawinglayer::primitive2d
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/svx/source/sdr/primitive2d/sdrframeborderprimitive2d.cxx b/svx/source/sdr/primitive2d/sdrframeborderprimitive2d.cxx
index 3c131948579b..9799417209f8 100644
--- a/svx/source/sdr/primitive2d/sdrframeborderprimitive2d.cxx
+++ b/svx/source/sdr/primitive2d/sdrframeborderprimitive2d.cxx
@@ -797,51 +797,55 @@ namespace drawinglayer::primitive2d
 
                     for(const auto& aCandidatePartial : aPartial)
                     {
-                        if(aRetval.empty())
-                        {
-                            // no local data yet, just add as 1st entry, done
-                            aRetval.append(aCandidatePartial);
-                        }
-                        else
-                        {
-                            bool bDidMerge(false);
+                        bool bDidMerge(false);
 
+                        // This algorithm is O(N^2) and repeated dynamic_cast inside would be quite costly.
+                        // So check first and skip if the primitives aren't BorderLinePrimitive2D.
+                        const drawinglayer::primitive2d::BorderLinePrimitive2D* candidatePartialAsBorder
+                            = dynamic_cast<const drawinglayer::primitive2d::BorderLinePrimitive2D*>(aCandidatePartial.get());
+                        if(candidatePartialAsBorder)
+                        {
                             for(auto& aCandidateRetval : aRetval)
                             {
-                                // try to merge by appending new data to existing data
-                                const drawinglayer::primitive2d::Primitive2DReference aMergeRetvalPartial(
-                                    drawinglayer::primitive2d::tryMergeBorderLinePrimitive2D(
-                                        aCandidateRetval,
-                                        aCandidatePartial));
-
-                                if(aMergeRetvalPartial.is())
-                                {
-                                    // could append, replace existing data with merged data, done
-                                    aCandidateRetval = aMergeRetvalPartial;
-                                    bDidMerge = true;
-                                    break;
-                                }
-
-                                // try to merge by appending existing data to new data
-                                const drawinglayer::primitive2d::Primitive2DReference aMergePartialRetval(
-                                    drawinglayer::primitive2d::tryMergeBorderLinePrimitive2D(
-                                        aCandidatePartial,
-                                        aCandidateRetval));
-
-                                if(aMergePartialRetval.is())
+                                const drawinglayer::primitive2d::BorderLinePrimitive2D* candidateRetvalAsBorder
+                                    = dynamic_cast<const drawinglayer::primitive2d::BorderLinePrimitive2D*>(aCandidateRetval.get());
+                                if(candidateRetvalAsBorder)
                                 {
-                                    // could append, replace existing data with merged data, done
-                                    aCandidateRetval = aMergePartialRetval;
-                                    bDidMerge = true;
-                                    break;
+                                    // try to merge by appending new data to existing data
+                                    const drawinglayer::primitive2d::Primitive2DReference aMergeRetvalPartial(
+                                        drawinglayer::primitive2d::tryMergeBorderLinePrimitive2D(
+                                            candidateRetvalAsBorder,
+                                            candidatePartialAsBorder));
+
+                                    if(aMergeRetvalPartial.is())
+                                    {
+                                        // could append, replace existing data with merged data, done
+                                        aCandidateRetval = aMergeRetvalPartial;
+                                        bDidMerge = true;
+                                        break;
+                                    }
+
+                                    // try to merge by appending existing data to new data
+                                    const drawinglayer::primitive2d::Primitive2DReference aMergePartialRetval(
+                                        drawinglayer::primitive2d::tryMergeBorderLinePrimitive2D(
+                                            candidatePartialAsBorder,
+                                            candidateRetvalAsBorder));
+
+                                    if(aMergePartialRetval.is())
+                                    {
+                                        // could append, replace existing data with merged data, done
+                                        aCandidateRetval = aMergePartialRetval;
+                                        bDidMerge = true;
+                                        break;
+                                    }
                                 }
                             }
+                        }
 
-                            if(!bDidMerge)
-                            {
-                                // no merge after checking all existing data, append as new segment
-                                aRetval.append(aCandidatePartial);
-                            }
+                        if(!bDidMerge)
+                        {
+                            // no merge after checking all existing data, append as new segment
+                            aRetval.append(aCandidatePartial);
                         }
                     }
                 }