The code doesn't compile, i.e. is in the broken state. The author is missing the comparison operators.
Accidentally quadratic: When Python is faster than C++
111–120 of 215 posts
Re: Accidentally quadratic: When Python is faster than C++
#112I’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…
FORTRAN is faster for many tasks, and is probably more popular in high performance computing. Also tasks that can be moved to the GPU go a lot faster. You can interact with those programs in C, but not natively. But some languages, like Julia, can easily move calculations to/from the GPU. And also can transparently take advantage of parallelism. Julia is in the process of growing rapidly for high performance computin…
To add onto your point: from what I've heard the split at HPC conferences is about 40% C to 60% Fortran.
Re: Accidentally quadratic: When Python is faster than C++
#113If 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 entail not a linear but an quadratic number of comparisons.
What I don't understand is what is happening in 'lt2'.
this is what I'd expect for __lt__
lt(a, b) also known as (a __lt__ b) is returning
True, iff a (a __eq__ b) iff not (a __lt__ b) and not (b __lt__ a)
cmp(a, b) = lt(a, b) - lt(b, a)
a 1
b -1
a == b: 0 - 0 ==> 0
Now two questions arise with respect to the presented hypothesis and the paper:
1. why does the paper call lt2 twice, recursively?
2. why does the paper compare the performance of their lt2 and lt3 instead of the performance of cmp2 and cmp3?
I intuit, when taking the double recursion out of lt2, which imnsho is erroneous, and when comparing cmp2 and cmp3, we'll see a performance penalty of a factor 2, between cmp2 and cmp3, and identical run times for lt2 and lt3, as it should be.
What am I missing?
edit: updated for clarity
Re: Accidentally quadratic: When Python is faster than C++
#114Earlier 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 ;)
You might be right but if it's just a technicality and in practice nobody uses restrict the way you said, would anyone care about the theoretical superiority of C? I'm sure some would, but they wouldn't be the majority.
Re: Accidentally quadratic: When Python is faster than C++
#115I’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…
> 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…
Let’s be careful here. All these languages are Turing complete. Heck, isn’t CSS Turing complete now? But insofar as goto in C produces a certain small amount of CPU instructions (1? 2?), can all those other higher level languages do the same? Or will something like JavaScript need a callback-based solution that will do several pointer lookups, memory allocation, etc?
Re: Accidentally quadratic: When Python is faster than C++
#116If 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…
> 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.
Re: Accidentally quadratic: When Python is faster than C++
#117cpython 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
Probably (1) above, no?
Re: Accidentally quadratic: When Python is faster than C++
#118I’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…
I've thought about this very question for years. My answer has been, usually, "no" for all cases that do not allow the developer to write straight assembly.
That is, until things like C++'s stackless coroutines came about, which are a construct intrinsic to the compiler and not functionality directly exposed by C.
Further, any machine code language is going to allow you specific instruction access that a compiler might not otherwise utilize (rare, but it happens). In such cases you can gain 'manual' speedups over what C could allow you to do. I would hope that is the obvious exception, however.
But you are asking a very good question not a lot of developers are willing to think much about.
Re: Accidentally quadratic: When Python is faster than C++
#119Earlier quoted context omitted.
> 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…
I think the point of the parent is that in principle you can always implement those optimizations by hand in C although it might of course be impractical.
If you go down this road then you can always drop down to assembler to be even faster than C.
I don't think this is a reasonable argument. Every Turing compatible language that gives you direct access to the metal, so to speak, provides you with the opportunity to implement these optimization by hand.
I think it's much better to look at average C code there. And then C has a tremendous advantage with their compiler support. C compilers have decades of optimization put into them. This will take a while for other languages to catch up to that.
Re: Accidentally quadratic: When Python is faster than C++
#120Earlier 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…
[deleted]