Removal of `virtual` keywords from ConstNeighborhoodIterator


(Dženan Zukić) #1

@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.


ITK 5.0 Alpha 2: Performance
(Bradley Lowekamp) #2

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.


(Pablo Hernandez-Cerdan) #3

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


(Bradley Lowekamp) #4

I am going to experiment with a patch where ALL virtualiazation of functions for ALL iterators is done… Lets see what happens…


ITK 5.0 Alpha 1: Modern C++
Is image.GetOffsetTable()[0] always equal to 1?
(Niels Dekker) #5

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.


itk::NeighborhoodRange: a new class for efficient modern C++ style iteration
itk::NeighborhoodRange: a new class for efficient modern C++ style iteration
(Bradley Lowekamp) #6

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.


(Pablo Hernandez-Cerdan) #7

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%

(Bradley Lowekamp) #8

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.


(Niels Dekker) #9

@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


(Niels Dekker) #10

@phcerdan Thanks very much for trying out the HoughTransformPerfTest with and without virtual keywords in ConstNeighborhoodIterator. Your results look really great! :grinning:

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 % :stuck_out_tongue_winking_eye:

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? :grinning:


(Pablo Hernandez-Cerdan) #11

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.


(Pablo Hernandez-Cerdan) #12

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? :smiley:


(Bradley Lowekamp) #13

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();
};

(Pablo Hernandez-Cerdan) #14

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.


(Bradley Lowekamp) #15

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.