From 07cda8035c34ca9f8ac3ba911a2b691349665fc7 Mon Sep 17 00:00:00 2001
From: Luboš Luňák <l.lunak@collabora.com>
Date: Wed, 24 Jun 2020 12:33:37 +0200
Subject: optimize SvtBroadcaster::Normalize() (tdf#132454)

New items are only appended, so it's wasteful to std::sort() the whole
container, just sort the unsorted part (often just one item) and then
merge.

Change-Id: I20b73730700c279e8f844c0b7a392a8f372a22da
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/97019
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>
---
 svl/source/notify/broadcast.cxx | 21 +++++++++++++++++++--
 1 file changed, 19 insertions(+), 2 deletions(-)

(limited to 'svl/source/notify')

diff --git a/svl/source/notify/broadcast.cxx b/svl/source/notify/broadcast.cxx
index 94ef1588e016..cc1ffcb10917 100644
--- a/svl/source/notify/broadcast.cxx
+++ b/svl/source/notify/broadcast.cxx
@@ -20,6 +20,7 @@
 #include <svl/broadcast.hxx>
 #include <svl/listener.hxx>
 #include <svl/hint.hxx>
+#include <o3tl/safeint.hxx>
 #include <cassert>
 #include <algorithm>
 
@@ -27,8 +28,24 @@ void SvtBroadcaster::Normalize() const
 {
     if (!mbNormalized)
     {
-        std::sort(maListeners.begin(), maListeners.end());
-        mbNormalized = true;
+        // Add() only appends new values, so often the container will be sorted expect for one
+        // or few last items. For larger containers it is much more efficient to just sort
+        // the unsorted part and then merge.
+        if(maListeners.size() > 100)
+        {
+            auto sortedEnd = std::is_sorted_until(maListeners.begin(),maListeners.end());
+            if( o3tl::make_unsigned( sortedEnd - maListeners.begin()) > maListeners.size() * 3 / 4 )
+            {
+                std::sort( sortedEnd, maListeners.end());
+                std::inplace_merge( maListeners.begin(), sortedEnd, maListeners.end());
+                mbNormalized = true;
+            }
+        }
+        if (!mbNormalized)
+        {
+            std::sort(maListeners.begin(), maListeners.end());
+            mbNormalized = true;
+        }
     }
 
     if (!mbDestNormalized)
-- 
cgit