Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

When Haskell is Faster than C

paulspontifications.blogspot.com

Post reply on HN
Print view View original

101–110 of 119 posts

Re: When Haskell is Faster than C

#101

Post by PaulAJ »

tedunangst wrote: post #59
bcoates wrote: post #56

Earlier quoted context omitted.

If they have the same semantics why doesn't the library do an unboxing implementation for types that support it and not for the rest?

This sounds like exactly the sort of optimization that I'm always hearing a sufficiently smart compiler will make for me.

No, because compilers are prohibited from changing the meaning of the program. Changing a lazy value to a strict value is only permitted when the compiler can prove that the value will always be evaluated. It can't do that for unboxed arrays because that is a global change, so it has to leave it to the programmer.

Re: When Haskell is Faster than C

#102

Post by PaulAJ »

gnuvince wrote: post #92
haberman wrote: post #76

Earlier quoted context omitted.

> Let's be honest: C is no "closer to the metal" than other high level languages This is dead wrong, and your links do not support it. This is exactly the kind of statement that gets me grumpy. Your link illustrates that an aggressive C optimizer can collapse a chunk of C code down to something smaller and simpler than the original code. This is true. But what you said is that C is "no closer to the metal" than other…

The equivalent `plus2` OCaml function compiles to: camlAdd__plus2_1030: .L100: addq $4, %rax ret (It's using 4 instead of 2, because ints are boxed; a 0 in the last bit denotes an int, a 1 denotes an address).

Part of the point of the original article is that not even assembler is "close to the metal" any more. How long does that fragment of assembly code take to execute? Depends on whether the instructions are in the I-cache, whether some previous branch prediction has failed, and whether the data are in the cache. All this adds up to a couple of orders of magnitude.

Re: When Haskell is Faster than C

#103

Post by ay »

jacquesm wrote: post #62
ay wrote: post #60

Earlier quoted context omitted.

Hey Jacques, may ask for a code review ? :-) http://stdio.be/revseq.c Compiled with "gcc -pipe -Wall -O3 -fomit-frame-pointer -std=c99 -pthread" on my Mac, it's about twice as fast at the blog author's version. Time spent: coding: 30 minutes bugfixing: 30 minutes I have a feeling there is some kind of catch in the description of the algorithm in terms of implementing the output, but I for the life of me could not gro…

Sure, I'll pick it up in the post. Neat little project this. I won't peek at your code until I'm done.

Thank you! It was indeed a nice little fun exercise. It is interesting the bugs that I made by being tired and not reading the task carefully/not thinking clearly (yesterday was a bit of a long and stressy day):

1) My initial understanding was that I do need to reverse the order, yet somehow after re-reading the article I understood the order does not need to change, and the "reverse" in the name is some kind of jargon. This is quite stupid, and probably not worth mentioning, if only to prove I was tired :)

2) missing that the first iteration of the "business logic" code in my case happens before anything is filled in. Crash.

3) forgetting about the "\n"s - with rather funny "partially correct" output effect.

Very much looking forward to see your code !

Re: When Haskell is Faster than C

#104

Post by ay »

alayne wrote: post #22
Xcelerate wrote: post #17

Hmm... it seems to me that whenever any article is posted that claims "X is faster than C", there are immediately 40 replies saying "Well, the author's C is horrible. If I wrote that, it would be much different." Okay, as someone who has NOT been programming in C 8 hours a day for years on end, I would actually like to see somebody do this -- to show me what GOOD C looks like. So if someone wouldn't mind, could you t…

There already is an efficient multithreaded C version on the shootout site. I don't know if that's what people would consider good production code, but at least it isn't laughably bad. http://benchmarksgame.alioth.debian.org/u32/program.php?test...

