Questions about "mismatch"

Hi

I would like to know more about the C++ "mismatch" template function.

(1) If both sequences are empty, what is the result?
(2) If one sequence is shorter than the other, what is the result?

Thanks for any info. I use "The C++ STL" from Plauger/Stepanov
/Lee/Musser but they do not describe any special cases.

The web docs do the same. Are the special cases specified?
Or they are implementation defined?

jacob

On Sat, 2010-12-18, jacob navia wrote:
> Hi
>
> I would like to know more about the C++ "mismatch" template function.
>
> (1) If both sequences are empty, what is the result?
> (2) If one sequence is shorter than the other, what is the result?

Since std::mismatch(A1, A2, B1) only takes three iterators, the second
sequence cannot safely be shorter than the first one -- we don't know
how long it it.

Apart from that, it's well-defined. std::mismatch(A1, A2, B1).second==A2
in both case (1) and (2).

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

Le 18/12/10 16:21, Jorgen Grahn a écrit :
> On Sat, 2010-12-18, jacob navia wrote:
>> Hi
>>
>> I would like to know more about the C++ "mismatch" template function.
>>
>> (1) If both sequences are empty, what is the result?
>> (2) If one sequence is shorter than the other, what is the result?
>
> Since std::mismatch(A1, A2, B1) only takes three iterators, the second
> sequence cannot safely be shorter than the first one -- we don't know
> how long it it.
>
> Apart from that, it's well-defined. std::mismatch(A1, A2, B1).second==A2
> in both case (1) and (2).
>
> /Jorgen
>

Thanks but precisely what do you mean?
If the second sequence *is* shorter, what is the result?

Crash?

Implementation defined?

That is what I wanted to know.

jacob

On Sat, 2010-12-18, jacob navia wrote:
> Le 18/12/10 16:21, Jorgen Grahn a écrit :
>> On Sat, 2010-12-18, jacob navia wrote:
>>> Hi
>>>
>>> I would like to know more about the C++ "mismatch" template function.
>>>
>>> (1) If both sequences are empty, what is the result?
>>> (2) If one sequence is shorter than the other, what is the result?
>>
>> Since std::mismatch(A1, A2, B1) only takes three iterators, the second
>> sequence cannot safely be shorter than the first one -- we don't know
>> how long it it.
>>
>> Apart from that, it's well-defined. std::mismatch(A1, A2, B1).second==A2
>> in both case (1) and (2).
>>
>> /Jorgen
>>
>
> Thanks but precisely what do you mean?
> If the second sequence *is* shorter, what is the result?
>
> Crash?
>
> Implementation defined?
>
> That is what I wanted to know.

You got to know the answer to the other 3/4 of your question, I hope.

For this last case someone else has to answer. For me personally
it's sufficient to know that it's a bug to end up in that situation.
A crash indeed seems like a possibility.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

On 18/12/2010 15:26, jacob navia wrote:
> Le 18/12/10 16:21, Jorgen Grahn a écrit :
>> On Sat, 2010-12-18, jacob navia wrote:
>>> Hi
>>>
>>> I would like to know more about the C++ "mismatch" template function.
>>>
>>> (1) If both sequences are empty, what is the result?
>>> (2) If one sequence is shorter than the other, what is the result?
>>
>> Since std::mismatch(A1, A2, B1) only takes three iterators, the second
>> sequence cannot safely be shorter than the first one -- we don't know
>> how long it it.
>>
>> Apart from that, it's well-defined. std::mismatch(A1, A2, B1).second==A2
>> in both case (1) and (2).
>>
>> /Jorgen
>>
>
> Thanks but precisely what do you mean?
> If the second sequence *is* shorter, what is the result?
>
> Crash?
>
> Implementation defined?
>
> That is what I wanted to know.

Undefined Behaviour.

/Leigh

Le 18/12/10 16:59, Jorgen Grahn a écrit :

> You got to know the answer to the other 3/4 of your question, I hope.
>

No, I do not know C++ very well, that is why I am asking questions here.
I am implementing a container library in plain C. Now, one of the most
important features of my library will be precisely that there is no
"undefined behavior", all behavior will be defined either

(1) As an error, with a defined result: an error code
(2) As a special case where the result is (maybe arbitrarily)
defined as being "X".

In this case I decided that when
the containers are of different length the result is
1+length of shorter container, if there is no difference
before that of course.

> For this last case someone else has to answer. For me personally
> it's sufficient to know that it's a bug to end up in that situation.
> A crash indeed seems like a possibility.
>
> /Jorgen
>

This looks (in my humble opinion) like a badly specified software.

