Hacker News Reader

Comment by Ygg2 | Hacker News Reader

As someone coming from Java, why is pop_back undefined behavior?

An error or noop is something I expect, but undefined behavior?

It's C++. Its goal is speed over all else. So it tries to carve out space for where the optimizer can assume lots of things are true. Since they don't use anything like Hoare logic they have to get their assertions from somewhere else, inferring them as follows (among other things):

Undefined behavior just means that the specification does not say what will happen--so you can't rely on it as a user.

The upside is that the compiler (and the compiler writers) can assume that places where the undefined behavior would occur in your program cannot be reached in practice--and thus optimize your program better.

STL, which these containers are part of, is famously speed-optimized. STL (like C++) was designed for speed first (if at all possible then zero-cost abstractions) and thus does very little error checking on its own.

Also, C++ is compiled ahead of time--so whatever optimizations it wants to make it has to do BEFORE it starts the program. That means it cannot adapt to the concrete runtime circumstances on the fly (like Java can) and so they have to keep even the worst case runtime down in everything they do.

If they did check whether the thing is empty beforehand then that would cause a slowdown (at least that's the idea--better measure it), mostly because now there would be a branch in the first place. Hence they avoid doing that.

Yet we get stuff like std::regex, the speeding train of regular expression parser engines.

My theory is the compiler maintainers don't themselves use 90% of the language features they implement. So they can't begin to care how well they work for people writing other types of software.

> STL, which these containers are part of, is famously speed-optimized. STL (like C++) was designed for speed first (if at all possible then zero-cost abstractions) and thus does very little error checking on its own.

Only kinda? A bunch of the containers then make other promises or leak details that prohibit meaningful optimizations. An extra branch in std::vector::pop_back() is such a pointless savings compared to, say, that std::map is basically mandatory red-black tree or that std::unordered_map must store elements in a linked list to preserver iterators across removals.

Like almost none of the containers in the STL are "fast" at this point. std::vector is probably about the best, but even it is missing small-size optimizations (and that's ignoring the hair-brained bool specialization that then breaks everything)

I had once assumed std::unordered_map was from the original Standard Template Library (which pre-dates C++ standardization), but turns out (I was told in a r/cpp thread) it's more modern. In 1998 std::unordered_map would have been an excusable design mistake, domain experts knew in 1998 that's a sub-optimal design for this dict / hashmap structure - but you could suppose perhaps they were not on the committee. In 2011 it's not an excusable mistake, better structures are widely known in academic and in industry - it was an unforced error.

The more closely I look at it, the more I'm convinced that unsafety wasn't an inadvertent and undesirable consequence of a "must go fast" mindset in standard C++, unsafety was the whole point. It makes me think about that speech by Susan Sarandon's Rick & Morty character, Dr Wong.

Dr Wong: "I have no doubt that you would be bored senseless by therapy, the same way I'm bored when I brush my teeth and wipe my ass, because the thing about repairing, maintaining, and cleaning is; it's not an adventure. There's no way to do it so wrong you might die."

Software Engineering is an engineering discipline, it is not supposed to be an adventure. Programming C++ is an adventure, you can do it so wrong you might die. We should stop paying people to go on an adventure, let them do that exclusively on their free time if they want.

hash_map was indeed part of the original STL, but was not standardized in C++98. It was still widely available, in slightly incompatible forms, as an extension. In C++11 it was standardized with only minor changes (and renamed).

The address-preserving property, which precludes an optimal implementation, was considered important to be a near drop-in replacement of std::map.

Java is memory safe, at a runtime cost (sometimes that cost is trivial, sometimes it isn't). It will insert a check every time you do a pop.

C++ is not. It's a precondition of calling pop_back() that the vector is not empty. It will not insert a runtime check - it leaves you to decide whether one is needed.

Your C++ toolchain will probably have an option to make (usually debug) builds check and complain if you actually call pop_back() on an empty vector.

So is Rust, and never did I hear a peep about `pop` is too slow better call unsafe.

I suppose it causes an integer underflow and tryies to in-place destruct in an empty buffer?

The std::vector class is somewhat inconsistent about safety and maps a lot of it's operations directly to unsafe, raw array access. The C++ STL contains a lot of historical baggage and design inconsistencies.

For instance, while std::vector has an `at(index)` method, that does proper bounds checking and throws an exception if the index is out of range, it also has an overloaded `operator []` that mimics array syntax that will happily write out of bounds, trashing the heap.

STL was designed to have no overhead over the corresponding C code. If push_back (and all other functions) had an extra check even when it was guaranteed non-empty by construction, it would have been a non-starter for many users.

Consider that it took many years for compilers to reach the near zero overhead for STL as it is, removing precondition checks would have been beyond the ability of many compilers 20 years ago, and it still challenging today.

Of course the actual overhead went down since and today we expect code to be more robust by default, but the original design principles were different. If you want safety by default, check your compiler documentation and compile with lightweight assertions enabled even in release builds.

This makes sense for std::vector::operator[], but not for pop_back and push_back - as those don't have any equivalent for a C array. Instead, it's just another example of C++ optimizing for speed as opposed to correctness.

The equivalent C code is what you would write inline to do a pop_back on an array. You can't write a fast pop_back for std::vector if it didn't provide one by default as the fields you would need to manipulate are private.

And yes, it is indeed an instance of C++ optimizing for speed, which is exactly what I said.

std::vector exposes the exact same API as a C array, in terms of being able to write an external pop_back() function, since C arrays only expose the ability to access a particular element - no more, no less (and std::vector::resize() can be used instead of realloc() if that is desired).

The equivalent of of std vector is an array+size+capacity field. pop_back would litterally be capacity--. resize has overhead as it needs to handle resize up as well as down.

Sure, and I'm saying in C you could write:

  struct stack {
    int[] elems;
    int len, cap;
  };

  int pop_back(struct stack *x) {
    elem = x->elems[x->len - 1];
    x->len--;
    return elem;
  }

while in C++ you could have written:

  struct stack {
    std::vector elems;
    int len, cap;
  };

  int pop_back(stack& x) {
    elem = x[x.len - 1];
    x.len--;
    return elem;
  }

If you wanted C-style speed, with no safety.

that is not valid c. and in valid c++ (which this isn't) you would not need those two integer values.

There are some minor syntax errors - I should have written `int *elems` instead of `int[] elems`, and I forgot to declare `int elem` instead. Apart from these nitpicks, it's completely valid C.

As for C++, the <int> is missing on the std::vector, the elem variable is again not declared, and instead of x[...] it should have been x.elems[...]. Otherwise working valid C++. And yes, the `cap` is not really required, we could use x.elems.size() instead.

> pop_back would litterally be capacity--.

Minor nit: I think you meant 'size--'

ouch, yes of course

I had more bugs pop up from people calling front() on an empty vector than from direct out of range bounds. I guess people are more cautious when they are manipulating indices than when calling a method that takes 0 arguments?

Debug asserts are nice, but not sufficient when the code path causing the empty vec is only encountered by a production user from a different country at 2am. Enabling the asserts in release mode will at least prevent undefined behaviour and malevolent users from harming the system, but the best interface is the one that returns an optional, so as to make the "vector was empty" case explicit. That way it has a higher chance to be considered by the authors of the code or their reviewers.

Well, front() returns a reference. std::optional can't hold references. The closest you get is a plain pointer, with a null pointer for an empty container.

Other languages allow to return `Option<&T>`. That's what I'm using these days.

I suppose a raw ptr is what I would use on C++ to model that case though, yes.

Yeah, for some reason `std::optional<T&>` is cursed and can't get through standardization. People can't decide what should happen on assignment.

I guess a raw pointer is good enough an approximation in that case, it is just annoying that suddenly you can no longer use an optional because your type is a reference

pop_back on an empty container is a programmer error.

A pop_back defined as noop would only leave the program in a slightly more defined state, but quite likely you can't really reason about the behavior of the program after. And implementations would not be allowed to diagnose the erroneous pop_back at runtime.

IMO if pop_back had a defined behavior, it should be immediate termination of the program, with a diagnostic message. The standard does this for some erroneous behaviors, like failing to join or detach a thread before destruction, failing to catch an exception in various contexts or throwing an exception during stack unwinding.

Undefined behavior already allows the behavior of terminating the program with a diagnostic message, and some implementation provide options to have this behavior. It might not be very discoverable though, which is a pity. It would be nice if some higher level build tools provided easier options for "fortifying" C and C++ code, but I doubt that there are options that uniformly apply across compilers and standard library implementations.

Because unlike Java, which is designed to bore you to death, C++ is designed to gaslight you into madness.

I don't really see how one could make it a real no-op, and an error would imply that pop_back would look like

    if(empty()) { /* some error handling mechanism */ }
    ... rest of the code ...

and every added branch adds some minimal but non zero cost

However really often this is a case you actually care about, and so if you don't capture it in pop you end up asking a predicate. I have a whole bunch of Rust code that does:

  while let Some(thing) = container.pop() { /* ... */ }

There is indeed a branch, that pop function might return None - but when it does our while loop exits, the container is empty and we're done. My guess is that the idiomatic C++ here checks !empty() for the loop and then calls pop() on the container if it's not empty so in these cases we're doing the same work except we made it more error prone.

It presumably allows the implementation to be a tiny bit faster, by avoiding a compare and branch for the empty case.

typically, c++ library functions do not use a possibly expensive check if the caller could have performed it themselves, should they have wished to. in this case, the caller could have tested if the container was empty before calling the function.

Because in c++ we assume the programmer doesn't make logic mistakes, and optimize for speed instead. A novice programmer can add assert() as needed.

To use a car analogy - We removed seatbelts to go faster, just don't make mistakes while driving.

I'm not a novice programmer (close to 15 year in total) and I still make mistakes.

¯\_(ツ)_/¯ Maybe I'm just stupid

Reply on news.ycombinator.com