[Libreoffice] [REVIEW] Speed up range name lookup from formula interpreter

Hi there,

I'd like to have the attached patch reviewed and pushed to the -3-4
branch.

It makes range name lookups by index a constant time which drastically
improves formula calculation performance especially with documents with
a larger number of named ranges.  This also improves the import
performance of binary Excel documents since the xls import filter
currently re-uses the range name storage to emulate shared formulas.

Review and sign-off appreciated.

Kohei

-- 
Kohei Yoshida, LibreOffice hacker, Calc

From 393f4815499c79575cb46952ecdaa9bb58918dc9 Mon Sep 17 00:00:00 2001
From: Kohei Yoshida <kohei.yoshida@suse.com>
Date: Fri, 2 Sep 2011 17:05:47 -0400
Subject: [PATCH] Speed up range name lookup by index.

This should speed up formula calculations considerably during xls
import since shared formulas are also stored in ScRangeName and
they are looked up by index. (bnc#715104)
---
 sc/inc/rangenam.hxx              |   10 ++++++++
 sc/source/core/tool/rangenam.cxx |   45 +++++++++++++++++++++++++++-----------
 2 files changed, 42 insertions(+), 13 deletions(-)

diff --git a/sc/inc/rangenam.hxx b/sc/inc/rangenam.hxx
index 21cf333..e3b1785 100644
--- a/sc/inc/rangenam.hxx
+++ b/sc/inc/rangenam.hxx
@@ -36,6 +36,7 @@
 #include "scdllapi.h"
 
 #include <map>
+#include <vector>
 #include <boost/ptr_container/ptr_set.hpp>
 #include <boost/ptr_container/ptr_map.hpp>
 
@@ -179,8 +180,10 @@ bool operator< (const ScRangeData& left, const ScRangeData& right);
 class ScRangeName
 {
 private:
+    typedef std::vector<ScRangeData*> IndexDataType;
     typedef ::boost::ptr_set<ScRangeData> DataType;
     DataType maData;
+    IndexDataType maIndexToData;
 
 public:
     /// Map that manages stored ScRangeName instances.
@@ -215,7 +218,14 @@ public:
     SC_DLLPUBLIC size_t size() const;
     bool empty() const;
     SC_DLLPUBLIC bool insert(ScRangeData* p);
+
     void erase(const ScRangeData& r);
+
+    /**
+     * Erase by iterator position.  Note that this method doesn't check for
+     * iterator's validity.  The caller must make sure that the iterator is
+     * valid.
+     */
     void erase(const iterator& itr);
     void clear();
     bool operator== (const ScRangeName& r) const;
diff --git a/sc/source/core/tool/rangenam.cxx b/sc/source/core/tool/rangenam.cxx
index efad9fe..599590a 100644
--- a/sc/source/core/tool/rangenam.cxx
+++ b/sc/source/core/tool/rangenam.cxx
@@ -735,7 +735,7 @@ void ScRangeName::copyLocalNames(const TabNameMap& rNames, TabNameCopyMap& rCopy
 ScRangeName::ScRangeName() {}
 
 ScRangeName::ScRangeName(const ScRangeName& r) :
-    maData(r.maData) {}
+    maData(r.maData), maIndexToData(r.maIndexToData) {}
 
 const ScRangeData* ScRangeName::findByRange(const ScRange& rRange) const
 {
@@ -774,9 +774,12 @@ const ScRangeData* ScRangeName::findByUpperName(const OUString& rName) const
 
 ScRangeData* ScRangeName::findByIndex(sal_uInt16 i)
 {
-    DataType::iterator itr = std::find_if(
-        maData.begin(), maData.end(), MatchByIndex(i));
-    return itr == maData.end() ? NULL : &(*itr);
+    if (!i)
+        // index should never be zero.
+        return NULL;
+
+    size_t nPos = i - 1;
+    return nPos < maIndexToData.size() ? maIndexToData[nPos] : NULL;
 }
 
 void ScRangeName::UpdateReference(
@@ -845,35 +848,51 @@ bool ScRangeName::insert(ScRangeData* p)
 
     if (!p->GetIndex())
     {
-        // Assign a new index.  An index must be unique.
-        sal_uInt16 nHigh = 0;
-        DataType::const_iterator itr = maData.begin(), itrEnd = maData.end();
-        for (; itr != itrEnd; ++itr)
+        // Assign a new index.  An index must be unique and is never 0.
+        IndexDataType::iterator itr = std::find(
+            maIndexToData.begin(), maIndexToData.end(), static_cast<ScRangeData*>(NULL));
+        if (itr != maIndexToData.end())
         {
-            sal_uInt16 n = itr->GetIndex();
-            if (n > nHigh)
-                nHigh = n;
+            // Empty slot exists.  Re-use it.
+            size_t nPos = std::distance(maIndexToData.begin(), itr);
+            p->SetIndex(nPos + 1);
         }
-        p->SetIndex(nHigh + 1);
+        else
+            // No empty slot.  Append it to the end.
+            p->SetIndex(maIndexToData.size() + 1);
     }
 
     pair<DataType::iterator, bool> r = maData.insert(p);
+    if (r.second)
+    {
+        // Data inserted.  Store its index for mapping.
+        size_t nPos = p->GetIndex() - 1;
+        if (nPos >= maIndexToData.size())
+            maIndexToData.resize(nPos+1, NULL);
+        maIndexToData[nPos] = p;
+    }
     return r.second;
 }
 
 void ScRangeName::erase(const ScRangeData& r)
 {
-    maData.erase(r);
+    DataType::iterator itr = maData.find(r);
+    if (itr != maData.end())
+        erase(itr);
 }
 
 void ScRangeName::erase(const iterator& itr)
 {
+    sal_uInt16 nIndex = itr->GetIndex();
     maData.erase(itr);
+    if (nIndex < maIndexToData.size())
+        maIndexToData[nIndex] = NULL;
 }
 
 void ScRangeName::clear()
 {
     maData.clear();
+    maIndexToData.clear();
 }
 
 bool ScRangeName::operator== (const ScRangeName& r) const
-- 
1.7.3.4