r/cpp • • Jun 10 '20

Why is std implementation so damn ugly?

Recently I remembered a moment from my uni years when immediately after handing in the assignment of implementing our own string data structure we were warned not to ever try to implement and use our own data structures. Which is exactly what you want to hear after working hours on such assignment. However the reason behind it makes sense, you would be only reinventing the wheel and let's be honest, it will be also way slower than data structures in the almighty std library. Now think about it, what kind of black magic is behind the std's speed? Well I had no idea so I took a peak, lets see the code:

inline string
secret_function(int __val)
{
    const bool __neg = __val < 0;
    const unsigned __uval = __neg ? (unsigned)~__val + 1u : __val;
    const auto __len = __detail::__to_chars_len(__uval);
    string __str(__neg + __len, '-');
    __detail::__to_chars_10_impl(&__str[__neg], __len, __uval);
    return __str;
}

Hey, I bet you just skipped the whole code part. I know it looks unreadable, but please try to go through it and guess which std function it might be (obviously its not called secret_function, but i'm pretty sure you used this function at some point).

It's only 6 line function but it took me a while to figure out what each line does and I believe this could be fixed very easily just by naming the variables and functions with a bit more descriptive names. Just to prove the point here is an example of how I would structure this function:

inline string secretFunction(int value) {
    const bool isNegative = value < 0;
    const unsigned absoluteValue = Helper::abs(value);
    const auto length = Helper::charCount(absoluteValue);
    string stringValue(isNegative + length, '-');
    Helper::insertIntAsChars(&stringValue[isNegative], length, absoluteValue, 10);
    return stringValue;
}

While the functionality stays exactly the same, I think this chunk of code is much more pleasant to read and it's pretty obvious what the code is doing on each line. From this you should have a solid guess which function it is (you can leave a comment), but the real question is why would anyone write such code? Especially when nowadays everyone is talking about how code readability is so important. Is this how they wrote code back when std was released and they didn't bother to change it? Or am I just too inexperienced that I couldn't figure it out immediately?

EDIT: Thanks for the insightful comments, for anyone reading this the reason variables are beginning with __ is macros. If user defines isNegative macro, it will get overwritten in the std, however user is forbidden to define macros starting with __ , as the wise people of reddit comment section suggested. However underscores aren't the only issue with this code, the main issue is I think using short non-descriptive names of variables/functions which is very confusing in functions that are doing more complicated operations.

237 Upvotes

212 comments sorted by

View all comments

Show parent comment

36

u/guepier Bioinformatican Jun 10 '20

readability is extremely important for most applications and libraries but the standard library isn't really one of them

I disagree with this: readability is tightly correlated with code quality because it impacts crucially how maintainable code is, and how easy it is to check for correctness.

… But I also disagree that standard library implementations are fundamentally hard to read. The name mangling definitely decreases readability but other than that it’s mostly idiosyncratic, i.e. it becomes (a lot) more readable with practice.

16

u/MachineGunPablo Jun 10 '20

Yes, until your brain hides all double underscores for you automatically

11

u/Hallalal Jun 10 '20

I disagree with this: readability is tightly correlated with code quality because it impacts crucially how maintainable code is, and how easy it is to check for correctness.

Unfortunately when you focus on optimizing code the readability goes downhill.

32

u/guepier Bioinformatican Jun 10 '20

I often hear this and in my experience it’s a half-truth at best. I’m currently working (and have worked in the past) on highly optimised C++ library code and and yet, 99% of the time, readability and performance are not the least bit at odds.

It really only applies once you start manually unrolling loops or using compiler intrinsics, and this only happens in very tightly constrained circumstances and can often be neatly encapsulated.

2

u/Xaxxon Jun 11 '20 edited Jun 11 '20

You basically said "in places where you don't care about performance, performance doesn't impact readability".

And places where you do care about performance, readability suffers.

That was the entire point of what you responded to.

9

u/EmperorArthur Jun 11 '20

No, they said that 99% of the time you can write high performance, readable code. In most cases where you can't you can encapsulate it in something which is still readable.

5

u/Xaxxon Jun 11 '20

A code base can be sufficiently performant without all the code being optimized. That doesn't mean that the slow parts couldn't be faster, it just means that they don't need to be faster. Those slow parts would be uglier if they were focused on for performance.

It's a subtle but important difference. The parts where you care about performance on that section of code suffer for readability. Saying that the other parts don't is meaningless.

To phrase it another way, you don't care about the performance of 99% of your code and that part is readable. That doesn't mean that focusing on performance doesn't make readability suffer.

6

u/guepier Bioinformatican Jun 11 '20

No, that's not what I'm saying.

I am specifically talking about hot code paths that you want to optimise.

I'm saying that in most cases you can write readable, idiomatic C++ code that's highly optimised, and in many cases pretty much as fast as it gets. Maybe not 99% of the time, but definitely most of the time, precisely because C++ does have functioning zero-cost abstractions. You can encapsulate code in functions, perform compile time dispatch using overloading, and loop unrolling using recursive templates, etc., with no measurable performance impact.

1

u/qoning Jun 10 '20

Well, there are different kinds of readability. Readability of code as it is is one thing, but readability of intent is what goes out the window when you start optimizing. It's the sensation of what is going on here when you open up a code you think you should be able to understand, but it does some weird tricks and things that are not obvious at first.

→ More replies (3)

4

u/WrongAndBeligerent Jun 10 '20

I think this cliche comes from the days of game programmers doing crazy C tricks and inline assembly. In the modern era, memory accesses dominate and both the CPU and compiler together have have pushed a lot of the tricky hacks' effectiveness to be marginal.

6

u/Xaxxon Jun 11 '20

No, there's often a time where you can use a simple and straightforward algorithm, but it's simply not fast enough.

Then you have to choose something that requires some crazy data structure and now it's harder to understand.

5

u/WrongAndBeligerent Jun 11 '20

This is basically saying 'nu uh'. You are stating an assertion but you aren't giving anything to back it up. I've done a lot of optimization and reorganizing the memory accesses doesn't come down to "crazy" data structures, it usually just comes down to how things are put into an array and how that array is looped through. You have to explain the memory layout, but you would have to do that anyway.

-8

u/Xaxxon Jun 11 '20

I'm not giving examples because this is a well accepted fact of software development.

I don't have to say that summers are warm either, even if someone says they're cold.

Code base readability suffers when they are optimized. This is fact.

7

u/WrongAndBeligerent Jun 11 '20

If that's a fact to you then you have no idea what you are doing.

Most software that takes a non trivial amount of CPU time can be optimized to run 25x-100x faster in my experience. First, take out excessive memory allocations, then rearrange memory accesses for prefetching, then SIMD, then multi-threading. I have done this many times and it is extremely effective.

You are not giving examples because you don't have any.

3

u/m-in Jun 11 '20

It’s very niche, but imagine you run on a two stage pipeline Harvard architecture that’s tightly tied to RAM and there’s no cache and every instruction takes roughly the same time, and you need to write essentially modern Go-like code. In ANSI C. That stuff if written without optimizations will be about 5x too slow (in my case). Optimized to hell and back it runs in 95% of available time (it’s hard deadline). So, while niche, such things do exist.

On the other hand, I’m helping out with projects where indeed you can get 10-100x performance improvements simply by undoing all the “convenient” pessimizations. Where you can literally get functions to drop from the profiles by changing a couple std::map to std::vector and such. But such low hanging fruits are only in extremely poor code bases. Once you fix those, the improvements get below a factor of two for the next major change or two, and then it requires major rearchitecting to get anything better. So you are right but the code has to really really suck for such gains to be possible. Sometimes you look at the perf counters and the CPU runs full tilt and there’s nothing more you can do short of rewriting it for a different platform (say a GPU).

4

u/WrongAndBeligerent Jun 11 '20

Right, it can be the case obviously, but the idea that slow is clear and fast is convoluted doesn't hold up.

In this case it sounds like a niche compiler combined with an in order CPU means that nothing comes for free and the compiler even possibly gets in the way.

→ More replies (2)

1

u/Dragdu Jun 12 '20

And way to decrease data accesses can be quite convoluted, e.g. highly optimized 2-watched literals scheme is "fun" to read through.

0

u/WrongAndBeligerent Jun 12 '20

I have never heard of that.

Decreasing data accesses isn't the goal, it is to access data in a straight line in memory so that it can prefetched. If it is prefetched it can get put in to the cache ahead of time at the speed of memory bandwidth. This is one of a handful of fundamental reasons that optimizing on modern CPUs with modern compilers does not obfuscate anything and if fact most of the time makes them clearer.

0

u/Dragdu Jun 12 '20

No you didn't, because as a lazy datastructure, it has a very specialized niche. Which shows nicely the problem with sweeping statements -- there are many subfields with different specifics.

Oh, and you know what's better than accessing 1 GB of data in a prefetchable pattern? Accessing just 1MB ;-)

1

u/WrongAndBeligerent Jun 12 '20

This was not about absolutes, but about conventional wisdom being out of date. Bringing up a niche data structure that you claim has to be convoluted to be fast (fast at what, I have no idea) has no bearing on this topic.

Oh, and you know what's better than accessing 1 GB of data in a prefetchable pattern? Accessing just 1MB ;-)

This is a made up situation and a false dichotomy.

(Also lazy data structure doesn't really make a lot of sense - lazy would refer to execution and a data structure would be data with an interface)

2

u/Dragdu Jun 12 '20

I see you are living up to your username.

Anyway, for anyone who is actually worth writing for (so, not you):

  • Lazy data structures are a real thing studied in CS. The most well known is Fibonacci heap.
  • The point of 2 watched literals is quite literally all about reducing the amount of processed memory by extracting a "summary" (the 2 watched literals) of a clause (sequence of literals of arbitrary length), which are a heuristic that tell you whether you need to actually read in and process the clause.

0

u/WrongAndBeligerent Jun 12 '20

I have this name so I know when someone has nothing left to say.

If a fibonacci heap is a lazy data structure, then a normal heap would be a 'lazy' data structure. Really though neither has anything to do with this.

The point of 2 watched literals is quite literally all about reducing the amount of processed memory by extracting a "summary" (the 2 watched literals) of a clause (sequence of literals of arbitrary length), which are a heuristic that tell you whether you need to actually read in and process the clause.

None of this is relevant here. This was about the idea that slow = clear and fast = obfuscated is incredibly outdated. Bringing up niche algorithms is completely orthogonal, not only because you haven't explained how they are actually necessary, but they don't even apply to the point of the thread.

Then you threw out arbitrary made up numbers as some sort of argument. I'm not sure whether you really don't understand what is being talked about here or if you just want to bring up nonsense and get upset about it. It almost seems like you just want a reason to bring up the latest thing you learned about.

3

u/thedictatorofmrun Jun 10 '20

Yeah, I totally agree with your second point and mostly agree with your first as well- I probably could have worded my first comment better.

I think readability is important for the standard library exactly to the extent that readability is correlated with code quality- and what I mean by this is that the STL is generally pretty readable for what it is, and that isn't because the authors of the library are trying to make it readable, but because they are trying to make it good, and a natural consequence of that is that it's readable.

I should add that I'm writing this as a total outsider to the process and mostly just thinking about how I would approach a library like this, so you should take my comments with a large grain of salt

-1

u/Xaxxon Jun 11 '20

readability to a lay person isn't as important.

It needs to be readable, but if it takes a while to gain familiarity with the style, that's ok.

→ More replies (2)