Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Accidentally quadratic: When Python is faster than C++

arxiv.org

Post reply on HN
Print view View original

41–50 of 215 posts

Re: Accidentally quadratic: When Python is faster than C++

#41

Post by knome »

WalterBright wrote: post #36
teddyh wrote: post #35

Earlier 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.

    const int world = 42;
    const int const * const hello = &world ;
Apparently, you can be very const and `gcc -Wall -Wextra -std=c99` won't raise any complaints.

Re: Accidentally quadratic: When Python is faster than C++

#42

Post by innocenat »

teddyh wrote: post #39
WalterBright wrote: post #36

Earlier quoted context omitted.

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.

Pointer arithmetic would surely make all value mutable. Or even simple array access.

Re: Accidentally quadratic: When Python is faster than C++

#43

Post by m_mueller »

kevin_thibedeau wrote: post #12
wvenable wrote: post #7

Earlier quoted context omitted.

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.

The restrict keyword helps with this.

That, or switching to FORTRAN. For numeric / HPC it is much easier to get a decently fast implementation there.

Re: Accidentally quadratic: When Python is faster than C++

#44

Post by marton78 »

teddyh wrote: post #39
WalterBright wrote: post #36

Earlier quoted context omitted.

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.

Only inside the same compilation unit.

Re: Accidentally quadratic: When Python is faster than C++

#45

Post by cbsmith »

tachyonbeam wrote: post #19
rz2k wrote: post #13

Earlier 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…

The sufficiently smart compiler is effectively unobtanium, but that presents a challenge for C as well. C has its own challenges with its memory model & language semantics.

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.

Re: Accidentally quadratic: When Python is faster than C++

#46

Post by coldtea »

halayli wrote: post #31

How can this paper be taken seriously when the paper doesn't even show the compilation flags?

Perhaps because the paper is not about the specifics of the incident (which is menial work to figure out, left as an exercize to the header) but the fact that it can happen and a general explanation of the circumstances?

Re: Accidentally quadratic: When Python is faster than C++

#47

Post by flohofwoe »

IgorPartola wrote: post #2

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 i…

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).

Re: Accidentally quadratic: When Python is faster than C++

#48

Post by coldtea »

mhh__ wrote: post #17
IgorPartola wrote: post #2

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 i…

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 c…

>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.

Re: Accidentally quadratic: When Python is faster than C++

#49

Post by teddyh »

knome wrote: post #41
WalterBright wrote: post #36

Earlier quoted context omitted.

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.

const int world = 42; const int const * const hello = &world ; Apparently, you can be very const and `gcc -Wall -Wextra -std=c99` won't raise any complaints.

Firstly, isn’t that a syntax error? There’s a stray “const” in there. You probably meant

  const int * const hello = &world;
Secondly, what should the compiler complain about? You have a const int, and then a const pointer to const int, pointing to that first const int. What’s the problem?

Thirdly, the latest C version supported by GCC is “-std=c17”.

Post reply on HN