Improve performance on structs 85/16785/2
Calixte DENIZET [Sat, 4 Jul 2015 13:44:37 +0000 (15:44 +0200)]
s=struct();
tic();for i=1:10000,s(string(i))=i;end;toc()
tic();for i=1:10000,s(string(i))=i;end;toc()
x=0;tic();for i=1:10000,x=x+getfield(i+2,s);end;toc()

Change-Id: I95aab823a48b981b0e97e816e8ad638a3609457b

scilab/modules/ast/includes/types/singlestruct.hxx
scilab/modules/ast/src/cpp/types/singlestruct.cpp
scilab/modules/ast/src/cpp/types/struct.cpp

index f1a79e1..3995763 100644 (file)
@@ -14,8 +14,9 @@
 #ifndef __SINGLESTRUCT_HXX__
 #define __SINGLESTRUCT_HXX__
 
-#include <map>
-#include <list>
+#include <unordered_map>
+#include <vector>
+
 #include "internal.hxx"
 #include "string.hxx"
 
@@ -47,21 +48,26 @@ public :
         return true;
     }
 
+    inline int getNumFields() const
+    {
+        return m_wstFields.size();
+    }
+
     bool                                    toString(std::wostringstream& ostr);
 
     bool                                    set(const std::wstring& _sKey, InternalType *_typedValue);
     InternalType*                           get(const std::wstring& _sKey);
     bool                                    exists(const std::wstring& _sKey);
     InternalType*                           insert(typed_list* _pArgs, InternalType* _pSource);
-    std::vector<InternalType*>              extract(std::list<std::wstring> _stFields);
+    std::vector<InternalType*>              extract(std::vector<std::wstring> & _stFields);
     String*                                 getFieldNames();
     bool                                    addField(const std::wstring& _sKey);
     bool                                    addFieldFront(const std::wstring& _sKey);
-    std::list<InternalType *>               getData();
-    std::list<std::wstring>                 getFields();
+    std::vector<InternalType *> &           getData();
+    std::vector<std::wstring>               getFieldsName();
+    std::unordered_map<std::wstring, int> & getFields();
     int                                     getFieldIndex(const std::wstring& _field);
     bool                                    removeField(const std::wstring& _sKey);
-    void                                    addFieldsFront(String* _pStrFieldNames);
 
     bool                                    operator==(const InternalType& it);
     bool                                    operator!=(const InternalType& it);
@@ -78,8 +84,9 @@ public :
     }
 
 private :
-    std::list<std::wstring> m_wstFields;
-    std::list<InternalType *> m_Data;
+
+    std::unordered_map<std::wstring, int> m_wstFields;
+    std::vector<InternalType *> m_Data;
 };
 }
 
index 33a914c..3d741fb 100644 (file)
@@ -43,45 +43,45 @@ SingleStruct::~SingleStruct()
 #endif
 }
 
-SingleStruct::SingleStruct(SingleStruct *_oSingleStructCopyMe)
+SingleStruct::SingleStruct(SingleStruct *_oSingleStructCopyMe) : m_wstFields(_oSingleStructCopyMe->getFields()), m_Data(_oSingleStructCopyMe->getData())
 {
-    std::list<std::wstring> wstFields = _oSingleStructCopyMe->getFields();
-    std::list<InternalType *> Data = _oSingleStructCopyMe->getData();
-
-    std::list<std::wstring>::iterator iterFieldName = wstFields.begin();
-    for (auto data : Data)
+    for (auto data : m_Data)
     {
-        m_wstFields.push_back(*iterFieldName);
-        m_Data.push_back(data);
-        m_Data.back()->IncreaseRef();
-        iterFieldName++;
+        data->IncreaseRef();
     }
 #ifndef NDEBUG
     Inspector::addItem(this);
 #endif
 }
 
-std::list<InternalType *> SingleStruct::getData()
+std::vector<InternalType *> & SingleStruct::getData()
 {
     return m_Data;
 }
 
-std::list<std::wstring> SingleStruct::getFields()
+std::unordered_map<std::wstring, int> & SingleStruct::getFields()
 {
     return m_wstFields;
 }
 
