13 ms·

I’ve been thinking about this lately. Can you actually be faster than C? Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust

I’ve been thinking about this lately. Can you actually be faster than C? Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), any algorithm for say parsing JSON can be expressed equally as efficiently in C, while a clever and hacky C-specific algorithm cannot necessarily be expressed in those higher level languages. 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”?

xrisk 6y ago
Rust already does better than C for some benchmarks. See: https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/rust.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
- coliveira 6y ago
  As the paper showed, even Python can be better than C at carefully selected tasks.
  - moonchild 6y ago
    No, the paper showed that use of a particular ecosystem default in c++ led to algorithmically worse performance then use of an ecosystem default in python. 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.
bqmjjx0kac 6y ago
Sure, managed languages can beat C performance. IIRC, the JVM can reorder branches on the fly to avoid jumps.
- pkolaczk 6y ago
  Reordering or hinting branches has virtually zero impact on branch prediction performance on modern architectures with advanced hardware branch prediction. 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.
offtop5 6y ago
I think about programming languages like I do cars. While rust may be a Ferrari, some kid who doesn't know how to drive a stick and has only had his license for about a month is going to have a rough time beating you driving from New York to Texas even if you're driving a Corolla. I consider myself to be an extremely good software engineer, but lower level programming languages scare me. Recently I've been riding a lot of code in C++ for my Arduino project, but aside from that I can't stand it. You have to be such a good C programmer to make things faster than you probably could knock out using Python + numpy or something like that, but to be fair under the hood numpy uses tons of optimized C code.
- sgtnoodle 6y ago
  I mainly write embedded software in C and C++, but I tend to use python for non-embedded stuff. The funny thing is that I've attempted to speed up multiple python scripts by replacing lists of floats with numpy arrays, and each time it's ended up slightly slower. I suspect numpy only really starts to pay off when you're doing the same operations to 1000+ elements. For modest data sets, or algorithms that don't map particularly well to numpy's operations, the built in data types do better. 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.)
  - ColFrancis 6y ago
    Just checking, even though you likely know. The numpy arrays really only pay off when you vectorise your calculations. Don't expect any speed up if you're still using list comprehensions. 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.
tylerhou 6y ago
If you use the normal toolchains for C vs another language, the other language still can be faster because it can dynamically generate bytecode based on runtime information. In the normal C toolchain, this is not possible. 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.
- thysultan 6y ago
  You can literally emit runtime assembly in C in any C toolchain, what are you on about?
  - tylerhou 6y ago
    How do you dynamically generate machine code without linking something like LLVM?
    - sgtnoodle 6y ago
      I believe that's actually what folk are doing these days, literally linking in LLVM and using it to compile C into machine code then executing it during runtime.
      - tylerhou 6y ago
        That's what I mean by "alternative toolchain," though; some of the code that you are executing at runtime isn't being generated by the normal GCC/Clang toolchain. It's being generated by your custom setup which links in LLVM. 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.
    - thysultan 6y ago
      same way you would with llvm, you can map executable memory without llvm and execute it.
wvenable 6y ago
C loses some optimization potential because of aliasing; it can't be guaranteed that some pointer operation isn't going to change a variable anywhere in memory so that limits certain reordering and loop optimizations. 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.
- kevin_thibedeau 6y ago
  The restrict keyword helps with this.
  - pjmlp 6y ago
    Provided their user knows what they are doing and never do the mistake to lie to the compiler.
  - m_mueller 6y ago
    That, or switching to FORTRAN. For numeric / HPC it is much easier to get a decently fast implementation there.
- coliveira 6y ago
  The C language has provided the restrict keyword to solve these aliasing issues since the C99 standard. That is, 20 years ago.
  - tachyonbeam 6y ago
    I think this generally doesn't have much of an impact on performance.
    - cozzyd 6y ago
      It certainly does... it's the main reason fortran was often faster than C, isn't it? Aliasing prevents automatic vectorization, among other things. Whether or not the compiler will be smart enough to autovectorize is a different question.
