From 094287b4dfbd30d6b17cb9d6cb892e62388c2170 Mon Sep 17 00:00:00 2001
From: rnc <rnc@opencascade.com>
Date: Mon, 22 Jul 2013 08:46:57 +0000
Subject: [PATCH] BUG: EDF 2655: Hexa splitting into tetra low performance

A better fix has been found by improving the getNextFree() method in ObjectPool.hxx. When there is no "hole" in the ID list we don't iterate on the _freeList to find the next free ID. We jump straight to the last occupied ID.
This fix is simpler and can benefit to other methods of SMESH_Editor like QuadTo4Tri for example.
---
 src/SMDS/ObjectPool.hxx        | 21 ++++++++++++++++++
 src/SMESH/SMESH_MeshEditor.cxx | 39 +---------------------------------
 2 files changed, 22 insertions(+), 38 deletions(-)

diff --git a/src/SMDS/ObjectPool.hxx b/src/SMDS/ObjectPool.hxx
index abb7c15f2..e664c260c 100644
--- a/src/SMDS/ObjectPool.hxx
+++ b/src/SMDS/ObjectPool.hxx
@@ -42,9 +42,16 @@ private:
   int _nextFree;
   int _maxAvail;
   int _chunkSize;
+  int _maxOccupied;
+  int _nbHoles;
 
   int getNextFree()
   {
+    // Don't iterate on the _freeList if all the "holes"
+    // are filled. Go straight to the last occupied ID + 1
+    if ( _nbHoles == 0 )
+      return std::min(_maxOccupied + 1, _maxAvail);
+    
     for (int i = _nextFree; i < _maxAvail; i++)
       if (_freeList[i] == true)
         {
@@ -73,6 +80,8 @@ public:
     _chunkSize = nblk;
     _nextFree = 0;
     _maxAvail = 0;
+    _maxOccupied = 0;
+    _nbHoles = 0;
     _chunkList.clear();
     _freeList.clear();
   }
@@ -103,6 +112,14 @@ public:
         _freeList[_nextFree] = false;
         obj = _chunkList[chunkId] + rank; // &_chunkList[chunkId][rank];
       }
+    if (_nextFree < _maxOccupied)
+      {
+        _nbHoles-=1;
+      }
+    else
+      {
+        _maxOccupied = _nextFree;
+      }
     //obj->init();
     return obj;
   }
@@ -124,6 +141,8 @@ public:
         _freeList[toFree] = true;
         if (toFree < _nextFree)
           _nextFree = toFree;
+        if (toFree < _maxOccupied)
+          _nbHoles += 1;
         //obj->clean();
         //checkDelete(i); compactage non fait
         break;
@@ -134,6 +153,8 @@ public:
   {
     _nextFree = 0;
     _maxAvail = 0;
+    _maxOccupied = 0;
+    _nbHoles = 0;
     for (size_t i = 0; i < _chunkList.size(); i++)
       delete[] _chunkList[i];
     clearVector( _chunkList );
diff --git a/src/SMESH/SMESH_MeshEditor.cxx b/src/SMESH/SMESH_MeshEditor.cxx
index 1d5698d24..49d3e14c7 100644
--- a/src/SMESH/SMESH_MeshEditor.cxx
+++ b/src/SMESH/SMESH_MeshEditor.cxx
@@ -1899,20 +1899,6 @@ namespace
   };
 } // namespace
 
-class TElemToDelete
-{
-public:
-  TElemToDelete(const SMDS_MeshElement* theElem, SMESHDS_SubMesh* theSubMesh)
-  {
-    elem = theElem;
-    subMesh = theSubMesh;
-  }
-  const SMDS_MeshElement* Elem() const {return elem;}
-  SMESHDS_SubMesh* Submesh() {return subMesh;}
-  const SMDS_MeshElement* elem;
-  SMESHDS_SubMesh* subMesh;
-};
-
 //=======================================================================
 //function : SplitVolumesIntoTetra
 //purpose  : Split volume elements into tetrahedra.
@@ -1938,7 +1924,6 @@ void SMESH_MeshEditor::SplitVolumesIntoTetra (const TIDSortedElemSet & theElems,
   double bc[3];
 
   TIDSortedElemSet::const_iterator elem = theElems.begin();
-  std::vector<TElemToDelete> elem_to_delete;
   for ( ; elem != theElems.end(); ++elem )
   {
     if ( (*elem)->GetType() != SMDSAbs_Volume )
@@ -2102,26 +2087,11 @@ void SMESH_MeshEditor::SplitVolumesIntoTetra (const TIDSortedElemSet & theElems,
         }
         ReplaceElemInGroups( face, triangles, GetMeshDS() );
         GetMeshDS()->RemoveFreeElement( face, fSubMesh, /*fromGroups=*/false );
-//         TElemToDelete faceToDelete(face, fSubMesh);
-//         elem_to_delete.push_back(faceToDelete); 
       }
 
     } // loop on volume faces to split them into triangles
 
-//     GetMeshDS()->RemoveFreeElement( *elem, subMesh, /*fromGroups=*/false );
-
-    // rnc : don't delete the elem here because it results in a mesh with a free
-    // ID at the beginning of the ID list. The first tetra is then inserted in O(1)
-    // but the second one is inserted in O(n), then the whole procedure has almost a O(n^2)
-    // complexity. If all elements to remove are stored and removed after tetra creation 
-    // we get a O(n) complexity for the whole procedure. 
-    // The memory cost is at worst a 6*n*constant memory occupation (where n is the number of elements) 
-    // before deletion of the hexas and then 5*n*constant instead of a maximum of 5*n*constant.
-    // So there is a transient 1/5*(memory occupation) additional cost.
-
-    // Store the elements to delete
-    TElemToDelete elemToDelete(*elem, subMesh);
-    elem_to_delete.push_back(elemToDelete);
+    GetMeshDS()->RemoveFreeElement( *elem, subMesh, /*fromGroups=*/false );
 
     if ( geomType == SMDSEntity_TriQuad_Hexa )
     {
@@ -2131,13 +2101,6 @@ void SMESH_MeshEditor::SplitVolumesIntoTetra (const TIDSortedElemSet & theElems,
           GetMeshDS()->RemoveNode( volNodes[i] );
     }
   } // loop on volumes to split
-
-  // Delete stored elements
-  std::vector<TElemToDelete>::iterator it;
-  for( it = elem_to_delete.begin(); it!= elem_to_delete.end(); it++)
-  {
-    GetMeshDS()->RemoveFreeElement( it->Elem(), it->Submesh(), /*fromGroups=*/false );
-  }
   
   myLastCreatedNodes = newNodes;
   myLastCreatedElems = newElems;
-- 
2.39.2