Question #1 was misunderstood. This is not about sorting a sorted vector, it is about processing a sorted vector, in general. The example code of the question sums the values. The example code of the answer does `sort(v.begin(), v.end());` in run(). It is obvious that sorting something that is already sorted shouldn't take much effort. Not so that adding all the values together should be faster if the values are sorted.
His answer does include what I would think is the correct reason in that specific case though - branch prediction on the
if(data[c] >= 128)
line. When the array is sorted, you would go from not taken to taken only once and likely get correct predictions nearly 100% of the time versus the shuffled list producing a rate around 50% depending on the predictor.
Also check out the first response for a nice explanation and an optimization to eliminate the branch. The author replaced it with a bit twiddling solution to either store the current element or zero if it is less than 128 in a temporary variable and then always add that to the sum.
The already sorted collection is a classic example for Quicksort's worst-case scenario -- specifically for implementations where the pivot point is the first element.
It's not obviously easy either. You won't know if an arbitrary collection is already sorted unless you check each element.
Interesting things happen on that page when you click on one of the sorts to see it in a bigger window, then you close it, then click it again. You can end up with multiple sorts running at the same time.
std::sort is not required to use any specific algorithm; it only guarantees that it uses an O(N log N) worst-case algorithm (since C++11, before C++11 the guarantee was average-case O(N log N), see https://en.cppreference.com/w/cpp/algorithm/sort).
It is not guaranteed, but all the libraries do. In fact in the past the bound was O(N²) as the expectation was that quick sort would be the default choice, but because all implementations used introsort, the bound was thighened.
QuickSort using middle element or median should perform optimally no?
The middle (median) element in a sorted array has only less elements on the left and greater elements on the right, so the first pass of the quicksort would do nothing and not recurse further.
Introsort, which used by the C++ standard libraries, switches from quicksort to heapsort for the (sub)partition for which has exceeded the expected recursion depth, so it is guaranteed to run in worst case O(nlogn) for all inputs.
edit: which means it does not need a do nothing first pass and takes mitigating actions only in the worst case.
In this case the processing seems to be deciding whether the number in the array is in the top half or bottom half. Branch prediction (assuming some simple heuristic) on that would be wrong once if it's sorted, but half the time when it's not.
It is also vague what "processing" means in this context. Just about everything you do is processing already, so there really shouldn't be a "reason" it is faster to "process" an unsorted or a sorted array. Now if we're given a hint at what the processing is, then we might be able to get further.
As far as I am concerned, Stroustrup's greatest contributions to programmer are these three quotes, all from thre 2nd Edition of The C++ Programming Language:
"The most important single aspect of software development is to be clear about what you are trying to build."
"There are no 'cookbook' methods that can replace intelligence, experience and good taste in design and programming."
"Design and programming are human activities; forget that and all is lost."
So true, so important, and so universally applicable.
I think he also said something along the lines of: don't introduce a class over a struct if you are not trying to maintain an invariant. Very good advice.
My impression is he would have wanted to but he was limited by that era's technology. Quoting from the article:
> If you could go back in time and change one thing about the original implementation of C++, what would it be?
> I don’t have a time machine and I shouldn’t try to second-guess 1983-vintage Bjarne—he knew the conditions at the time better than I do now, and any significant change probably wouldn’t have fitted in the 1MB memory I had to work with, and if it had maybe I wouldn’t have been able to port the compiler to an early 640MB Windows machine.
C++ cannot be greater than C... Because the ++ is post-increment
He created a great language though
--
And agreed on the linking: every snippet on stackoverflow is effectively gpl
Requiring attribution/license change --- Unless you've already hyperlinked every author name, stackoverflow, + the page it came from, AND those links are not nofollow
Note that there is some discussion [1] surrounding this licensing, as the content was orinally under cc by-sa 3.0 and recently (begin September) relicensed to 4.0.
The concern is if Stack Exchange Inc has the right to unilaterally and retroactively relicense the content.
nope, because when you post content on SO, you are transferring ownership of that content to stack overflow. you don't own it anymore, so you can't license it.
> All materials displayed or performed on the public Network, including but not limited to text, graphics, logos, tools, photographs, images, illustrations, software or source code, audio and video, and animations (collectively “Network Content”) (other than Network Content posted by individual “Subscriber Content”) are the property of Stack Overflow and/or third parties and are protected by United States and international copyright laws (“Stack Overflow Content”).
of course, if your answer replicates content from another source that you link to in your answer, that other source still owns the content. so perhaps if you self-publish first and then replicate and link to your original source, you might be able to side-step this and license the original source as you like.
No, this is incorrect. Note "(other than Network Content posted by individual “Subscriber Content”)"; this refers to the stuff that users create and post. See the "Subscriber Content" heading below.
You license the content you create to them:
> any and all content [...] that you provide to the public Network (collectively, “Subscriber Content”) is perpetually and irrevocably licensed to Stack Overflow
You still own the copyright to what you've written.
We would have better questions and answers if the community proposed and voted for questions knowing that they would be answered by Bjarne Stroustrup. Not just picking the most voted questions in Stack Overflow.
Hi, it's Sonny from Codecademy. Super awesome to see that this made it to the front page of HN. Here are a few questions that didn't quite make it to the original Codecademy blog post (written for our learners):
---
What’s your perfect Saturday?
Have a slow breakfast, do a bit of work – maybe writing. Maybe visit the grandchildren. Run a few miles. Eat a good dinner out with friends. Settle in for the evening with a good book.
---
How was the 2019 C++ Standards meeting in Germany?
It was a rather good meeting. The venue was great and we voted out a “Committee Draft” for review by the national standards bodies. There is now a feature freeze.
In February 2020, we’ll have the final vote C++20. It was a lot of work and there were 220 attendees – a new record.
C++ is going to be great!
---
What are some of the C++20 updates that you are especially excited about?
- Modules – to improve code hygiene and significantly speed up compilation.
- Concepts – to simplify generic programming by allowing precise specification of a template’s requirements on its arguments.
- Ranges – to finally be able to write sort(v) rather than sort(v.begin(), v.end()), to get more general sequences, and more flexibility and better error messages through the use of concepts.
- Coroutines – to get simpler and faster generators and pipelines, simplifying asynchronous programming.
- Dates – being able to efficiently and elegantly manipulate calendars; e.g., weekday{August/1/20/2019}==Thursday.
- jthreads and stop tokens – threads that joins on scope exit (doing proper RAII) and a mechanism for terminating them if their result is no longer needed.
These changes – and many smaller ones supporting them – are major in the sense that they will fundamentally change the way we program and think about our designs.
C++20 will be as big an improvement over C++11 as C++11 was over C++98. It will change the way we think about writing our code. I said “C++11 feels like a new language.” I will be able to say the same about C++20.
Our code will become smaller, simpler, run faster, and compile faster.
---
What newer languages or language paradigms are exciting to you?
I don’t easily get excited and the field of languages doesn’t really develop all that fast when you keep an eye on it.
Most changes are incremental and re-emerge repeatedly in different languages with minor differences. I think the word “paradigm” is overused and misused. If it means any more than “my latest bright new idea”, we don’t see a new paradigm every decade. Maybe object-oriented programming, generic programming, functional programming, and machine learning. That took 50+ years.
I tend to look for techniques that can be widely used. Over the last decade or so, my main work has focused on generic programming and compile-time evaluation. Maybe this will feed into a static reflection mechanism for C++ over the next few years. I like the idea of functional-programming-style pattern matching and did a bit of research on that in the previous decade.
Well it's good that he answers C++ stuff, a bit like Walter Bright here (or wherever) answers questions related to D - but the more important question is this:
In the face of more competition, e. g. python, Rust, Go etc.., what is the future of/for C++?
Stroustrup is the beloved creator of C++, but C++ is decidedly not governed by a benevolent dictator; a very large and active Committee guides its future: https://isocpp.org/std/the-committee
I have to say that I have a lot of respect for the man.
Many project leaders/creators position themselve "authoritative god" on their project, and finished often disconnected from their community taking arbitrary wrong decisions.
Bjarne has been smarter than that, giving the community (a very diversified community ) the opportunity to drive the language together.
And it worked, C++ survived 40 years, stronger than ever, evolving from a primitive "C with class" to a modern language present in almost every electronic device nowadays.
It might not be "perfect", "pure", but it does not matter. It fucking work... and evolve in the right direction... That's the C++ way.
In addition to benefiting from many smart people at the helm, instead of just one, it also benefits from having no real single points of failure. It has a multitude of cooperative leaders, support from many large and even small corporations, and many implementations as well as its formal Standard (which after the long wait for C++0x, has had a number of good, well-adopted updates).
All things considered the committee did quite well, but sometimes I think that Bjatne might have abdicated his position too early and the language might have benefited of a strongly opinionated dictator with veto powers for a while longer.
"Eschew flamebait. Don't introduce flamewar topics unless you have something genuinely new to say. Avoid unrelated controversies and generic tangents."
This is a reference to the ongoing uncertainty concerning StackOverflow's (and the rest of StackExchange) new code of conduct (which explicitly considers gender pronouns now). Gender pronouns are at the forefront since a widely respected moderator on the network was de-modded for murky reasons surrounding questions about gender pronouns and the new code of conduct. This decision (and the recent relicensing) has inflamed volunteer mods and those interested in the meta of StackExchange. If you are interested, see [1]. But know that right now, StackOverflow is in damage control and communication has been transferred to their CTO and legal team.
I think as a tongue-in-cheek comment, it sits on about the same ground as the other comments asking why it wasn't closed as a duplicate or as opinion-based.
"Undefined behavior" is a quirk of the C++ ISO standard legalese, not some property of computing or of the C++ language.
Briefly, the C++ standard defined three classes of stuff that isn't covered by the standard:
Implementation-defined behavior - "behavior, for a well-formed program construct and correct data, that depends on the implementation and that each implementation documents".
Unspecified behavior - "behavior, for a well-formed program construct and correct data, that depends on the implementation".
Undefined behavior - "behavior for which this document imposes no requirements".
So 'undefined behavior' is stuff that isn't mandated by the standard and also may or may not be an error.
Some UB stuff is bugs (like accessing arrays out of bounds), some isn't bugs but just processor/OS dependent stuff that is out of scope of the C++ standard. (Like what happens when integers overflow.)
In short, the existence of UB is a good thing; having a standard that clearly states what is part of it and what isn't is vastly better than a standard that mandates too much or is too vague.
(And it goes without saying that having no standard at all, like is usual for other programming languages in 2019, is worse in every way.)
If you were doing software development in the 80es when C++ was born, you wouldn't be asking this question. You'd either choose a language that allows undefined behavior and write a program that completes the work today or a language with all possible runtime checks and a program that completes the work sometime next week.
Sure, and in the 80s maybe it was justified, but in the 30 years since then, that justification has worn thin and IMO the cost of UB far outweighs the benefits. I've been writing software in C++ since the 90s and have been growing gradually more uneasy with it the whole time.
The thing is, by the very nature of UB, it could have been (and still could be) patched out in a backwards-compatible way. At the very least, catching UB before the nasal demons get out would allow a bit more confidence in C++ code.
Undefined behavior is stuff that is incorrect and must not happen (e.g. out of bounds access). Making it explicitly undefined helps writing efficient implementations.
So not only undefined behavior has not hindered the success of C++, it's probably one of the things contributing to its success, in particular its success in developing embedded and safety-critical systems.
If you write a program for which correctness is particularly important (e.g. a safety-critical program), you must ensure, through tests, proofs, magic, etc. that you don't have any incorrect behavior. Which might be undefined, but again the problem is that it's incorrect, not that it's undefined. If you're flying at Mach 2 and an out-of-bounds read or write happens in your flight control software, it doesn't really matter that much whether you get "undefined behavior" (i.e. read or write "random" address), a panic, a log message, a popup window, etc. The safety is compromised by the fact that you did an incorrect operation, not that the operation is undefined.
Now, if you want to write a music player or something like that, it does make sense to use a language like Python, Go, or whatever might give you more guarantees than C++, because realistically you're not going to write a proper test suite for it.
Someone has to write the operating systems and debuggers directly for hardware, including microcontrollers which don't have various cpu facilities/guarantees.
Also check out the first response for a nice explanation and an optimization to eliminate the branch. The author replaced it with a bit twiddling solution to either store the current element or zero if it is less than 128 in a temporary variable and then always add that to the sum.
It's not obviously easy either. You won't know if an arbitrary collection is already sorted unless you check each element.
http://greggman.github.io/doodles/sort.html
The middle (median) element in a sorted array has only less elements on the left and greater elements on the right, so the first pass of the quicksort would do nothing and not recurse further.
Or am I missing something?
Still, probably faster to incorporate a monotonic check in a quicksort first pass, than run a bubble-sort pass which probably won't help much anyway?
edit: which means it does not need a do nothing first pass and takes mitigating actions only in the worst case.
This blog post literally adds nothing.
> port the compiler to an early 640MB Windows machine.
Probably meaning a 640 kB MS-DOS machine - the first C++ 'cfront' tapes were going out by 1986, if memory serves.
"The most important single aspect of software development is to be clear about what you are trying to build."
"There are no 'cookbook' methods that can replace intelligence, experience and good taste in design and programming."
"Design and programming are human activities; forget that and all is lost."
So true, so important, and so universally applicable.
I would argue, however, that more people have used C++ than have used those pieces of advice...
> If you could go back in time and change one thing about the original implementation of C++, what would it be?
> I don’t have a time machine and I shouldn’t try to second-guess 1983-vintage Bjarne—he knew the conditions at the time better than I do now, and any significant change probably wouldn’t have fitted in the 1MB memory I had to work with, and if it had maybe I wouldn’t have been able to port the compiler to an early 640MB Windows machine.
He created a great language though
--
And agreed on the linking: every snippet on stackoverflow is effectively gpl
Requiring attribution/license change --- Unless you've already hyperlinked every author name, stackoverflow, + the page it came from, AND those links are not nofollow
https://stackoverflow.blog/2009/06/25/attribution-required/
""Stack Exchange Inc; user contributions licensed under cc by-sa 4.0 with attribution required.""
EDIT: see cc by-sa text. It considers itself gpl equivalent
The concern is if Stack Exchange Inc has the right to unilaterally and retroactively relicense the content.
[1] https://meta.stackexchange.com/questions/333615/will-concern...
> All materials displayed or performed on the public Network, including but not limited to text, graphics, logos, tools, photographs, images, illustrations, software or source code, audio and video, and animations (collectively “Network Content”) (other than Network Content posted by individual “Subscriber Content”) are the property of Stack Overflow and/or third parties and are protected by United States and international copyright laws (“Stack Overflow Content”).
https://stackoverflow.com/legal/terms-of-service#licensing
of course, if your answer replicates content from another source that you link to in your answer, that other source still owns the content. so perhaps if you self-publish first and then replicate and link to your original source, you might be able to side-step this and license the original source as you like.
You license the content you create to them:
> any and all content [...] that you provide to the public Network (collectively, “Subscriber Content”) is perpetually and irrevocably licensed to Stack Overflow
You still own the copyright to what you've written.
> [...]
> ""Stack Exchange Inc; user contributions licensed under cc by-sa 4.0 with attribution required.""
You literally said it isn't two sentences later!
So your code must become gpl, or something equivalent
Sorry for not being clearer, you are right to question. May I make that prior post explicit?
[1]: https://stackoverflow.com/questions/tagged/language-design?t... [2]: https://cs.stackexchange.com/questions/tagged/language-desig...
Not even Bjarne is safe from interview hell.
---
What’s your perfect Saturday?
Have a slow breakfast, do a bit of work – maybe writing. Maybe visit the grandchildren. Run a few miles. Eat a good dinner out with friends. Settle in for the evening with a good book.
---
How was the 2019 C++ Standards meeting in Germany?
It was a rather good meeting. The venue was great and we voted out a “Committee Draft” for review by the national standards bodies. There is now a feature freeze.
In February 2020, we’ll have the final vote C++20. It was a lot of work and there were 220 attendees – a new record.
C++ is going to be great!
---
What are some of the C++20 updates that you are especially excited about?
- Modules – to improve code hygiene and significantly speed up compilation.
- Concepts – to simplify generic programming by allowing precise specification of a template’s requirements on its arguments.
- Ranges – to finally be able to write sort(v) rather than sort(v.begin(), v.end()), to get more general sequences, and more flexibility and better error messages through the use of concepts.
- Coroutines – to get simpler and faster generators and pipelines, simplifying asynchronous programming.
- Dates – being able to efficiently and elegantly manipulate calendars; e.g., weekday{August/1/20/2019}==Thursday.
- jthreads and stop tokens – threads that joins on scope exit (doing proper RAII) and a mechanism for terminating them if their result is no longer needed.
These changes – and many smaller ones supporting them – are major in the sense that they will fundamentally change the way we program and think about our designs.
C++20 will be as big an improvement over C++11 as C++11 was over C++98. It will change the way we think about writing our code. I said “C++11 feels like a new language.” I will be able to say the same about C++20.
Our code will become smaller, simpler, run faster, and compile faster.
---
What newer languages or language paradigms are exciting to you?
I don’t easily get excited and the field of languages doesn’t really develop all that fast when you keep an eye on it.
Most changes are incremental and re-emerge repeatedly in different languages with minor differences. I think the word “paradigm” is overused and misused. If it means any more than “my latest bright new idea”, we don’t see a new paradigm every decade. Maybe object-oriented programming, generic programming, functional programming, and machine learning. That took 50+ years.
I tend to look for techniques that can be widely used. Over the last decade or so, my main work has focused on generic programming and compile-time evaluation. Maybe this will feed into a static reflection mechanism for C++ over the next few years. I like the idea of functional-programming-style pattern matching and did a bit of research on that in the previous decade.
In the face of more competition, e. g. python, Rust, Go etc.., what is the future of/for C++?
Many project leaders/creators position themselve "authoritative god" on their project, and finished often disconnected from their community taking arbitrary wrong decisions.
Bjarne has been smarter than that, giving the community (a very diversified community ) the opportunity to drive the language together.
And it worked, C++ survived 40 years, stronger than ever, evolving from a primitive "C with class" to a modern language present in almost every electronic device nowadays.
It might not be "perfect", "pure", but it does not matter. It fucking work... and evolve in the right direction... That's the C++ way.
https://news.ycombinator.com/newsguidelines.html
I think as a tongue-in-cheek comment, it sits on about the same ground as the other comments asking why it wasn't closed as a duplicate or as opinion-based.
[1]: https://meta.stackexchange.com/questions/333965/firing-mods-...
Briefly, the C++ standard defined three classes of stuff that isn't covered by the standard:
Implementation-defined behavior - "behavior, for a well-formed program construct and correct data, that depends on the implementation and that each implementation documents".
Unspecified behavior - "behavior, for a well-formed program construct and correct data, that depends on the implementation".
Undefined behavior - "behavior for which this document imposes no requirements".
So 'undefined behavior' is stuff that isn't mandated by the standard and also may or may not be an error.
Some UB stuff is bugs (like accessing arrays out of bounds), some isn't bugs but just processor/OS dependent stuff that is out of scope of the C++ standard. (Like what happens when integers overflow.)
In short, the existence of UB is a good thing; having a standard that clearly states what is part of it and what isn't is vastly better than a standard that mandates too much or is too vague.
(And it goes without saying that having no standard at all, like is usual for other programming languages in 2019, is worse in every way.)
The thing is, by the very nature of UB, it could have been (and still could be) patched out in a backwards-compatible way. At the very least, catching UB before the nasal demons get out would allow a bit more confidence in C++ code.
So not only undefined behavior has not hindered the success of C++, it's probably one of the things contributing to its success, in particular its success in developing embedded and safety-critical systems.
If you write a program for which correctness is particularly important (e.g. a safety-critical program), you must ensure, through tests, proofs, magic, etc. that you don't have any incorrect behavior. Which might be undefined, but again the problem is that it's incorrect, not that it's undefined. If you're flying at Mach 2 and an out-of-bounds read or write happens in your flight control software, it doesn't really matter that much whether you get "undefined behavior" (i.e. read or write "random" address), a panic, a log message, a popup window, etc. The safety is compromised by the fact that you did an incorrect operation, not that the operation is undefined.
Now, if you want to write a music player or something like that, it does make sense to use a language like Python, Go, or whatever might give you more guarantees than C++, because realistically you're not going to write a proper test suite for it.