How can this paper be taken seriously when the paper doesn't even show the compilation flags?
Accidentally quadratic: When Python is faster than C++
31–40 of 215 posts
Re: Accidentally quadratic: When Python is faster than C++
#32Earlier quoted context omitted.
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.
The developer must also be smart enough not to do the mistake to lie to the compiler, by actually doing aliasing with restricted variables as it is UB and nasal dragons beware. C compilers don't validate correct use of restrict.
Not all C compilers handle even correct uses of `restrict` properly. For about three years, Rust has been unable to use the LLVM equivalent of `restrict` when downleveling its references, because it keeps finding LLVM miscompilation bugs around it.
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.
Re: Accidentally quadratic: When Python is faster than C++
#33Have academic CS articles always had click-bait titles?
I have noticed this a lot too. I'd guess is has to do with the importance of conferences over journals in CS (as opposed to nearby fields where journals dominate). Conferences tend to be more informal and forgiving of titles like that.
Of course this is just a preprint. If they ultimately publish it somewhere the editors/reviewers may make them give a more conservative title.
Re: Accidentally quadratic: When Python is faster than C++
#34[deleted]
Re: Accidentally quadratic: When Python is faster than C++
#35I’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 i…
> 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 inefficie…
> For example, D enables a "pointer to immutable data" type, while C does not.
Wait, isn’t that what
const int *x;
Re: Accidentally quadratic: When Python is faster than C++
#36Earlier quoted context omitted.
> 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 inefficie…
> 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.
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.
Re: Accidentally quadratic: When Python is faster than C++
#37Earlier quoted context omitted.
The developer must also be smart enough not to do the mistake to lie to the compiler, by actually doing aliasing with restricted variables as it is UB and nasal dragons beware. C compilers don't validate correct use of restrict.
Not all C compilers handle even correct uses of `restrict` properly. For about three years, Rust has been unable to use the LLVM equivalent of `restrict` when downleveling its references, because it keeps finding LLVM miscompilation bugs around it. 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.
I wonder if these same LLVM issues affect LLVM fortran attempts?
Re: Accidentally quadratic: When Python is faster than C++
#38I’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 i…
> 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 inefficie…
Leading to eye-rolling problems like these: https://github.com/biojppm/rapidyaml/issues/40
Re: Accidentally quadratic: When Python is faster than C++
#39Earlier quoted context omitted.
> 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.
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.
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.
Re: Accidentally quadratic: When Python is faster than C++
#40Earlier quoted context omitted.
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…
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…
Thank you for the good explanation! I'm in embedded and my experience is that this stuff is almost totally ignored in universities. People have to go through a steep and (for us) expensive learning curve until they get the feeling for the whole system and what makes it fast. And then I think, is it asking for too much? Can we expect knowledge about a gazillion layers smeared onto each other from everybody who just wants to deliver value from the topmost layer?