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.
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.
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.
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
"Eschew flamebait. Don't introduce flamewar topics unless you have something genuinely new to say. Avoid unrelated controversies and generic tangents."
"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.
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.
[+] [-] cosarara|6 years ago|reply
[+] [-] robmccoll|6 years ago|reply
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.
[+] [-] Igelau|6 years ago|reply
It's not obviously easy either. You won't know if an arbitrary collection is already sorted unless you check each element.
[+] [-] lordnacho|6 years ago|reply
[+] [-] rhacker|6 years ago|reply
[+] [-] jmkni|6 years ago|reply
This blog post literally adds nothing.
[+] [-] dang|6 years ago|reply
[+] [-] ableal|6 years ago|reply
> 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.
[+] [-] MikeTaylor|6 years ago|reply
"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.
[+] [-] AnimalMuppet|6 years ago|reply
I would argue, however, that more people have used C++ than have used those pieces of advice...
[+] [-] jmount|6 years ago|reply
[+] [-] copperx|6 years ago|reply
[+] [-] tsegratis|6 years ago|reply
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
[+] [-] cdirkx|6 years ago|reply
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...
[+] [-] greggman2|6 years ago|reply
[+] [-] gpderetta|6 years ago|reply
> [...]
> ""Stack Exchange Inc; user contributions licensed under cc by-sa 4.0 with attribution required.""
You literally said it isn't two sentences later!
[+] [-] thiagoharry|6 years ago|reply
[+] [-] criddell|6 years ago|reply
[+] [-] ben509|6 years ago|reply
[1]: https://stackoverflow.com/questions/tagged/language-design?t... [2]: https://cs.stackexchange.com/questions/tagged/language-desig...
[+] [-] mansoor_|6 years ago|reply
[+] [-] gpderetta|6 years ago|reply
Not even Bjarne is safe from interview hell.
[+] [-] Ididntdothis|6 years ago|reply
[+] [-] sonnynomnom|6 years ago|reply
---
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.
[+] [-] blt|6 years ago|reply
[+] [-] cryptofits|6 years ago|reply
In the face of more competition, e. g. python, Rust, Go etc.., what is the future of/for C++?
[+] [-] saalweachter|6 years ago|reply
[+] [-] _lbaq|6 years ago|reply
[+] [-] cletus|6 years ago|reply
[+] [-] test1235|6 years ago|reply
[+] [-] JazCE|6 years ago|reply
[deleted]
[+] [-] dang|6 years ago|reply
https://news.ycombinator.com/newsguidelines.html
[+] [-] gizmo385|6 years ago|reply
[+] [-] taneq|6 years ago|reply
[+] [-] otabdeveloper4|6 years ago|reply
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.)
[+] [-] alexeiz|6 years ago|reply
[+] [-] pnako|6 years ago|reply
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.
[+] [-] sixplusone|6 years ago|reply
[+] [-] cjfd|6 years ago|reply
[+] [-] davrosthedalek|6 years ago|reply