Better than O(n) prop operations on vtkRenderer

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Better than O(n) prop operations on vtkRenderer

Elvis Stansvik
Hi all,

The props of a vtkRenderer are kept in a vtkCollection (and probably
have been since VTKs childhood), meaning linear time
search/insert/remove.

I realize the use of vtkCollection is pervasive in these classes, and
also shines through in their API, so this is a bit of a long shot,
but, is there any chance that it'll at some point be converted to use
a sorted data structure, to permit logarithmic operations?

Has anyone else had the need to rapidly insert/remove/check for props
in a renderer with a large amounts of props in it? Has the idea of
having vtkRenderer backed by something else been discussed before?

Cheers,
Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

David Gobbi
Hi Elvis,

I don't think there are any fans of vtkCollection, but replacing it
with something modern would be lot of work and would provide
far less benefit than e.g. the recent reworking of the VTK data
arrays to provide flexible memory access patterns.

Also, given the cost for vtkRenderer to render a bunch of props,
you would have to be doing many hundreds (thousands?) of
insertions/removals per render before the time required for those
operations becomes significant to overall app performance.

  David


On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
Hi all,

The props of a vtkRenderer are kept in a vtkCollection (and probably
have been since VTKs childhood), meaning linear time
search/insert/remove.

I realize the use of vtkCollection is pervasive in these classes, and
also shines through in their API, so this is a bit of a long shot,
but, is there any chance that it'll at some point be converted to use
a sorted data structure, to permit logarithmic operations?

Has anyone else had the need to rapidly insert/remove/check for props
in a renderer with a large amounts of props in it? Has the idea of
having vtkRenderer backed by something else been discussed before?

Cheers,
Elvis

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Sebastien Jourdain via vtk-developers
My solution to this kind of problem in the past has been to build a (non-clustered) sorted index for fast lookup on the collection, without changing the underlying collection itself. In fact multiple indicies could be built and (if desired) attached to the collection in a list. Of course it means that each index needs to be rebuilt, when anything is added to or removed from the collection. The most efficient way to do that is to set a flag when anything changes and then only rebuild the index the next time it is accessed.



Todd Martin, PhD.
Freelance Engineer/Software Architect.



On Friday, 14 December 2018, 12:06:59 PM NZDT, David Gobbi <[hidden email]> wrote:


Hi Elvis,

I don't think there are any fans of vtkCollection, but replacing it
with something modern would be lot of work and would provide
far less benefit than e.g. the recent reworking of the VTK data
arrays to provide flexible memory access patterns.

Also, given the cost for vtkRenderer to render a bunch of props,
you would have to be doing many hundreds (thousands?) of
insertions/removals per render before the time required for those
operations becomes significant to overall app performance.

  David


On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
Hi all,

The props of a vtkRenderer are kept in a vtkCollection (and probably
have been since VTKs childhood), meaning linear time
search/insert/remove.

I realize the use of vtkCollection is pervasive in these classes, and
also shines through in their API, so this is a bit of a long shot,
but, is there any chance that it'll at some point be converted to use
a sorted data structure, to permit logarithmic operations?

Has anyone else had the need to rapidly insert/remove/check for props
in a renderer with a large amounts of props in it? Has the idea of
having vtkRenderer backed by something else been discussed before?

Cheers,
Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers


_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Paul Harris
I had to hack vtkCollection for this exact reason.

It keeps an ordered linked list because its design allows for the same element to be added multiple times.

I replaced that ordered linked list with a boost::multi_index, so it kept the old interface, multiple-entry feature, and addition-order,
but also added fast lookups and fast removal.

I'm happy to share the code.  It was hacked into an older VTK version, and added a boost dependency, so it'll need some cleanup in that respect.  But I did check the newer VTK code when I hacked it in July and it didn't look like it had changed much.  So apart from the boost dependency, it might be easy to bring into the latest VTK.