nynx 6y ago
Be careful when you say that everything can be converted to C. While that's true in a naive fashion, it gets rid of a lot of additional information. For example, Rust can sometimes beat C because it's (1) often more friendly to auto-vectorization and (2) it has additional aliasing information.
TylerE 6y ago
Sure, theoretically. 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.
kevin_thibedeau 6y ago
C code that makes heavy use of callbacks in inner loops is at a disadvantage compared to languages with more powerful inlining facilities. Compare qsort() to std::sort().
rz2k 6y ago
Because C is not machine code or even assembly language it must be compiled. Not only might the compiler not be as opportunistic about improving the human written code, but it might not fully utilize the machine's full capabilities if the compiler does not understand the complete instruction set that is available or other things like memory and different levels of cache. 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.
- tachyonbeam 6y ago
  Compiler engineer here. In practice, compilers for higher-level languages often have a lot of difficulty getting anywhere close to the efficiency of comparable C code. If you take Python, for example, you have to do a lot of inlining to eliminate various abstractions. Inlining is actually non-trivial. Yes, inlining, by itself, is an easy program transformation, but knowing where to inline to get the best performance is very hard. If you inline too much, you increase code size, and you lose performance. You have to know precisely which inlining decisions will pay for themselves, and your large codebase might have tens of thousands of call sites and a call hierarchy 40 functions deep. Python also adds the fun little problem that you can redefine any function at run time, which makes it hard for the compiler to know which function you're actually going to be calling. To complicate things further, inlining decisions affect other optimizations. For example, if you inline foo into bar, do you then also inline into bar the functions that foo is calling? Do you unroll the loops from foo into bar? Etc. 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.
mhh__ 6y ago
C - and especially idiomatic C actually withholds a __lot__ of information from the compiler. People like to think C is just a portable assembler, but by god it ain't. 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.
- coldtea 6y ago
  >C - and especially idiomatic C actually withholds a __lot__ of information from the compiler. People like to think C is just a portable assembler, but by god it ain't. 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.
WalterBright 6y ago
> Can you actually be faster than C? 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.
- teddyh 6y ago
  > For example, D enables a "pointer to immutable data" type, while C does not. Wait, isn’t that what const int *x; does? I.e. a pointer to a constant.
  - WalterBright 6y ago
    In C, the value pointed to by `x` cannot be changed via a write through `x`, but if there is another pointer to that value, it can be changed through that. In D, `immutable(int)* x` cannot be changed by any reference to the value.
    - teddyh 6y ago
      You’d think that C could do any appropriate optimizations as well as D, since the C compiler (in theory) should know whether there can exist (in any given program) any writeable pointers to the same value or if there only can exist pointers to const.
      - innocenat 6y ago
        Pointer arithmetic would surely make all value mutable. Or even simple array access.
        6y ago
lmm 6y ago
> Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), any algorithm for say parsing JSON can be expressed equally as efficiently in C, while a clever and hacky C-specific algorithm cannot necessarily be expressed in those higher level languages. 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.
btilly 6y ago
FORTRAN is faster for many tasks, and is probably more popular in high performance computing. 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.
- Leo_Verto 6y ago
  To add onto your point: from what I've heard the split at HPC conferences is about 40% C to 60% Fortran.
  - btilly 6y ago
    That sounds right. 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.
  - SubjectToChange 6y ago
    In my limited experience, almost every language specific presentation at an HPC conference is about C++. New projects and initiatives like DPC++, SYCL/oneAPI, Ginkgo, etc are C++ based. And if you look at the open source libraries of the national laboratories, e.g. LLNL, C++ libraries are more common than C libraries, which in turn are more common than the Fortran libraries. If anything I'd say that C++ is the default for HPC conferences.
- not2b 6y ago
  Python users who use numpy and scipy are actually using a lot of Fortran code.
flohofwoe 6y ago
IME "faster than C" without going into a lot of details what manual optimizations have gone into a specific piece of the C code doesn't mean much. Writing C code doesn't automatically give you high performance, but it gives you quite a bit of wiggle room to manually optimize the code. 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).
Const-me 6y ago
> Can you actually be faster than C? 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.
- jcelerier 6y ago
  > 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). 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.
  - Const-me 6y ago
    I never tried to, but I think integration of runtime-generated native code gonna cause overhead. 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.
