GetPointer vs ValueRange for typed data arrays

Development
1

I’m using vtkIdTypeArray to implement a half-edge data structure for 2D meshes. Once the faces are prepared, the connectivity and offsets array will be sent to vtkCellArray with (vtkCellArray::SetData(vtkIdTypeArray*, vtkIdTypeArray*)).

I’m stuck b/w certain syntactic/API choices. It would help to get an expert opinion before I choose one over the other.

Internally, the struct uses API of said data arrays. But, I want to access member data-arrays through traditional operator[]. Now, I have two options: 1. Ranges, 2. GetPointer().

Also right after any Resize/InsertTypedComponent these proxy-like accessors are invalid, so I’ve to revalidate them.

Ex: Build 2-D meshes with half-edge data-structure and fill a vtkCellArray

struct HalfEdgeMesh
{
  HalfEdgeMesh() 
    : m_Conn(vtkIdTypeArray::New())
    , m_Offsts(vtkIdTypeArray::New())
    , m_HalfEdges(vtkIdTypeArray::New())
  {}

   // vtkCellArray will assume ownership, so no need to invoke GC rn.
  ~HalfEdgeMesh() {m_Conn->FastDelete(); m_Offsts->FastDelete(); ...}

  // to simplify access, provide public pointers.
  vtkIdType* polys
  vtkIdType* offsets
  vtkIdType* halfEdges
   
  void Allocate(vtkIdType maxPolys) {...}
  void Insert(vtkIdType* verts, vtkIdType* hedges) {...} 
  void FillUp(vtkCellArray* polys) { polys->SetData(m_Conn, m_Offsts); }
  void Link(vtkIdType hedge1, vtkIdType hedge2){...}
  void Size() {...}
 
private:
  vtkIdTypeArray* m_Conn;
  vtkIdTypeArray* m_Offsts;
  vtkIdTypeArray* m_HalfEdges;

protected:
  // must call this post-allocation or post-resize
  // in methods `Allocate`, `Insert` and `Link`
  void __revalidate_mem_accessors() {...}
};

Possible implementations of __revalidate_mem_accessors:

  1. This looks weird. Each line makes 4 assertions and is the one suggested by docs. :confused:
{
  polys = vtk::DataArrayValueRange<1>(m_Conn).begin();
  offsets = vtk::DataArrayValueRange<1>(m_Offsts).begin();
  halfEdges= vtk::DataArrayValueRange<1>(m_HalfEdges).begin();
}
  1. This is simple and readable. It has minimal overhead; zero assertions, zero range checks.
{
  polys = m_Conn->GetPointer(0);
  offsets = m_Offsts->GetPointer(0);
  halfEdges= m_HalfEdges->GetPointer(0);
}

Also, the functions Insert and Link are called in very tight loops that need to be performant. Which would be better? Is this a bad design?

I’m aware that exposing non-const public pointers is scary but I use this in a translation unit where I am the sole user of this struct.

Posting after a mini panic-attack when I found this in the documentation for GetPointer.

Get the address of a particular data index.
Performs no checks to verify that the memory has been allocated etc. Use of this method is
discouraged, as newer arrays require a deep-copy of the array data in order to return a suitable
pointer. See vtkArrayDispatch for a safer
alternative for fast data access.

Will that mean GetPointer will soon be deprecated in coming releases?
It would be great for typed data-arrays to retain this method.

Edit: code typos

2

tl;dr: Just storing the vtk::DataArrayValueRange<1>(array) object directly instead of the iterator (no begin()) will also provide operator[] access and is a bit cleaner. The range/iterator approaches provide additional runtime safety checks only in debugging builds. When building in release mode, identical assembly is emitted for the ranges and the pointer versions and performance is the same.

Now – since I love to get longwinded when talking about data models, a more detailed answer follows :smiley:

This is what I would use:

// Deduce range type
using RangeType = decltype(
  vtk::DataArrayValueRange<1>(std::declval<vtkIdTypeArray*>()));

// Declare variable
RangeType polys;

// Initialize
polys = vtk::DataArrayValueRange<1>(m_Conn);

This looks weird . Each line makes 4 assertions and is the one suggested by docs.

Weird is subjective I suppose :slight_smile: C++ has changed a lot over the years, and admittedly the newer syntaxes post-C++11 feel like a completely different language compared with the “C with classes” style from 1994, when most of the core VTK classes were originally written. It takes some adjustment.