On Fri, 14 Dec 2018 at 07:19, Todd Martin via vtk-developers <[hidden email]> wrote:
My solution to this kind of problem in the past has been to build a (non-clustered) sorted index for fast lookup on the collection, without changing the underlying collection itself. In fact multiple indicies could be built and (if desired) attached to the collection in a list. Of course it means that each index needs to be rebuilt, when anything is added to or removed from the collection. The most efficient way to do that is to set a flag when anything changes and then only rebuild the index the next time it is accessed.



Todd Martin, PhD.
Freelance Engineer/Software Architect.



On Friday, 14 December 2018, 12:06:59 PM NZDT, David Gobbi <[hidden email]> wrote:


Hi Elvis,

I don't think there are any fans of vtkCollection, but replacing it
with something modern would be lot of work and would provide
far less benefit than e.g. the recent reworking of the VTK data
arrays to provide flexible memory access patterns.

Also, given the cost for vtkRenderer to render a bunch of props,
you would have to be doing many hundreds (thousands?) of
insertions/removals per render before the time required for those
operations becomes significant to overall app performance.

  David


On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
Hi all,

The props of a vtkRenderer are kept in a vtkCollection (and probably
have been since VTKs childhood), meaning linear time
search/insert/remove.

I realize the use of vtkCollection is pervasive in these classes, and
also shines through in their API, so this is a bit of a long shot,
but, is there any chance that it'll at some point be converted to use
a sorted data structure, to permit logarithmic operations?

Has anyone else had the need to rapidly insert/remove/check for props
in a renderer with a large amounts of props in it? Has the idea of
having vtkRenderer backed by something else been discussed before?

Cheers,
Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers


_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Bill Lorensen
Do you have benchmarks that show the differences? 

On Thu, Dec 13, 2018, 3:47 PM Paul Harris <[hidden email] wrote:
I had to hack vtkCollection for this exact reason.

It keeps an ordered linked list because its design allows for the same element to be added multiple times.

I replaced that ordered linked list with a boost::multi_index, so it kept the old interface, multiple-entry feature, and addition-order,
but also added fast lookups and fast removal.

I'm happy to share the code.  It was hacked into an older VTK version, and added a boost dependency, so it'll need some cleanup in that respect.  But I did check the newer VTK code when I hacked it in July and it didn't look like it had changed much.  So apart from the boost dependency, it might be easy to bring into the latest VTK.


On Fri, 14 Dec 2018 at 07:19, Todd Martin via vtk-developers <[hidden email]> wrote:
My solution to this kind of problem in the past has been to build a (non-clustered) sorted index for fast lookup on the collection, without changing the underlying collection itself. In fact multiple indicies could be built and (if desired) attached to the collection in a list. Of course it means that each index needs to be rebuilt, when anything is added to or removed from the collection. The most efficient way to do that is to set a flag when anything changes and then only rebuild the index the next time it is accessed.



Todd Martin, PhD.
Freelance Engineer/Software Architect.



On Friday, 14 December 2018, 12:06:59 PM NZDT, David Gobbi <[hidden email]> wrote:


Hi Elvis,

I don't think there are any fans of vtkCollection, but replacing it
with something modern would be lot of work and would provide
far less benefit than e.g. the recent reworking of the VTK data
arrays to provide flexible memory access patterns.

Also, given the cost for vtkRenderer to render a bunch of props,
you would have to be doing many hundreds (thousands?) of
insertions/removals per render before the time required for those
operations becomes significant to overall app performance.

  David


On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
Hi all,

The props of a vtkRenderer are kept in a vtkCollection (and probably
have been since VTKs childhood), meaning linear time
search/insert/remove.

I realize the use of vtkCollection is pervasive in these classes, and
also shines through in their API, so this is a bit of a long shot,
but, is there any chance that it'll at some point be converted to use
a sorted data structure, to permit logarithmic operations?

Has anyone else had the need to rapidly insert/remove/check for props
in a renderer with a large amounts of props in it? Has the idea of
having vtkRenderer backed by something else been discussed before?

Cheers,
Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers


_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Paul Harris
I didn't bother with the benchmarks, the improvement was so significant for my situation, it went from 5-10 seconds down to milliseconds for some operations.

