[vtk-developers] vtkCellArray memory layout

[Berk Geveci]

My reaction STL vector of vectors is "yuck". That would cause horrible
memory segmentation and allocation of it would be terribly inefficient when
using it in the high performance context, special across multiple threads.

Having said that, David is working on allowing arbitrary subclasses of an
abstract cell array which would allow for creating such an implementation
when it is the best fit. We definitely need a compact array implementation
for performance reasons though.

-berk


On Wed, Mar 20, 2013 at 7:15 PM, Bill Lorensen <bill.lorensen at gmail.com>wrote:

> But if the API is going to be broken, we discuss many alternatives. The
> cell array could be a vector of vectors. Then we could use stl iterators.
> What overhead in time or memory would this introduce?
>
> What would the overhead be if we use stl vector's?
>
>
> On Wed, Mar 20, 2013 at 4:12 PM, Bill Lorensen <bill.lorensen at gmail.com>wrote:
>
>>  A backward compatible approach might use an additional offset array into
>> the existing cell ids array.
>>
>> On Wed, Mar 20, 2013 at 2:22 PM, David Lonie <david.lonie at kitware.com>wrote:
>>
>>> Hi list,
>>>
>>> I have some questions about the vtkCellArray implementation, as well as
>>> some concerns about it after seeing some widespread abuses of its
>>> "internal" access methods.
>>>
>>> First, some background:
>>>
>>> The vtkCellArray currently stores cell information in the form
>>>
>>> [ cellSize1 id id ... cellSize2 id id ... cellSizeN id id ... ]
>>>
>>> where the cell sizes tell the number of points in each cell, and the ids
>>> are offsets into an array of points. So a real vtkCellArray may look
>>> something like:
>>>
>>> [(2) 0 1 (4) 3 2 0 4 (3) 1 3 5 (3) 3 5 7]
>>>
>>> where the numbers in parenthesis are the sizes of the cells.
>>>
>>> The docs do point out the current implementation is "totally inadequate"
>>> for random access, and I'm trying to understand what benefit it offers at
>>> the expense of random cell lookup? There is a vtkCellTypes class that will
>>> build up an offset array like the one I propose above, but this approach
>>> effectively doubles the amount of memory needed to store the cell sizes
>>> (per vtkCellTypes instance, which is often used by parent containers as
>>> well as filters), and time must be spent generating these supplemental
>>> structures each time the data changes.
>>>
>>> It seems to me that another implementation would be more useful. In
>>> particular, splitting the array into two, one with cell offsets and another
>>> with just point ids, transforming the above list into:
>>>
>>> [0 2 6 9 12] (offsets, last entry points to end of ids)
>>> [(0 1) (3 2 0 4) (1 3 5) (3 5 7)] (ids)
>>>
>>> The parentheses in ids just group cells for readability.
>>>
>>> This offers random access by cell id for free, and eliminates the
>>> time/memory spent building the supplemental vtkCellTypes objects. There is
>>> a slightly higher penalty for sequential access than before, due to having
>>> to iterate through two arrays, but I doubt that this would have serious
>>> performance impacts.
>>>
>>> I've also noticed that there are a number of "random access" methods
>>> like vtkCellArray::GetCell(vtkIdType loc, ...) that take an offset into the
>>> "mixed" internal array. This breaks encapsulation and is rather unintuitive
>>> -- I think it's safe to say that most developers would expect the "loc"
>>> argument to be a cell id. Since these methods depend on implementation
>>> details they are labeled as internal in the docs. However, they have public
>>> visibility and are used commonly throughout various filters, which often
>>> build up a structure similar to vtkCellTypes in order to perform their
>>> lookups.
>>>
>>> I'm asking at this time because I'm looking at some changes that may
>>> modify the vtkCellArray API/implementation anyway, and it'd be nice to fix
>>> up this mix of sequential access, unintuitive random-access, and auxiliary
>>> lookup structures into a more friendly and intuitive API. These changes
>>> would not be effected until after VTK 6.0 is out.
>>>
>>> Thoughts? Discussions? Alternate perspectives? All are welcome :-)
>>>
>>> Thanks,
>>> Dave
>>>
>>> _______________________________________________
>>> Powered by www.kitware.com
>>>
>>> Visit other Kitware open-source projects at
>>> http://www.kitware.com/opensource/opensource.html
>>>
>>> Follow this link to subscribe/unsubscribe:
>>> http://www.vtk.org/mailman/listinfo/vtk-developers
>>>
>>>
>>>
>>
>>
>> --
>> Unpaid intern in BillsBasement at noware dot com
>>
>
>
>
> --
> Unpaid intern in BillsBasement at noware dot com
>
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtk-developers
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20130320/27c6788c/attachment.html>