thaumasiotes 6y ago
> you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto 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.
- jcelerier 6y ago
  > One obvious approach would be to emit code that implements a C runtime. how could you negate the python interpreter startup time though ?
  - thaumasiotes 6y ago
    Are we talking about compiling or performance? You negate the Python interpreter startup time by changing your implementation of the Python binary, but that isn't relevant to the problem of producing compiler output in the Python language.
- IgorPartola 6y ago
  Let’s be careful here. All these languages are Turing complete. Heck, isn’t CSS Turing complete now? But insofar as goto in C produces a certain small amount of CPU instructions (1? 2?), can all those other higher level languages do the same? Or will something like JavaScript need a callback-based solution that will do several pointer lookups, memory allocation, etc?
limaoscarjuliet 6y ago
Per Jim Keller, current source of speed in CPU is better branch prediction and data fetching prediction. It is possible C++ (or some other lang) may have more met information to drive these better, in which case it will be faster than C/assembler. https://www.youtube.com/watch?v=G4hL5Om4IJ4 https://www.youtube.com/watch?v=G4hL5Om4IJ4
junon 6y ago
I've thought about this very question for years. My answer has been, usually, "no" for all cases that do not allow the developer to write straight assembly. 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.
kllrnohj 6y ago
Easily. C++ has ways of being faster that C can't really match - namely, templates. They can be hellish to write & debug, but generating type-specific functions is fantastic for optimization & performance. It's also a lot easier to be faster in C++ on key things than it is in C, specifically small-size optimizations. Yes you can do an SSO string or function pointer in C, but it's hard & painful to do so, so it's rarely if ever done. But it's trivial to do in C++, and since the standard library does it for both strings & functions, it's also commonly done. 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.
- cb321 6y ago
  This seems oriented around just code bases you have seen personally rather than fundamental C limitations and so misleads. To clarify: C can do template-like macros for type specialization (and this is common in some code bases) and easier to debug ways [1] { I've personally used a variant of [1] techniques since the mid 90s }. C can do setjmp & longjmp exceptions and you can even do a TRY/CATCH like exception macros. Function pointers are in stdlib interfaces (e.g. qsort) and generally pretty common in C code. I believe gcc has been able to inline through C function pointers ("de-virtualize", though you qualify with "really" there..) in the same translation unit for like 2 decades now with the right compiler flags/annotations. 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. ;-) } [1] https://github.com/glouw/ctl/ https://github.com/glouw/ctl/ [2] https://nim-lang.org https://nim-lang.org
Measter 6y ago
> [..] Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C [..] 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; } For those unfamiliar with Rust, it multiplies a by b, and if it didn't overflow: * 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 https://godbolt.org/z/66n8W9
- lorenzhs 6y ago
  Something like this? https://godbolt.org/z/6nod5e https://godbolt.org/z/6nod5e. It even produces almost identical assembly. The equivalent to checked_mul is __builtin_mul_overflow, which is a compiler builtin: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.... Similarly, saturating_sub seems like it can be implemented with __builtin_sub_overflow.
  - Measter 6y ago
    Would those work on any compiler, or are they compiler-specific? If those are non-standard compiler-specific extensions, not even a library, is it truly a part of C++? 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.
    - lorenzhs 6y ago
      They're not part of the standard, but gcc, clang, and icc (Intel) support them. Alternatively, you could emit the correct instructions in an asm block on supported architectures (x86: 'jo'/'jno' for jumps, 'cmovo'/'cmovno' for conditional moves [1]) or reimplement the operations in software [2] [1] https://www.felixcloutier.com/x86/jcc https://www.felixcloutier.com/x86/jcc and https://www.felixcloutier.com/x86/cmovcc https://www.felixcloutier.com/x86/cmovcc [2] https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensur....
majjgepolja 6y ago
C also does lack few features which can provide better performance or provide hints to the compiler. 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..
Symmetry 6y ago
Well, generally optimized numerical libraries like BLAS are faster than what you write yourself. But a prolbem with calling them from C is that you don't get loop fusion, each call has to go through the data before the next one starts. That isn't true with Haskell's lazy evaluation so it can be faster in some cases. Of course, C++'s eigen does loop fusion for you with template magic so to go really fast you probably want that.
Blikkentrekker 6y ago
> Can you actually be faster than C? Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), 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.