I was adding hundreds or thousands of polydata actors (one per 3d model loaded from files),
and there were a few situations where VTK would to search the collection looking for a particular actor.

I recall that ::Remove() (or similar) was used in RemoveAll() ? Or destruction?  I can't quite remember.
There were a couple of other places where it would iterate through the list looking for a particular actor.
I think during destruction was a problem for me for this reason.
So it was effectively O(n^2) for a RemoveAll() operation.

eg If the list of actors / model files changed, I would need to remove lots of actors and add new actors to match the new files.
If the file list changed significantly, it would take a long long time just because of the actor removal.
If the user ticked off a whole folder of files, it might cause the GUI to pause for multiple seconds.
Significant enough that it became a road block and I had to spend some time on the problem.

Perhaps I could've structured it differently by putting all the polydata into one actor,
but as its implemented it works very quickly - no need to recompute polygons and vertices just to switch off an actor/model from the list of models.


On Fri, 14 Dec 2018 at 08:09, Bill Lorensen <[hidden email]> wrote:
Do you have benchmarks that show the differences? 

On Thu, Dec 13, 2018, 3:47 PM Paul Harris <[hidden email] wrote:
I had to hack vtkCollection for this exact reason.

It keeps an ordered linked list because its design allows for the same element to be added multiple times.

I replaced that ordered linked list with a boost::multi_index, so it kept the old interface, multiple-entry feature, and addition-order,
but also added fast lookups and fast removal.

I'm happy to share the code.  It was hacked into an older VTK version, and added a boost dependency, so it'll need some cleanup in that respect.  But I did check the newer VTK code when I hacked it in July and it didn't look like it had changed much.  So apart from the boost dependency, it might be easy to bring into the latest VTK.


On Fri, 14 Dec 2018 at 07:19, Todd Martin via vtk-developers <[hidden email]> wrote:
My solution to this kind of problem in the past has been to build a (non-clustered) sorted index for fast lookup on the collection, without changing the underlying collection itself. In fact multiple indicies could be built and (if desired) attached to the collection in a list. Of course it means that each index needs to be rebuilt, when anything is added to or removed from the collection. The most efficient way to do that is to set a flag when anything changes and then only rebuild the index the next time it is accessed.



Todd Martin, PhD.
Freelance Engineer/Software Architect.



On Friday, 14 December 2018, 12:06:59 PM NZDT, David Gobbi <[hidden email]> wrote:


Hi Elvis,

I don't think there are any fans of vtkCollection, but replacing it
with something modern would be lot of work and would provide
far less benefit than e.g. the recent reworking of the VTK data
arrays to provide flexible memory access patterns.

Also, given the cost for vtkRenderer to render a bunch of props,
you would have to be doing many hundreds (thousands?) of
insertions/removals per render before the time required for those
operations becomes significant to overall app performance.

  David


On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
Hi all,

The props of a vtkRenderer are kept in a vtkCollection (and probably
have been since VTKs childhood), meaning linear time
search/insert/remove.

I realize the use of vtkCollection is pervasive in these classes, and
also shines through in their API, so this is a bit of a long shot,
but, is there any chance that it'll at some point be converted to use
a sorted data structure, to permit logarithmic operations?

Has anyone else had the need to rapidly insert/remove/check for props
in a renderer with a large amounts of props in it? Has the idea of
having vtkRenderer backed by something else been discussed before?

Cheers,
Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers


_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Bill Lorensen
Is there an stl container that has similar performance. Adding a
 boost dependency in a core vtk class adds complexity to the build process.

On Thu, Dec 13, 2018, 4:26 PM Paul Harris <[hidden email] wrote:
I didn't bother with the benchmarks, the improvement was so significant for my situation, it went from 5-10 seconds down to milliseconds for some operations.

I was adding hundreds or thousands of polydata actors (one per 3d model loaded from files),
and there were a few situations where VTK would to search the collection looking for a particular actor.

