5 ms·

In general terms, how is it possible to beat really optimized C code? In particular, what property of Haskell or any other functional language would make that p

In general terms, how is it possible to beat really optimized C code? In particular, what property of Haskell or any other functional language would make that possible (in theory or practice).

hoseja 7y ago
Here, it's apparently FEARLESS CONCURRENCY
ummonk 7y ago
The C code is not particularly optimized, but more importantly, C being a low level language makes writing multi-threaded programs much more work. wc though cannot make use of multi-threading regardless because it must have the ability to work on streams, not just seekable files, as the haskell code here does.
- Annatar 7y ago
  C is a high level language with capability of low level access: we regularly made fun of C programmers in high school (like my math teacher) because they didn't know how to code in assembler and had to write abstract high level code in C, in order for the compiler to do it for them. The biggest brouhaha was always disassembly of "optimized" machine code generated by the C compiler, full of needless stack twiddling and housekeeping code, wasting hundreds or even thousands of CPU cycles on what amounts to useless abstractions. That's nonsense one finds only in a high level language. But it's always super for a good brouhaha!
  - ummonk 7y ago
    We've long since moved on from an era when anything above assembly could be considered high level. And the performance difference between idiomatic C code compiled with -O3 (to inline functions and minimize the stack twiddling and housekeeping code) and handwritten straightforward assembly is low enough as to be negligible. Not so with, say, Haskell vs C.
    - Annatar 7y ago
      Neither is true. Well, the first might be true for you in your mind, but doesn't change the fact that C is a high level language modelling an abstract system, and providing that model through its standard libraries (which is what makes it possible to write portable code). And the second with -O3 could not be more wrong, and I can prove it: compile anything with gcc -S -O3 and behold the extra code which a human would never write because it's unnecessary.
      - tom_mellior 7y ago
        > I can prove it: compile anything with gcc -S -O3 and behold the extra code which a human would never write because it's unnecessary. Since you claim that that's true for "anything", care to show us an example consisting of a 5-10 line C function and your assembly version?
        Annatar 7y ago
        Considering I wrote above exactly what to do (gcc -S), I believe you are not making this request in good faith; rather, you seek to test whether I know what I'm writing about. However, had you done what I told you to do, you wouldn't have asked. That's why I think you are actually trolling me.
        tom_mellior 7y ago
        Input code: float dot_product(float *a, float *b, int n) { float result = 0.0f; for (int i = 0; i < n; i++) { result += a[i] * b[i]; } return result; } Output from gcc -O3 -S: .file "foo.c" .text .p2align 4,,15 .globl dot_product .type dot_product, @function dot_product: .LFB0: .cfi_startproc testl %edx, %edx jle .L4 leal -1(%rdx), %eax pxor %xmm0, %xmm0 leaq 4(,%rax,4), %rdx xorl %eax, %eax .p2align 4,,10 .p2align 3 .L3: movss (%rdi,%rax), %xmm1 mulss (%rsi,%rax), %xmm1 addq $4, %rax cmpq %rax, %rdx addss %xmm1, %xmm0 jne .L3 rep ret .p2align 4,,10 .p2align 3 .L4: pxor %xmm0, %xmm0 ret .cfi_endproc .LFE0: .size dot_product, .-dot_product .ident "GCC: 7.4.0" .section .note.GNU-stack,"",@progbits Where's the unnecessary code? What does your hand-optimized version look like? Is your hand-optimized version faster than this?
