OSDev.org

nexos wrote:I'm not talking about implementation; I wouldn't make anyone look at that. What I mean is knowing the theory behind sorting.

Also, I would use STL any day instead of writing my own implementation of what it covers, but that doesn't mean a CS student shouldn't understand fundamental algorithms behind sorting, linked lists, memory management, etc. I am learning modern C++ through a course, and this course does it write. It looks at the internals of C++, going as far as explaining disassembly. After showing the C way of doing things, it shows the C++ way and says, "do it this way". It hasn't gotten to STL, but I'm sure a similar approach will be taken there.

Finally, the consensus these days is "modern CPUs are fast enough". That is trap, don't go there. Moore's law is ending, look for yourself! When I use an app, I get appalled at the speed most of the time. The reason? Because of layering. Nowadays, everyone uses Electron (which has a full Chromium installation per app!) or React, when there are much faster alternatives such as Xamarin. People make functions 5 or 10 lines each, and then subordinate to other functions. They create too many variables that aren't needed, make too many layers, depend on scripting languages too much, and who knows what else. The result? Windows XP has a more pleasant experience then Fedora with KDE has!

The fix is for people to understand algorithms, and hand write code where it helps, and then use superior libraries where they help. We need to focus on performance with (but not above or equal to) security, and not say "modern CPUs are fast enough".

Because of the above-mentioned excuse, programmers depend on stuff written by others that they don't understand. They go to Stack Overflow and copy-and-paste oodles of JavaScript, C++, and who-knows what else. And they don't even know that they are writing slow software. Why? Because they were told, "modern CPUs are fast enough".

That course is a pretty neat one; can you point me to it? As for the "modern CPUs are fast enough" one, I was using that in terms of data structures that we use every day (e.g. std::vector) when analysing the speed of data structures and algorithms. I wasn't using that as a general-purpose excuse and I see where your coming from with that.

It's a course on Udemy.com called "Modern C++". It assumes a basic C knowledge, but it still talks about pointers, data types, etc.

Also, I see what your saying about stuff like std::vector. It would obviously be more wise to use that then rolling your own. I just think people should understand arrays amd their advantages and drawbacks before using it, so that they know if it is a good pick or not.

nexos wrote:Also, I see what your saying about stuff like std::vector. It would obviously be more wise to use that then rolling your own. I just think people should understand arrays amd their advantages and drawbacks before using it, so that they know if it is a good pick or not.

Exactly. It's not about knowing the specific implementation of std::vector (which is not unique btw, there are several out there). It's about knowing that std::vector implements a dynamic array. So, you won't expect inserting in the middle of it to be "fast enough" nor you'll expect to use its iterators after disruptive operations like push_back(), because you know that the whole data will be copied to a new place at some point. You won't learn about "invalidation of iterators" after using vectors and hitting weird bugs for quite some time. Knowing DSA it's about knowing when and how to use std::set vs std::unordered_set, std::sort() vs std::stable_sort(), stack vs queue, DFS vs BFS etc. Also, it's about knowing how to compose multiple DSA together to achieve something more powerful that doesn't exist in the STL. Knowing DSA rarely means re-implementing what already exists. Writing software almost always means writing something that does not exist, at least not in a given particular context (language, platform, architecture, licensing model etc.). Also, many DSA do not have a generic implementation (e.g. graphs).

Doctor5555 wrote:As to why you would roll your own lexer, I would mostly do it for speed [...].
For parsing, it is incredibly difficult to write a state machine parser, but a handwritten recursive descent parser is actually not too hard.

I thought recursive descent parsers are no longer common because they become very slow with certain inputs.

Doctor5555 wrote:Hand writing a code generator will 100% generate a massive speed boost in compiling, though.