xrisk 6y ago

Rust already does better than C for some benchmarks. See: https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/rust.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

coliveira 6y ago
As the paper showed, even Python can be better than C at carefully selected tasks.
- moonchild 6y ago
  No, the paper showed that use of a particular ecosystem default in c++ led to algorithmically worse performance then use of an ecosystem default in python. 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.

bqmjjx0kac 6y ago

Sure, managed languages can beat C performance. IIRC, the JVM can reorder branches on the fly to avoid jumps.

pkolaczk 6y ago
Reordering or hinting branches has virtually zero impact on branch prediction performance on modern architectures with advanced hardware branch prediction. 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.

offtop5 6y ago

I think about programming languages like I do cars. While rust may be a Ferrari, some kid who doesn't know how to drive a stick and has only had his license for about a month is going to have a rough time beating you driving from New York to Texas even if you're driving a Corolla. I consider myself to be an extremely good software engineer, but lower level programming languages scare me. Recently I've been riding a lot of code in C++ for my Arduino project, but aside from that I can't stand it. You have to be such a good C programmer to make things faster than you probably could knock out using Python + numpy or something like that, but to be fair under the hood numpy uses tons of optimized C code.

sgtnoodle 6y ago
I mainly write embedded software in C and C++, but I tend to use python for non-embedded stuff. The funny thing is that I've attempted to speed up multiple python scripts by replacing lists of floats with numpy arrays, and each time it's ended up slightly slower. I suspect numpy only really starts to pay off when you're doing the same operations to 1000+ elements. For modest data sets, or algorithms that don't map particularly well to numpy's operations, the built in data types do better. 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.)
- ColFrancis 6y ago
  Just checking, even though you likely know. The numpy arrays really only pay off when you vectorise your calculations. Don't expect any speed up if you're still using list comprehensions. 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.

tylerhou 6y ago

If you use the normal toolchains for C vs another language, the other language still can be faster because it can dynamically generate bytecode based on runtime information. In the normal C toolchain, this is not possible. 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.

thysultan 6y ago
You can literally emit runtime assembly in C in any C toolchain, what are you on about?
- tylerhou 6y ago
  How do you dynamically generate machine code without linking something like LLVM?
  - sgtnoodle 6y ago
    I believe that's actually what folk are doing these days, literally linking in LLVM and using it to compile C into machine code then executing it during runtime.
    - tylerhou 6y ago
      That's what I mean by "alternative toolchain," though; some of the code that you are executing at runtime isn't being generated by the normal GCC/Clang toolchain. It's being generated by your custom setup which links in LLVM. 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.
  - thysultan 6y ago
    same way you would with llvm, you can map executable memory without llvm and execute it.

wvenable 6y ago

C loses some optimization potential because of aliasing; it can't be guaranteed that some pointer operation isn't going to change a variable anywhere in memory so that limits certain reordering and loop optimizations. 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.

kevin_thibedeau 6y ago
The restrict keyword helps with this.
- pjmlp 6y ago
  Provided their user knows what they are doing and never do the mistake to lie to the compiler.
- m_mueller 6y ago
  That, or switching to FORTRAN. For numeric / HPC it is much easier to get a decently fast implementation there.
coliveira 6y ago
The C language has provided the restrict keyword to solve these aliasing issues since the C99 standard. That is, 20 years ago.
- tachyonbeam 6y ago
  I think this generally doesn't have much of an impact on performance.
  - cozzyd 6y ago
    It certainly does... it's the main reason fortran was often faster than C, isn't it? Aliasing prevents automatic vectorization, among other things. Whether or not the compiler will be smart enough to autovectorize is a different question.

nynx 6y ago

Be careful when you say that everything can be converted to C. While that's true in a naive fashion, it gets rid of a lot of additional information. For example, Rust can sometimes beat C because it's (1) often more friendly to auto-vectorization and (2) it has additional aliasing information.

TylerE 6y ago

