The overhead of abstraction in C/C++ vs. Python/Ruby
blog.reverberate.org
blog.reverberate.org
Yes, but I am working in a situation where performance is an issue. So yes, the observation is relevant to the task at hand.
(Note that with this "benchmark", PyPy has (almost) no difference in runtime between the abstracted and non-abstracted versions.)
The power of Python or Ruby is not demonstrated doing a for loop, is with something like this:
print sum(int(n) for n in open('/a/file/with/numbers'))
We don't need to care about a lot of stuff that we would in C/C++ (memory management, iterate through a file, the format of stuff, terminating the loop properly)
Are C/C++ interesting languages? Of course, sometimes you need that extra level of control about what's going on.
But I don't agree that the cost of abstraction is higher in Python/Ruby. You can create code that does A LOT in a few lines, that most of the times will have a good enough speed.
In C/C++ you need a lot of work to create a good abstraction, that's not guaranteed to perform well.
using namespace folly::gen;
byLine('/a/file/with/numbers') | eachTo<int> | sum;
#include <fstream>
#include <iterator>
#include <numeric>
using namespace std;
int main() {
ifstream nf ("numbers.txt");
return accumulate (istream_iterator<int>(nf), istream_iterator<int>(), 0);
}Simple examples make for good blog articles. Real abstractions follow the same pattern as simple ones.
> The power of Python or Ruby is not demonstrated doing a for loop, is with something like this: print sum(int(n) for n in open('/a/file/with/numbers'))
In this case, your abstraction is sum(). Internally, sum() will use something like a for loop in its implementation. sum() is fast because it's implemented in C, not Python.
The point is that, with many interpreted language compilers, you doubly lose out: the primitive logical steps (in the author's example, function calls) are slower, and they aren't optimized away like they are in C.
I think that's a valid point, because it limits code reuse. As you build up vast libraries and frameworks, the trivial indirections build up and it slows everything to a crawl.
I think you missed the author's point - you may want to re-read the blog's first two paragraphs.
Observe what happens when you make a method virtual, for example.
This is not true. Sweeping general statements like this are almost never true. It is really problem dependent whether a particular type of abstraction is 'too expensive' or not.
I have to actively avoid vtbl lookups in my domain, and this is because if I don't I lose about 15% in execute time. You might think 15% "isn't very long", but it is when your application uses several thousand MPI processes.
Can you paste a representative snippet of your code that demonstrates this 15% penalty?
In my experience with tight loops executing a million iterations, the extra indirection of a vtable lookup is never more than 1% slower. Others also observe similar minor differences.[1]
This paper is old, but measures the direct cost of virtual table lookups (not taking into account indirect costs arising from the inability to inline) as 5% in real C++ programs. When they converted the C++ programs to use all virtual functions, the overhead rose to 13.7%: http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf
The stackoverflow observation and mine were on more modern cpus. Maybe that has something to do with the conflicting anecdotes.
If someone has a small snippet of code that shows non-inlined function calls running 15% faster than vtable calls, I'd like to study it.
[1]the context in grandparent post was already constrained to (non-inlined) normal function calls: ", but nowadays their cost over a normal function call is basically negligible." https://news.ycombinator.com/item?id=8476208
Then you are fighting a strawman. The decision to use virtuals or not has to be taken in the context of all the benfits, and inlining is a prominent one among them. Another is vectorization. Inlining a single function sometimes trigger an avalanche of other optimizations, so the cost of using virtuals can be quite high in such scenarios. It is a n unrepresentative to rule out some of the main motivators for choosing non virtual over virtual.
In my experience people who harp on the line that virtual functions are free, are those who do not write number crunching code, where the benefits are most apparent.
That said, vtable is really a neat performance optimization that targets runtime polymorphism. The problem lies in the fact that many people believe that runtime polymorphism is the only path to polymorphism. Java programmers certainly believe so, for a reason of course. Many uses of runtime polymorphism can be replaced by compile time polymorphism without any loss in flexibility, and frequent gains in performance. In many parts of code I know for certain that the types wont change, and in such cases runtime polymorphism is un-necessary. Many a game engine, array processing code has been written with zero or very sparse use of that feature.
There is this raging debate about whether C++ / D functions should default to virtuals, just like in Java. I certainly am in the camp that believes that they should not because runtime polymorphism is not as uniform a necessity as it is made out to be, as long as the language offers compile time polymorphism. Java is out of luck here, its designers did not include compile time polymorphism features or syntactic sugars (if I am not mistaken) but for C++ and D their defaults make sense.
@Jasode Indeed and in fact I had upvoted your comment even before writing my comment above.
Agree that the decision to use vtable must consider all the disadvantages including loss of inlining. The previous poster also already mentioned that as well.
My question about comparison was not about the decision of yes-or-no to virtual calls. It was about understanding the 15% penalty of vtable calls compared to normal non-inlined calls. If someone had a snippet of code showing that large of a penalty on a modern cpu, I thought it would be interesting to disassemble the compiler's output and study it.
When the previous poster (coherentpony) was complaining about 15%, I thought he was specifically talking about normal function calls because the poster he was responding to was restricting the word "negligible" to normal function calls. My questions were a continuation of that narrow and focused benchmark.
Yes, I think most people understand vtables are not "free". They have a cost. When Alexander Stepanov introduced the STL in the 1990s, one of the factors leading to fast adoption was that it used templates with extensive inlining and the performance blew away the previous attempts of algorithms+containers designed with inheritance & vtables. Heck, a C++ std::sort() could be even faster than C qsort().
Hope that clears up what my curiosity was about.
But since I wrote that, compilers have gotten too smart. When I tried it just now, the compiler devirtualized the function call (which I verified by reading the assembly language output).
I should mention though, the the inability to inline virtual functions is part of what makes them less efficient in some cases. Isolating the inlining factor removes one of the benefits that makes non-virtual functions perform better.
Putting some functionality into an object is not as interesting as running that functionality as a monadic command.
Would be more interesting to run some benchmarks in Haskell using functional abstractions rather than OO machinery.
One needs to measure the program doing the real work. And in this case for the C program you might find that bash forking is the actual cost not the C code running through the loop.
JRuby and PyPy are starting to do things with their specialisation tricks that mean that the overhead of abstraction is 1000 loops before it goes away.
A performance benchmark running for less than a few minutes is a joke. Startup variance alone will dominate the results.
That's not what I compared. Maybe you should read the article again?
> And in this case for the C program you might find that bash forking is the actual cost not the C code running through the loop.
I didn't publish any benchmark numbers of any C programs, because I didn't need to: the two C++ programs I was comparing compiled to exactly the same machine code, making empirical observations of their execution time immaterial.
First, I really don't like the angle taken, then the question of abstraction (why we do it, how) and choices made by languages designers (and variations in their idioms) are so vast that you really can't treat the question through a <1000 signs blog post.
Some quick points:
- You don't code for the machine, you code to be read by another human (possibly you) in the future. I insist, you will be read regularly and frequently. Thus, your code needs to be clear, precise, and concise. This must be the first thing in mind when coding: program what need to be done in a way that a fellow stranger could understand.
- Abstraction is a way to keep a structure of code clear when the interactions become complex and/or abundant. If you can avoid them when still being crystal clear in your code, do it. Direct speaking is always better than convolution.
- The main requirements when you code are often one or two of: quick to develop, easy to maintain, extensible, efficient (you control your big-O and _WORST_ exec times), correct (no bug. at. all.), real time (when X happens, Y is done between n µs and m µs during p ns)
- So, know when performance is a goal, and know when it's not. Choose your language, your techs, your team considering these goals.
- And yeah, C89, C99 and the C++es have a very high overhead of abstraction: clarity, concision, and sometimes performance (all abstractions can't be inlined). Think of it.
I was speaking of a specific context in which I was working (writing C or C++ extensions for Python and Ruby), and addressing a specific design question (how much of the library should be in C or C++ vs. Python or Ruby). I guess I didn't specifically say this, but I thought I made it pretty obvious that I'm working in a situation where performance is a factor.
My observations were also specific to the question of the relative cost of creating layering abstractions in Python/Ruby vs. C/C++.
> And yeah, C89, C99 and the C++es have a very high overhead of abstraction: clarity, concision
Now you're just being silly.
Abstractions are sometimes good, making things clearer and more concise. The wrong abstractions can make code less clear and concise.
Here is my solution to that problem: if an abstraction is not making your code clearer and more concise, don't use it. Saying that abstractions in C and C++ are inherently less clear and concise just shows anti-C/C++ bias.
This is one of those sayings (along with the one on "premature optimisation") that I believe has caused huge amounts of resource wastage over the years, and made much software orders of magnitude more inefficient that it could be. Only the exponential growth in hardware performance has hidden that waste, but that is (fortunately?) coming to an end.
Despite humans writing it, code does not exist mainly to be read by humans. It exists to be executed by a machine, to solve a real problem for its users. Your users do not care about your source code. They want a small, fast and efficient application that does what they want. The majority of useful code is executed far more than it's read or written.
program what need to be done in a way that a fellow stranger could understand
This is vague. I agree with you that writing purposely obtuse code for no other reason isn't a good idea, but you should also be exploiting all the power your programming language has to offer when it can make your code simpler and more efficient. I believe that if someone else using the same programming language cannot understand your code, then they should improve themselves so they can.
See also: http://www.linusakesson.net/programming/kernighans-lever/
Given that the cost for a developer is roughly constant while computation time gets cheaper, this means that nowadays it's best to write code that is quick to modify and thus cheap to modify. The way to do this is to make the code easy to read.
(There are exceptions where you end up writing difficult Fortran code on a supercomputer, but usually "You don't code for the machine, you code to be read by another human (possibly you) in the future." is a good rule of thumb for efficiency.)
I have an old laptop which 8 years ago worked just fine, and is now being more and more useless; not because it is degrading, rather because programs are degrading around it. It's like the world is devolving in an effort to churn out as much crap as possible.
When I open multiple programs which ought to be simple and things start to lag out, I feel a bit disrespected by developers which to avoid any kind of effort took it out on me cutting out what I could potentially do.
This is like the new 'premature optimization is the root of all evil'. Mindlessly repeated without considering any context.