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

191–200 of 215 posts

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

#191

Post by mehrdadn »

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.

There are lots of reasons to prefer trees (and, correspondingly, lots of reasons to prefer hashtables); I just pointed out ordering isn't the only one, and I merely gave another (worst-case performance guarantee). For example, yet another one is iterator stability; insertion can invalidate iterators for unordered containers, making them useless for some applications that need to analyze data efficiently as they insert.

I could go on, but it's very much detracting from the point of the paper to argue about the data structure choice when the paper isn't on this topic at all or trying to analyze any particular application to begin with.

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

#192

Post by WalterBright »

bhaak wrote: post #187
WalterBright wrote: post #182

Earlier quoted context omitted.

The three D compilers use, the GCC backend, the LLVM backend, and the Digital Mars backend. All the decades of optimization in them are taken advantage of by D. If you write C-style code in D, you'll get the same code generated as if your wrote it in C.

But isn't that a consequence of D "mimicking" C to some extent? Disclaimer, my compiler background was the Java compiler and its bytecode generation but I would expect both gcc and clang/llvm to have lots of optimization cruft hardcoded for how C programs are written. If you deviate from that, you get potentially less well optimized code.

> But isn't that a consequence of D "mimicking" C to some extent?

It's true that multi-language backends will inevitably cater to the semantics of the dominant language.

For a related example, I discovered that gdb doesn't pay much attention to the DWARF symbolic debug spec. It pays attention to the particular way gcc generates symbolic debug info. Other patterns, while compatible with the spec, don't work with gdb. Similar problems have happened with linkers.

It's a matter of "do as I do, not as I say".

Since I am the author of DMD's backend, I've been putting in optimizations that do cater to D, rather than just C and C++. For example, in the last few days I started putting in optimizations to take advantage of D's new "bottom" type:

https://github.com/dlang/dmd/pull/12245

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

#193

Post by lorenzhs »

Measter wrote: post #177
lorenzhs wrote: post #156

Earlier quoted context omitted.

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.

Would those work on any compiler, or are they compiler-specific? If those are non-standard compiler-specific extensions, not even a library, is it truly a part of C++? While I'll grant that Rust only has one fully functional compiler at this time, those functions have been part of Rust's corelib since 1.0. Any Rust compiler would have to support them.

They're not part of the standard, but gcc, clang, and icc (Intel) support them. Alternatively, you could emit the correct instructions in an asm block on supported architectures (x86: 'jo'/'jno' for jumps, 'cmovo'/'cmovno' for conditional moves [1]) or reimplement the operations in software [2]

[1] https://www.felixcloutier.com/x86/jcc and https://www.felixcloutier.com/x86/cmovcc

[2] https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensur....

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

#194

Post by mcguire »

asdfasgasdgasdg wrote: post #142
cesarb wrote: post #116

Earlier quoted context omitted.

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

C++: the language that's been around for 40 years and is completely new!

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

#195

Post by mehrdadn »

brobdingnagians wrote: post #171

Very interesting. I think it makes C++ come across looking quite good. The committee has considered a case where C++ comparisons are lacking, and C++20 rectifies the situation by having more expressive comparisons with partial and total orderings. C++ may be slower than other languages in doing innovations, but they move relentlessly forward with trying to adopt a good way of accomplishing new features & rectifying m…

C++20 doesn't quite rectify this unfortunately! The data structures still use std::less even in C++20, meaning the 2-way comparisons would happen twice. Except now each 2-way comparison is potentially implemented on top of 3-way comparisons. Perhaps I or someone else should get in touch with the committee to try to change that, otherwise things are going to be slower rather than faster if we still use 2-way comparisons but now they have to do 3-way comparisons underneath!

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

#196

Post by WalterBright »

gpderetta wrote: post #105
WalterBright wrote: post #24

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

> in principle you can always implement those optimizations by hand in C

Some things, like integral promotion rules, you can't get around. You may know that the promotion can be skipped in certain cases, but the compiler cannot know it.

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

#197

Post by ColFrancis »

sgtnoodle wrote: post #65
offtop5 wrote: post #5

Earlier quoted context omitted.