I recall that ::Remove() (or similar) was used in RemoveAll() ? Or destruction?  I can't quite remember.
There were a couple of other places where it would iterate through the list looking for a particular actor.
I think during destruction was a problem for me for this reason.
So it was effectively O(n^2) for a RemoveAll() operation.

eg If the list of actors / model files changed, I would need to remove lots of actors and add new actors to match the new files.
If the file list changed significantly, it would take a long long time just because of the actor removal.
If the user ticked off a whole folder of files, it might cause the GUI to pause for multiple seconds.
Significant enough that it became a road block and I had to spend some time on the problem.

Perhaps I could've structured it differently by putting all the polydata into one actor,
but as its implemented it works very quickly - no need to recompute polygons and vertices just to switch off an actor/model from the list of models.


On Fri, 14 Dec 2018 at 08:09, Bill Lorensen <[hidden email]> wrote:
Do you have benchmarks that show the differences? 

On Thu, Dec 13, 2018, 3:47 PM Paul Harris <[hidden email] wrote:
I had to hack vtkCollection for this exact reason.

It keeps an ordered linked list because its design allows for the same element to be added multiple times.

I replaced that ordered linked list with a boost::multi_index, so it kept the old interface, multiple-entry feature, and addition-order,
but also added fast lookups and fast removal.

I'm happy to share the code.  It was hacked into an older VTK version, and added a boost dependency, so it'll need some cleanup in that respect.  But I did check the newer VTK code when I hacked it in July and it didn't look like it had changed much.  So apart from the boost dependency, it might be easy to bring into the latest VTK.


On Fri, 14 Dec 2018 at 07:19, Todd Martin via vtk-developers <[hidden email]> wrote:
My solution to this kind of problem in the past has been to build a (non-clustered) sorted index for fast lookup on the collection, without changing the underlying collection itself. In fact multiple indicies could be built and (if desired) attached to the collection in a list. Of course it means that each index needs to be rebuilt, when anything is added to or removed from the collection. The most efficient way to do that is to set a flag when anything changes and then only rebuild the index the next time it is accessed.



Todd Martin, PhD.
Freelance Engineer/Software Architect.



On Friday, 14 December 2018, 12:06:59 PM NZDT, David Gobbi <[hidden email]> wrote:


Hi Elvis,

I don't think there are any fans of vtkCollection, but replacing it
with something modern would be lot of work and would provide
far less benefit than e.g. the recent reworking of the VTK data
arrays to provide flexible memory access patterns.

Also, given the cost for vtkRenderer to render a bunch of props,
you would have to be doing many hundreds (thousands?) of
insertions/removals per render before the time required for those
operations becomes significant to overall app performance.

  David


On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
Hi all,

The props of a vtkRenderer are kept in a vtkCollection (and probably
have been since VTKs childhood), meaning linear time
search/insert/remove.

I realize the use of vtkCollection is pervasive in these classes, and
also shines through in their API, so this is a bit of a long shot,
but, is there any chance that it'll at some point be converted to use
a sorted data structure, to permit logarithmic operations?

Has anyone else had the need to rapidly insert/remove/check for props
in a renderer with a large amounts of props in it? Has the idea of
having vtkRenderer backed by something else been discussed before?

Cheers,
Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers


_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Andras Lasso
In reply to this post by Sebastien Jourdain via vtk-developers
We do this very similarly in 3D Slicer, too: we very rarely iterate through VTK collections but we use STL maps, deques, sets, etc. to keep track of groups of VTK objects.

There is no need to hypothesize about what performance degradation collections may cause because we can find performance bottlenecks much more efficiently by profiling.

What I usually see on Windows is that polydata algorithms tends to spend a lot of time (few ten percent) doing elementary data access operations, such as getting and setting point coordinates. So, some tricks to speed that up could make a difference. The abstraction layer that was added to allow storing data using arbitrary memory layout seemed to decrease performance, too (by about 5-10%). While visualizing image slices  of volumes using OpenGL2 backend + Qt5 appears to be slowed down by some OpenGL texture operations, which results in 10-20% lower refresh rates compared to the old OpenGL backend. Has anyone else found these same performance bottlenecks while profiling VTK-based applications?

