[vtk-developers] Shared ownership of an array of pointers

Wed Nov 21 10:08:22 EST 2012

+1 for improving vtkCollection. This will also benefit Slicer :)

On Wed, Nov 21, 2012 at 2:34 AM, Philippe Pébay
<philippe.pebay at kitware.com>wrote:

> Hello all,
>
> Thanks for all the good comments.
>
> Bill: because when shallow copying the structure, then the vector holding
> the pointers would be duplicated. This could be a problem with the data
> size that I am aiming for.
>
> For context: we want to represent O(10^10) or more AMR meshes. Typically,
> one "root" can represent in an implicit (tree) structure O(10^4) or more
> AMR cells. At the root level, we thus need to be able to hold O(10^6)
> pointers to these trees. If we store these in a STD vector, a shallow copy
> of the entire data set will mean a deep copy of the vector holding the
> pointers (and yet a shallow copy of the pointers themselves). The cost is
> prohibitive. So, we need an efficient structure for shared ownership of the
> collection of pointers.
>
> I think I am going to try again the vtkCollection route, but with the
> following acceleration:
>
> > I think you are going to want to allocate a slab of memory the exact nx
> * ny
> > * nz * sizeof pointer. Than you can encode just the number of pointers
> and
> > initial memory position in each instance of the collection.
> A question though: will that work if I use vtkSmartPointers instead of raw
> pointers? Can I predict the size of a SmartPointer? I have not done this
> before.
>
> Thanks
> Philippe
>
>
>
> On Wed, Nov 21, 2012 at 3:37 AM, Bill Lorensen <bill.lorensen at gmail.com>wrote:
>
>> Why not an std::vector of vtk smart pointers?
>>
>> On Tue, Nov 20, 2012 at 6:27 PM, Robert Maynard
>> <robert.maynard at kitware.com> wrote:
>> > I think you are going to want to allocate a slab of memory the exact nx
>> * ny
>> > * nz * sizeof pointer. Than you can encode just the number of pointers
>> and
>> > initial memory position in each instance of the collection.
>> >
>> > Lookup of exact elements is constant time, and iteration over the
>> entire set
>> > can be done very efficiently as you will have cache coherency on the
>> > pointers(slab allocating the actual objects is also recommended).
>> >
>> > Sent from my iPhone
>> >
>> > On Nov 20, 2012, at 5:45 PM, Philippe Pébay <philippe.pebay at kitware.com
>> >
>> > wrote:
>> >
>> > Hello Dave
>> >
>> > Thanks for the comments. So, this might be the better option: rather
>> than
>> > implementing a new concrete array type, using a possibly improved
>> version of
>> > the vtkCollection.
>> >
>> > A little more context: no random access is necessary. All that is
>> needed is
>> > the ability to iterate over the elements rapidly and in a scalable
>> fashion.
>> > The collection size is set once for all at the time of the creation of
>> the
>> > hyper tree grid object. The collection is used to collect a serialized
>> list
>> > of the nx * ny * nz grid of individual trees. It is, also, necessary
>> that
>> > shallow copies be done efficiently, that is, by not only shallow
>> copying all
>> > individual trees, but also the collection itself, for we do not want to
>> have
>> > to replicate O(10^6) pointers.
>> >
>> > Thanks
>> > Philippe
>> >
>> > On Tue, Nov 20, 2012 at 11:34 PM, David Cole <david.cole at kitware.com>
>> wrote:
>> >>
>> >> Its implementation is just a linked list. It will be as fast as you
>> >> can possibly be for:
>> >>
>> >>   - iterating the whole collection and doing something on each element
>> >>   - adding a new element to the end of the list
>> >>
>> >> For all else, including finding or removing specific items (by index
>> >> or identity), it will be as ridiculously slow as you'd expect a linked
>> >> list to be...
>> >>
>> >> After just a glance at the implementation, I'm not surprised it doesn't
>> >> "scale".
>> >>
>> >> If you need scalability, perhaps a better implementation could be
>> >> dropped in to the same API.
>> >>
>> >>
>> >> On Tue, Nov 20, 2012 at 5:25 PM, Philippe Pébay
>> >> <philippe.pebay at kitware.com> wrote:
>> >> > Hello David
>> >> >
>> >> > Thanks for the suggestion. I looked into vtkCollection but the code
>> was
>> >> > running slow with large collections. But it is possible that I will
>> not
>> >> > get
>> >> > any better results with the vtkObjectArray. Are you surprised that
>> the
>> >> > vtkCollection did not scale well (my observation on only one
>> platform)?
>> >> >
>> >> > Thanks
>> >> > Philippe
>> >> >
>> >> >
>> >> >
>> >> > On Tue, Nov 20, 2012 at 6:41 PM, David Thompson
>> >> > <david.thompson at kitware.com>
>> >> > wrote:
>> >> >>
>> >> >> Hi Philippe,
>> >> >>
>> >> >> I think the vtkObjectArray class sounds like a good idea, however be
>> >> >> aware
>> >> >> that vtkCollection already exists to fulfill a similar purpose.
>> >> >>
>> >> >>         David
>> >> >>
>> >> >> On Nov 20, 2012, at 12:28 PM, Philippe Pébay
>> >> >> <philippe.pebay at kitware.com>
>> >> >> wrote:
>> >> >>
>> >> >> > Hello David
>> >> >> >
>> >> >> > Yes, I think this is the best option. I am thinking that I could
>> >> >> > create
>> >> >> > this as a new concrete subclass of vtkAbstractArray available to
>> all,
>> >> >> > and
>> >> >> > not only as a helper class internal to my hyper tree
>> implementation.
>> >> >> > What do
>> >> >> > you think? Would this be useful?
>> >> >> >
>> >> >> > Thanks
>> >> >> > Philippe
>> >> >> >
>> >> >> > On Tue, Nov 20, 2012 at 6:25 PM, David Gobbi <
>> david.gobbi at gmail.com>
>> >> >> > wrote:
>> >> >> > Hi Phillippe,
>> >> >> >
>> >> >> > Actually I was wrong about vtkVariant not having any size
>> overhead.
>> >> >> > It
>> >> >> > needs
>> >> >> > to store the type along with the value.  So vtkVariantArray is no
>> >> >> > good
>> >> >> > for this.
>> >> >> >
>> >> >> > A helper class might be the best option.  You could make a
>> >> >> > vtkObjectArray
>> >> >> > class which would be just like vtkVoidArray except that it would
>> >> >> > objects.
>> >> >> >
>> >> >> >  - David
>> >> >> >
>> >> >> >
>> >> >> > On Tue, Nov 20, 2012 at 9:54 AM, Philippe Pébay
>> >> >> > <philippe.pebay at kitware.com> wrote:
>> >> >> > > Hello David
>> >> >> > >
>> >> >> > > Thanks for the summary about the absence of performance hit when
>> >> >> > > using
>> >> >> > > SPs
>> >> >> > > as opposed to RPs. I will remember it and use them more often
>> as a
>> >> >> > > result.
>> >> >> > >
>> >> >> > > Regarding the variant array, yes, the conversion to vtkObject
>> is a
>> >> >> > > concern.
>> >> >> > > I think that the most efficient option would be to create a
>> small
>> >> >> > > helper
>> >> >> > > class that would internally store a raw array of pointers. That
>> >> >> > > helper
>> >> >> > > would
>> >> >> > > derive from vtkObjectBase. That should avoid any perfomance hit.
>> >> >> > >
>> >> >> > > Philippe
>> >> >> > >
>> >> >> > >
>> >> >> > > On Tue, Nov 20, 2012 at 5:49 PM, David Gobbi
>> >> >> > > <david.gobbi at gmail.com>
>> >> >> > > wrote:
>> >> >> > >>
>> >> >> > >> Hi Phillippe,
>> >> >> > >>
>> >> >> > >> A vtkVariant is 64 bits, it should be no larger than a pointer.
>> >> >> > >> There
>> >> >> > >> is a function call overhead in ToVTKObject(), which might be a
>> >> >> > >> concern to
>> >> >> > >> you.
>> >> >> > >>
>> >> >> > >> The vtkSmartPointer is exactly the same size as a pointer, so
>> >> >> > >> there
>> >> >> > >> is no
>> >> >> > >> size
>> >> >> > >> overhead.  It has no computational overhead, either, except for
>> >> >> > >> the
>> >> >> > >> "operator=",
>> >> >> > >> the copy constructor, and the destructor (I wouldn't even count
>> >> >> > >> the
>> >> >> > >> overhead in
>> >> >> > >> the destructor, because you have to call ->Delete() eventually
>> >> >> > >> anyway).
>> >> >> > >> So do
>> >> >> > >> not avoid smart pointers because you are worried about
>> efficiency.
>> >> >> > >> The
>> >> >> > >> VTK
>> >> >> > >> smart pointers are very efficient because vtkObjectBase already
>> >> >> > >> has a
>> >> >> > >> built-in
>> >> >> > >> reference count.
>> >> >> > >>
>> >> >> > >>  - David
>> >> >> > >>
>> >> >> > >>
>> >> >> > >> On Tue, Nov 20, 2012 at 9:35 AM, Philippe Pébay
>> >> >> > >> <philippe.pebay at kitware.com> wrote:
>> >> >> > >> > Hello David
>> >> >> > >> >
>> >> >> > >> > Thanks for the suggestion: I am concerned by the overhead
>> that
>> >> >> > >> > comes
>> >> >> > >> > with
>> >> >> > >> > variants. Wouldn't it be more lightweight to use a
>> vtkVoidArray
>> >> >> > >> > instead?
>> >> >> > >> > The
>> >> >> > >> > array can potentially contain O(10⁶) pointers. By the way
>> this
>> >> >> > >> > is
>> >> >> > >> > for
>> >> >> > >> > the
>> >> >> > >> > same reason that I have, so far, refrained from using
>> >> >> > >> > vtkSmartPointers
>> >> >> > >> > as
>> >> >> > >> > opposed to raw pointers, by fear of the overhead involved. Is
>> >> >> > >> > this
>> >> >> > >> > extra
>> >> >> > >> > caution excessive?
>> >> >> > >> >
>> >> >> > >> > Thanks
>> >> >> > >> > Philippe
>> >> >> > >> >
>> >> >> > >> > On Tue, Nov 20, 2012 at 5:31 PM, David Gobbi
>> >> >> > >> > <david.gobbi at gmail.com>
>> >> >> > >> > wrote:
>> >> >> > >> >>
>> >> >> > >> >> Hi Philippe,
>> >> >> > >> >>
>> >> >> > >> >> If the pointers are pointers to VTK objects, then you can
>> use
>> >> >> > >> >> vtkVariantArray.
>> >> >> > >> >>
>> >> >> > >> >>  - David
>> >> >> > >> >>
>> >> >> > >> >>
>> >> >> > >> >> On Tue, Nov 20, 2012 at 9:29 AM, Philippe Pébay
>> >> >> > >> >> <philippe.pebay at kitware.com> wrote:
>> >> >> > >> >> > Just an idea: couldn't a vtkVoidArray be used (or abused)
>> as
>> >> >> > >> >> > container
>> >> >> > >> >> > of
>> >> >> > >> >> > raw pointers, that would be appropriately downcasted
>> >> >> > >> >> > internally
>> >> >> > >> >> > to
>> >> >> > >> >> > the
>> >> >> > >> >> > concrete type to which they are supposed to point? For
>> >> >> > >> >> > instance,
>> >> >> > >> >> > instead
>> >> >> > >> >> > of
>> >> >> > >> >> > having a
>> >> >> > >> >> >  vtkMyInternalObject** obj
>> >> >> > >> >> > instance variable, couldn't I use a
>> >> >> > >> >> >  vtkVoidArray* obj
>> >> >> > >> >> > instead, where each entry in obj would be the raw pointer
>> to
>> >> >> > >> >> > a
>> >> >> > >> >> > vtkSmartPointer<vtkMyInternalObject>?
>> >> >> > >> >> >
>> >> >> > >> >> > Thanks
>> >> >> > >> >> > Philippe
>> >> >> > >> >> >
>> >> >> > >> >> >
>> >> >> > >> >> > On Tue, Nov 20, 2012 at 5:14 PM, Philippe Pébay
>> >> >> > >> >> > <philippe.pebay at kitware.com>
>> >> >> > >> >> > wrote:
>> >> >> > >> >> >>
>> >> >> > >> >> >> Hello Kyle
>> >> >> > >> >> >>
>> >> >> > >> >> >> Yes, I would want to avoid a dependency on Boost. But
>> this
>> >> >> > >> >> >> is
>> >> >> > >> >> >> basically
>> >> >> > >> >> >> what I am tried to reproduce (the Boost shared array of
>> >> >> > >> >> >> pointers).
>> >> >> > >> >> >>
>> >> >> > >> >> >> Thanks
>> >> >> > >> >> >> P
>> >> >> > >> >> >>
>> >> >> > >> >> >>
>> >> >> > >> >> >> On Tue, Nov 20, 2012 at 5:13 PM, Kyle Lutz
>> >> >> > >> >> >> <kyle.lutz at kitware.com>
>> >> >> > >> >> >> wrote:
>> >> >> > >> >> >>>
>> >> >> > >> >> >>> Would using boost suffice? Or do you want a solution
>> using
>> >> >> > >> >> >>> just
>> >> >> > >> >> >>> VTK?
>> >> >> > >> >> >>>
>> >> >> > >> >> >>> -kyle
>> >> >> > >> >> >>>
>> >> >> > >> >> >>> On Tue, Nov 20, 2012 at 7:58 AM, Philippe Pébay
>> >> >> > >> >> >>> <philippe.pebay at kitware.com> wrote:
>> >> >> > >> >> >>> > Hello all,
>> >> >> > >> >> >>> >
>> >> >> > >> >> >>> > I need to keep track of shared ownership of an array
>> of
>> >> >> > >> >> >>> > pointers.
>> >> >> > >> >> >>> > Can
>> >> >> > >> >> >>> > someone point me towards an example of code that
>> already
>> >> >> > >> >> >>> > does
>> >> >> > >> >> >>> > this?
>> >> >> > >> >> >>> > This
>> >> >> > >> >> >>> > should amount to a small helper class that contains
>> the
>> >> >> > >> >> >>> > array of
>> >> >> > >> >> >>> > pointers
>> >> >> > >> >> >>> > along with a reference count.
>> >> >> > >> >> >>> >
>> >> >> > >> >> >>> > Thank you!
>> >> >> > >> >> >>> > Philippe
>> >> >> > >> >> >>> >
>> >> >> > >> >> >>> >
>> >> >> > >> >> >>> > --
>> >> >> > >> >> >>> > Philippe Pébay, PhD
>> >> >> > >> >> >>> > Director of Visualization and High Performance
>> Computing
>> >> >> > >> >> >>> > /
>> >> >> > >> >> >>> > Directeur de la Visualisation et du Calcul Haute
>> >> >> > >> >> >>> > Performance
>> >> >> > >> >> >>> > Kitware SAS
>> >> >> > >> >> >>> > 26 rue Louis Guérin, 69100 Villeurbanne, France
>> >> >> > >> >> >>> > +33 (0) 6.83.61.55.70 / 4.37.45.04.15
>> >> >> > >> >> >>> > http://www.kitware.fr
>> >> >> > >
>> >> >> > >
>> >> >> > >
>> >> >> > >
>> >> >> > > --
>> >> >> > > Philippe Pébay, PhD
>> >> >> > > Director of Visualization and High Performance Computing /
>> >> >> > > Directeur de la Visualisation et du Calcul Haute Performance
>> >> >> > > Kitware SAS
>> >> >> > > 26 rue Louis Guérin, 69100 Villeurbanne, France
>> >> >> > > +33 (0) 6.83.61.55.70 / 4.37.45.04.15
>> >> >> > > http://www.kitware.fr
>> >> >> >
>> >> >> >
>> >> >> >
>> >> >> > --
>> >> >> > Philippe Pébay, PhD
>> >> >> > Director of Visualization and High Performance Computing /
>> >> >> > Directeur de la Visualisation et du Calcul Haute Performance
>> >> >> > Kitware SAS
>> >> >> > 26 rue Louis Guérin, 69100 Villeurbanne, France
>> >> >> > +33 (0) 6.83.61.55.70 / 4.37.45.04.15
>> >> >> > http://www.kitware.fr
>> >> >> > _______________________________________________
>> >> >> > 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
>> >> >> >
>> >> >>
>> >> >
>> >> >
>> >> >
>> >> > --
>> >> > Philippe Pébay, PhD
>> >> > Director of Visualization and High Performance Computing /
>> >> > Directeur de la Visualisation et du Calcul Haute Performance
>> >> > Kitware SAS
>> >> > 26 rue Louis Guérin, 69100 Villeurbanne, France
>> >> > +33 (0) 6.83.61.55.70 / 4.37.45.04.15
>> >> > http://www.kitware.fr
>> >> >
>> >> > _______________________________________________
>> >> > 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
>> >> >
>> >> >
>> >
>> >
>> >
>> >
>> > --
>> > Philippe Pébay, PhD
>> > Director of Visualization and High Performance Computing /
>> > Directeur de la Visualisation et du Calcul Haute Performance
>> > Kitware SAS
>> > 26 rue Louis Guérin, 69100 Villeurbanne, France
>> > +33 (0) 6.83.61.55.70 / 4.37.45.04.15
>> > http://www.kitware.fr
>> >
>> > _______________________________________________
>> > 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
>> >
>> >
>> > _______________________________________________
>> > 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
>>
>
>
>
> --
> Philippe Pébay, PhD
> Director of Visualization and High Performance Computing /
> Directeur de la Visualisation et du Calcul Haute Performance
> Kitware SAS
> 26 rue Louis Guérin, 69100 Villeurbanne, France
> +33 (0) 6.83.61.55.70 / 4.37.45.04.15
> http://www.kitware.fr <http://www.kitware.fr/>
>
> _______________________________________________
> 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
>
>
>

-- 
+1 919 869 8849
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20121121/a2cb9f49/attachment.html>