Accidentally quadratic: When Python is faster than C++

Post by kllrnohj » Thu, Mar 04, 2021, 11:45 AM 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…

Post by galangalalgol » Thu, Mar 04, 2021, 12:19 PM UTC

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

Post by gpderetta » Thu, Mar 04, 2021, 12:25 PM UTC

WalterBright wrote: post #24

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? Sure, in any language that provides more semantic information than C does. For example, D enables a "pointer to immutable data" type, while C does not. This can improve optimization. On a pragmatic note, C makes it easy to use 0-terminated strings, and clumsy to use length-terminated strings. The natural result is people use 0-terminated strings. 0-terminated strings are inefficie…

Post by Const-me » Thu, Mar 04, 2021, 12:28 PM UTC

pkolaczk wrote: post #92

Const-me wrote: post #86

Earlier quoted context omitted.

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

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

Post by bregma » Thu, Mar 04, 2021, 12:33 PM UTC

schot wrote: post #72

adgjlsfhk1 wrote: post #20

Earlier quoted context omitted.

Goto considered harmful is from 1968, so yes.

A minor historical note on this: the original title of Dijkstra's text was "A Case Against the Goto Statement" and it was the Communications of the ACM editor (Niklaus Wirth) that changed it[0]. [0]: https://en.wikipedia.org/wiki/Considered_harmful