You're right, but only because your hand-written code generator won't over-optimize. Years ago, I found GCC with a moderate, reasonable set of optimizations to be very fast and it still produced fast code. Optimizations to get that last 1 or 2% of possible performance took 90% of the compilation time. This was back when almost all of the software I wanted to compile was written in C. C++ can be very slow to compile for other reasons entirely. (It was a Linux desktop system with no desktop environment.)

If you want a very fast C compiler which applies reasonable optimizations, and you can accept a few language idiosyncrasies, try KenCC. It supports C89 with extensions covering much of C99, but doesn't support #if. (There is a separate preprocessor which does, but it's slow.) Further speeding compilation, it's typically used with Plan 9 where headers do not have include guards and do not include other headers. Instead, you're expected to include all the necessary headers in the right order. Each manual page gives the necessary list. It also supports #pragma lib so you don't have to separately specify libraries to the linker.

eekee wrote:I thought recursive descent parsers are no longer common because they become very slow with certain inputs.

Well, it turns out that speed is not as important as giving good diagnostic messages. If you make a mistake with a bottom-up parser, it can only tell you it cannot handle the token you have presented, and would rather like one of these (that's why GCC used to give you the message "expected ',', '.', or 'asm' before "whatever"" when you forgot a typedef), whereas a recursive descent parser can tell you you have a malformed statement, because it expected a type name. That sort of thing.

That said, competition is good for business. Since clang started putting an emphasis on good diagnostics, GCC's diagnostics have noticeably improved. Not just with the color and the marking of the error spot, also with the clarity of the message.

Note that I am speaking about novice programmers here. Kernel / library development is somewhat different, but for that very reason, it is not for novices...

nexos wrote:I'm not talking about implementation; I wouldn't make anyone look at that. What I mean is knowing the theory behind sorting.

Also, I would use STL any day instead of writing my own implementation of what it covers, but that doesn't mean a CS student shouldn't understand fundamental algorithms behind sorting, linked lists, memory management, etc. I am learning modern C++ through a course, and this course does it write. It looks at the internals of C++, going as far as explaining disassembly. After showing the C way of doing things, it shows the C++ way and says, "do it this way". It hasn't gotten to STL, but I'm sure a similar approach will be taken there.

And I believe that is a very, VERY BAD WAY of teaching C++. Simply because "the C way" is completely unidiomatic from the C++ point of view, and virtually everything related to "the C way" is very bad practice in C++ code. You are wasting time and energy teaching students something extremely hard and bug-ridden, only to tell them "now forget all about this and do it differently". You make your students think arrays and pointers first, and std::vector and references second. That is bad, it is frustrating for the students, and it is a huge part of why C++ has this reputation of being difficult to learn, when it really, really is not.

You also get your students tripped up in a lot of very basic and mundane things, basically reimplementing the wheel over and over and over at a level they should not be reimplementing things, ever.

Of course students should know what it means when an algorithm has "linear" or "exponential" or "logarithmic" complexity. They should know what a single linked list, a double linked list, a set or a map is. They should know when to choose which. But when asked to implement a list of MyClass objects, they should instinctively think std::forward_list< MyClass >, not constructors that allocate memory and pointer handling. That is simply the wrong abstraction layer.

Same about sorting. I absolutely contradict you here: Teaching how quicksort "works", or worse, going through the rigmarole of bubblesort et al. because that is the way you learned about it is pointless. Teach them about std::sort and its characteristics. Tell them there are others, show them Boost.Sort (every C++ programmer should know to look into Boost first if the standard does not satisfy). Then hammer it into them that, unless they are sure their work on their "own" sorting algorithm would be up to par for inclusion into Boost.Sort, it is not worth doing it.

I don't want novices to implement their own memory management, their own linked list or their own sorting algorithm. I want them to learn about the field they are interested in, and getting results there. Programming is a means to an end. Lots of work has been put into providing aspiring programmers with tools. Let's not spend our time reinventing them over and over again, but to move forwards.

Think of it like civilisation. Sure, you can teach your kids how to make fire with a bow and a stick. That might be a great experience even, if you are into survival as a subject. But on christmas eve, when there's a candle to be lit, I am pretty sure you will show them how a lighter works. (In case it isn't obvious, C is the bow and stick. Or perhaps ASM is the bow and stick, and C is flint and steel. C++ is the lighter. Yes, there is flint and steel in there, but you may as well not bother.)

