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

201–210 of 215 posts

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

#201

Post by SubjectToChange »

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

Earlier quoted context omitted.

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

> Still, LLVM is a huge dependency to redistribute.

But .NET isn't?

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

#202

Post by josephg »

jfrunyon wrote: post #104
josephg wrote: post #61

Earlier quoted context omitted.

Well said. I've had a lot of conversations with javascript engineers over the years who've argued to me that well tuned JS will be nearly as fast as the equivalent C code. I've written plenty of little toy benchmarks over the years, and in my experience they're partly right. Well written JS code in V8 can certainly run fast - sometimes around half the speed of C code. But a massive performance gap opens up when you u…

More like "well tuned JS will be nearly as fast as poorly tuned C code"...

True. But if I’m given the choice, I’d usually rather well written javascript than badly written C. And there’s a lot more decent JS programmers out there than decent C programmers.

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

#203

Post by a-dub »

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

Earlier quoted context omitted.

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

the pedantry around design and testing in CPAN is where i learned how to be a serious software engineer. perl was special in that it bridged the divide between software engineering and system administration. it was software engineering with the pedantic nature of high strung sysadmins who insisted the garden was in perfect shape at all times.

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

#204

Post by froh »

mehrdadn wrote: post #189
froh wrote: post #113

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

I think the sibling comment may have already answered your question, but if not, I think an earlier response I had might help clarify what exactly I'm comparing & why: https://news.ycombinator.com/item?id=26340952 Note that you do need to read the entire paper to see the overall picture and its consequences; if you stop halfway then it might appear like I'm comparing things unfairly. Feel free to let me know if anyth…

let me rephrase, as I indeed have read the paper, before posting.

1. the lt2 definition in the paper is wrong. A lexicographical compare is linear in the size. the derived cmp2 is correct and has a run time twice that of cmp3. which matches the stl definitions of lexicographical_compare, see below.

2. the c++ behaviour in 2.4.2 is puzzling and most likely bug, worth reporting to and discussing with STL implementors.

https://www.cplusplus.com/reference/vector/vector/operators/

http://www.cplusplus.com/reference/algorithm/lexicographical...

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

#205

Post by mehrdadn »

froh wrote: post #204
mehrdadn wrote: post #189

Earlier quoted context omitted.

I think the sibling comment may have already answered your question, but if not, I think an earlier response I had might help clarify what exactly I'm comparing & why: https://news.ycombinator.com/item?id=26340952 Note that you do need to read the entire paper to see the overall picture and its consequences; if you stop halfway then it might appear like I'm comparing things unfairly. Feel free to let me know if anyth…

let me rephrase, as I indeed have read the paper, before posting. 1. the lt2 definition in the paper is wrong. A lexicographical compare is linear in the size. the derived cmp2 is correct and has a run time twice that of cmp3. which matches the stl definitions of lexicographical_compare, see below. 2. the c++ behaviour in 2.4.2 is puzzling and most likely bug, worth reporting to and discussing with STL implementors.…

> 1. the lt2 definition in the paper is wrong.

Would you mind providing a counterexample to illustrate what incorrect output it's producing?

> A lexicographical compare is linear in the size.

Indeed, lt2() also has a loop that iterates a linear number of times as you mention. It is consistent with this.

> the derived cmp2 is correct and has a run time twice that of cmp3. which matches the stl definitions of lexicographical_compare, see below.

Perhaps you might be confused about what lexicographical_compare does? It does not "compare" in the 3-way sense. It only performs a "less-than" comparison. The name is rather misleading.

2. the c++ behaviour in 2.4.2 is puzzling and most likely bug, worth reporting to and discussing with STL implementors.

I'm not sure what to report to anyone, as I don't find it puzzling; it is entirely consistent with everything I'm aware of and have tried to explain in the paper. It is also not specific to any particular implementation; I believe you will see this behavior on any correct implementation you try it on. It might be helpful if you try to produce a counterexample using what you believe would be a correct & efficient implementation to validate or invalidate this.

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

#206

Post by teddyh »

innocenat wrote: post #42
teddyh wrote: post #39