Accepting that errors occur and that software must be able to handle
those errors producing known and similar results at each similar
error is the basis of my specification.

As far as I could read in the book from Plauger and others, nowhere
is explicitely required that the containers should have the same length.

It *can* be deduced but that doesn't give any answer to the question:

And what happens then?

I am surprised at this situation. Looking up in the C++ standard doesn't
help either. This "algorithm" is mentioned in page 635 ("Algorithms
Library") but nowhere is the length of the arguments mentioned. It is
specified at great length that the input iterators should be input
iterators, but there isn't any specification of borderline cases at all.

For instance the type of result in empty containers is not specified
either. This lead me to the question:

is it at all possible to create an input iterator of an empty container?

jacob

Le 18/12/10 17:18, Leigh Johnston a écrit :
> On 18/12/2010 15:26, jacob navia wrote:
>> Le 18/12/10 16:21, Jorgen Grahn a écrit :
>>> On Sat, 2010-12-18, jacob navia wrote:
>>>> Hi
>>>>
>>>> I would like to know more about the C++ "mismatch" template function.
>>>>
>>>> (1) If both sequences are empty, what is the result?
>>>> (2) If one sequence is shorter than the other, what is the result?
>>>
>>> Since std::mismatch(A1, A2, B1) only takes three iterators, the second
>>> sequence cannot safely be shorter than the first one -- we don't know
>>> how long it it.
>>>
>>> Apart from that, it's well-defined. std::mismatch(A1, A2, B1).second==A2
>>> in both case (1) and (2).
>>>
>>> /Jorgen
>>>
>>
>> Thanks but precisely what do you mean?
>> If the second sequence *is* shorter, what is the result?
>>
>> Crash?
>>
>> Implementation defined?
>>
>> That is what I wanted to know.
>
> Undefined Behaviour.
>
> /Leigh

This is quite surprising. Any error leads to a crash, like in assembler

:-)

It could be more sensible to return the index of the first element
of the longer container isn't it?

If container1 has 4 elements, and container2 8, and elements 0-3
are equal in both, the result could be 4 and could be specified as
such, i.e. breaking the comparisons when one of the containers is
exhausted.

I am writing a container library in plain C, and I am trying to know
wat other programming languages offer.

Thanks for your answer.

jacob

On 18/12/2010 16:45, jacob navia wrote:
> Le 18/12/10 17:18, Leigh Johnston a écrit :
>> On 18/12/2010 15:26, jacob navia wrote:
>>> Le 18/12/10 16:21, Jorgen Grahn a écrit :
>>>> On Sat, 2010-12-18, jacob navia wrote:
>>>>> Hi
>>>>>
>>>>> I would like to know more about the C++ "mismatch" template function.
>>>>>
>>>>> (1) If both sequences are empty, what is the result?
>>>>> (2) If one sequence is shorter than the other, what is the result?
>>>>
>>>> Since std::mismatch(A1, A2, B1) only takes three iterators, the second
>>>> sequence cannot safely be shorter than the first one -- we don't know
>>>> how long it it.
>>>>
>>>> Apart from that, it's well-defined. std::mismatch(A1, A2,
>>>> B1).second==A2
>>>> in both case (1) and (2).
>>>>
>>>> /Jorgen
>>>>
>>>
>>> Thanks but precisely what do you mean?
>>> If the second sequence *is* shorter, what is the result?
>>>
>>> Crash?
>>>
>>> Implementation defined?
>>>
>>> That is what I wanted to know.
>>
>> Undefined Behaviour.
>>
>> /Leigh
>
> This is quite surprising. Any error leads to a crash, like in assembler
>
> :-)
>
> It could be more sensible to return the index of the first element
> of the longer container isn't it?
>
> If container1 has 4 elements, and container2 8, and elements 0-3
> are equal in both, the result could be 4 and could be specified as
> such, i.e. breaking the comparisons when one of the containers is
> exhausted.
>
> I am writing a container library in plain C, and I am trying to know
> wat other programming languages offer.
>
> Thanks for your answer.
>

mismatch only takes 3 arguments so it cannot determine the length of the
second input sequence.

/Leigh

jacob navia <jacob@spamsink.net> wrote in
news:ieiofl$b65$1@speranza.aioe.org:

> This is quite surprising. Any error leads to a crash, like in
> assembler

This is the "don't pay for what was not ordered" policy inherited from C.
If one does not like it one should probably consider another language (in
Java I think most of things are defined).

The upside of "undefined behavior" is that the implementation can define it
to do something useful. For bad iterator dereference I believe MSVC++ with
checked iterator support switched on gives you a quite good error message
and aborts the program. This kind of thing is not possible in Java, one
always has the checking overhead and has to handle the resulting errors
inside the same app.

