include/svl/broadcast.hxx | 4 +-
svl/source/notify/broadcast.cxx | 76 ++++++++++++++++++++++------------------
2 files changed, 46 insertions(+), 34 deletions(-)
New commits:
commit b0e0ba28dcb69b6d042107f24c961b444eb6793e
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Fri Jun 26 08:48:55 2020 +0200
Commit: Noel Grandin <noel.gran...@collabora.co.uk>
CommitDate: Fri Jun 26 12:00:15 2020 +0200
optimize SvtBroadcaster::Normalize() even a bit more (tdf#132454)
Optimize also maDestructedListeners (often just one item). Optimize
also small vectors if there's just one item unsorted. Keep the index
of the first unsorted item in maListeners, so that it's cheap
to find out where the unsorted part starts.
This now improves tdf#132454 to 20s.
Change-Id: I21a69b440c27a2e31e74fd13b9263f54af12e320
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/97198
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.gran...@collabora.co.uk>
diff --git a/include/svl/broadcast.hxx b/include/svl/broadcast.hxx
index b4c8be5f9ac0..6569775b68d4 100644
--- a/include/svl/broadcast.hxx
+++ b/include/svl/broadcast.hxx
@@ -83,8 +83,10 @@ private:
/// Indicate that this broadcaster will be destructed (we indicate this on
all ScColumn's broadcasters during the ScTable destruction, eg.)
bool mbAboutToDie:1;
bool mbDisposing:1;
- mutable bool mbNormalized:1;
+ // Whether maDestructedListeners is sorted or not.
mutable bool mbDestNormalized:1;
+ // The first item in maListeners that is not sorted. The container can
become large, so this optimizes sorting.
+ mutable size_t mnListenersFirstUnsorted;
};
diff --git a/svl/source/notify/broadcast.cxx b/svl/source/notify/broadcast.cxx
index de7ec6b4374e..5bd8aeef1628 100644
--- a/svl/source/notify/broadcast.cxx
+++ b/svl/source/notify/broadcast.cxx
@@ -24,40 +24,42 @@
#include <cassert>
#include <algorithm>
+static void sortListeners(std::vector<SvtListener*>& listeners, size_t
firstUnsorted)
+{
+ // 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 handle
+ // the unsorted part.
+ auto sortedEnd = firstUnsorted == 0
+ ? std::is_sorted_until(listeners.begin(),listeners.end())
+ : listeners.begin() + firstUnsorted;
+ if( listeners.end() - sortedEnd == 1 )
+ { // Just one item, insert it in the right place.
+ SvtListener* item = listeners.back();
+ listeners.pop_back();
+ listeners.insert( std::upper_bound( listeners.begin(),
listeners.end(), item ), item );
+ }
+ else if( o3tl::make_unsigned( sortedEnd - listeners.begin()) >
listeners.size() * 3 / 4 )
+ { // Sort the unsorted part and then merge.
+ std::sort( sortedEnd, listeners.end());
+ std::inplace_merge( listeners.begin(), sortedEnd, listeners.end());
+ }
+ else
+ {
+ std::sort(listeners.begin(), listeners.end());
+ }
+}
+
void SvtBroadcaster::Normalize() const
{
- if (!mbNormalized)
+ if (mnListenersFirstUnsorted != maListeners.size())
{
- // 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 handle
- // the unsorted part.
- if(maListeners.size() > 100)
- {
- auto sortedEnd =
std::is_sorted_until(maListeners.begin(),maListeners.end());
- if( maListeners.end() - sortedEnd == 1 )
- { // Just one item, insert it in the right place.
- SvtListener* item = maListeners.back();
- maListeners.pop_back();
- maListeners.insert( std::upper_bound( maListeners.begin(),
maListeners.end(), item ), item );
- mbNormalized = true;
- }
- else if( o3tl::make_unsigned( sortedEnd - maListeners.begin()) >
maListeners.size() * 3 / 4 )
- { // Sort the unsorted part and then merge.
- 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;
- }
+ sortListeners(maListeners, mnListenersFirstUnsorted);
+ mnListenersFirstUnsorted = maListeners.size();
}
if (!mbDestNormalized)
{
- std::sort(maDestructedListeners.begin(), maDestructedListeners.end());
+ sortListeners(maDestructedListeners, 0);
mbDestNormalized = true;
}
}
@@ -68,9 +70,9 @@ void SvtBroadcaster::Add( SvtListener* p )
assert(!mbAboutToDie && "called after PrepareForDestruction()?");
if (mbDisposing || mbAboutToDie)
return;
- // only reset mbNormalized if we are going to become unsorted
- if (!maListeners.empty() && maListeners.back() > p)
- mbNormalized = false;
+ // Avoid normalizing if the item appended keeps the container sorted.
+ if (maListeners.empty() || (mnListenersFirstUnsorted == maListeners.size()
&& maListeners.back() < p))
+ ++mnListenersFirstUnsorted;
maListeners.push_back(p);
}
@@ -81,8 +83,10 @@ void SvtBroadcaster::Remove( SvtListener* p )
if (mbAboutToDie)
{
+ // only reset mbDestNormalized if we are going to become unsorted
+ if (!maDestructedListeners.empty() && maDestructedListeners.back() > p)
+ mbDestNormalized = false;
maDestructedListeners.push_back(p);
- mbDestNormalized = false;
return;
}
@@ -93,17 +97,23 @@ void SvtBroadcaster::Remove( SvtListener* p )
if (it != maListeners.end() && *it == p)
{
maListeners.erase(it);
+ --mnListenersFirstUnsorted;
}
if (maListeners.empty())
ListenersGone();
}
-SvtBroadcaster::SvtBroadcaster() : mbAboutToDie(false), mbDisposing(false),
mbNormalized(true), mbDestNormalized(true) {}
+SvtBroadcaster::SvtBroadcaster()
+ : mbAboutToDie(false)
+ , mbDisposing(false)
+ , mbDestNormalized(true)
+ , mnListenersFirstUnsorted(0)
+{}
SvtBroadcaster::SvtBroadcaster( const SvtBroadcaster &rBC ) :
mbAboutToDie(false), mbDisposing(false),
- mbNormalized(true), mbDestNormalized(true)
+ mbDestNormalized(true), mnListenersFirstUnsorted(0)
{
assert(!rBC.mbAboutToDie && "copying an object marked with
PrepareForDestruction()?");
assert(!rBC.mbDisposing && "copying an object that is in its destructor?");
_______________________________________________
Libreoffice-commits mailing list
libreoffice-comm...@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