Earlier quoted context omitted.

You’d think that C could do any appropriate optimizations as well as D, since the C compiler (in theory) should know whether there can exist (in any given program) any writeable pointers to the same value or if there only can exist pointers to const.

Pointer arithmetic would surely make all value mutable. Or even simple array access.

Yes, but the compiler should know if there is any pointer arithmetic present in the code, and whether any such pointer arithmetic could, possibly, result in a pointer pointing to the const data.

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

#207

Post by Const-me »

SubjectToChange wrote: post #201
Const-me wrote: post #164

Earlier quoted context omitted.

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

> Still, LLVM is a huge dependency to redistribute. But .NET isn't?

> But .NET isn't?

Indeed.

.NET runtime takes about 30 MB, or 50 MB if you're on Windows and need desktop components. Links there: https://dotnet.microsoft.com/download/dotnet/5.0

clang+llvm package takes 300-400 MB, that's almost an order of magnitude difference: https://github.com/llvm/llvm-project/releases/tag/llvmorg-11...

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

#208

Post by jcelerier »

Const-me wrote: post #207
SubjectToChange wrote: post #201

Earlier quoted context omitted.

> Still, LLVM is a huge dependency to redistribute. But .NET isn't?

> But .NET isn't? Indeed. .NET runtime takes about 30 MB, or 50 MB if you're on Windows and need desktop components. Links there: https://dotnet.microsoft.com/download/dotnet/5.0 clang+llvm package takes 300-400 MB, that's almost an order of magnitude difference: https://github.com/llvm/llvm-project/releases/tag/llvmorg-11...

> clang+llvm package takes 300-400 MB, that's almost an order of magnitude difference

I ship a statically compiled llvm + clang with my software and it does not add 300-400 mb to the binary at all, only something like 20-30 mb.

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

#209

Post by Const-me »

jcelerier wrote: post #208
Const-me wrote: post #207

Earlier quoted context omitted.

> But .NET isn't? Indeed. .NET runtime takes about 30 MB, or 50 MB if you're on Windows and need desktop components. Links there: https://dotnet.microsoft.com/download/dotnet/5.0 clang+llvm package takes 300-400 MB, that's almost an order of magnitude difference: https://github.com/llvm/llvm-project/releases/tag/llvmorg-11...

> clang+llvm package takes 300-400 MB, that's almost an order of magnitude difference I ship a statically compiled llvm + clang with my software and it does not add 300-400 mb to the binary at all, only something like 20-30 mb.

If you’re willing to compile, ship and support custom builds of .NET runtime, gonna be less than 20-30 MB.

coreclr.dll (the runtime) is 4.9 MB, clrjit.dll (JIT compiler) is 1.3 MB. The rest is mostly standard libraries, the largest piece of that is System.Private.CoreLib.dll at 9 MB. The numbers are for Win64 version of .NET 5.0.2.

Another thing, for .NET apps the runtime is required anyway, the overhead for runtime code generation is zero.

For C++ apps, llvm + clang (or an equivalent) is only needed on developer’s computers, not something you’d normally ship.

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

#210

Post by jcelerier »

Const-me wrote: post #209
jcelerier wrote: post #208

Earlier quoted context omitted.

> clang+llvm package takes 300-400 MB, that's almost an order of magnitude difference I ship a statically compiled llvm + clang with my software and it does not add 300-400 mb to the binary at all, only something like 20-30 mb.

If you’re willing to compile, ship and support custom builds of .NET runtime, gonna be less than 20-30 MB. coreclr.dll (the runtime) is 4.9 MB, clrjit.dll (JIT compiler) is 1.3 MB. The rest is mostly standard libraries, the largest piece of that is System.Private.CoreLib.dll at 9 MB. The numbers are for Win64 version of .NET 5.0.2. Another thing, for .NET apps the runtime is required anyway, the overhead for runtime…

> For C++ apps, llvm + clang (or an equivalent) is only needed on developer’s computers, not something you’d normally ship.

unless you want to JIT-compile C++ code at runtime which is the original point.

Post reply on HN