-int SingleStruct::getFieldIndex(const std::wstring& _field)
+std::vector<std::wstring> SingleStruct::getFieldsName()
 {
-    int idx = 0;
-    std::list<std::wstring>::iterator iterFieldNames = m_wstFields.begin();
-    for (auto name : m_wstFields)
+    std::vector<std::wstring> names;
+    names.reserve(m_wstFields.size());
+    for (const auto & p : m_wstFields)
     {
-        if (name == _field)
-        {
-            return idx;
-        }
-        idx++;
+        names.emplace_back(p.first);
+    }
+
+    return names;
+}
+
+int SingleStruct::getFieldIndex(const std::wstring & _field)
+{
+    const auto i = m_wstFields.find(_field);
+    if (i != m_wstFields.end())
+    {
+        return i->second;
     }
 
     return -1;
@@ -89,20 +89,17 @@ int SingleStruct::getFieldIndex(const std::wstring& _field)
 
 bool SingleStruct::set(const std::wstring& _sKey, InternalType *_typedValue)
 {
-    int index = getFieldIndex(_sKey);
+    const int index = getFieldIndex(_sKey);
     if (index == -1)
     {
         return false;
     }
 
-    std::list<InternalType*>::iterator iterFieldData = m_Data.begin();
-    std::advance(iterFieldData, index);
-
-    InternalType* pOld = *iterFieldData;
+    InternalType* pOld = m_Data[index];
     if (pOld != _typedValue)
     {
         /* Look if we are replacing some existing value */
-        if (pOld != NULL)
+        if (pOld != nullptr)
         {
             pOld->DecreaseRef();
             pOld->killMe();
@@ -111,11 +108,11 @@ bool SingleStruct::set(const std::wstring& _sKey, InternalType *_typedValue)
         if (_typedValue)
         {
             _typedValue->IncreaseRef();
-            *iterFieldData = _typedValue;
+            m_Data[index] = _typedValue;
         }
         else
         {
-            *iterFieldData = NULL;
+            m_Data[index] = nullptr;
         }
     }
     return true;
@@ -125,16 +122,12 @@ bool SingleStruct::set(const std::wstring& _sKey, InternalType *_typedValue)
 InternalType* SingleStruct::get(const std::wstring& _sKey)
 {
     int index = getFieldIndex(_sKey);
-
     if (index == -1)
     {
-        return NULL;
+        return nullptr;
     }
 
-    std::list<InternalType*>::iterator iterFieldData = m_Data.begin();
-    std::advance(iterFieldData, index);
-
-    return *iterFieldData;
+    return m_Data[index];
 }
 
 bool SingleStruct::exists(const std::wstring& _sKey)
@@ -167,67 +160,70 @@ InternalType* SingleStruct::insert(typed_list* _pArgs, InternalType* _pSource)
     String* pstKey = (*_pArgs)[0]->getAs<String>();
     for (int i = 0 ; i < pstKey->getSize() ; ++i)
     {
-        set(std::wstring(pstKey->get(i)), _pSource);
+        set(pstKey->get(i), _pSource);
     }
 
     return this;
-
 }
 
-std::vector<InternalType*> SingleStruct::extract(std::list<std::wstring> _stFields)
+std::vector<InternalType*> SingleStruct::extract(std::vector<std::wstring> & _stFields)
 {
     std::vector<InternalType*> Result;
 
-    std::list<std::wstring>::const_iterator it;
-    for (it = _stFields.begin() ; it != _stFields.end() ; it++)
+    for (const auto & f : _stFields)
     {
-        if (exists(*it) == false)
+        if (!exists(f))
         {
             return Result;
         }
     }
 
-    for (it = _stFields.begin() ; it != _stFields.end() ; it++)
+    for (const auto & f : _stFields)
     {
-        Result.push_back(get(*it));
+        Result.push_back(get(f));
     }
+
     return Result;
 }
 
 String* SingleStruct::getFieldNames()
 {
-    String* pOut = new String((int)m_wstFields.size(), 1);
+    std::set<std::wstring> names;
+    for (const auto & p : m_wstFields)
+    {
+        names.emplace(p.first);
+    }
+
+    String* pOut = new String((int)names.size(), 1);
     int i = 0;
-    for (auto name : m_wstFields)
+    for (const auto & name : names)
     {
         pOut->set(i++, name.c_str());
     }
     return pOut;
 }
 
-bool SingleStruct::removeField(const std::wstring& _sKey)
+bool SingleStruct::removeField(const std::wstring & _sKey)
 {
-    std::list<std::wstring>::iterator iterFieldNames = m_wstFields.begin();
-    std::list<InternalType*>::iterator iterFieldData = m_Data.begin();
-    std::list<std::wstring> wstFields;
-    std::list<InternalType *> Data;
-
-    for (int i = 0; iterFieldNames != m_wstFields.end(); iterFieldNames++, iterFieldData++, i++)
+    const auto i = m_wstFields.find(_sKey);
+    if (i != m_wstFields.end())
     {
-        if (*iterFieldNames == _sKey)
+        const int pos = i->second;
+        m_Data[pos]->DecreaseRef();
+        m_Data[pos]->killMe();
+        m_wstFields.erase(i);
+
+        for (auto & p : m_wstFields)
         {
-            (*iterFieldData)->DecreaseRef();
-            (*iterFieldData)->killMe();
-            continue;
+            if (p.second > pos)
+            {
+                --p.second;
+            }
         }
 
-        wstFields.push_back(*iterFieldNames);
-        Data.push_back(*iterFieldData);
+        m_Data.erase(m_Data.begin() + pos);
     }
 
-    m_wstFields = wstFields;
-    m_Data = Data;
-
     return true;
 }
 
@@ -240,10 +236,11 @@ bool SingleStruct::addField(const std::wstring& _sKey)
     }
 
     //not found so add field with []
-    m_wstFields.push_back(_sKey);
     InternalType* pIT = Double::Empty();
     pIT->IncreaseRef();
     m_Data.push_back(pIT);
+    m_wstFields.emplace(_sKey, m_Data.size() - 1);
+
     return true;
 }
 