Athas 7y ago
You are always at the mercy of the compiler, unless you use intrinsics or assembly directly (and then it's debatable whether what you are writing is really "C"). C compilers are pretty good, but there are things they cannot do. For example, ISPC[1] is a low-level language that is very similar to C, but which makes it straightforward for the compiler to use vector instructions very aggressively - far more than any existing C compiler would be able to. [1]: https://ispc.github.io/ https://ispc.github.io/
rienbdj 7y ago
In theory, C and assembly will give you the fastest possible implementation. However, in practice, we're just not smart enough to write this code without introducing bugs. High level languages allow us to specify what we want the program to do in a concise form and then allow the compiler and runtime to optimize it for us. This works to varying degrees in reality. A simple example is that pure functions can always be inlined and memoized.
easytiger 7y ago
In this case the answer is: do something entirely different than the program you are comparing it with

In general terms, how is it possible to beat really optimized C code? In particular, what property of Haskell or any other functional language would make that possible (in theory or practice).

hoseja 7y ago

Here, it's apparently FEARLESS CONCURRENCY

ummonk 7y ago

The C code is not particularly optimized, but more importantly, C being a low level language makes writing multi-threaded programs much more work. wc though cannot make use of multi-threading regardless because it must have the ability to work on streams, not just seekable files, as the haskell code here does.

Annatar 7y ago
C is a high level language with capability of low level access: we regularly made fun of C programmers in high school (like my math teacher) because they didn't know how to code in assembler and had to write abstract high level code in C, in order for the compiler to do it for them. The biggest brouhaha was always disassembly of "optimized" machine code generated by the C compiler, full of needless stack twiddling and housekeeping code, wasting hundreds or even thousands of CPU cycles on what amounts to useless abstractions. That's nonsense one finds only in a high level language. But it's always super for a good brouhaha!
- ummonk 7y ago
  We've long since moved on from an era when anything above assembly could be considered high level. And the performance difference between idiomatic C code compiled with -O3 (to inline functions and minimize the stack twiddling and housekeeping code) and handwritten straightforward assembly is low enough as to be negligible. Not so with, say, Haskell vs C.
  - Annatar 7y ago
    Neither is true. Well, the first might be true for you in your mind, but doesn't change the fact that C is a high level language modelling an abstract system, and providing that model through its standard libraries (which is what makes it possible to write portable code). And the second with -O3 could not be more wrong, and I can prove it: compile anything with gcc -S -O3 and behold the extra code which a human would never write because it's unnecessary.
    - tom_mellior 7y ago
      > I can prove it: compile anything with gcc -S -O3 and behold the extra code which a human would never write because it's unnecessary. Since you claim that that's true for "anything", care to show us an example consisting of a 5-10 line C function and your assembly version?
      - Annatar 7y ago
        Considering I wrote above exactly what to do (gcc -S), I believe you are not making this request in good faith; rather, you seek to test whether I know what I'm writing about. However, had you done what I told you to do, you wouldn't have asked. That's why I think you are actually trolling me.
        tom_mellior 7y ago
        Input code: float dot_product(float *a, float *b, int n) { float result = 0.0f; for (int i = 0; i < n; i++) { result += a[i] * b[i]; } return result; } Output from gcc -O3 -S: .file "foo.c" .text .p2align 4,,15 .globl dot_product .type dot_product, @function dot_product: .LFB0: .cfi_startproc testl %edx, %edx jle .L4 leal -1(%rdx), %eax pxor %xmm0, %xmm0 leaq 4(,%rax,4), %rdx xorl %eax, %eax .p2align 4,,10 .p2align 3 .L3: movss (%rdi,%rax), %xmm1 mulss (%rsi,%rax), %xmm1 addq $4, %rax cmpq %rax, %rdx addss %xmm1, %xmm0 jne .L3 rep ret .p2align 4,,10 .p2align 3 .L4: pxor %xmm0, %xmm0 ret .cfi_endproc .LFE0: .size dot_product, .-dot_product .ident "GCC: 7.4.0" .section .note.GNU-stack,"",@progbits Where's the unnecessary code? What does your hand-optimized version look like? Is your hand-optimized version faster than this?

Athas 7y ago

You are always at the mercy of the compiler, unless you use intrinsics or assembly directly (and then it's debatable whether what you are writing is really "C"). C compilers are pretty good, but there are things they cannot do. For example, ISPC[1] is a low-level language that is very similar to C, but which makes it straightforward for the compiler to use vector instructions very aggressively - far more than any existing C compiler would be able to. [1]: https://ispc.github.io/ https://ispc.github.io/

rienbdj 7y ago

In theory, C and assembly will give you the fastest possible implementation. However, in practice, we're just not smart enough to write this code without introducing bugs. High level languages allow us to specify what we want the program to do in a concise form and then allow the compiler and runtime to optimize it for us. This works to varying degrees in reality. A simple example is that pure functions can always be inlined and memoized.

easytiger 7y ago

In this case the answer is: do something entirely different than the program you are comparing it with