I think about programming languages like I do cars. While rust may be a Ferrari, some kid who doesn't know how to drive a stick and has only had his license for about a month is going to have a rough time beating you driving from New York to Texas even if you're driving a Corolla. I consider myself to be an extremely good software engineer, but lower level programming languages scare me. Recently I've been riding a l…

I mainly write embedded software in C and C++, but I tend to use python for non-embedded stuff. The funny thing is that I've attempted to speed up multiple python scripts by replacing lists of floats with numpy arrays, and each time it's ended up slightly slower. I suspect numpy only really starts to pay off when you're doing the same operations to 1000+ elements. For modest data sets, or algorithms that don't map pa…

Just checking, even though you likely know. The numpy arrays really only pay off when you vectorise your calculations. Don't expect any speed up if you're still using list comprehensions.

A vector operation is just where instead of having two lists, U and V which add to make W = [x+y for x,y in zip(U,V)] you directly operate on the arrays, W = U + V.

This allows the inner loop to be completely in native code. Sometimes some curious things happen where it's easier to do more vector operations resulting in more looping just because each of those operations is a vector operation and so is faster than the loop. For example, increment a number every time you see a particular element (time series breaking out subsequences) might look like np.cumsum(U == value) which is two loops in practice, but much faster than the iterative approach.

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

#198

Post by acdha »

a-dub wrote: post #184
acdha wrote: post #135

Earlier quoted context omitted.

I think a key part here is also being realistic about the time available to write and optimize your program. I’ve seen Python completely crush C++ a fair number of times (order of magnitude or better) and it basically came down to the C++ programmer having bitten off more than they could chew, spending so much time on the basics that they never got around to optimizing algorithms or the data layout. (One variation: P…

yeah, the c/c++ ecosystem never really had the benefit of a internet connected curated library community. afaik the first big example of that was perl in the late '90s. CPAN was awesome: here's this big library of awesome libraries that have been curated with full tests and documentation that you can search and add to your system with a few easy cli invocations. (for the uninitiated, this was npm or pip for perl in t…

CPAN definitely deserves more attention, especially for the emphasis on testing which many successors still don't have. That was even more necessary back when OS consistency was worse but it really should have been seen as a first-class feature.

I think C/C++ also had this problem with the whole cultural evolution around shared libraries. Because installs were non-trivial I think there was an almost subconscious blinder effect where people restricted themselves to what shipped with the OS / distribution even if that meant keeping a workaround for a bug which had been fixed upstream years before because that was seen as better than static linking or bundling a newer version.

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

#199

Post by SubjectToChange »

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.

In my limited experience, almost every language specific presentation at an HPC conference is about C++. New projects and initiatives like DPC++, SYCL/oneAPI, Ginkgo, etc are C++ based. And if you look at the open source libraries of the national laboratories, e.g. LLNL, C++ libraries are more common than C libraries, which in turn are more common than the Fortran libraries.

If anything I'd say that C++ is the default for HPC conferences.

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

#200

Post by lmm »

tachyonbeam wrote: post #128
lmm wrote: post #64

Earlier quoted context omitted.

C doesn't tell you anything about your cache efficiency, which is to first order the only thing that affects your program's performance. You're right that flat datastructures are important, but C is far from the only language that can offer those. I don't think C can ever be the answer; "comparable C code", i.e. code that was produced with the same amount of developer effort, is almost always undefined behaviour that…

I'm not arguing that C is the ultimate programming language for maximum performance or anything like that. Simply that it gives you a lot more freedom to tune your implementation where it matters for performance. For HPC, you'd likely be better with something designed to run on GPUs, with built-in primitives for matrix operations, and a compiler that can tune the way those operations get implemented for you. However,…

> However, when it comes to cache locality, if the C programmer knows what they are doing, I think you'll have a very hard time beating them with Haskell or ML.

A programmer who knows what they're doing is a rare thing indeed. On actual business problems with real-world programmers Haskell consistently beats C, IME.

> AFAIK those languages have the same pointer-chasing issues I've described earlier.

There's a pragma to flatten strict record fields, or a compiler flag to do that by default (at least in GHC).

Post reply on HN