[ITK-dev] Fwd: Change in ITK[master]: BUG: Make valid calling with m_NumElements == 0

[Luc Hermitte]

Le 26/10/2015 16:24, David Cole a écrit :
> (cc-ing myself with my ITK dev mailing list email so I can loop in the
> ITK dev list so others may participate in the discussion if they feel so
> inclined)
>
>
> I think you must mean:
> std::fill(m_Data, m_NumElements, val)
>
> ...because if you really do mean m_Data->m_NumElements, you
> still have a problem when m_Data is nullptr.

Yes indeed, you're right. (It won't compile anyway. ^^')


> Same with:
> std::copy(&v.m_Data[0], &v.m_Data[N], &this->m_Data[0]);
>
> If m_Data can possibly be nullptr in either "v" or "this" then I do not
> see how this is a useful call to std::copy without checking for nullptr.
> If m_Data is nullptr, m_Data[0] and m_Data[N] are meaningless expressions.

They still mean m_Data+0 and m_Data+N. If N == 0, this is, IMO, somehow
a valid range, even is trivially empty. And copy() knows how to copy
empty ranges. We should not have to test whether the range is empty or not.

> I would really really really like to see some evidence from you that
> adding nullptr checks is materially harmful to performance in some real
> world fill/copy scenario before agreeing to any patch which does not
> include nullptr checks.

fill_n case should have already been fixed: I've used fill() instead to
force VC++ STL use preconditions expressed with a range instead of an
iterator.

Regarding the last case: copy().
I could return the question.
What's wrong with replacing the last and only invalid call to std::copy
(according to VC++ excessive checks) with:

  for (size_t i = 0; i != m_NumElements ; ++i)
    this->m_Data[i] = v.m_Data[i];
?

I agree that premature optimisation is a waste of time. Here, several of
you are suggesting the opposite: a premature pessimization, i.e. to do a
test that shall not be required if VC++ std::copy() preconditions were
correct.