Andras


From: Todd Martin via vtk-developers <[hidden email]>
Sent: Thursday, December 13, 2018 6:19 PM
To: Elvis Stansvik; David Gobbi
Cc: VTK Developers
Subject: Re: [vtk-developers] Better than O(n) prop operations on vtkRenderer

My solution to this kind of problem in the past has been to build a (non-clustered) sorted index for fast lookup on the collection, without changing the underlying collection itself. In fact multiple indicies could be built and (if desired) attached to the collection in a list. Of course it means that each index needs to be rebuilt, when anything is added to or removed from the collection. The most efficient way to do that is to set a flag when anything changes and then only rebuild the index the next time it is accessed.



Todd Martin, PhD.
Freelance Engineer/Software Architect.



On Friday, 14 December 2018, 12:06:59 PM NZDT, David Gobbi <[hidden email]> wrote:


Hi Elvis,

I don't think there are any fans of vtkCollection, but replacing it
with something modern would be lot of work and would provide
far less benefit than e.g. the recent reworking of the VTK data
arrays to provide flexible memory access patterns.

Also, given the cost for vtkRenderer to render a bunch of props,
you would have to be doing many hundreds (thousands?) of
insertions/removals per render before the time required for those
operations becomes significant to overall app performance.

  David


On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
Hi all,

The props of a vtkRenderer are kept in a vtkCollection (and probably
have been since VTKs childhood), meaning linear time
search/insert/remove.

I realize the use of vtkCollection is pervasive in these classes, and
also shines through in their API, so this is a bit of a long shot,
but, is there any chance that it'll at some point be converted to use
a sorted data structure, to permit logarithmic operations?

Has anyone else had the need to rapidly insert/remove/check for props
in a renderer with a large amounts of props in it? Has the idea of
having vtkRenderer backed by something else been discussed before?

Cheers,
Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers


_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Paul Harris
In reply to this post by Bill Lorensen
No, not without combining a couple of containers

On Fri., 14 Dec. 2018, 9:53 am Bill Lorensen <[hidden email] wrote:
Is there an stl container that has similar performance. Adding a
 boost dependency in a core vtk class adds complexity to the build process.

On Thu, Dec 13, 2018, 4:26 PM Paul Harris <[hidden email] wrote:
I didn't bother with the benchmarks, the improvement was so significant for my situation, it went from 5-10 seconds down to milliseconds for some operations.

I was adding hundreds or thousands of polydata actors (one per 3d model loaded from files),
and there were a few situations where VTK would to search the collection looking for a particular actor.

I recall that ::Remove() (or similar) was used in RemoveAll() ? Or destruction?  I can't quite remember.
There were a couple of other places where it would iterate through the list looking for a particular actor.
I think during destruction was a problem for me for this reason.
So it was effectively O(n^2) for a RemoveAll() operation.

eg If the list of actors / model files changed, I would need to remove lots of actors and add new actors to match the new files.
If the file list changed significantly, it would take a long long time just because of the actor removal.
If the user ticked off a whole folder of files, it might cause the GUI to pause for multiple seconds.
Significant enough that it became a road block and I had to spend some time on the problem.

Perhaps I could've structured it differently by putting all the polydata into one actor,
but as its implemented it works very quickly - no need to recompute polygons and vertices just to switch off an actor/model from the list of models.


On Fri, 14 Dec 2018 at 08:09, Bill Lorensen <[hidden email]> wrote:
Do you have benchmarks that show the differences? 

On Thu, Dec 13, 2018, 3:47 PM Paul Harris <[hidden email] wrote:
I had to hack vtkCollection for this exact reason.

It keeps an ordered linked list because its design allows for the same element to be added multiple times.

I replaced that ordered linked list with a boost::multi_index, so it kept the old interface, multiple-entry feature, and addition-order,
but also added fast lookups and fast removal.

I'm happy to share the code.  It was hacked into an older VTK version, and added a boost dependency, so it'll need some cleanup in that respect.  But I did check the newer VTK code when I hacked it in July and it didn't look like it had changed much.  So apart from the boost dependency, it might be easy to bring into the latest VTK.