Cheers
Paavo

Le 18/12/10 18:24, Paavo Helde a écrit :
> jacob navia<jacob@spamsink.net> wrote in
> news:ieiofl$b65$1@speranza.aioe.org:
>
>> This is quite surprising. Any error leads to a crash, like in
>> assembler
>
> This is the "don't pay for what was not ordered" policy inherited from C.

Not really. My container library is in C and has always error checking
on. I do not see how an integer comparison would make any difference
really.

> If one does not like it one should probably consider another language (in
> Java I think most of things are defined).
>

I am using "another language": C.

> The upside of "undefined behavior" is that the implementation can define it
> to do something useful. For bad iterator dereference I believe MSVC++ with
> checked iterator support switched on gives you a quite good error message
> and aborts the program.

Sure, but why shouldn't that be a part of the specifications of the
language instead of an optional feature?

In any case it is surprising that the C++ standard doesn't even mention
those errors and their consequences.

> This kind of thing is not possible in Java, one
> always has the checking overhead and has to handle the resulting errors
> inside the same app.
>

In my design, all errors have defined consequences, i.e. if you throw
a NULL pointer (say) you know you will get the error code BADARG...

Of course not EVERY possible error is handled. Some errors like
a bad pointer (not NULL but just pointing to nowhere) can't be
catched. But any algorithmic errors provoke always a defined
outcome.

I suppose this is more of a design philosophy anyway. What is
astounding is that with machines today that are thousands of
times faster than 10 years ago we still keep the same botched
philosophy of not furnishing error analysis and error checking.

The C++ standard feels that is necessary to specify the complexity of
the operations but not any error checking analysis at all.

jacob

On 18/12/2010 17:51, jacob navia wrote:
> Le 18/12/10 18:24, Paavo Helde a écrit :
>> jacob navia<jacob@spamsink.net> wrote in
>> news:ieiofl$b65$1@speranza.aioe.org:
>>
>>> This is quite surprising. Any error leads to a crash, like in
>>> assembler
>>
>> This is the "don't pay for what was not ordered" policy inherited from C.
>
> Not really. My container library is in C and has always error checking
> on. I do not see how an integer comparison would make any difference
> really.
>
>> If one does not like it one should probably consider another language (in
>> Java I think most of things are defined).
>>
>
> I am using "another language": C.
>
>> The upside of "undefined behavior" is that the implementation can
>> define it
>> to do something useful. For bad iterator dereference I believe MSVC++
>> with
>> checked iterator support switched on gives you a quite good error message
>> and aborts the program.
>
> Sure, but why shouldn't that be a part of the specifications of the
> language instead of an optional feature?
>
> In any case it is surprising that the C++ standard doesn't even mention
> those errors and their consequences.
>
>> This kind of thing is not possible in Java, one
>> always has the checking overhead and has to handle the resulting errors
>> inside the same app.
>>
>
> In my design, all errors have defined consequences, i.e. if you throw
> a NULL pointer (say) you know you will get the error code BADARG...
>
> Of course not EVERY possible error is handled. Some errors like
> a bad pointer (not NULL but just pointing to nowhere) can't be
> catched. But any algorithmic errors provoke always a defined
> outcome.
>
> I suppose this is more of a design philosophy anyway. What is
> astounding is that with machines today that are thousands of
> times faster than 10 years ago we still keep the same botched
> philosophy of not furnishing error analysis and error checking.
>
> The C++ standard feels that is necessary to specify the complexity of
> the operations but not any error checking analysis at all.
>

"Don't use what you don't need". Performance can still be an issue even
if CPUs are faster.

/Leigh

jacob navia <jacob@spamsink.net> wrote in
news:ieisa8$lcd$1@speranza.aioe.org:

> Le 18/12/10 18:24, Paavo Helde a écrit :
>> jacob navia<jacob@spamsink.net> wrote in
>> news:ieiofl$b65$1@speranza.aioe.org:
>>
>>> This is quite surprising. Any error leads to a crash, like in
>>> assembler
>>
>> This is the "don't pay for what was not ordered" policy inherited
>> from C.
>
> Not really. My container library is in C and has always error checking
> on. I do not see how an integer comparison would make any difference
> really.

I'm quite sure there is no container library in the C standard. In C you
build everything needed by yourself to your own liking. The same applies
to C++ - but here you have more predefined pieces to play with.

