[vtk-developers] vtkFieldData::AddArray() is very painful with lots of arrays

Wilson, Andrew T atwilso at sandia.gov
Fri Nov 6 15:06:23 EST 2009


I have an application where I have about 90,000 state arrays that I need to
save (to disk) and restore on subsequent runs.  The arrays are all of
different lengths.   It seemed to make sense to put them in the field data
of a vtkDataObject and use vtkDataObjectReader/Writer.

It turns out that it takes a ridiculously long time (25 minutes) to load a
100MB file.  This is because vtkDataReader calls vtkFieldData::AddArray() as
it loads in each array (which seems proper).  However, AddArray() takes time
linear in the number of arrays already in the field data, so loading in a
field data takes O(n^2) time in the number of arrays being loaded.  When n =
90000 this is unpleasant.

I suppose that for the purposes of my application I can condense my 90000
arrays into one ginormous one and just save that.  Padding them out to the
same length isn't practical because some are very short and some are very,
very long.  Likewise, saving them in point data is problematic because every
array is a different length.

The problem remains that vtkFieldData::AddArray() is O(n^2).  This seems...
Unfashionable.  What could we do about it?  Replace the loop in
GetAbstractArray() with a hashtable lookup?  The worst-case complexity is
still O(n) for the lookup but the average case should be much better.

Other suggestions?  This is really vexing me.

-- Andy


PS.  Here are the relevant snippets of code:


//-----------------------------------------------------------------------
int vtkFieldData::AddArray(vtkAbstractArray *array)
{
[snip]
  this->GetAbstractArray(array->GetName(), index);
[snip]
  if (index == -1)
    {
    index = this->NumberOfActiveArrays;
    this->NumberOfActiveArrays++;
    }
  this->SetArray(index, array);
  return index;
}


//-------------------------------------------------------------------
vtkAbstractArray *vtkFieldData::GetAbstractArray(const char *arrayName, int
&index)
{
[snip]
  for (i=0; i < this->GetNumberOfArrays(); i++)
    {
    name = this->GetArrayName(i);
    if ( name && !strcmp(name,arrayName) )
      {
      index = i;
      return this->GetAbstractArray(i);
      }
    }
  return NULL;
}






More information about the vtk-developers mailing list