Sure, theoretically. 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.

kevin_thibedeau 6y ago

C code that makes heavy use of callbacks in inner loops is at a disadvantage compared to languages with more powerful inlining facilities. Compare qsort() to std::sort().

rz2k 6y ago

Because C is not machine code or even assembly language it must be compiled. Not only might the compiler not be as opportunistic about improving the human written code, but it might not fully utilize the machine's full capabilities if the compiler does not understand the complete instruction set that is available or other things like memory and different levels of cache. 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.

tachyonbeam 6y ago
Compiler engineer here. In practice, compilers for higher-level languages often have a lot of difficulty getting anywhere close to the efficiency of comparable C code. If you take Python, for example, you have to do a lot of inlining to eliminate various abstractions. Inlining is actually non-trivial. Yes, inlining, by itself, is an easy program transformation, but knowing where to inline to get the best performance is very hard. If you inline too much, you increase code size, and you lose performance. You have to know precisely which inlining decisions will pay for themselves, and your large codebase might have tens of thousands of call sites and a call hierarchy 40 functions deep. Python also adds the fun little problem that you can redefine any function at run time, which makes it hard for the compiler to know which function you're actually going to be calling. To complicate things further, inlining decisions affect other optimizations. For example, if you inline foo into bar, do you then also inline into bar the functions that foo is calling? Do you unroll the loops from foo into bar? Etc. 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.

mhh__ 6y ago

C - and especially idiomatic C actually withholds a __lot__ of information from the compiler. People like to think C is just a portable assembler, but by god it ain't. 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.

coldtea 6y ago
>C - and especially idiomatic C actually withholds a __lot__ of information from the compiler. People like to think C is just a portable assembler, but by god it ain't. 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.

WalterBright 6y ago

> Can you actually be faster than C? 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.

teddyh 6y ago
> For example, D enables a "pointer to immutable data" type, while C does not. Wait, isn’t that what const int *x; does? I.e. a pointer to a constant.
- WalterBright 6y ago
  In C, the value pointed to by `x` cannot be changed via a write through `x`, but if there is another pointer to that value, it can be changed through that. In D, `immutable(int)* x` cannot be changed by any reference to the value.
  - teddyh 6y ago
    You’d think that C could do any appropriate optimizations as well as D, since the C compiler (in theory) should know whether there can exist (in any given program) any writeable pointers to the same value or if there only can exist pointers to const.
    - innocenat 6y ago
      Pointer arithmetic would surely make all value mutable. Or even simple array access.
      - 6y ago

lmm 6y ago

> Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), any algorithm for say parsing JSON can be expressed equally as efficiently in C, while a clever and hacky C-specific algorithm cannot necessarily be expressed in those higher level languages. 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.

btilly 6y ago

FORTRAN is faster for many tasks, and is probably more popular in high performance computing. 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.

Leo_Verto 6y ago
To add onto your point: from what I've heard the split at HPC conferences is about 40% C to 60% Fortran.
- btilly 6y ago
  That sounds right. 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.
- SubjectToChange 6y ago
  In my limited experience, almost every language specific presentation at an HPC conference is about C++. New projects and initiatives like DPC++, SYCL/oneAPI, Ginkgo, etc are C++ based. And if you look at the open source libraries of the national laboratories, e.g. LLNL, C++ libraries are more common than C libraries, which in turn are more common than the Fortran libraries. If anything I'd say that C++ is the default for HPC conferences.
not2b 6y ago
Python users who use numpy and scipy are actually using a lot of Fortran code.

flohofwoe 6y ago

IME "faster than C" without going into a lot of details what manual optimizations have gone into a specific piece of the C code doesn't mean much. Writing C code doesn't automatically give you high performance, but it gives you quite a bit of wiggle room to manually optimize the code. 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).

Const-me 6y ago

> Can you actually be faster than C? 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.

jcelerier 6y ago
> 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). 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.
- Const-me 6y ago
  I never tried to, but I think integration of runtime-generated native code gonna cause overhead. 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.

thaumasiotes 6y ago

> you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto 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.