On Fri, 14 Dec 2018 at 07:19, Todd Martin via vtk-developers <[hidden email]> wrote:
My solution to this kind of problem in the past has been to build a (non-clustered) sorted index for fast lookup on the collection, without changing the underlying collection itself. In fact multiple indicies could be built and (if desired) attached to the collection in a list. Of course it means that each index needs to be rebuilt, when anything is added to or removed from the collection. The most efficient way to do that is to set a flag when anything changes and then only rebuild the index the next time it is accessed.



Todd Martin, PhD.
Freelance Engineer/Software Architect.



On Friday, 14 December 2018, 12:06:59 PM NZDT, David Gobbi <[hidden email]> wrote:


Hi Elvis,

I don't think there are any fans of vtkCollection, but replacing it
with something modern would be lot of work and would provide
far less benefit than e.g. the recent reworking of the VTK data
arrays to provide flexible memory access patterns.

Also, given the cost for vtkRenderer to render a bunch of props,
you would have to be doing many hundreds (thousands?) of
insertions/removals per render before the time required for those
operations becomes significant to overall app performance.

  David


On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
Hi all,

The props of a vtkRenderer are kept in a vtkCollection (and probably
have been since VTKs childhood), meaning linear time
search/insert/remove.

I realize the use of vtkCollection is pervasive in these classes, and
also shines through in their API, so this is a bit of a long shot,
but, is there any chance that it'll at some point be converted to use
a sorted data structure, to permit logarithmic operations?

Has anyone else had the need to rapidly insert/remove/check for props
in a renderer with a large amounts of props in it? Has the idea of
having vtkRenderer backed by something else been discussed before?

Cheers,
Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers


_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Elvis Stansvik
In reply to this post by David Gobbi
Den fre 14 dec. 2018 kl 00:06 skrev David Gobbi <[hidden email]>:

>
> Hi Elvis,
>
> I don't think there are any fans of vtkCollection, but replacing it
> with something modern would be lot of work and would provide
> far less benefit than e.g. the recent reworking of the VTK data
> arrays to provide flexible memory access patterns.
>
> Also, given the cost for vtkRenderer to render a bunch of props,
> you would have to be doing many hundreds (thousands?) of
> insertions/removals per render before the time required for those
> operations becomes significant to overall app performance.

Yes, I figured as much. Note that I haven't even profiled/benchmarked
my use case to see whether it's a problem, it was just something that
struck me while reading the code for vtkViewport/vtkRenderer, that
e.g. RemoveViewPort is O(2N) (first checks for presence, then walks
the collection again when doing the removal).

You're probably right David that the time needed for the collection is
negligible to the other things going on.

In my use case I was removing thousands (though not tens of thousands)
of poly actors when the user zooms in with the scroll wheel, which may
happen rather rapidly, so I guess the "other stuff" in my case would
be the freeing of graphics resources et.c. We are using a glyph mapper
to cut down on the number of actors, but there may still be ~1000-2000
or so of them that needs to be removed.

Thanks everyone for your answers. I might do some measurements to see
whether this could really be something that hurts interactivity in our
case.

Elvis

>
>   David
>
>
> On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
>>
>> Hi all,
>>
>> The props of a vtkRenderer are kept in a vtkCollection (and probably
>> have been since VTKs childhood), meaning linear time
>> search/insert/remove.
>>
>> I realize the use of vtkCollection is pervasive in these classes, and
>> also shines through in their API, so this is a bit of a long shot,
>> but, is there any chance that it'll at some point be converted to use
>> a sorted data structure, to permit logarithmic operations?
>>
>> Has anyone else had the need to rapidly insert/remove/check for props
>> in a renderer with a large amounts of props in it? Has the idea of
>> having vtkRenderer backed by something else been discussed before?
>>
>> Cheers,
>> Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Elvis Stansvik
Den fre 14 dec. 2018 kl 07:53 skrev Elvis Stansvik
<[hidden email]>:

>
> Den fre 14 dec. 2018 kl 00:06 skrev David Gobbi <[hidden email]>:
> >
> > Hi Elvis,
> >
> > I don't think there are any fans of vtkCollection, but replacing it
> > with something modern would be lot of work and would provide
> > far less benefit than e.g. the recent reworking of the VTK data
> > arrays to provide flexible memory access patterns.
> >
> > Also, given the cost for vtkRenderer to render a bunch of props,
> > you would have to be doing many hundreds (thousands?) of
> > insertions/removals per render before the time required for those
> > operations becomes significant to overall app performance.
>
> Yes, I figured as much. Note that I haven't even profiled/benchmarked
> my use case to see whether it's a problem, it was just something that
> struck me while reading the code for vtkViewport/vtkRenderer, that
> e.g. RemoveViewPort is O(2N) (first checks for presence, then walks

RemoveViewProp

> the collection again when doing the removal).
>
> You're probably right David that the time needed for the collection is
> negligible to the other things going on.
>
> In my use case I was removing thousands (though not tens of thousands)
> of poly actors when the user zooms in with the scroll wheel, which may
> happen rather rapidly, so I guess the "other stuff" in my case would
> be the freeing of graphics resources et.c. We are using a glyph mapper
> to cut down on the number of actors, but there may still be ~1000-2000
> or so of them that needs to be removed.
>
> Thanks everyone for your answers. I might do some measurements to see
> whether this could really be something that hurts interactivity in our
> case.
>
> Elvis
>
> >
> >   David
> >
> >
> > On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
> >>
> >> Hi all,
> >>
> >> The props of a vtkRenderer are kept in a vtkCollection (and probably
> >> have been since VTKs childhood), meaning linear time
> >> search/insert/remove.
> >>
> >> I realize the use of vtkCollection is pervasive in these classes, and
> >> also shines through in their API, so this is a bit of a long shot,
> >> but, is there any chance that it'll at some point be converted to use
> >> a sorted data structure, to permit logarithmic operations?
> >>
> >> Has anyone else had the need to rapidly insert/remove/check for props
> >> in a renderer with a large amounts of props in it? Has the idea of
> >> having vtkRenderer backed by something else been discussed before?
> >>
> >> Cheers,
> >> Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Elvis Stansvik
In reply to this post by Elvis Stansvik
Den fre 14 dec. 2018 kl 07:53 skrev Elvis Stansvik
<[hidden email]>:

>
> Den fre 14 dec. 2018 kl 00:06 skrev David Gobbi <[hidden email]>:
> >
> > Hi Elvis,
> >
> > I don't think there are any fans of vtkCollection, but replacing it
> > with something modern would be lot of work and would provide
> > far less benefit than e.g. the recent reworking of the VTK data
> > arrays to provide flexible memory access patterns.
> >
> > Also, given the cost for vtkRenderer to render a bunch of props,
> > you would have to be doing many hundreds (thousands?) of
> > insertions/removals per render before the time required for those
> > operations becomes significant to overall app performance.
>
> Yes, I figured as much. Note that I haven't even profiled/benchmarked
> my use case to see whether it's a problem, it was just something that
> struck me while reading the code for vtkViewport/vtkRenderer, that
> e.g. RemoveViewPort is O(2N) (first checks for presence, then walks
> the collection again when doing the removal).
>
> You're probably right David that the time needed for the collection is
> negligible to the other things going on.

I just did a very quick check and the collection overhead is indeed
completely negligible for our purposes (removal of 10000 actors using
RemoveActor was 0.002 s).

Elvis

