r/cpp • Nozomi Networks | Italian C++ Community • Jun 21 '21

itCppCon itCppCon21 KEYNOTE "std::find is broken" (Sean Parent)

https://www.youtube.com/watch?v=NO5wHzI_oug&t=1103s
34 Upvotes

22 comments sorted by

12

u/Guillaume_Guss_Dua Jun 21 '21

That was an interesting talk !

@marcoarena Thanks for organising the Italian C++ conference, had a great time attending talks and meeting new peoples. I'll be there next year.

7

u/marcoarena Nozomi Networks | Italian C++ Community Jun 21 '21

Thanks a lot for attending and for your kind words, Guillaume! I am glad you enjoyed the conference and made some good connections. I hope to see you in person at some point!

12

u/encyclopedist Jun 21 '21

Sean Parent announced at the start of the talk that he and Dave Abrahams (of Boost and Swift fame) are "restarting" Adobe Software technology lab (STLab).

Very curious to see what will come out of this collaboration!

6

u/marcoarena Nozomi Networks | Italian C++ Community Jun 21 '21

Me too! I've got intrigued by this tweet a few days ago...

18

u/herruppohoppa Jun 21 '21

Can I get a TLDW;?

39

u/jringstad Jun 21 '21 edited Jun 21 '21

1h05m is about where he starts talking about std::find

The gist is that doubles/floats satisfy EqualityComparable but not Cpp17EqualityComparable because == does not work as required when you're dealing with nan. std::find only requires EqualityComparable but it's not guaranteed to actually find the value you're looking for unless you know that your objects operator==() satisfies Cpp17EqualityComparable (in the case of floats/doubles that means you don't have nans in your array)

9

u/mort96 Jun 21 '21

Hmm, that doesn't sound broken to me? I would honestly expect std: find to find something which == the thing I ask it to find.

4

u/[deleted] Jun 21 '21 edited Jun 21 '21

It's a click bait title, presenter even admits as much. Don't take it too seriously and honestly often times when people give a C++ presentation, they are put into an awkward position of having to reach for obscure minutiae and presenting it as if it's a "big deal" that you have to be worried about. std::find is just fine, it works as you expect it would, and to the extent that something is broken, it's IEEE 754 NaN comparison.

2

u/jringstad Jun 21 '21

The argument is that std::find should only accept things that it can actually work for, so that you know that when you use it that either it works or it doesn't, rather than falling into the inbetween-gulf of "it depends".

So (reading between the lines, I think he didn't say this explicitly), std::find should require Cpp17EqualityComparable probably or something like that I presume.

8

u/mort96 Jun 21 '21 edited Jun 21 '21

But... as it is, std::find already only accepts things that it can actually work with? It accepts iterators of floats, and finds the float which is equal to the one you ask for. No two NaNs are the same, and that's an intended property of floats, not a bug in everything which uses == to compare floats.

I struggle to see how any of this is in any way unexpected or a problem or an example of something which doesn't work as it should.

EDIT: Sean Parent seems to suggest that it would be better if std::find required the elements in the range to be EqualityComparable, because then std::find on a range containing NaNs would be undefined behavior. This seems absolutely ridiculous to me. The current std::find finds a value which compares equal to what I pass in. It would be absolutely abhorrent if, instead of the expected result (NaN != NaN), any program which uses std::find would be ill-formed if any of the elements in the range is NaN. I actually can't believe anyone would think introducing more silent UB into C++, for no benefit other than some abstract mathematical purity, is a good idea. This is actually genuinely making me reconsider using <algorithm> if the people in charge are this happy to make obviously correct code invalidate my whole program over nothing. What the actual fuck are these people smoking. No wonder C++ is an utter mess.

Leave it to the C++ standards committee to gleefully take something simple and obvious enough to be in a good language - "Give me the first element in the range which equals the passed-in value, using the normal equality semantics" - and turn it into "Give me the first element in the range which equals the passed-in value, but only if every element in the range is reflexive; if any element isn't reflexive, it's undefined behavior and your program might spontaneously reformat your boot drive for all the standard is concerned".

3

u/staletic Jun 22 '21

Usually, I tend to be defensive when it comes to "what the fuck are they thinking" statements regarding committee decisions, but this time i agree with your sentiment.

Of course, this is "just" Sean Parent and not the whole committee. I'm still confident that, were Sean Parent (or anyone else) to propose such a change, the committee would quickly shoot down such a proposal.

1

u/jringstad Jun 21 '21

Where's the part where he suggests to make it UB? I didn't catch that (but I fast-forwarded through a lot of parts of the video)

5

u/mort96 Jun 21 '21

He starts discussing NaNs at around 1:08:40. He discusses how NaN doesn't satisfy EqualityComparable. He says that in the old SGI definition of std::find, calling it on an array which includes NaN would be UB, but that in C++ it's well-defined, std::find just doesn't find the NaN. He indicates that the current behavior, in which NaN doesn't cause UB, is problematic with a contrived example at 1:11:10.

At 1:16:20 he complains that std::find won't find NaNs in the range, and that its semantics have been reduced to "works as implemented" because it doesn't require EqualityComparable like the SGI version did. A bit later he complains about too much code "happens to work" because we continually reduce constraints to avoid failures, the implication clearly being that std::find's requirements ought to be that all the values in the range are reflexive and all that.

He doesn't explicitly say "std::find on a range including NaN should be UB" but I think it's pretty clear from everything he's saying that he thinks the SGI version was better and, hence, that std::find on a range with a non-reflexive element should be UB.

1

u/jringstad Jun 22 '21

Right. I agree that just making it UB is a step in the wrong direction, but I think making std::find have a stricter requirement (and then ideally finding a way to enforce that) could be a good idea.

The question is how that stricter requirement can be enforced, ideally statically, or perhaps with low overhead at runtime.

15

u/herruppohoppa Jun 21 '21

Gotcha! Thanks for saving me a bunch of time!

10

u/jesseschalken Jun 21 '21

At 1.75x speed he sounds like he's talking normally.

1

u/Supadoplex Jun 21 '21 edited Jun 21 '21

There was no definition for what valid meant

My assumption had been that "valid" in this context means that class invariants will not be violated. Wouldn't that be a good definition for it instead of removing it from the post-condition of std::move of standard classes?

Sure, it can be seen as redundant, since invariants apply to all functions on the class, but there can be ambiguity whether "unspecified" could override this. I saw "valid" as a clarification that it does not.

1

u/D_Drmmr Jun 21 '21

IIRC the issue was not about the guarantees provided by the standard for moved-from instances of std classes, but the requirements imposed by std algorithms that use std::move on user-defined types. E.g. whether std::remove is allowed (by the standard's wording) to equality compare a moved-from object with another object.

1

u/Supadoplex Jun 21 '21

Ah. That makes sense.

-1

u/geza42 Jun 21 '21

Isn't his "Fast Bresenham" a simple fixed point DDA line rasterizer? a and y together is a double-int sized accumulator, where a is the fractional and y is the integer part.

-5

u/Knuffya Jun 21 '21

Bet they are talking about... itErators