Note BTW that I'm just suggesting to revert one change that I've
introduced in a previous patch
(http://review.source.kitware.com/#/c/19962/7/Modules/Core/Common/include/itkVariableLengthVector.hxx)


On a side note, I've submitted a bug report to VC++ tracker
(https://connect.microsoft.com/VisualStudio/feedback/details/1947236).


Regards
--Luc H.

>
>
> Thanks,
> David C.
>
>
>
> On Mon, Oct 26, 2015 at 10:48 AM, Luc Hermitte <luc.hermitte at c-s.fr
> <mailto:luc.hermitte at c-s.fr>> wrote:
>
>     After further investigations.
>
>     VC++'s fill() requires:
>     - the output range to be valid (i.e., in our case, if first!=last,
first
>     and last must be non null pointers, and first must be < last)
>
>     VC++'s fill_n() requires
>     - the output iterator to be valid, i.e. not null in case of a pointer
>
>     This means that by using std::fill(m_Data, m_Data->m_NumElements, val)
>     we should fix the bug observed.
>
>     I've embedded the fix in my latest patch set
>     (http://review.source.kitware.com/#/c/20253/)
>
>
>     Regarding std::copy().
>     VC++'s copy() requires :
>     - the input range to be valid (if first!=last, first and last
shall not
>     be null pointers, and first shall be < last)
>     - the output iterator to be valid (!=0 in case of a pointer)
>
>     There is a still bug with VC++ copy() implementation in the following
>     use case:
>       VariableLengthVector v1, v2;
>       v1 = v2; // should fail as well with VC++
>
>
>     Indeed, first SetSize(0, DontShrinkToFit(), DumpOldValue()) is called
>     -> no copy is done, but this->m_Data is left null.
>     Then, std::copy(&v.m_Data[0], &v.m_Data[N], &this->m_Data[0]);
>     Unfortunately, &this->m_Data[0] is left unchanged and null, and VC++
>     will complain :(
>
>
>     This means, either :
>     - we provide an itk::copy() that does not require outIt to be non null
>     when the input range is empty
>     - or we write the loop manually
>     - or we add another test in operator=(Self) -- thing that'll
really like
>     to avoid
>
>     Finally, note as well odd situations in the current implementation
-- my
>     fault I guess.
>     A newly default-constructed VLV will have a null m_Data pointer.
>     However, a VLV constructed with VariableLengthVector<type> v(0) will
>     have a non null m_Data pointer.
>
>     Regards
>     --Luc Hermitte
>
>     Le 26/10/2015 09:03, Luc Hermitte a écrit :
>     > Hi,
>     >
>     > Le 25/10/2015 18:37, Johnson, Hans J a écrit :
>     >> Should we simply add documentation that states:  "Behavior is
>     undefined when length of vector is zero”, add an assertion when
>     compiled in debug mode, and then remove the degenerate case in the
>     test suite?
>     >
>     >
>     > This could be enough regarding Fill(). I'd say it's up to you.
IMO, it
>     > could be simply fixed with an loop or an alternative of fill_n that
>     > states as precondition that "The range [outIt, outIt+n) shall be
>     valid ;
>     > and n shall be >= 0", instead of "The iterator outIt shall be
valid ;
>     > and n >= 0".
>     > This way the end-user won't have to check he doesn't call Fill() on
>     > empty VariableLengthVectors -- it would be considered as a no-op
>     exactly
>     > as "delete nullptr".
>     >
>     > However, we need to be sure that the copy constructor of empty
>     > VariableLengthVector has no side effect.
>     >
>     > Regards,
>     > --Luc Hermitte
>     >
>     >>
>     >>
>     >>
>     >>
>     >>
>     >> On 10/25/15, 8:49 AM, "Luc Hermitte (Code Review)"
>     <review at kitware.com <mailto:review at kitware.com>> wrote:
>     >>
>     >>> Luc Hermitte has posted comments on this change.
>     >>>
>     >>> Change subject: BUG: Make valid calling with m_NumElements == 0
>     >>>
>     ......................................................................
>     >>>
>     >>>
>     >>> Patch Set 2:
>     >>>
>     >>>> You cannot call std::fill_n with a nullptr for Debug VS 2013.
>     >>>>
>     >>>> The implementation of fill_n looks like this:
>     >>>>
>     >>>> template<class _OutIt,
>     >>>> class _Diff,
>     >>>> class _Ty> inline
>     >>>> _OutIt fill_n(_OutIt _Dest, _Diff _Count, const _Ty& _Val)
>     >>>> {  // copy _Val _Count times through [_Dest, ...)
>     >>>> _DEBUG_POINTER(_Dest);
>     >>>> return (_Fill_n(_Dest, _Count, _Val,
>     >>>> _Is_checked(_Dest)));
>     >>>> }
>     >>>>
>     >>>> The _DEBUG_POINTER line is called unconditionally, and will throw
>     >>>> this assert if the pointer is nullptr.
>     >>>
>     >>> That's odd. I don't read such a precondition in the standard.
>     >>> Is it the same with std::copy()?
>     >>>
>     >>>
>     >>>> Why are you against doing a nullptr check or a check on the
number
>     >>>> of elements prior to calling fill_n?
>     >>>>
>     >>>> If you are calling fill_n so frequently that you're concerned
about
>     >>>> adding a micro-smidge of time to each call, perhaps you're
calling
>     >>>> it too frequently...
>     >>>
>     >>> I totally agree that such algorithms are often called to many
>     times. and yet, when they are, they are called on pixels. This means
>     they are sometimes called billion times. We don't need to add a test
>     that we could easily avoid and still stay robust.
>     >>>
>     >>> What we need is a fill_n implementation that have as a
>     precondition: "ptr!=nullptr || size==0", and not "ptr!=nullptr".
>     >>>
>     >>>
>     >>>
>     >>>> If you want the fastest code possible, without doing the
>     >>>> appropriate nullptr safety checks, then you must guarantee
that the
>     >>>> entire test suite never tries to execute a test case with a
>     >>>> nullptr. So another solution would be simply NOT to execute tests
>     >>>> that result in these calls for Debug Microsoft builds.
>     >>>
>     >>> We simply need algorithms with less restrictive preconditions.
>     >>> For instance
>     >>>
>     >>>    // untested code
>     >>>    template <typename OutIt, typename Size, typename T>
>     >>>    OutIt itk::fill_n(OutIt start, Size size, T const& value) {
>     >>>        assert(start ||size == 0); // the test is not correct,
>     just to give an idea of what it should look like
>     >>>        for ( ; size != 0 ; --size, ++start)
>     >>>            *start = value;
>     >>>        return start;
>     >>>    }
>     >>>
>     >>>
>     >>>> It is my contention that **if** there is a performance
problem with
>     >>>> code after simply adding "if (this->m_Data)" checks before
fill and
>     >>>> copy calls, that the performance problem is with the
**callers** of
>     >>>> these things.
>     >>>
>     >>> Somehow I agree. Unfortunately, we tend to call these functions
>     too many times, i.e. once per pixel if not more. We have a lot of
>     pixels.
>     >>>
>     >>> Here it's easy to have a correct code (that'll pass tests with
>     VC++ in Debug Mode) without this redundant branching. Why pay for
>     this branching?
>     >>>
>     >>>
>     >>>> Fill and copy effectively perform N assignment operations. If you
>     >>>> cannot afford a single nullptr check when you are doing N
>     >>>> assignment operations then you should write special case code to
>     >>>> avoid the safety checks.
>     >>>
>     >>> N is often small (< 16)
>     >>>
>     >>>> The rest of us would like to be alerted ASAP when we accidentally
>     >>>> try to "fill" or "copy into" an empty container.
>     >>>
>     >>> We don't need to here.
>     >>> However, if you consider that filling or copying an empty vector
>     is a programming error, then we should document it and formalize the
>     related precondition (assertion, or C++17 [[expect: size != 0]]).