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

81–90 of 215 posts

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

#81

Post by adrianN »

flohofwoe wrote: post #52
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.

Isn't that what 'restrict' is for? It's a new type of footgun of course because the compiler doesn't detect if the value is actually accessed through another pointer, but by simply ignoring that possibility via 'restrict', the compiler should have the same optimization opportunities, no?

restrict is used so rarely in C code that the Rust team hit a lot of bugs when they tried to give LLVM all the aliasing info the Rust compiler has.

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

#82

Post by jcelerier »

Const-me wrote: post #66
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…

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

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

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

#83

Post by thaumasiotes »

jcelerier wrote: post #79
thaumasiotes wrote: post #76

Earlier quoted context omitted.

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

> One obvious approach would be to emit code that implements a C runtime. how could you negate the python interpreter startup time though ?

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.

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

#84

Post by PixyMisa »

a-dub wrote: post #63

cpython is faster than c++ under the following circumstances: 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'…

4) string concatenation

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

#85

Post by petertodd »

jcelerier wrote: post #80
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.

> In D, `immutable(int)* x` cannot be changed by any reference to the value. even if I use a magnetic needle to change the bits in my RAM ? :)

There's an easy answer to that: using a magnetic needle to change the bits in your RAM violated the assumptions of the compiler, leading to undefined behaviour. What exactly will happen in that circumstance is just that: undefined.

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

#86

Post by Const-me »

pkolaczk wrote: post #78
Const-me wrote: post #70

Earlier quoted context omitted.

> Inlining is actually non-trivial. 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, Jav…

> JIT runtimes have more input data than a C compiler 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.

> They can't apply costly analysis to these data because they need to compile fast.

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.

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

#87

Post by mehrdadn »

Lvl999Noob wrote: post #73
josalhor wrote: post #53

Earlier quoted context omitted.

To be fair, certain compilation flags can change the time complexity of some algorithms if the mistake is trivial enough to figure out.

Really? Can you give some examples? I know compilers are amazing but this seems too much.

At least GCC was (and by now Clang and probably others are) known for occasionally optimizing out certain uses of functions like strlen(), which can change the time complexity in some trivial cases.

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.

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

#88

Post by Const-me »

jcelerier wrote: post #82
Const-me wrote: post #66

Earlier quoted context omitted.

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

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

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.

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

#90

Post by Omin »

flohofwoe wrote: post #55
WalterBright wrote: post #54

Earlier quoted context omitted.

> but by simply ignoring that possibility via 'restrict', 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.

Well yeah, sure. I wasn't picking on D, just pointing out that C offers an escape hatch, no matter how dangerous that might be ;)

restrict is so rarely used that clang has had open code generation bugs for years. Rust would like to use its non-aliasing guarantees to generate better code, but clang is unable to reliably generate correct code.

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.

Post reply on HN