Re: [Libreoffice] [PATCH] Replaced tools/list with std::vector in funcdesc.hxx / funcdesc.cxx

Yet another patch, removing use of tools/list from ScFunctionList,
too. In this class there should be a clear performance gain, by using
a vector instead of a list, as our tests revealed that the random
access Get() function is called 2-3000 times for each use of a
spreadsheet function. Note that we use a std::list for constructing
the object, as the number of elements is unknown while constructing,
but then convert the list to a vector at the end of the construction,
to make efficient random access possible.

With this patch (together with our last patch)
funcdesc.hxx/funcdesc.cxx shouldn't use tools/list anymore, so we have
removed the includes.
The patch compiles fine here, and scalc seems to work as expected.

Regards
Sören Möller

2011/1/28 Soeren Moeller <soerenmoeller2001@gmail.com>:
> Hi
>
> In the attached patches (0001 is the real patch, 0002 contains three
> comments missing in 0001) we have replaced use of tools/list by use of
> std::vector in ScFunctionMgr and ScFunctionCategory (in
> sc/inc/funcdesc.hxx and sc/source/core/funcdesc.cxx). We choose
> vector, as there is done random access to the lists, while they are
> only modified once (at creation). We changed the behaviour of
> ScFunctionMgr slightly, as Get() now no longer resets the iterators
> for First() and Next(), as this is quite counter intuitive. The patch
> builds fine, and the behaviour of scalc seems unchanged.
>
> The patch is joint work with Thies Pierdola, who is marked as author
> in the patch file.
>
> Regards
> Sören Möller
> (LGPLv3+/MPL for this and future patches)
From c9b432c08606761130a033e141d0e068d92b681d Mon Sep 17 00:00:00 2001
From: Thies Pierdola <thiespierdola@gmail.com>
Date: Fri, 28 Jan 2011 21:56:06 +0100
Subject: [PATCH] Replaced tools/list by std::vector in ScFunctionList

As the random access Get is called a couple of thousand times each time
a spreadsheet function is used, the use of vector should have a huge
performance gain.
---
 sc/inc/funcdesc.hxx              |   29 ++++++++---------------
 sc/source/core/data/funcdesc.cxx |   48 +++++++++++++++++++++++++++++++++----
 2 files changed, 52 insertions(+), 25 deletions(-)

diff --git a/sc/inc/funcdesc.hxx b/sc/inc/funcdesc.hxx
index 49909c5..8a2404d 100644
--- a/sc/inc/funcdesc.hxx
+++ b/sc/inc/funcdesc.hxx
@@ -29,14 +29,10 @@
 #ifndef SC_FUNCDESC_HXX
 #define SC_FUNCDESC_HXX
 
-/* Function descriptions for function wizard / autopilot / most recent used
- * list et al. Separated from the global.hxx lump, implementation still in
- * global.cxx
- */
+/* Function descriptions for function wizard / autopilot */
 
 #include "scfuncs.hrc"
 
-#include <tools/list.hxx>
 #include <formula/IFunctionDescription.hxx>
 #include <sal/types.h>
 #include <rtl/ustring.hxx>
@@ -240,26 +236,21 @@ public:
     ScFunctionList();
     ~ScFunctionList();
 
-    sal_uInt32           GetCount() const
-                    { return aFunctionList.Count(); }
+    sal_uInt32 GetCount() const
+               { return aFunctionList.size(); }
 
-    const ScFuncDesc*   First()
-                        { return (const ScFuncDesc*) aFunctionList.First(); }
+    const ScFuncDesc* First();
 
-    const ScFuncDesc*   Next()
-                        { return (const ScFuncDesc*) aFunctionList.Next(); }
+    const ScFuncDesc* Next();
 
-    const ScFuncDesc* GetFunction( sal_uInt32 nIndex ) const
-        { return static_cast<const ScFuncDesc*>(aFunctionList.GetObject(nIndex)); }
+    const ScFuncDesc* GetFunction( sal_uInt32 nIndex ) const;
 
-    ScFuncDesc* GetFunction( sal_uInt32 nIndex )
-        { return static_cast<ScFuncDesc*>(aFunctionList.GetObject(nIndex)); }
-
-    xub_StrLen      GetMaxFuncNameLen() const
-                    { return nMaxFuncNameLen; }
+    xub_StrLen GetMaxFuncNameLen() const
+               { return nMaxFuncNameLen; }
 
 private:
