Accidentally quadratic: When Python is faster than C++
arxiv.org
arxiv.org
I had something like a set<string> or a set<set<string>> (or map... I can't remember which) somewhere in my program a few years ago, and I was trying to improve the program's performance. I tried breaking into it several times and found it quite perplexing that the bottleneck appeared to be the set<> container. I mean, I get that cache locality and all has an effect, but it seemed to be having a little too much of an effect. Why did I find this odd? Because other languages (like C#) have tree-based sets and maps too, but I'd never felt they were quite as slow as I was seeing them in C++. So I felt something weird must be going on.
I tried to step through the program for a while and observe what's going on, and at some point, I realized (perhaps I hit the same breakpoint twice? I don't recall) that these functions were being called more often than I intuitively thought would be necessary. Which was obvious in hindsight, as less() needs to be called multiple times on the same objects (4 times at level 2). Now, this hadn't resulted in quadratic behavior, but that was only because my data structures weren't arbitrarily deep—the slowdown was nevertheless a significant constant factor at the core of my program, only linear because the data structure's depth was bounded.
So once I had realized the implications of this, including that constant-factor differences can actually turn into polynomial ones, I eventually decided to post an article about it on arXiv... hence this article. Aside from the complexity issue illustrated in the article, one of my (unexpected) higher-level takeaways was that you can't just take any utility function in a program and blindly put it into a library: even if it's correct, you probably have hidden assumptions about its use cases that won't hold true in general. You really need to think about how it could be used in ways you didn't initially expect, and this may well require a different kind of code review with an entirely different mindset than before. It really drove home the point for me that writing a library is quite a bit different (and in some ways more difficult) than writing an application.
It's possible there is more theory lying underneath this that I haven't touched on—it would be interesting if someone can take this and find more interesting consequences of it. For example, maybe when analyzing algorithms we need to consider something akin to a "recursive time complexity", too? Is there another useful notion of complexity that we can generalize here?
Anyway, hope people enjoy reading it and take something useful away from it. :)
The first one is lt2 and lt3 implementations. You are implementing cmp2 through lt2, but lt3 through cmp3 (is this omission?). Both of them are stack-sensitive. Without being too harsh, I'm getting the impression that the intention was to write the most horrible comparison possible, which is different than worst-case time complexity.
In the paper, lt2 (actually cmp2 in the paper) will always be at least two passes, and lt3 is at least one pass. I would not say they are two/single pass algorithms because complexity increases depending on list depth when lists are involved.
Maybe I'm wrong, but both Python and C++ comparison operators are designed to be general-purpose comparison functions (and I'm more sure about C++, because this was touted through hundreds of books). As such, they should be good enough for most average cases. If you want speed, you go with balanced trees or something funkier.
Also, for C++ Tree implementation, you are again using probably the worst approach - appending to vector recursively. Use list for this. Python list implements all sorts of tricks, comparing to C++ vector.
And the last thing, but not the least: C++ containers depend on implementation (gcc libstdc++, stlport, msvc whatever), and I've seen substantial speed differences in standard operations. Hell, my old (almost conforming) list implementation was much faster than libstdc++ implementation because it wasn't trying to be too clever with slices and other magic.
I'm sad you haven't used a more scientific approach with much more rigor here: what C++ compiler was used, what version, what assembly output was produced, on what processor, after how many runs, etc... Claiming "Python is faster than C++" sounds like a clickbait title.
The context to keep in mind when reading the paper is: When designing a programming language & its standard library (or any API), we need to define an interface we can use as a building block, and we're analyzing the consequences of our choice of building blocks. In particular, we first examine the case of comparison-based data structures, which requires defining ordering primitives. In C++, the primitive is the < operator. In Python 2, it's cmp(). (In Python 3, it's a mix of < and ==, whose implications I discuss as well.) We assume user-provided types implement that basic interface, and we implement everything else we need on top of that.
So the question I'm analyzing in that example is: What happens if my primitive comparison operation is a 2-way comparison (lt(), like in C++) and then I implement 3-way comparison in terms of that (such as when I need it for for a binary search tree)? Now, what if we do the opposite: what happens if instead my primitive comparison operation is a 3-way comparison (cmp(), like in Python 2) and I only need to perform a 2-way comparison later? What are the trade-offs?
To do this, I take both approaches, implementing each in terms of the other, and compare how they behave complexity-wise. The conclusion I come to is that the choice of the primitive (which is often made by the language designers) isn't merely a question of aesthetics, but rather, it actually affects the time complexity of common operations (like traversing search trees). Similarly, the decision to cache a hash code doesn't just result in a constant-factor improvement, but it can actually change the time complexity of a program. And so on.
I think if you re-read the paper with these in mind, it should hopefully make more sense. The rest of what you said doesn't enter the picture at all... these are already balanced binary trees, the decision to use less<> is fundamentally independent of what C++ stdlib implementation you use, and the time of the vector concatenation isn't even being measured. Those things are unrelated to the point of the paper entirely. I was just trying to minimize the extraneous lines of code so we can focus on the heart of the problem instead of getting distracted by boilerplate.
2. The C++ standard library's maps and sets are known to be rather slow. See, for example:
https://stackoverflow.com/q/42588264/1593077
when you have string values, it's even worse, as you describe. But it's not clear that an overly-clever implementation, which caches numeric ranks of strings etc., is a good idea to have.
There may be a benchmark out there where std::set can beat std::unordered_set, but you'll be really hard pressed to find it
Java uses balanced trees instead of linked list in their chained-hashtable implementation, if I recall correctly.
std::unordered_set has some very difficult to reason about worst case scenarios that must factor in both the size of the collection and the hash function. Unless you are very careful about the type of hashing you use, you can easily be vulnerable to DDOS attacks that scale on the order of O(k * n) for key size k and container size n.
I could go on, but it's very much detracting from the point of the paper to argue about the data structure choice when the paper isn't on this topic at all or trying to analyze any particular application to begin with.
Aren't unordered_set and unordered_map quite new (IIRC, they came only with C++0x)? For most of C++'s history, if you preferred to use the standard library, what you had was only ordered sets and maps.
Also, in 2005 IIANM, Google published their dense and sparse hash map implementations, which were fast-ish and quite usable.
"Sorted" rather than ordered (an order can be arbitrary and I'd personally associate the word with insertion order).
> The formal data structure is unordered
The formal data structure doesn't have complexity bounds, the STL does.
If/when `std2::` happens, this is one of the things I assume would change.
The PartialOrd trait also uses 3-way comparisons so I think the other issue is mitigated too, but it'd be interesting to check: https://doc.rust-lang.org/std/cmp/trait.PartialOrd.html#tyme...
1) when you're using native libraries via python that were written by better c/c++ programmers than you are and you're spending most of your time within them
2) when you're using native libraries in python that are better implementations than the c/c++ libraries you're comparing against
3) when you don't know the libraries you're using in c/c++ (what they're talking about here)
...otherwise, if you're just using doing basic control flow optimizing compiler c/c++ will almost always be faster. (unless you're using numba or pypy or something).
point stands about the constants though. yes, asymptotic analysis will tell you about how an algorithm's performance scales, but if you're just looking for raw performance, especially if you have "little data", you really have to measure as implementation details of the software and hardware start to have a greater effect. (often times the growth of execution time isn't even smooth with the growth of n for small n)
Now try to concatenate a bunch of them in C.
I would partially agree with you, if it only mentioned C++.
Only partially, because too many C++ devs still use plain old C strings.
std::string_view is a nice fix for this but few programmers seem to use it yet.
Why not just do a binary search through the entire 256TB virtual memory space, finding the largest memory address that doesn't segfault? :-)
const char* strings[]={"ab","cd", "ef", "gh", ....};
char result[1024*1024*1024*1024];
size_t sz=0;
for(int i=0; i<sizeof(strings); i++)
{ size_t len=strlen(strings[i]); memcpy(result+sz, strings[i], len); sz+=len; }
result[sz]=0;This is frustrating for programmers because everyone wants to focus on the cool part of a program and forgets how much the rest takes to write, debug, etc. There are many reasons why I prefer Rust but one of the biggest is simply that having a standard package manager means that you can get high-quality code as easily as in languages like Python or JavaScript and are more likely to avoid that pitfall of reinventing wheels because it initially seems easier than finding a library.
moreover, batteries included scripting languages like perl, python, matlab, etc all tend to have the benefit of having their core bits be best of breed. perl has/had one of the best re engines out there, matlab has a great blas all compiled with the best optimizing compiler and ready to go, python was more generic i suppose, with fairly strong libraries for most things (strings, io, network io, etc).
other than the microsoft nuget stuff, the c/c++ ecosystem never really had the benefit of anything like that other than boost which was pretty tough to pull into a given project and didn't really have the community of people writing high level libraries like the scripting languages did. that said, i often used to think it would have been interesting to build a language agnostic platform for language centered library communities. (a sort of generic cpan/pip/npm in a box for pulling down libraries and running tests for any language- a combination of build system, online community platform and search engine)
but the real moral of the story: use the libraries, luke/lucia! also, know them!
I think C/C++ also had this problem with the whole cultural evolution around shared libraries. Because installs were non-trivial I think there was an almost subconscious blinder effect where people restricted themselves to what shipped with the OS / distribution even if that meant keeping a workaround for a bug which had been fixed upstream years before because that was seen as better than static linking or bundling a newer version.
In other words, is “faster than C” even a good metric if all it means that “if you implement something inefficiently in C it will be faster than if it is implemented efficiently in not-C”?
You can always beat c if c happens to implement a bad enough algorithm and your n is large enough. That's no guarantee that the performance ∆ will continue to hold once the two language implement the same algorithm.
What's much more important for good performance is memory layout and good use of CPU caches. And in this area managed languages struggle a lot. For instance, every object in Java has 16 bytes of overhead for an object header (on 64-bit openjdk jvm). Or you can't organize objects in a flat array. Or there are some guarantees about memory zeroing which often lead to needless memory writes. Or you have to live with GC, which often wastes a lot additional memory and regularly brings unused but reachable memory to caches. Project Valhalla is going to improve some of these limitations hopefully some day, but don't expect the level of C, C++ or Rust performance.
I also recently gave numba a go, and it was significantly slower than vanilla python. I was surprised because the decorated function seemed exactly like the type of code that numba would be good at (iterating through a list of coordinates doing square roots and some quirky floating-point modulo math.)
A vector operation is just where instead of having two lists, U and V which add to make W = [x+y for x,y in zip(U,V)] you directly operate on the arrays, W = U + V.
This allows the inner loop to be completely in native code. Sometimes some curious things happen where it's easier to do more vector operations resulting in more looping just because each of those operations is a vector operation and so is faster than the loop. For example, increment a number every time you see a particular element (time series breaking out subsequences) might look like np.cumsum(U == value) which is two loops in practice, but much faster than the iterative approach.
However, if you used an alterative toolchain that could also generate bytecode from C at runtime, then I would bet that C would stay on top or be equal.
You'd still need to compile your code with a regular toolchain, but you also need additional tools to compile, optimize, and debug code at runtime. That's what I meant by toolchain, even if it is not the conventional (static) definition.
Languages without arbitrary pointers don't have this issue and safely assume they knows all the assignments done to values in memory allowing for optimizations.
Whether or not the compiler will be smart enough to autovectorize is a different question.
C compilers don't validate correct use of restrict.
These LLVM bugs don't get noticed with C because C programs rarely use `restrict` as pervasively as a downleveled Rust program ends up doing.
For example, Rust can sometimes beat C because it's (1) often more friendly to auto-vectorization and (2) it has additional aliasing information.
For instance, C function calls always do some things (like preserving the stack) that may not always be necessary.
I sure wouldn't want to to TRY to beat a C compiler, but it seems obvious to me that it is possible.
The compiler might not even provide access to these capabilities to a programmer who knows about them and wants to explicitly use them. In such cases, the programmer might have to use assembly, or Fortran, C++ or even something much higher level than C with a compiler that provides access or knows how to "intuit" when those capabilities are useful.
Also, there's an aspect that I feel is constantly overlooked, and this is the way that objects are laid out in memory. In Python, JavaScript, Ruby, you have a lot of pointers to objects. You get a lot of pointer-chasing as a result. This is BAD for caches. Each object you touch, each pointer you dereference means pulling in a new cache line. In C, you can design very compact and flat data structures. You can use 32-bit floats, 8-bit, or even one-bit integers if you want. You can have a struct within a struct, with an array inside of it, all without any pointer-chasing.
Modern CPUs are constrained by memory bandwidth, and it's very hard for any programming language to beat C on achievable memory efficiency. What's worse is that we have little to no academic compiler literature on automatically optimizing for memory efficient data layouts. It's an overlooked and understudied problem. You would have to prove that integer values lie within certain ranges (hard) and also do object inlining (collapsing objects into parents) which AFAIK is also hard and not done by any mainstream compiler.
So, yeah, keep thinking that a sufficiently-smart compiler will do everything for you. You will assuredly be very disappointed. Until we have strong AI, the sufficiently smart compiler is basically unobtainium. If you want efficiency, the best route is generally to have less layers of abstraction, or to only rely on compiler optimizations you know for certain will happen.
C never was the lowest level of abstraction; there are other abstraction models out there and more still to be invented no doubt. C's model did well (though struggled mightily against Fortran for the longest time) at aligning with processor models of the 80's and 90's. It helps that C's ubiquity meant that to a degree the trail was washing the dog: processor designs were often measured against how they executed code compiled with a C compiler. But past preformance is a poor predictor of future success; who is to say that as processor designs continue to evolve, C's abstraction model won't become increasingly leaky against another? Absent a sufficiently smart compiler, it's entirely possible that C compiler writers will find themselves at a disadvantage.
And that assumes they're competing with a traditional compiler. It's possible, though unlikely, there will be competition from other execution models. As you said memory is often the core area of performance bottlenecks these days, and as terribly inefficient as bytecode interpreters are, they tend to have smaller code sizes. Efficient interprets are hand tuned specifically to make the overhead of bytecode interpretation as efficient as possible. Now, intrinsically they are performing a translation step at runtime that a compiler did before runtime, but one can at least theorize of a model where the interpreter is effectively a specialized decompression algorithm that feeds machine code to the CPU (that's really not that far afield from what happens in hardware in modern cpus and in mobile runtimes). Higher levels of abstraction might allow for more efficient decompression... It's crazy, but not inconceivable.
s/interprets/interpreters/
Damn, I should have proof read this on my desktop rather than just blind posting from my phone.
I've had a lot of conversations with javascript engineers over the years who've argued to me that well tuned JS will be nearly as fast as the equivalent C code. I've written plenty of little toy benchmarks over the years, and in my experience they're partly right. Well written JS code in V8 can certainly run fast - sometimes around half the speed of C code. But a massive performance gap opens up when you use nontrivial data structures. Nested fields, non-uniform arrays, trees, and so on will all cripple javascript's performance when compared to C's equivalent of simple embedded nested structs. If you couple clean C data structures with allocation-free hot paths from arenas, the performance of C will easily hit 10-20x the performance of the equivalent JS code.
From memory my plain text based operational transform code does ~800k transforms / second in javascript. The equivalent C code does 20M/second. The C implementation is about twice as many lines of code as the JS version though.
(The code in question: https://github.com/ottypes/text-unicode/blob/master/lib/type... / https://github.com/ottypes/libot )
You're right that flat datastructures are important, but C is far from the only language that can offer those.
I don't think C can ever be the answer; "comparable C code", i.e. code that was produced with the same amount of developer effort, is almost always undefined behaviour that happens to work most of the time on the developer's compiler. C doesn't have the kind of polymorphism that you need to write code that's compositional, testable, but also has good cache locality, at least not for code that also has to interact back and forth with the outside world. There is at least some work in the literature on making efficient use of cache in a Haskell/ML-like evaluation-by-reduction model, and I think that's where the long-term way forward lies (and FWIW in my experience compilers for ML-family languages already more than smart enough).
For HPC, you'd likely be better with something designed to run on GPUs, with built-in primitives for matrix operations, and a compiler that can tune the way those operations get implemented for you.
However, when it comes to cache locality, if the C programmer knows what they are doing, I think you'll have a very hard time beating them with Haskell or ML. AFAIK those languages have the same pointer-chasing issues I've described earlier. If you need to design a complex data structure, for example a scene graph in a 3D game engine, it will be much easier to make it compact in C.
A programmer who knows what they're doing is a rare thing indeed. On actual business problems with real-world programmers Haskell consistently beats C, IME.
> AFAIK those languages have the same pointer-chasing issues I've described earlier.
There's a pragma to flatten strict record fields, or a compiler flag to do that by default (at least in GHC).
OTOH, JIT runtimes have more input data than a C compiler. They can implement some runtime equivalent of C++ profile-guided optimization: measure what actually happens in runtime, assume the input data is going to stay roughly the same, and re-generate machine code with this new information into something more efficient.
Pretty sure modern Java does that sometimes.
> In Python, JavaScript, Ruby, you have a lot of pointers to objects.
In C# you can make data structures which don’t use pointers much, or at all. The language is strongly typed, has value types, it’s easy to place structures inside other structures. There’s a native stack just like C, and even stackalloc keyword which is an equivalent of alloca() in C.
Personally, I'm more interested in executable optimization. It decompiles an executable, performs whole-program optimization, and re-compiles it. I'd love to tinker around with optimizing other people's binaries (e.g. games) for my machine. There is something like that for LLVM but it's very experimental.
They have more data, but they are at a disadvantage by being time-pressured. They can't apply costly analysis to these data because they need to compile fast. Therefore typically they limit themselves to local analysis which may miss a lot of opportunity for inlining.
True in general, but they use quite a few tricks to minimize the consequences.
They use interpreter, or very unoptimal but fast version of JIT compiler, first time a function is called. They replace it with faster version once it’s clear the function is called a lot.
Unlike C compilers, they don’t need to do that analysis globally for the whole program. They only need to do that for the hot paths, that’s often a small portion of the code.
They can offload that analysis and code generation to another CPU core, and replace the implementation once that background thread has produced a faster version.
That's often correct, however unfortunately codebases today can be very, very huge. It can take a really lot of effort to optimize even just 10% of the hottest code if the product is several hundreds of MB of compressed byte-code. There are also applications with no obvious hot-spots, but flat profiles - e.g. database systems, where most of the time is being spent transferring data between various layers of the system. If a request gets passed through most of the layers, and can be routed into different areas depending on the query type set at runtime, and the clients are allowed to send queries of various types, so they target various different submodules of the server, there will be no hotspots. In these cases warmup can take enormous amount of time.
Even for a server this can be a problem, because after restarting you get an immediate performance hit.
Also keep in mind many software products are not long-living backend processes that can warmup for hours or even minutes. Client apps need good responsiveness, and before JIT even realizes which code to compile, it is already too late.
Good enough for desktop or embedded use cases, even on slow CPUs. I have 3 such devices on my desk, Raspberry Pi 4, a dev.board with Rockchip RK3288, and a tablet with Atom Z3735G, .NET is reasonably fast on all of them, without noticeable warmup issues at startup.
Here is a nice analysis of how various JITs warmup in practice:
https://tratt.net/laurie/blog/entries/why_arent_more_users_m...
TL;DR; often they don't!
why is that?
Yeah but that's completely validating my point. C# is not Python or JS. It's a (remote) cousin of C which tries to take some of the valuable performance tools from C and bring those to a managed runtime. Because it's strongly typed, it's a lot easier for the compiler to optimize, and because you have all these tools to design compact objects without pointer, you can do that job so the compiler doesn't have to.
And again, an experienced C# programmer can probably write code that runs circles performance-wise around code written by an experienced JS/Python developer in most cases.
That’s correct. But at the same time, the language is way higher level than C or C++.
> experienced C# programmer can probably write code that runs circles performance-wise around code written by an experienced JS/Python developer in most cases.
In some cases, an experienced C# programmer can even write code which approaches or outperforms C. My Linux video player library https://github.com/Const-me/Vrmac/tree/master/VrmacVideo#per... uses CPU on par with VLC, and 20% less RAM.
Javascript has the fastest general purpose hashmap/dictionary implementation of all programming languages but at the same time you are forced to use them all the time which overall slows the language down. Writing exactly the same code in C would be even slower since C hashmaps aren't as optimized. However, C code is rarely written like that so it's usually faster.
Don't JavaScript JITs rely heavily on this to reduce JavaScript's floating-point arithmetic to integer arithmetic?
Not to say it's easy, but hasn't a lot of work been done on this?
If you think about this for a second. Suppose I have a loop where I'm multiplying values:
function foo(x, y, n) { for (var i = 0; i < n; ++i) { x = x * y; }
return x;In order to know that the multiplication won't overflow, you have to be able to prove that both x and y, coming into that function, will be integers. You also have to have information about the range of x, y and i. If you know that x>=0 and y>= but you don't know how many times the loop will execute at compile time, you are basically screwed. You could unroll the loop to reduce the number of dynamic checks you need, but then that increases your code size. So you mostly have to check that the multiplication doesn't overflow on every iteration. You may also have to do dynamic type checks if you can't prove that x,y,i will always be integers.
The reason why C programs often are fast or run faster is because the language forces you to approach almost all abstraction head on - this goes both ways however, in that linked lists are much faster to write in C than a safe array type, so programs can end up with bad data structures for too long.
Since the lingua franca of the operating system is still C or C-like, there are actual optimization opportunities that go missing because of the C interface: It's hard to devise many alternatives, but if you are calling into libc for mathematics in a hot loop it may be worth avoiding it and rolling your own since the compiler can't really inline libc calls.
Well it might not be, but the fact that it "withholds a lot of information from the compiler" is an argument in favor of it being (a portable assembler), not the opposite.
Sure, in any language that provides more semantic information than C does. For example, D enables a "pointer to immutable data" type, while C does not. This can improve optimization.
On a pragmatic note, C makes it easy to use 0-terminated strings, and clumsy to use length-terminated strings. The natural result is people use 0-terminated strings.
0-terminated strings are inefficient because of the constant need to strlen them. When I look to optimize C, I find plenty of paydirt in all the strlen instances. D makes it easy to use length-terminated strings, and so people naturally prefer them.
Wait, isn’t that what
const int *x;
In D, `immutable(int)* x` cannot be changed by any reference to the value.
const int world = 42;
const int const * const hello = &world ;
const int * const hello = &world;
Thirdly, the latest C version supported by GCC is “-std=c17”.
int main()
{
const int world = 42;
const const const int const const * const const hello = &world;
return 0;
}
If you deceive the compiler like that, it is entitled to hand you a broken executable :-/
Besides, I forgot to mention that D immutable data is inherently thread safe, no synchronization required. And you can have as many live references to it as you like.
Immutable data is part of D's support for functional programming.
So even if you manage to reason correctly around `restrict` in C, you can't count on the compiler to translate your code correctly.
GCC also had bugs around restrict, but I don't know about their current status.
even if I use a magnetic needle to change the bits in my RAM ? :)
I don't think this is a reasonable argument. Every Turing compatible language that gives you direct access to the metal, so to speak, provides you with the opportunity to implement these optimization by hand.
I think it's much better to look at average C code there. And then C has a tremendous advantage with their compiler support. C compilers have decades of optimization put into them. This will take a while for other languages to catch up to that.
Disclaimer, my compiler background was the Java compiler and its bytecode generation but I would expect both gcc and clang/llvm to have lots of optimization cruft hardcoded for how C programs are written. If you deviate from that, you get potentially less well optimized code.
It's true that multi-language backends will inevitably cater to the semantics of the dominant language.
For a related example, I discovered that gdb doesn't pay much attention to the DWARF symbolic debug spec. It pays attention to the particular way gcc generates symbolic debug info. Other patterns, while compatible with the spec, don't work with gdb. Similar problems have happened with linkers.
It's a matter of "do as I do, not as I say".
Since I am the author of DMD's backend, I've been putting in optimizations that do cater to D, rather than just C and C++. For example, in the last few days I started putting in optimizations to take advantage of D's new "bottom" type:
Some things, like integral promotion rules, you can't get around. You may know that the promotion can be skipped in certain cases, but the compiler cannot know it.
This isn't true though. Just off the top of my head: C doesn't expose the carry flag directly, C doesn't let you write signed arithmetic using twos-complement overflow, C doesn't let you share a value between separate compilation units without allowing it to be mutated...
"faster" or "slower" is a pretty terrible metric anyway, given that most projects do not have infinite developer time available. But it's very hard to benchmark "equivalent developer effort" between two different languages.
Also tasks that can be moved to the GPU go a lot faster. You can interact with those programs in C, but not natively. But some languages, like Julia, can easily move calculations to/from the GPU. And also can transparently take advantage of parallelism.
Julia is in the process of growing rapidly for high performance computing. I don't know if it has officially passed C there. But if not yet, it will.
I wonder what the current split is. I'm not in HPC computing, but I see a lot of posts about how quickly Julia is being adopted.
If anything I'd say that C++ is the default for HPC conferences.
In my mind, different languages have different "optimization sound barriers", where further manual optimization becomes impossible, or at least runs into diminishing returns. For instance Javascript can be made nearly as fast as "vanilla" natively compiled C code, but that means writing asm.js by hand, which is entirely different from "idiomatic Javascript". It's not worth it writing asm.js by hand, when C compiled to asm.js (or WASM nowadays) is much more maintainable.
Same with garbage-collected languages in general. You can write fast code with very little overhead from the garbage collector, but this means you need to know exactly how the garbage collector of that language works, and the resulting code will usually look very different and will be harder to maintain than the idiomatic style of that language.
In standard C the optimization sound barrier is a bit further away than in many other high-level languages but it's not all that special, on the other hand C with compiler- and CPU-architecture-specific extensions is pretty good (e.g. extensions can push the sound barrier quite a bit further away).
Sometimes. I know 2 reasons.
1. In some higher-level languages, some problems can be efficiently solved with code generation. For instance, you can take some of the input data, generate code from that, then run the generated code processing the rest of the input data. Examples of the mechanism include Lisp macros, or .NET shenanigans like System.Reflection.Emit or System.Linq.Expressions.
It’s hard to generate good machine code. Possible to do in C, but you gonna need to embed C compiler for that. They are extremely complex, and were not designed for the use case e.g. relatively slow (designed to run offline on fast developer’s computers, or on even faster build servers).
If your problem is a good fit for that approach, C# can actually be faster than C.
Parsing JSON is a good example. When your goal is not just parsing the syntax, but also populating structures with the data from the JSON, good C# JSON parsers gonna runtime-generate serialization code by reflecting the structure types being populated. For an isolated program, technically you can generate equivalent C code offline. But if you’re making a general-purpose JSON serialization library that’s borderline impossible to achieve in C, need reflection and code generation.
2. Modern computers are heterogenous, they have 2 chips computing stuff, CPU and GPU. Even when these pieces are on the same chip and using the same RAM like Intel’s UHD graphics or AMD’s APUs, GPU can be still faster for some problems. Not only because more GFlops (that’s not necessarily true for integrated graphics), also because GPUs have better strategy for dealing with RAM latency. They switch threads instead of waiting for the data to arrive. CPU cores only run 1-2 hardware threads each i.e. limited in that regard.
That’s how for some problems HLSL or OpenCL can actually be faster than C.
in 2021 bundling clang along with your program is actually reasonable - if you are compiling small functions without two tons of headers it's measured in milliseconds.
Where do you place these functions once compiled? Into a separate DLL/each?
In .NET it’s quite easy to generate code that calls manually written functions, or access data provided by manually-written stuff. JIT runtime doesn’t treat generated code as something special, e.g. may inline calls across runtime-generated and manually written pieces of the program. With clang you gonna need a layer of indirection to integrate, with function pointers and such.
Shared libraries include relocation tables https://en.wikipedia.org/wiki/Relocation_%28computing%29 with all code locations which needs patching. That’s how the OSes can load them into arbitrary locations in memory and the code will still work.
Still, LLVM is a huge dependency to redistribute. And probably has many points of failure. For instance, I expect you gonna need to watch for INCLUDE and PATH environment variables when using that thing.
In .NET everything is in the standard library. The generated code is even platform-independent, for no additional overhead. Here’s couple non-trivial examples: https://github.com/Const-me/ComLightInterop/blob/master/ComL... https://github.com/Const-me/ComLightInterop/blob/master/ComL...
But .NET isn't?
Indeed.
.NET runtime takes about 30 MB, or 50 MB if you're on Windows and need desktop components. Links there: https://dotnet.microsoft.com/download/dotnet/5.0
clang+llvm package takes 300-400 MB, that's almost an order of magnitude difference: https://github.com/llvm/llvm-project/releases/tag/llvmorg-11...
I ship a statically compiled llvm + clang with my software and it does not add 300-400 mb to the binary at all, only something like 20-30 mb.
coreclr.dll (the runtime) is 4.9 MB, clrjit.dll (JIT compiler) is 1.3 MB. The rest is mostly standard libraries, the largest piece of that is System.Private.CoreLib.dll at 9 MB. The numbers are for Win64 version of .NET 5.0.2.
Another thing, for .NET apps the runtime is required anyway, the overhead for runtime code generation is zero.
For C++ apps, llvm + clang (or an equivalent) is only needed on developer’s computers, not something you’d normally ship.
unless you want to JIT-compile C++ code at runtime which is the original point.
Turing-completeness tells you that it is in fact necessarily true that you can convert any bit of C into a corresponding bit of Python, Lisp, or Haskell. One obvious approach would be to emit code that implements a C runtime.
For goto in specific, you don't even need to do that. You don't need a goto keyword to implement goto functionality.
how could you negate the python interpreter startup time though ?
That is, until things like C++'s stackless coroutines came about, which are a construct intrinsic to the compiler and not functionality directly exposed by C.
Further, any machine code language is going to allow you specific instruction access that a compiler might not otherwise utilize (rare, but it happens). In such cases you can gain 'manual' speedups over what C could allow you to do. I would hope that is the obvious exception, however.
But you are asking a very good question not a lot of developers are willing to think much about.
How would you write this (admittedly contrived) Rust function in C without invoking UB:
pub fn foo(a: &mut i32, b: &mut i32) {
let (new_a, new_b) = a.checked_mul(*b)
.map(|new_a| (new_a, b.saturating_sub(*a)))
.unwrap_or((10, 20));
*a = new_a;
*b = new_b;
}
* a = a * b
* b = b - a, saturating at the minimum value (as in, it won't wrap it just stops there)
If it did overflow:
* a = 10
* b = 20
And finally, does it compiler better: https://godbolt.org/z/66n8W9
The equivalent to checked_mul is __builtin_mul_overflow, which is a compiler builtin: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.... Similarly, saturating_sub seems like it can be implemented with __builtin_sub_overflow.
While I'll grant that Rust only has one fully functional compiler at this time, those functions have been part of Rust's corelib since 1.0. Any Rust compiler would have to support them.
[1] https://www.felixcloutier.com/x86/jcc and https://www.felixcloutier.com/x86/cmovcc
[2] https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensur....
computed goto, non-aliasing guarantees, actual "const" - just a few on top of my mind.
Generic code is generally faster in C++ unless you manually reimplement it in C.
Rust can be faster than C in few cases because stronger aliasing guarantees, but few compiler bugs prevent it.
Doing some good-performance stuff is also more difficult in C. Strings are null terminated etc..
Similarly in languages like Java or C#, having first-class exceptions means fewer branches & error checking on the hot path over something like C. They are on the whole slower than C for other reasons, but it's not because C is "the best" or "the fastest" at everything. And of course you can't really do de-virtualization optimizations in C.
It is true that C cannot do full template meta-programming or certain state save/restore optimizations faster than setjmp/longjmp. Hard/painful/trivial are all a bit more subjective and relative to exposure/practice/training/etc.
Personally, I think Nim [2] is a much friendlier way to go than either C++ or Python without the pitfalls of either, but the ecosystem is admittedly much smaller. Also, I've yet to hit something where re-writing the C++/Rust in Nim did not speed things up from "at least a little" to "quite a bit". { This is more an artifact of "performance incautious programming" in the C++/Rust. Too many people fall into the trap that, since a language has a reputation for speed, they don't need to think. This is probably largely why @mehrdadn's original article had the title it did. ;-) }
Of course, C++ has those some macro capabilities. But macros are quite limited, and typically the "template-like" ones rely on non-standard preprocessor support like typeof for swap. But then you still lack the ability to specialize swap for different types (eg, you can't replicate std::swap's behavior on std::vector in C)
> C can do setjmp & longjmp exceptions and you can even do a TRY/CATCH like exception macros.
You can, but that's now another parameter to pass along down the call stack, and as LLVM notes https://llvm.org/docs/ExceptionHandling.html#setjmp-longjmp-... it still negatively impacts the non-exception performance path.
Sure, the use of these things in C is (usually) a bit more verbose/burdensome than C++. The misleading statements were performance-oriented, not syntactic sugar-oriented, and I already granted exception optimization. (Some folks, like Go/Rust authors, would tell you exceptions are bad anyway.)
Of course, C++'s eigen does loop fusion for you with template magic so to go really fast you probably want that.
I'm not sure why you think that, especially with Rust one of the reasons it can be theoretically faster is because it allows for even more undefined behavior and has a variety of datatypes that simply exist to inform the compiler of potential optimizations.
Demo: https://ideone.com/CBIEAE
This creates ~60 objects, but takes something like 2^30 operations to resolve (it times out on this online runner, and takes around 5s on my laptop with -O3).
That's much worse than claimed in this paper! An accidentally-exponential algorithm is the kind of thing that makes DoS attacks trivial...
I know this because I already received such criticism for my examples, with people telling me that it's unclear how wide-reaching the ramifications are in real-world applications (which I suppose is fair enough). People really want to see examples of real-world software being improved with such small tweaks in the algorithms, whereas I didn't have the bandwidth to try to investigate that, and just tried to settle for plausible examples. That criticism would be magnified many times further for DAGs and (especially) degenerate linked lists. (I'm not claiming these are the only relevant scenarios by the way—just saying this is how it is likely to be seen by many readers.) I moved on and didn't spend more time on this (it was kind of a random paper idea I had and not related to anything else), but I think it would be awesome to flesh this out further into something more interesting and compelling and properly publish it.
If you find this interesting and have the time to help joint-author & actually publish a paper on this, please grab my email from arXiv and email me! It would be great to flesh out more consequences and find more interesting examples together. I feel like there's a lot more underneath the surface that I might not have touched (both theoretically and practically), but I hadn't managed to gather enough interest from others in the topic (let alone the examples) to motivate me to look further until now!
Edit: The original title "Why Python is faster than C++" is much more clickbaity than the editorialized ("When Python is faster than C++")
# Uses 3-way cmp() for primitives
def cmp3(a, b):
if not isinstance(a, list):
global c; c += 1
return cmp(a, b)
for x, y in zip(a, b):
r = cmp3(x, y)
if r != 0:
return r
return 0
The paper points out that the convenience of just defining "less than", and heaving "equals" derived from that can be costly. Specifically, for the recursively defined data structure (tree), a three-way comparison which is derived canonically from the two way compare seems to entail not a linear but an quadratic number of comparisons.
What I don't understand is what is happening in 'lt2'.
this is what I'd expect for __lt__
lt(a, b) also known as (a __lt__ b) is returning
True, iff a < b, elementwise for lists
False otherwise
for same length lists.
(a __eq__ b) iff not (a __lt__ b) and not (b __lt__ a)
cmp(a, b) = lt(a, b) - lt(b, a)
a < b: 1 - 0 ==> 1
b < a: 0 - 1 ==> -1
a == b: 0 - 0 ==> 0
Now two questions arise with respect to the presented hypothesis and the paper:
1. why does the paper call lt2 twice, recursively?
2. why does the paper compare the performance of their lt2 and lt3 instead of the performance of cmp2 and cmp3?
I intuit, when taking the double recursion out of lt2, which imnsho is erroneous, and when comparing cmp2 and cmp3, we'll see a performance penalty of a factor 2, between cmp2 and cmp3, and identical run times for lt2 and lt3, as it should be.
What am I missing?
edit: updated for clarity
Note that you do need to read the entire paper to see the overall picture and its consequences; if you stop halfway then it might appear like I'm comparing things unfairly. Feel free to let me know if anything is still confusing after reading the other comments and taking another look at the paper and I'll try to clarify!
1. the lt2 definition in the paper is wrong. A lexicographical compare is linear in the size. the derived cmp2 is correct and has a run time twice that of cmp3. which matches the stl definitions of lexicographical_compare, see below.
2. the c++ behaviour in 2.4.2 is puzzling and most likely bug, worth reporting to and discussing with STL implementors.
https://www.cplusplus.com/reference/vector/vector/operators/
http://www.cplusplus.com/reference/algorithm/lexicographical...
Would you mind providing a counterexample to illustrate what incorrect output it's producing?
> A lexicographical compare is linear in the size.
Indeed, lt2() also has a loop that iterates a linear number of times as you mention. It is consistent with this.
> the derived cmp2 is correct and has a run time twice that of cmp3. which matches the stl definitions of lexicographical_compare, see below.
Perhaps you might be confused about what lexicographical_compare does? It does not "compare" in the 3-way sense. It only performs a "less-than" comparison. The name is rather misleading.
2. the c++ behaviour in 2.4.2 is puzzling and most likely bug, worth reporting to and discussing with STL implementors.
I'm not sure what to report to anyone, as I don't find it puzzling; it is entirely consistent with everything I'm aware of and have tried to explain in the paper. It is also not specific to any particular implementation; I believe you will see this behavior on any correct implementation you try it on. It might be helpful if you try to produce a counterexample using what you believe would be a correct & efficient implementation to validate or invalidate this.
I wonder (genuinely asking, not being snarky) what it is about C/C++ that seems to make these issues more common? It's also possible my perception of "more common" has just been inflated by seeing multiple examples in a single week
For instance, if you consider strcmp(x, y, strlen(y)) where x is of fixed length, then the whole function would be constant-time if strlen(y) is optimized out, whereas it would take linear time (linear in strlen(y)) otherwise. GCC et al. can optimize out strlen() in some such cases.
In practice you wouldn't want to rely on this, both because compilers aren't anywhere near smart enough to figure out complicated cases and also because these wouldn't happen in debug mode either, but it's not impossible for time complexity to change through optimization.
clang seems to optimize it to (n-1)(n-2)/2+2n-1, which is O(1).
This title states "Python is Faster Than C++", which neither implies that this is just an opinion, nor that it isn't an absolute statement. You have to figure out yourself that it's probably hyperbolic and just referring to special cases.
Of course this is just a preprint. If they ultimately publish it somewhere the editors/reviewers may make them give a more conservative title.
The C++ code shown is a great example: when you see very simple code in the middle of a paper talking about how a particular patterns fails badly, yes, you're primed to look for a problem but if that showed up for you in code review are you really confident that you'd say something other than “followed standard practice, maybe add braces around the if statement”?
The real lesson here is that nothing beats actually measuring your code to make sure you didn't miss something like this.