[vtk-developers] vtkCellArray memory layout

Bill Lorensen bill.lorensen at gmail.com
Wed Mar 20 19:24:42 EDT 2013


I agree. i just threw it out to start a discussion.

On Wed, Mar 20, 2013 at 4:22 PM, Berk Geveci <berk.geveci at kitware.com>wrote:

> 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
>>
>>
>>
>


-- 
Unpaid intern in BillsBasement at noware dot com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20130320/58cd0816/attachment.html>


More information about the vtk-developers mailing list