@Solar, I see what you are saying, but if a programmer can't write memory management code or a quicksort, who's to say they will be able to reason through problems that certainly will crop up in programming. If they don't understand pointers and their perils, or integer overflows, stack overflows, heap overflows, etc, or how sorting works, or all of the "low-level" things, and they use libraries instead, it might make it easier in the short term. Eventually, they will have a problem they can't solve with a library, and they will write ineffeicent . insecure code. All because they learned the easy way...

Remember, easy often leads to suboptimal results.

I can say for myself that knowing C and writing good C programs makes you able to write efficient programs and think on your feet (which is very important as a programmer!). Knowing nothing but STL won't allow that.

Merry Christmas, guys

nexos wrote:...if a programmer can't write memory management code or a quicksort, who's to say they will be able to reason through problems that certainly will crop up in programming.

There is nothing intrinsically "more instructive" in practicing programmer skills on memory management or quicksort implementations than, for example, implementing a graph algorithm using Boost.Graph.

With the difference that the latter is part of what will likely be actually expected of a C++ programmer in the field, while the former very, very much is not, because it is reimplementing the wheel, solving solved problems again.

nexos wrote:If they don't understand pointers and their perils, or integer overflows, stack overflows, heap overflows, etc, or how sorting works, or all of the "low-level" things, and they use libraries instead, it might make it easier in the short term. Eventually, they will have a problem they can't solve with a library, and they will write ineffeicent . insecure code. All because they learned the easy way...

To the contrary. You still haven't understood it: Manual memory management has no place in modern C++. None. Period. It's a leftover, a piece of backward compatibility for when you have to deal with C APIs, and if you think "new" faster than "#include <memory>", "pointer" faster than "reference", then you are a liability in a C++ team, and I hope QA will show you the error of your ways before you break something important.

The basis on which to build is not the C subset of C++. It's not even C++98, that ship has long sailed, left in the dust of the distant past by C++11, which really changed the way we should look at the language. C++17 is really the bare minimum you should accept today, and your training of newcomers should reflect that.

You don't teach C# newcomers C first, either. I hope.

nexos wrote:Remember, easy often leads to suboptimal results.

I have worked with C++ for over 20 years. 95% of all the problems I ever encountered -- and that estimate is very much on the safe side -- were due to people who learned C first, and stopped learning C++ halfway through because they figured they could "make do" with what they already knew. What resulted was a hodgepodge of C constructs sprinkled with some std::string that leaked and broke and was a pain to maintain.

And usually performed pretty poorly when compared to the C++ replacement, too. But even when the C code squeezed a couple of percent out of the platform, that was never worth the burden of resource leaks and unmaintainable spaghetti code.

Trust me, the very best thing that could happen, from a quality perspective, is a C++ programmer who has learned about pointers and "the nitty gritty" only when he was forced to do so by an actual assignment. I would love to see C++ programmers coming out of training who would actually understand that a C array[] and an Object * ptr = new ... and char * are basically big red neon signs saying "error to be found around here".

nexos wrote:I can say for myself that knowing C and writing good C programs makes you able to write efficient programs and think on your feet (which is very important as a programmer!).

Learning any language makes you able to write efficient programs in that language. When you start learning a new language, you might be able to carry over work ethics (like, be disciplined about code structure, make good commits, document your work). But you really have to learn the new language as a new language. C++ is not a superset of C, and has not been since last millennium. It is a language of its very own, with a somewhat unfortunately easy to access backward compatibility layer.

C is not the entry door to C++. It's like crawling in through the sewers and expecting to find your place at the dinner table.


----



PS: Kate Gregory agrees.