@@ -256,10 +253,16 @@ bool SingleStruct::addFieldFront(const std::wstring& _sKey)
     }
 
     //not found so add field with []
-    m_wstFields.push_front(_sKey);
     InternalType* pIT = Double::Empty();
     pIT->IncreaseRef();
-    m_Data.push_front(pIT);
+    m_Data.insert(m_Data.begin(), pIT);
+
+    for (auto & p : m_wstFields)
+    {
+        p.second++;
+    }
+
+    m_wstFields.emplace(_sKey, 0);
     return true;
 }
 
@@ -272,11 +275,10 @@ bool SingleStruct::toString(std::wostringstream& ostr)
     }
     else
     {
-        std::list<std::wstring>::iterator iterFieldNames;
-        std::list<InternalType*>::iterator iterFieldData = m_Data.begin();
-        for (iterFieldNames = m_wstFields.begin() ; iterFieldNames != m_wstFields.end(); iterFieldNames++, iterFieldData++)
+
+        for (auto & p : m_wstFields)
         {
-            ostr << *iterFieldNames << L" : " << (*iterFieldData)->getTypeStr() << std::endl;
+            ostr << p.first << L" : " << m_Data[p.second]->getTypeStr() << std::endl;
         }
     }
 
@@ -292,33 +294,18 @@ bool SingleStruct::operator==(const InternalType& it)
 
     SingleStruct* other = const_cast<InternalType &>(it).getAs<SingleStruct>();
 
-    std::list<std::wstring> otherFieldNames = other->getFields();
-    std::list<InternalType*> otherFieldData = other->getData();
+    std::unordered_map<std::wstring, int> & otherFieldNames = other->getFields();
+    std::vector<InternalType*> & otherFieldData = other->getData();
 
     if (m_wstFields.size() != otherFieldNames.size())
     {
         return false;
     }
 
-    if (m_Data.size() != otherFieldData.size())
-    {
-        return false;
-    }
-
-    std::list<std::wstring>::iterator itFieldNames = m_wstFields.begin();
-    std::list<InternalType*>::iterator itFieldData = m_Data.begin();
-
-    std::list<std::wstring>::iterator itOtherFieldNames = otherFieldNames.begin();
-    std::list<InternalType*>::iterator itOtherFieldData = otherFieldData.begin();
-
-    for (; itFieldNames != m_wstFields.end(); itFieldNames++, itOtherFieldNames++, itFieldData++, itOtherFieldData++)
+    for (const auto & p : m_wstFields)
     {
-        if (*itFieldNames != *itOtherFieldNames)
-        {
-            return false;
-        }
-
-        if (*(*itFieldData) != *(*itOtherFieldData))
+        const auto i = otherFieldNames.find(p.first);
+        if (i == otherFieldNames.end() || (*m_Data[p.second] != *otherFieldData[i->second]))
         {
             return false;
         }
index 3fde4f6..b2076b0 100644 (file)
@@ -614,17 +614,15 @@ std::vector<InternalType*> Struct::extractFields(typed_list* _pArgs)
         {
             break;
         }
-        else if (iIndex > (int)get(0)->getData().size() + 2)
+        else if (iIndex > (int)get(0)->getNumFields() + 2)
         {
             break;
         }
         else if (getSize() == 1)
         {
             //return elements
-            std::list<InternalType*> pData = get(0)->getData();
-            std::list<InternalType*>::iterator it = pData.begin();
-            std::advance(it, iIndex - 3);
-            ResultList.push_back((*it)->clone());
+            const std::vector<InternalType*> & pData = get(0)->getData();
+            ResultList.push_back(pData[iIndex - 3]->clone());
         }
         else
         {
@@ -634,10 +632,8 @@ std::vector<InternalType*> Struct::extractFields(typed_list* _pArgs)
             for (int j = 0 ; j < getSize() ; j++)
             {
                 //-2 for fieldlist and dims, -1 for indexed at 0
-                std::list<InternalType*> pData = get(j)->getData();
-                std::list<InternalType*>::iterator it = pData.begin();
-                std::advance(it, iIndex - 3);
-                pL->append((*it)->clone());
+                const std::vector<InternalType*> & pData = get(j)->getData();
+                pL->append(pData[iIndex - 3]->clone());
             }
 
             ResultList.push_back(pL);