For example, if you want to avoid such undefined behavior when calling
mismatch(), then you can easily write a wrapper function with error-
checking and only use that. Note that it would not be easy to do it vice-
versa: to remove error checking from the standard library function
(presumably in the case it has been proven to be too time-consuming for
your usage case). This is in the spirit of C++: provide building blocks
which one can easily build upon. It is not meant as a final solution for
all problems (that would be 42 ;-)

cheers
Paavo

jacob navia wrote:
> Le 18/12/10 16:59, Jorgen Grahn a écrit :
>
>> You got to know the answer to the other 3/4 of your question, I hope.
>>
>
> No, I do not know C++ very well, that is why I am asking questions here.
> I am implementing a container library in plain C. Now, one of the most
> important features of my library will be precisely that there is no
> "undefined behavior", all behavior will be defined either
>
> (1) As an error, with a defined result: an error code
> (2) As a special case where the result is (maybe arbitrarily)
> defined as being "X".
>
> In this case I decided that when
> the containers are of different length the result is
> 1+length of shorter container, if there is no difference
> before that of course.
>
>> For this last case someone else has to answer. For me personally
>> it's sufficient to know that it's a bug to end up in that situation.
>> A crash indeed seems like a possibility.
>>
>> /Jorgen
>>
>
> This looks (in my humble opinion) like a badly specified software.

I'm not sure what the standard states about mismatch pre-conditions, but
based on its arguments being an input iterator range and a comparable
iterator, it's apparent the sequence pointed to by the comparable
iterator must be at least as large as the input range. In "The C++
Standard Library" by Josuttis (a much more complete reference than the
one you cited, IMO) states on pg358: "The caller must ensure that the
range starting with cmpBeg contains enough elements.

This design minimizes the loop iterator comparisons. When either range
could be the longest, check the range sizes and swap the input range
with the comparison range, and swap the resulting pair of iterators.

When the pre-condition is met, there is no undefined behavior, and the
results for all cases are easily rationalized: if there is no mismatch
result.first == range1 end, result.second == range2 begin + range1 size.
Since range2 size >= range1 size, the result is well defined for all
sizes of range1 and range2.

Jeff

Le 19/12/10 17:44, Jeff Flinn a écrit :
> jacob navia wrote:

>> This looks (in my humble opinion) like a badly specified software.
>
> I'm not sure what the standard states about mismatch pre-conditions,

As far as I can see it says absolutely nothing. See 25.1.7 "Mismatch"
in the n1905 C++ standard document.

> but
> based on its arguments being an input iterator range and a comparable
> iterator, it's apparent the sequence pointed to by the comparable
> iterator must be at least as large as the input range.

Maybe. You can *deduce* that if you want, but it is not SPECIFIED.

> In "The C++
> Standard Library" by Josuttis (a much more complete reference than the
> one you cited, IMO) states on pg358: "The caller must ensure that the
> range starting with cmpBeg contains enough elements.
>

Yes, that is a sensible comment, but even that doesn't specify what
happens when the error arises.

ERROR ANALYSIS is completely missing, period.

That is one of the biggest differences between the library I am writing
and the C++ STL: I try to specify exactly what will happen for each
of the "borderline" conditions. For instance in this case I specified
that the matching search stops when the shorter container is exhausted
and the result is one more than the length of the shorter container.

This follows design principles like:
(1) be forgiving. Programming errors should never lead to a crash but
should be acnowledged by the software and an orderly return code
shoud notify the calling software of the condition.
(2) Error conditions can be converted in features: instead of crashing
when an error occurs, you return a meaningful result.


> This design minimizes the loop iterator comparisons.

At the enormous cost of crashing at the slightest error. You are saving
1 integer comparison and a conditional jump at each iteration, what is
absolutely NOTHING. The cost of a crash is much more serious. This is
exactly the kind of philosophy that produces brittle software that is
always just crashing around.

> When either range
> could be the longest, check the range sizes and swap the input range
> with the comparison range, and swap the resulting pair of iterators.
>
Great. This produces the same result as the specifications I outlined
above.

Why not incorporate those specs into the specification of "Mismatch"?

