# vtkDataCache: caching data to avoid duplicate computation

**URL:** https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871
**Category:** Development
**Tags:** proposal
**Created:** [August 26, 2021, 12:27pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871 "2021-08-26T12:27:26Z")
**Posts on this page:** 9
**Page:** 1

<div class="post-metadata">

### Author: ![utkarsh.ayachit](https://discourse.paraview.org/user_avatar/discourse.paraview.org/utkarsh.ayachit/32/39_2.png) [@utkarsh.ayachit](https://discourse.paraview.org/u/utkarsh.ayachit)
#### Post date: [August 26, 2021, 12:27pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871/1 "2021-08-26T12:27:26Z")

</div>

Consider this simple pipeline: **reader → calculator**. As the user is constructing this pipeline the geometry filter – which is automatically executed to generate polygons for rendering – executes twice on the same geometry + topology: first time when user hits `Apply` for the reader, and the another time when user hits `Apply` for the calculator. Both times, the geometry filter generates exactly the same surfaces since the mesh is unchanged, only the fields are changing.

This is just a simple illustration, but we can easily keep on making changes to this pipeline to come up with scenarios where filters keep doing the computation they already did over and over again.

A question that @Will_Schroeder and I have been brainstorming on and off over several months has been how can we avoid this. Ideally, without making any cumbersome changes to the VTK pipeline or adding memory costs. Will started a discussion in a similar spirit [here](https://discourse.vtk.org/t/data-caching/4290), however, it didn’t really go anywhere conclusive.

Here’s a more detailed proposal. I pose it as more of ParaView concern here, however, it’s broadly applicable to VTK use-cases too.

Let’s add a new global cache, let’s say `vtkDataCache`.

```cpp
class vtkDataCache : ... 
{
public:
   // this has to be a singleton to ensure cached data can
   // be shared between different instances of algorithms with
   // ease.
   static vtkDataCache* GetInstance();

   // API to access a cached item.
   template <typename T, typename ...KeyT>
   T* GetCachedData(ArgsT... key);

   // API to add an item to the cache.
   template <typename T, typename ...KeyT>
   void AddToCache(T* data, vtkObject* context, KeyT... key);
};

```

Let’s consider an example: a modified version of `vtkDataSetSurfaceFilter` to extract exterior surface from a vtkStructuredGrid – something the geometry filter in our illustrative example employs. The algorithm executes over cells and generates an `originalCellIds` array to identify cells in the input dataset that are part of the exterior shell. For simplicity, let’s just focus on this step. The algorithm can easily be changed to avoid re-computation as follows:

```cpp
vtkDataSetSurfaceFilter* self = ...

vtkStructuredGrid* sg = ... // input structured grid
auto points = sg->GetPoints();
auto ghostCells = sg->GetCellData()->GetArray(
    vtkDataSetAttributes::GhostArrayName());

auto cache = vtkDataCache::GetInstance();
auto originalCellIds = vtk::MakeSmartPointer(
    cache->GetCachedData<vtkIdTypeArray>(
       "vtkDSF::OriginalCellIds", points, ghostCells));
if (originalCellIds == nullptr)
{
    // iterate over cells and compute new original cell ids array
   cache->AddToCache(originalCellIds, /*context=*/ self,
      /* key .... */
     "vtkDSF::OriginalCellIds", points, ghostCells));
}

```

Let’s see how this works:

**Avoid re-computation** : this is fairly obvious. The **key** for the cache is built using input points which would indeed change if the input structured grid was changed in any way that would impact the result. Here, that is the input points and ghost cells arrays. If we had already computed the originalIds arrays for the chosen points and ghost cells, we won’t recompute it. And when we have to recompute, we update the cache.

**Avoid memory overhead** : this is a tricky one. To understand this, we’ll have to dive into the implementation of `vtkDataCache`. `vtkDataCache` stores vtkObject’s. Hence it can manage reference count for the stored object to release it for garbage collection or keep it around.  
When something is added to the cache, besides the object being cached, the arguments to `AddToCache` take in a set of arguments which comprise the `key` followed by an optional `vtkObject*` that we call the context. The key can comprise of `vtkObject*`s and `std::string`s (any copyable, comparable type can be supported here, but for now let’s just use strings for simplicity). The cache adds `ModifiedEvent` and `DeleteEvent` observers to all `vtkObject`s in key and context arguments. If any of those are fired, the cache simply release the reference to the cached `vtkObject`, thus releasing it. That is it! This simple trick minimizes memory overhead. With `key`, we are assured that it any item that affects the cached result changes, the cache will be flushed. With `context`, we are assured that if the filter itself changes we don’t need to keep around cached data for it. The `context` could easily be part of the `key`, however, keeping it separate enables multiple instances of `vtkDataSetSurfaceFilter` share the cache while still ensuring that if the filters go away, the cache is flushed.

The beauty of this approach is we no longer need to invest in any changes to the VTK pipeline or filters to deal with [static meshes](https://gitlab.kitware.com/paraview/staticmeshplugin). Computation results are now keyed only on input arrays that affect the result and hence will not be recomputed unless necessary.

The cache can be used to store things like array ranges too. Currently, computing array ranges does not take into account masks or ghost arrays. We can easily start supporting that and use cache to avoid recomputing ranges.

The cache can be used by readers too to avoid re-reading data from disk when iterating through time or if array selection, for example, changes etc.

The cache also works for caching this things like point/cell locators without requiring any changes to dataset API. Thus, no need to start storing point-locators with `vtkPoints` to avoid rebuilding them, the cache can help with that effortlessly!

It’s not limited a specific use-case either, as is the case with [`vtkOpenGLVertexBufferObjectCache`](https://gitlab.kitware.com/vtk/vtk/-/blob/master/Rendering/OpenGL2/vtkOpenGLVertexBufferObjectCache.h). The proposed cache can not only store `vtkOpenGLVertexBufferObject`, but also things like ranges, locators, you name it. Also, `vtkDataCache` does not require any explicit `Remove` calls. Using modification and delete events fired from key and context objects, it can automatically remove obsolete entries.

Thoughts? Suggestions? Critiques?

---

<div class="post-metadata">

### Author: ![mwestphal](https://discourse.paraview.org/user_avatar/discourse.paraview.org/mwestphal/32/17_2.png) [@mwestphal](https://discourse.paraview.org/u/mwestphal)
#### Post date: [August 26, 2021, 3:52pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871/2 "2021-08-26T15:52:06Z")

</div>

I would be very happy to see this implemented 🙂

---

<div class="post-metadata">

### Author: ![dcthomp](https://discourse.paraview.org/user_avatar/discourse.paraview.org/dcthomp/32/20_2.png) [@dcthomp](https://discourse.paraview.org/u/dcthomp)
#### Post date: [August 26, 2021, 5:02pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871/3 "2021-08-26T17:02:40Z")

</div>

There will probably be some issues with thread access to the cache, especially as vtkSMPTools becomes more prevalent. You might either

- lock access to the cache with a mutex or
- make the static `instance()` method return a `thread_local` instance and provide some reduce operation for caches across threads.

---

<div class="post-metadata">

### Author: ![berkgeveci](https://discourse.paraview.org/user_avatar/discourse.paraview.org/berkgeveci/32/1464_2.png) [@berkgeveci](https://discourse.paraview.org/u/berkgeveci)
#### Post date: [August 26, 2021, 5:05pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871/4 "2021-08-26T17:05:48Z")

</div>

This is fantastic! I second Dave’s comment about threaded access. Probably a mutex around modification and access…

---

<div class="post-metadata">

### Author: ![utkarsh.ayachit](https://discourse.paraview.org/user_avatar/discourse.paraview.org/utkarsh.ayachit/32/39_2.png) [@utkarsh.ayachit](https://discourse.paraview.org/u/utkarsh.ayachit)
#### Post date: [August 26, 2021, 5:33pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871/5 "2021-08-26T17:33:23Z")

</div>

Indeed; ensuring the API on `vtkDataCache` is thread-safe will be important. And also documenting so developers are aware of potential `mutex`. That may encourage them to move the cache access outside the threaded loop, which would be the best approach, performance-wise, anyways.

---

<div class="post-metadata">

### Author: ![Will\_Schroeder](https://discourse.paraview.org/user_avatar/discourse.paraview.org/will_schroeder/32/7258_2.png) [@Will\_Schroeder](https://discourse.paraview.org/u/Will_Schroeder)
#### Post date: [August 27, 2021, 12:03pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871/6 "2021-08-27T12:03:57Z")

</div>

Nice work Utkarsh!!!

It seems to use this effectively we need to modify many filters / classes to make them cache aware and take advantage of this capability. I’d like to do this in an organized way so we don’t end up with another feature in VTK that is partially implemented. Locators are very high on my list to address. It would be good to work through one use case to fully understand what the implications are…

---

<div class="post-metadata">

### Author: ![MicK7](https://discourse.paraview.org/user_avatar/discourse.paraview.org/mick7/32/1374_2.png) [@MicK7](https://discourse.paraview.org/u/MicK7)
#### Post date: [August 27, 2021, 12:20pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871/7 "2021-08-27T12:20:18Z")

</div>

This would be a nice feature to have. I was just wondering if a cache size limit would be necessary. In this case a cache policy should be defined : LRU, FIFO, LFU …(as a property of the class or as a template parameter) in order to remove data when the size limit is exceeded.

---

<div class="post-metadata">

### Author: ![utkarsh.ayachit](https://discourse.paraview.org/user_avatar/discourse.paraview.org/utkarsh.ayachit/32/39_2.png) [@utkarsh.ayachit](https://discourse.paraview.org/u/utkarsh.ayachit)
#### Post date: [August 27, 2021, 12:31pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871/8 "2021-08-27T12:31:02Z")

</div>

> [@Will\_Schroeder](#):
>
> I’d like to do this in an organized way so we don’t end up with another feature in VTK that is partially implemented.

I’ve started putting together an implementation of the `vtkDataCache`, so far seems promising. I was worried I was getting too lofty with the variadic arguments but seems like it’s workable. I’m also building a test that will test the guarantees made by the cache. Next, I am hoping to modify the geometry filters esp. the ones used in ParaView. That’d be a good place to test the impact of this. We can coordinate how to expand that to locator uses etc.

> [@MicK7](#):
>
> I was just wondering if a cache size limit would be necessary.

Perhaps. Originally, I was toying with the idea that the cache itself will only store weak-pointers. In the case I described, if the geometry filter put out the original ids array it generated as an array in the output dataset, the ids arrays will be held on to by something else and hence the cache will only be making it accessible rather than actually caching it. This falls apart if people use the cache to store intermediate results that are not added the output data object, or for things like locators, ranges etc. Something to ponder for sure.

---

<div class="post-metadata">

### Author: ![utkarsh.ayachit](https://discourse.paraview.org/user_avatar/discourse.paraview.org/utkarsh.ayachit/32/39_2.png) [@utkarsh.ayachit](https://discourse.paraview.org/u/utkarsh.ayachit)
#### Post date: [August 27, 2021, 2:49pm UTC](https://discourse.paraview.org/t/vtkdatacache-caching-data-to-avoid-duplicate-computation/7871/9 "2021-08-27T14:49:23Z")

</div>

Here’s a quick implementation: [!8347](https://gitlab.kitware.com/vtk/vtk/-/merge_requests/8347).