Accidentally quadratic: When Python is faster than C++ • Hacker News Board

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

#51

Post by johncolanduoni » Thu, Mar 04, 2021, 7:41 AM UTC

cozzyd wrote: post #37

Arnavion wrote: post #32

Earlier quoted context omitted.

Not all C compilers handle even correct uses of `restrict` properly. For about three years, Rust has been unable to use the LLVM equivalent of `restrict` when downleveling its references, because it keeps finding LLVM miscompilation bugs around it. These LLVM bugs don't get noticed with C because C programs rarely use `restrict` as pervasively as a downleveled Rust program ends up doing.

I wonder if these same LLVM issues affect LLVM fortran attempts?

I feel like they would have to, if they were to produce a remotely competitive compiler. That's why I'm hoping NVidia's Flang[1] efforts will lead to this aspect of LLVM being cleaned up.

[1]: https://github.com/flang-compiler/flang

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

#52

Post by flohofwoe » Thu, Mar 04, 2021, 7:46 AM UTC

WalterBright wrote: post #36

teddyh wrote: post #35

Earlier quoted context omitted.

> For example, D enables a "pointer to immutable data" type, while C does not. Wait, isn’t that what const int *x; does? I.e. a pointer to a constant.

In C, the value pointed to by `x` cannot be changed via a write through `x`, but if there is another pointer to that value, it can be changed through that. In D, `immutable(int)* x` cannot be changed by any reference to the value.

Isn't that what 'restrict' is for? It's a new type of footgun of course because the compiler doesn't detect if the value is actually accessed through another pointer, but by simply ignoring that possibility via 'restrict', the compiler should have the same optimization opportunities, no?

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

#53

Post by josalhor » Thu, Mar 04, 2021, 7:51 AM UTC

flohofwoe wrote: post #50

halayli wrote: post #31

How can this paper be taken seriously when the paper doesn't even show the compilation flags?

Once you go accidentally quadratic, any clever combination of optimization flags or compiler magic becomes quite irrelevant though.

To be fair, certain compilation flags can change the time complexity of some algorithms if the mistake is trivial enough to figure out.

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

#54

Post by WalterBright » Thu, Mar 04, 2021, 8:01 AM UTC

flohofwoe wrote: post #52

WalterBright wrote: post #36

Earlier quoted context omitted.

In C, the value pointed to by `x` cannot be changed via a write through `x`, but if there is another pointer to that value, it can be changed through that. In D, `immutable(int)* x` cannot be changed by any reference to the value.

Isn't that what 'restrict' is for? It's a new type of footgun of course because the compiler doesn't detect if the value is actually accessed through another pointer, but by simply ignoring that possibility via 'restrict', the compiler should have the same optimization opportunities, no?

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

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

#55

Post by flohofwoe » Thu, Mar 04, 2021, 8:09 AM UTC

WalterBright wrote: post #54

flohofwoe wrote: post #52

Earlier quoted context omitted.

Isn't that what 'restrict' is for? It's a new type of footgun of course because the compiler doesn't detect if the value is actually accessed through another pointer, but by simply ignoring that possibility via 'restrict', the compiler should have the same optimization opportunities, no?

> 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 ;)

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

#56

Post by globular-toast » Thu, Mar 04, 2021, 8:10 AM UTC

Why are we back to learning basic computer science? This isn't news to anyone here is it?

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

#57

Post by derriz » Thu, Mar 04, 2021, 8:31 AM UTC

Am I missing something? In the paper the definition of cmp3 on page 2 seems to have a bug - as defined, wouldn't cmp3([1,2,3], [1]) return 0?

    # Uses 3-way cmp() for primitives
    def cmp3(a, b):
        if not isinstance(a, list):
            global c; c += 1
            return cmp(a, b) 
        for x, y in zip(a, b):
            r = cmp3(x, y)
            if r != 0: 
                return r 
        return 0

This isn't generally the expected behaviour for comparing lists, surely?

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

#58

Post by mehrdadn » Thu, Mar 04, 2021, 8:36 AM UTC

derriz wrote: post #57

Am I missing something? In the paper the definition of cmp3 on page 2 seems to have a bug - as defined, wouldn't cmp3([1,2,3], [1]) return 0? # Uses 3-way cmp() for primitives def cmp3(a, b): if not isinstance(a, list): global c; c += 1 return cmp(a, b) for x, y in zip(a, b): r = cmp3(x, y) if r != 0: return r return 0 This isn't generally the expected behaviour for comparing lists, surely?

Oh yeah I think you did find a bug, thanks for pointing it out! I need to check the lengths as well. It shouldn't affect the conclusion (in fact I think I made all comparisons equal-length in the paper?) but I should revise it when I get the chance.

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

#59

Post by rav » Thu, Mar 04, 2021, 8:37 AM UTC

derriz wrote: post #57

Am I missing something? In the paper the definition of cmp3 on page 2 seems to have a bug - as defined, wouldn't cmp3([1,2,3], [1]) return 0? # Uses 3-way cmp() for primitives def cmp3(a, b): if not isinstance(a, list): global c; c += 1 return cmp(a, b) for x, y in zip(a, b): r = cmp3(x, y) if r != 0: return r return 0 This isn't generally the expected behaviour for comparing lists, surely?

Seems like you can fix this by changing return 0 to return cmp(len(a), len(b)).

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

#60

Post by [deleted] » Thu, Mar 04, 2021, 8:40 AM UTC

cbsmith wrote: post #45

tachyonbeam wrote: post #19

Earlier quoted context omitted.

Compiler engineer here. In practice, compilers for higher-level languages often have a lot of difficulty getting anywhere close to the efficiency of comparable C code. If you take Python, for example, you have to do a lot of inlining to eliminate various abstractions. Inlining is actually non-trivial. Yes, inlining, by itself, is an easy program transformation, but knowing where to inline to get the best performance…

The sufficiently smart compiler is effectively unobtanium, but that presents a challenge for C as well. C has its own challenges with its memory model & language semantics. C never was the lowest level of abstraction; there are other abstraction models out there and more still to be invented no doubt. C's model did well (though struggled mightily against Fortran for the longest time) at aligning with processor models…

[deleted]