-    List        aFunctionList; /**< List of functions */
+    ::std::vector<const ScFuncDesc*> aFunctionList; /**< List of functions */
+    ::std::vector<const ScFuncDesc*>::iterator aFunctionListIter; /**< position in function list */
     xub_StrLen  nMaxFuncNameLen; /**< Length of longest function name */
 };
 
diff --git a/sc/source/core/data/funcdesc.cxx b/sc/source/core/data/funcdesc.cxx
index 892d643..b3a502c 100644
--- a/sc/source/core/data/funcdesc.cxx
+++ b/sc/source/core/data/funcdesc.cxx
@@ -39,7 +39,6 @@
 
 #include <rtl/ustring.hxx>
 #include <rtl/ustrbuf.hxx>
-#include <tools/list.hxx>
 #include <tools/rcid.h>
 #include <tools/resid.hxx>
 #include <tools/string.hxx>
@@ -378,14 +377,13 @@ ScFunctionList::ScFunctionList() :
     ScFuncDesc* pDesc = NULL;
     xub_StrLen nStrLen = 0;
     FuncCollection* pFuncColl;
+    ::std::list<ScFuncDesc*> tmpFuncList;
     sal_uInt16 nDescBlock[] =
     {
         RID_SC_FUNCTION_DESCRIPTIONS1,
         RID_SC_FUNCTION_DESCRIPTIONS2
     };
 
-    aFunctionList.Clear();
-
     for (sal_uInt16 k = 0; k < SAL_N_ELEMENTS(nDescBlock); ++k)
     {
         ::std::auto_ptr<ScResourcePublisher> pBlock( new ScResourcePublisher( ScResId( 
nDescBlock[k] ) ) );
@@ -411,7 +409,7 @@ ScFunctionList::ScFunctionList() :
                 else
                 {
                     pDesc->nFIndex = i;
-                    aFunctionList.Insert( pDesc, LIST_APPEND );
+                    tmpFuncList.push_back(pDesc);
 
                     nStrLen = (*(pDesc->pFuncName)).getLength();
                     if (nStrLen > nMaxFuncNameLen)
@@ -523,7 +521,7 @@ ScFunctionList::ScFunctionList() :
             }
         }
 
-        aFunctionList.Insert(pDesc, LIST_APPEND);
+        tmpFuncList.push_back(pDesc);
         nStrLen = (*(pDesc->pFuncName)).getLength();
         if ( nStrLen > nMaxFuncNameLen)
             nMaxFuncNameLen = nStrLen;
@@ -540,7 +538,7 @@ ScFunctionList::ScFunctionList() :
 
         if ( pUnoAddIns->FillFunctionDesc( nFunc, *pDesc ) )
         {
-            aFunctionList.Insert(pDesc, LIST_APPEND);
+            tmpFuncList.push_back(pDesc);
             nStrLen = (*(pDesc->pFuncName)).getLength();
             if (nStrLen > nMaxFuncNameLen)
                 nMaxFuncNameLen = nStrLen;
@@ -548,6 +546,14 @@ ScFunctionList::ScFunctionList() :
         else
             delete pDesc;
     }
+
+    //Move list to vector for better random access performance
+    aFunctionList.reserve(tmpFuncList.size());
+    aFunctionList.assign(tmpFuncList.begin(),tmpFuncList.end());
+    tmpFuncList.clear();
+
+    //Initialize iterator
+    aFunctionListIter = aFunctionList.end();
 }
 
 ScFunctionList::~ScFunctionList()
@@ -560,6 +566,36 @@ ScFunctionList::~ScFunctionList()
     }
 }
 
+const ScFuncDesc* ScFunctionList::First()
+{
+    const ScFuncDesc* pDesc = NULL;
+    aFunctionListIter = aFunctionList.begin();
+    if(aFunctionListIter != aFunctionList.end())
+        pDesc = *aFunctionListIter;
+
+    return pDesc;
+}
+
+const ScFuncDesc* ScFunctionList::Next()
+{
+    const ScFuncDesc* pDesc = NULL;
+    if(aFunctionListIter != aFunctionList.end())
+    {
+        if((++aFunctionListIter) != aFunctionList.end())
+            pDesc = *aFunctionListIter;
+    }
+    return pDesc;
+}
+
+const ScFuncDesc* ScFunctionList::GetFunction( sal_uInt32 nIndex ) const
+{
+    const ScFuncDesc* pDesc = NULL;
+    if(nIndex < aFunctionList.size())
+        pDesc = aFunctionList.at(nIndex);
+
+    return pDesc;
+}
+
 //===================================================================
 // class ScFunctionCategory:
 //===================================================================
-- 
1.7.0.4