From ad6660a639aba236c9d30485da1cd2bb1292ef83 Mon Sep 17 00:00:00 2001 From: Vladimir Levin Date: Thu, 18 Jan 2018 12:35:11 -0800 Subject: Use equal_range for factory lookups This patch uses equal_range instead of linear search to look up a factory entry by name. This does require a sort, but the expected usage is that the sort happens once and look ups happen many times. This improves performance on Chromium's oop deserialization of flattenables by about 10% R=reed@chromium.org Change-Id: I907f457a2ffb7d5b6d8261343099d982260b8415 Reviewed-on: https://skia-review.googlesource.com/96820 Reviewed-by: Mike Klein Commit-Queue: Mike Klein --- gn/tests.gni | 1 + include/core/SkFlattenable.h | 1 + src/core/SkFlattenable.cpp | 52 +++++++++++++++++++++----------- src/core/SkGlobalInitialization_core.cpp | 3 ++ tests/FlattenableNameToFactory.cpp | 24 +++++++++++++++ 5 files changed, 64 insertions(+), 17 deletions(-) create mode 100644 tests/FlattenableNameToFactory.cpp diff --git a/gn/tests.gni b/gn/tests.gni index 18defe8ae1..15c7c83fe6 100644 --- a/gn/tests.gni +++ b/gn/tests.gni @@ -71,6 +71,7 @@ tests_sources = [ "$_tests/FitsInTest.cpp", "$_tests/FlattenableCustomFactory.cpp", "$_tests/FlattenableFactoryToName.cpp", + "$_tests/FlattenableNameToFactory.cpp", "$_tests/FlattenDrawableTest.cpp", "$_tests/Float16Test.cpp", "$_tests/FloatingPointTextureTest.cpp", diff --git a/include/core/SkFlattenable.h b/include/core/SkFlattenable.h index eaaf9c3d92..cfeda8fe6c 100644 --- a/include/core/SkFlattenable.h +++ b/include/core/SkFlattenable.h @@ -147,6 +147,7 @@ protected: private: static void InitializeFlattenablesIfNeeded(); + static void Finalize(); friend class SkGraphics; diff --git a/src/core/SkFlattenable.cpp b/src/core/SkFlattenable.cpp index c975023367..0c673181a7 100644 --- a/src/core/SkFlattenable.cpp +++ b/src/core/SkFlattenable.cpp @@ -9,6 +9,8 @@ #include "SkPtrRecorder.h" #include "SkReadBuffer.h" +#include + SkNamedFactorySet::SkNamedFactorySet() : fNextAddedFactory(0) {} uint32_t SkNamedFactorySet::find(SkFlattenable::Factory factory) { @@ -48,14 +50,34 @@ void SkRefCntSet::decPtr(void* ptr) { /////////////////////////////////////////////////////////////////////////////// +namespace { + struct Entry { const char* fName; SkFlattenable::Factory fFactory; SkFlattenable::Type fType; }; -static int gCount = 0; -static Entry gEntries[128]; +struct EntryComparator { + bool operator()(const Entry& a, const Entry& b) const { + return strcmp(a.fName, b.fName) < 0; + } + bool operator()(const Entry& a, const char* b) const { + return strcmp(a.fName, b) < 0; + } + bool operator()(const char* a, const Entry& b) const { + return strcmp(a, b.fName) < 0; + } +}; + +int gCount = 0; +Entry gEntries[128]; + +} // namespace + +void SkFlattenable::Finalize() { + std::sort(gEntries, gEntries + gCount, EntryComparator()); +} void SkFlattenable::Register(const char name[], Factory factory, SkFlattenable::Type type) { SkASSERT(name); @@ -80,32 +102,28 @@ static void report_no_entries(const char* functionName) { SkFlattenable::Factory SkFlattenable::NameToFactory(const char name[]) { InitializeFlattenablesIfNeeded(); + SkASSERT(std::is_sorted(gEntries, gEntries + gCount, EntryComparator())); #ifdef SK_DEBUG report_no_entries(__FUNCTION__); #endif - const Entry* entries = gEntries; - for (int i = gCount - 1; i >= 0; --i) { - if (strcmp(entries[i].fName, name) == 0) { - return entries[i].fFactory; - } - } - return nullptr; + auto pair = std::equal_range(gEntries, gEntries + gCount, name, EntryComparator()); + if (pair.first == pair.second) + return nullptr; + return pair.first->fFactory; } bool SkFlattenable::NameToType(const char name[], SkFlattenable::Type* type) { SkASSERT(type); InitializeFlattenablesIfNeeded(); + SkASSERT(std::is_sorted(gEntries, gEntries + gCount, EntryComparator())); #ifdef SK_DEBUG report_no_entries(__FUNCTION__); #endif - const Entry* entries = gEntries; - for (int i = gCount - 1; i >= 0; --i) { - if (strcmp(entries[i].fName, name) == 0) { - *type = entries[i].fType; - return true; - } - } - return false; + auto pair = std::equal_range(gEntries, gEntries + gCount, name, EntryComparator()); + if (pair.first == pair.second) + return false; + *type = pair.first->fType; + return true; } const char* SkFlattenable::FactoryToName(Factory fact) { diff --git a/src/core/SkGlobalInitialization_core.cpp b/src/core/SkGlobalInitialization_core.cpp index bc3e254bd0..f4f2ec8cb7 100644 --- a/src/core/SkGlobalInitialization_core.cpp +++ b/src/core/SkGlobalInitialization_core.cpp @@ -50,6 +50,9 @@ void SkFlattenable::PrivateInitializer::InitCore() { // Now initialize any optional/additional effects (implemented in src/ports) InitEffects(); + + // Finalize flattenable initialization. + SkFlattenable::Finalize(); }; void SkFlattenable::InitializeFlattenablesIfNeeded() { diff --git a/tests/FlattenableNameToFactory.cpp b/tests/FlattenableNameToFactory.cpp new file mode 100644 index 0000000000..d082504800 --- /dev/null +++ b/tests/FlattenableNameToFactory.cpp @@ -0,0 +1,24 @@ +/* + * Copyright 2018 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#include "SkFlattenable.h" +#include "Test.h" + +DEF_TEST(FlattenableNameToFactory, r) { + if (!SkFlattenable::NameToFactory("SkImageShader")) { + ERRORF(r, "SkFlattenable::NameToFactory() fails with SkImageShader."); + } + if (SkFlattenable::NameToFactory("AAA-non-existent")) { + ERRORF(r, "SkFlattenable::NameToFactory() succeeds with AAA-non-existent."); + } + if (SkFlattenable::NameToFactory("SkNonExistent")) { + ERRORF(r, "SkFlattenable::NameToFactory() succeeds with SkNonExistent"); + } + if (SkFlattenable::NameToFactory("ZZZ-non-existent")) { + ERRORF(r, "SkFlattenable::NameToFactory() succeeds with ZZZ-non-existent."); + } +} -- cgit v1.2.3