@Niels_Dekker suggests a somewhat significant interface change to ConstNeighborhoodIterator. But I think that it is not likely anyone created derived classes of it, so it is probably a non-issue. If someone has a contrary opinion, please pitch in here or in the patch.
The methods do appear to be overloaded:
$ grep virtual $(find Modules/Core/Common/include -name *Neighborhood*Iterator*.h)
...
Modules/Core/Common/include/itkConstShapedNeighborhoodIterator.h: virtual ~ConstIterator() {}
Modules/Core/Common/include/itkConstShapedNeighborhoodIterator.h: virtual void ActivateOffset(const OffsetType & off)
Modules/Core/Common/include/itkConstShapedNeighborhoodIterator.h: virtual void DeactivateOffset(const OffsetType & off)
Modules/Core/Common/include/itkConstShapedNeighborhoodIterator.h: virtual void ClearActiveList()
Modules/Core/Common/include/itkConstShapedNeighborhoodIterator.h: virtual void ActivateIndex( NeighborIndexType );
Modules/Core/Common/include/itkConstShapedNeighborhoodIterator.h: virtual void DeactivateIndex( NeighborIndexType );
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual IndexType GetIndex(void) const
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual IndexType GetIndex(const OffsetType & o) const
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual IndexType GetIndex(NeighborIndexType i) const
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: * of arbitrary type and must use virtual functions. */
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual void GoToBegin();
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual void GoToEnd();
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual void Initialize(const SizeType & radius, const ImageType *ptr, const RegionType & region);
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual bool IsAtBegin() const
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual bool IsAtEnd() const;
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual void SetLoop(const IndexType & p)
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual void SetBound(const SizeType &);
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual void SetBeginIndex(const IndexType & start)
Modules/Core/Common/include/itkConstNeighborhoodIteratorWithOnlyIndex.h: virtual void SetEndIndex();
...
I would think the other Neighborhood iterators should have their virtual methods removed too.
There are a lot of virtual methods in general in the Iterators. Using iterators polymorphicly is not a common practice and compromises performance. There should be consistency between the iterators if they can be used polymophically or not.
2 Likes
The ~18% increase performance is quite impressive. I have noticed as well that neighborhood iterators were a bottle-neck, glad to to see work on this.
Iterators are such a powerful abstraction, but making them as fast as possible (zero-cost abstraction in the c++ spirit) seems like a must.
+1
2 Likes
I am going to experiment with a patch where ALL virtualiazation of functions for ALL iterators is done… Lets see what happens…
3 Likes
FYI, I did observe the ~18% reduction of run-time duration by running the following little program, before and after the patch (PERF: Removed all ‘virtual’ keywords from ConstNeighborhoodIterator):
#include <itkHoughTransform2DCirclesImageFilter.h>
#include <iostream>
#include <ctime>
int main()
{
typedef unsigned char PixelType;
const auto image = itk::Image<PixelType>::New();
enum { sizeX = 19000, sizeY = sizeX };
image->SetRegions({ sizeX, sizeY });
image->Allocate();
image->FillBuffer(1);
const auto filter =
itk::HoughTransform2DCirclesImageFilter<PixelType, unsigned char, double>::New();
filter->SetInput(image);
std::cout << "Start" << std::endl;
const auto time1 = std::time(nullptr);
filter->Update();
const auto time2 = std::time(nullptr);
std::cout << "Duration: " << (time2 - time1) << " seconds" << std::endl;
}
It was built by Visual C++ 2015 (Update 3), 64-bit, Release configuration. Before the patch, filter->Update() took at least 28 seconds on my machine (at work), while it could do it in 23 seconds after the patch. So I gained 5 seconds. 5/28 is about 18%.
I’m interested to hear from any of you if you can also observe that the patch yields such a significant performance improvement. If you have the time, please try to compile + run my little program before and after the patch, and tell us the result!
Note: the little test program here is an adapted version of the test program I posted at Hough Transform 2D Circles Image Filter GetCircles patch. just having a higher value for sizeX and sizeY.
2 Likes
It would be great if you couladd a benchmark to the ITKPerformanceBencmark repository for the hough transform. There are some cool features for the repo that are begin developed what will help track performance over time for ITK.
Tested in my laptop:
cmake_minimum_required(VERSION 3.1)
project(HoughTransformPerfTest)
find_package(ITK COMPONENTS
ITKImageFeature
REQUIRED
)
include(${ITK_USE_FILE})
add_executable(HoughTransformPerfTest HoughTransformPerfTest.cpp)
target_link_libraries(HoughTransformPerfTest PUBLIC ${ITK_LIBRARIES})
10 runs each:
Old, virtual (seconds):
43, 51, 47, 45, 46, 46, 47, 47, 48, 47
mean: 46.5
New, not-virtual (seconds):
36, 32, 38, 36, 39, 33, 34, 35, 31, 39
mean: 35.3 (EDIT: corrected)
diff = 11.2
decrease_percentage = diff / old x 100 = 24%
1 Like
My experimentation with broad removal of all virtual functions ended in about 56 test failures and ~ 15 of those SEGFAULTS.
350 - itkShapedNeighborhoodIteratorTest (SEGFAULT)
1166 - itkVectorImageTest (SEGFAULT)
1712 - itkBinaryImageToWhitakerSparseLevelSetsv4AdaptorTest (Failed)
1723 - itkSingleLevelSetsv4WhitakerImage2DTest (Failed)
1724 - itkSingleLevelSetsv4WhitakerImage2DTestThreads (Failed)
1726 - itkSingleLevelSetsv4ShiImage2DTest (Failed)
1727 - itkSingleLevelSetsv4WhitakerImage2DWithCurvatureTest (Failed)
1731 - itkLevelSetsv4EquationPropagationTermTest (Failed)
1732 - itkLevelSetsv4EquationLaplacianTermTest (Failed)
1734 - itkTwoLevelSetsv4WhitakerImage2DTest (Failed)
1736 - itkTwoLevelSetsv4ShiImage2DTest (Failed)
1744 - itkMultiLevelSetsv4WhitakerImageSubset2DTest (Failed)
1745 - itkMultiLevelSetsv4ShiImageSubset2DTest (Failed)
1746 - itkMultiLevelSetsv4MalcolmImageSubset2DTest (Failed)
1750 - itkClosingByReconstructionImageFilterTest2 (Failed)
1759 - itkGrayscaleFillholeImageFilterTest (Failed)
1765 - itkHConcaveImageFilterTestFullyConnectedOff (Failed)
1766 - itkHConcaveImageFilterTestFullyConnectedOn (Failed)
1769 - itkHConvexConcaveImageFilterTest (Failed)
1773 - itkHMinimaImageFilterTestFullyConnectedOn (Failed)
1779 - itkOpeningByReconstructionImageFilterTest2 (Failed)
1783 - itkDoubleThresholdImageFilterTest2 (Failed)
1784 - itkRemoveBoundaryObjectsTest (Failed)
1785 - itkRemoveBoundaryObjectsTest2 (Failed)
2083 - itkConnectedThresholdImageFilterTest2 (Failed)
2174 - itkBoxMeanImageFilterTest3 (Failed)
2175 - itkBoxMeanImageFilterTest10 (Failed)
2176 - itkBoxSigmaImageFilterTest3 (Failed)
2177 - itkBoxSigmaImageFilterTest10 (Failed)
2463 - itkMorphologicalWatershedFromMarkersImageFilterTestM0F0 (Failed)
2464 - itkMorphologicalWatershedFromMarkersImageFilterTestM0F1 (Failed)
2465 - itkMorphologicalWatershedFromMarkersImageFilterTestM1F0 (SEGFAULT)
2466 - itkMorphologicalWatershedFromMarkersImageFilterTestM1F1 (SEGFAULT)
2467 - itkMorphologicalWatershedImageFilterTestButtonHoleM0F0 (Failed)
2468 - itkMorphologicalWatershedImageFilterTestPassValuesM0F0 (Failed)
2469 - itkMorphologicalWatershedImageFilterTestPlateauM0F0 (Failed)
2470 - itkMorphologicalWatershedImageFilterTestThickLinesM0F0 (Failed)
2471 - itkMorphologicalWatershedImageFilterTestButtonHoleM0F1 (Failed)
2472 - itkMorphologicalWatershedImageFilterTestPassValuesM0F1 (Failed)
2473 - itkMorphologicalWatershedImageFilterTestPlateauM0F1 (Failed)
2474 - itkMorphologicalWatershedImageFilterTestThickLinesM0F1 (Failed)
2475 - itkMorphologicalWatershedImageFilterTestButtonHoleM1F0 (SEGFAULT)
2476 - itkMorphologicalWatershedImageFilterTestPassValuesM1F0 (SEGFAULT)
2477 - itkMorphologicalWatershedImageFilterTestPlateauM1F0 (SEGFAULT)
2478 - itkMorphologicalWatershedImageFilterTestThickLinesM1F0 (Failed)
2479 - itkMorphologicalWatershedImageFilterTestButtonHoleM1F1 (SEGFAULT)
2480 - itkMorphologicalWatershedImageFilterTestPassValuesM1F1 (SEGFAULT)
2481 - itkMorphologicalWatershedImageFilterTestPlateauM1F1 (SEGFAULT)
2482 - itkMorphologicalWatershedImageFilterTestThickLinesM1F1 (SEGFAULT)
2483 - itkMorphologicalWatershedImageFilterTestLevel00 (SEGFAULT)
2484 - itkMorphologicalWatershedImageFilterTestLevel10 (SEGFAULT)
2485 - itkMorphologicalWatershedImageFilterTestLevel20 (SEGFAULT)
2486 - itkMorphologicalWatershedImageFilterTestLevel30 (SEGFAULT)
2487 - itkMorphologicalWatershedImageFilterTestLevel40 (SEGFAULT)
2488 - itkMorphologicalWatershedImageFilterTestLevel50 (SEGFAULT)
Broadly, the flood fill iterations and some of the derived neighborhood iterators override methods and polymorphism is not occurring in the base class implementations as needed.
I am wondering of these iterators could utilize the Curiously Recursive Design Pattern could be used.
1 Like
@blowekamp Hmmm…, that’s a pity! Can you figure out which particular virtual functions were supposed to be overridden, causing the test failures? I never saw any override of any virtual function introduced by itk::ConstNeighborhoodIterator. But you know, I first declared all of them ‘final’, as a WIP, just to be sure that they were not overridden anywhere in ITK: http://review.source.kitware.com/#/c/23285/3
1 Like
@phcerdan Thanks very much for trying out the HoughTransformPerfTest with and without virtual keywords in ConstNeighborhoodIterator. Your results look really great! 
What compiler (+ version) did you use? Did you switch on compiler optimizations?
Maybe you should compare the best result, instead of the mean, of both virtual and not-virtual: (43 - 31)/43 x 100 = 27,9 % 
Update (based on an old version of Pablo’s post):
My calculator tells me that the mean of the new (not-virtual) results (36, 32, 38, 36, 39, 33, 34, 35, 31, 39) is 35.3 seconds!!! So then, based on comparing the means, you’ll get to 24%, right?
1 Like
You are right! I summed 38 twice (I still have the calculator app open). I have corrected the post.
The optimizations are the ones provided by CMake with the CMAKE_BUILD_TYPE = Release config.
The compiler was g++ version 7.3.1.
1 Like
The only iterator unit test failing is this… not that bad.
Can you run ctest on that test with -VV to see more? And/or can you upload your experimentation to gerrit with a big WIP on it? 
1 Like
Sorry for this brevity…
Patch:
http://review.source.kitware.com/#/c/23307/
stack trace:
Starting program: /scratch/blowekamp/build/ITK/bin/ITKCommon2TestDriver "--redirectOutput" "/scratch/blowekamp/build/ITK/Testing/Temporary/itkShapedNeighborhoodIteratorTest.txt" "itkShapedNeighborhoodIteratorTest"
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".
Test output has been redirected to: /scratch/blowekamp/build/ITK/Testing/Temporary/itkShapedNeighborhoodIteratorTest.txt
Program received signal SIGSEGV, Segmentation fault.
0x00000000006187e2 in itk::ConstNeighborhoodIterator<itk::Image<itk::Index<4u>, 4u>, itk::ZeroFluxNeumannBoundaryCondition<itk::Image<itk::Index<4u>, 4u>, itk::Image<itk::Index<4u>, 4u> > >::GetPixel (this=0x7fffffffd4d0, n=140737488344272,
IsInBounds=@0x7fffffffd35f: true)
at /home/blowekamp/src/ITK/Modules/Core/Common/include/itkConstNeighborhoodIterator.hxx:163
163 return ( m_NeighborhoodAccessorFunctor.Get( this->operator[](n) ) );
Missing separate debuginfos, use: debuginfo-install glibc-2.17-196.el7_4.2.x86_64 libgcc-4.8.5-16.el7_4.2.x86_64 libstdc++-4.8.5-16.el7_4.2.x86_64
(gdb) where
#0 0x00000000006187e2 in itk::ConstNeighborhoodIterator<itk::Image<itk::Index<4u>, 4u>, itk::ZeroFluxNeumannBoundaryCondition<itk::Image<itk::Index<4u>, 4u>, itk::Image<itk::Index<4u>, 4u> > >::GetPixel (this=0x7fffffffd4d0,
n=140737488344272, IsInBounds=@0x7fffffffd35f: true)
at /home/blowekamp/src/ITK/Modules/Core/Common/include/itkConstNeighborhoodIterator.hxx:163
#1 0x00000000006163c0 in itk::ConstNeighborhoodIterator<itk::Image<itk::Index<4u>, 4u>, itk::ZeroFluxNeumannBoundaryCondition<itk::Image<itk::Index<4u>, 4u>, itk::Image<itk::Index<4u>, 4u> > >::GetPixel (this=0x7fffffffd4d0,
i=140737488344272) at /home/blowekamp/src/ITK/Modules/Core/Common/include/itkConstNeighborhoodIterator.h:177
#2 0x0000000000623b7c in itk::ConstShapedNeighborhoodIterator<itk::Image<itk::Index<4u>, 4u>, itk::ZeroFluxNeumannBoundaryCondition<itk::Image<itk::Index<4u>, 4u>, itk::Image<itk::Index<4u>, 4u> > >::ConstIterator::Get (this=0x7fffffffd970)
at /home/blowekamp/src/ITK/Modules/Core/Common/include/itkConstShapedNeighborhoodIterator.h:187
#3 0x0000000000622e7c in itkShapedNeighborhoodIteratorTest ()
at /home/blowekamp/src/ITK/Modules/Core/Common/test/itkShapedNeighborhoodIteratorTest.cxx:116
#4 0x0000000000414104 in main (ac=1, av=0x7fffffffe050) at Modules/Core/Common/test/ITKCommon2TestDriver.cxx:521
Proposed design pattern:
template <class T>
struct Base
{
void interface()
{
// ...
static_cast<T*>(this)->implementation();
// ...
}
static void static_func()
{
// ...
T::static_sub_func();
// ...
}
};
struct Derived : Base<Derived>
{
void implementation();
static void static_sub_func();
};
1 Like
I think the destructor of the bases should be virtual at least.
This is the case for ConstNeighborhoodIterator which is derived from Neighborhood, which keeps the virtual destructor.
1 Like
I have a comprehensive removal of virtual from the neighborhood iterators in Gerrit now:
http://review.source.kitware.com/#/c/23319/
The “Shape” iterators had some use of overloaded methods that needed attention, where I utilized the Curiously Recurrent design patter for static polymorphism. It it a bit overkill, so if there are more elegant solutions suggested please feel free to propose an alternative patch for those classes.
Additionally, I added a performance test for the MorphologicalWatershedImageFilter which utilizes the Shaped iterators:
I was getting about a 15% improvement with this patch.
2 Likes