The docs suggest this approach because the assertions are your friends – they catch bugs early and don’t affect performance unless you’re building in Debug mode, in which case testing and correctness are the goals of the build, not peak performance. You can also define VTK_DEBUG_RANGE_ITERATORS to get even more correctness checks to help track down trickier problems, again at the cost of performance. Alternatively, you can instead define VTK_ALWAYS_OPTIMIZE_ARRAY_ITERATORS to opt out of the checks and enable optimizations for the ranges/iterators in debug mode, which should help recover a significant amount of performance.

But performance is never impacted where it matters: using ranges and iterators in Release mode generally produces the exact same assembly as using a raw pointer. Towards the end of this blog post I summarized a series of benchmarks on the tight loop iteration performance of ranges vs raw pointers. If you’re using a typed vtkIdTypeArray to create the ranges, the relevant results will be the 3rd and 4th bar charts in that post comparing the vtkAOSDataArrayTemplate results. There’s virtually no difference between the Pointer vs the Range/Iterator benchmarks, all are within noise. Whether you write:

  const ValueType *data = array->GetPointer(0);
  ValueType sum{0};
  for (vtk::ValueIdType v = 0; v < numValues; ++v)
  {
    sum += *data++;
  }

or

  const auto range = vtk::DataArrayValueRange<TupleSize>(array);
  APIType sum{0};
  for (const auto& value : range)
  {
    sum += value;
  }

will have no impact on performance in a release build, but the second version helps catch bugs in debugging builds.

The sources are here if you’re curious what the implementations of the other benchmarks look like.

the functions Insert and Link are called in very tight loops that need to be performant. Which would be better? Is this a bad design?

I wouldn’t say it’s a bad design, but calling either of those in a loop is going to be bad for performance. Both allocate memory, and those allocations are expensive. The Insert method is especially troublesome – it’s branchy, and every call will execute a lot of extra instructions to check whether the array needs reallocation. Not to mention the fact that its behavior is completely different and surprising compared to any other container’s insert methods :sweat_smile: Use it cautiously, and read the docs for that one carefully!

Ideally, you’ll want to pre-allocate memory whenever possible and keep allocations/invalidations to an absolute minimum. There are three scenarios, in order from best performance to worst:

  1. The exact final size of the array is known. Do a single allocation before the tight loop that exactly fits the data. Use Range APIs to make sure that your calculated size is correct and detect accesses beyond the predicted size when debugging.
  2. The exact size is unknown, but has a known upper bound. Same as above, but preallocate the upper bound and then Resize to the final size once it is known.
  3. Worst case: nothing is known about the final size of the array. Pre-allocate a reasonable guess at the final size with Allocate (which increases capacity without increasing the actual number of valid values) and then fill with InsertNextValue to make sure the array is grown as-needed. Finish up with Squeeze if you want to release any excess memory (this will also invalidate pointers/ranges, btw).

Will that mean GetPointer will soon be deprecated in coming releases?

No. Subclasses of vtkAOSDataArrayTemplate<T> (including vtkIdTypeArray) will always provide the typed GetPointer method. At one point I was pushing to deprecate GetVoidPointer in the generic levels of the array hierarchy, since that’s a real can of worms after the SOA-layout arrays were added. But I don’t think there’s been much interest in continuing that effort since I stopped working on VTK.

Also – unrelated, but as a heads up,

__revalidate_mem_accessors

Identifiers containing double underscores are reserved by compiler vendors. It’s best to avoid them.

1 Like
3

Hi, Thanks for your reply.

Sweet.

Yes!

Right, so much to ensure MaxId is appropriate. I dealt with worst-case scenarios by resizing the array beforehand followed by successive InsertTypedComponent. I found this to be better than naive calls to InsertTypedComponent. That’s the least I could do. :man_shrugging:

In worst-case it is bad. In my use, almost always, I have a rough estimate of the upper bound.

It’s the cases when the rough estimate is a poor one… Such scenarios will require Ranges to be revalidated. But I think I can get around that by querying MaxId and revalidate only if required.

Ah, ok. Thanks for pointing that out.

Good. You improved the data-access part of this library. Most of the stuff I do in VTK is impossible without your contributions. Thank you :sweat_smile:

1 Like