jcelerier 6y ago
> One obvious approach would be to emit code that implements a C runtime. how could you negate the python interpreter startup time though ?
- thaumasiotes 6y ago
  Are we talking about compiling or performance? You negate the Python interpreter startup time by changing your implementation of the Python binary, but that isn't relevant to the problem of producing compiler output in the Python language.
IgorPartola 6y ago
Let’s be careful here. All these languages are Turing complete. Heck, isn’t CSS Turing complete now? But insofar as goto in C produces a certain small amount of CPU instructions (1? 2?), can all those other higher level languages do the same? Or will something like JavaScript need a callback-based solution that will do several pointer lookups, memory allocation, etc?

limaoscarjuliet 6y ago

Per Jim Keller, current source of speed in CPU is better branch prediction and data fetching prediction. It is possible C++ (or some other lang) may have more met information to drive these better, in which case it will be faster than C/assembler. https://www.youtube.com/watch?v=G4hL5Om4IJ4 https://www.youtube.com/watch?v=G4hL5Om4IJ4

junon 6y ago

I've thought about this very question for years. My answer has been, usually, "no" for all cases that do not allow the developer to write straight assembly. 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.

kllrnohj 6y ago

Easily. C++ has ways of being faster that C can't really match - namely, templates. They can be hellish to write & debug, but generating type-specific functions is fantastic for optimization & performance. It's also a lot easier to be faster in C++ on key things than it is in C, specifically small-size optimizations. Yes you can do an SSO string or function pointer in C, but it's hard & painful to do so, so it's rarely if ever done. But it's trivial to do in C++, and since the standard library does it for both strings & functions, it's also commonly done. 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.

cb321 6y ago
This seems oriented around just code bases you have seen personally rather than fundamental C limitations and so misleads. To clarify: C can do template-like macros for type specialization (and this is common in some code bases) and easier to debug ways [1] { I've personally used a variant of [1] techniques since the mid 90s }. C can do setjmp & longjmp exceptions and you can even do a TRY/CATCH like exception macros. Function pointers are in stdlib interfaces (e.g. qsort) and generally pretty common in C code. I believe gcc has been able to inline through C function pointers ("de-virtualize", though you qualify with "really" there..) in the same translation unit for like 2 decades now with the right compiler flags/annotations. 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. ;-) } [1] https://github.com/glouw/ctl/ https://github.com/glouw/ctl/ [2] https://nim-lang.org https://nim-lang.org

Measter 6y ago

> [..] Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C [..] 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; } For those unfamiliar with Rust, it multiplies a by b, and if it didn't overflow: * 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 https://godbolt.org/z/66n8W9

lorenzhs 6y ago
Something like this? https://godbolt.org/z/6nod5e https://godbolt.org/z/6nod5e. It even produces almost identical assembly. The equivalent to checked_mul is __builtin_mul_overflow, which is a compiler builtin: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.... Similarly, saturating_sub seems like it can be implemented with __builtin_sub_overflow.
- Measter 6y ago
  Would those work on any compiler, or are they compiler-specific? If those are non-standard compiler-specific extensions, not even a library, is it truly a part of C++? 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.
  - lorenzhs 6y ago
    They're not part of the standard, but gcc, clang, and icc (Intel) support them. Alternatively, you could emit the correct instructions in an asm block on supported architectures (x86: 'jo'/'jno' for jumps, 'cmovo'/'cmovno' for conditional moves [1]) or reimplement the operations in software [2] [1] https://www.felixcloutier.com/x86/jcc https://www.felixcloutier.com/x86/jcc and https://www.felixcloutier.com/x86/cmovcc https://www.felixcloutier.com/x86/cmovcc [2] https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensur....

majjgepolja 6y ago

C also does lack few features which can provide better performance or provide hints to the compiler. 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..

Symmetry 6y ago

Well, generally optimized numerical libraries like BLAS are faster than what you write yourself. But a prolbem with calling them from C is that you don't get loop fusion, each call has to go through the data before the next one starts. That isn't true with Haskell's lazy evaluation so it can be faster in some cases. Of course, C++'s eigen does loop fusion for you with template magic so to go really fast you probably want that.

Blikkentrekker 6y ago

> Can you actually be faster than C? Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), 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.