On my 64-bit MBP, this program does not terminate - at least not within the 3 minutes I allowed it to run. (the blog article's one completes within 4 seconds, so I thought 60-fold slack is enough).

I did not debug it though.

Re: When Haskell is Faster than C

#105

Post by _dps »

haberman wrote: post #98
_dps wrote: post #84

Earlier quoted context omitted.

Seconded. I'd add that languages like Python hide an enormous amount of not-close-to-the-metal-ness in every single statement, because every single statement has the implicit context "Interpreter, please interpret this string relative to your potentially complex internal state". Haskell is only slightly less prone to this, despite being compiled, since every expression by default becomes a request to instantiate a th…

Could you explain your second paragraph in a bit more detail? I feel you have honed in on a deep and significant pont, but my passing understanding of Haskell isn't allowing me to fully understand it. In particular, what would it look like if you were avoiding instantiating thunks?

Very crudely (Haskell experts please chime in!):

Every Haskell program is a lazily-evaluated tree of expressions; the program output itself is the root node and links represent data flow dependencies. The Haskell compiler turns source code into an initial representation of this tree as well as machine code that performs a sequence of reduction steps to turn the tree into a final output value. So a tree node at any given time is either a concrete value, or a chunk of code that can be executed to obtain that value (a thunk).

The compiler has the right to choose an arbitrary (semantics-preserving) node evaluation sequence to reduce the tree down to the final result.

Through strictness annotations (http://www.haskell.org/haskellwiki/Performance/Strictness#Ev...) you can force particular subtrees to be fully evaluated whenever-in-program-execution their parent node begins evaluation; to programmers in other languages this seems alien, but in Haskell you, by default, turn control of operation sequencing to the compiler.

Such annotations are sometimes desirable because the thunk representation of, say, a large chain of arithmetic operations on a list of numbers can be very expensive in memory, so one might want to force it to be reduced down to a concrete double as soon as possible (see, e.g., http://benchmarksgame.alioth.debian.org/u32/program.php?test..., and note all the areas where function arguments are preceded by exclamation points; those are strictness annotations).

Strictness annotations are often important for getting good performance out of certain kinds of Haskell code, and are in some cases not just important but essential for controlling memory consumption.

It can be very hard for non-experts to reason about where and why to use strictness, and I submit that this is because you're essentially doing an indirect second level of programming. The un-annotated source code describes the value-transformation semantics, while the strictness annotations are a side-band language for controlling the tree-evaluator that is embedded into your compiled program.

Hope that helps :)

Re: When Haskell is Faster than C

#106

Post by haberman »

_dps wrote: post #105
haberman wrote: post #98

Earlier quoted context omitted.

Could you explain your second paragraph in a bit more detail? I feel you have honed in on a deep and significant pont, but my passing understanding of Haskell isn't allowing me to fully understand it. In particular, what would it look like if you were avoiding instantiating thunks?

Very crudely (Haskell experts please chime in!): Every Haskell program is a lazily-evaluated tree of expressions; the program output itself is the root node and links represent data flow dependencies. The Haskell compiler turns source code into an initial representation of this tree as well as machine code that performs a sequence of reduction steps to turn the tree into a final output value. So a tree node at any gi…

Thanks for writing this up!

Re: When Haskell is Faster than C

#107

Post by haberman »

hosay123 wrote: post #97
haberman wrote: post #76

Earlier quoted context omitted.

> Let's be honest: C is no "closer to the metal" than other high level languages This is dead wrong, and your links do not support it. This is exactly the kind of statement that gets me grumpy. Your link illustrates that an aggressive C optimizer can collapse a chunk of C code down to something smaller and simpler than the original code. This is true. But what you said is that C is "no closer to the metal" than other…

While a fan of your original comment, I think the logic got a little flaky here. Claiming any language is 'close to the metal' is to make implicit reference to particular implementations of said language. In recent years there has been an explosion in the use of techniques that have levelled this old distinction. For example today it is quite possible to have Javascript OO code that runs more efficiently than, say, c…

This sounds like the Sufficiently Smart Compiler line of reasoning that was supposed to make Itanium the architecture of the future and has been forecast to make high-level languages faster than C any day now. In practice, the extra costs imposed by high-level languages (and in particular, the loss of memory management control) have outweighed the benefit of extra high-level information consistently for decades. And I see no reason why this will change.

In particular, the the optimizing VMs you are describing still have to be written in something. The proof is in the pudding: no serious language runtime is written in anything other than C or C++. The argument that C is being displaced will be an empty one until you start to see language runtimes being written in something else.

(Just to clarify, since another commenter missed this distinction earlier: I'm talking specifically about VMs/runtimes, not ahead-of-time compilers. Compilers are frequently written in non-C languages because an ahead-of-time transformation doesn't have the same stringent efficiency and resource usage requirements that language runtimes do).

Re: When Haskell is Faster than C

#108

Post by igouy »

ay wrote: post #104
alayne wrote: post #22

Earlier quoted context omitted.

There already is an efficient multithreaded C version on the shootout site. I don't know if that's what people would consider good production code, but at least it isn't laughably bad. http://benchmarksgame.alioth.debian.org/u32/program.php?test...

On my 64-bit MBP, this program does not terminate - at least not within the 3 minutes I allowed it to run. (the blog article's one completes within 4 seconds, so I thought 60-fold slack is enough). I did not debug it though.

64-bit Ubuntu -- 0.7s

http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...

Re: When Haskell is Faster than C

#109

Post by ay »

igouy wrote: post #108
ay wrote: post #104

Earlier quoted context omitted.

On my 64-bit MBP, this program does not terminate - at least not within the 3 minutes I allowed it to run. (the blog article's one completes within 4 seconds, so I thought 60-fold slack is enough). I did not debug it though.

64-bit Ubuntu -- 0.7s http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...

I know it works on Ubuntu 64-bit. :-) Just that it appears to be hanging on MacOS 64-bit. The algorithms like this one should hardly have such a catastrophic failure - that's why I am curious if someone else can replicate it hanging on MacOS.

BTW, on 8-core Ubuntu box with 32Gb RAM, my silly half-an-hour hack from yesterday - http://stdio.be/revseq.c - still outperforms this one and completes in 60% of time. So I am getting more and more convinced that either I did not get the spec right while writing it.. Or that I should submit it :-)

EDIT: If you have a chance to give it a whirl alongside, could be fun to compare your results with mine...

Re: When Haskell is Faster than C

#110

Post by srean »

DannyBee wrote: post #88
Yttrill wrote: post #70

I'm afraid the argument that C+ASM is always faster is flawed in reality. Pure ASM, with a bit of C thrown in, maybe, but this is just as impractical for complex codes as C itself is. It is well known that for numerical codes Fortran beats the pants off C. Why is this? Because the structure of C programs proves difficult to optimise automatically. Indeed the C committee attempted to address one of the main problems b…

It's not actually the structure of C programs, it's the guarantees the language offers. So only about the first paragraph of your rant is right. Fortran had almost no memory aliasing, explicit global accesses, and offered almost unbridled implementor freedom. As long as the operations got done, it didn't care what happened behind the scenes. None of the rest of the things you talk about matter when it comes to optimi…

Lots of interesting information. However, I think you over-reacted about Fortran. After reading the parent comment and your comment it seems both of you are saying the same thing: Fortran has the advantage of having no pointer aliasing.

Regarding unification based algorithms, do microsoft use any of it in their F# compiler. I ask because they have time to time tried to say we wont sue you for F# technology. Dont know how much of those sweet nothings are binding. Given your knowledge about compilers and legal systems I am very curious to hear your opinion.

Post reply on HN