# Addition: stack vector

**URL:** <https://discourse.vtk.org/t/addition-stack-vector/5168>\
**Category:** Development\
**Created:** [February 10, 2021, 3:59pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168 "2021-02-10T15:59:44Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Thomas\_Caissard](https://discourse.vtk.org/user_avatar/discourse.vtk.org/thomas_caissard/32/2636_2.png) [@Thomas\_Caissard](https://discourse.vtk.org/u/Thomas_Caissard)\
**Post date:** [February 10, 2021, 3:59pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168/1 "2021-02-10T15:59:44Z")

</div>

There are some places in VTK that could be improved using an array-like data structure: it would lie on the stack if its size is less than a compile-time knows size (typically twice the cache line size) otherwise lie on the heap and use the typical new/delete idom. Up to my knowledge, there is no internal structure that does this in VTK.

Following this [conversation](https://gitlab.kitware.com/vtk/vtk/-/merge_requests/7600#note_901001), I would like to add to VTK core such a data structure. You can find a first implementation [here](https://gitlab.kitware.com/vtk/vtk/-/merge_requests/7600/diffs#78966d1601c91a6b600f298be6f9f8f99cfb103b), currently named `vtkStackVector`. Although the current implementation provides methods such as `reserve`, `resize` and `shrink_to_fit` but also a copy constructor and a assignement operator, it should only be used as a one time scoped allocated vector. A typical usage is to replace a scoped array allocation followed by a deletion within a function.

Pros for this structure are:

- its lightweight and easily droppable as the mr shows
- avoid unecessary heap allocation, espacially for local scoped arrays
- portable as it currently compiles on most compilers

Speed improvements have already been shown in this [MR](https://gitlab.kitware.com/vtk/vtk/-/merge_requests/7349).

I’d like to emphasize on the fact that this is not a replacement for the `std::vector`: it’s not meant to be used as a dynamic vector, where it would performs poorly. It would also be bad, for performance reasons, to follow the usual vtkNew idiom, as the purpose of this new data structure is to avoid unecessary heap allocations.

I’m open to suggestions and feedback such as naming conventions, but also portability!

---

<div class="post-metadata">

**Author:** ![utkarshayachit](https://discourse.vtk.org/user_avatar/discourse.vtk.org/utkarshayachit/32/379_2.png) [@utkarshayachit](https://discourse.vtk.org/u/utkarshayachit)\
**Post date:** [February 10, 2021, 4:10pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168/2 "2021-02-10T16:10:01Z")

</div>

I am not sure we need a new construct that’s not a C++ standard for several reasons:

- allocations should generally be not done inside performance-critical loops anyways.
- is there any dramatic performance benefit to using `vtkStackVector` instead of a combination of `std::array`, `std::vector` and out-of-loop allocations in the `vtkEnSightGoldBinaryReader`? It’s a reader. I’d suspect the reading from disk will be the slower part anyways.
- since it’s not something C++ developers are expecting to exist, I am not sure how many developers will actually use this in their code instead of the standard options.

Whenever possible, we need to start moving away from creating VTK-ism and using standard C++.

---

<div class="post-metadata">

**Author:** ![ben.boeckel](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/b/ea5d25/32.png) [@ben.boeckel](https://discourse.vtk.org/u/ben.boeckel)\
**Post date:** [February 10, 2021, 4:33pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168/3 "2021-02-10T16:33:02Z")

</div>

> [@utkarshayachit](#):
>
> Whenever possible, we need to start moving away from creating VTK-ism and using standard C++.

I agree with this. I’ve done a review of the code as well and there are some open questions that I have related to some bits.

I think just using `std::array` should be considered here rather than adding new API.

---

<div class="post-metadata">

**Author:** ![olesenm](https://discourse.vtk.org/user_avatar/discourse.vtk.org/olesenm/32/10443_2.png) [@olesenm](https://discourse.vtk.org/u/olesenm)\
**Post date:** [February 10, 2021, 4:36pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168/4 "2021-02-10T16:36:00Z")

</div>

@utkarshayachit  
Can probably move smallish items out of loops. Makes the code slightly uglier, but doable.  
If we want everything _standard_, I think we can also have a local wrapper for `std::vector`.  
For example,

```auto
std::vector<int> someCache;
someCache.reserve(bigNum);  

...
someCache.resize(n);  

```

This makes the item dynamically resizable without multiple heap allocs each time.

@ben.boeckel - using `std::array` is non-starter. The sizes can be changing in various places. Not a fixed size.

---

<div class="post-metadata">

**Author:** ![Thomas\_Caissard](https://discourse.vtk.org/user_avatar/discourse.vtk.org/thomas_caissard/32/2636_2.png) [@Thomas\_Caissard](https://discourse.vtk.org/u/Thomas_Caissard)\
**Post date:** [February 10, 2021, 4:46pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168/5 "2021-02-10T16:46:27Z")

</div>

If you only wanna go with `std::array` and `std::vector`, you could just do as I’ve done in my implementation and trick the compiler by using a pointer to either the beginning of the array or the beginning of the vector. Doing that would be better than what’s done in the reader (and in various places throughout VTK), but worse than the proposed data structure as you have the overhead of `std::vector` which implements a dynamically re-sizable array (you would potentially allocate much more than what’s needed).

If non-standard is the way then I could either:

- keep the data structure within the reader cxx (which would not make it available for future performance improvements to other part of VTK)
- use a mix of `std::vector` and `std::array`.

---

<div class="post-metadata">

**Author:** ![dgobbi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/dgobbi/32/18_2.png) [@dgobbi](https://discourse.vtk.org/u/dgobbi)\
**Post date:** [February 10, 2021, 6:31pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168/6 "2021-02-10T18:31:16Z")

</div>

For the EnSight reader, it really looks like it would be sufficient to use a `std::vector` that is constructed outside of the loop and then resized as necessary within the loop. That would reduce the number of allocations from O(n) to O(1), or at worst O(log(n)), since the vector would quickly grow to the necessary size.

One problem with using a `vtkStackVector` here is that it doesn’t move the allocation out of the loop if the allocation size is more than the reserved stack size. In other words, the worst-case behavior is just as bad as before.

---

<div class="post-metadata">

**Author:** ![Thomas\_Caissard](https://discourse.vtk.org/user_avatar/discourse.vtk.org/thomas_caissard/32/2636_2.png) [@Thomas\_Caissard](https://discourse.vtk.org/u/Thomas_Caissard)\
**Post date:** [February 10, 2021, 6:50pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168/7 "2021-02-10T18:50:54Z")

</div>

I tried to use `std::vector`, but for the data set I have we need to have the memory tight (simply switching to `std::vector` allocates 8gb more than the implemented method which already allocates ~30gb).

I think the best thing to do right now is benchmarking. I will come up with data and memory usage for both methods.

---

<div class="post-metadata">

**Author:** ![dgobbi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/dgobbi/32/18_2.png) [@dgobbi](https://discourse.vtk.org/u/dgobbi)\
**Post date:** [February 10, 2021, 8:18pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168/8 "2021-02-10T20:18:46Z")

</div>

Regarding memory use, the problem with `vtkEnsightGoldBinaryReader` is that it uses temporary arrays rather than simply reading the data directly into the VTK data structures, which would be much more efficient.

Current code:

```auto
  xCoords = new float[numPts];
  yCoords = new float[numPts];
  zCoords = new float[numPts];
  this->ReadFloatArray(xCoords, numPts);
  this->ReadFloatArray(yCoords, numPts);
  this->ReadFloatArray(zCoords, numPts);

  for (i = 0; i < numPts; i++)
  {
    points->InsertNextPoint(xCoords[i], yCoords[i], zCoords[i]);
  }

```

Since `vtkPoints` is just a wrapper around a VTK data array (a `vtkFloatArray` by default), the `ReadFloatArray()` method should be reading directly into `vtkPoints`. All that `ReadFloatArray()` would need is an additional argument for the stride to use for its output buffer. Then `x` could be written to every third element starting at 0, ‘y’ could be written to every third element starting at 1, ‘z’ to every third element starting at 2.

* * *

Edit: instead of saying "`ReadFloatArray()` should be reading directly into `vtkPoints`“, it would be clearer to say "`ReadFloatArray()` should be reading directly into the `vtkFloatArray` that `vtkPoints` uses to store the points.”

---

<div class="post-metadata">

**Author:** ![will.schroeder](https://discourse.vtk.org/user_avatar/discourse.vtk.org/will.schroeder/32/233_2.png) [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)\
**Post date:** [February 11, 2021, 12:20pm UTC](https://discourse.vtk.org/t/addition-stack-vector/5168/10 "2021-02-11T12:20:30Z")

</div>

As a point of reference, a lot of work has gone into supporting AOS (array of structures) and SOA (structure of arrays) vtkDataArrays. See for example: [https://blog.kitware.com/new-data-array-layouts-in-vtk-7-1/](https://blog.kitware.com/new-data-array-layouts-in-vtk-7-1/) and [https://blog.kitware.com/working-with-vtkdataarrays-2019-edition/](https://blog.kitware.com/working-with-vtkdataarrays-2019-edition/).