[vtk-developers] Shared ownership of an array of pointers
Philippe Pébay
philippe.pebay at kitware.com
Wed Nov 21 02:34:06 EST 2012
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/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20121121/319b449b/attachment.html>
More information about the vtk-developers
mailing list