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

151–160 of 215 posts

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

#151

Post by einpoklum »

cesarb wrote: post #116
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…

> People often use set instead of unordered_set (and same for map) despite not needing order. This slows things down. Aren't unordered_set and unordered_map quite new (IIRC, they came only with C++0x)? For most of C++'s history, if you preferred to use the standard library, what you had was only ordered sets and maps.

By now, this is no longer "quite new". A recent C++ community survey suggests that under 10% of developers currently use C++98/C++03 the most. Naturally this is not a valid sample of the whole userbase, but it's a good indication.

Also, in 2005 IIANM, Google published their dense and sparse hash map implementations, which were fast-ish and quite usable.

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

#152

Post by Symmetry »

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…

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.

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

#153

Post by [deleted] »

attractivechaos wrote: post #136
froh wrote: post #113

If I read the paper correctly, then it compares three-way comparison with two two-way comparisons, for a recursively defined (tree) data type. The paper points out that the convenience of just defining "less than", and heaving "equals" derived from that can be costly. Specifically, for the recursively defined data structure (tree), a three-way comparison which is derived canonically from the two way compare seems to…

Initially I thought this preprint is a click bait (sorry, author), but when I read into details, I realize it is an interesting one. The key observation is the code under section 2.4.2. There, the author triggers the worse case (everything being equal in two trees) and shows that C++'s lt2 behavior leads to its horrible performance: 4.1s in C++ vs 0.018s in Python. Note that the difference is much more than two folds…

[deleted]

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

#154

Post by brundolf »

Reminds me of the sscanf thing that popped up a few days ago (in fact I assumed this was about that at first): https://news.ycombinator.com/item?id=26302744

I wonder (genuinely asking, not being snarky) what it is about C/C++ that seems to make these issues more common? It's also possible my perception of "more common" has just been inflated by seeing multiple examples in a single week

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

#155

Post by brundolf »

einpoklum wrote: post #95
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…

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…

Why is the default set implementation ordered in the first place? The formal data structure is unordered, which probably informs people's assumptions about its performance characteristics. Should it not be "set" and "ordered_set"?

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

#156

Post by lorenzhs »

Measter wrote: post #122
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…

Something like this? 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.... Similarly, saturating_sub seems like it can be implemented with __builtin_sub_overflow.

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

#157

Post by Const-me »

tachyonbeam wrote: post #130
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…

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

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

That’s correct. But at the same time, the language is way higher level than C or C++.

> experienced C# programmer can probably write code that runs circles performance-wise around code written by an experienced JS/Python developer in most cases.

In some cases, an experienced C# programmer can even write code which approaches or outperforms C. My Linux video player library https://github.com/Const-me/Vrmac/tree/master/VrmacVideo#per... uses CPU on par with VLC, and 20% less RAM.

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

#158

Post by zlynx »

varajelle wrote: post #131
pjmlp wrote: post #124

Earlier quoted context omitted.

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.

C++ code usually use std:: string, std::string_view, or other string classes that stores the string size and has some capacity pre-allocated to avoid such issues.

Profiling is essential. I found a performance bug in calling some C++ functions a while ago, because they accepted a const std::string& and were being called in loops with a C const char*. Every single call had to construct a std::string involving a strlen, allocation and copy.

std::string_view is a nice fix for this but few programmers seem to use it yet.

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

#159

Post by jcelerier »

Const-me wrote: post #150
jcelerier wrote: post #132

Earlier quoted context omitted.

LLVM can just put the compiled code at some place in your ram and then you can just execute it

Processors need addresses of things. Look at the following code https://godbolt.org/z/PYEqKn note the function uses another symbol, “func.counter”. Shared libraries include relocation tables https://en.wikipedia.org/wiki/Relocation_%28computing%29 with all code locations which needs patching. That’s how the OSes can load them into arbitrary locations in memory and the code will still work.

... yes ? https://github.com/weliveindetail/JitFromScratch

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

#160

Post by hashingroll »

brundolf wrote: post #155
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…

Why is the default set implementation ordered in the first place? The formal data structure is unordered, which probably informs people's assumptions about its performance characteristics. Should it not be "set" and "ordered_set"?

One reason would be because std::set guarantees O(log n) complexity for each operation on the worst case. std::unordered_set has average complexity O(1) and O(size) for the worst case (it being a hash table) which can be unexpected to debug in those rare cases.
Post reply on HN