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

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

#141

Post by imtringued » Thu, Mar 04, 2021, 3:16 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…

Actually, action for action managed languages tend to be "faster" than C in the sense that writing the equivalent program would be slower in C. However, the additional freedom leads to increased program complexity and that complexity eats into the performance budget enough to end up slower than "idiomatically" written C where the developer distilled the solution to its bare essence.

Javascript has the fastest general purpose hashmap/dictionary implementation of all programming languages but at the same time you are forced to use them all the time which overall slows the language down. Writing exactly the same code in C would be even slower since C hashmaps aren't as optimized. However, C code is rarely written like that so it's usually faster.

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

#142

Post by asdfasgasdgasdg » Thu, Mar 04, 2021, 3:21 PM UTC

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.

They've been in the language for about a decade now, and before that we had the tr1 hash_map classes that were available in most environments.

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

#143

Post by kllrnohj » Thu, Mar 04, 2021, 3:21 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…

Easily. C++ has ways of being faster that C can't really match - namely, templates. They can be hellish to write & debug, but generating type-specific functions is fantastic for optimization & performance. It's also a lot easier to be faster in C++ on key things than it is in C, specifically small-size optimizations. Yes you can do an SSO string or function pointer in C, but it's hard & painful to do so, so it's rarely if ever done. But it's trivial to do in C++, and since the standard library does it for both strings & functions, it's also commonly done.

Similarly in languages like Java or C#, having first-class exceptions means fewer branches & error checking on the hot path over something like C. They are on the whole slower than C for other reasons, but it's not because C is "the best" or "the fastest" at everything. And of course you can't really do de-virtualization optimizations in C.

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

#144

Post by frankus » Thu, Mar 04, 2021, 3:23 PM UTC

Here’s an article from 2001 discussing a very similar issue: https://www.joelonsoftware.com/2001/12/11/back-to-basics/

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

#145

Post by owl57 » Thu, Mar 04, 2021, 3:24 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.

Note that this isn't just some user-supplied bad hashers. Hash for std::string in GNU library is not much harder to hack for collisions than your example. And also it uses the whole string, so is slow on long strings. I didn't investigate if other implementations of STL are any better.

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

#146

Post by harveywi » Thu, Mar 04, 2021, 3:31 PM UTC

pjmlp wrote: post #124

piker wrote: post #117

Earlier quoted context omitted.

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.

>you need to traverse them to find the terminator.

Why not just do a binary search through the entire 256TB virtual memory space, finding the largest memory address that doesn't segfault? :-)

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

#147

Post by teddyh » Thu, Mar 04, 2021, 3:34 PM UTC

tick_tock_tick wrote: post #97

teddyh wrote: post #49

Earlier quoted context omitted.

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

Nah const is fun int main() { const int world = 42; const const const int const const * const const hello = &world; return 0; } Is a valid program https://onlinegdb.com/SJcwJrRzd

Sure, but those extra “const” do not mean anything, and are apparently ignored by the compiler.

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

#148

Post by leecarraher » Thu, Mar 04, 2021, 3:44 PM UTC

This is a pretty clickbaity title in my opinion. Bubble sort in lower level language X is going to be slower than quick sort in high level language Y. And bubblesort in high level language is going to be faster than merge sort for small data sets on low level language X. If you aren't comparing the same underlying routine, or data application, I don't think any conclusion should be made. Comparisons between languages is exactly why asymptomatic analysis was devised. Extract the process from the low level and hardware characteristics, and get the overall complexity growth. But this doesn't work the other way around. You can't compare different routines in different languages and expect big oh to be comparable.

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

#149

Post by brundolf » Thu, Mar 04, 2021, 3:50 PM UTC

leecarraher wrote: post #148

This is a pretty clickbaity title in my opinion. Bubble sort in lower level language X is going to be slower than quick sort in high level language Y. And bubblesort in high level language is going to be faster than merge sort for small data sets on low level language X. If you aren't comparing the same underlying routine, or data application, I don't think any conclusion should be made. Comparisons between languages…

The problem is that a language isn't just its speed, a language is a UX. If that UX makes it easier to accidentally make performance mistakes, then practically speaking, things written in that language are slower than they would be otherwise.

Edit: The original title "Why Python is faster than C++" is much more clickbaity than the editorialized ("When Python is faster than C++")

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

#150

Post by Const-me » Thu, Mar 04, 2021, 3:53 PM UTC

jcelerier wrote: post #132

Const-me wrote: post #88

Earlier quoted context omitted.

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

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.