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

161–170 of 215 posts

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

#161

Post by masklinn »

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"?

> Why is the default set implementation ordered in the first place?

"Sorted" rather than ordered (an order can be arbitrary and I'd personally associate the word with insertion order).

> The formal data structure is unordered

The formal data structure doesn't have complexity bounds, the STL does.

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

#162

Post by Kranar »

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.

Technically is a very valid opinion if you're writing software that needs to be robust and secure in the face of user input. std::set is guaranteed to be logarithmic strictly in the number of comparisons in the worst case without exception.

std::unordered_set has some very difficult to reason about worst case scenarios that must factor in both the size of the collection and the hash function. Unless you are very careful about the type of hashing you use, you can easily be vulnerable to DDOS attacks that scale on the order of O(k * n) for key size k and container size n.

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

#163

Post by bobbylarrybobby »

brundolf wrote: post #154

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

See this comment and children: https://news.ycombinator.com/item?id=26340233

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

#164

Post by Const-me »

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

Earlier quoted context omitted.

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

Interesting, I didn’t know llvm is that flexible.

Still, LLVM is a huge dependency to redistribute. And probably has many points of failure. For instance, I expect you gonna need to watch for INCLUDE and PATH environment variables when using that thing.

In .NET everything is in the standard library. The generated code is even platform-independent, for no additional overhead. Here’s couple non-trivial examples: https://github.com/Const-me/ComLightInterop/blob/master/ComL... https://github.com/Const-me/ComLightInterop/blob/master/ComL...

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

#166

Post by nneonneo »

Hang on, this isn't accidentally quadratic, this is accidentally exponential in the worst case. If you set the tree branching factor to one, then the running time of C++‘s std::less becomes 2^h, but there’s only h nodes.

Demo: https://ideone.com/CBIEAE

This creates ~60 objects, but takes something like 2^30 operations to resolve (it times out on this online runner, and takes around 5s on my laptop with -O3).

That's much worse than claimed in this paper! An accidentally-exponential algorithm is the kind of thing that makes DoS attacks trivial...

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

#167

Post by btilly »

Leo_Verto wrote: post #112
btilly wrote: post #27

Earlier quoted context omitted.

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.

That sounds right.

I wonder what the current split is. I'm not in HPC computing, but I see a lot of posts about how quickly Julia is being adopted.

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

#168

Post by mannerheim »

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"?

Probably because the underlying implementation is a binary search tree which requires a comparison operator. Haskell likewise has Data.Set which requires an Ord instance. There's HashSet which requires a Hashable instance which can be automatically derived for any data type, so in principle you don't need ordering, but I would imagine in C++ you would have to provide your own hashing function from whatever data type you're trying to put in a hash set.

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

#169

Post by cb321 »

kllrnohj wrote: post #143
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 rare…

This seems oriented around just code bases you have seen personally rather than fundamental C limitations and so misleads. To clarify: C can do template-like macros for type specialization (and this is common in some code bases) and easier to debug ways [1] { I've personally used a variant of [1] techniques since the mid 90s }. C can do setjmp & longjmp exceptions and you can even do a TRY/CATCH like exception macros. Function pointers are in stdlib interfaces (e.g. qsort) and generally pretty common in C code. I believe gcc has been able to inline through C function pointers ("de-virtualize", though you qualify with "really" there..) in the same translation unit for like 2 decades now with the right compiler flags/annotations.

It is true that C cannot do full template meta-programming or certain state save/restore optimizations faster than setjmp/longjmp. Hard/painful/trivial are all a bit more subjective and relative to exposure/practice/training/etc.

Personally, I think Nim [2] is a much friendlier way to go than either C++ or Python without the pitfalls of either, but the ecosystem is admittedly much smaller. Also, I've yet to hit something where re-writing the C++/Rust in Nim did not speed things up from "at least a little" to "quite a bit". { This is more an artifact of "performance incautious programming" in the C++/Rust. Too many people fall into the trap that, since a language has a reputation for speed, they don't need to think. This is probably largely why @mehrdadn's original article had the title it did. ;-) }

[1] https://github.com/glouw/ctl/

[2] https://nim-lang.org

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

#170

Post by namibj »

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

I'll give Terra[0] as an example for something relatively high-level that uses LLVM as a JIT. It can also be used as an AoT compiler with fancy macro stuff in place of the C preprocessor.

[0]: http://terralang.org/

Post reply on HN