Accidentally quadratic: When Python is faster than C++ • Hacker News Board

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

#121

Post by shultays » Thu, Mar 04, 2021, 1:40 PM UTC

mehrdadn wrote: post #98

einpoklum wrote: post #95

Earlier quoted context omitted.

1. People often use set instead of unordered_set (and same for map) despite not needing order. This slows things down. 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., i…

Ordering is not the only concern here. std::set actually provides a logarithmic worst-case guarantee, whereas std::unordered_set does not. This is a factor to consider depending on the application, regardless of whether ordering is necessary. Whichever one prefers in any case, though, is beside my point—I'm merely trying to use trees and hashtables to illustrate a far more general CS phenomenon that can occur in lots…

Imho "but technically..." is not a valid opinion while in practice the access is O(1) on average. Yea sure, it becomes linear if your hash is "return 42;", it can't grantee that you supplied a good hasher.

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

#122

Post by Measter » Thu, Mar 04, 2021, 1:58 PM UTC

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…

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

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

#123

Post by majjgepolja » Thu, Mar 04, 2021, 1:59 PM UTC

shultays wrote: post #121

mehrdadn wrote: post #98

Earlier quoted context omitted.

Ordering is not the only concern here. std::set actually provides a logarithmic worst-case guarantee, whereas std::unordered_set does not. This is a factor to consider depending on the application, regardless of whether ordering is necessary. Whichever one prefers in any case, though, is beside my point—I'm merely trying to use trees and hashtables to illustrate a far more general CS phenomenon that can occur in lots…

Imho "but technically..." is not a valid opinion while in practice the access is O(1) on average. Yea sure, it becomes linear if your hash is "return 42;", it can't grantee that you supplied a good hasher.

It's not technically. Worst-case guarantee is required for some applications. Hash Maps have better amortized complexity but some implementations have bad worst case time.

Java uses balanced trees instead of linked list in their chained-hashtable implementation, if I recall correctly.

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

#124

Post by pjmlp » Thu, Mar 04, 2021, 2:00 PM UTC

piker wrote: post #117

PixyMisa wrote: post #84

Earlier quoted context omitted.

4) string concatenation

Probably (1) above, no?

NULL terminated strings are quite bad for performance, because you need to transverse them to find the terminator.

Now try to concatenate a bunch of them in C.

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

#125

Post by nivenkos » Thu, Mar 04, 2021, 2:01 PM UTC

mehrdadn wrote: post #26

If you're wondering whether this is a theoretical or practical problem: I actually observed some of this effect in practice first, and only after thinking about it for a while did the larger issue (and the complexity implications) dawn on me. I had something like a set or a set > (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…

By the way for the hashing example in count() - Rust has the Entry API for HashMaps to avoid exactly this problem: https://doc.rust-lang.org/std/collections/struct.HashMap.htm...

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

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

#126

Post by majjgepolja » Thu, Mar 04, 2021, 2:03 PM UTC

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

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

#127

Post by pkolaczk » Thu, Mar 04, 2021, 2:07 PM UTC

Const-me wrote: post #107

pkolaczk wrote: post #92

Earlier quoted context omitted.

> They only need to do that for the hot paths, that’s often a small portion of the code. 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, wh…

I think what you wrote largely applies to Java and especially JavaScript, much less to C#. Value types, real generics, and native stack allow even the faster version of the .NET JIT to produce native code that’s not too horrible performance wise. 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…

I was talking about JITs in general. Sure, you can AOT-compile .NET code quite efficiently, but then this is a different story.

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!

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

#128

Post by tachyonbeam » Thu, Mar 04, 2021, 2:15 PM UTC

lmm wrote: post #64

tachyonbeam wrote: post #19

Earlier quoted context omitted.

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…

C doesn't tell you anything about your cache efficiency, which is to first order the only thing that affects your program's performance. 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…

I'm not arguing that C is the ultimate programming language for maximum performance or anything like that. Simply that it gives you a lot more freedom to tune your implementation where it matters for performance.

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.

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

#129

Post by tachyonbeam » Thu, Mar 04, 2021, 2:21 PM UTC

MaxBarraclough wrote: post #108

tachyonbeam wrote: post #19

Earlier quoted context omitted.

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…

> You would have to prove that integer values lie within certain ranges (hard) 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?

Sometimes you can prove that values will remain integer when iterating over array indices for example. However, in the general case, when doing integer additions or multiplications, they need to insert dynamic integer overflow check instructions everywhere. When the integers would overflow they have to be converted to floating-point values.

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

    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.

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

#130

Post by tachyonbeam » Thu, Mar 04, 2021, 2:26 PM UTC

Const-me wrote: post #70

tachyonbeam wrote: post #19

Earlier quoted context omitted.

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…

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

> In C# you can make data structures which [...]

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.