> When the pre-condition is met, there is no undefined behavior, and the
> results for all cases are easily rationalized: if there is no mismatch
> result.first == range1 end, result.second == range2 begin + range1 size.
> Since range2 size >= range1 size, the result is well defined for all
> sizes of range1 and range2.
> `

Sure, WHEN the preconditions are met. Error analysis investigates what
happens when those preconditions are NOT met, and prescribes a defined
behavior for exceptional circumstances. That is correctly specified
software.

As I said elsewhere the machines running today's software are thousands
of times faster than merely 10 years ago. It is completely ridiculous
to go on trying to take enormous risks for the sake of saving an integer
comparison and a conditional jump, what in today's CPUs counts as a
few cycles at 2GHZ or more.

Why?

Because the mindset of people designing software today is still in the
times when "efficiency" was counted on cycles.

Obviously "Mismatch" will spend millions of cycles in the searech
through a generalized container, comparing each element with another,
fetching both, calling the predicate, retrieving the result,
advancing both iterators, etc.

In THAT context, an integer comparison and a conditional jump are
NOTHING AT ALL.

In any case, in my container library those cases are specified. I am
rewriting the STL in C. Yes, pure C.

I have implemented iterators, containers, abstract containers (what
C++ calls "algorithms"), and many other things like automatic
saving and loading to/from disk, and other goodies that the STL never
even touches.

jacob

jacob

jacob navia wrote:
> Le 19/12/10 17:44, Jeff Flinn a écrit :
>> jacob navia wrote:
>
>>> This looks (in my humble opinion) like a badly specified software.
>>
>> I'm not sure what the standard states about mismatch pre-conditions,
>
> As far as I can see it says absolutely nothing. See 25.1.7 "Mismatch"
> in the n1905 C++ standard document.
>
>> but
>> based on its arguments being an input iterator range and a comparable
>> iterator, it's apparent the sequence pointed to by the comparable
>> iterator must be at least as large as the input range.
>
> Maybe. You can *deduce* that if you want, but it is not SPECIFIED.
>
>> In "The C++
>> Standard Library" by Josuttis (a much more complete reference than the
>> one you cited, IMO) states on pg358: "The caller must ensure that the
>> range starting with cmpBeg contains enough elements.
>>
>
> Yes, that is a sensible comment, but even that doesn't specify what
> happens when the error arises.
>
> ERROR ANALYSIS is completely missing, period.
>
> That is one of the biggest differences between the library I am writing
> and the C++ STL: I try to specify exactly what will happen for each
> of the "borderline" conditions. For instance in this case I specified
> that the matching search stops when the shorter container is exhausted
> and the result is one more than the length of the shorter container.
>
> This follows design principles like:
> (1) be forgiving. Programming errors should never lead to a crash but
> should be acnowledged by the software and an orderly return code
> shoud notify the calling software of the condition.
> (2) Error conditions can be converted in features: instead of crashing
> when an error occurs, you return a meaningful result.
>
>
>> This design minimizes the loop iterator comparisons.
>
> At the enormous cost of crashing at the slightest error. You are saving
> 1 integer comparison and a conditional jump at each iteration, what is
> absolutely NOTHING. The cost of a crash is much more serious. This is
> exactly the kind of philosophy that produces brittle software that is
> always just crashing around.
>
>> When either range
>> could be the longest, check the range sizes and swap the input range
>> with the comparison range, and swap the resulting pair of iterators.
>>
> Great. This produces the same result as the specifications I outlined
> above.
>
> Why not incorporate those specs into the specification of "Mismatch"?

Because, if the ranges I'm checking are already known to be of the
proper sizes, I can directly call mismatch without paying the cost of
the size check and swap code.

>> When the pre-condition is met, there is no undefined behavior, and the
>> results for all cases are easily rationalized: if there is no mismatch
>> result.first == range1 end, result.second == range2 begin + range1 size.
>> Since range2 size >= range1 size, the result is well defined for all
>> sizes of range1 and range2.
>> `
>
> Sure, WHEN the preconditions are met. Error analysis investigates what
> happens when those preconditions are NOT met, and prescribes a defined
> behavior for exceptional circumstances. That is correctly specified
> software.

And when they are not met my unit tests will inform me, by (debug)
iterators asserting when incremented or derefed.

> As I said elsewhere the machines running today's software are thousands
> of times faster than merely 10 years ago. It is completely ridiculous
> to go on trying to take enormous risks for the sake of saving an integer
> comparison and a conditional jump, what in today's CPUs counts as a
> few cycles at 2GHZ or more.
>
> Why?

Because profiling tells me it's important to meet my users requirements.

> Because the mindset of people designing software today is still in the
> times when "efficiency" was counted on cycles.
>
> Obviously "Mismatch" will spend millions of cycles in the searech
> through a generalized container, comparing each element with another,
> fetching both, calling the predicate, retrieving the result,
> advancing both iterators, etc.

Because in my case that extra compare kept the compiler from unrolling
the loop, leading to a 20% overall reduction in performance.

> In THAT context, an integer comparison and a conditional jump are
> NOTHING AT ALL.

That is totally context dependent with today's compilers/linkers.

Jeff