* Bug 15087 fixed: deleting rows or cols from matrix was slow 65/20965/7
St├ęphane MOTTELET [Fri, 3 May 2019 12:11:30 +0000 (14:11 +0200)]
https://bugzilla.scilab.org/show_bug.cgi?id=15087

Change-Id: Ia9e7161a684b2dee75a78f323c98264182d26a73

scilab/CHANGES.md
scilab/modules/ast/src/cpp/types/arrayof.cpp
scilab/modules/ast/tests/nonreg_tests/bug_15087.tst [new file with mode: 0644]

index 09eb112..88aab6b 100644 (file)
@@ -147,6 +147,7 @@ Bug Fixes
 * [#14812](http://bugzilla.scilab.org/show_bug.cgi?id=14812): Minor typos in messages.
 * [#14863](http://bugzilla.scilab.org/show_bug.cgi?id=14863): In Xcos, the default ending time was unhandily high (100000), reduced it to 30.
 * [#14982](http://bugzilla.scilab.org/show_bug.cgi?id=14982): `msprintf` segmentation fault was caught due to wrong size
+* [#15087](http://bugzilla.scilab.org/show_bug.cgi?id=15087): Deleting rows or columns from a matrix is slow (regression)
 * [#15269](http://bugzilla.scilab.org/show_bug.cgi?id=15269): `xgetech` was poor and stiff compared to any combination of `gca()` properties `.axes_bounds`, `.data_bounds`, `.log_flags`, and `.margins`. It is removed.
 * [#15271](http://bugzilla.scilab.org/show_bug.cgi?id=15271): `bitget` needed to be upgraded.
 * [#15425](http://bugzilla.scilab.org/show_bug.cgi?id=15425): The Kronecker product `a.*.b` failed when `a` or `b` or both are hypermatrices, with one or both being polynomials or rationals.
index dd5c266..b42aa90 100644 (file)
@@ -868,110 +868,69 @@ GenericType* ArrayOf<T>::remove(typed_list* _pArgs)
         return this;
     }
 
-    bool* pbFull = new bool[iDims];
-    //coord must represent all values on a dimension
+    int iToDelIndex = -1;
+    std::vector<int> toDelIndexVect;
+
+    // dimensions not subject to deletion must be indexed with colon or equivalent
     for (int i = 0; i < iDims; i++)
     {
-        pbFull[i] = false;
         int iDimToCheck = getVarMaxDim(i, iDims);
         int iIndexSize = pArg[i]->getAs<GenericType>()->getSize();
-
-        //we can have index more than once
-        if (iIndexSize >= iDimToCheck)
+        if ((*_pArgs)[i]->isColon() == false)
         {
-            //size is good, now check datas
+            //if equivalent to colon, should be 1:iDimToCheck after sorting and removing duplicates
             double* pIndexes = getDoubleArrayFromDouble(pArg[i]);
-            for (int j = 0; j < iDimToCheck; j++)
+            std::vector<int> pIndexesVect(pIndexes, pIndexes + iIndexSize);
+            std::sort(pIndexesVect.begin(), pIndexesVect.end());
+            pIndexesVect.erase(unique(pIndexesVect.begin(), pIndexesVect.end()), pIndexesVect.end());
+            //remove index > iDimToCheck to allow a[10, 10](1, 1:100) = [] and a[10, 10]([1 5 20], :) = []
+            auto lastUnique = std::find_if(pIndexesVect.begin(), pIndexesVect.end(),
+                                           [&iDimToCheck](int idx) { return idx > iDimToCheck; });
+            pIndexesVect.erase(lastUnique, pIndexesVect.end());
+
+            if (pIndexesVect.size() != iDimToCheck)
             {
-                bool bFind = false;
-                for (int k = 0; k < iIndexSize; k++)
+                // index is not equivalent to colon -> index to delete
+                if (iToDelIndex < 0)
                 {
-                    if ((int)pIndexes[k] == j + 1)
-                    {
-                        bFind = true;
-                        break;
-                    }
+                    iToDelIndex = i;
+                    toDelIndexVect = pIndexesVect;
+                }
+                else
+                {
+                    //cannot delete indexes on more than one dimension
+                    //free pArg content
+                    cleanIndexesArguments(_pArgs, &pArg);
+                    return NULL;
                 }
-                pbFull[i] = bFind;
-            }
-        }
-    }
-
-    //only one dims can be not full/entire
-    bool bNotEntire = false;
-    int iNotEntire = 0;
-    bool bTooMuchNotEntire = false;
-    for (int i = 0; i < iDims; i++)
-    {
-        if (pbFull[i] == false)
-        {
-            if (bNotEntire == false)
-            {
-                bNotEntire = true;
-                iNotEntire = i;
-            }
-            else
-            {
-                bTooMuchNotEntire = true;
-                break;
             }
         }
     }
 
-    delete[] pbFull;
-
-    if (bTooMuchNotEntire == true)
+    if (iToDelIndex < 0)
     {
-        //free pArg content
+        // overall removal x(:,...,:) = []
+        int piDims[2] = {0,0};
+        pOut = createEmpty(2, piDims, false);
         cleanIndexesArguments(_pArgs, &pArg);
-        return NULL;
+        return pOut;
     }
 
-    //find index to keep
-    int iNotEntireSize = pArg[iNotEntire]->getAs<GenericType>()->getSize();
-    double* piNotEntireIndex = getDoubleArrayFromDouble(pArg[iNotEntire]);
-    int iKeepSize = getVarMaxDim(iNotEntire, iDims);
-    bool* pbKeep = new bool[iKeepSize];
-
-    //fill pbKeep with true value
-    for (int i = 0; i < iKeepSize; i++)
+    if (toDelIndexVect.size() == 0)
     {
-        pbKeep[i] = true;
+        // no removal because of too large indexes
+        cleanIndexesArguments(_pArgs, &pArg);
+        return this;
     }
 
-    for (int i = 0; i < iNotEntireSize; i++)
-    {
-        int idx = (int)piNotEntireIndex[i] - 1;
-
-        //don't care of value out of bounds
-        if (idx < iKeepSize)
-        {
-            pbKeep[idx] = false;
-        }
-    }
-
-    int iNewDimSize = 0;
-    for (int i = 0; i < iKeepSize; i++)
-    {
-        if (pbKeep[i] == true)
-        {
-            iNewDimSize++;
-        }
-    }
-    delete[] pbKeep;
+    int iNewDimSize = getVarMaxDim(iToDelIndex, iDims) - toDelIndexVect.size();
 
     int* piNewDims = new int[iDims];
     for (int i = 0; i < iDims; i++)
     {
-        if (i == iNotEntire)
-        {
-            piNewDims[i] = iNewDimSize;
-        }
-        else
-        {
-            piNewDims[i] = getVarMaxDim(i, iDims);
-        }
+        piNewDims[i] = getVarMaxDim(i, iDims);
     }
+    piNewDims[iToDelIndex] = iNewDimSize;
 
     //remove last dimension if are == 1
     int iOrigDims = iDims;
@@ -987,14 +946,6 @@ GenericType* ArrayOf<T>::remove(typed_list* _pArgs)
         }
     }
 
-    if (iNewDimSize == 0)
-    {
-        //free pArg content
-        cleanIndexesArguments(_pArgs, &pArg);
-        delete[] piNewDims;
-        return createEmpty();
-    }
-
     if (iDims == 1)
     {
         //two cases, depends of original matrix/vector
@@ -1002,96 +953,77 @@ GenericType* ArrayOf<T>::remove(typed_list* _pArgs)
         {
             //special case for row vector
             int piRealDim[2] = {1, iNewDimSize};
-            pOut = createEmpty(2, piRealDim, m_pImgData != NULL);
             //in this case we have to care of 2nd dimension
-            //iNotEntire = 1;
+            //iToDelIndex = 1;
+            pOut = createEmpty(2, piRealDim, m_pImgData != NULL);
         }
         else
         {
             int piRealDim[2] = {iNewDimSize, 1};
             pOut = createEmpty(2, piRealDim, m_pImgData != NULL);
         }
-
-        {
-            int iNewPos = 0;
-            int size = getSize();
-
-            //try to sort piNotEntireIndex
-            std::sort(piNotEntireIndex, piNotEntireIndex + iNotEntireSize);
-
-            int last = 0;
-            for (int i = 0; i < iNotEntireSize; ++i)
-            {
-                int ii = piNotEntireIndex[i] - 1;
-                for (int j = last; j < ii; ++j)
-                {
-                    pOut->set(iNewPos, get(j));
-                    if (m_pImgData != NULL)
-                    {
-                        pOut->setImg(iNewPos, getImg(j));
-                    }
-                    iNewPos++;
-                }
-
-                last = ii + 1;
-            }
-
-            for (int i = last; i < size; ++i)
-            {
-                pOut->set(iNewPos, get(i));
-                if (m_pImgData != NULL)
-                {
-                    pOut->setImg(iNewPos, getImg(i));
-                }
-                iNewPos++;
-            }
-        }
     }
     else
     {
         pOut = createEmpty(iDims, piNewDims, m_pImgData != NULL);
+    }
 
-        //find a way to copy existing data to new variable ...
-        int iNewPos = 0;
-        int* piIndexes = new int[iOrigDims];
-        int* piViewDims = new int[iOrigDims];
-        for (int i = 0; i < iOrigDims; i++)
-        {
-            piViewDims[i] = getVarMaxDim(i, iOrigDims);
-        }
+    // find a way to copy existing data to new variable ...
+    int* piViewDims = new int[iOrigDims];
+    int* piOffset = new int[iOrigDims+1];
 
-        for (int i = 0; i < getSize(); i++)
-        {
-            bool bByPass = false;
-            getIndexesWithDims(i, piIndexes, piViewDims, iOrigDims);
+    // offsets
+    piOffset[0] = 1;
+    for (int i = 0; i < iOrigDims; i++)
+    {
+        piViewDims[i] = getVarMaxDim(i, iOrigDims);
+        piOffset[i+1] = piViewDims[i]*piOffset[i];
+    }
 
-            //check if piIndexes use removed indexes
-            for (int j = 0; j < iNotEntireSize; j++)
+    // indexes to remove -> [ 0, toDelIndexVect, piViewDims[iToDelIndex]+1 ] to facilitate loop
+    toDelIndexVect.insert(toDelIndexVect.begin(),0);
+    toDelIndexVect.push_back(piViewDims[iToDelIndex]+1);
+
+    int iStart;
+    int iSize;
+    int iOffset1 = piOffset[iToDelIndex];
+    int iOffset2 = piOffset[iToDelIndex+1];
+    int iNbChunks = getSize()/iOffset2;
+
+    // fast algorithm (allowing in place removal if necessary)
+    for (int k = 0, iDest = 0; k < iNbChunks; k++)
+    {
+        iStart = k*iOffset2;
+        // loop on indexes to remove
+        for (int j = 0; j < toDelIndexVect.size()-1; j++)
+        {
+            iSize =  (toDelIndexVect[j+1]-toDelIndexVect[j]-1)*iOffset1;
+            if (isNativeType())
             {
-                if ((piNotEntireIndex[j] - 1) == piIndexes[iNotEntire])
+                memcpy(pOut->m_pRealData + iDest, m_pRealData + iStart, iSize*sizeof(T));
+                if (m_pImgData != NULL)
                 {
-                    //by pass this value
-                    bByPass = true;
-                    break;
+                    memcpy(pOut->m_pImgData + iDest, m_pImgData + iStart, iSize*sizeof(T));
                 }
+                iDest += iSize;
             }
-
-            if (bByPass == false)
+            else
             {
-                //compute new index
-                pOut->set(iNewPos, get(i));
-                if (m_pImgData != NULL)
+                for (int i = iStart; i < iStart+iSize; i++, iDest++)
                 {
-                    pOut->setImg(iNewPos, getImg(i));
+                    pOut->set(iDest, get(i));
+                    if (m_pImgData != NULL)
+                    {
+                        pOut->setImg(iDest, getImg(i));
+                    }
                 }
-                iNewPos++;
             }
+            iStart += iSize + iOffset1;
         }
-
-        delete[] piIndexes;
-        delete[] piViewDims;
     }
 
+    delete[] piViewDims;
+    delete[] piOffset;
     delete[] piNewDims;
 
     //free pArg content
diff --git a/scilab/modules/ast/tests/nonreg_tests/bug_15087.tst b/scilab/modules/ast/tests/nonreg_tests/bug_15087.tst
new file mode 100644 (file)
index 0000000..fb7240f
--- /dev/null
@@ -0,0 +1,29 @@
+// =============================================================================
+// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+// Copyright (C) 2019 - St├ęphane MOTTELET
+//
+//  This file is distributed under the same license as the Scilab package.
+// =============================================================================
+//
+// <-- CLI SHELL MODE -->
+// <-- NO CHECK REF -->
+//
+// <-- Non-regression test for bug 15087 -->
+//
+// <-- Bugzilla URL -->
+// http://bugzilla.scilab.org/15087
+//
+// <-- Short Description -->
+// Deleting rows or columns from a matrix is slow
+
+X = rand(1e5,5);
+tic();
+X(:,3)=[];
+T1 = toc();
+
+tic();
+X(:)=[];
+T2 = toc();
+
+assert_checkalmostequal(T1, T2, 1E-4, 1E-3);
+