>
> In my use case I was removing thousands (though not tens of thousands)
> of poly actors when the user zooms in with the scroll wheel, which may
> happen rather rapidly, so I guess the "other stuff" in my case would
> be the freeing of graphics resources et.c. We are using a glyph mapper
> to cut down on the number of actors, but there may still be ~1000-2000
> or so of them that needs to be removed.
>
> Thanks everyone for your answers. I might do some measurements to see
> whether this could really be something that hurts interactivity in our
> case.
>
> Elvis
>
> >
> >   David
> >
> >
> > On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
> >>
> >> Hi all,
> >>
> >> The props of a vtkRenderer are kept in a vtkCollection (and probably
> >> have been since VTKs childhood), meaning linear time
> >> search/insert/remove.
> >>
> >> I realize the use of vtkCollection is pervasive in these classes, and
> >> also shines through in their API, so this is a bit of a long shot,
> >> but, is there any chance that it'll at some point be converted to use
> >> a sorted data structure, to permit logarithmic operations?
> >>
> >> Has anyone else had the need to rapidly insert/remove/check for props
> >> in a renderer with a large amounts of props in it? Has the idea of
> >> having vtkRenderer backed by something else been discussed before?
> >>
> >> Cheers,
> >> Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers

Reply | Threaded
Open this post in threaded view
|

Re: Better than O(n) prop operations on vtkRenderer

Elvis Stansvik
Den fre 14 dec. 2018 kl 08:13 skrev Elvis Stansvik
<[hidden email]>:

>
> Den fre 14 dec. 2018 kl 07:53 skrev Elvis Stansvik
> <[hidden email]>:
> >
> > Den fre 14 dec. 2018 kl 00:06 skrev David Gobbi <[hidden email]>:
> > >
> > > Hi Elvis,
> > >
> > > I don't think there are any fans of vtkCollection, but replacing it
> > > with something modern would be lot of work and would provide
> > > far less benefit than e.g. the recent reworking of the VTK data
> > > arrays to provide flexible memory access patterns.
> > >
> > > Also, given the cost for vtkRenderer to render a bunch of props,
> > > you would have to be doing many hundreds (thousands?) of
> > > insertions/removals per render before the time required for those
> > > operations becomes significant to overall app performance.
> >
> > Yes, I figured as much. Note that I haven't even profiled/benchmarked
> > my use case to see whether it's a problem, it was just something that
> > struck me while reading the code for vtkViewport/vtkRenderer, that
> > e.g. RemoveViewPort is O(2N) (first checks for presence, then walks
> > the collection again when doing the removal).
> >
> > You're probably right David that the time needed for the collection is
> > negligible to the other things going on.
>
> I just did a very quick check and the collection overhead is indeed
> completely negligible for our purposes (removal of 10000 actors using
> RemoveActor was 0.002 s).

Scratch that, the removal order I used hit a sweet spot. Removing in
random order it's 0.25 s, so not quite negligible..

Elvis

>
> Elvis
>
> >
> > In my use case I was removing thousands (though not tens of thousands)
> > of poly actors when the user zooms in with the scroll wheel, which may
> > happen rather rapidly, so I guess the "other stuff" in my case would
> > be the freeing of graphics resources et.c. We are using a glyph mapper
> > to cut down on the number of actors, but there may still be ~1000-2000
> > or so of them that needs to be removed.
> >
> > Thanks everyone for your answers. I might do some measurements to see
> > whether this could really be something that hurts interactivity in our
> > case.
> >
> > Elvis
> >
> > >
> > >   David
> > >
> > >
> > > On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <[hidden email]> wrote:
> > >>
> > >> Hi all,
> > >>
> > >> The props of a vtkRenderer are kept in a vtkCollection (and probably
> > >> have been since VTKs childhood), meaning linear time
> > >> search/insert/remove.
> > >>
> > >> I realize the use of vtkCollection is pervasive in these classes, and
> > >> also shines through in their API, so this is a bit of a long shot,
> > >> but, is there any chance that it'll at some point be converted to use
> > >> a sorted data structure, to permit logarithmic operations?
> > >>
> > >> Has anyone else had the need to rapidly insert/remove/check for props
> > >> in a renderer with a large amounts of props in it? Has the idea of
> > >> having vtkRenderer backed by something else been discussed before?
> > >>
> > >> Cheers,
> > >> Elvis
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Search the list archives at: http://markmail.org/search/?q=vtk-developers

Follow this link to subscribe/unsubscribe:
https://public.kitware.com/mailman/listinfo/vtk-developers