[vtk-developers] vtkSMPTools::Sort()

[Will Schroeder]

Does anyone have a deeper understanding of vtkSortDataArray?

Not only does it use std::sort, but qsort, and even bubble sort make a
guest appearance in the Cxx file. I'd like to replace everything with a
vtkSMPTools::Sort(). (Utkarsh says this is worth parallelizing for
ParaView). It may that the comparison operation when using the tuple
components as a key is the difficulty if used with std::sort but I'm not
sure.

W


On Mon, Oct 5, 2015 at 11:29 AM, Will Schroeder <will.schroeder at kitware.com>
wrote:

> FYI- As some of you know we have been inserting shared memory parallel
> constructs via vtkSMPTools into VTK
> <http://www.kitware.com/blog/home/post/915>. Recently we added a new
> capability, vtkSMPTools::Sort(), that is a drop in replacement for
> std::sort. For large data with multi-core machines this can have a
> significant performance impact, and I am thinking about broadening the
> reach of vtkSMPTools::Sort() by replacing std::sort wherever it makes sense
> in VTK. There is a modest length list of classes that currently use
> std::sort (see the list below). I plan on doing this slowly over the next
> several months.
>
> Does anyone have a problem with this? I know some of the sorts are
> performed on relatively short containers and I'm sure it's not really worth
> the effort (so I will probably skip them). Any other comments or concerns?
>
> W
>
> PS- Note: parallel sorting really only works with
> VTK_SMP_IMPLEMENTATION_TYPE=TBB. We plan on adding an OpenMP version soon.
> Otherwise the fallback for Sequential, etc. is simply std::sort.
>
> --
> ./Charts/Core/vtkChartXY.cxx
> ./Charts/Core/vtkPlotArea.cxx
> ./Charts/Core/vtkPlotBag.cxx
> ./Charts/Core/vtkPlotBar.cxx
> ./Charts/Core/vtkPlotBox.cxx
> ./Charts/Core/vtkPlotPoints.cxx
> ./Charts/Core/vtkPlotStacked.cxx
> ./Common/Core/Testing/Cxx/TestArrayLookup.cxx
> ./Common/Core/Testing/Cxx/TestAtomic.cxx
> ./Common/Core/vtkSortDataArray.cxx
> ./Common/Core/vtkStringArray.cxx
> ./Common/DataModel/Testing/Cxx/TestDataArrayDispatcher.cxx
> ./Common/DataModel/Testing/Cxx/TestDispatchers.cxx
> ./Common/DataModel/vtkGraph.cxx
> ./Common/DataModel/vtkKdTree.cxx
> ./Common/DataModel/vtkPiecewiseFunction.cxx
> ./Common/DataModel/vtkReebGraph.cxx
> ./Common/DataModel/vtkSelectionNode.cxx
> ./Common/ExecutionModel/vtkSpanSpace.cxx
> ./Filters/AMR/vtkAMRCutPlane.cxx
> ./Filters/AMR/vtkAMRResampleFilter.cxx
> ./Filters/Extraction/vtkConvertSelection.cxx
> ./Filters/FlowPaths/vtkModifiedBSPTree.cxx
> ./Filters/FlowPaths/vtkStreaklineFilter.cxx
> ./Filters/General/vtkContourTriangulator.cxx
> ./Filters/General/vtkYoungsMaterialInterface.cxx
> ./Filters/Matlab/vtkMatlabMexAdapter.cxx
> ./Filters/Parallel/vtkExtractCTHPart.cxx
> ./Filters/ParallelGeometry/vtkPUnstructuredGridConnectivity.cxx
> ./Filters/ReebGraph/vtkReebGraphToJoinSplitTreeFilter.cxx
> ./Filters/Statistics/vtkExtractFunctionalBagPlot.cxx
> ./Imaging/Core/vtkImageStencilData.cxx
> ./Imaging/General/vtkImageHybridMedian2D.cxx
> ./Infovis/BoostGraphAlgorithms/vtkBoostExtractLargestComponent.cxx
> ./Infovis/Core/vtkNetworkHierarchy.cxx
> ./Infovis/Core/vtkReduceTable.cxx
> ./Infovis/Layout/vtkCosmicTreeLayoutStrategy.cxx
> ./Infovis/Parallel/Testing/Cxx/PBGLRandomGraph.cxx
> ./Interaction/Widgets/vtkClosedSurfacePointPlacer.cxx
> ./IO/Core/vtkGlobFileNames.cxx
> ./IO/Core/vtkSortFileNames.cxx
> ./IO/EnSight/vtkEnSightReader.cxx
> ./IO/Xdmf2/vtkXdmfWriter.cxx
> ./Parallel/Core/vtkSubGroup.cxx
> ./Rendering/Core/vtkColorTransferFunction.cxx
> ./Web/WebGLExporter/vtkWebGLExporter.cxx
>



-- 
William J. Schroeder, PhD
Kitware, Inc.
28 Corporate Drive
Clifton Park, NY 12065
will.schroeder at kitware.com
http://www.kitware.com
(518) 881-4902
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20151020/c40d7d26/attachment.html>